Разложение матрицы

Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 17 апреля 2022 года; проверки требует 1 правка.

Разложе́ние ма́трицы — представление матрицы $A$ в виде произведения матриц, обладающих некоторыми определёнными свойствами (например, ортогональностью, симметричностью, диагональностью). У каждого класса матричных разложений имеется своя область применения; в частности, многие эффективные алгоритмы вычислительной линейной алгебры^[англ.] основаны на построении соответствующих матричных разложений.

Разложения для решения СЛАУ

LU-разложение

Ограничения: матрица $A$ — квадратная и невырожденная, причём все её ведущие главные миноры отличны от нуля^[1].
Вид разложения: $A=LU$ , где $L$ — нижняя треугольная матрица, а $U$ — верхняя треугольная. Для однозначности разложения обычно дополнительно требуют, что матрица $L$ была унитреугольной, т. е. треугольной матрицей с диагональными элементами, равными единице (иногда вместо этого требование унитреугольности накладывают на матрицу $U$ )^[2].
Сходные разложения: LDU-разложение в виде $A=LDU$ , где $L$ — нижняя унитреугольная матрица, $U$ — верхняя унитреугольная, а $D$ — диагональная.
Сходные разложения: LUP-разложение в виде $PA=LU$ , где $P$ — матрица перестановок (выбирается в процессе построения разложения), $L$ нижняя унитреугольная матрица, $U$ — верхняя треугольная матрица. Это — обобщение LU-разложения на случай произвольных невырожденных матриц.
Существование: LUP-разложение существует для любой квадратной матрицы $A$ . Когда матрица $P$ сводится к единичной матрице, LUP-разложение сводится к LU-разложению.
LUP и LU-разложения используются при решении СЛАУ $Ax=b$ размерности $n\times n$ . Соответствующие методы представляют собой варианты матричной формы метода Гаусса. Матрица $P$ характеризует при этом совокупный эффект перестановок строк в методе Гаусса.

Ранговая факторизация

Ограничения: произвольная матрица $A$ размера $m\times n$ и ранга $r$ .

Вид разложения: $A=CF$ , где $C$ — матрица $m\times r$ и $F$ — матрица $r\times n$ .
Ранговая факторизация может быть использована для вычисления псевдообратной матрицы, которая применяется при отыскании общего решения СЛАУ $Ax=b$ .

Разложение Холецкого

Ограничения: симметричная положительно определённая матрица $A$ ^[3].
Вид разложения: $A=U^{T}U$ (или, что эквивалентно, $A=LL^{T}$ ), где матрица $U$ — верхняя треугольная (соответственно, матрица $L$ — нижняя треугольная)^[3].
Сходные разложения: альтернативой является модифицированное разложение Холецкого (LDL-разложение), которое позволяет избежать извлечения корней (в нём матрица $L$ — нижняя унитреугольная, а $D$ — диагональная).
Разложение Холецкого единственно.
Разложение Холецкого также применимо, если матрица $A$ эрмитова и положительно определена.
Разложение Холецкого применяется для решения СЛАУ $Ax=b$ , если матрица $A$ имеет соответствующие свойства. Этот способ решения, по сравнению с методом LU-разложения, заведомо численно устойчив и требует в два раза меньше арифметических операций^[4].

QR-разложение

Ограничения: произвольная матрица $A$ размера $m\times n$ .
Вид разложения: $A=QR$ , где $Q$ — ортогональная матрица размера $m\times m$ , и $R$ — верхняя треугольная размера $m\times n$ .
Сходные разложения: существуют аналогичные QL-, RQ- и LQ-разложения.
В силу ортогональности матрицы $Q$ (что означает совпадение обратной матрицы $Q^{-1}$ с транспонированной матрицей $Q^{T}$ ) система $Ax=b$ эквивалентна системе $Rx=Q^{T}b$ с треугольной матрицей, решение которой не доставляет труда.
Одним из способов получения матрицы $Q$ является процесс Грама ― Шмидта, и тогда $R=Q^{T}A$ .
Построение QR-разложения является основой QR-алгоритма ― одного из методов поиска собственных векторов и значений матрицы.
Алгоритмы решения СЛАУ на основе QR-разложения практически одинаково работают как для хорошо обусловленных, так и для сингулярных систем^[5].

Интерполяционное разложение

Ограничения: произвольная матрица $A$ размерности $m\times n$ и ранга $r$ .
Вид разложения: $A=A_{(:,J)}X$ , где $J$ — подмножество из $r$ индексов $1,...,n$ ; матрица $A_{(:,J)}$ состоит из соответствующих столбцов изначальной матрицы; $X$ — $r\times n$ матрица, все элементы которой по модулю не больше 2 (кроме того, $X$ содержит единичную подматрицу размерности $r\times r$ ). Аналогичное разложение можно получить и по строкам.

