Eigenvalue-algoritme - Eigenvalue algorithm

I numerisk analyse er et af de vigtigste problemer at designe effektive og stabile algoritmer til at finde egenværdierne i en matrix . Disse egenværdealgoritmer kan også finde egenvektorer.

Eigenværdier og egenvektorer

Givet en $n \times n$ kvadratmatrix $A$ med reelle eller komplekse tal, er en egenværdi $λ$ og dens tilknyttede generaliserede egenvektor $v$ et par, der adlyder forholdet

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

hvor $v$ er en nul $n \times 1$ søjlevektor, $I$ er $n \times n$ identitetsmatrix , $k$ er et positivt heltal, og både $λ$ og $v$ får lov til at være komplekse, selv når $A$ er reel. Når $k = 1$ , kaldes vektoren simpelthen en egenvektor , og parret kaldes et eget par . I dette tilfælde er $A v = λ v$ . Enhver egenværdi $λ$ af $A$ har almindelige egenvektorer tilknyttet, for hvis $k$ er det mindste heltal, således at $(A - λI) k v = 0$ for en generaliseret egenvektor $v$ , så $(A - λI) k -1 v$ er en almindelig egenvektor . Værdien $k$ kan altid tages som mindre end eller lig med $n$ . Især $(A - λI) n v = 0$ for alle generaliserede egenvektorer $v$ associeret med $λ$ .

For hver egenværdi $λ$ af $A$ , den kerne $ker (A - Ai)$ består af alle egenvektorer associeret med $λ$ (sammen med 0), kaldet den eigenspace af $λ$ , mens vektorrummet $ker ((A - Ai) n)$ består af alle generaliserede egenvektorer og kaldes det generaliserede egenrum . Den geometriske mangfoldighed af $λ$ er dimensionen af dens egenrum. Den algebraiske mangfoldighed af $λ$ er dimensionen af dets generaliserede ejenspace. Sidstnævnte terminologi er begrundet med ligningen

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

hvor $that$ er den afgørende funktion, $λ jeg$ er alle de distinkte egenværdierne for $A$ og $α jeg$ er den tilsvarende algebraiske mangfoldigheder. Funktionen $p A (z)$ er det karakteristiske polynomium af $A$ . Så den algebraiske mangfoldighed er mangfoldigheden af egenværdien som et nul af det karakteristiske polynom. Da enhver egenvektor også er en generaliseret egenvektor, er den geometriske mangfoldighed mindre end eller lig med den algebraiske mangfoldighed. De algebraiske multiplikationer summeres til $n$ , graden af det karakteristiske polynom. Ligningen $p A (z) = 0$ kaldes karakteristiske ligning , som dens rødder er nøjagtig de egenværdierne for $A$ . Af Cayley-Hamilton sætning , $A$ selv adlyder samme ligning: $p A (A) = 0$ . Som en konsekvens skal matricens søjler enten være 0 eller generaliserede egenvektorer af egenværdien $λ$ $j$ , da de udslettes af . Faktisk kolonnerummet er den generaliserede eigenspace af $λ$ $j$ . ${\ textstyle \ prod _ {i \ neq j} (A- \ lambda _ {i} I) ^ {\ alpha _ {i}}}$ ${\ displaystyle (A- \ lambda _ {j} I) ^ {\ alpha _ {j}}}$

Enhver samling af generaliserede egenvektorer med forskellige egenværdier er lineært uafhængige, så der kan vælges et grundlag for alle $C n$ bestående af generaliserede egenvektorer. Mere specifikt er dette grundlag ${v i} n i = 1$ kan vælges og organiseres, så

hvis $v i$ og $v j$ har den samme egenværdi, så gør $v k også$ for hver $k$ mellem $i$ og $j$ , og
hvis $v i$ ikke er en almindelig egenvektor, og hvis $λ i$ er dens egenværdi, så $(A - λ i I) v i = v i -1$ (især skal $v 1$ være en almindelig egenvektor).

