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

В математической дисциплине линейной алгебры , А матрица разложение или разложение матрицы является разложением из матрицы в произведение матриц. Есть много различных матричных разложений; каждый находит применение среди определенного класса проблем.

Пример [ править ]

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

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

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

Разложения, связанные с решением систем линейных уравнений [ править ]

LU разложение [ править ]

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

Уменьшение LU [ править ]

Блочная декомпозиция LU [ править ]

Факторизация ранга [ править ]

• Применимо к: m -by- n матрице A ранга r
• Разложение: где C - матрица с полным столбцом ранга размером m на r, а F - матрица с полным рангом строки размером r на n.${\ displaystyle A = CF}$
• Комментарий: Оценка разложение может быть использован для вычисления псевдообратной матрицы из А , ^[2] , который можно применить , чтобы получить все решения линейной системы .${\ displaystyle Ax = b}$

Разложение Холецкого [ править ]

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

QR-разложение [ править ]

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

Факторизация RRQR [ править ]

Интерполяционная декомпозиция [ править ]

Разложения на основе собственных значений и связанных понятий [ править ]

Eigendecomposition [ править ]

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

Реальное разложение Шура [ править ]

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

QZ разложение [ править ]

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

Факторизация Такаги [ править ]

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

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

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

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

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

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

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

Другие разложения [ править ]

Полярное разложение [ править ]

• Применимо к: любой квадратной комплексной матрицы 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^{*}}$

Алгебраическое полярное разложение [ править ]

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

Разложение Мостова [ править ]

• Применимо к: квадратной, сложной, невырожденной матрице А . ^{[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 является неотрицательным п матрицы с размерностью п диагональной матрицей. ^[12]${\displaystyle A=S^{T}{\textrm {diag}}(D,D)S}$${\displaystyle S\in {\text{Sp}}(2n)}$

Обобщения [ править ]

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

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

См. Также [ править ]

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

Примечания [ править ]

Ссылки [ править ]

• Чоудхури, Дипа; Хорн, Роджер А. (апрель 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. Кёнигль. Ges. Gött (на немецком языке), 1904 : 49–91.
• Хорн, Роджер А .; Мерино, Деннис И. (январь 1995 г.). «Контрагредиентная эквивалентность: каноническая форма и некоторые приложения» . Линейная алгебра и ее приложения . 214 : 43–92. DOI : 10.1016 / 0024-3795 (93) 00056-6 .
• Мейер, CD (2000), Матричный анализ и прикладная линейная алгебра , SIAM , ISBN 978-0-89871-454-8
• Schmidt, E. (1907), "Zur Theorie der linearen und nichtlinearen Integralgleichungen. I Teil. Entwicklung willkürlichen Funktionen nach System vorgeschriebener" , Mathematische Annalen (на немецком языке), 63 (4): 433–476, doi : 1014497 / b.
• Саймон, С .; Блюм, Л. (1994). Математика для экономистов . Нортон. ISBN 978-0-393-95733-4.
• Стюарт, GW (2011), Фредгольм, Гильберт, Шмидт: три фундаментальные статьи по интегральным уравнениям (PDF) , извлеченные 2015-01-06
• Townsend, A .; Trefethen, LN (2015), "Непрерывные аналоги матричных факторизаций", Proc. R. Soc. , 471 (+2173): 20140585, Bibcode : 2014RSPSA.47140585T , DOI : 10.1098 / rspa.2014.0585 , ПМК  4277194 , PMID  25568618

Внешние ссылки [ править ]

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