Algoritm pentru calcularea valorilor proprii

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

Valori proprii și vectori proprii

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]

\left(A-\lambda E\right)^{k}{\mathbf {v} }=0,

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

p_{A}\left(z\right)={\rm {det))\left(zE-A\right)=\prod _{i=1}^{k}(z-\lambda _ {i})^{\alpha _{i)),

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. $\textstyle \prod _{i\neq j}(A-\lambda _{i}E)^{\alpha _{i)}$ $\textstyle (A-\lambda _{j}E)^{\alpha _{j)).$

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ă v i și v j au aceeași valoare proprie, atunci acest lucru va fi valabil și pentru orice v k cu k între i și j ;
dacă v i nu este un vector propriu simplu și dacă λ i este valoarea lui proprie, atunci ( A - λ i E ) v i = v i -1 (în special, v 1 trebuie să fie un vector propriu simplu).

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 :

V^{-1}AV={\begin{bmatrix}\lambda _{1}&\beta _{1}&0&\ldots &0\\0&\lambda _{2}&\beta _{2} &\ldots &0\\0&0&\lambda _{3}&\ldots &0\\\vdots &\vdots &\vdots &\ddots &\vdots \\0&0&0&\ldots &\lambda _{n}\end{bmatrix} },

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.

Matrici simetrice normale, hermitiene și reale

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:

Fiecare vector propriu rădăcină al unei matrice normale este un vector propriu simplu.
Orice matrice normală este similară cu una diagonală, deoarece forma sa normală Jordan este o matrice diagonală.
Vectorii proprii corespunzători diferitelor valori proprii ale unei matrice normale sunt ortogonali.
Pentru orice matrice normală A C n are o bază ortonormală constând din vectorii proprii ai matricei A . Matricea vectorului propriu corespunzătoare este unitară .
Valorile proprii ale unei matrice hermitiene sunt numere reale deoarece ( λ - λ) v = ( A * - A ) v = ( A - A ) v = 0 pentru un vector propriu diferit de zero v .
Dacă matricea A este reală, atunci există o bază ortonormală pentru R n constând din vectorii proprii ai matricei A dacă și numai dacă A este simetric.

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

Numărul condiției

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ă. $\;\;|\delta \lambda |\leqslant \kappa _{op}(V)\|\delta A\|_{op)$

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.

Algoritmi

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 λ́.

Matrici Hessenberg și matrici tridiagonale

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.

Algoritmi iterativi

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 .
algoritm QR [9]	hessenberg	toate valorile proprii	6 n 3 + O ( n 2 )	cub
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.
Divide and Conquer	Tridiagonala hermitiana	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.

Calcul direct

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:

Matrici triunghiulare

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. $\mathrm {det} \left(\lambda ET\right)={\prod }_{i}\left(\lambda -T_{ii}\right)$

Ecuații polinomiale descomponabile

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

P_{+}={\frac {1}{2}}\left(E+{\frac {A}{\alpha }}\right)

P_{-}={\frac {1}{2}}\left(E-{\frac {A}{\alpha }}\right)

satisface egalitățile

AP_{+}=\alpha P_{+}\quad AP_{-}=-\alpha P_{-}

și

P_{+}P_{+}=P_{+}\quad P_{-}P_{-}=P_{-}\quad P_{+}P_{-}=P_{-}P_{+} =0.

Spațiile coloane ale matricelor P + și P - sunt subspații ale vectorilor proprii ai matricei A , corespunzând lui +α și respectiv -α .

Matrici 2×2

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

A={\begin{bmatrix}a&b\\c&d\end{bmatrix}),

polinomul caracteristic este

{\rm {det)} {\begin {bmatrix}\lambda -a&-b\\-c&\lambda -d\end {bmatrix})=\lambda ^{2}\,-\,\left (a+d\right)\lambda \,+\,\left(ad-bc\right)=\lambda ^{2}\,-\,\lambda \,{\rm {tr))(A)\ ,+\,{\rm {det}}(A).

Valorile proprii pot fi găsite ca rădăcini ale unei ecuații pătratice :

\lambda ={\frac {{\rm {tr}}(A)\pm {\sqrt ({\rm {tr}}^{2}(A)-4{\rm {det}}( A)}}}{2}}.

Dacă este definită ca distanța dintre două valori proprii, este ușor de calculat $\textstyle {\rm {gap}}\left(A\right)={\sqrt ({\rm {tr}}^{2}(A)-4{\rm {det}}(A) }}$

{\frac {\partial \lambda }{\partial a))={\frac {1}{2)}\left(1\pm {\frac {ad}({\rm {gap)}( A)))\right),\qquad {\frac {\partial \lambda }{\partial b))={\frac {\pm c}({\rm {gap))(A)))

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

A={\begin{bmatrix}4&3\\-2&-3\end{bmatrix}),

atunci tr( A ) = 4 - 3 = 1 și det( A ) = 4(-3) - 3(-2) = -6 , deci ecuația caracteristică este

0=\lambda ^{2}-\lambda -6=(\lambda -3)(\lambda +2),

iar valorile proprii sunt 3 și -2. Acum

A-3E={\begin{bmatrix}1&3\\-2&-6\end{bmatrix}}

\qquad A+2E={\begin{bmatrix}6&3\\-2&-1\end{bmatrix}}

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

Matrici 3×3

