Algoritm QR

Algoritmul QR este o metodă numerică în algebră liniară pentru rezolvarea completă a problemei cu valori proprii, adică găsirea tuturor valorilor proprii și vectorilor proprii ai unei matrice . A fost dezvoltat la sfârșitul anilor 1950 independent de V. N. Kublanovskaya și J. Francis.

Algoritm

Fie A o matrice reală pentru care dorim să găsim valori proprii și vectori. Punem A 0 = A . La pasul k (începând de la k = 0), se calculează descompunerea QR A k = Q k R k , unde Q k este o matrice ortogonală (adică Q k T = Q k −1 ) și R k este o matrice superioară matrice triunghiulara . Atunci definim A k +1 = R k Q k .

observa asta

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

adică toate matricele A k sunt similare , adică valorile lor proprii sunt egale.

Fie toate diagonalele minore ale matricei A să fie nedegenerate . Apoi secvența matricelor A k at converge în formă către forma celulară triunghiulară drept corespunzătoare celulelor cu valori proprii de același modul. [unu] $k\to \infty ,$

Pentru a obține vectorii proprii ai matricei, trebuie să înmulțiți toate matricele Q k .

Algoritmul este considerat stabil din punct de vedere computațional , deoarece este produs prin transformări de similaritate ortogonală.

Demonstrație pentru o matrice definită pozitivă simetrică

Presupunem că valorile proprii ale unei matrice pozitiv-definite A sunt ordonate în ordine descrescătoare:

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

Lăsa

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

iar S este o matrice compusă din vectori proprii ai matricei A . Apoi, matricea A poate fi scrisă ca o descompunere spectrală

A=S\Lambda S^{T}.

Să găsim o expresie pentru puterile matricei originale în termenii matricilor Q k și R k . Pe de o parte, prin definiția algoritmului QR:

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

Aplicând recursiv această relație, obținem:

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

Prin introducerea următoarei notații:

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

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

primim

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

Pe de altă parte:

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

Echivalând părțile corecte ale ultimelor două formule, obținem:

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

Să presupunem că există o descompunere LU a matricei S T :

S^{T}=LU,

apoi

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

Înmulțim de la dreapta cu matricea inversă lui U și apoi cu matricea inversă lui Λ 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}.

Se poate arăta că

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

Pentru că fără pierdere a generalității, putem presupune că există unități pe diagonala matricei L , așadar $k\to \infty$

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

Denota

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

în plus, matricea P k este triunghiulară superioară, ca produsul dintre matricele triunghiulare superioare și diagonale.

Astfel, noi am dovedit că

S_{k}P_{k}\la S

Din unicitatea descompunerii QR rezultă că dacă produsul dintre o matrice ortogonală și triunghiulară converge către o matrice ortogonală, atunci matricea triunghiulară converge către matricea de identitate . Din cele spuse rezultă că

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

Adică, matricele S k converg către matricea de vectori proprii ai matricei A .

pentru că

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

apoi

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

Trecând la limită, obținem:

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

Deci, am demonstrat că algoritmul QR ne permite să rezolvăm problema completă a valorilor proprii pentru o matrice simetrică pozitiv-definită.

Implementarea algoritmului QR

În anumite condiții, succesiunea de matrice converge către o matrice triunghiulară, descompunerea Schur a unei matrice . În acest caz, valorile proprii ale matricei triunghiulare sunt situate pe diagonala acesteia, iar problema găsirii valorilor proprii este considerată rezolvată. În testele de convergență, nu este practic să se solicite zerouri exacte în partea zero a unei matrice, dar se poate folosi teorema cercului Gershgorin , care stabilește limite de eroare. $A_k$ $A$

