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

Не путать с матричной факторизацией полинома .

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

Пример

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

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

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

связанные с решением систем

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

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

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

Сокращение LU

Основная статья: уменьшение LU

Разложение блоков LU

Основная статья: Разложение блоков LU

Ранговая

Основная статья: Ранговая факторизация

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

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

Основная статья: разложение Холецкого

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

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

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

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

Факторизация RRQR

Основная статья: факторизация RRQR

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

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

Разложения на основе собственных значений и связанных

Собственная декомпозиция

Основная статья: Собственное разложение (матрица)

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

Жордановое разложение

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

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

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

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

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

Шура

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

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

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

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

Факторизация Такаги

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

Разложение по сингулярным значениям

Основная статья: Разложение по сингулярным значениям

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

Масштабно-инвариантные разложения

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

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

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

Хессенберга

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

Полное

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

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

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

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

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

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

полярное

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

Разложение Мостова

• , комплексной, неособой матрице A. Применимо к: квадратной
• Разложение: $A=Ue^{iM}e^{S}$, где U унитарно, M вещественно антисимметрично и S вещественно симметрично.
• Комментарий: Матрицу A также можно разложить как $A=U_{2}e^{S_{2}}e^{iM_{2}}$, где U ₂ унитарно, M ₂ вещественно антисимметрично и S ₂ вещественно симметрично.

Синкхорн

Основная статья: теорема Синкхорна

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

декомпозиция

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

Уильямсона

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

Матричный квадратный корень

Основная статья: Квадратный корень из матрицы

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

Обобщения

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

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

См. также

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

Ссылки

Библиография

• Чоудхури, Дипа; Хорн, Роджер А. (апрель 1987 г.). «Комплексный ортогонально-симметричный аналог полярного разложения». SIAM Journal по алгебраическим и дискретным методам . 8 (2): 219–225. дои : 10.1137/0608019 .
• Фредхольм И. (1903), «Об одном классе функциональных уравнений», Acta Mathematica (на французском языке), 27 : 365–390, doi : 10.1007/bf02421317
• Гильберт, Д. (1904), "Основные особенности общей теории линейных интегральных уравнений", Nachr. Гез (на немецком языке), 1904 : 49–91.
• Хорн, Роджер А.; Мерино, Деннис И. (январь 1995 г.). «Контрагредиентная эквивалентность: каноническая форма и некоторые приложения» . Линейная алгебра и ее приложения . 214 : 43–92. дои : 10.1016/0024-3795(93)00056-6 .
• Мейер, CD (2000), Матричный анализ и прикладная линейная алгебра , SIAM , ISBN  978-0-89871-454-8
• Шмидт, Э. (1907), «К теории линейных и нелинейных интегральных уравнений. Часть I. Развитие произвольных функций по системе заданных правил» , Mathematical Annals (на немецком языке), 63 (4): 433–476. , дои : 10.1007/bf01449770
• Саймон, К.; Блюм, Л. (1994). Математика для экономистов . Нортон. ISBN  978-0-393-95733-4 .
• Стюарт, Г.В. (2011), Фредхольм, Гильберт, Шмидт: три фундаментальные статьи по интегральным уравнениям (PDF) , получено 6 января 2015 г.
• Таунсенд, А.; Трефетен, Л.Н. (2015), «Непрерывные аналоги матричных факторизаций», Proc. Р. Сок. A , 471 (2173): 20140585, Bibcode : 2014RSPSA.47140585T , doi : 10.1098/rspa.2014.0585 , PMC   4277194 , PMID   25568618
• Джун, Лу (2021), Числовое матричное разложение и его современные приложения: строгий первый курс , arXiv : 2107.02579

Внешние ссылки

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