Mehrgitterverfahren - de.LinkFang.org

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.

Inhaltsverzeichnis

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 {\displaystyle A_{l}x=b_{l}} mit regulärer quadratischer Matrix {\displaystyle A_{l}\in \mathbb {R} ^{n\times n}} gegeben. Auf die Näherung {\displaystyle x_{l}^{k}} auf einem feinen Gitter wird dann als erstes ein Glätter {\displaystyle 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 {\displaystyle r_{l}=b_{l}-A_{l}S_{l}x_{l}^{k}} wird auf das nächstgröbere Gitter restringiert: {\displaystyle 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 {\displaystyle A_{l-1}e=r_{l-1}} für den Fehler e ein Problem mit ähnlicher Struktur wie das Ursprungsproblem, allerdings mit kleinerer Dimension.

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:

{\displaystyle MG(x_{l},b_{l},l)}
if {\displaystyle (l=0)}, {\displaystyle x_{l}=A_{l}^{-1}b_{l}} (Löse exakt auf gröbstem Gitter)
else
{\displaystyle x_{l}=S_{l}^{\nu _{1}}(x_{l},b_{l})} (Vorglättung)
{\displaystyle r_{l-1}=R_{l-1,l}(b_{l}-A_{l}x_{l})} (Restriktion)
{\displaystyle v_{l-1}=0}
Für {\displaystyle (j=0;\;j<\gamma ;\;j++)} {\displaystyle MG(v_{l-1},r_{l-1},l-1)} (Berechnung der Grobgitterkorrektur)
{\displaystyle x_{l}=x_{l}+P_{l,l-1}v_{l-1}} (Prolongation der Grobgitterkorrektur)
{\displaystyle 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 {\displaystyle e=x^{k}-x^{*}} der Näherungslösung x^k über die Residuumsgleichung {\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 {\displaystyle L(u)=f} lässt sich das obige Vorgehen nicht direkt übertragen, da die Residuumsgleichung {\displaystyle L(e)=r} gar nicht lösbar sein muss. Deswegen löst man da auf dem groben Gitter stattdessen {\displaystyle L(u+e)=L(u)+r}, was im linearen Fall äquivalent wäre. Es ergibt sich dann

{\displaystyle MG({\tilde {u}}_{l},u_{l},f_{l},l)}
if {\displaystyle (l=0)}, {\displaystyle u_{l}=L_{l}^{-1}f_{l}}
else
{\displaystyle u_{l}=S_{l}^{\nu _{1}}(u_{l},f_{l})}
{\displaystyle r_{l}=f_{l}-L_{l}u_{l}}
Wähle {\displaystyle {\tilde {u}}_{l-1}} und {\displaystyle s_{l-1}}
{\displaystyle f_{l-1}=L_{l-1}({\tilde {u}}_{l-1})+s_{l-1}R_{l-1,l}r_{l}}
Für {\displaystyle (j=0;\;j<\gamma ;\;j++)} {\displaystyle MG({\tilde {u}}_{l-1},u_{l-1},f_{l-1},l-1)}
{\displaystyle u_{l}=u_{l}+(1/s_{l-1})P_{l-1,l}(u_{l-1}-{\tilde {u}}_{l-1})}
{\displaystyle u_{l}=S_{l}^{\nu _{2}}(u_{l},f_{l})}
end if
End

{\displaystyle {\tilde {u}}_{l}} beschreibt dabei eine Approximation an die Lösung und {\displaystyle 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.

Geschichte


Die frühesten Arbeiten zu Mehrgitterverfahren stammen von den sowjetischen Mathematikern Radi Petrowitsch Fedorenko[1] 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


Weblinks


Einzelnachweise


  1. Fedorenko On the history of the Multigrid method



Kategorien: Numerische Mathematik



Quelle: Wikipedia - https://de.wikipedia.org/wiki/Mehrgitterverfahren (Autoren [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Veränderungen: Alle Bilder und die meisten Designelemente, die mit ihnen in Verbindung stehen, wurden entfernt. Icons wurden teilweise durch FontAwesome-Icons ersetzt. Einige Vorlagen wurden entfernt (wie „Lesenswerter Artikel“, „Exzellenter Artikel“) oder umgeschrieben. CSS-Klassen wurden zum Großteil entfernt oder vereinheitlicht.
Wikipedia spezifische Links, die nicht zu Artikeln oder Kategorien führen (wie „Redlink“, „Bearbeiten-Links“, „Portal-Links“) wurden entfernt. Alle externen Links haben ein zusätzliches FontAwesome Icon erhalten. Neben weiteren kleinen Designanpassungen wurden Media-Container, Karten, Navigationsboxen, gesprochene Versionen & Geo-Mikroformate entfernt.


Stand der Informationen: 21.10.2019 10:01:26 CEST - Wichtiger Hinweis Da die gegebenen Inhalte zum angegebenen Zeitpunkt maschinell von Wikipedia übernommen wurden, war und ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.org nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein oder Fehler in der Darstellung vorliegen, bitten wir Sie darum uns per zu kontaktieren: E-Mail.
Beachten Sie auch : Impressum & Datenschutzerklärung.