QR-algoritmi

QR-algoritmi on lineaarialgebran numeerinen menetelmä täydellisen ominaisarvoongelman ratkaisemiseksi, eli matriisin kaikkien ominaisarvojen ja ominaisvektorien löytämiseksi . Sen kehittivät 1950-luvun lopulla itsenäisesti V. N. Kublanovskaya ja J. Francis .

Algoritmi

Olkoon A todellinen matriisi, jolle haluamme löytää ominaisarvoja ja vektoreita. Laitamme A 0 = A . Laske k :nnessa vaiheessa (alkaen k = 0: sta) QR-hajotelma A k = Q k R k , missä Q k on ortogonaalinen matriisi (eli Q k T = Q k −1 ) ja R k on ylempi kolmion matriisi . Sitten määritellään A k +1 = R k Q k .

huomaa, että

A_{k+1}=R_{k}Q_{k}=Q_{k}^{-1}Q_{k}R_{k}Q_{k}=Q_{k}^{-1} A_{k}Q_{k}=Q_{k}^{T}A_{k}Q_{k},

eli kaikki matriisit A k ovat samanlaisia , eli niiden ominaisarvot ovat yhtä suuret.

Olkoot matriisin A kaikki diagonaaliset minorit ei - degeneroituneita . Sitten matriisien sarja A k konvergoi muodoltaan solun oikeanpuoleiseen kolmiomuotoon , joka vastaa soluja, joilla on saman moduulin ominaisarvot. [yksi] $k\to \infty ,$

Saadaksesi matriisin ominaisvektorit, sinun on kerrottava kaikki matriisit Q k .

Algoritmia pidetään laskennallisesti stabiilina , koska se tuotetaan ortogonaalisilla samankaltaisuusmuunnoksilla.

Todistus symmetriselle positiiviselle määrätylle matriisille

Oletetaan, että positiivisen määrätyn matriisin A ominaisarvot on järjestetty laskevassa järjestyksessä:

\lambda _{1}>\lambda _{2}>...>\lambda _{n}>0.

Päästää

\Lambda =\mathrm {diag} \left(\lambda _{1},...,\lambda _{n}\right),

ja S on matriisi, joka koostuu matriisin A ominaisvektoreista . Sitten matriisi A voidaan kirjoittaa spektrihajotelmana

A=S\Lambda S^{T}.

Etsitään lauseke alkuperäisen matriisin potenssien suhteen matriisien Q k ja R k suhteen . Toisaalta QR-algoritmin määritelmän mukaan:

A^{k}=A_{1}^{k}=\left(Q_{1}R_{1}\right)^{k}=Q_{1}\left(R_{1}Q_{ 1}\oikea)^{k-1}R_{1}=Q_{1}A_{2}^{k-1}R_{1}.

Kun tätä suhdetta käytetään rekursiivisesti, saamme:

{\displaystyle A^{k}=Q_{1}\cdot ...\cdot Q_{k}\cdot R_{k}\cdot ...\cdot R_{1))

Ottamalla käyttöön seuraavan merkinnän:

S_{k}=Q_{1}\cdot ...\cdot Q_{k},

T_{k}=R_{k}\cdot ...\cdot R_{1},

saamme

A^{k}=S_{k}T_{k}.

Toisaalta:

A^{k}=S\Lambda ^{k}S^{T}.

Yhdistämällä kahden viimeisen kaavan oikeat osat saamme:

S\Lambda ^{k}S^{T}=S_{k}T_{k}.

Oletetaan, että matriisilla S T on LU-hajotelma :

S^{T}=LU,

sitten

S\Lambda ^{k}LU=S_{k}T_{k}.

Kerrotaan oikealta matriisin käänteisarvolla U ja sitten matriisin käänteisluvulla Λ k :

S\Lambda ^{k}L=S_{k}T_{k}U^{-1},

S\Lambda ^{k}L\Lambda ^{-k}=S_{k}T_{k}U^{-1}\Lambda ^{-k}.

Sen voi osoittaa

\Lambda ^{k}L\Lambda ^{-k}\to \mathrm {diag} \left(l_{11},...,l_{nn}\right)=L^{\prime } .

