Arnoldi iteration

I numerisk linjär algebra är Arnoldi -iterationen en egenvärdesalgoritm och ett viktigt exempel på en iterativ metod . Arnoldi hittar en approximation till egenvärdena och egenvektorerna för generella (möjligen icke- hermitiska ) matriser genom att konstruera en ortonormal bas för Krylov-underrummet , vilket gör det särskilt användbart när man har att göra med stora glesa matriser .

Arnoldimetoden tillhör en klass av linjära algebraalgoritmer som ger ett partiellt resultat efter ett litet antal iterationer, till skillnad från så kallade direkta metoder som måste genomföras för att ge några användbara resultat (se till exempel Hushållartransformation ). Delresultatet i detta fall är de första vektorerna av den bas som algoritmen bygger.

När den tillämpas på hermitiska matriser reduceras den till Lanczos-algoritmen . Arnoldi-iterationen uppfanns av WE Arnoldi 1951.

Krylov underrum och kraft iterationen

En intuitiv metod för att hitta det största (i absoluta värdet) egenvärdet för en given m × m matris $A$ är potens iterationen : börja med en godtycklig initialvektor b , beräkna Ab , A ² b , A ³ b , ... normalisera resultatet efter varje applicering av matrisen A .

Denna sekvens konvergerar till egenvektorn som motsvarar egenvärdet med det största absoluta värdet, $\lambda _{1}$ . Men mycket potentiellt användbar beräkning går till spillo genom att endast använda slutresultatet, $A^{n-1}b$ . Detta tyder på att vi istället bildar den så kallade Krylov-matrisen :

$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 extrahera en ortogonal bas , via en metod som Gram–Schmidt-ortogonalisering . Den resulterande uppsättningen av vektorer är således en ortogonal bas för Krylov-underrummet , ${\mathcal {K}}_{n}$ . Vi kan förvänta oss att vektorerna för denna bas spänner över goda approximationer av egenvektorerna som motsvarar de $n$ största egenvärdena, av samma anledning som $A^{n-1}b$ approximerar den dominerande egenvektorn.

Arnoldi-iterationen

Arnoldi-iterationen använder den modifierade Gram-Schmidt-processen för att producera en sekvens av ortonormala vektorer, q ₁ , q ₂ , q ₃ , ..., kallade Arnoldi-vektorerna , så att för varje n , vektorerna q ₁ , ... , q _n spänner över Krylov-underrummet ${\mathcal {K}}_{n}$ . Algoritmen är uttryckligen följande:

 
    
     
 Börja med en godtycklig vektor  q  1  med norm 1. Upprepa för  k  = 2, 3, ...  q  k  :=  A  q  k  −1  för  j  från 1 till  k  − 1  h  j  ,  k  −1  :=  q  j  *  q  k  q  k  :=  q  k  − h  j  ,  k  −1  q  j  h  k  ,  k  −1  := ||  q  k  ||  q  k  :=  q  k  /  h  k  ,  k  −1 

J - loopen projicerar ut komponenten av $q_{k}$ i riktningarna $q_{1},\dots ,q_{k-1}$ . Detta säkerställer ortogonaliteten hos alla genererade vektorer.

Algoritmen går sönder när q _k är nollvektorn. Detta händer när det minimala polynomet av A är av graden k . I de flesta tillämpningar av Arnoldi-iterationen, inklusive egenvärdealgoritmen nedan och GMRES , har algoritmen konvergerat vid denna punkt.

Varje steg i k -loopen tar en matris-vektorprodukt och cirka 4 mk flyttalsoperationer.

I programmeringsspråket Python med stöd av NumPy -biblioteket:

   

    
    






    





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

Egenskaper för Arnoldi-iterationen

Låt Qn beteckna m -by- n -matrisen som bildas av de första n _Arnoldi -vektorerna q ₁ , q ₂ , ..., q _n , och låt H _n vara den (övre Hessenberg ) matrisen som bildas av talen h _{j , k} beräknas av algoritmen:

$H_{n}=Q_{n}^{*}AQ_{n}.$

Ortogonaliseringsmetoden måste väljas specifikt så att de lägre Arnoldi/Krylov-komponenterna tas bort från högre Krylov-vektorer. Eftersom $Aq_{i}$ kan uttryckas i termer av q ₁ , ..., q _{i +1} genom konstruktion, är de ortogonala mot q _{i +2} , ..., q _n ,

Det har vi då

$H_{n}={\begin{bmatrix}h_{1,1}&h_{1,2}&h_{1,3}&\cdots &h_{1,n}\\h_{2,1}&h_ {2,2}&h_{2,3}&\cdots &h_{2,n}\\0&h_{3,2}&h_{3,3}&\cdots &h_{3,n}\\\vdots &\ddots &\ddots &\ddots &\vdots \\0&\cdots &0&h_{n,n-1}&h_{n,n}\end{bmatrix}}.$

