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$

linear-algebra optimization iterative-method

— Paweł
źródło

Nie do końca twoje pytanie, ale patrz Salakhutdinov i Roweis, Adaptive Overrelaxed Bound Optimization Methods 2003, 8 str. ( Przyspieszenia adaptacyjne mają wysoki huk na złotówkę, ale nie można ich analizować, więc nie na temat tutaj.)

— den

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_{Jacobi} = I - ω D^{- 1} A

$B_\text{Jacobi} = I - \omega D^{-1} A$

[1 - ω b, 1 - ω a]

$[1 - \omega b,1 - \omega a]$

ω_{opt} = \frac{2}{a + b}

$\omega_{\text{opt}} = \frac 2 {a + b}$

ρ_{opt} = 1 - \frac{2 a}{a + b} = \frac{b - a}{a + b} .

$\rho_\text{opt} = 1 - \frac{2a}{a+b} = \frac{b-a}{a+b}.$

a ≪ b

$a \ll b$

b

$b$ stosując metodę Kryłowa, ale dość drogie oszacować .

a

$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$

ω_{opt} = 1 + {(\frac{μ_{max}}{1 + \sqrt{1 - μ_{max}^{2}}})}^{2}

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

ρ_{opt} = ω_{opt} - 1.

$\rho_\text{opt} = \omega_\text{opt} - 1.$

ω_{opt}

$\omega_\text{opt}$

μ_{max} \to 1

$\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_{SOR} = 1 - {(\frac{1}{ω} D + L)}^{- 1} A

$B_\text{SOR} = 1 - \left(\frac 1 \omega D + L\right)^{-1} A$

(\frac{1}{ω} D + L)^{- 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.

— Jed Brown
źródło

Zgadzam się, że to już nie jest rok 1950: o) nie zgadzam się jednak, że nie ma sensu używać iteracyjnych rozwiązań solvera. Wydajność podręczników wieloskładnikowych możemy osiągnąć za pomocą stacjonarnego solvera iteracyjnego dla inżynieryjnego solvera aplikacyjnego opartego na rozwiązaniach nieliniowych o swobodnej powierzchni wysokiego rzędu (zarówno równania przepływu potencjalnego, jak i równania eulera). Wydajność była tak dobra, jak wstępnie przygotowana metoda podprzestrzeni krylov GMRES z osiągalną dokładnością (nasz najnowszy pub znajduje się tutaj onlinelibrary.wiley.com/doi/10.1002/fld.2675/abstract służący jako dowód koncepcji).

— Allan P. Engsig-Karup

Używasz Gaussa-Seidla jako płynniejszej dla wielosieciowej (do której należą metody takie jak SOR). Jeśli multigrid działa dobrze, zewnętrzna metoda Kryłowa również nie jest konieczna (chociaż twoje opracowanie nie pokazuje tych porównań). Gdy tylko multigrid zaczyna tracić efektywność (np. Więcej niż 5 iteracji, aby osiągnąć błąd dyskretyzacji), zwykle warto owijać metodę Kryłowa wokół cyklu multigrid.

— Jed Brown

Cała metoda jest p-multigrid z wygładzaniem typu GS, jednak kompletną metodę można zapisać jako stacjonarną metodę iteracyjną, ponieważ wszystkie operatory są stałe. Możesz go zobaczyć jako wstępnie kondycjonowaną metodę Richardsona, a M - kondycjoner zbudowany z metody wielosiatkowej. Analiza została wykonana, ale nie została jeszcze opublikowana. W rzeczywistości praca ta poszła w innym kierunku, który proponujecie. Metodę krylowa w tej pracy (GMRES) odrzucono, a następnie przekształcono ją w wielopoziomową metodę wyższego rzędu, ponieważ stwierdziliśmy, że była ona równie wydajna (i przy zmniejszonych wymaganiach pamięci).

— Allan P. Engsig-Karup

Zastosowanie - i -multigrid jest oczywiście niezależne od tego, czy na zewnątrz stosowana jest metoda Kryłowa. Względne koszty różnych operacji są oczywiście różne dla procesorów graficznych w porównaniu do procesorów, a implementacje są zmienne. Wstępnie przygotowany Richardson to tylko metoda korekcji wad. Podobnie są metody nieliniowe Newtona i Picarda (jeśli są zapisane jako takie). Inne metody nieliniowe (NGMRES, BFGS itp.) Również wykorzystują historię i mogą być lepsze w zależności od względnej siły nieliniowości.

p

$p$

h p

$hp$

— Jed Brown

Należy zauważyć, że w wygładzaczach wielosieciowych czasem lepiej jest (jeśli pozwala na to architektura), aby multipleksowanie sprzężeń wysokiego / niskiego rzędu było zwielokrotnione. To także rozszerza formułę „wstępnie kondycjonowanego Richardsona”. (W zeszłym tygodniu rozmawiałem na konferencji z facetem, który chciał postrzegać zasadniczo wszystkie metody jako warunkowo przygotowane Richardson z iteracją zagnieżdżoną, co nie uważam za szczególnie korzystne w porównaniu z innymi stwierdzeniami dotyczącymi składu solvera. Nie wiem, czy to jest istotne dla ciebie, ale twoje uwagi przypomniały mi o dyskusji).

— Jed Brown