Как найти обратную треугольную матрицу - Сайт, где вы сможете решить свои вопросы

Let $$
A=begin{pmatrix}
a_{11} & a_{12} & cdots & a_{1,n-1} & a_{1,n}\
& a_{22} & cdots & a_{2,n-1} & a_{2,n}\
& & ddots & vdots & vdots\
& & & a_{n-1,n-1} & a_{n-1,n}\
& & & & a_{n,n}
end{pmatrix}.
$$
Let $i,j$ be two integers such that $i,jin{1,dots,n}
$ and $i<j$.
Let $A_{i,j}$ be an $n-1times n-1$ matrix which is obtained by crossing out row $i$ and column $j$ of $A$.
Then, $A_{i,j}$ is
$$
begin{pmatrix}
a_{11} & a_{12} & cdots & a_{1,i-1} & a_{1,i} &a_{1,i+1}&a_{1,i+2}&cdots&a_{1,j-1}&a_{1,j+1}&a_{1,j+2}&cdots&a_{1n}\
& a_{22} & cdots & a_{2,i-1} & a_{2,i} &a_{2,i+1}&a_{2,i+2}&cdots&a_{2,j-1}&a_{2,j+1}&a_{2,j+2}&cdots&a_{2n}\
& & ddots & vdots & vdots &vdots&vdots&cdots&vdots&vdots&vdots&cdots&vdots\
& & & a_{i-1,i-1} & a_{i-1,i} &a_{i-1,i+1}&a_{i-1,i+2}&cdots&a_{i-1,j-1}&a_{i-1,j+1}&a_{i-1,j+2}&cdots&a_{i-1,n}\
& & & & 0 & a_{i+1,i+1}&a_{i+1,i+2}&cdots&a_{i+1,j-1}&a_{i+1,j+1}&a_{i+1,j+2}&cdots&a_{i+1,n}\
& & & & & 0&a_{i+2,i+2}&cdots&a_{i+2,j-1}&a_{i+2,j+1}&a_{i+2,j+2}&cdots&a_{i+2,n}\
& & & & & &0&cdots&vdots&vdots&vdots&cdots&vdots\
& & & & & &&ddots&a_{j-1,j-1}&a_{j-1,j+1}&a_{j-1,j+2}&cdots&a_{j-1,n}\
& & & & & &&&0&a_{j,j+1}&a_{j,j+2}&cdots&a_{j,n}\
& & & & & &&&&a_{j+1,j+1}&a_{j+1,j+2}&cdots&a_{j+1,n}\
& & & & & &&&&&a_{j+2,j+2}&cdots&a_{j+2,n}\
& & & & & &&&&&&ddots&vdots\
& & & & & &&&&&&&a_{n,n}\
end{pmatrix}.
$$

So, $det A_{i,j}=0$ if $i,j$ are two integers such that $i,jin{1,dots,n}
$ and $i<j$.
Let $C_{i,j}$ be the $(i,j)$-cofactor of $A$.
Then, $C_{i,j}=(-1)^{i+j}det A_{i,j}=0$ if $i,j$ are two integers such that $i,jin{1,dots,n}
$ and $i<j$.
So, $$A^{-1}=frac{1}{det A}begin{pmatrix}C_{11}&C_{21}&cdots&C_{n,1}\
C_{12}&C_{22}&cdots&C_{n,2}\
vdots&vdots&&vdots\
C_{1n}&C_{2n}&cdots&C_{n,n}\
end{pmatrix}=frac{1}{det A}begin{pmatrix}C_{11}&C_{21}&cdots&C_{n,1}\
0&C_{22}&cdots&C_{n,2}\
vdots&vdots&&vdots\
0&0&cdots&C_{n,n}\
end{pmatrix}.$$

Источник

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

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

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

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

где

— соответствующая присоединённая матрица,

— определитель матрицы

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

Свойства обратной матрицы[править | править код]

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

Способы нахождения обратной матрицы[править | править код]

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

Точные (прямые) методы[править | править код]

Метод Жордана—Гаусса[править | править код]

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

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

${displaystyle Lambda _{1}cdot dots cdot Lambda _{n}cdot A=Lambda A=ERightarrow 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 &1end{bmatrix}}.}$

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

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

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

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

где

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

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

Использование LU- или LUP-разложения[править | править код]

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

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

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

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

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

Итерационные методы[править | править код]

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

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

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

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

Выбор начального приближения[править | править код]

