QR-algoritmi

Wikipedia
Loikkaa: valikkoon, hakuun

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.

QR-algoritmin kuvaus[muokkaa | muokkaa wikitekstiä]

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

 A_{k} \to Q_k R_k
 R_k Q_k \to A_{k+1}

Huomaa että

 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 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[muokkaa | muokkaa wikitekstiä]

Olkoon


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

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


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


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


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


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}

Lähteet[muokkaa | muokkaa wikitekstiä]

  1. J.G.F. Francis, "The QR Transformation, I", The Computer Journal, vol. 4, no. 3, pages 265-271 (1961) online at oxfordjournals.org;
    J.G.F. Francis, "The QR Transformation, II" The Computer Journal, vol. 4, no. 4, pages 332-345 (1962) online at oxfordjournals.org.
    Vera N. Kublanovskaya, "On some algorithms for the solution of the complete eigenvalue problem," USSR Computational Mathematics and Mathematical Physics, vol. 1, no. 3, pages 637–657 (1963, received Feb 1961). Also published in: Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki, vol.1, no. 4, pages 555–570 (1961).

Aiheesta muualla[muokkaa | muokkaa wikitekstiä]