В математической дисциплине линейной алгебры , А матрица разложение или разложение матрицы является разложением из матрицы в произведение матриц. Есть много различных матричных разложений; каждый находит применение среди определенного класса проблем.
Пример
В численном анализе используются различные декомпозиции для реализации эффективных матричных алгоритмов .
Например, при решении системы линейных уравнений , матрица A может быть разложена с помощью LU-разложения . Разложение LU факторизация матрицы в нижний треугольную матрице L и верхнюю треугольную матрицу U . Системы а также требует меньшего количества сложений и умножений для решения по сравнению с исходной системой , хотя может потребоваться значительно больше цифр в неточной арифметике, такой как с плавающей точкой .
Точно так же разложение QR выражает A как QR, где Q - ортогональная матрица, а R - верхнетреугольная матрица. Система Q ( R x ) = b решается с помощью R x = Q T b = c , а система R x = c решается с помощью « обратной подстановки ». Количество требуемых сложений и умножений примерно в два раза больше, чем при использовании решателя LU, но в неточной арифметике больше не требуется цифр, поскольку QR-разложение численно стабильно .
LU разложение
- Традиционно применимо к квадратной матрице A , хотя могут применяться и прямоугольные матрицы. [1] [номер 1]
- Разложение: , где L - нижний треугольник, а U - верхний треугольник.
- Связаны: LDU разложение является, где L - нижний треугольник с единицами на диагонали, U - верхний треугольник с единицами на диагонали, а D - диагональная матрица .
- Связаны: LUP разложение является, где L - нижний треугольник , U - верхний треугольник , а P - матрица перестановок .
- Существование: разложение LUP существует для любой квадратной матрицы A . Когда P является единичной матрицей , разложение LUP сводится к разложению LU. Если LU-декомпозиция существует, значит, LDU-декомпозиция существует. [2]
- Комментарии: LUP и LU-разложения полезны при решении n -by- n системы линейных уравнений.. Эти разложения суммируют процесс исключения Гаусса в матричной форме. Матрица P представляет любые перестановки строк, выполненные в процессе исключения Гаусса. Если исключение Гаусса дает форму эшелона строк без необходимости каких-либо перестановок строк, то P = I , поэтому существует разложение LU.
Сокращение LU
Блочная декомпозиция LU
Факторизация рангов
- Применимо к: m -by- n матрице A ранга r
- Разложение: где C - это матрица с полным столбцом ранга размером m на r, а F - матрица с полным рангом строки размером r на n.
- Комментарий: Оценка разложение может быть использовано для вычисления псевдообратной матрицы из А , [3] , который можно применить , чтобы получить все решения линейной системы .
Разложение Холецкого
- Применимо к: квадратной , эрмитовой , положительно определенной матрице A
- Разложение: , где является верхнетреугольным с вещественными положительными диагональными элементами
- Комментарий: если матрица является эрмитовым и положительно полуопределенным, то имеет разложение вида если диагональные элементы могут быть равны нулю
- Единственность: для положительно определенных матриц разложение Холецкого единственно. Однако в положительном полуопределенном случае он не уникален.
- Комментарий: если A действительный и симметричный, имеет все реальные элементы
- Комментарий: Альтернативой является разложение LDL , которое позволяет избежать извлечения квадратных корней.
QR-разложение
- Применимо к: m -by- n матрице A с линейно независимыми столбцами
- Разложение: где является унитарной матрицей размера М матрицы с размерностью м , иявляется верхней треугольной матрицей размера м матрицы с размерностью п
- Уникальность: в целом не уникальна, но если имеет полный ранг , то существует единственныйкоторый имеет все положительные диагональные элементы. Если квадратный, также уникален.
- Комментарий: QR-разложение обеспечивает эффективный способ решения системы уравнений. . Дело в том, чтоэто ортогональные означает , что, чтобы эквивалентно , который очень легко решить, так как является треугольной .
RRQR факторизация
Интерполяционная декомпозиция
Собственное разложение
- Также называется спектральным разложением .
- Применимо к: квадратной матрице A с линейно независимыми собственными векторами (не обязательно различными собственными значениями).
- Разложение: , Где D представляет собой диагональная матрица формируется из собственных значений из А , а столбцы V являются соответствующим собственными векторами из А .
- Существование: п матрицы с размерностью п матрица всегда имеет п (комплексные) собственные значения, которые могут быть заказаны (в более чем одним способе) с образованием п матрица с размерностью п диагональной матрицей D и соответствующей матрицей ненулевых столбцов V , который удовлетворяет уравнение на собственные значения . обратима тогда и только тогда, когда n собственных векторов линейно независимы (т. е. каждое собственное значение имеет геометрическую кратность, равную его алгебраической кратности ). Достаточным (но не необходимым) условием для этого является то, что все собственные значения различны (в этом случае геометрическая и алгебраическая кратность равны 1)
- Комментарий: всегда можно нормализовать собственные векторы, чтобы они имели длину, равную единице (см. Определение уравнения для собственных значений)
- Комментарий: каждая нормальная матрица A (т. Е. Матрица, для которой, где является сопряженным транспонированием ) может быть собственно разложен. Для нормальной матрицы A (и только для нормальной матрицы) собственные векторы также можно сделать ортонормированными (), а собственное разложение имеет вид . В частности, все унитарные , эрмитовы или кососимметричные (в вещественном случае все ортогональные , симметричные или кососимметричные соответственно) матрицы нормальны и, следовательно, обладают этим свойством.
- Комментарий: Для любой вещественной симметричной матрицы A всегда существует собственное разложение, и его можно записать как, где и D, и V являются действительными значениями.
- Комментарий: Собственное разложение полезно для понимания решения системы линейных обыкновенных дифференциальных уравнений или линейных разностных уравнений. Например, разностное уравнение начиная с начального состояния решается , что эквивалентно , Где V и D являются матрицами , образованные из собственных векторов и собственных значений А . Поскольку D диагональный, возводя его в степень, просто требует возведения каждого элемента на диагонали в степень t . Это намного проще сделать и понять, чем возвести A в степень t , поскольку A обычно не диагональна.
Разложение Жордана
Жордановой нормальной формы и разложение Жордана-Шевалье
- Применимо к: квадратной матрице A
- Комментарий: нормальная форма Жордана обобщает собственное разложение на случаи, когда есть повторяющиеся собственные значения и не могут быть диагонализованы, разложение Жордана – Шевалле делает это без выбора базиса.
Разложение Шура
- Применимо к: квадратной матрице A
- Разложение (сложная версия): , где U - унитарная матрица ,является сопряженной транспозицией из U , а Т представляет собой верхняя треугольная матрица называется комплексная Шура форма , которая имеет собственные значения из А вдоль его диагонали.
- Комментарий: если A - нормальная матрица , то T диагональна и разложение Шура совпадает со спектральным разложением.
Реальное разложение Шура
- Применимо к: квадратной матрице A
- Разложение: это версия разложения Шура, где а также содержат только действительные числа. Всегда можно написатьгде V - вещественная ортогональная матрица ,является транспонированной из V , и S представляет собой блок - верхняя треугольная матрица называется реальной формой Шура . Блоки на диагонали S имеют размер 1 × 1 (в этом случае они представляют действительные собственные значения) или 2 × 2 (в этом случае они получены из комплексно сопряженных пар собственных значений).
QZ разложение
- Также называется: обобщенное разложение Шура
- Применимо к: квадратным матрицам A и B
- Комментарий: есть две версии этой декомпозиции: сложная и реальная.
- Разложение (сложная версия): а также где Q и Z - унитарные матрицы , верхний индекс * представляет сопряженное транспонирование , а S и T - верхние треугольные матрицы.
- Комментарий: в комплексном разложении QZ отношения диагональных элементов S к соответствующим диагональным элементам T ,, являются обобщенными собственными значениями, которые решают обобщенную задачу на собственные значения (где - неизвестный скаляр, а v - неизвестный ненулевой вектор).
- Разложение (реальная версия): а также где A , B , Q , Z , S и T - матрицы, содержащие только действительные числа. В этом случае Q и Z - ортогональные матрицы , верхний индекс T представляет транспонирование , а S и T - блочные верхнетреугольные матрицы. Блоки на диагонали S и T имеют размер 1 × 1 или 2 × 2.
Факторизация Такаги
- Применимо к: квадрат, сложной, симметричной матрицы A .
- Разложение: , где D - вещественная неотрицательная диагональная матрица , а V - унитарная .обозначает матрицу транспонирование из V .
- Комментарий: диагональные элементы D являются неотрицательными квадратными корнями из собственных значений.
- Комментарий: V может быть сложным, даже если A реально.
- Комментарий: это не частный случай собственного разложения (см. Выше), в котором используется вместо . Более того, если A не является действительным, оно не эрмитово, и форма, использующая тоже не применяется.
Разложение по сингулярным числам
- Применимо к: м матрицу с размерностью п матрицы А .
- Разложение: , где D - неотрицательная диагональная матрица , а U и V удовлетворяют. Здесьявляется сопряженной транспозицией из V (или просто транспонированная , если V содержит только действительные числа), и я обозначает единичную матрицу (некоторой размерности).
- Комментарий: Диагональные элементы D называются сингулярные значения из A .
- Комментарий: Как и собственное разложение выше, разложение по сингулярным числам включает в себя поиск базисных направлений, по которым умножение матриц эквивалентно скалярному умножению, но оно имеет большую общность, поскольку рассматриваемая матрица не обязательно должна быть квадратной.
- Уникальность: особые значения всегда однозначно определены. а также не обязательно быть уникальным в целом.
Масштабно-инвариантные разложения
Относится к вариантам существующих матричных разложений, таких как SVD, которые инвариантны относительно диагонального масштабирования.
- Применимо к: м матрицу с размерностью п матрицы А .
- Разложение по сингулярным значениям, инвариантное единичному масштабу: , где S - единственная неотрицательная диагональная матрица масштабно-инвариантных сингулярных значений, U и V - унитарные матрицы ,является сопряженной транспозицией из V , и положительные диагональные матрицы D и E .
- Комментарий: Аналогичен SVD, за исключением того, что диагональные элементы S инвариантны относительно умножения A слева и / или справа на произвольные невырожденные диагональные матрицы, в отличие от стандартного SVD, для которого сингулярные значения инвариантны относительно слева и / или правое умножение A на произвольные унитарные матрицы.
- Комментарий: Является альтернативой стандартному СВД , когда требуется инвариантность по отношению к диагонали , а не унитарных преобразований A .
- Уникальность: масштабно-инвариантные особые значения (заданные диагональными элементами S ) всегда однозначно определены. Диагональные матрицы D и E и унитарные U и V , вообще говоря, не обязательно уникальны.
- Комментарий: матрицы U и V отличаются от матриц SVD.
Аналогичные масштабно-инвариантные разложения могут быть получены из других матричных разложений, например, для получения масштабно-инвариантных собственных значений. [4] [5]
Другие разложения
Полярное разложение
- Применимо к: любой квадратной комплексной матрицы A .
- Разложение: (правополярное разложение) или (левополярное разложение), где U - унитарная матрица, а P и P ' - положительные полуопределенные эрмитовы матрицы .
- Уникальность: всегда уникален и равен (который всегда эрмитов и положительно полуопределен). Если обратима, то уникален.
- Комментарий: Поскольку любая эрмитова матрица допускает спектральное разложение с унитарной матрицей, можно записать как . С положительно полуопределено, все элементы в неотрицательны. Поскольку произведение двух унитарных матриц унитарно, взявможно писать которое является разложением по сингулярным числам. Следовательно, существование полярного разложения эквивалентно существованию разложения по сингулярным значениям.
Алгебраическое полярное разложение
- Применимо к: квадратной, сложной, невырожденной матрице А . [6]
- Разложение: , где Q - комплексная ортогональная матрица, а S - комплексная симметричная матрица.
- Уникальность: Если не имеет отрицательных действительных собственных значений, то разложение единственное. [7]
- Комментарий: Существование этого разложения эквивалентно быть похожим на . [8]
- Комментарий: Вариант этой декомпозиции , где R - вещественная матрица, а C - круговая матрица . [7]
Разложение Мостова
- Применимо к: квадратной, сложной, невырожденной матрице А . [9] [10]
- Разложение: , где U унитарно, M вещественно антисимметрично, а S вещественно симметрично.
- Комментарий: Матрица A также может быть разложена как, Где U 2 является унитарным, М 2 являются реальным анти-симметричным и S 2 является реальным симметричным. [7]
Синхорн нормальной формы
- Применимо к: квадратной вещественной матрице A со строго положительными элементами.
- Разложение: , где S - двустохастическая матрица, а D 1 и D 2 - вещественные диагональные матрицы со строго положительными элементами.
Секторальная декомпозиция
- Применимо к: квадратной комплексной матрице A с числовым диапазоном, содержащимся в секторе.
- Разложение: , где C - обратимая комплексная матрица и со всеми . [11] [12]
Нормальная форма Вильямсона
- Применимо к квадратной положительно определенной вещественной матрице A порядка 2 n × 2 n .
- Разложение: , где является симплектической матрицей и D является неотрицательным н матрицей с размерностью п диагональной матрицей. [13]
Матричный квадратный корень
- Разложение: , не уникальна в целом.
- В случае положительного полуопределенного существует единственная положительно полуопределенная такой, что .
Обобщения
Существуют аналоги SVD, QR, LU и факторизации Холецкого для квазиматриц и c- матриц или непрерывных матриц . [14] «Квазиматрица», как и матрица, представляет собой прямоугольную схему, элементы которой индексированы, но один дискретный индекс заменен непрерывным индексом. Точно так же «c-матрица» непрерывна по обоим индексам. В качестве примера c-матрицы можно представить ядро интегрального оператора .
Эти факторизации основаны на ранних работах Фредгольма (1903) , Гильберта (1904) и Шмидта (1907) . Отчет и перевод основополагающих статей на английский см. В Stewart (2011) .
Смотрите также
- Расщепление матрицы
- Факторизация неотрицательной матрицы
- Анализ главных компонентов
Рекомендации
Заметки
- ^ Если не-квадратная матрица используется, однако, то матрица U также будет иметь такую же прямоугольную форму исходной матрицы A . Итак, призывая матрицу U было бы неправильнопоскольку правильный термин будет точто U является «строка формы эшелон» А . Кроме этого, нет никаких различий в факторизации LU для квадратных и неквадратных матриц.
Цитаты
- ^ Lay, Дэвид С. (2016). Линейная алгебра и ее приложения . Стивен Р. Лэй, Джудит Макдональд (Пятое глобальное издание). Харлоу. п. 142. ISBN. 1-292-09223-8. OCLC 920463015 .
- ^ Саймон и Блюм 1994 Глава 7.
- ^ Piziak, R .; Оделл, Польша (1 июня 1999 г.). «Полная ранговая факторизация матриц». Математический журнал . 72 (3): 193. DOI : 10,2307 / 2690882 . JSTOR 2690882 .
- ^ Ульманн, Дж. К. (2018), «Обобщенная обратная матрица, соответствующая диагональным преобразованиям», Журнал SIAM по матричному анализу , 239 (2): 781–800, doi : 10,1137 / 17M113890X
- ^ Ульманн, Дж. К. (2018), «Сохраняющая ранг обобщенная матрица, обратная для согласованности по отношению к подобию», IEEE Control Systems Letters , arXiv : 1804.07334 , doi : 10.1109 / LCSYS.2018.2854240 , ISSN 2475-1456
- ^ Чоудхури & Horn 1987 , стр. 219-225
- ^ а б в Бхатия, Раджендра (15 ноября 2013 г.). «Биполярный распад» . Линейная алгебра и ее приложения . 439 (10): 3031–3037. DOI : 10.1016 / j.laa.2013.09.006 .
- ^ Horn & Merino 1995 , стр. 43-92
- ^ Мостов, GD (1955), Некоторые новые теоремы о разложении для полупростых групп , Mem. Амер. Математика. Soc., 14 , Американское математическое общество, стр. 31–54.
- ^ Нильсен, Франк; Бхатия, Раджендра (2012). Матричная информационная геометрия . Springer. п. 224. arXiv : 1007.4402 . DOI : 10.1007 / 978-3-642-30232-9 . ISBN 9783642302329.
- ^ Чжан, Фучжэнь (30 июня 2014 г.). «Матричная декомпозиция и ее приложения» (PDF) . Линейная и полилинейная алгебра . 63 (10): 2033–2042. DOI : 10.1080 / 03081087.2014.933219 .
- ^ Друри, SW (ноябрь 2013 г.). «Детерминантные неравенства Фишера и гипотеза Хигема» . Линейная алгебра и ее приложения . 439 (10): 3129–3133. DOI : 10.1016 / j.laa.2013.08.031 .
- ^ Идель, Мартин; Сото Гаона, Себастьян; Вольф, Майкл М. (15.07.2017). «Границы возмущения для симплектической нормальной формы Вильямсона». Линейная алгебра и ее приложения . 525 : 45–58. arXiv : 1609.01338 . DOI : 10.1016 / j.laa.2017.03.013 .
- ^ Townsend & Trefethen 2015
Библиография
- Чоудхури, Дипа; Хорн, Роджер А. (апрель 1987 г.). «Комплексный ортогонально-симметричный аналог полярного разложения». Журнал СИАМ по алгебраическим и дискретным методам . 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. Königl. 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
- Шмидт, Э. (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 (две тысячи сто семьдесят-три): 20140585, Bibcode : 2014RSPSA.47140585T , DOI : 10.1098 / rspa.2014.0585 , ПМК 4277194 , PMID 25568618
Внешние ссылки
- Онлайн-калькулятор матрицы
- Вычисление разложения альфа-матрицы Wolfram »Разложение LU и QR
- Математическая энциклопедия Springer »Факторизация матриц
- GraphLab Библиотека коллаборативной фильтрации GraphLab , крупномасштабная параллельная реализация методов матричной декомпозиции (на C ++) для многоядерных процессоров.