Проблема выбора начального приближения $X_{0}$ в рассматриваемых здесь процессах итерационного обращения матриц не позволяет относиться к ним как к самостоятельным универсальным методам, конкурирующими с прямыми методами обращения, основанными, например, на -разложении матриц. Имеются некоторые рекомендации по выбору $X_{0}$ , обеспечивающие выполнение условия ${displaystyle rho (Psi _{0})<1}$ (спектральный радиус матрицы меньше единицы), являющегося необходимым и достаточным для сходимости итерационного процесса. Однако при этом, во-первых, требуется знать оценку сверху спектра обращаемой матрицы либо матрицы ${displaystyle AA^{T}}$ (а именно, если — симметричная положительно определённая матрица и , то можно взять ${displaystyle X_{0}={alpha }E}$ , где ; если же — произвольная невырожденная матрица и ${displaystyle rho (AA^{T})leqslant beta }$ , то полагают ${displaystyle X_{0}={alpha }A^{T}}$ , где также ; можно, конечно, упростить ситуацию и, воспользовавшись тем, что ${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 ||cdot ||_{1}}$ и ${displaystyle ||cdot ||_{infty }}$ — соответствующие матричные нормы. Такое $X_{0}$ вычисляется всего за $O(n^{2})$ операций, где — порядок матрицы, и обеспечивает сходимость алгоритма^[3].

Примеры[править | править код]

Матрица 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}}.}$

^[4]

Обращение матрицы 2 × 2 возможно только при условии, что .

Примечания[править | править код]

↑ Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ, — М.: Вильямс, 2006 (с. 700).
↑ 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.
↑ 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.
↑ Как найти обратную матрицу? mathprofi.ru. Дата обращения: 18 октября 2017. Архивировано 17 октября 2017 года.

Ссылки[править | править код]

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

Источник

В математической дисциплине линейной алгебры, треугольная матрица – это особый вид квадратной матрицы. Квадратная матрица называется нижнетреугольной, если все элементы над главной диагональю равны нулю. Точно так же квадратная матрица называется верхнетреугольной, если все элементы ниже главной диагонали равны нулю.

Поскольку матричные уравнения с треугольными матрицами легче решать, они очень важны в численном анализе. С помощью алгоритма LU-разложения обратимая матрица может быть записана как произведение нижней треугольной матрицы L и верхней треугольной матрицы U тогда и только тогда, когда all его ведущий принципал миноры отличен от нуля.

Содержание

1 Описание
- 1.1 Примеры
2 Прямая и обратная подстановка
- 2.1 Прямая подстановка
- 2.2 Приложения
3 Свойства
4 Специальные формы
- 4.1 Унитреугольная матрица
- 4.2 Строго треугольная матрица
- 4.3 Атомарная треугольная матрица
5 Треугольная возможность
- 5.1 Одновременная треугольная возможность
6 Алгебры треугольных матриц
- 6.1 Борелевские подгруппы и борелевские подалгебры
- 6.2 Примеры
7 См. Также
8 Ссылки

Описание

Матрица вида

L = [ℓ 1, 1 0 ℓ 2, 1 ℓ 2, 2 ℓ 3, 1 ℓ 3, 2 ⋱ ⋮ ⋮ ⋱ ⋱ ℓ n, 1 ℓ n, 2… ℓ n, n – 1 ℓ n, n] { displaystyle L = { begin {bmatrix} ell _ {1,1} 0 \ ell _ {2,1} ell _ {2,2} \ ell _ {3,1} ell _ {3,2} ddots \ vdots vdots ddots точки \ ell _ {n, 1} ell _ {n, 2} ldots ell _ {n, n-1} ell _ {n, n} end {bmatrix}} } ${ displaystyle L = { begin {bmatrix} ell _ {1,1} 0 \ ell _ {2,1} ell _ {2,2} \ ell _ {3,1 } ell _ {3,2} ddots \ vdots vdots ddots ddots \ ell _ {n, 1} ell _ {n, 2} ldots ell _ {n, n-1} ell _ {n, n} end {bmatrix}}}$

называется нижнетреугольной матрицей или левой треугольной матрицей, и аналогично матрицей вида

U = [u 1, 1 u 1, 2 u 1, 3… u 1, nu 2, 2 u 2, 3… u 2, n ⋱ ⋱ ⋮ ⋱ un – 1, n 0 un, n] { displaystyle U = { begin {bmatrix} u_ {1,1} u_ {1, 2} u_ {1,3} ldots u_ {1, n} \ u_ {2,2} u_ {2,3} ldots u_ {2, n} \ ddots ddots vdots \ ddots u_ {n-1, n} \ 0 u_ {n, n} end {bmatrix}}} ${ displaystyle U = { begin {bmatrix} u_ {1,1 } u_ {1,2} u_ {1,3} ldots u_ {1, n} \ u_ {2,2} u_ {2,3} ldots u_ {2, n} \ ddots ddots vdots \ ddots u_ {n-1, n} \ 0 u_ {n, n} end {bmatrix}}}$