Hvis disse basisvektorer er placeret som søjlevektorerne i en matrix $V = [v 1 v 2 \dots v n]$ , kan $V$ bruges til at konvertere $A$ til sin normale Jordan-form :

{\ displaystyle 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} },}

hvor $λ i$ er egenværdierne, $β i = 1$ hvis ellers $(A - λ i +1) v i +1 = v i$ og $β i = 0$ .

Mere generelt, hvis $W$ er en hvilken som helst inverterbar matrix, og $λ$ er en egenværdi af $A$ med generaliseret egenvektor $v$ , så $(W -1 AW - λI) k W - k v = 0$ . Således er $λ$ en egenværdi af $W -1 AW$ med generaliseret egenvektor $W - k v$ . Det vil sige, at lignende matricer har de samme egenværdier.

Normale, hermitiske og ægte-symmetriske matricer

Den adjungerede $M *$ af en kompleks matrix $M$ er transponeringen af konjugatet af $M$ : $M * = M T$ . En firkantet matrix $A$ kaldes normal, hvis den pendler med dens tilknytning: $A * A = AA *$ . Det kaldes hermitisk hvis det er lig med dens adjungerede: $A * = A$ . Alle Hermitian-matricer er normale. Hvis $A$ kun har reelle elementer, er tilslutningen kun transponeringen, og $A$ er Hermitian, hvis og kun hvis den er symmetrisk . Når det anvendes på søjlevektorer, kan tilslutningen bruges til at definere det kanoniske indre produkt på $C n$ : $w \cdot v = w * v$ . Normale, hermitiske og ægte-symmetriske matricer har flere nyttige egenskaber:

Hver generaliseret egenvektor i en normal matrix er en almindelig egenvektor.
Enhver normal matrix svarer til en diagonal matrix, da dens normale Jordan-form er diagonal.
Eigenvektorer med forskellige egenværdier i en normal matrix er ortogonale.
Nulrummet og billedet (eller kolonneområdet) for en normal matrix er vinkelrette på hinanden.
For enhver normal matrix $A$ , $C n$ har en ortonormalbasis bestående af egenvektorer af $A$ . Den tilsvarende matrix af egenvektorer er enhed .
Egenværdierne for en hermitisk matrix er reelle, da $(λ - λ) v = (A * - A) v = (A - A) v = 0$ for en ikke-nul egenvektor $v$ .
Hvis $A$ er reel, er der en ortonormalbasis for $R n$ bestående af egenvektorer af $A$ hvis og kun hvis $A$ er symmetrisk.

Det er muligt for en reel eller kompleks matrix at have alle reelle egenværdier uden at være Hermitian. For eksempel har en ægte trekantet matrix sine egenværdier langs sin diagonale, men er generelt ikke symmetrisk.

Betingelsesnummer

Ethvert problem med numerisk beregning kan ses som en evaluering af en funktion $f$ for noget input $x$ . Problemets tilstandsnummer $κ (f, x)$ er forholdet mellem den relative fejl i funktionens output og den relative fejl i input og varierer med både funktionen og input. Betingelsesnummeret beskriver, hvordan fejlen vokser under beregningen. Dens base-10 logaritme fortæller, hvor mange færre nøjagtighedscifre der findes i resultatet, end der var i input. Betingelsesnummeret er et bedste tilfælde. Det afspejler den ustabilitet, der er indbygget i problemet, uanset hvordan det løses. Ingen algoritme kan nogensinde producere mere nøjagtige resultater end angivet af betingelsesnummeret, undtagen tilfældigt. Imidlertid kan en dårligt designet algoritme give betydeligt dårligere resultater. For eksempel, som nævnt nedenfor, er problemet med at finde egenværdier til normale matricer altid godt betinget. Problemet med at finde rødderne til et polynom kan imidlertid være meget dårligt betinget . Således kan egenværdealgoritmer, der fungerer ved at finde rødderne til det karakteristiske polynom, være dårligt betingede, selv når problemet ikke er.

