рефераты конспекты курсовые дипломные лекции шпоры

Раздел Математика
/
Блочные матрицы

Реферат Курсовая Конспект

Выберите учебное заведение

Блочные матрицы

Блочные матрицы - раздел Математика, Числа. Метод математической индукции. Целые числа. Рациональные числа. Многочлены. Операции над многочленами. Корень многочлена Напомним, Матрица – Таблица Чисел. Часто Полезно Рассматривать Матрицу Как Та...

Напомним, матрица – таблица чисел. Часто полезно рассматривать матрицу как таблицу, элементами которой являются не числа, а матрицы меньших порядков. При такой точке зрения говорят о блочном строении матрицы. Использование блочного строения матриц позволяет строить более эффективные алгоритмы.

Теорема 6.3. Умножение блочных матриц.

Пусть матрицаAимеет блочное строение , а матрицаBимеет блочное строение , причем размеры блоков согласованы так, что существует произведение при любыхi,j,r. Тогда произведение матрицC=ABбудет иметь блочное строение , причем . Последнее выражение имеет такой же вид, как если бы умножали матрицы с числовыми элементами.

Доказательство. Элемент блочной матрицы A, расположенный в блоке на пересечении строки r и столбца s обозначим через . По определению произведения матриц, имеем , где - количество столбцов в блоке (по условиям теоремы это число совпадает с количеством строк блока ). Сумма является элементом матрицы , расположенным на пересечении строки r и столбца s. Следовательно, , что и требовалось доказать.

Использования блочного представления матриц позволяет получать более эффективные алгоритмы для решения задач линейной алгебры.

6.5.1 Алгоритм Штрассена

Использование правил блочного произведения матриц позволяет уменьшить общее количество операций, а значит, и время выполнения работы программы. Допустим, требуется умножить квадратные матрицы A и B порядка . При перемножении матриц, по формулам, приведённым в определении произведения, потребуется умножений и сложений. Разобьём матрицы A и B на блоки порядка n. Вычисление произведения блочных матриц проведём по формулам Штрассена

потребуется умножений и сложений
потребуется умножений и сложений
потребуется умножений и сложений
потребуется умножений и сложений
потребуется умножений и сложений
потребуется умножений и сложений
потребуется умножений и сложений
потребуется сложений
потребуется сложений
потребуется сложений
потребуется сложений.

Всего, для вычисления произведения матриц по формулам Штрассена, потребуется операций сложения и умножения. При выполнении неравенства (n>7) формулы Штрассена приводят к меньшему объёму вычислений. Выигрыш в числе операций будет увеличиваться, если при вычислении произведения матриц (шаги1-7) использовать ту же схему.

Обозначим через число операций сложения и умножения, используемых при умножении матриц n-го порядка по формулам Штрассена. Справедлива рекуррентная формула . Положим . Тогда , далее, свернём сумму по формуле суммы членов геометрической прогрессии и заметим. В результате получим . Подставив вместо k его выражение через n () получим ( ).

6.5.2 Кронекерово произведение

Определение 6.3Пусть и - прямоугольные матрицы соответственно размеров и . Кронекеровым произведением называется матрица размеров следующего блочного строения .

Приведем основные свойства кронекерова произведения матриц.

Свойство 6.2. Пусть и , тогда .

Доказательство следует из правила блочного произведения матриц.

Свойство 6.3. Пусть существуют и , тогда .

Доказательство. По доказанному ранее (Свойство 6.2), имеем . Из полученного равенства вытекает требуемое утверждение.

Свойство 6.4. .

Доказательство следует из определения операций кронекерова произведения и транспонирования матриц.

Свойство 6.5. Пусть - квадратная матрица порядка , а - квадратная матрица порядка , тогда .

Доказательство. Если матрица A имеет верхний треугольный вид, то утверждение получается последовательным разложением определителя по теореме Лапласа по первым m столбцам. Если матрица A имеет нижний треугольный вид, то утверждение получается последовательным разложением определителя по теореме Лапласа по первым m строкам. Рассмотрим случай, когда матрица A не треугольная. Элементарными преобразованиями со строками (а именно, подстановкой строк и прибавлением к одной строки, другой строки умноженной на число) приведём матрицу A к треугольному виду T. Тогда , где - матрица элементарных преобразований. Имеет место равенство , из которого выводим . Поскольку T – треугольная матрица, то . Матрица элементарного преобразования , если она соответствует прибавлению к некоторой строке другой строки, умноженной на число, имеет треугольный вид, и, значит . Если матрица элементарного преобразования соответствует подстановке двух строк, то . Таким образом, . Для доказательства утверждения осталось заметить равенство .

