Обратная матрица

Материал из Википедии — свободной энциклопедии
Это старая версия этой страницы, сохранённая Satels (обсуждение | вклад) в 03:51, 27 июля 2009. Она может серьёзно отличаться от текущей версии.
Перейти к навигации Перейти к поиску

Обра́тная ма́трица — такая матрица A-1, при умножении на которую исходная матрица A даёт в результате единичную матрицу E:

Квадратная матрица обратима тогда и только тогда, когда она невырожденная, то есть её определитель не равен нулю. Для неквадратных матриц и сингулярных матриц обратных матриц не существует. Однако, возможно обобщить это понятие и ввести псевдообратные матрицы, похожие на обратные по многим свойствам.

Свойства обратной матрицы

  • , где обозначает определитель.
  • для любых двух обратимых матриц и .
  • где обозначает транспонированную матрицу.
  • для любого коэффициента .
  • Если необходимо решить систему линейных уравнений , (b — ненулевой вектор) где  — искомый вектор, и если существует, то . В противном случае либо размерность пространства решений больше нуля, либо их нет вовсе.

Способы нахождения обратной матрицы

Если матрица обратима, то для нахождения обратной матрицы можно воспользоваться одним из следующих способов:

Точные (прямые) методы

Метод Гаусса

Возьмём две матрицы: саму A и единичную E. Приведём матрицу A к единичной матрице методом Гаусса. После применения каждой операции к первой матрице применим ту же операцию ко второй. Когда приведение первой матрицы к единичному виду будет завершено, вторая матрица окажется равной A-1.

При использовании метода Гаусса первая матрица будет умножаться слева на одну из элементарных матриц (трансвекцию или диагональную матрицу с единицами на главной диагонали, кроме одной позиции):

.
.

Вторая матрица после применения всех операций станет равна , то есть будет искомой. Сложность алгоритма — .

С помощью союзной матрицы

 — союзная матрица;

Полученная матрица A-1 и будет обратной. Сложность алгоритма зависит от сложности алгоритма расчета определителя Odet и равна O(n²)·Odet.

Использование LU/LUP-разложения

Матричное уравнение для обратной матрицы можно рассматривать как совокупность систем вида . Обозначим -ой столбец матрицы через ; тогда , ,поскольку -м столбцом матрицы является единичный вектор . другими словами, нахождение обратной матрицы сводится к решению n уравнений с одной матрицей и разными правыми частями. После выполнения LUP-разложения (время O(n³)) на решение каждого из n уравнений нужно время O(n²), так что и эта часть работы требует времени O(n³)[1].

Если матрица A невырождена то для нее можно рассчитать LUP-разложение . Пусть , . Тогда из свойств обратной матрицы можно записать: . Если умножить это равенство на U и L то можно получить два равенства вида и . Первое из этих равенств представляет собой систему из n² линейных уравнений для из которых известны правые части (из свойств треугольных матриц). Второе представляет также систему из n² линейных уравнений для из которых известны правые части (также из свойств треугольных матриц). Вместе они престаляют собой систему из n² равенств. С помощью этих равенств можно реккурентно определить все n² элементов матрицы D. Тогда из равенства (PA)-1 = A-1P-1 = B-1 = D. получаем равенство .

Ниже представлен код на языке C++ алгоритма обращения матрицы с помощью LUP-разложения с комментариями.[источник не указан 5699 дней]

Matrix Inverse(const Matrix &A) {
    //n - размерность квадратной матрицы A
    const int n=A.Rows();
    //при инициализации задается размерность nxn
    Matrix X(n, n);
    Matrix P(n, n);
    Matrix C(n, n);
    //предполагается что в результате следующего вызова матрица C = L + U - E
    LUP(A, C, P);
    for(int k = n-1; k >= 0; k--) {
        X[ k ][ k ] = 1;
        for( int j = n-1; j > k; j--) X[ k ][ k ] -= C[ k ][ j ]*X[ j ][ k ];
        X[ k ][ k ] /= C[ k ][ k ];
        for( int i = k-1; i >= 0; i-- ) {
            for( int j = n-1; j > i; j-- ) {
                X[ i ][ k ] -= C[ i ][ j ]*X[ j ][ k ];
                X[ k ][ i ] -= C[ j ][ i ]*X[ k ][ j ];
            }
            X[ i ][ k ] /= C[ i ][ i ];
        }
    }
    X = X*P;
    return( X );
}

В случае использования вектора перестановок (см. LUP-разложение) вместо финального умножения потребуется следующий код:

int temp;
for( int i = 0; i < n; i++ ) {
    temp = i;
    while( p[ temp ] != i ) temp++;
    X.SwapColumns(i, temp);
    p[ temp ] = p[ i ];
}

В случае использования LU-разложения не требуется перестановки столбцов матрицы D но решение может разойтись даже если матрица A невырождена.

Сложность алгоритма — O(n³).

Итерационные методы

Методы Шульца

Зейделева модификация метода

Оценка погрешности

Выбор начального приближения

Проблема выбора начального приближения в рассматриваемых здесь процессах итерационного обращения матриц не позволяет относиться к ним как к самостоятельным универсальным методам, конкурирующими с прямыми методами обращения, основанными, например, на LU-разложении матриц. Имеются некоторые рекомендации по выбору , обеспечивающие выполнение условия (спектральный радиус матрицы меньше единицы), являющегося необходимым и достаточным для сходимости процесса. Однако при этом, во-первых, требуется знать сверху оценку спектра обращаемой матрицы A либо матрицы (а именно, если A — симметричная положительно определённая матрица и , то можно взять , где ; если же A — произвольная невырожденная матрица и , то полагают , где также ; можно конечно упростить ситуацию и, воспользовавшись тем, что , положить ). Во-вторых, при таком задании начальной матрицы нет гарантии, что будет малой (возможно, даже окажется ), и высокий порядок скорости сходимости обнаружится далеко не сразу.

Примеры

Матрица 2х2

Обращение матрицы 2х2 возможно только при условии, что

Примечания

  1. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ, — М.: Вильямс, 2006 (стр. 700)

Внешние ссылки