Mehrgitterverfahren

Beschreibung

Die Grundidee ist, den unbekannten Fehler zu einer gegebenen Näherung auf einem feinen Gitter, auf einem gröberen Gitter zu approximieren. Da auf dem gröberen Gitter weniger Unbekannte gegeben sind, ist dies günstig möglich. Rekursive Anwendung auf einer Hierarchie von gröber werdenden Gittern liefert eine Mehrgitter-Struktur.

Der Einsatz der groben Gitter beschleunigt die Informationsausbreitung über dem Diskretisierungsgebiet. Die Kombination von Grobgitterkorrektur und Glätter ergibt eine schnelle, maschenweitenunabhängige Konvergenzrate.

Lineare Gleichungssysteme

Zunächst sei auf jedem Gitter ein lineares Gleichungssystem A_l x = b_l mit regulärer quadratischer Matrix gegeben. Auf die Näherung x^k_l auf einem feinen Gitter wird dann als erstes ein Glätter S_l angewandt, der hochfrequente Fehleranteile dämpft, wodurch ein glatter Fehler entsteht. Was ein sinnvoller Glätter ist, hängt davon ab welche partielle Differentialgleichung gelöst werden soll. Für viele sind Gauß-Seidel- oder Jacobi-Relaxation geeignet. Das zugehörige Residuum r_l = b_l - A_l S_l x^k_l wird auf das nächstgröbere Gitter restringiert: r_l-1 = Rr_l . Die Restriktion R ist dabei eine Abbildung vom feinen auf das nächstgröbere Gitter. Da niederfrequente Fehleranteile auf feinen Gittern hochfrequenten Fehleranteilen auf gröberen Gittern entsprechen, ergibt sich mit der Residuumsgleichung A_l-1 e = r_l-1 für den Fehler e ein Problem mit ähnlicher Struktur wie das Ursprungsproblem, allerdings mit kleinerer Dimension.

MG(x_l , b_l , l)

if (l = 0), x_l = A^-1_l b_l (Löse exakt auf gröbstem Gitter)

else

(Vorglättung)

r_l-1 = R_{l-1, l} (b_l - A_l x_l ) (Restriktion)

v_l-1 = 0

Für MG(v_l-1 , r_l-1 , l-1) (Berechnung der Grobgitterkorrektur)

x_l = x_l + P_{l, l-1} v_l-1 (Prolongation der Grobgitterkorrektur)

(Nachglättung)

end if

End

Dies funktioniert bei einem linearen Problem Ax = b mit Lösung x^* , da dann der Fehler e = x^k - x^* der Näherungslösung x^k über die Residuumsgleichung Ae = r = Ax^k - b berechnet werden kann.

Mehrgitterverfahren können die Norm des Fehlers für das Poisson-Problem in einem V-Zyklus um mehr als den Faktor 10 reduzieren, sind hier also äußerst effektiv.

Full Approximation Scheme

Auf ein nichtlineares Problem L(u) = f lässt sich das obige Vorgehen nicht direkt übertragen, da die Residuumsgleichung L(e) = r gar nicht lösbar sein muss. Deswegen löst man da auf dem groben Gitter statt dessen L(u + e) = L(u) + r, was im linearen Fall äquivalent wäre. Es ergibt sich dann

if (l = 0), u_l = L^-1_l f_l

else

r_l = f_l - L_l u_l

Wähle und s_l-1

Für

end if

End

beschreibt dabei eine Approximation an die Lösung und s_l wird so klein gewählt, dass das entsprechende nichtlineare Gleichungssystem lösbar ist. s = 1 entspricht dem Full Approximation Scheme (FAS) von Achi Brandt (1977). Eine Variante dieses Verfahrens wird in der numerischen Strömungsmechanik eingesetzt.

Copyright- und Lizenzinformationen: Diese Seite basiert auf dem Artikel Mehrgitterverfahren aus der freien Enzyklοpädιe Wιkιpedιa und steht unter der Lizenz Creative Commons CC-BY-SA 3.0 Unported (Kurzfassung). Liste der Autoren

Anbieterkennzeichnung