For problemet med at løse den lineære ligning $A v = b$ hvor $A$ er inverterbar, gives betingelsesnummeret $κ (A -1, b)$ ved $|| A || op || A -1 || op$ , hvor || || _op er den operatør normen underordnet den normale euklidiske norm på $C n$ . Eftersom dette antal er uafhængig af $b$ og er den samme for $A$ og $A -1$ , er det normalt blot kaldes konditionstallet $κ (A)$ af matrixen $A$ . Denne værdi $κ (A)$ er også den absolutte værdi af forholdet mellem den største egenværdi af $A$ og dens mindste. Hvis $A$ er enhed , så $|| A || op = || A -1 || op = 1$ , så $κ (A) = 1$ . For generelle matricer er operatørnormen ofte vanskelig at beregne. Af denne grund bruges andre matrixnormer ofte til at estimere tilstandsnummeret.

For egenværdiproblemet beviste Bauer og Fike, at hvis $λ$ er en egenværdi for en diagonaliserbar $n \times n-$ matrix $A$ med egenvektormatrix $V$ , så er den absolutte fejl ved beregning af $λ$ afgrænset af produktet af $κ (V)$ og den absolutte fejl i $A$ . Som et resultat , konditionstallet om at finde $λ$ er $κ (λ, A) = κ (V) = || V || op || V -1 || op$ . Hvis $A$ er normal, er $V$ enhed, og $κ (λ, A) = 1$ . Således er egenværdiproblemet for alle normale matricer godt betinget.

Konditionstallet for problemet med at finde den eigenspace af en normal matrix $A$ svarer til en egenværdi $λ$ er blevet vist at være omvendt proportional med den minimale afstand mellem $λ$ og de andre særskilte egenværdierne for $A$ . Især er ejenspace-problemet for normale matricer godt betinget af isolerede egenværdier. Når egenværdier ikke isoleres, er det bedste, man kan håbe på, at identificere spændvidden for alle egenvektorer af nærliggende egenværdier.

Algoritmer

Ethvert monikpolynom er det karakteristiske polynom af dets ledsagermatrix . Derfor kunne en generel algoritme til at finde egenværdier også bruges til at finde rødderne til polynomer. De Abel-Ruffini sætningen viser, at en sådan algoritme til større dimensioner end 4, skal enten være uendelig eller involvere funktioner af større kompleksitet end elementære aritmetiske operationer og brøkpotenser. Af denne grund findes algoritmer, der nøjagtigt beregner egenværdier i et endeligt antal trin, kun for et par specielle klasser af matricer. For generelle matricer er algoritmer iterative , hvilket giver bedre omtrentlige løsninger med hver iteration.

Nogle algoritmer producerer hver egenværdi, andre producerer nogle få eller kun en. Selv de sidstnævnte algoritmer kan dog bruges til at finde alle egenværdier. Når en egenværdi $λ$ af en matrix $A$ er blevet identificeret, kan den bruges til enten at styre algoritmen mod en anden løsning næste gang eller til at reducere problemet til en, der ikke længere har $λ$ som en løsning.

Omdirigering opnås normalt ved at skifte: erstatte $A$ med $A - μI$ for noget konstant $μ$ . Den egenværdi fundet for $A - μI$ skal have $μ$ tilføjet tilbage i at få en egenværdi for $A$ . For eksempel til power iteration er $μ = λ$ . Power iteration finder den største egenværdi i absolut værdi, så selv når $λ$ kun er en tilnærmet egenværdi, vil power iteration sandsynligvis ikke finde det en anden gang. Omvendt finder inverse iterationsbaserede metoder den laveste egenværdi, så $μ$ vælges langt væk fra $λ$ og forhåbentlig tættere på en anden egenværdi.

Reduktion kan opnås ved at begrænse $A$ til kolonneområdet i matricen $A - λI$ , som $A$ bærer til sig selv. Da $A - λI$ er ental, har søjlerummet mindre dimension. Egenværdealgoritmen kan derefter anvendes til den begrænsede matrix. Denne proces kan gentages, indtil alle egenværdier findes.

