QR-алгоритм

[bukinland]

QR-алгоритм: алгоритм решения полной проблемы собственных значений, основанный на QR-разложении матриц. QR-разложение представление матрицы в виде произведения ортогональной матрицы и верхнетреугольной матрицы.
В ходе QR алгоритма делаем QR-разложение исходной матрицы: $A_0 = Q_1 \cdot R_1$. Далее перемножаем $R_1 \cdot Q_1$ и получаем $A_1$, которую опять раскладываем на $Q_2 \cdot R_2$. И т.д. Критерий останова – это соблюдение условия, что все поддиагональные элементы матрицы $A_k$ по модулю меньше некоторого заранее заданного числа $\varepsilon$, характеризующего точность вычислений.

Вопрос. Почему можно утверждать, что на диагонали конечной матрицы $A_k$ будут лежать собственные значения исходной матрицы?

[Deggial]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Причина переноса: формулы не оформлены $\TeX$ом

bukinland
Наберите все формулы и термы $\TeX$ом, картинку сносите.
Инструкции по оформлению формул здесь или здесь (или в этом видеоролике).
После исправлений сообщите в теме Сообщение в карантине исправлено, и тогда тема будет возвращена.

[Toucan]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»
Причина переноса: вернул.

[svv]

Пусть $Q$ и $R$ — квадратные матрицы порядка $n$, причем $Q$ невырождена. Попробуйте доказать, что тогда $QR$ и $RQ$ имеют одни и те же собственные числа (и для этого факта неважно, является ли $Q$ ортогональной, а $R$ верхнетреугольной).

Раз так, то после каждой итерации собственные числа не меняются. Когда мы в конце концов получим матрицу $A_k=R_k Q_k$, которая является с достаточной точностью верхнетреугольной, тут уж ясно, чему её собственные числа равны. В силу вышесказанного они были теми же и у исходной матрицы $A_0$.

[bukinland]

Наверно так:
$A_0 = Q_1 \cdot R_1$. Отсюда $R_1 = Q_1^{-1} \cdot A_0$.
$A_1 = R_1 \cdot Q_1 = Q_1^{-1} \cdot A_0 \cdot Q_1$. Следовательно $A_1$ подобна $A_0$. А по свойству подобных матриц собственные значения $A_1$ и $A_0$ совпадают.

Теперь еще один вопрос: почему в ходе итераций матрица $A_k$ стремится к верхнетреугольной матрице?

[Евгений Машеров]

Самое интересное, конечно, понять, отчего приходим именно к верхней треугольной...

[bukinland]

Глупы вопрос) Спасибо за наводку с подобием матриц.

[svv]

Кто недостаточно прилежно учился (вроде меня) и не знает свойств подобных матриц, можно так. Пусть $Ax=\lambda x$.
Тогда для матрицы $Q^{-1}AQ$ число $\lambda$ с вектором $Q^{-1}x$ будут собственными:

$$Q^{-1}AQ(Q^{-1}x)=Q^{-1}Ax=Q^{-1}\lambda x=\lambda(Q^{-1}x)$$

[bukinland]

А почему собственный вектор матрицы $Q^{-1}AQ$ имеет вид $Q^{-1}x$?

[svv]

Ответ 1. Взяли, проверили, подошло.

Ответ 2. Теория учит, что при преобразовании базиса с матрицей перехода $T$:
$\tilde{\mathbf e}_k=\mathbf e_i T^i_k$
матрица оператора $\mathsf A$ преобразуется так:
$\tilde A = T^{-1}A T\;,$
а набор компонент вектора $\mathbf x$ так:
$\tilde x=T^{-1} x\;.$

Тогда наши формулы допускают такую естественную трактовку: это в точности пересчет компонент оператора $\mathsf A$ и его собственного вектора $\mathbf x$ к новому базису, при том, что сами оператор и вектор (а также собственное число) остаются неизменными.

[bukinland]

svv
Спасибо огромное. Спасли, помогли, уму-разуму научили.