QR-algoritm

QR-algoritmen är en numerisk metod i linjär algebra för att lösa hela egenvärdesproblemet, det vill säga att hitta alla egenvärden och egenvektorer i en matris . Det utvecklades i slutet av 1950-talet oberoende av V. N. Kublanovskaya och J. Francis.

Algoritm

Låt A vara en reell matris för vilken vi vill hitta egenvärden och vektorer. Vi sätter A 0 = A . Vid det k : te steget (med början från k = 0), beräkna QR-sönderdelningen Ak = Qk Rk , där Qk är en ortogonal matris ( det vill säga QkT = Qk − 1 ) och Rk är en övre triangulär matris . Sedan definierar vi A k +1 = R k Q k .

Lägg märke till att

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},

det vill säga alla matriser A k är lika , det vill säga deras egenvärden är lika.

Låt alla diagonala minorer i matrisen A vara icke- degenererade . Sedan konvergerar sekvensen av matriser A k i form till den cellulära rätvinkliga triangulära formen som motsvarar celler med egenvärden med samma modul. [ett] $k\to \infty ,$

För att få matrisens egenvektorer måste du multiplicera alla matriserna Q k .

Algoritmen anses beräkningsstabil , eftersom den produceras av ortogonala likhetstransformationer.

Bevis för en symmetrisk positiv bestämd matris

Vi antar att egenvärdena för en positiv-definitiv matris A är ordnade i fallande ordning:

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

Låta

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

och S är en matris sammansatt av egenvektorer för matrisen A . Sedan kan matrisen A skrivas som en spektral nedbrytning

A=S\Lambda S^{T}.

Låt oss hitta ett uttryck för potenserna av den ursprungliga matrisen i termer av matriserna Q k och R k . Å ena sidan, per definition av QR-algoritmen:

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

Genom att tillämpa denna relation rekursivt får vi:

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

Genom att införa följande notation:

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

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

vi får

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

Å andra sidan:

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

Genom att likställa de rätta delarna av de två sista formlerna får vi:

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

Antag att det finns en LU-sönderdelning av matrisen S T :

S^{T}=LU,

sedan

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

Vi multiplicerar från höger med matrisen invers till U och sedan med matrisen invers till Λ 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}.

Det kan man visa

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

För utan förlust av generalitet kan vi anta att det finns enheter på diagonalen av matrisen L , därför $k\to \infty$

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

Beteckna

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

dessutom är matrisen Pk övre triangulär, som produkten av övre triangulära och diagonala matriser.

Det har vi alltså bevisat

S_{k}P_{k}\to S

Det följer av det unika med QR-nedbrytningen att om produkten av en ortogonal och triangulär matris konvergerar till en ortogonal matris, då konvergerar den triangulära matrisen till identitetsmatrisen . Av det sagda följer att

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

Det vill säga, matriserna Sk konvergerar till matrisen av egenvektorer för matrisen A .

Därför att

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

sedan

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

När vi går till gränsen får vi:

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

Så vi har bevisat att QR-algoritmen tillåter oss att lösa hela egenvärdesproblemet för en symmetrisk positiv-definitiv matris.

Implementering av QR-algoritmen

Under vissa förhållanden konvergerar sekvensen av matriser till en triangulär matris, Schur-nedbrytningen av en matris . I det här fallet är egenvärdena för den triangulära matrisen placerade på dess diagonal, och problemet med att hitta egenvärden anses löst. I konvergenstest är det inte praktiskt att kräva exakta nollor i nolldelen av en matris, men man kan använda Gershgorins cirkelsats , som sätter felgränser. $A_k$ $A$