называется верхнетреугольной матрицей или правотреугольной матрица . Нижняя или левая треугольная матрица обычно обозначается переменной L, а верхняя или правая треугольная матрица обычно обозначается переменной U или R.

Матрица, которая является как верхней, так и нижней треугольной, – это диагональ. Матрицы, которые аналогичны треугольным матрицам, называются треугольными матрицами .

Неквадратная (или иногда любая) матрица с нулями над (под) диагональю называется нижней (верхней) трапецеидальной матрицей. Ненулевые элементы образуют форму трапеции .

Примеры

Эта матрица

[1 4 1 0 6 4 0 0 1] { displaystyle { begin {bmatrix} 1 4 1 \ 0 6 4 \ 0 0 1 \ end {bmatrix}}} ${ displaystyle { begin {bmatrix} 1 4 1 \ 0 6 4 \ 0 0 1 \ end {bmatrix}}}$

является верхним треугольником, и эта матрица

[1 0 0 2 8 0 4 9 7] { displaystyle { begin {bmatrix} 1 0 0 \ 2 8 0 \ 4 9 7 \ end {bmatrix}}} ${ displaystyle { begin {bmatrix} 1 0 0 \ 2 8 0 \ 4 9 7 \ end {bmatrix}}}$

является нижним треугольником.

Прямая и обратная подстановка

Матричное уравнение в форме L x = b { displaystyle mathbf {L} mathbf {x} = mathbf {b}}или U x = b { displaystyle mathbf {U} mathbf {x} = mathbf {b}}очень легко решить с помощью итеративного процесса под названием прямая подстановка для нижнетреугольных матриц и аналогичная обратная подстановка для верхнетреугольных матриц. Процесс называется так потому, что для нижнетреугольных матриц сначала вычисляется x 1 { displaystyle x_ {1}} $x_ {1}$ , а затем это подставляется в следующее уравнение для решения для x 2 { displaystyle x_ {2}} $x_{2}$ и повторяется до xn { displaystyle x_ {n}} $x_ {n}$ . В верхней треугольной матрице мы работаем в обратном направлении, сначала вычисляя xn { displaystyle x_ {n}} $x_ {n}$ , а затем подставляя это обратно в предыдущее уравнение, чтобы найти xn – 1 { displaystyle x_ {n-1}} $x_{n-1}$ и повторение до x 1 { displaystyle x_ {1}} $x_ {1}$ .

Обратите внимание, что это не требует инвертирования матрицы.

Прямая подстановка

Матричное уравнение L x = b может быть записано как система линейных уравнений

ℓ 1, 1 x 1 = b 1 ℓ 2, 1 Икс 1 + ℓ 2, 2 Икс 2 знак равно б 2 ⋮ ⋮ ⋱ ⋮ ℓ м, 1 Икс 1 + ℓ м, 2 Икс 2 + ⋯ + ℓ м, mxm = bm { displaystyle { begin {matrix} ell _ {1,1} x_ {1} = b_ {1} \ ell _ {2,1} x_ {1} + ell _ {2,2} x_ {2} = b_ { 2} \ vdots vdots ddots vdots \ ell _ {m, 1} x_ {1} + ell _ {m, 2} x_ {2} + dotsb + ell _ {m, m} x_ {m} = b_ {m} \ end {matrix}}} ${ displaystyle { begin {matrix} ell _ {1,1} x_ {1} = b_ {1} \ ell _ { 2,1} x_ {1} + ell _ {2,2} x_ {2} = b_ {2} \ vdots vdots ddots vdots \ ell _ {m, 1} x_ {1} + ell _ {m, 2} x_ {2} + dotsb + ell _ {m, m} x_ {m} = b_ {m} \ конец {матрица}}}$

Обратите внимание, что первое уравнение (ℓ 1, 1 x 1 = b 1 { displaystyle ell _ {1,1} x_ {1} = b_ {1}} $ell _ {1,1} x_ {1} = b_ {1}$ ) включает только x 1 { displaystyle x_ {1}} $x_ {1}$ , и, таким образом, можно напрямую найти x 1 { displaystyle x_ {1}} $x_ {1}$ . Второе уравнение включает только x 1 { displaystyle x_ {1}} $x_ {1}$ и x 2 { displaystyle x_ {2}} $x_{2}$ , и поэтому может быть решено один раз подставить в уже решенное значение вместо x 1 { displaystyle x_ {1}} $x_ {1}$ . Продолжая таким образом, k { displaystyle k}-ое уравнение включает только x 1,…, xk { displaystyle x_ {1}, dots, x_ {k} } $x_ {1}, dots, x_ {k}$ , и можно найти для xk { displaystyle x_ {k}} $x_ {k}$ , используя ранее решенные значения для x 1,…, xk – 1 { displaystyle x_ {1}, dots, x_ {k-1}} $x_ {1}, dots, x_ {k-1}$ .

