Войти
Вычислительная гидроСтатьи

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

Автор:

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

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

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

Для решения задачи представим исходную матрицу A размером n x n в виде блочной
          image001 | Рекурсивный метод обращения матриц общего вида                                                                                    (1)
где    image004 | Рекурсивный метод обращения матриц общего вида-  матрица размером (n-1) x (n-1)
          image003 | Рекурсивный метод обращения матриц общего вида- вектор-столбец, размером 1 x (n-1)
          image008 | Рекурсивный метод обращения матриц общего вида - вектор-строка, размером (n-1) x 1
          image005 | Рекурсивный метод обращения матриц общего вида- скаляр
Требуется найти обратную к A матрицу B
          image012 | Рекурсивный метод обращения матриц общего вида                                                                                                (2)
Представим матрицу B также в виде блочной
          image007 | Рекурсивный метод обращения матриц общего вида                                                                                                (3)
где    image016 | Рекурсивный метод обращения матриц общего вида  -  матрица размером (n-1) x (n-1)
          image018 | Рекурсивный метод обращения матриц общего вида  - вектор-столбец, размером 1 x (n-1)
          image020 | Рекурсивный метод обращения матриц общего вида - вектор-строка, размером (n-1) x 1
          image022 | Рекурсивный метод обращения матриц общего вида - скаляр
Очевидно, что произведение A и B будет равное еденичной матрице:
          image024 | Рекурсивный метод обращения матриц общего вида   
или
          image013 | Рекурсивный метод обращения матриц общего вида                  (4)
отсюда для блоков можно записать следующие равенства
          image028 | Рекурсивный метод обращения матриц общего вида                                                                              (5a)
          image030 | Рекурсивный метод обращения матриц общего вида                                                                              (5b)
          image032 | Рекурсивный метод обращения матриц общего вида                                                                                          (5c)
          image034 | Рекурсивный метод обращения матриц общего вида                                                                                            (5d)
Рассмотрим систему из (5a) и (5b)
          image036 | Рекурсивный метод обращения матриц общего вида       
Умножив первое из этих уравнений на image005 | Рекурсивный метод обращения матриц общего вида, а второе на вектор image003 | Рекурсивный метод обращения матриц общего вида, получим
          image038 | Рекурсивный метод обращения матриц общего вида       
поскольку  image005 | Рекурсивный метод обращения матриц общего вида скаляр, то
          image040 | Рекурсивный метод обращения матриц общего вида       
и поэтому можно из первого уравнения вычесть второе
          image042 | Рекурсивный метод обращения матриц общего вида       
разделив результат на скаляр image005 | Рекурсивный метод обращения матриц общего вида, получим
          image044 | Рекурсивный метод обращения матриц общего вида     
из которого следует
          image046 | Рекурсивный метод обращения матриц общего вида                                                                                        (6)
Разрешим (5b) относительно image016 | Рекурсивный метод обращения матриц общего вида
          image049 | Рекурсивный метод обращения матриц общего вида                                                                                                    (7)
Рассмотрим систему из (5c) и (5d)
          image051 | Рекурсивный метод обращения матриц общего вида       
Умножив первое из этих уравнений на image005 | Рекурсивный метод обращения матриц общего вида, а второе на вектор  image003 | Рекурсивный метод обращения матриц общего вида, получим
          image053 | Рекурсивный метод обращения матриц общего вида       
поскольку image005 | Рекурсивный метод обращения матриц общего вида скаляр, то
          image055 | Рекурсивный метод обращения матриц общего вида       
поэтому можно из первого уравнения вычесть второе
          image057 | Рекурсивный метод обращения матриц общего вида       
разделив результат на скаляр image005 | Рекурсивный метод обращения матриц общего вида, получим
          image059 | Рекурсивный метод обращения матриц общего вида       
из этого уравнения следует
          image061 | Рекурсивный метод обращения матриц общего вида       
Заметим, что
          image063 | Рекурсивный метод обращения матриц общего вида       
поэтому
          image065 | Рекурсивный метод обращения матриц общего вида                                                                                                    (8)
Разрешив (5d) относительно  image022 | Рекурсивный метод обращения матриц общего вида, получим
          image067 | Рекурсивный метод обращения матриц общего вида                                                                                            (9)
Итак, выражения для определения значений блоков в матрице B:
          image069 | Рекурсивный метод обращения матриц общего вида                                    (10)
Заметим, что здесь вычисление матрицы B размером n x n сводится к обращению матрицы image016 | Рекурсивный метод обращения матриц общего вида, размером (n-1) x (n-1) и умножению  на векторы. Численно этот метод можно реализовать в виде рекурсивного алгоритма.

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

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

В случае симметричной исходной матрицы A, матрица image004 | Рекурсивный метод обращения матриц общего вида  будет также симметричной и потому может быть записана в виде суммы нижней треугольной матрицы image073 | Рекурсивный метод обращения матриц общего вида, диагональной image075 | Рекурсивный метод обращения матриц общего вида и верхней треугольной image077 | Рекурсивный метод обращения матриц общего вида
          image079 | Рекурсивный метод обращения матриц общего вида       
