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

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

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

Пример

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

Например, при решении системы линейных уравнений $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++) для многоядерных процессоров.