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

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

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

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

• Ограничения: матрица $A$ — квадратная и невырожденная, причём все её ведущие главные миноры отличны от нуляШаблон:Sfn.
• Вид разложения: $A=LU$, где $L$ — нижняя треугольная матрица, а $U$ — верхняя треугольная. Для однозначности разложения обычно дополнительно требуют, что матрица $L$ была унитреугольной, т. е. треугольной матрицей с диагональными элементами, равными единице (иногда вместо этого требование унитреугольности накладывают на матрицу $U$)Шаблон:Sfn.
• Сходные разложения: 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$Шаблон:Sfn.
• Вид разложения: $A=U^{T}U$ (или, что эквивалентно, $A=L{L}^T$), где матрица $U$ — верхняя треугольная (соответственно, матрица $L$ — нижняя треугольная)Шаблон:Sfn.
• Сходные разложения: альтернативой является модифицированное разложение Холецкого (LDL-разложение), которое позволяет избежать извлечения корней (в нём матрица $L$ — нижняя унитреугольная, а $D$ — диагональная).
• Разложение Холецкого единственно.
• Разложение Холецкого также применимо, если матрица $A$ эрмитова и положительно определена.
• Разложение Холецкого применяется для решения СЛАУ $Ax=b$, если матрица $A$ имеет соответствующие свойства. Этот способ решения, по сравнению с методом LU-разложения, заведомо численно устойчив и требует в два раза меньше арифметических операций.

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-разложения практически одинаково работают как для хорошо обусловленных, так и для сингулярных систем.

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

• Ограничения: произвольная матрица $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=VD{V}^{-1}$, где $D$ — диагональная, образованная из собственных значений $A$, а столбцы $V$ — соответствующие собственные вектора.
• Существование: матрица размерности $n\times n$ всегда имеет $n$ собственных значений (с учётом кратности), которые могут быть упорядочены (не единственным способом), чтобы построить диагональную матрицу $D$ размерности $n\times n$ и соответствующую матрицу из ненулевых столбцов $V$, которые удовлетворяют равенству $AV=VD$. Если $n$ собственных векторов различны, тогда матрица $V$ имеет обратную, что и даст искомое разложение $A=VD{V}^{-1}$Шаблон:Sfn.
• Всегда можно нормировать собственные векторы, чтобы те имели длину 1. Если $A$ вещественная симметричная матрица, то $V$ всегда обратима и нормализуема. В этом случае матрица $V$ оказывается ортогональной, поскольку собственные векторы ортогональны по отношению друг к другу. Таким образом, искомое разложение (которое в рассматриваемом случае всегда существует) можно записать как $A=VD{V}^T$.
• Необходимым и достаточным условием диагонализуемости является совпадение геометрической и алгебраической кратности каждого собственного значения. В частности, наличие $n$ различных собственных значений является достаточным (но не необходимым) условием.
• Спектральное разложение полезно для понимания решений систем линейных обыкновенных дифференциальных уравнений или разностных уравнений. Например, разностное уравнение $x_{t+1}=A{x}_t$ с начальным условием $x_0=c$ имеет решение $x_t=A^{t}c$, что можно записать иначе как $x_t=V{D}^t{V}^{-1}c$ (в случае, если $A=VD{V}^{-1}$). Возведение в степень $t$ диагональной матрицы $D$ сведётся к возведению каждого элемента на диагонали в степень $t$, что несравнимо проще, чем $A$ (если, конечно, последняя изначально не имеет диагональный вид).

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга