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

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

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

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

Основная статья: LU-разложение

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

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

Основная статья: 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=VDV^{-1}$, где $D$ — диагональная, образованная из собственных значений $A$, а столбцы $V$ — соответствующие собственные вектора.
• Существование: матрица размерности $n\times n$ всегда имеет $n$ собственных значений (с учётом кратности), которые могут быть упорядочены (не единственным способом), чтобы построить диагональную матрицу $D$ размерности $n\times n$ и соответствующую матрицу из ненулевых столбцов $V$, которые удовлетворяют равенству $AV=VD$. Если $n$ собственных векторов различны, тогда матрица $V$ имеет обратную, что и даст искомое разложение $A=VDV^{-1}$.
• Всегда можно нормировать собственные векторы, чтобы те имели длину 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$.
• Вид разложения: $A=U\Sigma V^{H}$, где $\Sigma$ — неотрицательная диагональная матрица, $U,V$ — унитарные матрицы, а $V^{H}$ — эрмитово-сопряжённая. В вещественном случае $A=U\Sigma V^{T}$, причём $\Sigma$, как и прежде, неотрицательная диагональная матрица, $U,V$ — ортогональные.
• Элементы на диагонали матрицы $\Sigma$ называются сингулярными значениями матрицы $A$ и обозначаются $\sigma _{j}.$ Число ненулевых сингулярных значений матрицы $A$ равно рангу этой матрицы.
• Сингулярное разложение, как и спектральное разложение, включает в себя отыскание базиса подпространств, действие на элементы которых оператора ${\mathcal {A}}$ эквивалентны умножению на скаляр (т. е. $Av=\sigma _{j}v$), но при этом сингулярное разложение является более общим методом, поскольку матрица $A$ не обязана быть квадратной.

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

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

Основная статья: Полярное разложение

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

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

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

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

Литература

• Воеводин В. В., Кузнецов Ю. А. . Матрицы и вычисления. — М.: Наука, 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.