Обратная матрица
Обра́тная ма́трица — такая матрица <math>A^{-1}</math>, при умножении которой на исходную матрицу <math>A</math> получается единичная матрица <math>E</math>:
- <math>AA^{-1} = A^{-1}A = E.</math>
Обратную матрицу можно определить как:
- <math> A^{-1} = \frac{\mbox{adj} A}{|A|}, </math>
- где <math>\mbox{adj} A</math> — соответствующая присоединённая матрица,
- <math>|A|</math> — определитель матрицы <math>A</math>.
Из этого определения следует критерий обратимости: матрица обратима тогда и только тогда, когда она невырождена, то есть её определитель не равен нулю. Для неквадратных матриц и вырожденных матриц обратных матриц не существует. Однако возможно обобщить это понятие и ввести псевдообратные матрицы, похожие на обратные по многим свойствам.
Свойства обратной матрицы
Пусть квадратные матрицы <math>A,~ B</math> — невырожденные. Тогда:
- Если <math>A</math> обратима, то <math>A^{-1}</math> единственна.
- <math>\bigl(A^{-1}\bigr)^{-1} = A</math>
- <math>\det A^{-1} = \frac{1}{\det A}</math>, где <math>\det</math> обозначает определитель.
- <math>(AB)^{-1} = B^{-1}A^{-1}</math>
- <math>(A^T)^{-1} = (A^{-1})^T</math>, где <math>T</math> обозначает операцию транспонирования.
- <math>(kA)^{-1} = k^{-1}A^{-1}</math> для любого коэффициента <math>k\not=0</math>.
- <math>E^{-1} = E</math>.
- Пусть необходимо решить систему линейных уравнений <math>Ax=b</math>, где <math>x</math> — искомый вектор, <math>b</math> — ненулевой вектор. Если <math>A^{-1}</math> существует, то <math>x=A^{-1} b</math>. В противном случае либо размерность пространства решений больше нуля, либо их нет вовсе.
- <math>\left({A} - {B}\right)^{-1} = {A}^{-1} + {A}^{-1}{B}\left({A} - {B}\right)^{-1},</math>
- <math>\left({A} + {B}\right)^{-1} = \left({I} + {A}^{-1}{B}\right)^{-1}{A}^{-1},</math>
- <math>\left({A} - {B}\right)^{-1} = \sum_{k=0}^{\infty} \left({A}^{-1}{B}\right)^k{A}^{-1}.</math>
Способы нахождения обратной матрицы
Если матрица обратима, то для нахождения обратной матрицы можно воспользоваться одним из следующих способов:
Точные (прямые) методы
Метод Жордана—Гаусса
Возьмём две матрицы: саму <math>A</math> и единичную матрицу <math>E</math>. Приведём матрицу <math>A</math> к единичной методом Гаусса—Жордана, применяя преобразования по строкам (можно также применять преобразования и по столбцам). После применения каждой операции к первой матрице применим ту же операцию ко второй. Когда приведение первой матрицы к единичному виду будет завершено, вторая матрица окажется равной <math>A^{-1}</math>.
При использовании метода Гаусса первая матрица будет умножаться слева на одну из элементарных матриц <math>\Lambda_i</math> (трансвекцию или диагональную матрицу с единицами на главной диагонали, кроме одной позиции):
- <math>\Lambda_1 \cdot \dots \cdot \Lambda_n \cdot A = \Lambda A = E \Rightarrow \Lambda = A^{-1}.</math>
- <math>\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}.</math>
Вторая матрица после применения всех операций станет равна <math>\Lambda</math>, то есть будет искомой. Сложность алгоритма — <math>O(n^3)</math>.
С помощью матрицы алгебраических дополнений
Матрица, обратная матрице <math>A</math>, представима в виде:
- <math>{A}^{-1}= {{\mbox{adj} (A)}\over{\det(A)}},</math>
- где <math>\mbox{adj}(A)</math> — присоединенная матрица (матрица, составленная из алгебраических дополнений для соответствующих элементов транспонированной матрицы).
Сложность алгоритма зависит от сложности <math>O_{\det}</math> алгоритма расчета определителя и равна <math>O(n^2) \cdot O_{\det}</math>.
Использование LU- или LUP-разложения
Матричное уравнение <math>AX=I_n</math> для обратной матрицы <math>X</math> можно рассматривать как совокупность <math>n</math> систем вида <math>Ax=b</math>. Обозначим <math>i</math>-й столбец матрицы <math>X</math> через <math>X_i</math>; тогда <math>AX_i=e_i</math>, <math>i=1,\ldots,n</math>, поскольку <math>i</math>-м столбцом матрицы <math>I_n</math> является единичный вектор <math>e_i</math>. Иными словами, нахождение обратной матрицы сводится к решению <math>n</math> уравнений с одной матрицей и разными правыми частями. Решение этих уравнений может быть упрощено с помощью LU- или LUP-разложения матрицы <math>A</math>. После выполнения LUP-разложения за время <math>O(n^3)</math> на решение каждого из <math>n</math> уравнений нужно время <math>O(n^2)</math>, так что и этот алгоритм требует времени <math>O(n^3)</math><ref>Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ, — Шаблон:М: Вильямс, 2006 (с. 700).</ref>.
Матрицу, обратную к заданной невырожденной матрице <math>A</math>, можно также вычислить непосредственно с помощью матриц, полученных в результате разложения.
Результатом LUP-разложения матрицы <math>A</math> является равенство <math>PA=LU</math>. Пусть <math>PA=B</math>, <math>B^{-1}=D</math>. Тогда из свойств обратной матрицы можно записать: <math>D=U^{-1}L^{-1}</math>. Если умножить это равенство на <math>U</math> и <math>L</math> то можно получить два равенства вида <math>UD=L^{-1}</math> и <math>DL=U^{-1}</math>. Первое из этих равенств представляет собой систему из <math>n^2</math> линейных уравнений, для <math>n(n+1)/2</math> из которых известны правые части (из свойств треугольных матриц). Второе также представляет систему из <math>n^2</math> линейных уравнений, для <math>n(n-1)/2</math> из которых известны правые части (также из свойств треугольных матриц). Вместе они представляют собой систему из <math>n^2</math> равенств. С их помощью можно рекуррентно определить все <math>n^2</math> элементов матрицы <math>D</math>. Тогда из равенства <math>(PA)^{-1} = A^{-1} P^{-1} = B^{-1} = D</math> получаем равенство <math>A^{-1} = DP</math>.
В случае использования LU-разложения (<math>A=LU</math>) не требуется перестановки столбцов матрицы <math>D</math>, но решение может разойтись даже если матрица <math>A</math> невырождена.
Сложность обоих алгоритмов — <math>O(n^3)</math>.
Итерационные методы
Матрицу <math>A^{-1}</math> можно вычислить с произвольной точностью в результате выполнения следующего итерационного процесса, называющегося методом Шульца и являющегося обобщением классического метода Ньютона:
- <math>X_{k+1} = 2X_k - X_k A X_k.</math>
Последовательность матриц <math>X_k</math> сходится к <math>A^{-1}</math> при <math>k \to \infty</math>. Существует также так называемый обобщённый метод Шульца, который описывается следующими рекуррентными соотношениями<ref>Шаблон:Статья</ref>:
- <math>\begin{cases} \Psi_k=E-AX_k, \\
X_{k+1}=X_k \sum\limits_{i=0}^n \Psi^i_k. \end{cases}</math>
Выбор начального приближения
Проблема выбора начального приближения <math>X_0</math> в рассматриваемых здесь процессах итерационного обращения матриц не позволяет относиться к ним как к самостоятельным универсальным методам, конкурирующими с прямыми методами обращения, основанными, например, на <math>LU</math>-разложении матриц. Имеются некоторые рекомендации по выбору <math>X_0</math>, обеспечивающие выполнение условия <math>\rho(\Psi_0)<1</math> (спектральный радиус матрицы меньше единицы), являющегося необходимым и достаточным для сходимости итерационного процесса. Однако при этом, во-первых, требуется знать оценку сверху спектра обращаемой матрицы <math>A</math> либо матрицы <math>AA^T</math> (а именно, если <math>A</math> — симметричная положительно определённая матрица и <math>\rho(A)\leqslant\beta</math>, то можно взять <math>X_0={\alpha}E</math>, где <math>\alpha\in\left(0,2/\beta\right)</math>; если же <math>A</math> — произвольная невырожденная матрица и <math>\rho(AA^T)\leqslant\beta</math>, то полагают <math>X_0={\alpha}A^T</math>, где также <math>\alpha\in\left(0,2/\beta\right)</math>; можно, конечно, упростить ситуацию и, воспользовавшись тем, что <math>\rho(AA^T)\leqslant\mathcal{k}AA^T\mathcal{k}</math>, положить <math>X_0=A^T/\|AA^T\|</math>). Во-вторых, при таком задании начальной матрицы нет гарантии, что <math>\|\Psi_0\|</math> будет малой (возможно, даже окажется <math>\|\Psi_0\|>1</math>), и высокий порядок скорости сходимости обнаружится далеко не сразу.
Для метода Ньютона в качестве начального приближения можно выбрать <math>X_0 = A^H/ \left( ||A||_1 ||A||_\infty \right)</math>, где верхний индекс <math>H</math> обозначает эрмитово сопряжение, <math>|| \cdot ||_1</math> и <math>|| \cdot ||_\infty</math> — соответствующие матричные нормы. Такое <math>X_0</math> вычисляется всего за <math>O(n^2)</math> операций, где <math>n</math> — порядок матрицы, и обеспечивает сходимость алгоритма<ref>Шаблон:Статья</ref>.
Примеры
Матрица 2 × 2
- <math>\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}</math><ref>Шаблон:Cite web</ref>.
Обращение матрицы 2 × 2 возможно только при условии, что <math>ad - bc = \det A \neq 0 </math>.