Матрица элементарных преобразований

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

1. Подстановка строк i и j эквивалентна умножению слева на матрицу, которая получается из единичной матрицы подстановкой i и j строк.

2. Умножение строки i на число a эквивалентно умножению слева на матрицу, отличающейся от единичной только одним элементом, стоящим на пересечении i строки и столбца и равного a.

3. Прибавление к i-ой строке j-ой, умноженной на число a равно сильно умножению слева матрицу, отличающейся от единичной только элементом, стоящим на пересечении i-ой строки и j-го столбца и равного a.

Аналогично, преобразования над столбцами матрицы эквивалентны умножению справа на матрицы элементарных преобразований.

Построение обратной матрицы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Определение 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. Тогда , что и требовалось доказать.

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

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

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

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

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

Линейные пространства.

Определение 7.1Множество V называется линейным пространством над числовым полем P, если определены две операции

1. сложения элементов из V (+)

2. умножения элемента из V на элемент из P (*)

Эти операции удовлетворяют аксиомам:

1. ассоциативность сложения, т.е. (x+ y)+ z= x+(y+ z)

2. коммутативность сложения, т.е. x+ y= y+ x

3. существование 0, т.е. x+0=x

4. существование обратного x+ y=0, обратный обозначают – x.

5. ассоциативность умножения .

6. Дистрибутивность

7. Дистрибутивность

8. умножение на 0 0 x=0. (в правой части 0 – элемент из V)

9. умножение на 1; 1x=x

Элементы линейного пространства называются векторами, а элементы числового поля P – скалярами.

Примеры линейных пространств.

1. Множество непрерывных функций над R

2. Множество векторов пространства над R

3. Арифметическое пространство (множество наборов из n чисел из P)

Определение 7.2Подмножество W линейного пространства V над полем P называется подпространством, если оно является пространством (в смысле выполняются все аксиомы)

Теорема 7.1. Для того, что бы подмножество W линейного пространства V над числовым полем P являлось подпространством необходимо и достаточно выполнения двух условий:

Примеры подпространств:

1. Множество многочленов образует подпространство в пространстве всех функций.

2. Множество решений системы линейных уравнений Ax=0 в арифметическом пространстве

3. Плоскость, прямая в пространстве векторов.

4. Линейная оболочка системы векторов (то есть множество всех линейных комбинаций векторов)

Следствие 7.1. Пересечение линейных подпространств является подпространством

Доказательство заключается в проверке выполнений условий Теорема 7.1.

Определение 7.3 Суммой подпространств V+W называется множество векторов вида

Следствие 7.2 Сумма подпространств – подпространство.

Доказательство заключается в проверке выполнений условий Теорема 7.1.

Следствие 7.3 Сумма подпространств V+W – наименьшее подпространство, которое содержит как V так и W.

Доказательство. Обозначим через F подпространство, являющееся пересечением всех подпространств содержащих подпространства V и W. Так как V+W содержит оба этих подпространства, то . Поскольку F содержит как V так и W, и является подпространством (Следствие 7.1), то сумма векторов x+y, где и , принадлежит F. Таким образом, установлено включение . Объединяя включения, получаем равенство V+W=F.