Обратная матрица - NiNa.Az

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle \Lambda _{1}\cdot \dots \cdot \Lambda _{n}\cdot A=\Lambda A=E\Rightarrow \Lambda =A^{-1}.}$

${\displaystyle \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}}.}$

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

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

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

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

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

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

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

Матричное уравнение ${\displaystyle AX=I_{n}}$ для обратной матрицы ${\displaystyle X}$ можно рассматривать как совокупность ${\displaystyle n}$ систем вида ${\displaystyle Ax=b}$. Обозначим ${\displaystyle i}$-й столбец матрицы ${\displaystyle X}$ через ${\displaystyle X_{i}}$; тогда ${\displaystyle AX_{i}=e_{i}}$, ${\displaystyle i=1,\ldots ,n}$, поскольку ${\displaystyle i}$-м столбцом матрицы ${\displaystyle I_{n}}$ является единичный вектор ${\displaystyle e_{i}}$. Иными словами, нахождение обратной матрицы сводится к решению ${\displaystyle n}$ уравнений с одной матрицей и разными правыми частями. Решение этих уравнений может быть упрощено с помощью LU- или LUP-разложения матрицы ${\displaystyle A}$. После выполнения LUP-разложения за время ${\displaystyle O(n^{3})}$ на решение каждого из ${\displaystyle n}$ уравнений нужно время ${\displaystyle O(n^{2})}$, так что и этот алгоритм требует времени ${\displaystyle O(n^{3})}$.

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

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

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

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

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

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

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

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

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

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

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

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

Примеры

Матрица 2 × 2

${\displaystyle \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 возможно только при условии, что ${\displaystyle ad-bc=\det A\neq 0}$.

Примечания

1. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ, — М.: Вильямс, 2006 (с. 700).
2. Petković, M. D.. Generalized Schultz iterative methods for the computation of outer inverses (англ.) // Computers & Mathematics with Applications. — 2014. — June (vol. 67, iss. 10). — P. 1837—1847. — doi:10.1016/j.camwa.2014.03.019.
3. Pan, V., Reif, J.. Fast and efficient parallel solution of dense linear systems (англ.) // Computers & Mathematics with Applications. — 1989. — Vol. 17, iss. 11. — P. 1481—1491. — doi:10.1016/0898-1221(89)90081-3.
4. Как найти обратную матрицу?  (неопр.) mathprofi.ru. Дата обращения: 18 октября 2017. Архивировано 17 октября 2017 года.

Ссылки

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