Численные методы линейной алгебры

4.6.1. QL – алгоритм

Пусть detA0, тогда согласно теореме 1.3 матрицу А можно разложить

A=QL, (4.34)
где Q – ортогональная матрица, L – нижняя треугольная матрица. Тогда матрица В, равная
B=LQ=Q^TAQ=Q^-1AQ, (4.35)
подобна матрице А.
Дальше, согласно формуле (4.35) формируется последовательность подобных матриц
A₁=A; A₁=Q₁L₁ , A₂=L₁Q₁= A₁Q₁ ,
A₂=Q₂L₂ , A₃=L₂Q₂= A₂Q₂ , (4.36)
……………………………….
A_k=Q_kL_k , A_k+1=L_kQ_k= A_kQ_k .
Формула (4.36) описывает QL – алгоритм без сдвигов. При к последовательность матриц А_k+1 сходятся к треугольной. Их диагональные элементы стремятся к её собственным значениям, которые в свою очередь являются собственными значениями матрицы А.
Наддиагональный элемент (A_k)_ij матрицы A_k на к-ой итерации QL – алгоритма равен s_ij(_i/_j)^k , где s_ij – постоянная и ₁<₂<…<_n.
Отметим, что сходимость QL – алгоритма улучшится, если использовать сдвиги.


4.6.2. QR – алгоритм

Пусть detA0, тогда согласно теореме 1.2 матрицу А можно представить в виде

A=QR, (4.37)
где Q – ортогональная матрица, R – верхняя треугольная матрица. Тогда матрица В, равная
B=RQ=Q^TAQ=Q^-1AQ, (4.38)
подобна матрице А.
Согласно, формуле (4.38) составляется последовательность подобных матриц
A₁=A; A₁=Q₁R₁ , A₂=R₁Q₁= A₁Q₁ ,
A₂=Q₂R₂ , A₃=R₂Q₂= A₂Q₂ , (4.39)
……………………………….
A_k=Q_kR_k , A_k+1=R_kQ_k= A_kQ_k .
В общем случае, когда собственные значения матрицы А различны, последовательность матриц A_k имеет пределом верхнюю треугольную матрицу А_ , диагональные элементы которой представляют собой собственные значения исходной матрицы. Формула (4.39) описывает QR – алгоритм без сдигов.
Модификация вида A₁=A,…, A_k-_kE=Q_kR_k , A_k+1=R_kQ_k+_kE = A_kQ_k , где _k – величина сдвига называется QR – алгоритмом со сдвигом сходимость, которого существенно выше по сравнению с QR – алгоритмом.