Sillä ilman yleisyyden menetystä voidaan olettaa, että matriisin L diagonaalissa on yksiköitä , joten $k\to \infty$

S_{k}T_{k}U^{-1}\Lambda ^{-k}\to S.

Merkitse

P_{k}=T_{k}U^{-1}\Lambda ^{-k},

lisäksi matriisi P k on ylempi kolmiomainen, ylempien kolmio- ja diagonaalimatriisien tulona.

Olemme siis todistaneet sen

S_{k}P_{k}\to S

QR-hajoamisen ainutlaatuisuudesta seuraa, että jos ortogonaalisen ja kolmiomatriisin tulo konvergoi ortogonaalimatriisiin, kolmiomatriisi konvergoi identiteettimatriisiin . Siitä, mitä on sanottu, se seuraa

S_{k}=Q_{1}\cdot ...\cdot Q_{k}\to S.

Toisin sanoen matriisit S k konvergoivat matriisin A ominaisvektorien matriisiin .

Koska

A_{k+1}=Q_{k}^{T}A_{k}Q_{k}=...=\left(Q_{k}^{T}\cdot ...\cdot Q_ {1}^{T}\oikea)A_{1}\left(Q_{1}\cdot ...\cdot Q_{k}\right)=\left(Q_{1}\cdot ...\cdot Q_{k}\oikea)^{T}A\vasen(Q_{1}\cdot ...\cdot Q_{k}\oikea),

sitten

A_{k+1}=S_{k}^{T}AS_{k}.

Ylittäessämme rajan, saamme:

\lim _{k\to \infty }A_{k}=\lim _{k\to \infty }A_{k+1}=S^{T}AS=S^{T}S\Lambda S^{T}S=\Lambda .

Olemme siis osoittaneet, että QR-algoritmin avulla voimme ratkaista täydellisen ominaisarvoongelman symmetriselle positiivis-määräiselle matriisille.

QR-algoritmin toteutus

Tietyissä olosuhteissa matriisien sekvenssi konvergoi kolmiomatriisiin, matriisin Schur-hajotelmaan . Tässä tapauksessa kolmiomatriisin ominaisarvot sijaitsevat sen diagonaalissa, ja ominaisarvojen löytämisen ongelma katsotaan ratkaistuksi. Konvergenssitesteissä ei ole käytännöllistä vaatia tarkkoja nollia matriisin nollaosaan, vaan voidaan käyttää Gershgorinin ympyrälausetta , joka asettaa virherajat. $A_k$ $A$

Matriisin alkutilassa (ilman lisämuunnoksia) iteraatioiden kustannukset ovat suhteellisen korkeat. Algoritmin kustannuksia voidaan pienentää muuntamalla matriisi ensin ylemmän Hessenberg-matriisin muotoon (jonka saamisen kustannukset Householder-muunnokseen perustuvalla menetelmällä arvioidaan aritmeettisina operaatioina) ja sitten käyttämällä äärellistä ortogonaalista sarjaa. samankaltaisuusmuunnoksia. Tämä algoritmi on jossain määrin samanlainen kuin kaksipuolinen QR-hajotus. (Tavallisessa QR-jakelussa Householderin heijastusmatriisi kerrotaan alkuperäisellä vain vasemmalla, kun taas Hessenberg-muotoa käytettäessä heijastusmatriisi kerrotaan alkuperäisellä sekä vasemmalla että oikealla.) Ylemmän Hessenberg-matriisin QR-hajotelman löytäminen arvioidaan aritmeettisina operaatioina. Koska Hessenberg-matriisin muoto on melkein ylemmän kolmion muotoinen (sillä on vain yksi diagonaalinen elementti, joka ei ole yhtä suuri kuin nolla), on mahdollista välittömästi vähentää QR-algoritmin konvergenssiin tarvittavien iteraatioiden määrää. . $A$ ${10 \over 3}n^{3}+O(n^{2})$ $6n^{2}+O(n)$

