Gibt es Heuristiken zur Optimierung der Methode der sukzessiven Überentspannung (SOR)?

Nach meinem Verständnis funktioniert die sukzessive Relaxation durch Auswahl eines Parameters $0\leq\omega\leq2$ und Verwendung einer linearen Kombination aus einer (quasi) Gauß-Seidel-Iteration und dem Wert im vorherigen Zeitschritt ... das heißt

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

Ich sage 'quasi', weil ${u_{gs}}^{k+1}$ zu jedem Zeitpunkt die neuesten Informationen enthält, die gemäß dieser Regel aktualisiert wurden. (Beachten Sie, dass dies bei $\omega=1$ genau Gauß-Seidel ist).

Auf jeden Fall habe ich gelesen, dass sich bei optimaler Wahl für $\omega$ (so dass die Iteration schneller konvergiert als jede andere) 2 für das Poisson-Problem nähert, wenn sich die räumliche Auflösung Null nähert. Gibt es einen ähnlichen Trend für andere symmetrische, diagonal dominierende Probleme? Gibt es eine Möglichkeit, Omega optimal zu wählen, ohne es in ein adaptives Optimierungsschema einzubetten? Gibt es andere Heuristiken für andere Arten von Problemen? Welche Art von Problemen wäre eine Unterentspannung ( $\omega<1$ ) optimal?

Gedämpfte Jacobi

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

Aufeinanderfolgende Überentspannung (SOR)

$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}$nähert sich 2, wenn .$\mu_\max \to 1$

Bemerkungen

Es ist nicht mehr 1950 und es macht wirklich keinen Sinn, stationäre iterative Methoden als Löser zu verwenden. Stattdessen verwenden wir sie als Glätter für Multigrid. In diesem Zusammenhang möchten wir nur das obere Ende des Spektrums ansprechen. Durch die Optimierung des Relaxationsfaktors in SOR wird bei SOR nur eine sehr geringe Dämpfung hoher Frequenzen erzeugt (im Austausch für eine bessere Konvergenz bei niedrigeren Frequenzen). Daher ist es normalerweise besser, Standard-Gauß-Seidel zu verwenden, das in SOR . Bei unsymmetrischen Problemen und Problemen mit stark variablen Koeffizienten kann eine unterentspannte SOR ( ) bessere Dämpfungseigenschaften aufweisen.$\omega = 1$$\omega <1$

Das Schätzen beider Eigenwerte von ist teuer, aber der größte Eigenwert kann mit wenigen Krylov-Iterationen schnell geschätzt werden. Polynomglätter (mit Jacobi vorkonditioniert) sind effektiver als mehrere Iterationen von gedämpftem Jacobi und einfacher zu konfigurieren, daher sollten sie bevorzugt werden. In dieser Antwort finden Sie weitere Informationen zu Polynomglättern.$D^{-1}A$

Es wird manchmal behauptet, dass SOR nicht als Vorkonditionierer für Krylov-Methoden wie GMRES verwendet werden sollte. Dies ergibt sich aus der Beobachtung, dass der optimale Relaxationsparameter alle Eigenwerte der Iterationsmatrix auf einen Kreis setzen sollte zentriert am Ursprung. Das Spektrum des vorkonditionierten Operators

$$B_\text{SOR} = 1 - \left(\frac 1 \omega D + L\right)^{-1} A$$ $(\frac 1 \omega D + L)^{-1} A$hat Eigenwerte auf einem Kreis mit demselben Radius, ist jedoch auf 1 zentriert. Bei schlecht konditionierten Operatoren liegt der Radius des Kreises ziemlich nahe bei 1, sodass GMRES Eigenwerte in der Nähe des Ursprungs in einem Winkelbereich sieht, der normalerweise nicht gut ist für die Konvergenz. In der Praxis kann GMRES bei Vorkonditionierung mit SOR vernünftig konvergieren, insbesondere bei Problemen, die bereits ziemlich gut konditioniert sind, aber andere Vorkonditionierer sind häufig wirksamer.