Hvis en egenværdealgoritme ikke producerer egenvektorer, er en almindelig praksis at bruge en invers iterationsbaseret algoritme med $μ$ indstillet til en tæt tilnærmelse til egenværdien. Dette konvergerer hurtigt til egenvektoren for den nærmeste egenværdi til $μ$ . For små matricer er et alternativ at se på kolonneområdet for produktet af $A - λ' I$ for hver af de andre egenværdier $λ'$ .

En formel for normen for enhedens egenvektorkomponenter i normale matricer blev opdaget af Robert Thompson i 1966 og genopdaget uafhængigt af flere andre. Hvis $A$ er en normal matrix med egenværdier $Å$ $i$ $($ $A$ $)$ og tilsvarende enhed egenvektorer $v$ $jeg$ hvis komponent indgange er $v$ $i, j$ , lad $A$ $j$ være den opnås ved fjernelse af matrixen $i$ 'te række og søjle fra $A$ , og lad $λ$ $k$ $($ $A$ $j$ $)$ være dens $k$ -th egenværdi. Derefter ${\ textstyle n \ times n}$ ${\ textstyle n-1 \ times n-1}$

{\ displaystyle | v_ {i, j} | ^ {2} \ prod _ {k = 1, k \ neq i} ^ {n} (\ lambda _ {i} (A) - \ lambda _ {k} ( A)) = \ prod _ {k = 1} ^ {n-1} (\ lambda _ {i} (A) - \ lambda _ {k} (A_ {j}))}

Hvis er de karakteristiske polynomer af og , kan formlen omskrives som ${\ displaystyle p, p_ {j}}$ ${\ displaystyle A}$ ${\ displaystyle A_ {j}}$