В результате получаются следующие формулы:

x 1 = b 1 ℓ 1, 1, x 2 = b 2 – ℓ 2, 1 x 1 ℓ 2, 2, xm = bm – i = 1 m – 1 ℓ m, ixi ℓ m, m. { displaystyle { begin {align} x_ {1} = { frac {b_ {1}} { ell _ {1,1}}}, \ x_ {2} = { frac {b_ { 2} – ell _ {2,1} x_ {1}} { ell _ {2,2}}}, \ vdots \ x_ {m} = { frac {b_ {m } – sum _ {i = 1} ^ {m-1} ell _ {m, i} x_ {i}} { ell _ {m, m}}}. end {align}}} ${ displaystyle { begin {выровнено} x_ {1} = { frac {b_ {1}} { ell _ {1,1}}}, \ x_ {2} = { frac {b_ {2} - ell _ {2,1} x_ {1}} { ell _ {2,2}}}, \ vdots \ x_ {m} = { frac {b_ {m} - sum _ {i = 1} ^ {m-1} ell _ {m, i} x_ {i}} { ell _ {m, m}}}. end {align}}}$

Матричное уравнение с верхнетреугольной матрицей U можно решить аналогичным образом, только работая в обратном направлении.

Приложения

Прямая замена используется в финансовой начальной загрузке для построения кривой доходности.

Свойства

транспонирование верхней треугольной матрицы является нижней треугольной матрицей и наоборот.

Матрица, которая является как симметричной, так и треугольной, диагональной. Аналогичным образом, матрица, которая является как нормальной (что означает AA = AA, где A – сопряженное транспонирование ), так и треугольной, также является диагональной. Это можно увидеть, посмотрев на диагональные входы AA и AA.

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

На самом деле верно больше: собственные значения треугольной матрицы – это в точности ее диагональные элементы. Более того, каждое собственное значение встречается ровно k раз на диагонали, где k – его алгебраическая кратность, то есть его кратность как корень характеристического многочлена п A (x) = det ⁡ (x I – A) { displaystyle p_ {A} (x) = operatorname {det} (xI-A)} ${ displaystyle p_ {A} (x) = operatorname {det} (xI-A)}$ из A. Другими словами, характеристический многочлен треугольной матрицы A размера n × n равен

p A (x) = (x – a 11) (x – a 22) ⋯ (x – ann) { displaystyle p_ {A} (x) = (x-a_ {11}) (x-a_ {22}) cdots (x-a_ {nn})} ${ displaystyle p_ {A} (x) = (x-a_ {11}) (x-a_ {22}) cdots (x-a_ {nn})}$

то есть уникальный многочлен степени n, корни которого являются диагональными элементами A (с кратности). Чтобы увидеть это, заметьте, что x I – A { displaystyle xI-A} xI-A также треугольный и, следовательно, его определитель det ⁡ (x I – A) { displaystyle operatorname { det} (xI-A)}– произведение его диагональных элементов (x – a 11) (x – a 22) ⋯ (x – ann) { displaystyle (x-a_ { 11}) (x-a_ {22}) cdots (x-a_ {nn})} ${ displaystyle (x-a_ {11}) (x-a_ {22}) cdots (x-a_ {nn})}$ .

Особые формы

Унитреугольная матрица

Если записи на main диагональ (верхней или нижней) треугольной матрицы все равны 1, матрица называется (верхняя или нижняя) унитреугольная .

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

Все единичные треугольники матрицы унипотентны.

Строго треугольная матрица

Если все элементы на главной диагонали (верхней или нижней) треугольной матрицы равны 0, матрица называется строго (верхняя или нижняя) треугольная .

Все строго треугольные матрицы являются нильпотентными.

атомарными треугольными матрицами

атомарными (верхними или нижними) треугольными матрица – это особая форма унитреугольной матрицы, где все недиагональные элементы равны нулю, за исключением записей в одном столбце. Такая матрица также называется матрицей Фробениуса, матрицей Гаусса или матрицей преобразования Гаусса .

Треугольником

Матрицей , подобный треугольной матрице, упоминается как триангулируемая . Абстрактно это эквивалентно стабилизации флага : верхнетреугольные матрицы – это в точности те, которые сохраняют стандартный флаг , который задается стандартным упорядоченным базисом (e 1,…, en) { displaystyle (e_ {1}, ldots, e_ {n})} $(e_ {1}, ldots, e_ {n})$ и результирующий флаг 0 < ⟨ e 1 ⟩ < ⟨ e 1, e 2 ⟩ < ⋯ < ⟨ e 1, …, e n ⟩ = K n. {displaystyle 0<leftlangle e_{1}rightrangle <leftlangle e_{1},e_{2}rightrangle <cdots <leftlangle e_{1},ldots,e_{n}rightrangle =K^{n}.} $0 < left langle e_ {1} right rangle < left langle e_ {1}, e_ {2} right rangle < cdots < left langle e_ {1}, ldots, e_ {n} right rangle = K ^ {n}.$ Все флаги сопряжены (поскольку общая линейная группа действует транзитивно на базисах), поэтому любая матрица, стабилизирующая флаг, аналогична матрице, стабилизирующей стандартный флаг.

