Algoritm för beräkning av egenvärden

Egenvärdesberäkningsalgoritm - en algoritm som låter dig bestämma egenvärdena och egenvektorerna för en given matris . Skapandet av effektiva och stabila algoritmer för detta problem är ett av nyckelproblemen inom beräkningsmatematik .

Egenvärden och egenvektorer

Givet en n × n kvadratmatris A över reella eller komplexa tal, är egenvärdet λ och dess motsvarande rotvektor v ett par som uppfyller likheten [1]

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

där v är en n × 1 kolumnvektor som inte är noll, E är en n × n identitetsmatris , k är ett positivt heltal och λ och v kan vara komplexa även om A är reell. Om k = 1 kallas vektorn helt enkelt en egenvektor . I detta fall A v = λ v . Varje egenvärde λ för en matris A har en enkel [not 1] egenvektor som motsvarar den så att om k är det minsta heltal så att ( A - λ E ) k v = 0 för rotvektorn v , då ( A - λ E ) k -1 v kommer att vara en enkel egenvektor. Värdet på k kan alltid tas mindre än eller lika med n . Speciellt ( A - λ E ) n v = 0 för alla rotvektorer v som motsvarar λ.

För varje egenvärde λ av matris A , består kärnan ker( A - λ E ) av alla egenvektorer som motsvarar λ (tillsammans med 0) och kallas för egendelrummet för λ , och vektordelrummet ker(( A - λ E ) n ) består av alla rotvektorer (utfyllda med en nollvektor) och kallas för rotunderrymden . Den geometriska multipliciteten av ett värde λ är dimensionen av dess eget delrum. Den algebraiska multipliciteten av ett värde λ är dimensionen av dess rotdelrum. Ytterligare termer är relaterade till jämlikhet

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

Här är det determinanten av , λ i är alla distinkta egenvärden för matrisen A , och α i är motsvarande algebraiska multipliciteter. Funktionen p A ( z ) är det karakteristiska polynomet för matrisen A. Således är algebraisk multiplicitet multipliciteten av egenvärden som rötter till det karakteristiska polynomet. Eftersom vilken egenvektor som helst är en rotvektor är den geometriska multipliciteten mindre än eller lika med den algebraiska multipliciteten. Summan av algebraiska multipliciteter är lika med n -graden av det karakteristiska polynomet. Ekvationen p A ( z ) = 0 kallas den karakteristiska ekvationen eftersom dess rötter är exakt matrisens A egenvärden . Enligt Hamilton-Cayleys sats uppfyller matrisen A själv samma ekvation: p A ( A ) = 0 [not 2] . Som en konsekvens måste matrisens kolumner vara antingen 0 eller rotvektorer som motsvarar egenvärdet λ j , eftersom de förintas av matrisen $\textstyle \prod _{i\neq j}(A-\lambda _{i}E)^{\alpha _{i))$ $\textstyle (A-\lambda _{j}E)^{\alpha _{j)).$

Varje uppsättning rotvektorer med distinkta egenvärden är linjärt oberoende, så grunden för hela Cn kan väljas från uppsättningen rotvektorer . Mer exakt, denna grund { v i }ni
= 1kan väljas och ordnas så att

om v i och v j har samma egenvärde, så kommer detta också att vara sant för alla v k med k mellan i och j ;
om v i inte är en enkel egenvektor och om λ i är dess egenvärde, då ( A - λ i E ) v i = v i -1 (i synnerhet måste v 1 vara en enkel egenvektor).

Om dessa basvektorer är ordnade som kolumner i matrisen V = [ v 1 v 2 ... v n ] , så kan V användas för att transformera matrisen A till dess normala Jordan-form :

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

där λi är egenvärden, βi = 1 om ( A - λi + 1 ) v i +1 = vi och βi = 0 annars .

