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

Поделись знанием:
Перейти к: навигация, поиск

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

<math>AA^{-1} = A^{-1}A = E</math>

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





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

  • <math>\det A^{-1} = \frac{1}{\det A}</math>, где <math>\ \det</math> обозначает определитель.
  • <math>\ (AB)^{-1} = B^{-1}A^{-1}</math> для любых двух обратимых матриц <math>A</math> и <math>B</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>, (b — ненулевой вектор) где <math>x</math> — искомый вектор, и если <math>A^{-1}</math> существует, то <math>x=A^{-1} b</math>. В противном случае либо размерность пространства решений больше нуля, либо их нет вовсе.

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

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

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

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

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

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

Сложность алгоритма зависит от сложности алгоритма расчета определителя Odet и равна O(n²)·Odet.

Использование 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>. другими словами, нахождение обратной матрицы сводится к решению n уравнений с одной матрицей и разными правыми частями. После выполнения LUP-разложения (время O(n³)) на решение каждого из n уравнений нужно время O(n²), так что и эта часть работы требует времени O(n³)[1].

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

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

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

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

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

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

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

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

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

Примеры

Матрица 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> Обращение матрицы 2х2 возможно только при условии, что <math>ad - bc = \det A \neq 0 </math>.

Напишите отзыв о статье "Обратная матрица"

Примечания

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

Ссылки

  • [drobotenko.com/code_rus.html Реализация с полным выбором ведущего элемента на C++]

Отрывок, характеризующий Обратная матрица