Любая комплексная квадратная матрица допускает треугольную форму. Фактически, матрица A над полем , содержащая все собственные значения A (например, любая матрица над алгебраически замкнутым полем ), подобна треугольной матрице. Это можно доказать с помощью индукции по тому факту, что A имеет собственный вектор, взяв фактор-пространство по собственному вектору и проведя индукцию, чтобы показать, что A стабилизирует флаг и, таким образом, является треугольным относительно базиса для этого флага.

Более точное утверждение дает теорема Жордана о нормальной форме, которая утверждает, что в этой ситуации A подобна верхнетреугольной матрице очень конкретной формы. Однако более простого результата триангуляции часто бывает достаточно, и в любом случае он используется при доказательстве теоремы Жордана о нормальной форме.

В случае комплексных матриц можно сказать больше о триангуляризации, а именно, что любая квадратная матрица A имеет разложение Шура. Это означает, что A унитарно эквивалентна (то есть подобна, используя унитарную матрицу в качестве замены базиса) верхнетреугольной матрице; это следует путем взятия эрмитовой основы флага.

Одновременная треугольная возможность

Набор матриц A 1,…, A k { displaystyle A_ {1}, ldots, A_ {k}} $A_ {1}, ldots, A_ {k}$ называются одновременно треугольными, если существует основание, при котором все они являются верхнетреугольными; эквивалентно, если они поддаются верхнему треугольнику с помощью одной матрицы подобия P. Такой набор матриц легче понять, рассматривая алгебру матриц, которую он генерирует, а именно все многочлены из A i, { displaystyle A_ {i},} $A_{i},$ обозначается K [A 1,…, A k]. { displaystyle K [A_ {1}, ldots, A_ {k}].} $K [A_ {1}, ldots, A_ {k}].$ Одновременная триангулируемость означает, что эта алгебра сопряжена в подалгебру Ли верхнетреугольных матриц и эквивалентна тому, что эта алгебра является подалгебра Ли подалгебры Бореля.

. Основной результат состоит в том, что (над алгебраически замкнутым полем) коммутирующие матрицы A, B { displaystyle A, B} A, B или, в более общем смысле, A 1,…, A k { displaystyle A_ {1}, ldots, A_ {k}} $A_ {1}, ldots, A_ {k}$ одновременно треугольными. Это можно доказать, сначала показав, что коммутирующие матрицы имеют общий собственный вектор, а затем проведя индукцию по размерности, как и раньше. Это было доказано Фробениусом, начиная с 1878 г. для коммутирующей пары, как обсуждалось в коммутирующих матриц. Что касается единственной матрицы, по комплексным числам они могут быть треугольными с помощью унитарных матриц.

Тот факт, что коммутирующие матрицы имеют общий собственный вектор, можно интерпретировать как результат Nullstellensatz Гильберта: коммутирующие матрицы образуют коммутативную алгебру K [A 1,…, A k] { displaystyle K [A_ {1}, ldots, A_ {k}]} $K [A_ {1}, ldots, A_ {k}]$ более K [x 1,…, xk] { displaystyle K [x_ {1}, ldots, x_ {k}]} $K [x_ {1}, ldots, x_ {k}]$ , которое можно интерпретировать как многообразие в k-мерном аффинном пространстве, и наличие (общего) собственного значения (и, следовательно, общего собственного вектора) соответствует этому многообразию, имеющему точку (непустой), который является содержанием (weak) Nullstellensatz. В алгебраических терминах эти операторы соответствуют представлению алгебры полиномов от k переменных.

Это обобщается с помощью теоремы Ли, которая показывает, что любое представление разрешимой алгебры Ли одновременно является треугольным верхним углом, причем случай коммутирующих матриц является абелева алгебра Ли случай, причем абелева тем более разрешима.

