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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Разложе́ние ма́трицы — представление матрицы в виде произведения матриц, обладающих некоторыми определёнными свойствами, например, ортогональностью, симметричностью, диагональностью — и потому облегчающих рассмотрение свойств линейного оператора с матрицей .

Разложения для решения СЛАУ[править | править вики-текст]

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

Ранговая факторизация[править | править вики-текст]

  • Ограничения: произвольная матрица размера и ранга .
  • Разложение: , где  — матрица и — матрица .
  • Ранговая факторицация может быть использована для вычисления псевдообратной матрицы, которая применяется в отыскании общего решения СЛАУ .

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

  • Ограничения: симметричная, положительно определённая матрица .
  • Разложение: (или, что эквивалентно, ), где матрица  — верхнетреугольная (соответственно, матрица  — нижнетреугольная).
  • Связанное: альтернативой является LDL-разложение, которое помогает избежать извлечения корней.
  • Разложение Холецкого единственно.
  • Разложение Холецкого также применимо, если матрица эрмитова и положительно определённая.
  • Разложение Холецкого применяется для решения СЛАУ , если матрица имеет соответствующие свойства. Этот способ решения, по сравнению с его более общими аналогами — методом Гаусса и LU-разложением, численно устойчивее и требует в два раза меньше арифметических операций.[1]

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

  • Ограничения: произвольная матрица размера .
  • Разложение: , где — ортогональная матрица размера , и верхнетреугольная размера .
  • Связанное: существуют аналогичные QL, RQ и LQ разложения.
  • QR-разложение даёт альтернативный способ решения СЛАУ , не вычисляя обратную матрицу для . Поскольку ортогональна (), то система эквивалентна , которая значительно упрощает решение в силу того, что треугольная.
  • Матрицу проще всего получить через процесс Грама-Шмидта, и тогда .
  • QR-разложение является основой QR-алгоритма — одного из методов поиска собственных векторов и значений матрицы.
  • Алгоритмы решения СЛАУ на основе QR-разложения практически одинаково работают как для хорошо обусловленных, так и для сингулярных систем.[2]

Интерполяционное разложение[править | править вики-текст]

  • Ограничения: произвольная матрица размерности и ранга .
  • Разложение: , где  — подмножество из индексов ; матрица состоит из соответствующих столбцов изначальной матрицы; матрица, все элементы которой по модулю не больше 2 (кроме того, содержит единичную подматрицу размерности ). Аналогичное разложение можно получить и по строкам.

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

Спектральное разложение[править | править вики-текст]

  • Ограничения: диагонализуемая квадратная матрица , т.е. имеющая набор из различных собственных векторов (при этом собственным значениям не обязательно различаться).
  • Разложение: , где  — диагональная, образованная из собственных значений , а столбцы — соответствующие собственные вектора.
  • Существование: матрица размерности всегда имеет собственных значений (с учетом кратности), которые могут быть упорядочены (не единственным способом), чтобы построить диагональную матрицу размерности и соответствующую матрицу из ненулевыми столбцов , которые удовлетворяют равенству . Если собственных векторов различны, тогда матрица имеет обратную, что и даст искомое разложение .[3]
  • Всегда можно нормировать собственные вектора, чтобы те имели длину 1. Если вещественная симметричная матрица, то всегда обратима и нормализуема. В этом случае , так как собственные вектора по отношению друг к другу ортогональны. Таким образом, разложение (которое всегда существует, в рассматриваемом случае) можно записать как .
  • Необходимым и достаточным условием диагонализуемости является совпадение геометрической и алгебраической кратности каждого собственного значения. В частности, наличие различных собственных значений является достаточным (но не необходимым) условием.
  • Спектральное разложение полезно в понимании решений систем линейных обыкновенных дифференциальных уравнений или разностных уравнений. Например, разностное уравнение с начальным условием имеет решение , что можно записать иначе как (в случае, если ). Возведение в степень диагональной матрицы сведётся к возведению каждого элемента на диагонали в степень , что несравнимо проще, чем (если конечно последняя изначально не имеет диагональный вид).

Жорданова нормальная форма[править | править вики-текст]

  • Ограничения: квадратная матрица .
  • Разложение: , где — жорданова матрица, а — матрица перехода в новый базис.
  • Жорданова нормальная форма является обобщением диагональной формы матрицы , составленной из собственных значений, на случай, когда геометрическая кратность одного или нескольких собственных значений меньше алгебраической кратности.

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

  • Ограничения: квадратная матрица .
  • Существует две версии разложения для случая вещественной матрицы и комплексной. Последняя всегда имеет комплексное разложение Шура.
  • Разложение (вещественное): (все матрицы в обоих частях равенства составлены из строго вещественных значений). В этом случае ортогональная матрица, а квазитреугольная. Последняя зовётся вещественной формой Шура. Блоки на диагонали либо размера (в таком случае они представляют собой действительные собственные значения) или (образуемые парой комплексно-сопряженных собственных чисел).
  • Разложение (комплексное): , где унитарная, — её эрмитово-сопряженная, а — верхняя треугольная матрица, называемая коплексной формой Шура, которая содержит собственные значения на диагонали.

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

  • Ограничения: квадратные матрицы и .
  • Существует две версии разложения комплексная и действительная.
  • Разложение (комплексное): , где и унитарные матрицы, эрмитово-сопряжённая к , и верхне-треугольные матрицы.
  • В указанном разложении соотношение диагональных элементов в и соответствующих в , являются обобщенными собственными значениями, которые являются решением обобщенной задачи поиска собственных значений (где неизвестный скаляр и неизвестный ненулевой вектор).
  • Разложение (вещественное): , где все матрицы состоят строго из вещественных значений. — ортогональные матрицы, а квазитреугольные, состоящие из блоков или (аналогичных соответствующим в разложении Шура).

Сингулярное разложение[править | править вики-текст]

  • Ограничения: произвольная матрица размера .
  • Разложение: , где — неотрицательная диагональная матрица, унитарные матрицы, а эрмитово-сопряжённая. В вещественном случае , причём , как и прежде, неотрицательная диагональная матрица, ортогональные.
  • Элементы на диагонали матрицы называются сингулярными значениями матрицы и обозначаются .
  • Сингулярное разложение, как и спектральное разложение, включает в себя отыскание базиса подпространств, действие на элементы которых оператора эквивалентны умножению на скаляр (т.е. ), но при этом сингулярное разложение является более общим методом, поскольку матрица не обязана быть квадратной.

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

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

  • Ограничения: квадратная комплексная матрица .
  • Разложение: , где эрмитова и унитарная.
  • Полярное разложение матрицы является аналогом разложения любого комплексного числа в виде .

Фробениусова нормальная форма[править | править вики-текст]

Источники[править | править вики-текст]

  1. William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery. 2.9 Cholesky Decomposition // Numerical Recipes in C. — 2nd edition. — Cambridge: Cambridge University Press. — ISBN 0-521-43108-5. 
  2. QR- и SVD- разложения: «плохие» СЛАУ.
  3. Meyer 2000, С. 514