Om W är en inverterbar matris och λ är ett egenvärde för matris A med en motsvarande rotvektor v , då ( W - 1 AW- λ E ) k W - k v = 0 . Sålunda är λ ett egenvärde för matrisen W - 1AW med motsvarande rotvektor W - kv . Sålunda har liknande matriser samma egenvärden.

Normala, Hermitiska och reella symmetriska matriser

Den hermitiska konjugerade matrisen M * till en komplex matris M är en transponerad matris med alla element ersatta av konjugerade värden: M * = M T . En kvadratisk matris A kallas normal om den pendlar med det hermitiska konjugatet: A * A = AA * . En matris kallas hermitisk om den är lika med dess konjugat: A * = A . Alla hermitiska matriser är normala. Om A bara har reella element, är dess konjugat bara en transponerad matris, och den kommer att vara hermitisk om och bara om den är symmetrisk . Genom att tillämpa detta på kolumner kan konjugation användas för att definiera den kanoniska punktprodukten i C n : w • v = w * v [not 3] . Normala, hermitiska och reella symmetriska matriser har ett antal användbara egenskaper:

Varje rotegenvektor i en normal matris är en enkel egenvektor.
Vilken normal matris som helst liknar en diagonal eftersom dess normala Jordan-form är en diagonal matris.
Egenvektorer som motsvarar olika egenvärden för en normal matris är ortogonala.
För vilken normal matris som helst har A C n en ortonormal bas som består av matrisens A egenvektorer . Motsvarande egenvektormatris är enhetlig .
Egenvärdena för en hermitisk matris är reella tal eftersom ( λ - λ) v = ( A * - A ) v = ( A - A ) v = 0 för en egenvektor som inte är noll v .
Om matrisen A är reell, så finns det en ortonormal grund för Rn bestående av egenvektorerna för matrisen A om och endast om A är symmetrisk.

Det är möjligt för både reella och komplexa matriser att ha alla egenvärden reella utan att vara en hermitisk matris. Till exempel har en riktig triangulär matris alla sina egenvärden på diagonalen, men är i allmänhet inte symmetrisk.

Villkorsnummer

Alla problem med beräkningsmatematik kan betraktas som beräkningen av någon funktion ƒ från något argument x . Villkorstalet κ (ƒ, x ) för problemet är förhållandet mellan det relativa felet för beräkningsresultatet och det relativa felet för funktionsparametern och beror på både funktionen och parametern. Villkorsnumret beskriver hur mycket felet ökar under beräkningen. Decimallogaritmen för detta tal indikerar antalet tecken som vi förlorar i förhållande till originaldata. Villkorsnumret hänvisar till det bästa scenariot, vilket återspeglar instabiliteten i själva problemet, oavsett lösningen. Ingen algoritm kan ge ett bättre resultat än det som bestäms av villkorsnumret, utom kanske av en slump. En dåligt utformad algoritm kan dock ge betydligt sämre resultat. Till exempel, som kommer att nämnas nedan, är problemet med att hitta egenvärdena för en normal matris alltid väl betingat, men problemet med att hitta rötterna till ett polynom kan vara mycket dåligt betingat . Sådana egenvärdealgoritmer som fungerar genom att hitta rötterna till det karakteristiska polynomet kan vara dåligt betingade, även om själva problemet är välkonditionerat.

För problemet med att lösa ett system av linjära ekvationer A v = b , där A är reversibel, ges villkorstalet κ ( A -1 , b ) av || A || op || A -1 || op , där || || op är en operatornorm som är underordnad den vanliga euklidiska normen på C n . Eftersom detta tal är oberoende av b och är detsamma för både A och A -1 , kallas det vanligen för villkorsnumret κ ( A ) för matrisen A. Detta värde κ ( A ) är också det absoluta värdet av förhållandet mellan det största egenvärdet för matrisen A och dess minsta egenvärde. Om A är enhetlig , då || A || op = || A -1 || op = 1 , så κ ( A ) = 1 . I allmänhet är det för matriser ofta svårt att beräkna operatornormen. Av denna anledning används vanligtvis andra matrisnormer för att uppskatta tillståndsnumret.

