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).  

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.

QR-algoritmin kuvaus
Olkoon A matriisi, josta halutaan laskea ominaisarvot, ja olkoon A0:=A. Iteraation askeleella k (alussa k = 0), hajotetaan Ak ortogonaalisen matriisin Qk ja yläkolmiomatriisin Rk tuloksi ja muodostetaan Ak+1 = RkQk. 

 

Huomaa että

joten kaikki Ak: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 Ak supistuu kolmiomatriisiksi, jolloin matriisin ominaisarvot voidaan lukea suoraan diagonaalista.

Esimerkki 
Olkoon

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

Ensimmäinen iteraatiokierros

Toinen iteraatiokierros

Lopulta 10 iteraatiokierroksen jälkeen...

Lähteet

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

Lineaarialgebra