Jos alkuperäinen matriisi on symmetrinen, ylempi Hessenberg-matriisi on myös symmetrinen ja siksi kolmikulmainen. Koko matriisijonolla on sama ominaisuus . Tässä tapauksessa toimenpiteen hinta arvioidaan aritmeettisina operaatioina Householder-muunnoksen menetelmällä. Symmetrisen kolmikulmaisen matriisin QR-hajotelman löytäminen arvioidaan operaatioina. $A_k$ ${4 \over 3}n^{3}+O(n^{2})$ $Päällä)$

Konvergenssin nopeus riippuu ominaisarvojen erotteluasteesta, ja käytännön toteutuksessa "siirtymiä" käytetään eksplisiittisesti tai implisiittisesti tehostamaan ominaisarvojen erottelua ja nopeuttamaan konvergenssia. Tyypillisessä muodossaan symmetrisille matriiseille QR-algoritmi löytää tarkasti yhden ominaisarvon (pienentämällä matriisin ulottuvuutta) yhdessä tai kahdessa iteraatiossa, mikä tekee tästä lähestymistavasta sekä tehokkaan että luotettavan.

QR-algoritmin implisiittinen toteutus

Nykyaikaisessa laskentakäytännössä QR-algoritmi toteutetaan käyttämällä sen implisiittistä versiota, mikä yksinkertaistaa useiden "siirtojen" lisäämistä. Aluksi matriisi pelkistetään ylemmän Hessenberg-matriisin muotoon , aivan kuten eksplisiittisessä versiossa. Sitten jokaisessa vaiheessa ensimmäinen sarake muunnetaan pieniulotteisella Householder-samankaltaisuusmuunnolla ensimmäiseksi sarakkeeksi (tai ), jossa on astepolynomi, joka määrittää "siirtymien" strategian (yleensä , missä ja ovat kaksi ominaisarvoa 2 × 2 jäännösalimatriisista nämä ovat niin kutsuttuja implisiittisiä kaksoissiirtoja). Sitten suoritetaan peräkkäiset Householder-muunnokset dimensiosta työmatriisin palauttamiseksi ylemmän Hessenberg-matriisin muotoon. $A_{0}=QAQ^{T}$ $A_k$ $p(A_{k})$ ${\displaystyle p(A_{k})e_{1))$ $p(A_{k})$ $r$ $p(x)=(x-\lambda )(x-{\bar {\lambda )))$ $\lambda$ ${\bar {\lambda ))$ $A_k$ $r+1$ $A_k$

Muistiinpanot

↑ Numeeriset menetelmät / N. S. Bakhvalov, N. P. Zhidkov, G. M. Kobelkov. - 3. painos - M. : BINOM, Knowledge Laboratory, 2004. - S. 321. - 636 s. — ISBN 5-94774-175-X .

Linkit

Peter Olverin muistiinpanot ortogonaalisista perusteista ja QR-algoritmista

Vektorit ja matriisit

Vektorit

Peruskonseptit	Vektori geometriassa Perusta Ortogonaalinen perusta Vektorikoordinaatit Kollineaarisuus Ortogonaalisuus Lineaarinen riippuvuus Saraketila
Vektorityypit	Yksikkövektori Aksiaalinen vektori isotrooppinen vektori Normaali Kollineaarisuus Nolla vektori Sädevektori Omavektori
Operaatiot vektoreille	Skalaarituote vektorituote sekoitettu tuote Pseudoskalaarinen tuote Kaksinkertainen ristituote
Tilatyypit	vektoriavaruus affinista tilaa Euklidinen avaruus Pseudoeuklidinen avaruus Normaali tila Minkowskin tila

matriiseja

Peruskonseptit	Matriisin kertolasku Transponoitu matriisi Hermitian konjugaattimatriisi Symmetrinen matriisi käänteinen matriisi Ominaisarvo Matriisin karakteristinen polynomi
Erikoismatriisit	Identiteettimatriisi Nolla matriisi Diagonaalinen matriisi lambda matriisi
Matriisihajotukset	LU:n hajoaminen Cholesky-hajoaminen QR-hajoaminen LUP-hajoaminen singulaariarvon hajottelu Matriisin spektrihajotus

Muut