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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

Литература

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