QR-алгоритм для несимметрических матриц

Эта задача существенно более трудная, чем для симметрических матриц и QR-алгоритм, по-видимому, один из наиболее общих методов ее решения. Основная идея этого метода состоит в разложении исходной матрицы А₀=А в произведение ортогональной матрицы и верхней треугольной. Последовательность преобразований дает нам очередные модификации матрицы А: A_k=Q_kR_k, A_k+1=R_kQ_k, k=0, 1, 2, …, где каждая из матриц Q_k является ортогональной (если матрица А вещественна) или унитарной (если А невещественна). R_k – верхние треугольные матрицы.

Примечание: унитарной называется матрица U, удовлетворяющая соотношению U^*U=E, где U^* – матрица, сопряженная к U, т.е. получающаяся из U заменой элементов на комплексно-сопряженные с последующим транспонированием, Е – единичная матрица.

Для преобразований будем использовать известный алгоритм Хаусхолдера, состоящий в следующем:

пусть некоторый вектор w₁ выбран так, что

Тогда A₂=(E-2w₁ )A₀= , где * обозначает в общем случае ненулевой элемент. Выберем теперь вектор w₂ так, что

Лежащие ниже главной диагонали элементы двух первых столбцов матрицы (E-2w₂ )A₂ обратятся в нуль. Продолжая этот процесс с помощью векторов w_i c нулями в первых i–1 позициях, получим

(E-2w_n-1 )…(E-2w₂ )(E-2w₁ )A=R=QA

где R – верхняя треугольная матрица, а Q – ортогональная в силу того, что составляющие ее сомножители в круглых скобках есть ортогональные матрицы. Так как в этом случае Q^-1=Q^T, то можем записать A=QR, представляющее собой QR-разложение матрицы А. Теорема о QR-алгоритме звучит так:

Если все собственные значения матрицы различны по абсолютной величине и A=PDP^-1, где D – диагональная матрица из собственных значений матрицы А, то генерируемые QR-алгоритмом матрицы A_k сходятся к верхней треугольной матрице с собственными значениями в главной диагонали, а элементы ниже диагонали сходятся к нулю с линейной скоростью, пропорциональной отношению собственных значений.

Для повышения эффективности приведенного алгоритма перед его применением матрицу рекомендуют привести к так называемой форме Хессенберга с нулями ниже первой за главной поддиагональю; это приведение осуществляют с применением преобразований Хаусхолдера. После этого разложение матрицы выполняется значительно проще или уже рассмотренными преобразованиями Хаусхолдера, либо (что еще лучше) воспользоваться преобразованиями Гивенса (плоскими вращениями). Но мы эти усовершенствования алгоритма рассматривать не будем. Скажем только, что QR-алгоритм практически не налагает на исходную матрицу существенных ограничений и является численно устойчивым.