QR-algoritmi

QR-algoritmi on lineaarialgebrassa ominaisarvojen laskennassa käytetty algoritmi, eli menetelmä, jolla lasketaan matriisien ominaisarvoja. QR-algoritmin kehittivät samanaikaisesti 1961 John G.F. Francis (Englanti) ja Vera N. Kublanovskaya (Neuvostoliitto).^[1]

QR-algoritmi perustuu QR-hajotelman muodostamien ortogonaalisen matriisin ja yläkolmiomatriisin kertomiseen päinvastaisessa järjestyksessä ja algoritmin soveltamiseen rekursiivisesti uuteen muodostuneeseen matriisiin, kunnes riittävän monen iteraatiokierrosten jälkeen ortogonaalinen matriisi lähestyy kohti ykkösmatriisia ja yläkolmiomatriisi matriisia, jonka diagonaalista voidaan lukea matriisin ominaisarvot.

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