Czy są jakieś heurystyki dla optymalizacji metody sukcesywnej nadmiernej relaksacji (SOR)?

Jak rozumiem, sukcesywne nad relaksacją działa poprzez wybranie parametru i użycie liniowej kombinacji (quasi) iteracji Gaussa-Seidela i wartości w poprzednim kroku czasu ... $0\leq\omega\leq2$

${u}^{k+1} = (\omega){u_{gs}}^{k+1} + (1-\omega)u^{k}$

Podaję „quasi”, ponieważ zawiera najnowsze informacje zaktualizowane zgodnie z tą zasadą, w dowolnym momencie. (zauważ, że dla jest to dokładnie gauss-seidel). ${u_{gs}}^{k+1}$$\omega=1$

W każdym razie przeczytałem, że przy optymalnym wyborze dla (takiego, że iteracja zbiega się szybciej niż jakikolwiek inny) zbliża się 2 do problemu poissona, gdy rozdzielczość przestrzenna zbliża się do zera. Czy istnieje podobny trend w przypadku innych symetrycznych, dominujących po przekątnej problemów? Czy istnieje sposób optymalnego wyboru omegi bez osadzania jej w adaptacyjnym schemacie optymalizacji? Czy istnieją inne heurystyki dla innych rodzajów problemów? Jakie problemy byłyby zbyt niskie ( ) optymalne?$\omega$$\omega<1$

Tłumione Jacobi

Załóżmy, że macierz ma przekątnej . Jeśli widmo leży w przedziale dodatniej osi rzeczywistej, to macierz iteracji Jacobiego ze współczynnikiem tłumienia ma widmo w zakresie , więc minimalizacja promienia widmowego za pomocą daje współczynnik zbieżności Jeśli , to ten współczynnik konwergencji jest bardzo słaby, zgodnie z oczekiwaniami. Zauważ, że stosunkowo łatwo jest oszacować$A$$D$$D^{-1}A$$[a,b]$$\omega$

$$B_\text{Jacobi} = I - \omega D^{-1} A$$ $[1 - \omega b,1 - \omega a]$ $$\omega_{\text{opt}} = \frac 2 {a + b}$$ $$\rho_\text{opt} = 1 - \frac{2a}{a+b} = \frac{b-a}{a+b}.$$ $a \ll b$$b$stosując metodę Kryłowa, ale dość drogie oszacować .$a$

Sukcesywna nadmierna relaksacja (SOR)

Young (1950), okazały się optymalnego wyniku dla SOR stosowane do matryc z tak zwanego WŁASNOŚCI , spójnej kolejności , a dodatnie rzeczywiste wartości własne . Biorąc pod uwagę maksymalną wartość własną niehamowanej macierzy iteracji Jacobi ( jest zagwarantowane przez założenia w tym przypadku), optymalnym współczynnikiem tłumienia dla SOR jest co daje współczynnik konwergencji Zauważ, że zbliża się do 2, gdy .$D^{-1}A$$\mu_\max$$I - D^{-1} A$$\mu_\max < 1$

$$\omega_\text{opt} = 1 + \left( \frac{\mu_\max}{1 + \sqrt{1 - \mu_\max^2}} \right)^2$$ $$\rho_\text{opt} = \omega_\text{opt} - 1.$$ $\omega_\text{opt}$$\mu_\max \to 1$

Komentarze

To już nie jest 1950 rok i naprawdę nie ma sensu używać stacjonarnych metod iteracyjnych jako solverów. Zamiast tego używamy ich jako wygładzaczy dla wielu sieci. W tym kontekście dbamy tylko o górną granicę spektrum. Optymalizacja współczynnika relaksacji w SOR powoduje, że SOR wytwarza bardzo małe tłumienie wysokich częstotliwości (w zamian za lepszą zbieżność na niższych częstotliwościach), dlatego zwykle lepiej jest używać standardowego Gaussa-Seidela, odpowiadającego w SOR. W przypadku problemów niesymetrycznych i problemów o bardzo zmiennych współczynnikach, słabo zrelaksowany SOR ( ) może mieć lepsze właściwości tłumiące.$\omega = 1$$\omega <1$

Szacowanie obu wartości własnych jest drogie, ale największą wartość własną można szybko oszacować za pomocą kilku iteracji Kryłowa. Wygładzacze wielomianowe (wstępnie przygotowane z Jacobi) są bardziej skuteczne niż wielokrotne iteracje tłumionego Jacobi i są łatwiejsze do skonfigurowania, więc powinny być preferowane. Zobacz tę odpowiedź, aby uzyskać więcej informacji na temat wygładzaczy wielomianowych.$D^{-1}A$

Czasami twierdzi się, że SOR nie powinien być stosowany jako warunek wstępny dla metod Kryłowa, takich jak GMRES. Wynika to z obserwacji, że optymalny parametr relaksacji powinien umieścić wszystkie wartości własne macierzy iteracji na kole wyśrodkowany na początku. Spektrum kondycjonowanego operatora

$$B_\text{SOR} = 1 - \left(\frac 1 \omega D + L\right)^{-1} A$$ $(\frac 1 \omega D + L)^{-1} A$ma wartości własne na kole o tym samym promieniu, ale wyśrodkowane na 1. W przypadku słabo uwarunkowanych operatorów promień koła jest dość bliski 1, więc GMRES widzi wartości własne bliskie źródłu pod pewnym kątem, co zwykle nie jest dobre dla konwergencji. W praktyce GMRES może racjonalnie zbiegać się po przygotowaniu z SOR, szczególnie w przypadku problemów, które są już dość dobrze uwarunkowane, ale inne warunki wstępne są często bardziej skuteczne.