iteracja Arnoldiego

W numerycznej algebrze liniowej iteracja Arnoldiego jest algorytmem wartości własnej i ważnym przykładem metody iteracyjnej . Arnoldi znajduje przybliżenie wartości własnych i wektorów własnych macierzy ogólnych (prawdopodobnie niehermitowskich ) konstruując bazę ortonormalną podprzestrzeni Kryłowa , co czyni ją szczególnie przydatną w przypadku dużych, rzadkich macierzy .

należy do klasy algorytmów algebry liniowej, które dają częściowy wynik po niewielkiej liczbie iteracji, w przeciwieństwie do tzw . Częściowym wynikiem w tym przypadku jest kilka pierwszych wektorów bazy, którą buduje algorytm.

W zastosowaniu do macierzy hermitowskich sprowadza się do algorytmu Lanczosa . Iteracja Arnoldiego została wynaleziona przez WE Arnoldiego w 1951 roku.

Podprzestrzenie Kryłowa i iteracja potęgowa

Intuicyjną metodą znajdowania największej (w wartości bezwzględnej) wartości własnej danej Ab , ZA ² b , ^macierzy jest b , ... iteracja potęgowa : zaczynając od dowolnego wektora początkowego b , $3$ ZA normalizowanie wyniku po każdym zastosowaniu macierzy A .

Ta sekwencja zbiega się do wektora własnego odpowiadającego wartości własnej o największej wartości bezwzględnej ${\ Displaystyle \ lambda _ {1}}$ . Jednak wiele potencjalnie użytecznych ${\ Displaystyle A ^ {n-1} b}$ jest marnowanych przy użyciu tylko wyniku końcowego, ZA . Sugeruje to, że zamiast tego tworzymy tak zwaną macierz Kryłowa :

${\ Displaystyle K_ {n} = {\ rozpocząć {bmatrix} b & Ab & A ^ {2} b & \ cdots & A ^ {n-1} b \ koniec {bmatrix}}.}$

