Mehrgitterverfahren
Mehrgitterverfahren bilden eine
Klasse von
Algorithmen und Methoden zur effizienten Lösung von Gleichungssystemen mehrdimensionaler Probleme in der
numerischen Mathematik.
Partielle Differentialgleichungen wie die Poisson-Gleichung können damit mit einem Rechenaufwand von der Ordnung
O(N) mit
N der Anzahl der Unbekannten gelöst werden.
Mehrgitterverfahren sind also "optimal".
Die Grundidee ist dabei, dass man die Auflösung des Gitters in einer Hierarchie von Ebenen immer weiter vergröbert und somit auch die Problemgröße reduziert. Auf den groben Gittern werden aber jeweils nur Korrekturen der Fehler auf den feineren Gitter mittels Glättern (Gauß-Seidel oder Jakobi Relaxation) angenähert und anschließend aufaddiert. Hochfrequente Fehleranteile werden durch diese Prozedur schnell gedämpft. Der Fehler wird also sehr schnell glatt. Niederfrequente Fehleranteile auf den feinen Gittern werden dabei zu hochfrequenten Fehlernanteilen auf gröberen Gittern, die die Glätter schnell reduzieren können.
Der Einsatz der groben Gitter beschleunigt die Informationsausbreitung über dem Diskretisierungsgebiet. Die
Kombination von Grobgitterkorrektur und Glätter ergibt eine schnelle, maschenweitenunabhängige Konvergenzrate.
Ein normaler Mehrgitterzyklus (oder
V-Zyklus) beginnt auf dem feinsten Gitter mit einer Näherung der Lösung. Mit dieser meist falschen Lösung wird die Residuumsgleichung aufgestellt. Dieses neue Gleichungssystem wird durch eine Restriktion auf die
Dimension des nächstgröberen Gitters überführt. Dann wird dieses Verfahren rekursiv bis zur gröbsten Mehrgitter
Ebene durchgeführt, wo das Gleichungssystem meist direkt gelöst wird. Beim Zurückkehren werden die Korrekturen durch Prolongation (meist
Interpolation) auf die feinere
Ebene überführt und dann zur dortigen Näherung aufaddiert. Auf dem feinsten Gitter angelangt ist ein V-Zyklus
abgeschlossen.
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.
Geschichte
Die frühesten Arbeiten zu
Mehrgitterverfahren stammen von den sowjetischen Mathematikern Fedorenko und Bakhvalov aus den frühen 60er 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.
Trotz ihrer Optimalität sind Mehrgitterverfahren im industriellen Sektor momentan nur spärlich verbreitet. Gründe hierfür sind:
- Die Verfahren sind noch "relativ" jung.
- Mehrgitterverfahren sind schwierig zu implementieren. Grobe Gitter, Prolongations- und Restriktionsoperatoren müssen sorgfältig abgestimmt werden auf
- Aufgrund ihrer Natur (Zugriff auf alternierend feinere und gröbere Gitter) führen Mehrgitterverfahren
- zu vielen Cache-Misses (bei lexikographischer Knotennummerierung),
- und sind schwer zu parallelisieren.
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.
Für Probleme mit großen Skalenunterschieden (beispielsweise turbulente Strömungen: Wirbel im Bereich von
μm, 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. Ein Beispiel für ein solches Verfahren ist die heterogene Mehrskalenmethode (engl.: The Heterogeneous Multiscale Method), entwickelt von Weinan E, Bjorn Enquist und anderen.
Jede mathematische Formel in einem Buch halbiert die Verkaufszahl dieses Buches.
Stephen Hawking
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld
• Dοrfplatz 25 • 17237 Blankеnsее
• Tel.: 01734332309 (Vodafone/D2) •
Email: cο@maτhepedιa.dе