4.6. Методы для матриц, не принадлежащих к специальному классу

Здесь будут рассмотрены методы решения полной проблемы собственных значений для несимметричных матриц, при этом не делается каких-либо оговорок относительно кратности или не кратности собственных значений. К таким методам относятся QL и QR алгоритмы [9, 11, 12]. Отметим, что эти алгоритмы являются типичными представителями методов трансформационного типа. Общая идея этих методов состоит в том, чтобы посредством последовательности простых преобразований подобий привести матрицу к той или иной канонической форме, позволяющей без труда определить собственные значения и вектора.

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 – алгоритмом.

4.7. Обобщенная задача на собственные значения

Обобщенная задача на собственные значения [13] очень важна для приложений. Эта задача задается уравнением

Ах=Вх. (4.40)

Если матрица В положительно определена, то для задачи (4.40) справедливы:

1. Все её собственные значения вещественны;

2. Собственные значения имеют тот же знак, что и собственные значения задачи Ах=х.