2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 QR-алгоритм
Сообщение21.11.2013, 20:42 
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$ будут лежать собственные значения исходной матрицы?

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

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

 
 
 
 Posted automatically
Сообщение22.11.2013, 00:15 
Аватара пользователя
 i  Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»
Причина переноса: вернул.

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

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

 
 
 
 Re: QR-алгоритм
Сообщение22.11.2013, 13:00 
Наверно так:
$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$ стремится к верхнетреугольной матрице?

 
 
 
 Re: QR-алгоритм
Сообщение22.11.2013, 13:38 
Аватара пользователя
Самое интересное, конечно, понять, отчего приходим именно к верхней треугольной...

 
 
 
 Re: QR-алгоритм
Сообщение22.11.2013, 13:43 
Глупы вопрос) Спасибо за наводку с подобием матриц.

 
 
 
 Re: QR-алгоритм
Сообщение22.11.2013, 14:33 
Аватара пользователя
Кто недостаточно прилежно учился (вроде меня) и не знает свойств подобных матриц, можно так. Пусть $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)$$

 
 
 
 Re: QR-алгоритм
Сообщение22.11.2013, 14:52 
А почему собственный вектор матрицы $Q^{-1}AQ$ имеет вид $Q^{-1}x$?

 
 
 
 Re: QR-алгоритм
Сообщение22.11.2013, 17:14 
Аватара пользователя
Ответ 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$ к новому базису, при том, что сами оператор и вектор (а также собственное число) остаются неизменными.

 
 
 
 Re: QR-алгоритм
Сообщение22.11.2013, 19:33 
svv
Спасибо огромное. Спасли, помогли, уму-разуму научили.

 
 
 [ Сообщений: 11 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group