В более общем смысле и точнее, набор матриц A 1,…, A k { displaystyle A_ {1}, ldots, A_ {k}} $A_ {1}, ldots, A_ {k}$ одновременно треугольным тогда и только тогда, когда матрица p (A 1,…, A k) [A i, A j] { displaystyle p (A_ {1}, ldots, A_ {k}) [A_ {i}, A_ {j}]} $p (A_ {1}, ldots, A_ {k}) [A_ {i}, A_ {j}]$ является нильпотентным для всех многочленов p от k некоммутирующих переменных, где [A i, A j] { displaystyle [A_ {i}, A_ {j}]} $[A_ {i}, A_ {j}]$ – коммутатор ; для коммутации A i { displaystyle A_ {i}} $A_ {i}$ коммутатор обращается в нуль, поэтому это верно. Это было доказано в (Drazin, Dungey Gruenberg 1951); краткое доказательство приведено в (Прасолов 1994, стр. 178–179 ). Одно направление ясно: если матрицы одновременно треугольные, то [A i, A j] { displaystyle [A_ {i}, A_ {j}]} $[A_ {i}, A_ {j}]$ строго верхнетреугольным (следовательно нильпотентный), который сохраняется умножением на любой A k { displaystyle A_ {k}} $A_ {k}$ или их комбинацию – он все равно будет иметь нули на диагонали в основе треугольника.

Алгебры треугольных матриц

Двоичные нижние унитреугольные теплицы матрицы, умноженные с использованием операций F2. Они образуют таблицу Кэли из Z4 и соответствуют степеням перестановки 4-битного кода Грея.

Верхняя треугольность сохраняется при многих операциях:

Сумма двух верхних треугольников матрица является верхнетреугольной.
Произведение двух верхнетреугольных матриц является верхнетреугольной.
Обратная матрица верхней треугольной матрицы, если существует, является верхнетреугольной.
произведение верхнетреугольной матрицы и скаляра является верхнетреугольным.

Вместе эти факты означают, что верхнетреугольные матрицы образуют подалгебру в ассоциативной алгебре квадратных матриц для данного размер. Кроме того, это также показывает, что верхнетреугольные матрицы можно рассматривать как подалгебру Ли в алгебре Ли квадратных матриц фиксированного размера, где скобка Ли [a, b] задается коммутатором ab – ba. Алгебра Ли всех верхнетреугольных матриц является разрешимой алгеброй Ли. Ее часто называют борелевской подалгеброй алгебры Ли всех квадратных матриц.

Все эти результаты остаются в силе, если верхний треугольник полностью заменен на нижний; в частности, нижнетреугольные матрицы также образуют алгебру Ли. Однако операции смешивания верхних и нижних треугольных матриц, как правило, не дают треугольных матриц. Например, сумма верхней и нижней треугольных матриц может быть любой матрицей; произведение нижнего треугольника на верхнюю треугольную матрицу также не обязательно треугольное.

Набор унитреугольных матриц образует группу Ли.

Набор строго верхних (или нижних) треугольных матриц образует нильпотентную алгебру Ли, обозначенную n. { displaystyle { mathfrak {n}}.}Эта алгебра является производной алгеброй Ли от b { displaystyle { mathfrak {b}}}, алгебра Ли всех верхнетреугольных матриц; в символах n = [b, b]. { displaystyle { mathfrak {n}} = [{ mathfrak {b}}, { mathfrak {b}}].}Кроме того, n { displaystyle { mathfrak { n}}}– алгебра Ли группы Ли унитреугольных матриц.

Фактически, согласно теореме Энгеля, любая конечномерная нильпотентная алгебра Ли сопряжена с подалгеброй строго верхнетреугольных матриц, то есть конечномерной нильпотентной алгеброй Ли одновременно строго верхнетреугольником.

Алгебры верхнетреугольных матриц имеют естественное обобщение в функциональном анализе, которое дает алгебры гнезд на гильбертовых пространствах.

подгруппы Бореля и подалгебры Бореля

Набор обратимых треугольных матриц данного вида (верхнего или нижнего) образует группу, действительно, группу Ли, которая является подгруппой общей линейная группа всех обратимых матриц. Треугольная матрица обратима в точности тогда, когда ее диагональные элементы обратимы (ненулевые).

По действительным числам эта группа разъединяется, имея 2 n { displaystyle 2 ^ {n}} $2 ^ {n}$ компонентов соответственно, поскольку каждая диагональная запись является положительной или отрицательной. Компонент единицы – это обратимые треугольные матрицы с положительными элементами на диагонали, а группа всех обратимых треугольных матриц является полупрямым произведением этой группы и группы диагональных матриц с ± 1 { displaystyle pm 1} pm 1 по диагонали, соответствующей компонентам.

Алгебра Ли группы Ли обратимых верхнетреугольных матриц – это набор всех верхнетреугольных матриц, не обязательно обратимых, и является разрешимой алгеброй Ли. Это, соответственно, стандартная подгруппа Бореля B группы Ли GL n и стандартная борелевская подалгебра b { displaystyle { mathfrak { b}}}алгебры Ли gl n.