Следствие 6.2. .

Доказательство проведём индукцией по n. Положим и . При n=2 имеем , т.е. утверждение верно. Пусть оно справедливо при n-1. Тогда , что и требовалось доказать.

6.5.3 Формула Фробениуса

Пусть матрица A имеет блочный вид . Припишем к ней справа единичную матрицу и найдём обратную к матрице A. Для этого выполним следующие действия:

Умножим (слева) на матрицу (конечно в предположении существования обратной матрицы). В результате получим матрицу .
Вычтем из второй блочной строки первую, умноженную на матрицу (на языке матриц мы умножим слева на матрицу ). В результате получится матрица .
Умножим слева на матрицу . В результате получим матрицу
Вычтем из первой блочной строки вторую, умноженную на матрицу (т.е. умножим слева на матрицу ). В результате получится матрица

Тем самым найдена обратная матрица к матрице A. Формула называется формулой Фробениуса. Использование формулы Фробениуса позволяет уменьшить количество арифметических операций при вычислении обратной матрицы.

Обозначим через и число арифметических операций необходимых, соответственно, для обращения и умножения матриц n-го порядка. Имеет место рекуррентная формула . Положим , тогда при умножении матриц по формулам Штрассена . Применив формулу k раз (учитывая ) получим . Подставив вместо k его выражение через n () получим .

Развернуть

Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

Числа. Метод математической индукции. Целые числа. Рациональные числа. Многочлены. Операции над многочленами. Корень многочлена

Числа Натуральные числа натуральное число Если n... Метод математической индукции... Тот факт что множество натуральных чисел может быть упорядочено по возрастанию часто используется при доказательстве...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Блочные матрицы

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Натуральные числа
Определение 1.1Определение натуральных чисел N 1 - натуральное число. Если n - натуральное число, то следующее за ним n+1 так же натуральное число. Если кодировать натуральное число количе

Бином Ньютона, треугольник Паскаля
Рассмотрим бином (a+b)n. Если раскрыть скобки, привести подобные, то получившиеся сумма состоит из слагаемых вида aibn-i с некоторыми числовым

Числовые кольца, поля
Множество чисел, замкнутых относительно операции +, *, и в котором разрешимо уравнение a+x=b называется числовым кольцом. Любое числовое кольцо содержит 0. Множество чётных чисел

Поле комплексных чисел
Положим . Числа вида , где

Комплексная плоскость.
Комплексному числу c поставим в соответствие точку плоскости c координатами (Re(c),Im(c)). Это соответствие взаимно однозначное. Для вектора, соединяющего начало

Извлечение корней, корни из единицы
Из комплексного числа существует ровно n корней степени n. Справедливо . Если

Вычисление формул специального вида
1.7.3.1 Вычисление формул вида Введём комплексное число

Делимость многочленов. Наибольший общий делитель. Алгоритм Евклида. Расширенный алгоритм Евклида.
Рассматриваются многочлены над числовым полем. Говорят, что многочлен f(x) делится на многочлен g(x), если остаток от деления равен нолю. Для пары многочленов

Неприводимый многочлен, его свойства
Многочлен называется неприводимым над числовым полем, если он не делится на многочлены меньшей степени (исключая константы) Теорема 2.7 Пусть многочлен f(x) неприводим. Тогда

Интерполяционный многочлен
Под задачей интерполяции понимают задачу построения многочлена наименьшей степени, который в заданных точках принимает заданные значения. 2.6.1 Интерполяционный многочлен в

Свойство 3
Если степень многочлена f(x) равна n, то разность порядка k есть многочлен степени n-k при n

Разложение многочлена над полем рациональных чисел
2.7.1 Примитивный многочлен, его свойства Определение 2.2Многочлен над кольцом целых чисел называется примитивным, если наибольший общий делитель его коэф

