Рекурсивный метод обращения матриц общего вида

Автор: О. Федор

Описан метод обращения матриц общего вида с выводом необходимых формул.
Приложена c++ функция, реализующая метод.

Достоинства метода:
Минимальное число сравнений, обращенная матрица лежит на месте исходной (экономия памяти).
Вычислительные затраты O(n^3).

Идея метода вызрела 2 года назад при обсуждении топика.

Для решения задачи представим исходную матрицу A размером n x n в виде блочной
                                                                                              (1)
где    -  матрица размером (n-1) x (n-1)
          - вектор-столбец, размером 1 x (n-1)
          - вектор-строка, размером (n-1) x 1
          - скаляр
Требуется найти обратную к A матрицу B
                                                                                                          (2)
Представим матрицу B также в виде блочной
                                                                                                          (3)
где      -  матрица размером (n-1) x (n-1)
            - вектор-столбец, размером 1 x (n-1)
          - вектор-строка, размером (n-1) x 1
          - скаляр
Очевидно, что произведение A и B будет равное еденичной матрице:
             
или
                            (4)
отсюда для блоков можно записать следующие равенства
                                                                                        (5a)
                                                                                        (5b)
                                                                                                    (5c)
                                                                                                      (5d)
Рассмотрим систему из (5a) и (5b)
                 
Умножив первое из этих уравнений на , а второе на вектор , получим
                 
поскольку  скаляр, то
                 
и поэтому можно из первого уравнения вычесть второе
                 
разделив результат на скаляр , получим
               
из которого следует
                                                                                                  (6)
Разрешим (5b) относительно
                                                                                                              (7)
Рассмотрим систему из (5c) и (5d)
                 
Умножив первое из этих уравнений на , а второе на вектор  , получим
                 
поскольку скаляр, то
                 
поэтому можно из первого уравнения вычесть второе
                 
разделив результат на скаляр , получим
                 
из этого уравнения следует
                 
Заметим, что
                 
поэтому
                                                                                                              (8)
Разрешив (5d) относительно  , получим
                                                                                                      (9)
Итак, выражения для определения значений блоков в матрице B:
                                              (10)
Заметим, что здесь вычисление матрицы B размером n x n сводится к обращению матрицы , размером (n-1) x (n-1) и умножению  на векторы. Численно этот метод можно реализовать в виде рекурсивного алгоритма.

Легко оценить затраты метода на вычисления. В выражении (10) справа дана оценка числа умножений для одной итерации, отсюда следует оценка общего числа умножений в случае выполнения всех рекурсивных вызовов:
                 
Таким образом, метод имеет обычную для прямых методов стоимость O(n^3).

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

В случае симметричной исходной матрицы A, матрица   будет также симметричной и потому может быть записана в виде суммы нижней треугольной матрицы , диагональной и верхней треугольной
                 
также будет выполняться
               
Обратная к A матрица B будет также симметричной и потому также может быть записана в виде суммы нижней треугольной матрицы , диагональной и верхней треугольной
               
С использованием этих обозначений выражения (10) можно переписать для частного случая симметричных матриц  A  и B:
                                    (11)
При практической реализации этого метода как матрицу A так и B можно хранить в линейных масивах размером .

Приложение: Рекурсивная функция обращения матрицы общего вида