Разложения, связанные с собственными или сингулярными значениями

Спектральное разложение

Ограничения: диагонализуемая квадратная матрица $A$ , т. е. имеющая набор из $n$ различных собственных векторов (при этом собственным значениям не обязательно различаться).
Вид разложения: $A=VDV^{-1}$ , где $D$ — диагональная, образованная из собственных значений $A$ , а столбцы $V$ — соответствующие собственные вектора.
Существование: матрица размерности $n\times n$ всегда имеет $n$ собственных значений (с учётом кратности), которые могут быть упорядочены (не единственным способом), чтобы построить диагональную матрицу $D$ размерности $n\times n$ и соответствующую матрицу из ненулевых столбцов $V$ , которые удовлетворяют равенству $AV=VD$ . Если $n$ собственных векторов различны, тогда матрица $V$ имеет обратную, что и даст искомое разложение $A=VDV^{-1}$ ^[6].
Всегда можно нормировать собственные векторы, чтобы те имели длину 1. Если $A$ вещественная симметричная матрица, то $V$ всегда обратима и нормализуема. В этом случае матрица $V$ оказывается ортогональной, поскольку собственные векторы ортогональны по отношению друг к другу. Таким образом, искомое разложение (которое в рассматриваемом случае всегда существует) можно записать как $A=VDV^{T}$ .
Необходимым и достаточным условием диагонализуемости является совпадение геометрической и алгебраической кратности каждого собственного значения. В частности, наличие $n$ различных собственных значений является достаточным (но не необходимым) условием.
Спектральное разложение полезно для понимания решений систем линейных обыкновенных дифференциальных уравнений или разностных уравнений. Например, разностное уравнение $x_{t+1}=Ax_{t}$ с начальным условием $x_{0}=c$ имеет решение $x_{t}=A^{t}c$ , что можно записать иначе как $x_{t}=VD^{t}V^{-1}c$ (в случае, если $A=VDV^{-1}$ ). Возведение в степень $t$ диагональной матрицы $D$ сведётся к возведению каждого элемента на диагонали в степень $t$ , что несравнимо проще, чем $A$ (если, конечно, последняя изначально не имеет диагональный вид).

Жорданова нормальная форма

Ограничения: квадратная матрица $A$ .
Вид разложения: $A=CJC^{-1}$ , где $J$ — жорданова матрица, а $C$ — матрица перехода к новому базису.
Жорданова нормальная форма является обобщением диагональной формы матрицы $A$ , составленной из собственных значений, на случай, когда геометрическая кратность одного или нескольких собственных значений меньше алгебраической кратности.

Разложение Шура

Ограничения: квадратная матрица $A$ .
Существует две версии разложения: для случая вещественной матрицы и для случая комплексной матрицы. Последняя всегда имеет комплексное разложение Шура.
Вид разложения (вещественный случай): $A=VSV^{T}$ (все матрицы в обеих частях равенства составлены из строго вещественных значений). В этом случае $V$ — ортогональная матрица, а $S$ — квазитреугольная. Последняя называется вещественной формой Шура. Блоки на диагонали $S$ либо размера $1\times 1$ (в таком случае они представляют собой действительные собственные значения) или $2\times 2$ (образуемые парой комплексно-сопряжённых собственных чисел).
Вид разложения (комплексный случай): $A=UTU^{H}$ , где $U$ — унитарная, $U^{H}$ — её эрмитово-сопряжённая, а $T$ — верхняя треугольная матрица, называемая комплексной формой Шура, которая содержит собственные значения $A$ на диагонали.

QZ-разложение

Ограничения: квадратные матрицы $A$ и $B$ .
Существует две версии разложения: комплексная и действительная.
Вид разложения (комплексный случай): $A=QSZ^{H},B=QTZ^{H}$ , где $Q$ и $Z$ — унитарные матрицы, $Z^{H}$ — эрмитово-сопряжённая к $Z$ , $S$ и $T$ — верхне-треугольные матрицы.
В указанном разложении соотношение диагональных элементов в $S$ и соответствующих в $T$ , $\lambda _{i}=S_{ii}/T_{ii}$ являются обобщёнными собственными значениями, которые являются решением обобщённой задачи поиска собственных значений $Av=\lambda Bv$ (где $\lambda$ — неизвестный скаляр и $v$ — неизвестный ненулевой вектор).
Вид разложения (вещественный случай): $A=QSZ^{T},B=QTZ^{T}$ , где все матрицы состоят строго из вещественных значений. $Q,Z$ — ортогональные матрицы, а $S,T$ — квазитреугольные, состоящие из блоков $1\times 1$ или $2\times 2$ (аналогичных соответствующим блокам в разложении Шура).

