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

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

$\! AA^{-1} = A^{-1}A = E$

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

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

• $\det A^{-1} = \frac{1}{\det A}$, где $\ \det$ обозначает определитель.
• $\ (AB)^{-1} = B^{-1}A^{-1}$ для любых двух обратимых матриц $A$ и $B$.
• $\ (A^T)^{-1} = (A^{-1})^T$ где $*^T$ обозначает транспонированную матрицу.
• $\ (kA)^{-1} = k^{-1}A^{-1}$ для любого коэффициента $k\not=0$ .
• Если необходимо решить систему линейных уравнений $Ax=b$, (b — ненулевой вектор) где $x$ — искомый вектор, и если $A^{-1}$ существует, то $x=A^{-1} b$. В противном случае либо размерность пространства решений больше нуля, либо их нет вовсе.

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

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

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

Метод Гаусса—Жордана

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

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

$\Lambda_1 \cdot \dots \cdot \Lambda_n \cdot A = \Lambda A = E \Rightarrow \Lambda = A^{-1}$.

$\Lambda_m = \begin{bmatrix} 1 & \dots & 0 & -a_{1m} /a_{mm} & 0 &\dots & 0 \\ & & &\dots & & &\\ 0 & \dots & 1 & -a_{m-1m} /a_{mm} & 0 &\dots &0 \\ 0 & \dots & 0 & 1/a_{mm} & 0 &\dots & 0 \\ 0 & \dots & 0 & -a_{m+1m} /a_{mm} & 1 &\dots &0 \\ & & &\dots & & &\\ 0 & \dots & 0 & -a_{nm}/a_{mm} & 0 &\dots & 1 \end{bmatrix}$.

Вторая матрица после применения всех операций станет равна $\Lambda$, то есть будет искомой. Сложность алгоритма — $O(n^3)$.

С помощью матрицы алгебраических дополнений

$A^{-1} = \frac{1}{\det A}\cdot C^{T}$

$C^{T}$ — транспонированная матрица алгебраических дополнений;

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

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

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

Матричное уравнение $AX=I_n$ для обратной матрицы $X$ можно рассматривать как совокупность $n$ систем вида $Ax=b$. Обозначим $i$-ый столбец матрицы $X$ через $X_i$; тогда $AX_i=e_i$, $i=1,\ldots,n$ ,поскольку $i$-м столбцом матрицы $I_n$ является единичный вектор $e_i$. другими словами, нахождение обратной матрицы сводится к решению n уравнений с одной матрицей и разными правыми частями. После выполнения LUP-разложения (время O(n³)) на решение каждого из n уравнений нужно время O(n²), так что и эта часть работы требует времени O(n³)^[1].

Если матрица A невырождена, то для неё можно рассчитать LUP-разложение $PA=LU$. Пусть $PA=B$, $B^{-1}=D$. Тогда из свойств обратной матрицы можно записать: $D=U^{-1}L^{-1}$. Если умножить это равенство на U и L то можно получить два равенства вида $UD=L^{-1}$ и $DL=U^{-1}$. Первое из этих равенств представляет собой систему из n² линейных уравнений для $\frac{n(n+1)}{2}$ из которых известны правые части (из свойств треугольных матриц). Второе представляет также систему из n² линейных уравнений для $\frac{n(n-1)}{2}$ из которых известны правые части (также из свойств треугольных матриц). Вместе они представляют собой систему из n² равенств. С помощью этих равенств можно реккурентно определить все n² элементов матрицы D. Тогда из равенства (PA)⁻¹ = A⁻¹P⁻¹ = B⁻¹ = D. получаем равенство $A^{-1} = DP$.

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

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

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

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

$\begin{cases}\Psi_k=E-AU_k,\\ U_{k+1}=U_k \sum_{i=0}^n \Psi^i_k\end{cases}$

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

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

Проблема выбора начального приближения $U_0~$ в рассматриваемых здесь процессах итерационного обращения матриц не позволяет относиться к ним как к самостоятельным универсальным методам, конкурирующими с прямыми методами обращения, основанными, например, на LU-разложении матриц. Имеются некоторые рекомендации по выбору $U_0~$, обеспечивающие выполнение условия $\rho(\Psi_0)<1~$ (спектральный радиус матрицы меньше единицы), являющегося необходимым и достаточным для сходимости процесса. Однако при этом, во-первых, требуется знать сверху оценку спектра обращаемой матрицы A либо матрицы $AA^T~$ (а именно, если A — симметричная положительно определённая матрица и $\rho(A)\le\beta~$, то можно взять $U_0={\alpha}E~$, где $\alpha\in\left(0,\frac{2}{\beta}\right)~$; если же A — произвольная невырожденная матрица и $\rho(AA^T)\le\beta~$, то полагают $U_0={\alpha}A^T~$, где также $\alpha\in\left(0,\frac{2}{\beta}\right)~$; можно конечно упростить ситуацию и, воспользовавшись тем, что $\rho(AA^T)\le\mathcal{k}AA^T\mathcal{k}~$, положить $U_0=\frac{A^T}{\|AA^T\|}~$). Во-вторых, при таком задании начальной матрицы нет гарантии, что $\|\Psi_0\|~$ будет малой (возможно, даже окажется $\|\Psi_0\|>1~$), и высокий порядок скорости сходимости обнаружится далеко не сразу.

Примеры

Матрица 2х2

$A^{-1} = \begin{bmatrix} a & b \\ c & d \\ \end{bmatrix}^{-1} = \frac{1}{ad - bc} \begin{bmatrix} \,\,\,d & \!\!-b \\ -c & \,a \\ \end{bmatrix}= \frac{1}{ad - bc} \begin{bmatrix} \,\,\,d & \!\!-c \\ -b & \,a \\ \end{bmatrix}^{T}= \frac{1}{\det A}\cdot C^{T}.$

Обращение матрицы 2х2 возможно только при условии, что $ad - bc = \det A \neq 0$.

Примечания

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

Ссылки

• Реализация с полным выбором ведущего элемента на C++

В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники. Эта отметка установлена 14 мая 2011.