Mehrgitterverfahren

Mehrgitterverfahren bilden in der numerischen Mathematik eine Klasse von effizienten Algorithmen zur näherungsweisen Lösung von Gleichungssystemen, die aus der Diskretisierung partieller Differentialgleichungen stammen. Elliptische Probleme wie die Poisson-Gleichung können damit bei $n$ Unbekannten mit einem Rechenaufwand von der Ordnung $O(n)$ gelöst werden. Die Konvergenzordnung ist dabei nicht von der Feinheit der Gitter abhängig, im Gegensatz zu den meisten anderen numerischen Verfahren, die mit kleiner werdender Diskretisierungsfeinheit langsamer werden. Mehrgitterverfahren sind in dieser Hinsicht „optimal“. Die wesentliche Alternative zu Mehrgitterverfahren sind vorkonditionierte Krylow-Unterraum-Verfahren.

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 $A_{l}\in \mathbb {R} ^{n\times n}$ gegeben. Auf die Näherung $x_{l}^{k}$ 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_{l}^{k}$ 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.

V-Zyklus

W-Zyklus

Dies wird rekursiv bis zum gröbsten Gitter wiederholt (V-Zyklus), wo das Gleichungssystem direkt gelöst werden kann. Der berechnete Fehler wird dann sukzessive mittels Prolongation P auf die feineren Gitter rückprolongiert und geglättet. Schließlich wird mit der Fehlerapproximation auf dem feinsten Gitter die ursprüngliche Näherung der Lösung korrigiert. Eine Iteration des Mehrgitter-Verfahrens sieht dann folgendermaßen aus:

$MG(x_{l},b_{l},l)$

if $(l=0)$, $x_{l}=A_{l}^{-1}b_{l}$ (Löse exakt auf gröbstem Gitter)

else

$x_{l}=S_{l}^{\nu _{1}}(x_{l},b_{l})$ (Vorglättung)

$r_{l-1}=R_{l-1,l}(b_{l}-A_{l}x_{l})$ (Restriktion)

$v_{l-1}=0$

Für $(j=0;\;j<\gamma ;\;j++)$ $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)

$x_{l}=S_{l}^{\nu _{2}}(x_{l},b_{l})$ (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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x^k} über die Residuumsgleichung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L(u)=f} lässt sich das obige Vorgehen nicht direkt übertragen, da die Residuumsgleichung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L(e)=r} gar nicht lösbar sein muss. Deswegen löst man da auf dem groben Gitter stattdessen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L(u+e) = L(u)+r} , was im linearen Fall äquivalent wäre. Es ergibt sich dann

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle MG(\tilde{u}_l,u_l, f_l, l)}

if Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (l=0)} , Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u_l = L_l^{-1}f_l}

else

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u_l = S_l^{\nu_1}(u_l,f_l)}

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r_l=f_l-L_lu_l}

Wähle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tilde{u}_{l-1}} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s_{l-1}}

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f_{l-1} = L_{l-1}(\tilde{u}_{l-1}) + s_{l-1}R_{l-1,l}r_l}

Für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (j=0; \; j<\gamma; \; j++)} Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle MG(\tilde{u}_{l-1},u_{l-1},f_{l-1},l-1)}

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u_l = u_l + (1/s_{l-1})P_{l-1,l}(u_{l-1}-\tilde{u}_{l-1})}

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u_l = S_l^{\nu_2}(u_l,f_l)}

end if

End

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tilde{u}_l} beschreibt dabei eine Approximation an die Lösung und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s_l} wird so klein gewählt, dass das entsprechende nichtlineare Gleichungssystem lösbar ist. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s=1} entspricht dem Full Approximation Scheme (FAS) von Achi Brandt (1977). Eine Variante dieses Verfahrens wird in der numerischen Strömungsmechanik eingesetzt.

Geschichte

Die frühesten Arbeiten zu Mehrgitterverfahren stammen von den sowjetischen Mathematikern Radi Petrowitsch Fedorenko und Nikolai Sergejewitsch Bachwalow (Bakhvalov) aus den frühen 1960er Jahren. Bekannt wurden sie im Wesentlichen durch die Arbeiten von Wolfgang Hackbusch in den späten 1970er Jahren, der auch wichtige Konvergenzresultate erzielte. Ein weiterer Mehrgitterpionier ist Achi Brandt: er behauptet, jede partielle Differentialgleichung sei durch Mehrgitterverfahren effizient und schnell lösbar. Brandt führte das FAS-Verfahren ein, was von Antony Jameson und anderen für den Bereich der numerischen Strömungsmechanik aufgegriffen wurde.

Verwandte Verfahren

Bei komplexen Geometrien erreichen Mehrgitterverfahren schnell ihre Grenzen. Als Alternative wurden algebraische Mehrgitterverfahren entwickelt, die rein auf Modifikationen der Gleichungssysteme beruhen und keine speziellen geometrischen Eigenschaften wie Änderungen der Gitterweite benutzen. Generell sind Multilevel-Verfahren von Mehrgitter inspiriert.

Für Probleme mit großen Skalenunterschieden (beispielsweise turbulenten Strömungen: Wirbel im Bereich von Mikrometern, normale Geometrien im Bereich von Metern) gibt es in jüngerer Zeit (etwa seit 1995) Ansätze, die physikalischen Vorgänge auf den verschiedenen Skalen durch verschiedene numerische Ansätze zu lösen. Dies wird auch als Mehrskalenansatz bezeichnet und ist mit dem Mehrgitterverfahren eng verwandt.

In der Signalverarbeitung gibt es die Gauß-Laplace-Pyramide für eine Mehrgittertechnik.

Literatur

• William L. Briggs, Van Emden Henson, and Steve F. McCormick, A Multigrid Tutorial, Second Edition, SIAM, 2000 (book home page), ISBN 0-89871-462-1
• Wolfgang Hackbusch: Multigrid Methods and Applications, Springer, 1985
• Pieter Wesseling: An Introduction to Multigrid Methods, Corrected Reprint. Philadelphia: R.T. Edwards, Inc., 2004. ISBN 1-930217-08-0
• Schwetlick, H. und Kretschmar, H.: Numerische Verfahren für Naturwissenschaftler und Ingenieure. Fachbuchverlag Leipzig, 1991, S. 354. 

Weblinks

• Frank Liebau: Mehrgitterverfahren
• T. Rung, L. Xue, J. Yan, M. Schatz, F. Thiele: Numerische Methoden der Thermo- und Fluiddynamik (Abschnitt Mehrgitterverfahren)