Kolumny tej macierzy nie są na ogół ortogonalne , ale możemy wyodrębnić bazę ortogonalną za pomocą metody takiej jak ortogonalizacja Grama-Schmidta . Otrzymany zestaw wektorów jest zatem ortogonalną bazą podprzestrzeni Kryłowa . $}$ } Możemy oczekiwać, że wektory tej podstawy będą obejmowały dobre przybliżenia wektorów własnych odpowiadających największym wartościom własnym, z tego samego powodu, dla którego $n-1} b}$ b ${$ dominujący wektor własny.

Iteracja Arnoldiego

Iteracja Arnoldiego wykorzystuje zmodyfikowany proces Grama-Schmidta do wytworzenia sekwencji wektorów ortonormalnych q ₁ , q ₂ , q ₃ , ..., zwanych wektorami Arnoldiego , tak że dla każdego n wektory q ₁ , ... , q _n obejmuje podprzestrzeń Kryłowa ${\ Displaystyle {\ mathcal {K}} _ {n}}$ . W sposób jawny algorytm jest następujący:

 
    
     
 Zacznij od dowolnego wektora  q  1  z normą 1. Powtórz dla  k  = 2, 3, ...  q  k  :=  A  q  k  −1  dla  j  od 1 do  k  − 1  h  j  ,  k  −1  :=  q  j  *  q  k  q  k  :=  q  k  - godz  jot  ,  k  -1  q  jot  godz  k  ,  k  -1  := ||  q  k  ||  q  k  :=  q  k  /  godz  k  ,  k  -1 

Pętla j rzutuje składową ${\ Displaystyle q_ {k}}$ w kierunkach ${\ Displaystyle q_ {1}, \ kropki, q_ {k-1}}$ . Zapewnia to ortogonalność wszystkich generowanych wektorów.

Algorytm załamuje się, gdy q _k jest wektorem zerowym. Dzieje się tak , gdy minimalny wielomian A ma stopień k . W większości zastosowań iteracji Arnoldiego, w tym algorytm wartości własnej poniżej i GMRES , algorytm osiągnął w tym momencie zbieżność.

Każdy krok pętli k zajmuje jeden iloczyn macierzowo-wektorowy i około 4 mk operacji zmiennoprzecinkowych.

W języku programowania Python ze wsparciem biblioteki NumPy :

   

    
    






    





      
      
      0
     
    0       
       
             
             
               
                  
          
             
              
          
              
       import  numpy  as  np  def  arnoldi_iteration  (  A  ,  b  ,  n  :  int  ):  """Oblicza podstawę podprzestrzeni (n + 1)-Krylowa A: przestrzeń  rozpięta przez {b, Ab, ..., A^ nb}  Argumenty  A: tablica m × m  b: wektor początkowy (długość m)  n: wymiar podprzestrzeni Kryłowa, musi być >= 1  Zwraca  Q: tablica mx (n + 1), kolumny są ortonormalną bazą  Kryłowa podprzestrzeń  h: (n + 1) xn tablica, A na podstawie Q. Jest to górny Hessenberg.  """  eps  =  1e-12  h  =  np  .  zera  ((  n  +  1  ,  n  ))  Q  =  np  .  zera  ((  A  .  shape  [  ],  n  +  1  ))  # Normalizuj wektor wejściowy  Q  [:,  ]  =  b  /  np  .  język  .  norma  (  b  ,  2  )  # Użyj go jako pierwszego wektora Kryłowa  dla  k  w  zakresie  (  1  ,  n  +  1  ):  v  =  np  .  kropka  (  A  ,  Q  [:,  k  -  1  ])  # Wygeneruj nowy kandydujący wektor  dla  j  w  zakresie  (  k  ):  # Odejmij rzuty na poprzednie wektory  h  [  j  ,  k  -  1  ]  =  np  .  kropka  (  Q  [:,  jot  ]  .  T  ,  v  )  v  =  v  -  godz  [  jot  ,  k  -  1  ]  *  Q  [:,  jot  ]  godz  [  k  ,  k  -  1  ]  =  np  .  język  .  norm  (  v  ,  2  )  if  h  [  k  ,  k  -  1  ]  >  eps  :  # Dodaj utworzony wektor do listy, chyba że  Q  [:,  k  ]  =  v  /  h  [  k  ,  k  -  1  ]  else  :  # Jeśli to się dzieje, przestań powtarzać.  zwróć  Q  ,  godz  zwróć  Q  ,  godz 

Własności iteracji Arnoldiego

Niech Q _n oznacza macierz m -by- n utworzoną z pierwszych n wektorów Arnoldiego q ₁ , q ₂ , ..., q _n , i niech H _n będzie macierzą (górnego Hessenberga ) utworzoną z liczb h _{j , k} obliczone przez algorytm:

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

Metoda ortogonalizacji musi być specjalnie dobrana tak, aby niższe składowe Arnoldiego/Krylowa zostały usunięte z wyższych wektorów Kryłowa. Za ${\ displaystyle Aq_ {i}}$ można wyrazić za pomocą konstrukcji q ₁ , ..., q _{ja +1} , są one prostopadłe do ja _{+2 ,} ..., q _n ,

Mamy wtedy

${\ Displaystyle H_ {n} = {\ rozpocząć {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{bmacierz}}.}$

Macierz H _n można postrzegać jako A w podprzestrzeni $z$ wektorami Arnoldiego jako podstawą A jest rzutowane prostopadle na ${\ displaystyle {\ mathcal {K}} _ {n}}$ . Macierz Hn można scharakteryzować następującym warunkiem optymalności _. Charakterystyczny wielomian H _n minimalizuje || p ( ZA ) q ₁ || ₂ spośród wszystkich wielomianów monicznych stopnia n . Ten problem optymalności ma unikalne rozwiązanie wtedy i tylko wtedy, gdy iteracja Arnoldiego się nie załamie.

Relacja między macierzami Q w kolejnych iteracjach jest dana przez

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

Gdzie

${\ Displaystyle {\ tylda {H}} _ {n} = {\ rozpocząć {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{bmacierz}}}$

jest macierzą ( n +1)-na- _n utworzoną przez dodanie dodatkowego wiersza do Hn .

Znajdowanie wartości własnych za pomocą iteracji Arnoldiego

Ideą iteracji Arnoldiego jako algorytmu wartości własnej jest obliczenie wartości własnych w podprzestrzeni Kryłowa. Wartości własne Hn nazywane są wartościami własnymi Ritza _. Ponieważ H _n jest macierzą Hessenberga o niewielkich rozmiarach, jej wartości własne można skutecznie obliczyć, na przykład za pomocą algorytmu QR lub nieco pokrewnego algorytmu Francisa. Również sam algorytm Francisa można uznać za związany z iteracjami mocy, działający na zagnieżdżonej podprzestrzeni Kryłowa. W rzeczywistości najbardziej podstawową formą algorytmu Francisa wydaje się być wybranie b równego Ae ₁ i rozszerzenie n do pełnego wymiaru A . Ulepszone wersje obejmują jedną lub więcej przesunięć, a wyższe potęgi A mogą być stosowane w jednym kroku.

To jest przykład metody Rayleigha-Ritza .

W praktyce często obserwuje się, że niektóre wartości własne Ritza zbiegają się z wartościami własnymi A . Ponieważ Hn jest n -na- n , ma co najwyżej n wartości własnych i nie wszystkie wartości własne A mogą być przybliżone _. Zazwyczaj wartości własne Ritza zbiegają się do największych wartości własnych A . Aby uzyskać najmniejsze wartości własne A , zamiast tego należy zastosować odwrotność (operację) A. Można to powiązać z charakterystyką H _n jako macierzy, której charakterystyczny wielomian minimalizuje || p ( ZA ) q ₁ || w następujący sposób. Dobrym sposobem na uzyskanie p ( A ) jest wybranie takiego wielomianu p , że p ( x ) jest małe zawsze , gdy x jest wartością własną A . Stąd zera p (a tym samym wartości własne Ritza) będą zbliżone do wartości własnych A .

Jednak szczegóły nie są jeszcze w pełni zrozumiałe. Kontrastuje to z przypadkiem, w którym A jest hermitowskie . W tej sytuacji iteracja Arnoldiego staje się iteracją Lanczosa , dla której teoria jest pełniejsza.

Iteracja Arnoldiego pokazująca zbieżność wartości Ritza (kolor czerwony) z wartościami własnymi (kolor czarny) macierzy 400x400, złożonej z jednolitych wartości losowych w dziedzinie [-0,5 +0,5]

Niejawnie zrestartowana metoda Arnoldiego (IRAM)

Ze względu na praktyczne rozważania dotyczące przechowywania, typowe implementacje metod Arnoldiego zwykle uruchamiają się ponownie po pewnej liczbie iteracji. Jedna z głównych innowacji w ponownym uruchamianiu była zasługą Lehoucqa i Sorensena, którzy zaproponowali metodę Arnoldiego z niejawnym ponownym uruchomieniem. Zaimplementowali również algorytm w ogólnodostępnym pakiecie oprogramowania o nazwie ARPACK . To zachęciło wiele innych odmian, w tym metodę Implicitly Restarted Lanczos. Wpłynęło to również na to, jak analizowane są inne ponownie uruchomione metody. Teoretyczne wyniki wykazały, że konwergencja poprawia się wraz ze wzrostem wymiaru podprzestrzeni Kryłowa n . Jednak a priori wartość n , która doprowadziłaby do optymalnej zbieżności, nie jest znana. Ostatnio zaproponowano dynamiczną strategię przełączania, która zmienia wymiar n przed każdym ponownym uruchomieniem, a tym samym prowadzi do przyspieszenia tempa konwergencji.

Zobacz też

Metoda uogólnionych minimalnych reszt (GMRES) jest metodą rozwiązywania Ax = b opartą na iteracji Arnoldiego.

• WE Arnoldi, „Zasada zminimalizowanych iteracji w rozwiązaniu problemu wartości własnej macierzy”, Quarterly of Applied Mathematics , tom 9, strony 17–29, 1951.
•   Yousef Saad , Metody numeryczne dla problemów z dużą wartością własną , Manchester University Press, 1992. ISBN 0-7190-3386-1 .
•   Lloyd N. Trefethen i David Bau, III, Numeryczna algebra liniowa , Towarzystwo Matematyki Przemysłowej i Stosowanej, 1997. ISBN 0-89871-361-7 .
•   Jaschke, Leonhard: Wstępnie uwarunkowane metody Arnoldiego dla układów równań nieliniowych . (2004). ISBN 2-84976-001-3
• Implementacja: Matlab ma wbudowany ARPACK. Zarówno zapisane, jak i ukryte macierze można analizować za pomocą eigs() .