также будет выполняться
          image081 | Рекурсивный метод обращения матриц общего вида     
Обратная к A матрица B будет также симметричной и потому также может быть записана в виде суммы нижней треугольной матрицы image083 | Рекурсивный метод обращения матриц общего вида, диагональной image085 | Рекурсивный метод обращения матриц общего вида и верхней треугольной image087 | Рекурсивный метод обращения матриц общего вида
          image089 | Рекурсивный метод обращения матриц общего вида     
С использованием этих обозначений выражения (10) можно переписать для частного случая симметричных матриц  A  и B:
          image091 | Рекурсивный метод обращения матриц общего вида                          (11)
При практической реализации этого метода как матрицу A так и B можно хранить в линейных масивах размером image093 | Рекурсивный метод обращения матриц общего вида.

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

 
template <class T, const long nDim>
bool MatrixT_Ar  <T, nDim>::InvertMatrixRecursionIn (const int &iDim, T v[])
{
            static const T eps = std::numeric_limits<T>::epsilon(); //машинная точность                      
            //Рекурсивный метод вычисление обратной матрицы 
            if (iDim==0)     // Условие прекращения рекурсии
            {
                        if (eps > fabs(a[0][0]))  return true;  //матрица имеет дискриминант==0 и потому не может быть обращена                
                        a[0][0] = 1.0f/a[0][0];
            }
            else
            {          
                        int iNoZero = iDim;
                        T Pivot = 0.0f;
                        if (eps > fabs(a[iDim][iDim]))                                                  
                                   for (int i = 0; i < iDim; ++i) //выбирает строку с максимальным значением элемента                                                           
                                               if (Pivot < fabs(a[i][iDim]))
                                                           {Pivot = fabs(a[i][iDim]); iNoZero = i;}                      

                        if (eps > fabs(a[iNoZero][iDim]))  return true;  //матрица имеет дискриминант==0 и потому не может быть обращена                       
                        if (iNoZero != iDim)   //если нужно суммирование строк для предотвращения a22==0
                                   for (int j = 0; j < nDim; ++j) a[iDim][j] += a[iNoZero][j]; 
   
                        for (int j = 0; j < iDim; ++j)      a[iDim][j] /= a[iDim][iDim];                             // a21 = a21/a22
                        for (int i = 0; i < iDim; ++i)                              
                                   for (int j = 0; j < iDim; ++j) 
                                               a[i][j] -= a[i][iDim]*a[iDim][j];            //  a11 = a11 - a12*a21          

                        if (InvertMatrixRecursionIn (iDim-1, v))  // Рекурсивное вычисление b11 = (a11 - a12*a21)^(-1)
                                   return true;

                        for (int i = 0; i < iDim; ++i)       v[i] = a[i][iDim] / a[iDim][iDim];          // a12 = a12/a22
                        for (int i = 0; i < iDim; ++i)
                        {
                                   a[i][iDim] = 0;
                                   for (int j = 0; j < iDim; ++j)                  
                                               a[i][iDim] -= v[j]*a[i][j];                                  // b12 = -b11*a12
                        }
                      
                        a[iDim][iDim] = 1.0f/a[iDim][iDim];
                        for (int i = 0; i < iDim; ++i)
                        {
                                   v[i] = a[iDim][i];
                                   a[iDim][iDim] -= v[i]*a[i][iDim];                      // b22 =1/a22 - a21*b12                                
                        }
                        
                        for (int j = 0; j < iDim; ++j)
                        {
                                   a[iDim][j] = 0;
                                   for (int i = 0; i < iDim; ++i)                              
                                               a[iDim][j] -= v[i]*a[i][j];                                  // b21 = -a21 * b11
                        }          
                        //Обратная коррекция предпоследнего столбца
                        if (iNoZero != iDim)   //если нужно было суммирование строк для предотвращения a22==0             
                                   for (int i = 0; i <= iDim; ++i)    a[i][iDim-1] += a[i][iDim];                                                      
            }
            return false;
}

template <class T, const long nDim>
bool MatrixT_Ar  <T, nDim>::InvertMatrixRecursion ()
{
            //Рекурсивный метод вычисление обратной матрицы 
            //Написана и отлажена 16-30.05.06
            //вход исходная матрица, выход - обращенная матрица, в той же области памяти
            T v[nDim-1];    
            return (InvertMatrixRecursionIn (nDim-1, v));    // Рекурсивное вычисление матрицы
}

Более оптимальный вариант функции реалиован в библиотеке lazy написаной eagle.
Библиотека доступна по адресу http://code.google.com/p/lazymatrix/

#lazy, #matrix inversion, #обращение матриц, #рекурсия

5 марта 2008 (Обновление: 7 мар. 2008)

Комментарии [6]