Матричное разложение

В математической дисциплине линейной алгебры матричная декомпозиция или матричная факторизация — это факторизация матрицы в произведение матриц. Существует много различных матричных декомпозиций; каждая из них находит применение среди определенного класса задач.

В численном анализе для реализации эффективных матричных алгоритмов используются различные разложения .

Например, при решении системы линейных уравнений матрица A может быть разложена с помощью LU-разложения . LU-разложение факторизует матрицу на нижнюю треугольную матрицу L и верхнюю треугольную матрицу U. Системы и требуют меньше сложений и умножений для решения по сравнению с исходной системой , хотя может потребоваться значительно больше цифр в неточной арифметике, такой как числа с плавающей точкой .${\displaystyle A\mathbf {x} =\mathbf {b} }$ ${\displaystyle L(U\mathbf {x} )=\mathbf {b} }$${\displaystyle U\mathbf {x} =L^{-1}\mathbf {b} }$${\displaystyle A\mathbf {x} =\mathbf {b} }$

Аналогично, разложение QR выражает A как QR с Q — ортогональной матрицей и R — верхней треугольной матрицей. Система Q ( R x ) = b решается с помощью R x = Q ^T b = c , а система R x = c решается с помощью « обратной подстановки ». Количество требуемых сложений и умножений примерно вдвое больше, чем при использовании решателя LU, но в неточной арифметике больше цифр не требуется, поскольку разложение QR численно устойчиво .

• Традиционно применимо к: квадратной матрице A , хотя прямоугольные матрицы также могут быть применимы. ^{[1] [nb 1]}
• Разложение: , где L — нижний треугольный , а U — верхний треугольный .${\displaystyle A=LU}$
• Связано: разложение LDU имеет вид , где L — нижняя треугольная матрица с единицами на диагонали, U — верхняя треугольная матрица с единицами на диагонали, а D — диагональная матрица .${\displaystyle A=LDU}$
• Связано: разложение LUP имеет вид , где L — нижняя треугольная матрица , U — верхняя треугольная матрица , а P — матрица перестановки .${\displaystyle PA=LU}$
• Существование: LUP-разложение существует для любой квадратной матрицы A. Когда P является единичной матрицей , LUP-разложение сводится к LU-разложению.
• Комментарии: Разложения LUP и LU полезны при решении систем линейных уравнений размером n на n . Эти разложения суммируют процесс исключения Гаусса в матричной форме. Матрица P представляет любые перестановки строк, выполненные в процессе исключения Гаусса. Если исключение Гаусса дает форму ступенчатой ​​строки без необходимости перестановок строк, то P  =  I , поэтому существует разложение LU.${\displaystyle A\mathbf {x} =\mathbf {b} }$

• Применимо к: матрице A размером m на n ранга r
• Разложение: где C — это матрица ранга столбцов размером m на r, а F — это матрица ранга строк размером r на n.${\displaystyle A=CF}$
• Комментарий: Ранговую факторизацию можно использовать для вычисления псевдообратной матрицы Мура–Пенроуза для A ^[2] , которую можно применить для получения всех решений линейной системы .${\displaystyle A\mathbf {x} =\mathbf {b} }$

• Применимо к: квадратным , эрмитовым , положительно определенным матрицам${\displaystyle A}$
• Разложение: , где — верхний треугольник с действительными положительными диагональными элементами${\displaystyle A=U^{*}U}$${\displaystyle U}$
• Комментарий: если матрица эрмитова и положительно полуопределена, то она имеет разложение вида, если диагональные элементы разрешается принимать равными нулю${\displaystyle A}$${\displaystyle A=U^{*}U}$${\displaystyle U}$
• Уникальность: для положительно определенных матриц разложение Холецкого единственно. Однако оно не единственно в случае положительно полуопределенных матриц.
• Комментарий: если является действительным и симметричным, то имеет все действительные элементы${\displaystyle A}$${\displaystyle U}$
• Комментарий: Альтернативой является разложение ЛПНП , которое позволяет избежать извлечения квадратных корней.