Соня кивнула головой.
Графиня обняла Соню и заплакала.
«Пути господни неисповедимы!» – думала она, чувствуя, что во всем, что делалось теперь, начинала выступать скрывавшаяся прежде от взгляда людей всемогущая рука.
– Ну, мама, все готово. О чем вы?.. – спросила с оживленным лицом Наташа, вбегая в комнату.
– Ни о чем, – сказала графиня. – Готово, так поедем. – И графиня нагнулась к своему ридикюлю, чтобы скрыть расстроенное лицо. Соня обняла Наташу и поцеловала ее.
Наташа вопросительно взглянула на нее.
– Что ты? Что такое случилось?
– Ничего… Нет…
– Очень дурное для меня?.. Что такое? – спрашивала чуткая Наташа.
Соня вздохнула и ничего не ответила. Граф, Петя, m me Schoss, Мавра Кузминишна, Васильич вошли в гостиную, и, затворив двери, все сели и молча, не глядя друг на друга, посидели несколько секунд.
Граф первый встал и, громко вздохнув, стал креститься на образ. Все сделали то же. Потом граф стал обнимать Мавру Кузминишну и Васильича, которые оставались в Москве, и, в то время как они ловили его руку и целовали его в плечо, слегка трепал их по спине, приговаривая что то неясное, ласково успокоительное. Графиня ушла в образную, и Соня нашла ее там на коленях перед разрозненно по стене остававшимися образами. (Самые дорогие по семейным преданиям образа везлись с собою.)
На крыльце и на дворе уезжавшие люди с кинжалами и саблями, которыми их вооружил Петя, с заправленными панталонами в сапоги и туго перепоясанные ремнями и кушаками, прощались с теми, которые оставались.
Как и всегда при отъездах, многое было забыто и не так уложено, и довольно долго два гайдука стояли с обеих сторон отворенной дверцы и ступенек кареты, готовясь подсадить графиню, в то время как бегали девушки с подушками, узелками из дому в кареты, и коляску, и бричку, и обратно.
– Век свой все перезабудут! – говорила графиня. – Ведь ты знаешь, что я не могу так сидеть. – И Дуняша, стиснув зубы и не отвечая, с выражением упрека на лице, бросилась в карету переделывать сиденье.
– Ах, народ этот! – говорил граф, покачивая головой.
Старый кучер Ефим, с которым одним только решалась ездить графиня, сидя высоко на своих козлах, даже не оглядывался на то, что делалось позади его. Он тридцатилетним опытом знал, что не скоро еще ему скажут «с богом!» и что когда скажут, то еще два раза остановят его и пошлют за забытыми вещами, и уже после этого еще раз остановят, и графиня сама высунется к нему в окно и попросит его Христом богом ехать осторожнее на спусках. Он знал это и потому терпеливее своих лошадей (в особенности левого рыжего – Сокола, который бил ногой и, пережевывая, перебирал удила) ожидал того, что будет. Наконец все уселись; ступеньки собрались и закинулись в карету, дверка захлопнулась, послали за шкатулкой, графиня высунулась и сказала, что должно. Тогда Ефим медленно снял шляпу с своей головы и стал креститься. Форейтор и все люди сделали то же.
– С богом! – сказал Ефим, надев шляпу. – Вытягивай! – Форейтор тронул. Правый дышловой влег в хомут, хрустнули высокие рессоры, и качнулся кузов. Лакей на ходу вскочил на козлы. Встряхнуло карету при выезде со двора на тряскую мостовую, так же встряхнуло другие экипажи, и поезд тронулся вверх по улице. В каретах, коляске и бричке все крестились на церковь, которая была напротив. Остававшиеся в Москве люди шли по обоим бокам экипажей, провожая их.
Наташа редко испытывала столь радостное чувство, как то, которое она испытывала теперь, сидя в карете подле графини и глядя на медленно подвигавшиеся мимо нее стены оставляемой, встревоженной Москвы. Она изредка высовывалась в окно кареты и глядела назад и вперед на длинный поезд раненых, предшествующий им. Почти впереди всех виднелся ей закрытый верх коляски князя Андрея. Она не знала, кто был в ней, и всякий раз, соображая область своего обоза, отыскивала глазами эту коляску. Она знала, что она была впереди всех.
В Кудрине, из Никитской, от Пресни, от Подновинского съехалось несколько таких же поездов, как был поезд Ростовых, и по Садовой уже в два ряда ехали экипажи и подводы.
Объезжая Сухареву башню, Наташа, любопытно и быстро осматривавшая народ, едущий и идущий, вдруг радостно и удивленно вскрикнула:
– Батюшки! Мама, Соня, посмотрите, это он!
– Кто? Кто?
– Смотрите, ей богу, Безухов! – говорила Наташа, высовываясь в окно кареты и глядя на высокого толстого человека в кучерском кафтане, очевидно, наряженного барина по походке и осанке, который рядом с желтым безбородым старичком в фризовой шинели подошел под арку Сухаревой башни.
– Ей богу, Безухов, в кафтане, с каким то старым мальчиком! Ей богу, – говорила Наташа, – смотрите, смотрите!
– Да нет, это не он. Можно ли, такие глупости.
– Мама, – кричала Наташа, – я вам голову дам на отсечение, что это он! Я вас уверяю. Постой, постой! – кричала она кучеру; но кучер не мог остановиться, потому что из Мещанской выехали еще подводы и экипажи, и на Ростовых кричали, чтоб они трогались и не задерживали других.
Действительно, хотя уже гораздо дальше, чем прежде, все Ростовы увидали Пьера или человека, необыкновенно похожего на Пьера, в кучерском кафтане, шедшего по улице с нагнутой головой и серьезным лицом, подле маленького безбородого старичка, имевшего вид лакея. Старичок этот заметил высунувшееся на него лицо из кареты и, почтительно дотронувшись до локтя Пьера, что то сказал ему, указывая на карету. Пьер долго не мог понять того, что он говорил; так он, видимо, погружен был в свои мысли. Наконец, когда он понял его, посмотрел по указанию и, узнав Наташу, в ту же секунду отдаваясь первому впечатлению, быстро направился к карете. Но, пройдя шагов десять, он, видимо, вспомнив что то, остановился.
Высунувшееся из кареты лицо Наташи сияло насмешливою ласкою.
– Петр Кирилыч, идите же! Ведь мы узнали! Это удивительно! – кричала она, протягивая ему руку. – Как это вы? Зачем вы так?
Пьер взял протянутую руку и на ходу (так как карета. продолжала двигаться) неловко поцеловал ее.
– Что с вами, граф? – спросила удивленным и соболезнующим голосом графиня.