QR algoritme

QR-algoritmen er en numerisk metode i lineær algebra til at løse det komplette egenværdiproblem, det vil sige at finde alle egenværdier og egenvektorer i en matrix . Det blev udviklet i slutningen af 1950'erne uafhængigt af V. N. Kublanovskaya og J. Francis.

Algoritme

Lad A være en reel matrix, som vi ønsker at finde egenværdier og vektorer for. Vi sætter A 0 = A . Ved det k . trin (startende fra k = 0), udregn QR-dekomponeringen A k = Q k R k , hvor Q k er en ortogonal matrix (det vil sige Q k T = Q k −1 ), og R k er en øvre trekantet matrix . Så definerer vi A k +1 = R k Q k .

Læg mærke til det

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 vil sige, at alle matricer A k er ens , det vil sige, at deres egenværdier er ens.

Lad alle diagonale minorer i matrix A være ikke - degenererede . Derefter konvergerer sekvensen af matricer A k i form til den cellulære retvinklede trekantede form svarende til celler med egenværdier af samme modul. [en] $k\to \infty ,$

For at få egenvektorerne til matricen skal du gange alle matricerne Q k .

Algoritmen betragtes som beregningsstabil , da den er produceret af ortogonale lighedstransformationer.

Bevis for en symmetrisk positiv bestemt matrix

Vi antager, at egenværdierne af en positiv-definitiv matrix A er ordnet i faldende rækkefølge:

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

Lade

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

og S er en matrix sammensat af egenvektorer af matricen A . Derefter kan matrix A skrives som en spektral dekomponering

A=S\Lambda S^{T}.

Lad os finde et udtryk for potenserne af den oprindelige matrix i form af matricerne Q k og R k . På den ene side, per definition af QR-algoritmen:

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

Ved at anvende denne relation rekursivt får vi:

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

Ved at introducere følgende 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}.

På den anden side:

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

Ved at sidestille de rigtige dele af de sidste to formler får vi:

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

Antag, at der er en LU-nedbrydning af matricen S T :

S^{T}=LU,

derefter

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

Vi multiplicerer fra højre med matrixen invers til U og derefter med matrixen invers til Λ 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 vise

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

For uden tab af generalitet kan vi antage, at der er enheder på diagonalen af matricen L , derfor $k\to \infty$

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

Betegn

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

desuden er matrixen P k øvre trekantet, som produktet af øvre trekantede og diagonale matricer.

Det har vi altså bevist

S_{k}P_{k}\to S

Det følger af det unikke ved QR-nedbrydningen, at hvis produktet af en ortogonal og trekantet matrix konvergerer til en ortogonal matrix, så konvergerer den trekantede matrix til identitetsmatrixen . Af det sagte følger det

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

Det vil sige, at matricerne Sk konvergerer til matrixen af egenvektorer for matricen A.

Fordi

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\venstre(Q_{1}\cdot ...\cdot Q_{k}\right),

derefter

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

Går vi til 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 bevist, at QR-algoritmen giver os mulighed for at løse det komplette egenværdiproblem for en symmetrisk positiv-bestemt matrix.

Implementering af QR-algoritmen

Under visse betingelser konvergerer sekvensen af matricer til en trekantet matrix, Schur-nedbrydningen af en matrix . I dette tilfælde er egenværdierne af den trekantede matrix placeret på dens diagonal, og problemet med at finde egenværdierne anses for at være løst. I konvergenstests er det ikke praktisk at kræve nøjagtige nuller i nuldelen af en matrix, men man kan bruge Gershgorins cirkelsætning , som sætter fejlgrænser. $A_k$ $EN$

