Algoritm de calcul al valorilor proprii - un algoritm care vă permite să determinați valorile proprii și vectorii proprii ai unei anumite matrice . Crearea de algoritmi eficienți și stabili pentru această problemă este una dintre problemele cheie în matematica computațională .
Având în vedere o matrice pătrată n × n A peste numere reale sau complexe , valoarea proprie λ și vectorul său rădăcină corespunzător v sunt o pereche care satisface egalitatea [1]
unde v este un vector coloană diferit de zero n × 1 , E este o matrice de identitate n × n , k este un întreg pozitiv și λ și v pot fi complexe chiar dacă A este real. Dacă k = 1 , vectorul se numește pur și simplu un vector propriu . În acest caz A v = λ v . Orice valoare proprie λ a unei matrice A are un vector propriu simplu [nota 1] corespunzător acestuia, astfel încât, dacă k este cel mai mic număr întreg astfel încât ( A - λ E ) k v = 0 pentru vectorul rădăcină v , atunci ( A - λ E ) ) k -1 v va fi un vector propriu simplu. Valoarea lui k poate fi luată întotdeauna mai mică sau egală cu n . În particular, ( A - λ E ) n v = 0 pentru toți vectorii rădăcină v corespunzători lui λ.
Pentru orice valoare proprie λ a matricei A , kernelul ker( A - λ E ) este format din toți vectorii proprii corespunzători lui λ (împreună cu 0) și se numește subspațiul propriu al lui λ și subspațiul vectorial ker(( A - λ E ) n ) constă din toți vectorii rădăcină (completați cu un vector nul) și se numește subspațiu rădăcină . Multiplicitatea geometrică a unei valori λ este dimensiunea propriului său subspațiu. Multiplicitatea algebrică a unei valori λ este dimensiunea subspațiului său rădăcină. Alți termeni sunt legați de egalitate
Aici det este determinantul lui , λ i sunt toate valorile proprii distincte ale matricei A , iar α i sunt multiplicitățile algebrice corespunzătoare. Funcția p A ( z ) este polinomul caracteristic al matricei A . Astfel, multiplicitatea algebrică este multiplicitatea valorilor proprii ca rădăcini ale polinomului caracteristic. Deoarece orice vector propriu este un vector rădăcină, multiplicitatea geometrică este mai mică sau egală cu multiplicitatea algebrică. Suma multiplicităţilor algebrice este egală cu gradul n al polinomului caracteristic. Ecuația p A ( z ) = 0 se numește ecuație caracteristică deoarece rădăcinile sale sunt exact valorile proprii ale matricei A. Prin teorema Hamilton-Cayley, matricea A însăși satisface aceeași ecuație: p A ( A ) = 0 [nota 2] . În consecință, coloanele matricei trebuie să fie fie 0, fie vectori rădăcină corespunzători valorii proprii λ j , deoarece sunt anihilate de matrice.
Orice set de vectori rădăcină de valori proprii distincte este liniar independent, astfel încât baza pentru întregul C n poate fi aleasă din setul de vectori rădăcină. Mai precis, această bază { v i }n
i =1pot fi alese şi aranjate astfel încât
Dacă acești vectori de bază sunt aranjați ca coloane ale matricei V = [ v 1 v 2 ... v n ] , atunci V poate fi folosit pentru a transforma matricea A în forma sa normală Jordan :
unde λ i sunt valori proprii, β i = 1 dacă ( A - λ i +1 ) v i +1 = v i și β i = 0 în caz contrar.
Dacă W este o matrice inversabilă și λ este o valoare proprie a matricei A cu un vector rădăcină corespunzător v , atunci ( W -1 AW - λ E ) k W - k v = 0 . Astfel, λ este o valoare proprie a matricei W -1 AW cu vectorul rădăcină corespunzător W - k v . Astfel, matrice similare au aceleași valori proprii.
Matricea conjugată hermitiană M * la o matrice complexă M este o matrice transpusă cu toate elementele înlocuite cu valori conjugate: M * = M T . O matrice pătrată A se numește normală dacă comută cu conjugatul hermitian: A * A = AA * . O matrice se numește hermitiană dacă este egală cu conjugatul ei: A * = A . Toate matricele hermitiene sunt normale. Dacă A are doar elemente reale, atunci conjugatul său este doar o matrice transpusă și va fi hermitian dacă și numai dacă este simetric . Aplicând acest lucru coloanelor, conjugarea poate fi utilizată pentru a defini produsul punctual canonic în C n : w • v = w * v [nota 3] . Matricele simetrice normale, hermitiene și reale au o serie de proprietăți utile:
Este posibil ca atât matricele reale, cât și cele complexe să aibă toate valorile proprii reale fără a fi o matrice hermitiană. De exemplu, o matrice triunghiulară reală are toate valorile proprii pe diagonală, dar în general nu este simetrică.
Orice problemă de matematică computațională poate fi considerată ca fiind calculul unei funcții ƒ dintr-un argument x . Numărul condiției κ (ƒ, x ) al problemei este raportul dintre eroarea relativă a rezultatului calculului și eroarea relativă a parametrului funcției și depinde atât de funcție, cât și de parametru. Numărul condiției descrie cât de mult crește eroarea în timpul calculului. Logaritmul zecimal al acestui număr indică numărul de caractere pe care le pierdem în raport cu datele originale. Numărul condiției se referă la cel mai bun scenariu, reflectând instabilitatea problemei în sine, indiferent de soluție. Niciun algoritm nu poate da un rezultat mai bun decât cel determinat de numărul condiției, cu excepția, poate, întâmplător. Cu toate acestea, un algoritm prost conceput poate da rezultate substanțial mai proaste. De exemplu, așa cum se va menționa mai jos, problema găsirii valorilor proprii ale unei matrice normale este întotdeauna bine condiționată, dar problema găsirii rădăcinilor unui polinom poate fi foarte prost condiționat . Astfel de algoritmi cu valori proprii care funcționează prin găsirea rădăcinilor polinomului caracteristic pot fi prost condiționat, chiar dacă problema în sine este bine condiționată.
Pentru problema rezolvării unui sistem de ecuații liniare A v = b , unde A este reversibil, condiția numărul κ ( A -1 , b ) este dat de || A || op || A -1 || op , unde || || op este o normă operator subordonată normei euclidiene uzuale pe C n . Deoarece acest număr este independent de b și este același atât pentru A cât și pentru A -1 , este denumit în mod obișnuit numărul de condiție κ ( A ) al matricei A . Această valoare κ ( A ) este, de asemenea, valoarea absolută a raportului dintre cea mai mare valoare proprie a matricei A și cea mai mică valoare proprie a acesteia. Dacă A este unitar , atunci || A || op = || A -1 || op = 1 , deci κ ( A ) = 1 . În general, pentru matrice este adesea dificil să se calculeze norma operatorului. Din acest motiv, alte norme matriceale sunt de obicei folosite pentru a estima numărul de condiție.
Pentru problema calculării valorilor proprii , Bauer și Faik au demonstrat că, dacă λ este o valoare proprie a unei matrice A diagonalizabile n × n cu matricea vectorului propriu V , atunci eroarea absolută în calculul lui λ este mărginită de produsul lui κ ( V ) iar eroarea absolută în A : [2 ] . Ca o consecință, numărul condiției pentru calcularea λ este κ (λ, A ) = κ ( V ) = || V || op || V -1 || op . Dacă matricea A este normală, atunci V este unitară și κ (λ, A ) = 1 . Astfel, problema calculării valorilor proprii ale matricelor normale este bine condiționată.
S-a demonstrat că numărul de condiție al problemei de calcul al subspațiului propriu al matricei normale A corespunzător valorii proprii λ este invers proporțional cu distanța minimă dintre λ și altele, diferite de λ , valorile proprii ale matricei A [3] . În special, problema determinării subspațiului propriu pentru matricele normale este bine condiționată pentru valorile proprii izolate. Dacă valorile proprii nu sunt izolate, cel mai bun lucru la care putem spera este să definim un subspațiu al tuturor vectorilor proprii ai valorilor proprii din apropiere.
Orice polinom normalizat este polinomul caracteristic al matricei însoțitoare , astfel încât un algoritm pentru calcularea valorilor proprii poate fi utilizat pentru a găsi rădăcinile polinoamelor. Teorema Abel-Ruffini arată că orice astfel de algoritm pentru dimensiuni mai mari de 4 trebuie fie să fie infinit, fie să implice funcții mai complexe decât operațiile aritmetice elementare sau puterile fracționale. Din acest motiv, algoritmi care calculează exact valorile proprii într-un număr finit de pași există doar pentru clase speciale de matrice. În cazul general, algoritmii sunt iterativi , dând la fiecare iterație următoarea aproximare a soluției.
Unii algoritmi dau toate valorile proprii, alții dau mai multe valori sau chiar una, dar acești algoritmi pot fi utilizați pentru a calcula toate valorile proprii. Odată determinată valoarea proprie λ a matricei A , aceasta poate fi folosită fie pentru a forța algoritmul să producă o altă valoare proprie, fie pentru a reduce problema la una care nu are λ ca soluție.
Reducerea se face de obicei printr-o deplasare: A este înlocuit cu A - μ E pentru o constantă μ . Valoarea proprie găsită pentru A - μ E trebuie adăugată la μ pentru a obține valoarea proprie a matricei A . De exemplu, în metoda puterii μ = λ . Iterația metodei puterii găsește cea mai mare valoare în valoare absolută, deci chiar dacă λ este o aproximare a unei valori proprii, este puțin probabil ca iterația metodei puterii să o găsească a doua oară. În schimb, metodele de iterație inversă găsesc cea mai mică valoare proprie, astfel încât μ este ales departe de λ în speranța de a fi mai aproape de o altă valoare proprie.
Reducerea se poate face prin îngustarea matricei A la spațiul coloanei matricei A - λ E . Deoarece A - λ E este degenerat, spațiul coloanei are o dimensiune mai mică. Algoritmul de calcul al valorilor proprii poate fi apoi aplicat acestei matrice restrânse. Procesul poate fi continuat până când sunt găsite toate valorile proprii.
Dacă algoritmul nu dă k valori proprii, este o practică obișnuită să se folosească un algoritm bazat pe iterație înapoi, setând μ la cea mai apropiată aproximare a valorii proprii. Acest lucru duce rapid la un vector propriu cu cea mai apropiată valoare proprie de μ . Pentru matricele mici, o alternativă este utilizarea subspațiului coloanei al produsului A - λ́ E pentru fiecare dintre celelalte valori proprii λ́.
Deoarece valorile proprii ale unei matrice triunghiulare sunt intrările diagonale, nu există în general o metodă finită precum eliminarea gaussiană pentru a triangula o matrice, păstrând în același timp valorile proprii, totuși, se poate obține ceva apropiat de o matrice triunghiulară. Matricea superioară Hessenberg este o matrice pătrată în care toate elementele de sub prima subdiagonală sunt egale cu zero. Matricea inferioară Hessenberg este o matrice pătrată în care toți termenii de deasupra primei superdiagonale sunt egali cu zero. Matricele care sunt atât matrice Hessenberg inferioară cât și superioară sunt matrici tridiagonale . Matricele Hessenberg și matricele tridiagonale sunt punctul de plecare pentru mulți algoritmi de calcul al valorilor proprii, deoarece valorile zero reduc complexitatea problemei. Există mai multe metode pentru reducerea matricelor la matrice Hessenberg cu aceleași valori proprii. Dacă matricea originală este simetrică sau hermitiană, atunci matricea rezultată va fi tridiagonală.
Dacă sunt necesare doar valori proprii, nu este nevoie să se calculeze matricea de similaritate, deoarece matricea transformată are aceleași valori proprii. Dacă sunt necesari și vectori proprii, este necesară o matrice de similitudine pentru a converti vectorii proprii ai matricei Hessenberg în vectorii proprii ai matricei originale.
Metodă | Aplicabil matricelor | Rezultat | Preț fără matrice de similaritate | Preț cu matrice de similitudine | Descriere |
---|---|---|---|---|---|
Gospodar se transformă | vedere generala | matricea Hessenberg | 2 n 3 ⁄ 3 +O(n2)[4] | 4 n 3 ⁄ 3 +O(n2)[4] | Reflectați fiecare coloană în raport cu subspațiul pentru a elimina elementele de jos ale coloanei. |
Givens se întoarce | vedere generala | matricea Hessenberg | 4 n 3 ⁄ 3 +O(n2)[4] | Se efectuează o rotație plată la zero elemente individuale. Rotațiile sunt ordonate astfel încât următoarele rotații să nu afecteze elementele nule. | |
Iterații ale lui Arnoldi | vedere generala | matricea Hessenberg | Se realizează ortogonalizarea Gram-Schmidt pe subspatiile Krylov . | ||
Algoritmul Lanczos [5] | Hermitian | matrice tridiagonală | Iterații Arnoldi pentru matrici hermitiene. |
Algoritmii iterativi rezolvă problema calculării valorilor proprii prin construirea de secvențe care converg către valorile proprii. Unii algoritmi dau și secvențe de vectori convergenți către vectori proprii. Cel mai adesea, secvențele de valori proprii sunt exprimate în termeni de secvențe de matrici similare care converg într-o formă triunghiulară sau diagonală, ceea ce facilitează obținerea valorilor proprii. Secvențele de vectori proprii sunt exprimate în termenii matricilor de similaritate corespunzătoare.
Metodă | Aplicabil matricelor | Rezultat | Preț pe pas | Convergenţă | Descriere |
---|---|---|---|---|---|
Metoda de putere | vedere generala | cea mai mare valoare proprie și vectorul corespunzător | O ( n2 ) _ | Liniar | Înmulțirea matricei multiple cu un vector inițial ales arbitrar, urmată de normalizare. |
Metoda puterii inverse | vedere generala | valoarea proprie cea mai apropiată de μ și vectorul corespunzător | Liniar | Iterație de putere cu matrice ( A - μ E ) -1 | |
Metoda iterației Rayleigh | vedere generala | valoarea proprie cea mai apropiată de μ și vectorul corespunzător | cub | Iterație de putere cu matrice ( A - μ i E ) -1 , unde μ i este raportul Rayleigh din iterația anterioară. | |
Iterație inversă precondițională [6] sau LOBPCG | pozitiv definit real simetric | valoarea proprie cea mai apropiată de μ și vectorul corespunzător | Iterație inversă cu precondiționare (inversarea aproximativă a matricei A ). | ||
Metoda bisectării [7] | triagonală simetrică reală | orice valoare proprie | Liniar | Folosește metoda bisecției pentru a găsi rădăcinile polinomului caracteristic și proprietățile șirului Sturm . | |
Iterații ale lui Laguerre | triagonală simetrică reală | orice valoare proprie | Cubic [8] | Utilizează metoda Laguerre pentru calcularea rădăcinilor polinomului caracteristic și a proprietăților șirului Sturm . | |
algoritm QR [9] | hessenberg | toate valorile proprii | O ( n2 ) _ | cub | Descompunerea A = QR , unde Q este ortogonal, R este triunghiular, apoi se folosește iterația la RQ . |
toate valorile proprii | 6 n 3 + O ( n 2 ) | ||||
metoda Jacobi | real simetric | toate valorile proprii | O ( n 3 ) | pătratică | Utilizează rotația lui Givens în încercarea de a scăpa de elementele în afara diagonalei. Încercarea eșuează, dar întărește diagonala. |
Divide and Conquer | Tridiagonala hermitiana | toate valorile proprii | O ( n2 ) _ | Matricea este împărțită în submatrici, care sunt diagonalizate și apoi recombinate. | |
toate valorile proprii | ( 4 ⁄ 3 ) n 3 + O ( n 2 ) | ||||
Metoda homotopiei | triagonală simetrică reală | toate valorile proprii | O ( n 2 ) [10] | Se construiește o homotopie calculabilă. | |
Metoda convoluției spectrale | real simetric | valoarea proprie cea mai apropiată de μ și vectorul propriu corespunzător | Iterație înapoi precondiționată aplicată la ( A - μ E ) 2 | ||
Algoritmul MRRR [11] | triagonală simetrică reală | unele sau toate valorile proprii și vectorii proprii corespunzători | O ( n2 ) _ | "Reprezentări multiple relativ robuste" - Iterația inversă este efectuată cu descompunerea LDL T a matricei părtinitoare. |
Nu există algoritmi simpli pentru calcularea directă a valorilor proprii pentru matrice în cazul general, dar pentru multe clase speciale de matrice, valorile proprii pot fi calculate direct. Aceasta:
Deoarece determinantul unei matrice triunghiulare este produsul elementelor sale diagonale, atunci pentru o matrice triunghiulară T . Astfel, valorile proprii ale lui T sunt elementele sale diagonale.
Dacă p este orice polinom și p ( A ) = 0, atunci valorile proprii ale matricei A satisfac aceeași ecuație. Dacă polinomul p poate fi factorizat, atunci valorile proprii ale lui A sunt printre rădăcinile sale.
De exemplu, un proiector este o matrice pătrată P care satisface ecuația P 2 = P . Rădăcinile ecuației polinomiale scalare corespunzătoare λ 2 = λ vor fi 0 și 1. Astfel, proiectorul are 0 și 1 ca valori proprii. Multiplicitatea valorii proprii 0 este defectul lui P , în timp ce multiplicitatea lui 1 este rangul lui P .
Un alt exemplu este o matrice A care satisface ecuația A 2 = α 2 E pentru un scalar α . Valorile proprii trebuie să fie egale cu ±α . Operatori de proiectare
satisface egalitățile
și
Spațiile coloane ale matricelor P + și P - sunt subspații ale vectorilor proprii ai matricei A , corespunzând lui +α și respectiv -α .
Pentru dimensiunile de la 2 la 4, există formule radicale care pot fi utilizate pentru a calcula valorile proprii. aceasta este o practică obișnuită, dar pentru matricele 4x4 complexitatea tot mai mare a formulelor rădăcinilor face această abordare mai puțin atractivă.
Pentru matrice 2×2
polinomul caracteristic este
Valorile proprii pot fi găsite ca rădăcini ale unei ecuații pătratice :
Dacă este definită ca distanța dintre două valori proprii, este ușor de calculat
cu formule similare pentru c și d . Rezultă că calculul este bine condiționat dacă valorile proprii sunt izolate.
Vectorii proprii pot fi obținuți folosind teorema Hamilton-Cayley . Dacă λ 1 , λ 2 sunt valori proprii, atunci ( A - λ 1 E )( A - λ 2 E ) = ( A - λ 2 E )( A - λ 1 E ) = 0 , deci coloanele ( A - λ 2 ) E ) sunt setate la zero de către matrice ( A - λ 1 E ) și invers. Presupunând că niciuna dintre matrice nu este egală cu zero, coloanele fiecărei matrice trebuie să conțină vectori proprii pentru o altă valoare proprie (dacă matricea este zero, atunci A este produsul matricei de identitate printr-o constantă și orice non- vectorul zero este un vector propriu).
De exemplu, lasa
atunci tr( A ) = 4 - 3 = 1 și det( A ) = 4(-3) - 3(-2) = -6 , deci ecuația caracteristică este
iar valorile proprii sunt 3 și -2. Acum
,În ambele matrice, coloanele diferă prin coeficienți scalari, astfel încât orice coloană poate fi aleasă. Deci, (1, -2) poate fi folosit ca vector propriu corespunzător valorii proprii -2 și (3, -1) ca vector propriu pentru valoarea proprie 3, care poate fi ușor verificat prin înmulțirea cu matricea A .
Dacă A este o matrice 3×3, atunci ecuația caracteristică va fi:
Această ecuație poate fi rezolvată folosind metodele lui Cardano sau Lagrange , dar transformarea afină a matricei A simplifică foarte mult expresia și duce direct la soluția trigonometrică . Dacă A = pB + qE , atunci A și B au aceiași vectori proprii și β este o valoare proprie a matricei B dacă și numai dacă α = pβ + q este o valoare proprie a matricei A . Dacă punem și , obținem
Substituția β = 2cos θ și o oarecare simplificare folosind identitatea cos 3 θ = 4cos 3 θ - 3cos θ reduce ecuația la cos 3 θ = det( B ) / 2 . În acest fel,
Dacă det( B ) este un număr complex sau mai mare decât 2 în valoare absolută, cosinusul invers pentru toate cele trei k valori ar trebui luat din aceeași ramură. Problema nu apare dacă A este real și simetric, ceea ce duce la un algoritm simplu: [12]
% Având în vedere o matrice A reală simetrică 3x3, se calculează valorile proprii p1 = A ( 1 , 2 ) ^ 2 + A ( 1 , 3 ) ^ 2 + A ( 2 , 3 ) ^ 2 dacă ( p1 == 0 ) % A este diagonală. eig1 = A ( 1 , 1 ) eig2 = A ( 2 , 2 ) eig3 = A ( 3 , 3 ) altfel q = urmă ( A ) / 3 p2 = ( A ( 1 , 1 ) - q ) ^ 2 + ( A ( 2 , 2 ) - q ) ^ 2 + ( A ( 3 , 3 ) - q ) ^ 2 + 2 * p1 p = sqrt ( p2 / 6 ) B = ( 1 / p ) * ( A - q * E ) % E este matricea identității r = det ( B ) / 2 % În aritmetică exactă pentru o matrice simetrică -1 <= r <= 1 %, dar eroarea de calcul o poate lăsa ușor în afara acestui interval. dacă ( r <= - 1 ) phi = pi / 3 elseif ( r >= 1 ) phi = 0 altfel phi = acos ( r ) / 3 Sfârşit % valorile proprii satisfac eig3 <= eig2 <= eig1 eig1 = q + 2 * p * cos ( phi ) eig3 = q + 2 * p * cos ( phi + ( 2 * pi / 3 )) eig2 = 3 * q - eig1 - eig3 % deoarece trace(A) = eig1 + eig2 + eig3 SfârşitDin nou, vectorii proprii ai lui A pot fi obținuți folosind teorema Hamilton-Cayley . Dacă α 1 , α 2 , α 3 sunt valori proprii diferite ale matricei A , atunci ( A - α 1 E )( A - α 2 E )( A - α 3 E ) = 0 . Apoi, coloanele produsului a oricăror două dintre aceste matrici conțin vectorii proprii ai celei de-a treia valori proprii. Totuși, dacă a 3 = a 1 , atunci ( A - α 1 E ) 2 ( A - α 2 E ) = 0 și ( A - α 2 E )( A - α 1 E ) 2 = 0 . Astfel, subspațiul propriu -zis rădăcină α 1 este acoperit de coloanele A - α 2 E , în timp ce subspațiul propriu-zis obișnuit este acoperit de coloanele ( A - α 1 E )( A - α 2 E ) . Subspațiul propriu obișnuit α 2 este acoperit de coloane ( A - α 1 E ) 2 .
De exemplu, lasa
Ecuația caracteristică este
cu valori proprii 1 (multiplicitatea 2) și -1. calculati
,și apoi
.Atunci (-4, -4, 4) este vectorul propriu pentru −1 și (4, 2, -2) este vectorul propriu pentru 1. Vectorii (2, 3, -1) și (6, 5, -3) sunt vectorii rădăcină corespunzători valorii 1, dintre care oricare poate fi combinat cu (-4, -4, 4) și (4, 2, -2) pentru a forma baza vectorilor rădăcină ai matricei A .