{\ displaystyle | v_ {i, j} | ^ {2} = {\ frac {p_ {j} (\ lambda _ {i} (A))} {p '(\ lambda _ {i} (A)) }}}

forudsat at derivatet ikke er nul ved .

{\ displaystyle p '}

{\ displaystyle \ lambda _ {i} (A)}

Hessenberg og trediekantede matricer

Fordi egenværdierne for en trekantet matrix er dens diagonale elementer, er der for generelle matricer ingen endelig metode som gaussisk eliminering for at konvertere en matrix til trekantet form, samtidig med at egenværdierne bevares. Men det er muligt at nå noget tæt på trekantet. En øvre Hessenberg-matrix er en firkantet matrix, hvor alle poster under subdiagonalen er nul. En lavere Hessenberg-matrix er en, for hvilken alle poster over superdiagonalen er nul. Matricer, der er både øvre og nedre Hessenberg, er tredobbelte . Hessenberg og trediekantede matricer er udgangspunktet for mange egenværdealgoritmer, fordi nulindgangene reducerer problemets kompleksitet. Flere metoder bruges ofte til at konvertere en generel matrix til en Hessenberg-matrix med de samme egenværdier. Hvis den oprindelige matrix var symmetrisk eller Hermitian, vil den resulterende matrix være trediekantet.

Når der kun er behov for egenværdier, er der ikke behov for at beregne lighedsmatrixen, da den transformerede matrix har de samme egenværdier. Hvis der også er behov for egenvektorer, kan det være nødvendigt med lighedsmatrixen til at omdanne egenvektorerne i Hessenberg-matricen tilbage til egenvektorer i den oprindelige matrix.

Metode	Gælder	Producerer	Omkostninger uden lighedsmatrix	Omkostninger med lighedsmatrix	Beskrivelse
Husholderske transformation	Generel	Hessenberg	$.mw-parser-output .frac{white-space:nowrap}.mw-parser-output .frac .num,.mw-parser-output .frac .den{font-size:80%;line-height:0;vertical-align:super}.mw-parser-output .frac .den{vertical-align:sub}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px} 2 n 3 ⁄ 3 + O ( n 2 )$	$4 n 3 ⁄ 3 + O (n 2)$	Reflekter hver kolonne gennem et underområde for at nulstille de nederste poster.
Givens rotationer	Generel	Hessenberg	$4 n 3 ⁄ 3 + O (n 2)$		Anvend plane rotationer for at nulstille individuelle poster. Rotationer bestilles, så senere ikke får nul poster til at blive ikke-nul igen.
Arnoldi iteration	Generel	Hessenberg			Udfør Gram-Schmidt-ortogonalisering på Krylov-underområder.
Lanczos algoritme	Hermitian	Tridiagonal			Arnoldi-iteration for Hermitian-matricer med genveje.

For symmetriske trediekantede egenværdiproblemer kan alle egenværdier (uden egenvektorer) beregnes numerisk i tid O (n log (n)) ved hjælp af halvering på det karakteristiske polynom.

Iterative algoritmer

Iterative algoritmer løser egenværdiproblemet ved at producere sekvenser, der konvergerer til egenværdierne. Nogle algoritmer producerer også sekvenser af vektorer, der konvergerer til egenvektorerne. Mest almindeligt udtrykkes egenværdisekvenserne som sekvenser af lignende matricer, der konvergerer til en trekantet eller diagonal form, så egenværdierne let kan læses. Egenvektorsekvenserne udtrykkes som de tilsvarende lighedsmatricer.

Metode	Gælder	Producerer	Pris pr. Trin	Konvergens	Beskrivelse
Lanczos algoritme	Hermitian	$m$ største / mindste egenpar
Power iteration	generel	egenpar med den største værdi	$O (n 2)$	lineær	Anvender matrixen gentagne gange på en vilkårlig startvektor og renormaliserer.
Omvendt iteration	generel	egenpar med værdi tættest på μ		lineær	Power iteration for $(A - μI) -1$
Rayleigh kvotient iteration	Hermitian	ethvert eget par		kubisk	Power iteration for $(A - μ i I) -1$ , hvor $μ i$ for hver iteration er Rayleigh kvotienten for den tidligere iteration.
Forudbetalt invers iteration eller LOBPCG-algoritme	positiv-bestemt reel symmetrisk	egenpar med værdi tættest på μ			Invers iteration ved hjælp af en forkonditionering (en omtrentlig invers til $A$ ).
Halveringsmetode	ægte symmetrisk trekant	enhver egenværdi		lineær	Bruger halveringsmetoden til at finde rødderne til det karakteristiske polynom understøttet af Sturm-sekvensen.
Laguerre iteration	ægte symmetrisk trekant	enhver egenværdi		kubisk	Bruger Laguerres metode til at finde rødderne til det karakteristiske polynom understøttet af Sturm-sekvensen.
QR-algoritme	Hessenberg	alle egenværdier	$O (n 2)$	kubisk	Faktorer A = QR , hvor Q er ortogonal og R er trekantet, anvender derefter den næste iteration på RQ .
QR-algoritme	Hessenberg	alle egenpar	$6 n 3 + O (n 2)$	kubisk
Jacobi egenværdealgoritme	ægte symmetrisk	alle egenværdier	$O (n 3)$	kvadratisk	Bruger Givens-rotationer til at forsøge at rydde alle off-diagonale poster. Dette mislykkes, men styrker diagonalen.
Opdel-og-erobre	Hermitian tredobbelt	alle egenværdier	$O (n 2)$		Opdeler matrixen i submatricer, der er diagonaliseret og derefter rekombineret.
Opdel-og-erobre	Hermitian tredobbelt	alle egenpar	$(4 ⁄ 3) n 3 + O (n 2)$
Homotopimetode	ægte symmetrisk trekant	alle egenpar	$O (n 2)$		Konstruerer en beregningsbar homotopisti fra et diagonalt egenværdiproblem.
Foldet spektrummetode	ægte symmetrisk	egenpar med værdi tættest på μ			Forudbetalt omvendt iteration anvendt til $(A - μI) 2$
MRRR-algoritme	ægte symmetrisk trekant	nogle eller alle egenpar	$O (n 2)$		"Flere relativt robuste repræsentationer" - udfører invers iteration på en LDL ^T- nedbrydning af den forskudte matrix.

Direkte beregning

Mens der ikke er nogen simpel algoritme til direkte beregning af egenværdier for generelle matricer, er der adskillige specielle klasser af matricer, hvor egenværdier kan beregnes direkte. Disse inkluderer:

Trekantede matricer

Da determinanten for en trekantet matrix er produktet af dens diagonale indgange, hvis T er trekantet, så . Således er egenværdierne for T dens diagonale poster. ${\ textstyle \ det (\ lambda IT) = \ prod _ {i} (\ lambda -T_ {ii})}$

Faktorable polynomiske ligninger

Hvis $p$ er et polynom og $p (A) = 0,$ så tilfredsstiller egenværdierne af $A$ også den samme ligning. Hvis $p$ tilfældigvis har en kendt faktorisering, ligger egenværdierne for $A$ blandt dens rødder.

For eksempel et fremspring er en kvadratisk matrix $P$ opfylder $P 2 = P$ . Rødderne til den tilsvarende skalære polynomligning, $λ 2 = λ$ , er 0 og 1. Enhver projektion har altså 0 og 1 for sine egenværdier. Mangfoldigheden af 0. en egenværdi er ugyldig af $P$ , mens de mange 1 er rang af $P$ .

Et andet eksempel er en matrix $A$ , der tilfredsstiller $A 2 = α 2 I$ for nogle skalar $α$ . Egenværdierne skal være $\pm α$ . Projektionsoperatørerne

{\ displaystyle P _ {+} = {\ frac {1} {2}} \ venstre (I + {\ frac {A} {\ alpha}} \ højre)}

{\ displaystyle P _ {-} = {\ frac {1} {2}} \ venstre (I - {\ frac {A} {\ alpha}} \ højre)}

tilfredsstille

{\ displaystyle AP _ {+} = \ alpha P _ {+} \ quad AP _ {-} = - \ alpha P _ {-}}

og

{\ displaystyle P _ {+} P _ {+} = P _ {+} \ quad P _ {-} P _ {-} = P _ {-} \ quad P _ {+} P _ {-} = P _ {-} P _ {+} = 0.}

De kolonne rum af $P +$ og $P -$ er egenrum af $A$ svarende til $+ α$ og $- α$ hhv.

2 × 2 matricer

For dimensionerne 2 til 4 findes der formler, der involverer radikaler, der kan bruges til at finde egenværdierne. Mens en almindelig praksis for 2 × 2 og 3 × 3 matricer, for 4 × 4 matricer gør den stigende kompleksitet af rodformler denne tilgang mindre attraktiv.

Til 2 × 2-matrixen

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

det karakteristiske polynom er

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

Således kan egenværdierne findes ved hjælp af den kvadratiske formel :

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

Når det defineres som afstanden mellem de to egenværdier, er det ligetil at beregne ${\ textstyle {\ rm {gap}} \ left (A \ right) = {\ sqrt {{\ rm {tr}} ^ {2} (A) -4 \ det (A)}}}$

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

med lignende formler for $c$ og $d$ . Heraf følger, at beregningen er velkonditioneret, hvis egenværdierne er isoleret.

Eigenvektorer kan findes ved at udnytte sætningen Cayley – Hamilton . Hvis $λ 1, λ 2$ er egenværdierne, er $(A - λ 1 I) (A - λ 2 I) = (A - λ 2 I) (A - λ 1 I) = 0$ , så kolonnerne i $(A - λ 2 I)$ udslettes af $(A - λ 1 I)$ og omvendt. Forudsat at ingen af matricerne er nul, skal kolonnerne i hver indeholde egenvektorer for den anden egenværdi. (Hvis en matrix er nul, er $A$ et multiplum af identiteten, og enhver ikke-nul vektor er en egenvektor.)

Antag for eksempel

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

derefter $tr (A) = 4 - 3 = 1$ og $det (A) = 4 (-3) - 3 (-2) = -6$ , så den karakteristiske ligning er

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

og egenværdierne er 3 og -2. Nu,

{\ displaystyle A-3I = {\ begin {bmatrix} 1 & 3 \\ - 2 & -6 \ end {bmatrix}}, \ qquad A + 2I = {\ begin {bmatrix} 6 & 3 \\ - 2 & -1 \ end {bmatrix }}.}

I begge matricer er kolonnerne multipla af hinanden, så begge kolonner kan bruges. Således $(1, -2)$ kan tages som en egenvektor forbundet med egenværdi -2, og $(3, 1)$ som en egenvektor forbundet med egenværdi 3, som kan verificeres ved at multiplicere dem ved $A$ .

3 × 3 matricer

Den karakteristiske ligning af en symmetrisk, 3 × 3 matrix, $A$ , er:

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

Denne ligning kan løses ved hjælp af metoderne fra Cardano eller Lagrange , men en affinisk ændring til $A$ vil forenkle udtrykket betydeligt og føre direkte til en trigonometrisk løsning . Hvis $A = pB + Qi$ , så $A$ og $B$ har de samme egenvektorer, og $β$ er en egenværdi af $B$ hvis og kun hvis $α = pβ + q$ er en egenværdi af $A$ . Udlejning og , giver ${\ textstyle q = {\ rm {tr}} (A) / 3}$ ${\ textstyle p = \ left ({\ rm {tr}} \ left ((A-qI) ^ {2} \ right) / 6 \ right) ^ {1/2}}$

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

Substitutionen $β = 2cos θ$ og en vis forenkling ved hjælp af identiteten $cos 3 θ = 4cos 3 θ - 3cos θ$ reducerer ligningen til $cos 3 θ = det (B) / 2$ . Dermed

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

Hvis $det (B)$ er komplekst eller er større end 2 i absolut værdi, skal arccosinen tages langs den samme gren for alle tre værdier af $k$ . Dette problem opstår ikke, når $A$ er reel og symmetrisk, hvilket resulterer i en simpel algoritme:

% Given a real symmetric 3x3 matrix A, compute the eigenvalues
% Note that acos and cos operate on angles in radians

p1 = A(1,2)^2 + A(1,3)^2 + A(2,3)^2
if (p1 == 0) 
   % A is diagonal.
   eig1 = A(1,1)
   eig2 = A(2,2)
   eig3 = A(3,3)
else
   q = trace(A)/3               % trace(A) is the sum of all diagonal values
   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 * I)    % I is the identity matrix
   r = det(B) / 2

   % In exact arithmetic for a symmetric matrix  -1 <= r <= 1
   % but computation error can leave it slightly outside this range.
   if (r <= -1) 
      phi = pi / 3
   elseif (r >= 1)
      phi = 0
   else
      phi = acos(r) / 3
   end

   % the eigenvalues satisfy eig3 <= eig2 <= eig1
   eig1 = q + 2 * p * cos(phi)
   eig3 = q + 2 * p * cos(phi + (2*pi/3))
   eig2 = 3 * q - eig1 - eig3     % since trace(A) = eig1 + eig2 + eig3
end

Endnu en gang kan egenvektorerne til $A$ opnås ved at anvende sætningen Cayley – Hamilton . Hvis $α 1, α 2, α 3$ er forskellige egenværdier for $A$ , er $(A - α 1 I) (A - α 2 I) (A - α 3 I) = 0$ . Kolonnerne i produktet fra to af disse matricer indeholder således en egenvektor til den tredje egenværdi. Hvis $α 3 = α 1$ , er $(A - α 1 I) 2 (A - α 2 I) = 0$ og $(A - α 2 I) (A - α 1 I) 2 = 0$ . Således generaliseret eigenspace af $α 1$ er udspændt af søjlerne i $A - α 2 I$ mens den almindelige eigenspace er udspændt af søjlerne af $(A - α 1 I) (A - α 2 I)$ . Det almindelige egenrum af $α 2$ er spændt af søjlerne i $(A - α 1 I) 2$ .

Lad f.eks

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

Den karakteristiske ligning er

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

med egenværdier 1 (af multiplicitet 2) og -1. Beregning,

{\ displaystyle AI = {\ begin {bmatrix} 2 & 2 & 6 \\ 2 & 1 & 5 \\ - 2 & -1 & -5 \ end {bmatrix}}, \ qquad A + I = {\ begin {bmatrix} 4 & 2 & 6 \\ 2 & 3 & 5 \\ - 2 & -1 & -3 \ end {bmatrix}}}

og

{\ displaystyle (AI) ^ {2} = {\ begin {bmatrix} -4 & 0 & -8 \\ - 4 & 0 & -8 \\ 4 & 0 & 8 \ end {bmatrix}}, \ qquad (AI) (A + I) = {\ start {bmatrix} 0 & 4 & 4 \\ 0 & 2 & 2 \\ 0 & -2 & -2 \ end {bmatrix}}}

Således $(-4, -4, 4)$ er en egenvektor for −1, og $(4, 2, -2)$ er en egenvektor for 1. $(2, 3, -1)$ og $(6, 5, -3)$ er begge generaliserede egenvektorer forbundet med 1, den ene af hvilke kan kombineres med $(-4, -4, 4)$ og $(4, 2, -2)$ for at danne et grundlag med generelle egenvektorer af $a$ . Når de er fundet, kan egenvektorerne normaliseres, hvis det er nødvendigt.

Eigenvektorer af normale 3 × 3 matricer

Hvis en 3 × 3-matrix er normal, kan krydsproduktet bruges til at finde egenvektorer. Hvis er en egenværdi af , så er nulrummet vinkelret på dets søjlerum, Tværproduktet af to uafhængige søjler af vil være i nulrummet. Det vil sige, det vil være en egenvektor forbundet med . Da søjlerummet i dette tilfælde er todimensionelt, skal ejensområdet være en dimensionelt, så enhver anden egenvektor vil være parallel med det. ${\ displaystyle A}$ ${\ displaystyle \ lambda}$ ${\ displaystyle A}$ ${\ displaystyle A- \ lambda I}$ ${\ displaystyle A- \ lambda I}$ ${\ displaystyle \ lambda}$

Hvis ikke indeholder to uafhængige kolonner, men ikke er $0$ , kan krydsproduktet stadig bruges. I dette tilfælde er en egenværdi af multiplicitet 2, så enhver vektor vinkelret på kolonneområdet vil være en egenvektor. Antag at er en kolonne, der ikke er nul . Vælg en vilkårlig vektor, der ikke er parallel med . Derefter og vil være vinkelret på og således være egenvektorer af . ${\ displaystyle A- \ lambda I}$ ${\ displaystyle \ lambda}$ ${\ displaystyle \ mathbf {v}}$ ${\ displaystyle A- \ lambda I}$ ${\ displaystyle \ mathbf {u}}$ ${\ displaystyle \ mathbf {v}}$ ${\ displaystyle \ mathbf {v} \ times \ mathbf {u}}$ ${\ displaystyle (\ mathbf {v} \ times \ mathbf {u}) \ times \ mathbf {v}}$ ${\ displaystyle \ mathbf {v}}$ ${\ displaystyle \ lambda}$

Dette fungerer ikke, når det ikke er normalt, da nulrummet og kolonneområdet ikke behøver at være vinkelret på sådanne matricer. ${\ displaystyle A}$

Se også

Liste over egenværdealgoritmer

Bemærkninger

Referencer

Yderligere læsning

Bojanczyk, Adam W .; Adam Lutoborski (jan 1991). "Beregning af Euler-vinklerne i en symmetrisk 3X3 matrix" . SIAM Journal om matrixanalyse og applikationer . 12 (1): 41–48. doi : 10.1137 / 0612005 .

Languages

In other projects