För problemet med att beräkna egenvärden bevisade Bauer och Faik att om λ är ett egenvärde av en n × n diagonaliserbar matris A med egenvektormatris V , så är det absoluta felet vid beräkning av λ begränsat av produkten av κ ( V ) och det absoluta felet i A : [2] . Som en konsekvens är villkorstalet för beräkning av λ κ ( λ, A ) = κ ( V ) = || V || op || V -1 || op . Om matrisen A är normal är V enhetlig och κ (λ, A ) = 1 . Således är problemet med att beräkna egenvärdena för normala matriser välkonditionerat. ${\displaystyle \;\;|\delta \lambda |\leqslant \kappa _{op}(V)\|\delta A\|_{op))$

Det visades att villkorsnumret för problemet med att beräkna egenunderrummet för den normala matrisen A som motsvarar egenvärdet λ är omvänt proportionell mot det minsta avståndet mellan λ och andra, skilda från λ , egenvärden för matrisen A [3] . I synnerhet är problemet med att bestämma egenunderrummet för normala matriser väl betingat för isolerade egenvärden. Om egenvärdena inte är isolerade är det bästa vi kan hoppas på att definiera ett delrum av alla egenvektorer för närliggande egenvärden.

Algoritmer

Varje normaliserat polynom är det karakteristiska polynomet för den medföljande matrisen , så en algoritm för att beräkna egenvärden kan användas för att hitta rötterna till polynom. Abel-Ruffini-satsen visar att varje sådan algoritm för dimensioner större än 4 antingen måste vara oändlig eller involvera funktioner som är mer komplexa än elementära aritmetiska operationer eller bråkpotenser. Av denna anledning existerar algoritmer som exakt beräknar egenvärdena i ett ändligt antal steg endast för speciella klasser av matriser. I det allmänna fallet är algoritmerna iterativa och ger vid varje iteration nästa approximation till lösningen.

Vissa algoritmer ger alla egenvärden, andra ger flera värden eller till och med bara ett, men dessa algoritmer kan användas för att beräkna alla egenvärden. När egenvärdet λ för matrisen A har bestämts kan det användas antingen för att tvinga algoritmen att producera ett annat egenvärde eller för att reducera problemet till ett som inte har λ som lösning.

Reduktionen görs vanligtvis genom en förskjutning: A ersätts med A - μ E för någon konstant μ . Egenvärdet som hittas för A - μ E måste adderas till μ för att erhålla egenvärdet för matris A . Till exempel i effektmetoden μ = λ . Iterationen av potensmetoden hittar det största värdet i absolut värde, så även om λ är en approximation till ett egenvärde, är det osannolikt att iteration av potensmetoden hittar det en andra gång. Omvänt hittar tillbaka iterationsmetoder det minsta egenvärdet, så μ väljs bort från λ i hopp om att vara närmare något annat egenvärde.

Reduktionen kan göras genom att minska matrisen A till kolumnutrymmet för matrisen A - λ E . Eftersom A - λ E är degenererad har kolumnutrymmet en lägre dimension. Egenvärdesberäkningsalgoritmen kan sedan appliceras på denna avsmalnande matris. Processen kan fortsätta tills alla egenvärden har hittats.

Om algoritmen inte ger k egenvärden, är det vanligt att använda en algoritm baserad på bakåt iteration, som sätter μ till närmaste approximation av egenvärdet. Detta leder snabbt till en egenvektor med det egenvärdet som ligger närmast μ . För små matriser är ett alternativ att använda kolumnunderrummet för produkten A - λ́ E för vart och ett av de andra egenvärdena λ́.

Hessenbergmatriser och tridiagonala matriser