• Применимо к: матрице A размером m на n с линейно независимыми столбцами
• Разложение: где — унитарная матрица размером m на m , а — верхняя треугольная матрица размером m на n.${\displaystyle A=QR}$${\displaystyle Q}$${\displaystyle R}$
• Уникальность: В общем случае он не уникален, но если имеет полный ранг , то существует единственный , имеющий все положительные диагональные элементы. Если является квадратным, то также уникален.${\displaystyle A}$${\displaystyle R}$${\displaystyle A}$${\displaystyle Q}$
• Комментарий: QR-разложение обеспечивает эффективный способ решения системы уравнений . Тот факт, что является ортогональным, означает, что , так что это эквивалентно , что очень легко решить, поскольку является треугольным .${\displaystyle A\mathbf {x} =\mathbf {b} }$${\displaystyle Q}$${\displaystyle Q^{\mathrm {T} }Q=I}$${\displaystyle A\mathbf {x} =\mathbf {b} }$${\displaystyle R\mathbf {x} =Q^{\mathsf {T}}\mathbf {b} }$${\displaystyle R}$

• Также называется спектральным разложением .
• Применимо к: квадратной матрице A с линейно независимыми собственными векторами (не обязательно различными собственными значениями).
• Разложение: , где D — диагональная матрица, образованная из собственных значений A , а столбцы V — соответствующие собственные векторы A.${\displaystyle A=VDV^{-1}}$
• Существование: Матрица A размером n на n всегда имеет n (комплексных) собственных значений, которые можно упорядочить (более чем одним способом) для формирования диагональной матрицы D размером n на n и соответствующей матрицы ненулевых столбцов V , удовлетворяющей уравнению собственных значений . обратима тогда и только тогда, когда n собственных векторов линейно независимы (то есть каждое собственное значение имеет геометрическую кратность , равную его алгебраической кратности ). Достаточным (но не необходимым) условием для этого является то, что все собственные значения различны (в этом случае геометрическая и алгебраическая кратности равны 1) ${\displaystyle AV=VD}$${\displaystyle V}$
• Комментарий: Всегда можно нормализовать собственные векторы так, чтобы они имели длину один (см. определение уравнения собственных значений)
• Комментарий: Каждая нормальная матрица A (то есть матрица, для которой , где — сопряженное транспонирование ) может быть разложена на собственные числа. Для нормальной матрицы A (и только для нормальной матрицы) собственные векторы также могут быть сделаны ортонормированными ( ), а разложение на собственные числа читается как . В частности, все унитарные , эрмитовы или косоэрмитовы (в вещественном случае все ортогональные , симметричные или кососимметричные , соответственно) матрицы являются нормальными и, следовательно, обладают этим свойством.${\displaystyle AA^{*}=A^{*}A}$${\displaystyle A^{*}}$ ${\displaystyle VV^{*}=I}$${\displaystyle A=VDV^{*}}$
• Комментарий: Для любой действительной симметричной матрицы A собственное разложение всегда существует и может быть записано как , где D и V являются действительными значениями.${\displaystyle A=VDV^{\mathsf {T}}}$
• Комментарий: Собственное разложение полезно для понимания решения системы линейных обыкновенных дифференциальных уравнений или линейных разностных уравнений. Например, разностное уравнение, начинающееся с начального условия, решается с помощью , что эквивалентно , где V и D — матрицы, образованные из собственных векторов и собственных значений матрицы A . Поскольку матрица D диагональна, возведение ее в степень , просто подразумевает возведение каждого элемента на диагонали в степень t . Это гораздо проще сделать и понять, чем возведение A в степень t , поскольку A обычно не является диагональной.${\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 D^{t}}$

Нормальная форма Жордана и разложение Жордана–Шевалле

• Применимо к: квадратной матрице A
• Комментарий: нормальная форма Жордана обобщает собственное разложение на случаи, когда имеются повторяющиеся собственные значения и их невозможно диагонализировать, разложение Жордана–Шевалле делает это без выбора базиса.

• Применимо к: квадратной матрице A
• Разложение (комплексная версия): , где U — унитарная матрица , — сопряженная транспонированная матрица U , а T — верхняя треугольная матрица, называемая комплексной формой Шура , которая имеет собственные значения A вдоль своей диагонали.${\displaystyle A=UTU^{*}}$${\displaystyle U^{*}}$
• Комментарий: если A — нормальная матрица , то T — диагональна и разложение Шура совпадает со спектральным разложением.

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

