7.4 QR-menetelmä

QR -menetelmä on paras yleiskäyttöinen menetelmä kaikkien ominaisarvojen ratkaisemiseksi. Siinä matriisi A saatetaan Schurin lauseessa esitettyyn yläkolmiomuotoon unitaarisilla similaarisuusmuunnosmatriiseilla. Merkillistä on, että menetelmä suppenee kohti yläkolmiomatriisia. Wilkinson (1965) sisältää hyvän esityksen QR-menetelmän suppenemisesta.

1. Muutetaan A unitaarisella similaarisuusmuunnoksella Hessenbergin matriisiksi T . Tämä askel ei aina ole välttämätön. Hessenbergin muoto on kuitenkin usein lähempänä yläkolmiomatriisia, kuin A.

2. Muodostetaan T :n QR -hajotelma

T  = Q R .

ja määritellään

Havaitaan, että T ja T ovat similaarisia, joten niillä on samat ominaisarvot. Jatketaan samaan tyyliin.

k. Muodostetaan T :n QR -hajotelma

T  = Q R

ja valitaan

Taas havaitaan että

joten T ja A ovat unitaarisesti similaarisia. Kun k -> , niin hyvin yleisillä ehdoilla T  -> Schurin lauseen yläkolmiomatriisia, josta ominaisarvotnäkee paljain silmin.

Harjoitus 7.4.1 QR -menetelmä pysähtyy mm., jos jokin T matriiseista on unitaarinen. Tämä voidaan välttää seuraavalla muunnoksella, jota voidaan myös käyttää konvergenssin kiihdyttämiseen. Valitaan

T  - b I = Q R

T  = R Q  + b I,

missä b on sopivasti valittu vakio. Osoita, että T ja T ovat similaarisia.

Huom. 7.4.2 Mikäli A:lla on itseisarvoltaan yhtäsuuria kompleksisia ominaisarvoja, voi QR -menetelmä supeta kohti lohkoyläkolmiomatriisia, jossa lohkot liittyvät itseisarvoltaan samansuuruisiin ominaisarvoihin. Edellisen harjoituksen tulos auttaa tässäkin, kun b valitaan kompleksiseksi. Laskut ikävä kyllä ovat tämän jälkeen kompleksisia, vaikka matriisi A alunperin olisikin reaalinen. (Reaalimatriisin kompleksiset ominaisarvot voidaan laskea reaaliaritmetiikalla ns. kaksi askel QR-menetelmän avulla (double step QR -algorithm)).