Eftersom egenvärdena för en triangulär matris är de diagonala posterna, finns det i allmänhet ingen ändlig metod som Gaussisk eliminering för att triangulera en matris samtidigt som egenvärdena bevaras, men något nära en triangulär matris kan erhållas. Den övre Hessenberg-matrisen är en kvadratisk matris där alla element under den första subdiagonalen är lika med noll. Den nedre Hessenberg-matrisen är en kvadratisk matris där alla termer ovanför den första superdiagonalen är lika med noll. Matriser som är både undre och övre Hessenbergmatriser är tridiagonala matriser . Hessenbergmatriser och tridiagonala matriser är utgångspunkten för många algoritmer för att beräkna egenvärden, eftersom nollvärden minskar problemets komplexitet. Det finns flera metoder för att reducera matriser till Hessenbergmatriser med samma egenvärden. Om den ursprungliga matrisen är symmetrisk eller hermitisk, kommer den resulterande matrisen att vara tridiagonal.

Om endast egenvärden behövs finns det inget behov av att beräkna likhetsmatrisen, eftersom den transformerade matrisen har samma egenvärden. Om egenvektorer också behövs behövs en likhetsmatris för att omvandla egenvektorerna för Hessenbergmatrisen till egenvektorerna för den ursprungliga matrisen.

Metod	Gäller matriser	Resultat	Pris utan likhetsmatris	Pris med likhetsmatris	Beskrivning
Hushållarförvandlingar	allmän syn	Hessenberg matris	2 n 3 ⁄ 3 +O(n2)[4]	4 n 3 ⁄ 3 +O(n2)[4]	Reflektera varje kolumn med avseende på delutrymme för att nollställa de nedre elementen i kolumnen.
Gives svängar	allmän syn	Hessenberg matris	4 n 3 ⁄ 3 +O(n2)[4]		En platt rotation utförs till noll enskilda element. Rotationerna är ordnade så att följande rotationer inte påverkar nollelementen.
Iterationer av Arnoldi	allmän syn	Hessenberg matris			Gram–Schmidt- ortogonaliseringen på Krylov-delrummen genomförs .
Lanczos algoritm [5]	Hermitian	tridiagonal matris			Arnoldi-iterationer för hermitiska matriser.

Iterativa algoritmer

Iterativa algoritmer löser problemet med att beräkna egenvärden genom att konstruera sekvenser som konvergerar till egenvärden. Vissa algoritmer ger också sekvenser av vektorer som konvergerar till egenvektorer. Oftast uttrycks sekvenser av egenvärden i termer av sekvenser av liknande matriser som konvergerar till en triangulär eller diagonal form, vilket sedan gör det enkelt att få fram egenvärdena. Egenvektorsekvenser uttrycks i termer av motsvarande likhetsmatriser.

