Блочные матрицы и формула обращения Фробениуса: разделяй и властвуй

Алгебра блочных матриц

Замечательное свойство блочных матриц заключается в том, что с ними можно производить алгебраические операции точно так же, как и с обычными числовыми матрицами, при условии, что размеры блоков согласованы (совместимы). Если мы складываем две блочные матрицы одинаковой структуры, мы просто складываем их соответствующие блоки. Самое интересное происходит при умножении: если столбцы первой матрицы разбиты точно так же, как строки второй, то при умножении мы применяем стандартное правило «строка на столбец», но в качестве элементов выступают не числа, а целые матрицы. Единственное, о чем нельзя забывать — это некоммутативность матричного умножения (при умножении блоков A*B нельзя менять их местами B*A, в отличие от умножения чисел).

Блочно-диагональные и треугольные матрицы

Особую ценность представляют блочные матрицы специального вида. Блочно-диагональная матрица (имеющая квадратные блоки на главной диагонали и нули во всех остальных позициях) ведет себя как набор абсолютно независимых подсистем. Чтобы найти ее определитель, достаточно перемножить определители ее блоков. Чтобы обратить такую матрицу, нужно просто обратить каждый блок на диагонали по отдельности. Это свойство используется в параллельном программировании: гигантская задача разрезается на сотни независимых кусков, которые решаются одновременно. Для блочно-треугольных матриц (нули стоят только ниже или выше блочной диагонали) определитель также равен произведению определителей диагональных блоков, что критически важно при анализе спектров сложных систем дифференциальных уравнений.

Дополнение Шура (Schur Complement)

Ключевым инструментом при работе с матрицами, разбитыми на четыре блока (размерностью 2x2 в блочном смысле), является Дополнение Шура. Пусть матрица M состоит из блоков A (верхний левый), B (верхний правый), C (нижний левый) и D (нижний правый). Если блок A квадратный и невырожденный, мы можем алгебраически «исключить» его из системы (подобно методу Гаусса для блоков). Величина S = D - C * A^(-1) * B называется дополнением Шура блока A в матрице M. Это дополнение хранит в себе информацию о структуре всей оставшейся части системы после исключения первой группы переменных. Определитель всей огромной матрицы M элегантно вычисляется как произведение: det(M) = det(A) * det(S). Дополнение Шура повсеместно применяется в теории вероятностей (для вычисления условных гауссовских распределений) и в методах оптимизации.

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

Опираясь на концепцию дополнения Шура, немецкий математик Фердинанд Георг Фробениус (а также Исай Шур и Томас Банахевич) вывели аналитическую формулу для обращения произвольной невырожденной матрицы, разбитой на 4 блока. Формула Фробениуса показывает, что обратная матрица M^(-1) также будет состоять из четырех блоков. Нижний правый блок будет в точности равен S^(-1) (обратному дополнению Шура). Остальные три блока выражаются через комбинации A^(-1), B, C и S^(-1). Практическое значение этой формулы колоссально: она позволяет обратить матрицу размера, скажем, 2000x2000, путем обращения только двух матриц размера 1000x1000. Поскольку вычислительная сложность обращения кубична (O(n^3)), разбиение задачи пополам ускоряет общее время вычислений почти в 4 раза!