În starea inițială a matricei (fără transformări suplimentare), costul iterațiilor este relativ mare. Costul algoritmului poate fi redus prin conversia mai întâi a matricei în forma unei matrice Hessenberg superioară (costul de obținere care prin metoda bazată pe transformarea Householder este estimat ca operații aritmetice), apoi folosind o secvență finită de ortogonale. transformări de similaritate. Acest algoritm este oarecum similar cu descompunerea QR pe două fețe. (În descompunerea QR obișnuită, matricea de reflecție Householder este înmulțită cu originalul doar în stânga, în timp ce în cazul utilizării formei Hessenberg, matricea de reflexie este înmulțită cu originalul atât în stânga, cât și în dreapta.) Găsirea descompunerii QR a matricei superioare Hessenberg este evaluată ca operații aritmetice. Datorită faptului că forma matricei Hessenberg este aproape triunghiulară superioară (are un singur element subdiagonal care nu este egal cu zero), este posibil să se reducă imediat numărul de iterații necesare pentru convergența algoritmului QR . $A$ ${10 \over 3}n^{3}+O(n^{2})$ $6n^{2}+O(n)$

Dacă matricea originală este simetrică, matricea superioară Hessenberg este, de asemenea, simetrică și, prin urmare, tridiagonală. Întreaga secvență de matrice are aceeași proprietate . În acest caz, costul procedurii este estimat ca operații aritmetice folosind o metodă bazată pe transformarea Householder. Găsirea descompunerii QR a unei matrice tridiagonale simetrice este evaluată ca operații. $A_k$ ${4 \over 3}n^{3}+O(n^{2})$ $Pe)$

Rata de convergență depinde de gradul de separare a valorilor proprii, iar în implementarea practică, „schimbările” sunt folosite explicit sau implicit pentru a îmbunătăți separarea valorilor proprii și pentru a accelera convergența. În forma sa tipică pentru matricele simetrice, algoritmul QR găsește cu acuratețe o valoare proprie (reducerea dimensiunii matricei) în una sau două iterații, făcând această abordare atât eficientă, cât și robustă.

Implementarea implicită a algoritmului QR

În practica modernă de calcul, algoritmul QR este implementat folosind versiunea sa implicită, care simplifică adăugarea de „schift” multiple. Inițial, matricea este redusă la forma matricei superioare Hessenberg , la fel ca în versiunea explicită. Apoi, la fiecare pas, prima coloană este transformată printr-o transformare de similitudine a gospodăriei de dimensiuni joase cu prima coloană (sau ), unde este un polinom de grad care determină strategia „deplasărilor” (de obicei , unde și sunt două valori proprii ). a submatricei reziduale 2×2, acestea sunt așa-numitele deplasări duble implicite). Apoi sunt efectuate transformări succesive ale dimensiunii Householder pentru a readuce matricea de lucru la forma matricei Hessenberg superioare. $A_{0}=QAQ^{T}$ $A_k$ $p(A_{k})$ $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$

Note

↑ Metode numerice / N. S. Bakhvalov, N. P. Zhidkov, G. M. Kobelkov. - Ed. a 3-a. - M. : BINOM, Laboratorul de cunoștințe, 2004. - S. 321. - 636 p. — ISBN 5-94774-175-X .

Link -uri

Notele lui Peter Olver despre bazele ortogonale și algoritmul QR

Vectori și matrice

Vectori

Noțiuni de bază	Vector în geometrie Bază Baza ortogonala Coordonatele vectoriale Coliniaritate Ortogonalitatea Dependență liniară Spațiul coloanei
Tipuri de vectori	Vector unitar Vector axial vector izotrop Normal Coliniaritate Vector zero Vector rază Vector propriu
Operații pe vectori	Produs scalar produs vectorial produs mixt Produs pseudoscalar Produs dublu cruce
Tipuri de spațiu	spațiu vectorial spatiu afin Spațiul euclidian Spațiul pseudo-euclidian Spațiu normat Spațiul Minkowski

matrici

Noțiuni de bază	Înmulțirea matricei Matrice transpusă Matricea conjugată hermitiană Matricea simetrică matrice inversă Valoare proprie Polinom caracteristic al unei matrice
Matrici speciale	Matrice de identitate Matrice zero Matricea diagonală matricea lambda
Descompuneri de matrice	descompunerea LU Descompunerea Cholesky Descompunerea QR Descompunerea LUP descompunerea unei valori singulare Descompunerea spectrală a unei matrice

Alte