Сингулярное разложение

Ограничения: произвольная матрица $A$ размера $m\times n$ ^[7].
Вид разложения: $A=U\Sigma V^{H}$ , где $\Sigma$ — неотрицательная диагональная матрица, $U,V$ — унитарные матрицы, а $V^{H}$ — эрмитово-сопряжённая. В вещественном случае $A=U\Sigma V^{T}$ , причём $\Sigma$ , как и прежде, неотрицательная диагональная матрица, $U,V$ — ортогональные^[7]^[8].
Элементы на диагонали матрицы $\Sigma$ называются сингулярными значениями матрицы $A$ и обозначаются $\sigma _{j}.$ Число ненулевых сингулярных значений матрицы $A$ равно рангу этой матрицы^[9].
Сингулярное разложение, как и спектральное разложение, включает в себя отыскание базиса подпространств, действие на элементы которых оператора ${\mathcal {A}}$ эквивалентны умножению на скаляр (т. е. $Av=\sigma _{j}v$ ), но при этом сингулярное разложение является более общим методом, поскольку матрица $A$ не обязана быть квадратной.

Другие разложения

Полярное разложение

Ограничения: квадратная комплексная матрица $A$ ^[10].
Вид разложения (комплексный случай): $A=SU$ , где $S$ — эрмитова матрица с неотрицательными ведущими минорами, а $U$ — унитарная матрица^[10]^[11].
Вид разложения (вещественный случай): $A=SQ$ , где $S$ — симметричная матрица с неотрицательными ведущими минорами, а $Q$ — ортогональная матрица^[12]^[13].
Для невырожденной матрицы полярное разложение единственно, а для вырожденной матрицы однозначно определён лишь множитель $S$ ^[10].
Полярное разложение матрицы в комплексном случае является аналогом представления произвольного комплексного числа $z$ в виде $z=|z|e^{i\varphi }$ ^[14].

Фробениусова нормальная форма

Ограничения: квадратная матрица $A$ .
Вид разложения: $A=PCP^{-1}$ , где $C$ — блочно-диагональная матрица, состоящая из сопровождающих матриц для унитарных многочленов $f_{i}$ таких, что $f_{i+1}$ кратен $f_{i}$ . $P$ — переходная матрица.

Примечания

↑ Икрамов, 1991, с. 20.
↑ Воеводин и Кузнецов, 1984, с. 75—76.
↑ ¹ ² Воеводин и Кузнецов, 1984, с. 176.
↑ William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery. . 2.9 Cholesky Decomposition // Numerical Recipes in C. 2nd edition. — Cambridge: Cambridge University Press. — ISBN 0-521-43108-5.
↑ QR- и SVD- разложения: «плохие» СЛАУ (неопр.). Дата обращения: 17 ноября 2016. Архивировано 22 июня 2017 года.
↑ Meyer, 2000, p. 514.
↑ ¹ ² Икрамов, 1991, с. 21.
↑ Воеводин и Кузнецов, 1984, с. 80.
↑ Форсайт Дж., Малькольм М., Моулер К. . Машинные методы математических вычислений. — М.: Мир, 1980. — 280 с. — С. 214, 225.
↑ ¹ ² ³ Воеводин и Кузнецов, 1984, с. 78.
↑ Гантмахер, 1988, с. 234—236.
↑ Воеводин и Кузнецов, 1984, с. 79.
↑ Гантмахер, 1988, с. 244.
↑ Гантмахер, 1988, с. 236.

Литература

Воеводин В. В., Кузнецов Ю. А. . Матрицы и вычисления. — М.: Наука, 1984. — 320 с.
Гантмахер Ф. Р. . Теория матриц. 4-е изд. — М.: Наука, 1988. — 552 с. — ISBN 5-02-013722-7.
Икрамов Х. Д. . Несимметричная проблема собственных значений. Численные методы. — М.: Наука, 1991. — 240 с. — ISBN 5-02-014462-2.
Meyer, Carl D. . Matrix Analysis and Applied Linear Algebra. — Philadelphia: SIAM, 2000. — xii + 718 p. — ISBN 0-89871-454-0.

Источник — https://ru.wiki.x.io/w/index.php?title=Разложение_матрицы&oldid=127463946