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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

↑ Икрамов, 1991, с. 20.
↑ Воеводин и Кузнецов, 1984, с. 75—76.
↑ ^3,0 ^3,1 Воеводин и Кузнецов, 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.
↑ ^7,0 ^7,1 Икрамов, 1991, с. 21.
↑ Воеводин и Кузнецов, 1984, с. 80.
↑ Форсайт Дж., Малькольм М., Моулер К. . Машинные методы математических вычислений. — М.: Мир, 1980. — 280 с. — С. 214, 225.
↑ ^10,0 ^10,1 ^10,2 Воеводин и Кузнецов, 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.

[_58ec55cef3d12764-1] Икрамов, 1991, с. 20.

[_a3d5c21fbaea3cc4-2] Воеводин и Кузнецов, 1984, с. 75—76.

[_18c54659e3bc8703-3] 3,0 ^3,1 Воеводин и Кузнецов, 1984, с. 176.

[4] 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.

[5] QR- и SVD- разложения: «плохие» СЛАУ (неопр.). Дата обращения: 17 ноября 2016. Архивировано 22 июня 2017 года.

[_b11bf8dedc80b603-6] Meyer, 2000, p. 514.

[_58ec55cef3d12765-7] 7,0 ^7,1 Икрамов, 1991, с. 21.

[_f42a62574e34debb-8] Воеводин и Кузнецов, 1984, с. 80.

[9] Форсайт Дж., Малькольм М., Моулер К. . Машинные методы математических вычислений. — М.: Мир, 1980. — 280 с. — С. 214, 225.

[_f42a5f574e34d94a-10] 10,0 ^10,1 ^10,2 Воеводин и Кузнецов, 1984, с. 78.

[_52dfc4d9390f4212-11] Гантмахер, 1988, с. 234—236.

[_f42a5f574e34d94b-12] Воеводин и Кузнецов, 1984, с. 79.

[_1de10ab86b4b9ce4-13] Гантмахер, 1988, с. 244.

[_1de111b86b4ba883-14] Гантмахер, 1988, с. 236.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]