Matrisen H _n kan ses som A i delrummet ${\mathcal {K}}_{n}$ med Arnoldi-vektorerna som ortogonal bas; A projiceras ortogonalt på ${\mathcal {K}}_{n}$ . Matrisen Hn kan karakteriseras av följande optimalitetsvillkor _. Det karakteristiska polynomet för H _n minimerar || p ( A ) q ₁ || ₂ bland alla moniska polynom av grad n . Detta optimalitetsproblem har en unik lösning om och bara om Arnoldi-iterationen inte går sönder.

Relationen mellan Q- matriserna i efterföljande iterationer ges av

$AQ_{n}=Q_{n+1}{\tilde {H}}_{n}$

var

${\tilde {H}}_{n}={\begin{bmatrix}h_{ 1,1}&h_{1,2}&h_{1,3}&\cdots &h_{1,n}\\h_{2,1}&h_{2,2}&h_{2,3}&\cdots &h_{ 2,n}\\0&h_{3,2}&h_{3,3}&\cdots &h_{3,n}\\\vdots &\ddots &\ddots &\ddots &\vdots \\\vdots &&0&h_{n ,n-1}&h_{n,n}\\0&\cdots &\cdots &0&h_{n+1,n}\end{bmatrix}}$

är en ( n +1)-för -n _- matris bildad genom att lägga till en extra rad till Hn .

Att hitta egenvärden med Arnoldi-iterationen

Idén med Arnoldi-iterationen som en egenvärdesalgoritm är att beräkna egenvärdena i Krylov-underrummet. Egenvärdena för H _n kallas Ritz - egenvärden . Eftersom Hn är en Hessenberg-matris av blygsam storlek, kan dess egenvärden beräknas effektivt, till exempel med QR _- algoritmen , eller något relaterad, Francis's algoritm. Även Francis' algoritm i sig kan anses vara relaterad till kraftiterationer, som arbetar på kapslade Krylov-underrymden. Faktum är att den mest grundläggande formen av Franciskus algoritm tycks vara att välja b för att vara lika med Ae ₁ och att sträcka n till hela dimensionen av A . Förbättrade versioner inkluderar ett eller flera skift, och högre effekt av A kan tillämpas i ett enda steg.

Detta är ett exempel på Rayleigh-Ritz-metoden .

Det observeras ofta i praktiken att några av Ritz-egenvärdena konvergerar till egenvärden för A . Eftersom H _n är n -by- n , har den högst n egenvärden, och inte alla egenvärden för A kan approximeras. Typiskt konvergerar Ritz-egenvärdena till de största egenvärdena för A . För att få de minsta egenvärdena för A ska inversen (operationen) av A användas istället. Detta kan relateras till karakteriseringen av H _n som matrisen vars karakteristiska polynom minimerar || p ( A ) q ₁ || på följande sätt. Ett bra sätt att få p ( A ) liten är att välja polynomet p så att p ( x ) är liten när x är ett egenvärde till A . Därför kommer nollorna för p (och därmed Ritz-egenvärdena) att vara nära egenvärdena för A .

Men detaljerna är inte helt klarlagda ännu. Detta är i motsats till fallet där A är hermitisk . I den situationen blir Arnoldi-iterationen Lanczos-iterationen , för vilken teorin är mer komplett.

Arnoldi iteration som visar konvergens av Ritz-värden (röd) till egenvärdena (svart) för en 400x400-matris, sammansatt av enhetliga slumpmässiga värden på domänen [-0,5 +0,5]

Implicit omstartad Arnoldi-metoden (IRAM)

På grund av praktisk lagringsövervägande startar vanliga implementeringar av Arnoldi-metoder vanligtvis om efter ett antal iterationer. En stor innovation vid omstart berodde på Lehoucq och Sorensen som föreslog den implicit omstartade Arnoldi-metoden. De implementerade också algoritmen i ett fritt tillgängligt mjukvarupaket som heter ARPACK . Detta har stimulerat ett antal andra varianter inklusive Implicitly Restarted Lanczos-metoden. Det påverkade också hur andra omstartade metoder analyseras. Teoretiska resultat har visat att konvergensen förbättras med en ökning av Krylovs delrumsdimension n . Ett a-priori-värde på n som skulle leda till optimal konvergens är emellertid inte känt. Nyligen har en dynamisk omkopplingsstrategi föreslagits som fluktuerar dimensionen n före varje omstart och således leder till acceleration i konvergenshastigheten.

Se även

Den generaliserade minimala residualmetoden (GMRES) är en metod för att lösa Ax = b baserad på Arnoldi iteration.

• WE Arnoldi, "Principen för minimerade iterationer i lösningen av matrisegenvärdesproblemet," Quarterly of Applied Mathematics , volym 9, sidorna 17–29, 1951.
•   Yousef Saad , Numerical Methods for Large Eigenvalue Problems , Manchester University Press, 1992. ISBN 0-7190-3386-1 .
•   Lloyd N. Trefethen och David Bau, III, Numerisk linjär algebra , Society for Industrial and Applied Mathematics, 1997. ISBN 0-89871-361-7 .
•   Jaschke, Leonhard: Förkonditionerade Arnoldi-metoder för system av icke-linjära ekvationer . (2004). ISBN 2-84976-001-3
• Implementering: Matlab kommer med ARPACK inbyggt. Både lagrade och implicita matriser kan analyseras genom eigs() -funktionen.