• Также называется: обобщенное разложение Шура.
• Применимо к: квадратным матрицам A и B
• Комментарий: существует две версии этого разложения: комплексная и действительная.
• Разложение (комплексная версия): где Q и Z — унитарные матрицы , верхний индекс * обозначает сопряженную транспонированную матрицу , а S и T — верхние треугольные матрицы.${\displaystyle A=QSZ^{*}}$${\displaystyle B=QTZ^{*}}$
• Комментарий: в комплексном разложении QZ отношения диагональных элементов S к соответствующим диагональным элементам T , , являются обобщенными собственными значениями , которые решают обобщенную задачу на собственные значения (где — неизвестный скаляр, а v — неизвестный ненулевой вектор).${\displaystyle \lambda _{i}=S_{ii}/T_{ii}}$ ${\displaystyle A\mathbf {v} =\lambda B\mathbf {v} }$${\displaystyle \lambda }$
• Разложение (реальная версия): и где A , B , Q , Z , S , и T — матрицы, содержащие только действительные числа. В этом случае Q и Z — ортогональные матрицы , верхний индекс T представляет транспонирование , а S и T — блочные верхние треугольные матрицы. Блоки на диагонали S и T имеют размер 1×1 или 2×2.${\displaystyle A=QSZ^{\mathsf {T}}}$${\displaystyle B=QTZ^{\mathsf {T}}}$

• Применимо к: квадратной, комплексной, симметричной матрице A.
• Разложение: , где D — действительная неотрицательная диагональная матрица , а V — унитарная . обозначает матрицу, транспонированную к V .${\displaystyle A=VDV^{\mathsf {T}}}$${\displaystyle V^{\mathsf {T}}}$
• Комментарий: Диагональные элементы D являются неотрицательными квадратными корнями собственных значений .${\displaystyle AA^{*}=VD^{2}V^{-1}}$
• Комментарий: V может быть комплексным, даже если A действительно.
• Комментарий: Это не частный случай собственного разложения (см. выше), которое использует вместо . Более того, если A не является действительным, оно не является эрмитовым, и форма с использованием также не применима.${\displaystyle V^{-1}}$${\displaystyle V^{\mathsf {T}}}$${\displaystyle V^{*}}$

• Применимо к: матрице A размером m на n .
• Разложение: , где D — неотрицательная диагональная матрица , а U и V удовлетворяют . Здесь — сопряженная транспонированная матрица V (или просто транспонированная матрица , если V содержит только действительные числа), а I обозначает единичную матрицу (некоторой размерности).${\displaystyle A=UDV^{*}}$${\displaystyle U^{*}U=I,V^{*}V=I}$${\displaystyle V^{*}}$
• Комментарий : Диагональные элементы D называются сингулярными значениями A.
• Комментарий: Как и в случае с собственным разложением, приведенном выше, разложение по сингулярным значениям подразумевает нахождение базисных направлений, вдоль которых умножение матриц эквивалентно скалярному умножению, но оно имеет большую общность, поскольку рассматриваемая матрица не обязательно должна быть квадратной.
• Уникальность: сингулярные значения всегда определяются однозначно и не обязательно должны быть уникальными в общем случае.${\displaystyle A}$${\displaystyle U}$${\displaystyle V}$

Относится к вариантам существующих матричных разложений, таким как SVD, которые инвариантны относительно диагонального масштабирования.

• Применимо к: матрице A размером m на n .
• Разложение по сингулярным значениям, инвариантным к масштабу единиц: , где S — уникальная неотрицательная диагональная матрица сингулярных значений, инвариантных к масштабу единиц, U и V — унитарные матрицы , — сопряженная транспонированная матрица V , и положительные диагональные матрицы D и E.${\displaystyle A=DUSV^{*}E}$${\displaystyle V^{*}}$
• Комментарий: Аналогично SVD, за исключением того, что диагональные элементы S инвариантны относительно левого и/или правого умножения A на произвольные невырожденные диагональные матрицы, в отличие от стандартного SVD, для которого сингулярные значения инвариантны относительно левого и/или правого умножения A на произвольные унитарные матрицы.
• Комментарий: Является альтернативой стандартному SVD, когда требуется инвариантность относительно диагональных, а не унитарных преобразований A.
• Уникальность: Масштабно-инвариантные сингулярные значения (задаваемые диагональными элементами S ) всегда определяются однозначно. Диагональные матрицы D и E , а также унитарные U и V , в общем случае не обязательно уникальны.${\displaystyle A}$
• Комментарий: Матрицы U и V не совпадают с матрицами SVD.