Dacă A este o matrice 3×3, atunci ecuația caracteristică va fi:

{\rm {det)}\left(\alpha EA\right)=\alpha ^{3}-\alpha ^{2}{\rm {tr)}(A)-\alpha {\frac { 1}{2}}\left({\rm {tr}}(A^{2})-{\rm {tr}}^{2}(A)\right)-{\rm {det}}( A)=0.

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 $\textstyle q={\rm {tr)}(A)/3$ $\textstyle p=\left({\rm {tr))\left((A-qE)^{2}\right)/6\right)^{1/2)$

{\rm {det)}\left(\beta EB\right)=\beta ^{3}-3\beta -{\rm {det)}(B)=0.

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,

\beta =2{\rm {cos}}\left({\frac {1}{3}}{\rm {arccos}}\left({\rm {det}}(B)/2\ dreapta)+{\frac {2k\pi }{3}}\dreapta),\quad k=0,1,2.

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şit

Din 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

A={\begin{bmatrix}3&2&6\\2&2&5\\-2&-1&-4\end{bmatrix}}.

Ecuația caracteristică este

0=\lambda ^{3}-\lambda ^{2}-\lambda +1=(\lambda -1)^{2}(\lambda +1),

cu valori proprii 1 (multiplicitatea 2) și -1. calculati

AE={\begin{bmatrix}2&2&6\\2&1&5\\-2&-1&-5\end{bmatrix}),\qquad A+E={\begin{bmatrix}4&2&6\\2&3&5\\-2& -1&-3\end{bmatrix}}

și apoi

(AE)^{2}={\begin{bmatrix}-4&0&-8\\-4&0&-8\\4&0&8\end{bmatrix)),\qquad (AE)(A+E)={\ începe{bmatrix}0&4&4\\0&2&2\\0&-2&-2\end{bmatrix}}

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 .

Vezi și

Lista algoritmilor de calcul al valorilor proprii

Comentarii

↑ Termenul „simplu” este folosit aici doar pentru a sublinia diferența dintre „vector propriu” și „vector rădăcină”.
↑ unde termenul constant este înmulțit cu matricea de identitate E .
↑ Această ordine în produsul scalar (cu elementul conjugat în stânga) este preferată de fizicieni. Algebriștii preferă adesea notația w • v = v * w .

Note

↑ Sheldon Axler. Jos determinanții! // American Mathematical Monthly. - 1995. - Emisiune. 102 . - S. 139-154 .
↑ FL Bauer, CT Fike. Norme și teoreme de excludere // Numer. Matematică. - 1960. - Emisiune. 2 . - S. 137-141 .
↑ SC Eisenstat, ICF Ipsen. Rezultate de perturbare relativă pentru valorile proprii și vectorii proprii ai matricelor diagonalizabile // BIT. - 1998. - T. 38 , nr. 3 . - S. 502-9 . - doi : 10.1007/bf02510256 .
↑ 1 2 3 William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery. Reţete numerice în C. - a 2-a. - Cambridge University Press, 1992. - ISBN 0-521-43108-5 .
↑ Kh. D. Ikramov. Matrici rare. - 1982. - T. 20. - (Rezultatele ştiinţei şi tehnicii. Ser. Mat. anal).
↑ K. Neymeyr. O teorie geometrică pentru iterația inversă precondiționată IV: Despre cele mai rapide cazuri de convergență. // Aplicația algebră liniară. - 2006. - T. 415 , nr. 1 . - S. 114-139 . - doi : 10.1016/j.laa.2005.06.022 .
↑ Wilkinson, 1970 , p. 274, Metoda Bisecției
↑ T. Y Li, Zhonggang Zeng. Iterația lui Laguerre în rezolvarea problemei proprii tridiagonale simetrice - Revizuită // SIAM Journal on Scientific Computing . — 1992.
↑ Parlett, 1983 , p. 156, capitolul 8, algoritmi QR și QL
↑ Moody T. Chu. O notă despre metoda homotopiei pentru problemele cu valori proprii algebrice liniare // Aplicația algebră liniară. - 1988. - T. 105 . - S. 225-236 . - doi : 10.1016/0024-3795(88)90015-8 .
↑ Inderjit S. Dhillon, Beresford N. Parlett, Christof Vömel. Proiectarea și implementarea algoritmului MRRR // Tranzacții ACM pe software matematic . - 2006. - T. 32 , nr. 4 . - S. 533-560 . - doi : 10.1145/1186785.1186788 .
↑ Oliver K. Smith. Valori proprii ale unei matrice simetrice 3 × 3 // Comunicațiile ACM . - T. 4 , nr. 4 . - S. 168 . - doi : 10.1145/355578.366316 .

Literatură

J. Golub, C. Van Lone. Calculele matriceale. - Moscova: Mir, 1999. - ISBN 5-03-002406-9 .
B. Parlett. Problema cu valori proprii simetrice. - Moscova: Mir, 1983.
J. H. Wilkinson. Problema cu valori proprii algebrice. - Moscova: „Nauka” Ediția principală a literaturii fizice și matematice, 1970.

Lectură suplimentară

Adam W. Bojanczyk, Adam Lutoborski. Calculul unghiurilor Euler ale unei matrice simetrice 3X3 // SIAM Journal on Matrix Analysis and Applications. - ian 1991. - T. 12 , nr. 1 . - S. 41-48 . - doi : 10.1137/0612005 .