I matrixens begyndelsestilstand (uden yderligere transformationer) er omkostningerne ved iterationer relativt høje. Omkostningerne ved algoritmen kan reduceres ved først at konvertere matricen til form af en øvre Hessenberg-matrix (omkostningerne ved at opnå, som ved metoden baseret på Householder-transformationen estimeres som aritmetiske operationer), og derefter bruge en endelig sekvens af ortogonal lighedstransformationer. Denne algoritme minder lidt om den tosidede QR-nedbrydning. (I den sædvanlige QR-nedbrydning multipliceres Householder-reflektionsmatricen kun med originalen til venstre, mens i tilfælde af brug af Hessenberg-formen multipliceres refleksionsmatricen med originalen både til venstre og på højre.) At finde QR-nedbrydningen af den øvre Hessenberg-matrix vurderes som aritmetiske operationer. På grund af det faktum, at formen af Hessenberg-matricen er næsten øvre trekantet (den har kun et subdiagonalt element, der ikke er lig med nul), er det muligt straks at reducere antallet af iterationer, der kræves til konvergensen af QR-algoritmen . $EN$ ${10 \over 3}n^{3}+O(n^{2})$ $6n^{2}+O(n)$

Hvis den oprindelige matrix er symmetrisk, er den øvre Hessenberg-matrix også symmetrisk og derfor tridiagonal. Hele sekvensen af matricer har den samme egenskab . I dette tilfælde estimeres omkostningerne ved proceduren som aritmetiske operationer ved hjælp af en metode baseret på Householder-transformationen. At finde QR-nedbrydningen af en symmetrisk tridiagonal matrix evalueres som operationer. $A_k$ ${4 \over 3}n^{3}+O(n^{2})$ $På)$

Konvergenshastigheden afhænger af graden af separation af egenværdierne, og i praktisk implementering bruges "skift" eksplicit eller implicit for at øge separationen af egenværdierne og for at fremskynde konvergens. I sin typiske form for symmetriske matricer finder QR-algoritmen nøjagtigt én egenværdi (reducerer dimensionen af matrixen) i en eller to iterationer, hvilket gør denne tilgang både effektiv og pålidelig.

Implicit implementering af QR-algoritmen

I moderne computerpraksis implementeres QR-algoritmen ved hjælp af dens implicitte version, hvilket forenkler tilføjelsen af flere "skift". Til at begynde med er matrixen reduceret til formen af den øvre Hessenberg-matrix , ligesom i den eksplicitte version. Derefter, ved hvert trin, transformeres den første søjle gennem en lavdimensionel husholderlighedstransformation til den første søjle (eller ), hvor er et gradpolynomium , der bestemmer "skift"-strategien (normalt , hvor og er to egenværdier) af 2×2 resterende submatrix, er disse såkaldt implicit dobbeltforskydning). Derefter udføres successive Householder-transformationer af dimensionen for at returnere arbejdsmatricen til formen af den øvre Hessenberg-matrix. $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$

Noter

↑ Numeriske metoder / N. S. Bakhvalov, N. P. Zhidkov, G. M. Kobelkov. - 3. udg. - M. : BINOM, Videnlaboratoriet, 2004. - S. 321. - 636 s. — ISBN 5-94774-175-X .

Links

Peter Olvers noter om ortogonale baser og QR-algoritmen

Vektorer og matricer

Vektorer

Basale koncepter	Vektor i geometri Basis Ortogonalt grundlag Vektorkoordinater Kolinearitet Ortogonalitet Lineær afhængighed Søjleplads
Slags vektorer	Enhedsvektor Aksial vektor isotrop vektor Normal Kolinearitet Nul vektor Radius vektor Egenvektor
Operationer på vektorer	Skalært produkt vektor produkt blandet produkt Pseudoskalært produkt Dobbelt kryds produkt
Rumtyper	vektor rum affint rum Euklidisk rum Pseudo-euklidisk rum Normeret rum Minkowski plads

matricer

Basale koncepter	Matrix multiplikation Transponeret matrix Hermitisk konjugeret matrix Symmetrisk matrix omvendt matrix Egenværdi Karakteristisk polynomium af en matrix
Særlige matricer	Identitetsmatrix Nul matrix Diagonal matrix lambda matrix
Matrix nedbrydninger	LU nedbrydning Kolesky nedbrydning QR-nedbrydning LUP nedbrydning singular værdi nedbrydning Spektral nedbrydning af en matrix

Andet