Аналогичные масштабно-инвариантные разложения могут быть получены из других матричных разложений; например, для получения масштабно-инвариантных собственных значений. ^{[3] [4]}

• Применимо к: квадратной матрице A.
• Разложение: где — матрица Хессенберга , — унитарная матрица .${\displaystyle A=PHP^{*}}$${\displaystyle H}$${\displaystyle P}$
• Комментарий: часто является первым шагом в разложении Шура.

• Также известно как: разложение UTV , разложение ULV , разложение URV .
• Применимо к: матрице A размером m на n .
• Разложение: , где T — треугольная матрица , а U и V — унитарные матрицы .${\displaystyle A=UTV^{*}}$
• Комментарий: Аналогично разложению по сингулярным значениям и разложению Шура.

• Применимо к: любой квадратной комплексной матрице A.
• Разложение: (правое полярное разложение) или (левое полярное разложение), где U — унитарная матрица , а P и P' — положительно полуопределенные эрмитовы матрицы .${\displaystyle A=UP}$${\displaystyle A=P'U}$
• Уникальность: всегда уникален и равен (который всегда эрмитов и положительно полуопределен). Если обратим, то уникален.${\displaystyle P}$${\displaystyle {\sqrt {A^{*}A}}}$${\displaystyle A}$${\displaystyle U}$
• Комментарий: Поскольку любая эрмитова матрица допускает спектральное разложение с унитарной матрицей, можно записать как . Поскольку является положительно полуопределенной, все элементы в неотрицательны. Поскольку произведение двух унитарных матриц унитарно, взяв одну, можно записать которая является сингулярным разложением. Следовательно, существование полярного разложения эквивалентно существованию сингулярного разложения.${\displaystyle P}$${\displaystyle P=VDV^{*}}$${\displaystyle P}$${\displaystyle D}$${\displaystyle W=UV}$${\displaystyle A=U(VDV^{*})=WDV^{*}}$

• Применимо к: квадратной, комплексной, невырожденной матрице A. ^[5 ]
• Разложение: , где Q — комплексная ортогональная матрица, а S — комплексная симметричная матрица.${\displaystyle A=QS}$
• Уникальность: Если не имеет отрицательных действительных собственных значений, то разложение уникально. ^[6]${\displaystyle A^{\mathsf {T}}A}$
• Комментарий: Существование этого разложения эквивалентно тому, что оно подобно . ^[7]${\displaystyle AA^{\mathsf {T}}}$${\displaystyle A^{\mathsf {T}}A}$
• Комментарий: Вариантом этого разложения является , где R — действительная матрица, а C — круговая матрица. ^[6]${\displaystyle A=RC}$

• Применимо к: квадратной, комплексной , невырожденной матрице A. ^{[8] [9]}
• Разложение: , где U — унитарное, M — действительное антисимметричное, а S — действительное симметричное.${\displaystyle A=Ue^{iM}e^{S}}$
• Комментарий: Матрицу A можно также разложить как , где U ₂ является унитарным, M ₂ является действительным антисимметричным, а S ₂ является действительным симметричным. ^[6]${\displaystyle A=U_{2}e^{S_{2}}e^{iM_{2}}}$

• Применимо к: квадратной действительной матрице A со строго положительными элементами.
• Разложение: , где S — дважды стохастическая матрица , а D ₁ и D ₂ — действительные диагональные матрицы со строго положительными элементами.${\displaystyle A=D_{1}SD_{2}}$

• Применимо к: квадратной, комплексной матрице A с числовым диапазоном, содержащимся в секторе .${\displaystyle S_{\alpha }=\left\{re^{i\theta }\in \mathbb {C} \mid r>0,|\theta |\leq \alpha <{\frac {\pi }{2}}\right\}}$
• Разложение: , где C — обратимая комплексная матрица и при всех . ^{[10] [11]}${\displaystyle A=CZC^{*}}$${\displaystyle Z=\operatorname {diag} \left(e^{i\theta _{1}},\ldots ,e^{i\theta _{n}}\right)}$${\displaystyle \left|\theta _{j}\right|\leq \alpha }$