Верхнетреугольные матрицы – это в точности те, которые стабилизируют стандартный флаг. Обратимые среди них образуют подгруппу общей линейной группы, сопряженные подгруппы которой определены как стабилизатор некоторого (другого) полного флага. Эти подгруппы являются борелевскими подгруппами. Группа обратимых нижнетреугольных матриц является такой подгруппой, поскольку она является стабилизатором стандартного флага, ассоциированного со стандартным базисом в обратном порядке.

Стабилизатор частичного флага, полученный путем забвения некоторых частей стандартного флага, может быть описан как набор блочных верхнетреугольных матриц (но его элементы не все треугольные матрицы). Сопряженные с такой группой подгруппы определены как стабилизатор некоторого частичного флага. Эти подгруппы называются параболическими подгруппами.

Примеры

Группа верхних унитреугольных матриц 2 на 2 изоморфна аддитивной группе поля скаляры; в случае комплексных чисел это соответствует группе, образованной параболическими преобразованиями Мёбиуса ; верхние унитреугольные матрицы 3 на 3 образуют группу Гейзенберга.

См. также

Список литературы

Источник

1. По методу Гаусса. Всякая
неособенная матрица, для которой,
имеет обратную матрицу. Очевидно, чтоА*А^–1=Е. запишем это
равенство в виде системыnуравнений сnнеизвестными

;
(37)

где а_ik– элементы матрицыА;

z_kj– элементы обратной матрицы (А^–1);

_ij– элементы
единичной матрицы.

При этом _ij=

Для нахождения элементов одного столбца
обратной матрицы необходимо решить
соответствующую линейную систему (37) с
матрицей А. Так для полученияj-го
столбца дляА^–1(z₁_j_,z₂_j,…z_nj)
решается система:

(38)

Следовательно для обращения матрицы Анужноnраз решить
систему (38) приj=.
Поскольку матрицаАсистемы не
меняется, то исключение неизвестных
осуществляется только один раз, а (n–1)
раз при решении (38) делается только
обратный ход с соответствующим изменением
правой ее части.

2. Другой подход к определению обратной матрицы а–1

где – определитель
матрицы,А_ij– алгебраические дополнения
соответствующих элементов матрицыА.

3. Обращение матрицы а посредством треугольных матриц

Известно, что всякая обратная матрица,
если она существует, то по структуре
будет такая же, как и исходная, т.к.

А^–1А =АА^–1=Е=.
(39)

Рассмотрим пример обращения матрицы
3-го порядка следующего вида:

А=.
(40)

Решение. МатрицуА^–1ищем в виде

А^–1=.
(41)

Перемножая АиА^–1с учетом
(39) будем иметьt₁₁= 1;t₁₁+ 2t₂₁= 0; 2t₂₂= 1;

Отсюда последовательно находим t₁₁= 1;t₂₁= –1/2;t₃₁= 0;t₂₂= 1/2;t₃₂= –1/3;t₃₃= 1/3, следовательно

А^–1=.
(42)

Перемножив (42) и (40) получим (39).

Известно, что любая произвольная матрица
Аможет быть представлена в виде
двух треугольных.

Например, пусть имеется матрица

.
(43)

Будем искать Т₁=иТ₂=.
Диагональ в матрицеТ₂искусственно берется равной 1. Тогда

A =T₁T₂. (44)

Реализуя (44) и сравнивая с (43), получим

Сравнивая значения правой и левой частей
и выполняя простейшие вычисления,
очевидно:

t₁₁
= 1; t₁₁r₁₂
= –1; t₁₁r₁₃
= 2;

t₂₁
= –1; t₂₁r₁₂
+ t₂₂
= 5; t₂₁r₁₃+
t₂₂
r₂₃=
4;

t₃₁= 2;t₃₁r₁₂+t₃₂= –1;t₃₁r₁₃+t₃₂ r₂₃+t₃₃= 14;

Решив полученную систему, получим

t₁₁= 1;t₂₁= –1;t₃₁= 2;

t₂₂= 4;t₃₂= 6;t₃₁= 1;

r₁₂=–1;r₁₃= 2;r₂₃= 3/2.

Таким образом Т₁=иТ₂=,
тогдаA^–1=
.

2.5. Применение метода итераций для уточнения элементов обратной матрицы

Точность получения элементов обратной
матрицы естественно оценивается
соотношением

А^–1А =А⁰=Е.

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

Пусть для неособенной матрицы Аполучено приближенное значение элементов
матрицыА^–1. Обозначим ее
черезD₀A^–1. Тогда для
уточнения элементов обратной матрицы
строится следующий итерационный процесс:

F_k_–1=E–AD_k_–1,k =1,2,3… ; (*)

D_k=D_k_–1(E
+F_k_–1);k = 1,2,3… (**)

Доказано, что итерации сходятся, если
начальная матрица D₀достаточно близка к искомойА^–1.

