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

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

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

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

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

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

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

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

  1. потребуется умножений и сложений
  2. потребуется умножений и сложений
  3. потребуется умножений и сложений
  4. потребуется умножений и сложений
  5. потребуется умножений и сложений
  6. потребуется умножений и сложений
  7. потребуется умножений и сложений
  8. потребуется сложений
  9. потребуется сложений
  10. потребуется сложений
  11. потребуется сложений.

Всего, для вычисления произведения матриц по формулам Штрассена, потребуется операций сложения и умножения. При выполнении неравенства (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 () получим .