• Применимо к: квадратной, положительно определенной действительной матрице A порядка 2 n ×2 n .
• Разложение: , где — симплектическая матрица , а D — неотрицательная диагональная матрица размером n на n . ^[12]${\displaystyle A=S^{\mathsf {T}}\operatorname {diag} (D,D)S}$${\displaystyle S\in {\text{Sp}}(2n)}$

• Разложение: , в общем случае не уникально.${\displaystyle A=BB}$
• В случае положительной полуопределенности существует единственная положительная полуопределенность такая, что .${\displaystyle A}$${\displaystyle B}$${\displaystyle A=B^{*}B=BB}$

This section needs expansion with: examples and additional citations. You can help by adding to it. (December 2014)

Существуют аналоги SVD, QR, LU и факторизации Холецкого для квазиматриц и матриц или непрерывных матриц . ^[13] «Квазиматрица», как и матрица, представляет собой прямоугольную схему, элементы которой индексированы, но один дискретный индекс заменен непрерывным индексом. Аналогично, «матрица» непрерывна по обоим индексам. В качестве примера матрицы можно представить ядро ​​интегрального оператора .

Эти факторизации основаны на ранних работах Фредгольма (1903), Гильберта (1904) и Шмидта (1907). Для отчета и перевода на английский язык основополагающих работ см. Stewart (2011).

• Матричное расщепление
• Неотрицательная матричная факторизация
• Анализ главных компонент

• Choudhury, Dipa; Horn, Roger A. (апрель 1987 г.). «Комплексный ортогонально-симметричный аналог полярного разложения». Журнал SIAM по алгебраическим и дискретным методам . 8 (2): 219–225. doi :10.1137/0608019.
• Фредхольм, И. (1903), «Sur une classe d'equations fonctionnelles», Acta Mathematica (на французском языке), 27 : 365–390, doi : 10.1007/bf02421317
• Гильберт, Д. (1904), "Grundzüge einer allgemeinen Theorie der Linearen Integralgleichungen", Nachr. Кенигль. Гес. Гетт (на немецком языке), 1904 : 49–91.
• Хорн, Роджер А.; Мерино, Деннис И. (январь 1995 г.). «Контрагредиентная эквивалентность: каноническая форма и некоторые приложения». Линейная алгебра и ее приложения . 214 : 43–92. doi : 10.1016/0024-3795(93)00056-6 .
• Мейер, CD (2000), Матричный анализ и прикладная линейная алгебра, SIAM , ISBN 978-0-89871-454-8
• Шмидт, Э. (1907), «Zur Theorie der Linearen und Nichtlinearen Integralgleichungen. I Teil. Entwicklung willkürlichen Funktionen nach System vorgeschriebener», Mathematische Annalen (на немецком языке), 63 (4): 433–476, doi : 10.1007/bf01449770
• Саймон, К.; Блюм, Л. (1994). Математика для экономистов . Нортон. ISBN 978-0-393-95733-4.
• Стюарт, Г. В. (2011), Фредгольм, Гильберт, Шмидт: три фундаментальные статьи по интегральным уравнениям (PDF) , получено 06.01.2015
• Таунсенд, А.; Трефетен, Л. Н. (2015), "Непрерывные аналоги матричных факторизаций", Proc. R. Soc. A , 471 (2173): 20140585, Bibcode : 2014RSPSA.47140585T, doi : 10.1098/rspa.2014.0585, PMC  4277194 , PMID  25568618
• Джун, Лу (2021), Численное разложение матриц и его современные приложения: строгий первый курс , arXiv : 2107.02579

• Онлайн-калькулятор матриц
• Вычисление разложения матрицы Wolfram Alpha » Разложение LU и QR
• Математическая энциклопедия Springer » Факторизация матриц
• GraphLab Библиотека совместной фильтрации GraphLab , крупномасштабная параллельная реализация методов разложения матриц (на C++) для многоядерных процессоров.