Metod	Gäller matriser	Resultat	Pris per steg	Konvergens	Beskrivning
Effektmetod	allmän syn	största egenvärdet och motsvarande vektor	O ( n2 ) _	Linjär	Multipel matrismultiplikation med en godtyckligt vald initial vektor följt av normalisering.
Invers effektmetod	allmän syn	egenvärdet närmast μ och motsvarande vektor		Linjär	Power iteration med matris ( A - μ E ) -1
Rayleigh iterationsmetod	allmän syn	egenvärdet närmast μ och motsvarande vektor		kubisk	Power iteration med matris ( A - μ i E ) -1 , där μ i är Rayleigh-förhållandet från föregående iteration.
Förutsättning bakåt iteration [6] eller LOBPCG	positiv definitiv reell symmetri	egenvärdet närmast μ och motsvarande vektor			Omvänd iteration med förkonditionering (ungefärlig inversion av matris A ).
Bisektionsmetod [7]	riktigt symmetrisk tridiagonal	något egenvärde		Linjär	Använder bisektionsmetoden för att hitta rötterna till det karakteristiska polynomet och egenskaperna för Sturm-sekvensen .
Iterationer av Laguerre	riktigt symmetrisk tridiagonal	något egenvärde		Kubik [8]	Använder Laguerre-metoden för att beräkna rötterna till det karakteristiska polynomet och egenskaperna för Sturm-sekvensen .
QR-algoritm [9]	hessenberg	alla egenvärden	O ( n2 ) _	kubisk	Nedbrytning A = QR , där Q är ortogonal, R är triangulär, sedan används iteration till RQ .
QR-algoritm [9]	hessenberg	alla egenvärden	6 n 3 + O ( n 2 )	kubisk
Jacobi metod	riktigt symmetrisk	alla egenvärden	O ( n 3 )	kvadratisk	Använder Givens rotation i ett försök att bli av med off-diagonala element. Försöket misslyckas, men stärker diagonalen.
Dela och erövra	Hermitisk tridiagonal	alla egenvärden	O ( n2 ) _		Matrisen är uppdelad i submatriser, som diagonaliseras och sedan återkombineras.
Dela och erövra	Hermitisk tridiagonal	alla egenvärden	( 4 ⁄ 3 ) n 3 + O ( n 2 )
Homotopi metod	riktigt symmetrisk tridiagonal	alla egenvärden	O ( n 2 ) [10]		En beräkningsbar homotopi konstrueras.
Spektral faltningsmetod	riktigt symmetrisk	egenvärdet närmast μ och motsvarande egenvektor			Förkonditionerad tillbaka iteration tillämpad på ( A - μ E ) 2
MRRR-algoritm [11]	riktigt symmetrisk tridiagonal	några eller alla egenvärden och motsvarande egenvektorer	O ( n2 ) _		"Flera relativt robusta representationer" - Omvänd iteration utförs med LDL T - nedbrytning av den förspända matrisen.

Direkt beräkning

Det finns inga enkla algoritmer för att direkt beräkna egenvärden för matriser i det allmänna fallet, men för många specialklasser av matriser kan egenvärden beräknas direkt. Det:

Triangulära matriser

Eftersom determinanten för en triangulär matris är produkten av dess diagonala element, då för en triangulär matris T . Således är egenvärdena för T dess diagonala element. $\mathrm {det} \left(\lambda ET\right)={\prod }_{i}\left(\lambda -T_{ii}\right)$

Nedbrytbara polynomekvationer

Om p är vilket polynom som helst och p ( A ) = 0, så uppfyller egenvärdena för matris A samma ekvation. Om polynomet p kan faktoriseras, är egenvärdena för A bland dess rötter.

Till exempel är en projektor en kvadratisk matris P som uppfyller ekvationen P 2 = P . Rötterna till den motsvarande skalära polynomekvationen λ 2 = λ kommer att vara 0 och 1. Projektorn har alltså 0 och 1 som egenvärden. Egenvärdets multiplicitet 0 är defekten av P , medan multipliciteten av 1 är rangordningen av P .

Ett annat exempel är en matris A som uppfyller ekvationen A 2 = α 2 E för viss skalär α . Egenvärdena måste vara lika med ±α . Designoperatörer

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

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

tillfredsställa jämlikheterna

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

och

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

Kolumnutrymmena för matriserna P + och P - är delrum till matrisens A egenvektorer , motsvarande +α respektive -α .

Matriser 2×2

För dimensionerna 2 till 4 finns radikalformler som kan användas för att beräkna egenvärden. matriser är detta vanligt, men för 4x4-matriser gör den växande komplexiteten hos rotformlerna detta tillvägagångssätt mindre attraktivt.

För 2×2 matriser

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

det karakteristiska polynomet är

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

Egenvärdena kan hittas som rötterna till en andragradsekvation :

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

Om det definieras som avståndet mellan två egenvärden är det lätt att beräkna $\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)))

med liknande formler för c och d . Det följer att beräkningen är väl betingad om egenvärdena är isolerade.

