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

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

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

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

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

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

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

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

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

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

• Если $A$ обратима, то $A^{-1}$ единственна.
• $(A^{-1}{)}^{-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=0$.
• $E^{-1}=E$.
• Пусть необходимо решить систему линейных уравнений $Ax=b$, где $x$ — искомый вектор, $b$ — ненулевой вектор. Если $A^{-1}$ существует, то $x=A^{-1}b$. В противном случае либо размерность пространства решений больше нуля, либо их нет вовсе.
• ${(A-B)}^{-1}=A^{-1}+A^{-1}B{(A-B)}^{-1},$
• ${(A+B)}^{-1}={(I+A^{-1}B)}^{-1}{A}^{-1},$
• ${(A-B)}^{-1}=\sum _{k=0}^{\mathrm{\infty }}{\left(A^{-1}B\right)}^k{A}^{-1}.$

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

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

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

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

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

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

${\mathrm{\Lambda }}_1\cdot \dots \cdot {\mathrm{\Lambda }}_n\cdot A=\mathrm{\Lambda }A=E\Rightarrow \mathrm{\Lambda }=A^{-1}.$

${\mathrm{\Lambda }}_m=\left[\begin{array}{ccccccc}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{array}\right].$

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

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

Матрица, обратная матрице $A$, представима в виде:

$A^{-1}=\frac{\text{adj}(A)}{\det (A)},$

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

Сложность алгоритма зависит от сложности $O_{\det }$ алгоритма расчета определителя и равна $O(n^2)\cdot O_{\det }$.

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

Матричное уравнение $AX=I_n$ для обратной матрицы $X$ можно рассматривать как совокупность $n$ систем вида $Ax=b$. Обозначим $i$-й столбец матрицы $X$ через $X_i$; тогда $A{X}_i=e_i$, $i=1,\dots ,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}A{X}_k.$

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

$\{\begin{array}{c}{\mathrm{\Psi }}_k=E-A{X}_k,\\ X_{k+1}=X_k\sum _{i=0}^n{\mathrm{\Psi }}_k^i.\end{array}$

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

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

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

Примеры

Матрица 2 × 2

${𝐀}^{-1}={\left[\begin{array}{cc}a& b\\ c& d\end{array}\right]}^{-1}=\frac{1}{\det 𝐀}\left[\begin{array}{cc}d& -b\\ -c& a\end{array}\right]=\frac{1}{ad-bc}\left[\begin{array}{cc}d& -b\\ -c& a\end{array}\right]$.

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

Ссылки

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