Arnoldi iteration

I numerisk linjär algebra är Arnoldi-iteration en algoritm för att beräkna egenvärden . Arnoldi hittar en approximation av egenvärdena och egenvektorerna för allmänna (möjligen icke- hermitiska ) matriser genom att konstruera en ortonormal bas för Krylov-underrummet .

Arnoldi-metoden hänvisar till linjära algebraalgoritmer som gör att en partiell lösning kan erhållas efter ett litet antal iterationer, i motsats till de så kallade direkta metoderna, som måste slutföras helt för att ge några tillfredsställande resultat (t.ex. Householder-reflektion ).

Om algoritmen tillämpas på hermitiska matriser, reduceras den till Lanczos-algoritmen . Arnoldi-iterationen uppfanns av Walter Edwin Arnoldi 1951.

Krylov-underrummet och maktmetoden

En intuitiv metod för att hitta det största (modulo) egenvärdet för en given dimensionsmatris är effektmetoden : börja med en godtycklig initialvektor , beräkna , normalisera resultatet efter varje beräkning. $A$ $m \ gånger m$ $b$ $Ab,A^{2}b,A^{3}b,\dots$

Denna sekvens konvergerar till egenvektorn för motsvarande egenvärde med maximal modul. Detta tyder på att mycket beräkning går till spillo, som i slutändan används bara slutresultatet . Låt oss då istället komponera den så kallade Krylov-matrisen : $\lambda _{1}$ $A^{n-1}b$

$K_{n}={\begin{bmatrix}b&Ab&A^{2}b&\cdots &A^{n-1}b\end{bmatrix}}.$

Kolumnerna i denna matris är i allmänhet inte ortogonala, men vi kan få en ortogonal grund från dem med hjälp av Gram-Schmidt-ortogonalisering . Den resulterande uppsättningen av vektorer kommer att vara den ortogonala basen för Krylov-underrummet . Det kan förväntas att vektorerna för denna bas kommer att vara en bra approximation till de vektorer som motsvarar de största egenvärdena i absolut värde. ${\mathcal {K}}_{n}$ $n$

Arnoldi iteration

Arnoldi-iteration använder en stabiliserad Gram-Schmidt-process för att erhålla en sekvens av ortonormala vektorer , kallade Arnoldi-vektorer , så att, för var och en, vektorerna är en bas för ett Krylov-underrum . Algoritmen ser ut så här: $q_{1},q_{2},q_{3},\dots$ $n$ ${\displaystyle q_{1},\dots ,q_{n))$ ${\mathcal {K}}_{n}$

Börja med en godtycklig vektor q 1 med norm 1.
Upprepa för k = 2, 3, …
- $q_{k}\leftarrow Aq_{k-1}\,$
- för j = 1 ... k − 1
  - $h_{j,k-1}\leftarrow q_{j}^{*}q_{k}\,$
  - $q_{k}\leftarrow q_{k}-h_{j,k-1}q_{j}\,$
- $h_{k,k-1}\leftarrow \|q_{k}\|\,$
- $q_{k}\leftarrow {\frac {q_{k}}{h_{k,k-1}}}\,$

Slingan över projicerar komponenten på . Detta säkerställer ortogonaliteten hos alla konstruerade vektorer. $j$ $q_{k}$ $q_{1},\dots ,q_{k-1}.$

Algoritmen stannar när är en nollvektor. Detta händer när minimipolynomet i matrisen kommer att vara av grad $q_{k}$ $A$ $k.$

Varje steg i for-slingan utför en matris-vektormultiplikation och om bråkoperationer. $k$ $4mk$

I python programmeringsspråk:

importera numpy som np def arnoldi_iteration ( A , b , n : int ): """Beräknar en bas för (n + 1)-Krylov-underrummet i A: det utrymme som spänner över av {b, Ab, ..., A^nb}. Argument A: m × m array b: initial vektor (längd m) n: dimensionen av Krylov underrum, måste vara >= 1 Returnerar Q: mx (n + 1) array, kolumnerna är en ortonormal bas för Krylov-underrummet. h: (n + 1) xn-matris, A på basis av Q. Det är övre Hessenberg. """ m = A . form [ 0 ] h = np . nollor (( n + 1 , n )) Q = np . nollor (( m , n + 1 )) q = b / np . linalg . norm ( b ) ) # Normalisera ingångsvektorn Q [:, 0 ] = q # Använd den som den första Krylovvektorn för k i intervallet ( n ) : v = A. punkt ( q ) # Generera en ny kandidatvektor för j i intervallet ( k + 1 ): # Subtrahera projektionerna på tidigare vektorer h [ j , k ] = np . punkt ( Q [:, j ] . conj (), v ) v = v - h [ j , k ] * Q [:, j ] h [ k + 1 , k ] = np . linalg . norm ( v ) eps = 1e-12 # Om v är kortare än detta tröskelvärde är det nollvektorn om h [ k + 1 , k ] > eps : # Lägg till den producerade vektorn till listan, om inte q = v / h [ k + 1 , k ] # nollvektorn produceras. Q [:, k + 1 ] = q annat : # Om det händer, sluta iterera. return Q , h return Q , h