4.3 QR-hajotelman muodostaminen Householderin matriiseilla

Olkoon

korkea mxn matriisi, jonka aste, rank(A) = n ja  n .

1. askel. Koska rank(A) = n, on a   0, joten valitaan Householderin mxm matriisi P joka toteuttaa yhtälön

Siis

2. askel. Kirjoitetaan (m-1)x(n-1) matriisi A sarakevektoriesityksenä s.e.

Edelleen aste-ehdosta seuraa, että a   0. (Jos a  =0, niin rank(A)=rank(P A) <n, oletuksen vastaisesti.) Etsitään Householderin kertalukua (m-1)x(m-1) oleva matriisi B siten, että

Valitaan mxm matriisi

jolla kerrotaan P A vasemmalta ja saadaan

On helppo havaita, että P on unitaarinen.

3. askel. Valitaan Householderin matriisi B siten,että

B a r e ,

missä a on A :n ensimmäinen sarake. Samoin kuin edellä, a 0. Valitaan

Nyt matriisin P P P A kolme ensimmäistä saraketta ovat yläkolmiomuodossa.

n. askel. A , A 0, on m-n+1 vektori. Jos n lopetetaan tähän. Jos n, etsitään vielä Householderin matriisi B s.e.

ja valitaan

Merkitsemällä Q* = P .....P P saadaan haluttu lopputulos

missä R on mxn yläkolmiomatriisi( R on nxn yläkolmiomatriisi) , ja Q on unitaaristen matriisien tulona mxm unitaarinen matriisi.

Esimerkki 4.3.1 Matriisin

QR-hajotelma on

Harjoitus 4.3.2. Jos A on neliömatriisi ja rank(A) = n, niin Q voidaan valita niin, että R:n diagonaalialkiot ovat positiiviset. Tällöin QR-hajotelma on yksikäsitteinen.

(Vihje: Jos ortogonaalisen vektorijoukon vektorit {q } kerrotaan kompleksiluvuilla , joiden itseisarvo | |=1, niin saatu vektorijoukko { q } on ortogonaalinen )

Muuta tätä tulosta käyttäen QR-hajotelmassa R:n diagonaalialkiot positiivisiksi ja sovella tulosta edelliseen QR-hajotelmaan.

Oikea vastaus on

Esimerkki 4.3.2 QR-hajotelman muodostaminen käsin on työlästä. Sen sijaan sen ohjelmointi on helppoa. Olkoon

1. Askel

2. Askel

Tarkista, että

A = QR.

Jos R:n diagonaalialkiot valitaan positiivisiksi, niin silloin

Interaktiivinen harjoitus 4.3.1. QR-hajotelma.

Laskenta-aikoja. QR-hajotelman muodostamiseen mxn matriisille kuluu n (m-n/3) flopsia.