I matrisens initiala tillstånd (utan ytterligare transformationer) är kostnaden för iterationer relativt hög. Kostnaden för algoritmen kan reduceras genom att först konvertera matrisen till formen av en övre Hessenberg-matris (kostnaden för att erhålla vilken med metoden baserad på hushållartransformen uppskattas som aritmetiska operationer), och sedan använda en ändlig sekvens av ortogonal likhetstransformationer. Denna algoritm påminner något om den tvåsidiga QR-nedbrytningen. (I den vanliga QR-sönderdelningen multipliceras Householder-reflektionsmatrisen med originalet endast till vänster, medan vid användning av Hessenberg-formen multipliceras reflektionsmatrisen med originalet både till vänster och på höger.) Att hitta QR-nedbrytningen av den övre Hessenberg-matrisen utvärderas som aritmetiska operationer. På grund av det faktum att formen på Hessenberg-matrisen är nästan övre triangulär (den har bara ett subdiagonalt element som inte är lika med noll), är det möjligt att omedelbart minska antalet iterationer som krävs för konvergensen av QR-algoritmen . $A$ ${10 \over 3}n^{3}+O(n^{2})$ $6n^{2}+O(n)$

Om den ursprungliga matrisen är symmetrisk, är den övre Hessenberg-matrisen också symmetrisk och därför tridiagonal. Hela sekvensen av matriser har samma egenskap . I detta fall uppskattas kostnaden för proceduren som aritmetiska operationer med hjälp av en metod baserad på hushållartransformeringen. Att hitta QR-sönderdelningen av en symmetrisk tridiagonal matris utvärderas som operationer. $A_k$ ${4 \over 3}n^{3}+O(n^{2})$ $På)$

Konvergenshastigheten beror på graden av separation av egenvärdena, och i praktisk implementering används "förskjutningar" explicit eller implicit för att förbättra separationen av egenvärdena och för att påskynda konvergensen. I sin typiska form för symmetriska matriser hittar QR-algoritmen exakt ett egenvärde (minskar matrisens dimension) i en eller två iterationer, vilket gör detta tillvägagångssätt både effektivt och tillförlitligt.

Implicit implementering av QR-algoritmen

I modern datorpraxis implementeras QR-algoritmen med sin implicita version, vilket förenklar tillägget av flera "skift". Inledningsvis reduceras matrisen till formen av den övre Hessenberg-matrisen , precis som i den explicita versionen. Sedan, vid varje steg, transformeras den första kolumnen genom en lågdimensionell hushållarlikhetsomvandling till den första kolumnen (eller ), där är ett gradpolynom som bestämmer strategin för "förskjutningar" (vanligtvis , där och är två egenvärden av 2×2 restsubmatrisen är dessa så kallade implicita dubbelskift). Sedan utförs successiva hushållartransformationer av dimensionen för att återställa arbetsmatrisen till formen av den övre Hessenberg-matrisen. $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$

Anteckningar

↑ Numeriska metoder / N. S. Bakhvalov, N. P. Zhidkov, G. M. Kobelkov. - 3:e uppl. - M. : BINOM, Kunskapslaboratoriet, 2004. - S. 321. - 636 sid. — ISBN 5-94774-175-X .

Länkar

Peter Olvers anteckningar om ortogonala baser och QR-algoritmen

Vektorer och matriser

Vektorer

Grundläggande koncept	Vektor i geometri Grund Ortogonal grund Vektorkoordinater Kolinearitet Ortogonalitet Linjärt beroende Kolumnutrymme
Typer av vektorer	Enhet vektor Axiell vektor isotrop vektor Vanligt Kolinearitet Noll vektor Radie vektor Egenvektor
Operationer på vektorer	Skalär produkt vektor produkt blandad produkt Pseudoskalär produkt Dubbelkorsprodukt
Utrymmestyper	vektor utrymme affint utrymme Euklidiskt utrymme Pseudo-euklidiskt utrymme Normerat utrymme Minkowski utrymme

matriser

Grundläggande koncept	Matrismultiplikation Transponerad matris Hermitisk konjugatmatris Symmetrisk matris invers matris Eget värde Karakteristiskt polynom för en matris
Specialmatriser	Identitetsmatris Noll matris Diagonal matris lambda matris
Matrisnedbrytningar	LU-nedbrytning Cholesky nedbrytning QR-sönderdelning LUP-nedbrytning singulärvärdesfaktorisering Spektral nedbrytning av en matris

Övrig