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 .
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]
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
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
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 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 :
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.
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:
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.
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.
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.
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 λ́.
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 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 . |
alla egenvärden | 6 n 3 + O ( n 2 ) | ||||
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. | |
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. |
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:
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.
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
tillfredsställa jämlikheterna
och
Kolumnutrymmena för matriserna P + och P - är delrum till matrisens A egenvektorer , motsvarande +α respektive -α .
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
det karakteristiska polynomet är
Egenvärdena kan hittas som rötterna till en andragradsekvation :
Om det definieras som avståndet mellan två egenvärden är det lätt att beräkna
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
sedan tr( A ) = 4 - 3 = 1 och det( A ) = 4(-3) - 3(-2) = -6 , så den karakteristiska ekvationen är
och egenvärdena är 3 och −2. Nu
,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 .
Om A är en 3×3-matris kommer den karakteristiska ekvationen att vara:
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
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,
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
Den karakteristiska ekvationen är
med egenvärden 1 (multiplicitet 2) och −1. Beräkna
,och då
.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 .