В данной итерационной схеме матрица Fна каждом шаге как бы оценивает близость
матрицыDкА^–1.

Схема работает следующим образом.

Сначала по (*) при k
= 1 находитсяF₀=E–AD₀,
затем находится произведениеD₀F₀.

По итерации (**) при k= 1 находитсяD₁
=D₀+ D₀F₀.

Чтобы проверить, достигнута ли желаемая
точность, вычисляется AD₁,
а по (*) приk = 2,
вычисляетсяF₁=E –AD₁и, если наибольший элемент матрицыF₁<,
итерации прекращаются иA^–1D₁.

– 39–

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

Источник

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

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

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

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

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

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

Метод Гаусса

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

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

${displaystyle Lambda _{1}cdot dots cdot Lambda _{n}cdot A=Lambda A=ERightarrow Lambda =A^{-1}}$

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

С помощью союзной матрицы

${displaystyle A^{-1}={frac {1}{det A}}cdot (C^{*})^{T}}$

${displaystyle C^{*}}$ – союзная матрица;

${displaystyle (C^{*})^{T}}$ – матрица, полученная в результате транспонирования союзной матрицы;

Полученная матрица A^-1 и будет обратной. Сложность алгоритма зависит от сложности алгоритма расчета определителя O_det и равна O(n²)O_det.

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

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

Ниже представлен псевдокод на языке C++ алгоритма обращения матрицы с помощью LUP-разложения.

Matrix Inverse(const Matrix &A) {
    //n - размерность квадратной матрицы A
    const int n=A.Rows();
    //при инициализации задается размерность nxn
    Matrix X(n, n);
    Matrix P(n, n);
    Matrix C(n, n);
    //предполагается что в результате следующего вызова матрица C = L + U - E
    LUP(A, C, P);
    for(int k = n-1; k >= 0; k--) {
        X[ k ][ k ] = 1;
        for( int j = n-1; j > k; j--) X[ k ][ k ] -= C[ k ][ j ]*X[ j ][ k ];
        X[ k ][ k ] /= C[ k ][ k ];
        for( int i = k-1; i >= 0; i-- ) {
            for( int j = n-1; j > i; j-- ) {
                X[ i ][ k ] -= C[ i ][ j ]*X[ j ][ k ];
                X[ k ][ i ] -= C[ j ][ i ]*X[ k ][ j ];
            }
            X[ i ][ k ] /= C[ i ][ i ];
        }
    }
    X = X*P
    return( X );
}

В случае использования вектора перестановок (см. LUP-разложение) вместо финального умножения потребуется следующий код:

int temp;
for( int i = 0; i < n; i++ ) {
    temp = i;
    while( p[ temp ] != i ) temp++;
    X.SwapColumns(i, temp);
    p[ temp ] = p[ i ];
}

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

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

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

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

${displaystyle {begin{cases}Psi _{k}=E-AU_{k},\U_{k+1}=U_{k}sum _{i=0}^{n}Psi _{k}^{i}end{cases}}}$

Зейделева модификация метода

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

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

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

См. также

Псевдообратные матрицы

Эта страница использует содержимое раздела Википедии на русском языке. Оригинальная статья находится по адресу: Обратная матрица. Список первоначальных авторов статьи можно посмотреть в истории правок. Эта статья так же, как и статья, размещённая в Википедии, доступна на условиях CC-BY-SA .

Источник

Свойства обратной матрицы[править | править код]

Способы нахождения обратной матрицы[править | править код]

Точные (прямые) методы[править | править код]

Метод Жордана—Гаусса[править | править код]

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

Использование LU- или LUP-разложения[править | править код]

Итерационные методы[править | править код]

Выбор начального приближения[править | править код]

Примеры[править | править код]

Матрица 2 × 2[править | править код]

Примечания[править | править код]

Ссылки[править | править код]

Содержание

Описание

Примеры

Прямая и обратная подстановка

Прямая подстановка

Приложения

Свойства

Особые формы

Унитреугольная матрица

Строго треугольная матрица

атомарными треугольными матрицами

Треугольником

Одновременная треугольная возможность

Алгебры треугольных матриц

подгруппы Бореля и подалгебры Бореля

Примеры

См. также

Список литературы

2. Другой подход к определению обратной матрицы а–1

3. Обращение матрицы а посредством треугольных матриц

2.5. Применение метода итераций для уточнения элементов обратной матрицы

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

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

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

Метод Гаусса

С помощью союзной матрицы

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

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

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

Зейделева модификация метода

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

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

См. также

Вам также может понравиться

Получился жидкий сметанный крем для торта как исправить

Как найти единомышленников для создания бизнеса

Как найти пары равных дробей

Добавить комментарий Отменить ответ