QR-algoritmi

Olkoon A matriisi, josta halutaan laskea ominaisarvot, ja olkoon A₀:=A. Iteraation askeleella k (alussa k = 0), hajotetaan A_k ortogonaalisen matriisin Q_k ja yläkolmiomatriisin R_k tuloksi ja muodostetaan A_k+1 = R_kQ_k.

${\displaystyle A_{k}\to Q_{k}R_{k}}$

${\displaystyle R_{k}Q_{k}\to A_{k+1}}$

Huomaa että

${\displaystyle A_{k+1}=R_{k}Q_{k}=Q_{k}^{T}Q_{k}R_{k}Q_{k}=Q_{k}^{T}A_{k}Q_{k}=Q_{k}^{-1}A_{k}Q_{k},}$

joten kaikki A_k:t ovat similaarisia matriiseja ja siten niillä on samat ominaisarvot. Algoritmi on numeraalisesti stabiili, koska se perustuu ortogonaalisiin similaarisuusmuunnoksiin.

Riittävän monen iteraatiokierroksen jälkeen matriisi A_k supistuu kolmiomatriisiksi, jolloin matriisin ominaisarvot voidaan lukea suoraan diagonaalista.

Olkoon

${\displaystyle A={\begin{bmatrix}5&2\\4&9\end{bmatrix}}}$

joka hajotetaan Givensin rotaation avulla ortogonaaliseksi matriisiksi Q ja yläkolmiomatriisiksi R.

${\displaystyle A\to Q*R={\begin{bmatrix}0,781&-0,625\\0,625&0,781\end{bmatrix}}{\begin{bmatrix}6,403&7,184\\0,000&5,778\end{bmatrix}}}$

Ensimmäinen iteraatiokierros

${\displaystyle A_{1}=R*Q={\begin{bmatrix}6,403&7,184\\0,000&5,778\end{bmatrix}}{\begin{bmatrix}0,781&-0,625\\0,625&0,781\end{bmatrix}}={\begin{bmatrix}0,949&1,610\\3,610&4,512\end{bmatrix}}}$

Toinen iteraatiokierros

${\displaystyle A_{2}=R*Q={\begin{bmatrix}10,151&3,109\\0,000&3,645\end{bmatrix}}{\begin{bmatrix}0,935&-0,356\\0,356&0,935\end{bmatrix}}={\begin{bmatrix}10,593&-0,704\\1,296&3,407\end{bmatrix}}}$

Lopulta 10 iteraatiokierroksen jälkeen...

${\displaystyle A_{10}=R*Q={\begin{bmatrix}10,464&-1,999\\0,000&3,536\end{bmatrix}}{\begin{bmatrix}1,000&0,000\\0,000&1,000\end{bmatrix}}={\begin{bmatrix}10,464&-2,000\\0,000&3,536\end{bmatrix}}}$

• Prof. Peter Olver's notes on orthogonal bases and the workings of the QR algorithm
• Module for the QR Method