Egenvektorer kan erhållas med hjälp av Hamilton-Cayleys sats . Om λ 1 , λ 2 är egenvärden, då ( A - λ 1 E )( A - λ 2 E ) = ( A - λ 2 E )( A - λ 1 E ) = 0 , så kolumnerna ( A - λ 2 E ) sätts till noll av matrisen ( A - λ 1 E ) och vice versa. Om man antar att ingen av matriserna är lika med noll, måste kolumnerna i varje matris innehålla egenvektorer för ett annat egenvärde (om matrisen är noll, så är A produkten av identitetsmatrisen med en konstant, och alla icke- nollvektor är en egenvektor).

Till exempel, låt

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

sedan tr( A ) = 4 - 3 = 1 och det( A ) = 4(-3) - 3(-2) = -6 , så den karakteristiska ekvationen är

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

och egenvärdena är 3 och −2. Nu

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

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

I båda matriserna skiljer sig kolumnerna med skalära koefficienter, så vilken kolumn som helst kan väljas. Så, (1, -2) kan användas som egenvektor som motsvarar egenvärdet −2, och (3, -1) som egenvektor för egenvärdet 3, vilket enkelt kan kontrolleras genom att multiplicera med matrisen A .

Matriser 3×3

Om A är en 3×3-matris kommer den karakteristiska ekvationen att vara:

{\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.

Denna ekvation kan lösas med metoderna för Cardano eller Lagrange , men den affina transformationen av matrisen A förenklar uttrycket avsevärt och leder direkt till den trigonometriska lösningen . Om A = pB + qE så har A och B samma egenvektorer och β är ett egenvärde för matris B om och endast om α = pβ + q är ett egenvärde för matris A . Om vi sätter och får vi $\textstyle q={\rm {tr))(A)/3$ ${\displaystyle \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.

Substitutionen β = 2cos θ och viss förenkling med identiteten cos 3 θ = 4cos 3 θ - 3cos θ reducerar ekvationen till cos 3 θ = det( B ) / 2 . På det här sättet,

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

Om det( B ) är ett komplext tal eller större än 2 i absolut värde, bör den inversa cosinus för alla tre k- värden tas från samma gren. Problemet uppstår inte om A är reell och symmetrisk, vilket leder till en enkel algoritm: [12]

% Givet en reell symmetrisk 3x3 matris A, beräkna egenvärdena p1 = A ( 1 , 2 ) ^ 2 + A ( 1 , 3 ) ^ 2 + A ( 2 , 3 ) ^ 2 om ( p1 == 0 ) % A är diagonal. eig1 = A ( 1 , 1 ) eig2 = A ( 2 , 2 ) eig3 = A ( 3 , 3 ) annan q = spår ( 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 är identitetsmatrisen r = det ( B ) / 2 % I exakt aritmetik för en symmetrisk matris -1 <= r <= 1 % men beräkningsfel kan lämna det utanför detta område något. om ( r <= - 1 ) phi = pi / 3 elseif ( r >= 1 ) phi = 0 annan phi = acos ( r ) / 3 slutet % egenvärdena uppfyller eig3 <= eig2 <= eig1 eig1 = q + 2 * p * cos ( phi ) eig3 = q + 2 * p * cos ( phi + ( 2 * pi / 3 )) eig2 = 3 * q - eig1 - eig3 % eftersom spår(A) = eig1 + eig2 + eig3 slutet

Återigen kan egenvektorerna för A erhållas genom att använda Hamilton-Cayleys sats . Om α 1 , α 2 , α 3 är olika egenvärden för matrisen A , då ( A - α 1 E ) ( A - α 2 E ) ( A - α 3 E ) = 0 . Då innehåller kolumnerna av produkten av två av dessa matriser egenvektorerna för det tredje egenvärdet. Emellertid , om a3 = ai , då ( A - aiE ) 2 ( A - a2E ) = 0 och ( A - a2E ) ( A - a1E ) 2 = 0 . _ _ _ Sålunda sträcks det egentliga rotunderrummet α1 av kolumnerna A - α2E , medan det vanliga egentliga underutrymmet sträcks av kolumnerna ( A - α1E ) ( A - α2E ) . Det vanliga rätta underrummet α 2 spänns av kolumner ( A - α 1 E ) 2 .

Till exempel, låt

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

Den karakteristiska ekvationen är

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

med egenvärden 1 (multiplicitet 2) och −1. Beräkna

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

och då

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

Då är (-4, -4, 4) egenvektorn för −1 och (4, 2, -2) är egenvektorn för 1. Vektorerna (2, 3, -1) och (6, 5, -3) är de rotvektorer som motsvarar värdet 1, vilka alla kan kombineras med (-4, -4, 4) och (4, 2, -2) för att bilda basen för matrisens A rotvektorer .

Se även

Lista över egenvärdesberäkningsalgoritmer

Kommentarer

↑ Termen "enkel" används här endast för att betona skillnaden mellan "egenvektor" och "rotvektor".
↑ där konstanttermen multipliceras med identitetsmatrisen E .
↑ Denna ordning i den skalära produkten (med det konjugerade elementet till vänster) föredras av fysiker. Algebraister föredrar ofta notationen w • v = v * w .

Anteckningar

↑ Sheldon Axler. Ned med determinanter! // American Mathematical Monthly. - 1995. - Utgåva. 102 . - S. 139-154 .
↑ FL Bauer, CT Fike. Normer och uteslutningssatser // Tal. Matematik. - 1960. - Utgåva. 2 . - S. 137-141 .
↑ SC Eisenstat, ICF Ipsen. Relativa störningsresultat för egenvärden och egenvektorer för diagonaliserbara matriser // 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. Numeriska recept i C. - 2:a. - Cambridge University Press, 1992. - ISBN 0-521-43108-5 .
↑ Kh. D. Ikramov. Glesa matriser. - 1982. - T. 20. - (Resultat av vetenskap och teknik. Ser. Mat. anal).
↑ K. Neymeyr. En geometrisk teori för förkonditionerad invers iteration IV: Om de snabbaste konvergensfallen. // Linjär Algebra Appl. - 2006. - T. 415 , nr. 1 . - S. 114-139 . - doi : 10.1016/j.laa.2005.06.022 .
↑ Wilkinson, 1970 , s. 274, Bisektionsmetod
↑ T. Y Li, Zhonggang Zeng. Laguerre's Iteration In Solving The Symmetric Tridiagonal Eigenproblem - Revisited // SIAM Journal on Scientific Computing . — 1992.
↑ Parlett, 1983 , s. 156, kapitel 8, QR- och QL-algoritmer
↑ Moody T. Chu. En anmärkning om homotopimetoden för linjära algebraiska egenvärdeproblem // Linear Algebra Appl. - 1988. - T. 105 . - S. 225-236 . - doi : 10.1016/0024-3795(88)90015-8 .
↑ Inderjit S. Dhillon, Beresford N. Parlett, Christof Vömel. Utformningen och implementeringen av MRRR-algoritmen // ACM-transaktioner på matematisk programvara . - 2006. - T. 32 , nr. 4 . - S. 533-560 . - doi : 10.1145/1186785.1186788 .
↑ Oliver K. Smith. Egenvärden för en symmetrisk 3 × 3 matris // Kommunikation av ACM . - T. 4 , nej. 4 . - S. 168 . - doi : 10.1145/355578.366316 .

Litteratur

J. Golub, C. Van Lone. Matrisberäkningar. - Moskva: Mir, 1999. - ISBN 5-03-002406-9 .
B. Parlett. Symmetriskt egenvärdeproblem. - Moskva: Mir, 1983.
J.H. Wilkinson. Algebraiskt egenvärdeproblem. - Moskva: "Nauka" Huvudupplagan av fysisk och matematisk litteratur, 1970.

Ytterligare läsning

Adam W. Bojanczyk, Adam Lutoborski. Beräkning av Euler-vinklarna för en symmetrisk 3X3-matris // SIAM Journal on Matrix Analysis and Applications. - Jan 1991. - T. 12 , nr. 1 . - S. 41-48 . - doi : 10.1137/0612005 .