Присоединение корня. Поле разложения многочлена.
Пусть f(x) - неприводимый многочлен степени n над числовым полем P, и пусть корень этого многочлена в некотором числовом поле T (P содержитс

Формальная производная, ее свойства
Многочлен f(x+y)-f(x) делится на y без остатка (проверить по теореме Безу). Положим . Многочлен F(

Интерполяционный многочлен Лагранжа-Сильвестра
В ряде случаев необходимо найти многочлен наименьшей степени, у которого на некотором множестве заданы не только его значения, но и значения производных до определенных порядков. Пусть на множестве

Симметрические полиномы
Определение 2.4Многочленом от n переменных называется функция вида . Степенью многочлена называется максимальная суммарная степень по всем п

Основная теорема Алгебры
Лемма 2.5. Многочлен нечётной степени с вещественными коэффициентами имеет хотя бы один вещественный корень. Доказательство. Не нарушая общности можно считать старший коэффициент мн

III. Последний многочлен не имеет вещественных корней.
IV. Если в окрестностях корня a многочлена сам многочлен возрастает, то , а

Метод Гаусса решения системы линейных уравнений
Ряд задач алгебры приводит к задаче построения решения системы линейных уравнений. Например, вычисление коэффициентов интерполяционного многочлена методом неопределённых коэффициентов. В общем виде

Равносильные преобразования
Обозначим через M множество решений системы линейных уравнений (элементами множества M являются n-элементные наборы, удовлетворяющие системе линейных уравнений). Преобразование системы линейных ура

Подстановки
Определение 4.1. Подстановкой n-го порядка называется взаимно однозначное отображение множества чисел от 1 до n на себя. Подстановки можно записывать в виде таблицы, где под каждым числом

Четность подстановок
Дискриминантом называется многочлен от n переменных . Квадрат дискриминанта является симметрическим многочленом. Следовательно, при подстано

Свойства определителя
Разберем свойства определителей. Замену строк матрицы на ее столбцы назовем операцией транспонирования и обозначим через .

Определитель Вандермонда
Пусть даны числа . Матрицей Вандермонда называется матрица, у которой на пересечении i-го столбца и j-ой строки расположен элемент, равный

Теорема Лапласа
Определение 5.2. Пусть и множества номеров строк и столбцов матрицы A, соответствен

Формула Бине-Кощи
Теорема 5.2 (Бине-Коши). . Пусть A матрица размерами m*n, а B матрица размерами n*m (n больше либо равно n). Справедливо равенство , где

Обратная матрица
Квадратная матрица n-го порядка, у которой по диагонали 1, а все остальные элементы 0, называется единичной и обозначается E. Для любой матрицы A справедливы равенства AE=EA=A. Таким образ

Правило Крамера
Рассмотрим систему линейных уравнений Ax=b, где матрица A невырожденная. Умножим слева это равенство на обратную матрицу, придем к равенству

Матрица элементарных преобразований
Элементарные преобразования матрицы A, такие как подстановка строк; прибавление к одной строке другой строки, умноженной на число; умножение строки на число можно трактовать как умножение матрицы A

Построение обратной матрицы
Пусть A невырожденная матрица. Рассмотрим задачу построения обратной матрицы. Припишем справа к матрице A единичную матрицу. Элементарными преобразованиями строк добьемся, что бы на месте матрицы A

Линейные пространства.
Определение 7.1Множество V называется линейным пространством над числовым полем P, если определены две операции 1. сложения элементов из V (+) 2. умножени

Линейная зависимость. Теорема о замене. Ранг системы.
Определение 7.4. Система векторов называется линейно зависимой, если существуют числа

Конечномерные пространства. Базис. Размерность. Дополнение до базиса. Базис суммы, пересечения.
Определение 7.9. Пространство называется конечномерным, если оно является линейной оболочкой конечной системы векторов. Теорема 7.3. Подпространство конечномерного пространства – конечноме

Прямая сумма подпространств. Проекция.
Определение 7.12 Сумма подпространств и называется прямой, если

Изменение координат вектора при изменении базиса.
Пусть в пространстве V заданы два базиса: и . Координаты вектора x в этих базисах

Изоморфизм линейных пространств.
Определение 7.13 Линейные пространства над числовым полем P называются изоморфными, если существует взаимно однозначное соответствие между векторами этих пространств, сохраняющее операции сложения

Ранги матрицы.
Для матрицы можно дать три определения ранга: 1. Столбцовый ранг - ранг системы столбцов. 2. Строчечный ранг - ранг системы строк. 3. Минорный ранг - Порядок наибольшего

Общее решение системы линейных уравнений.
Теорема 7.12. Размерность пространства решений однородной СЛУ равна n-rgA. Доказательство. Рассмотрим однородную систему линейных уравнений Ax=0. Множество решений системы

Двойственное пространство
Пусть V – линейное пространство над полем P. Линейной формой (функцией) над V называется функция, удовлетворяющая условиям

Взаимное расположение линейных многообразий в пространстве.
С помощью рангов соответствующих матриц можно определить взаимное расположение подпространств из некоторого пространства. При этом определённую пользу принесёт следующая теорема. Теорема 7