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

Обра́тная ма́трица — такая матрица $A^{-1}$, при умножении которой на исходную матрицу $A$ получается единичная матрица $E$:

$AA^{-1}=A^{-1}A=E.$

Обратную матрицу можно определить как:

$A^{-1}={\frac {{\mbox{adj}}A}{|A|}},$

где ${\mbox{adj}}A$ — соответствующая присоединённая матрица,

$|A|$ — определитель матрицы $A$.

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

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

Пусть квадратные матрицы $A,~B$ — невырожденные. Тогда:

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

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

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

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

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

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

При использовании метода Гаусса первая матрица будет умножаться слева на одну из элементарных матриц $\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$, представима в виде:

${A}^{-1}={{{\mbox{adj}}(A)} \over {\det(A)}},$

где ${\mbox{adj}}(A)$ — присоединенная матрица (матрица, составленная из алгебраических дополнений для соответствующих элементов транспонированной матрицы).

Сложность алгоритма зависит от сложности $O_{\det }$ алгоритма расчета определителя и равна $O(n^{2})\cdot 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$ уравнений с одной матрицей и разными правыми частями. Решение этих уравнений может быть упрощено с помощью LU- или LUP-разложения матрицы $A$. После выполнения LUP-разложения за время $O(n^{3})$ на решение каждого из $n$ уравнений нужно время $O(n^{2})$, так что и этот алгоритм требует времени $O(n^{3})$.

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

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

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

Сложность обоих алгоритмов — $O(n^{3})$.

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

Матрицу $A^{-1}$ можно вычислить с произвольной точностью в результате выполнения следующего итерационного процесса, называющегося методом Шульца и являющегося обобщением классического метода Ньютона:

$X_{k+1}=2X_{k}-X_{k}AX_{k}.$

Последовательность матриц $X_{k}$ сходится к $A^{-1}$ при $k\to \infty$. Существует также так называемый обобщённый метод Шульца, который описывается следующими рекуррентными соотношениями:

${\begin{cases}\Psi _{k}=E-AX_{k},\\X_{k+1}=X_{k}\sum \limits _{i=0}^{n}\Psi _{k}^{i}.\end{cases}}$

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

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

Для метода Ньютона в качестве начального приближения можно выбрать $X_{0}=A^{H}/\left(||A||_{1}||A||_{\infty }\right)$, где верхний индекс $H$ обозначает эрмитово сопряжение, $||\cdot ||_{1}$ и $||\cdot ||_{\infty }$ — соответствующие матричные нормы. Такое $X_{0}$ вычисляется всего за $O(n^{2})$ операций, где $n$ — порядок матрицы, и обеспечивает сходимость алгоритма.

Примеры

Матрица 2 × 2

$\mathbf {A} ^{-1}={\begin{bmatrix}a&b\\c&d\\\end{bmatrix}}^{-1}={\frac {1}{\det \mathbf {A} }}{\begin{bmatrix}d&-b\\-c&a\\\end{bmatrix}}={\frac {1}{ad-bc}}{\begin{bmatrix}d&-b\\-c&a\\\end{bmatrix}}.$

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

Ссылки

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