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

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

Разложе́ние ма́трицы — представление матрицы в виде произведения матриц, обладающих некоторыми определёнными свойствами (например, ортогональностью, симметричностью, диагональностью). У каждого класса матричных разложений имеется своя область применения; в частности, многие эффективные алгоритмы вычислительной линейной алгебры[en] основаны на построении соответствующих матричных разложений.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • Ограничения: квадратная комплексная матрица [10].
  • Вид разложения (комплексный случай): , где эрмитова матрица с неотрицательными ведущими минорами, а унитарная матрица[10][11].
  • Вид разложения (вещественный случай): , где симметричная матрица с неотрицательными ведущими минорами, а ортогональная матрица[12][13].
  • Для невырожденной матрицы полярное разложение единственно, а для вырожденной матрицы однозначно определён лишь множитель [10].
  • Полярное разложение матрицы в комплексном случае является аналогом представления произвольного комплексного числа в виде [14].

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

Примечания[править | править вики-текст]

  1. Икрамов, 1991, с. 20.
  2. Воеводин и Кузнецов, 1984, с. 75—76.
  3. 1 2 Воеводин и Кузнецов, 1984, с. 176.
  4. 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.
  5. QR- и SVD- разложения: «плохие» СЛАУ.
  6. Meyer, 2000, p. 514.
  7. 1 2 Икрамов, 1991, с. 21.
  8. Воеводин и Кузнецов, 1984, с. 80.
  9. Форсайт Дж., Малькольм М., Моулер К.  Машинные методы математических вычислений. — М.: Мир, 1980. — 280 с. — С. 214, 225.
  10. 1 2 3 Воеводин и Кузнецов, 1984, с. 78.
  11. Гантмахер, 1988, с. 234—236.
  12. Воеводин и Кузнецов, 1984, с. 79.
  13. Гантмахер, 1988, с. 244.
  14. Гантмахер, 1988, с. 236.

Литература[править | править вики-текст]