Die Hauptidee hinter Multigrid ist die Projektion. Ich versuche wie folgt darüber nachzudenken:
Angenommen, ich möchte eine PDE sehr genau lösen, und diskretisiere die Domäne (sagen wir, mit der Finite-Differenzen-Methode) auf einem sehr feinen Raster mit vielen, vielen Punkten. Am Ende stelle ich mein Gleichungssystem auf und bin bereit, es zu lösen. Ich versuche, meinen bevorzugten iterativen Löser zu verwenden (jacobi, gauss seidel, konjugierter Gradient usw.). Ich warte länger als einen Tag und stelle fest, dass mein Computer immer noch versucht, die Antwort zu berechnen !!!
Der Grund, warum diese iterativen Methoden nicht schnell funktionieren, liegt (normalerweise) darin, dass beim Erstellen eines großen Gleichungssystems wie dieses die Matrix selbst Eigenwerte aufweist, die extrem nahe bei 1 liegen. Warum ist das wichtig? Weil die Konvergenzrate vieler iterativer Methoden umgekehrt zum größten Eigenwert in Beziehung steht (siehe Christian Clasons Link zu Briggs Multigrid Tutorial-Folien, Teil 1, Seite 27). Je näher der größte Eigenwert an 1 liegt, desto langsamer ist die iterative Methode. (Hinweis: Dies vereinfacht die Dinge ein wenig, trägt aber dazu bei, die Notwendigkeit von Multigrid zu motivieren.)
Offensichtlich ist es immer schneller, das Problem zu lösen, wenn es weniger Unbekannte gibt (dh auf einem groben Gitter mit weniger Gitterpunkten). Noch wichtiger ist jedoch, dass die Lösung (oder Näherungslösung) in einem gröberen Raster ein guter Ausgangspunkt ist, um das Problem in einem feineren Raster zu lösen. Dies ist die Schlüsselidee hinter den meisten (wenn nicht allen) Multigrid-Methoden. Warum ist das so? Intuitiv ist es sinnvoll, aber es gibt eine mathematisch strenge Methode, um dies zu rechtfertigen.
Betrachten wir die Fourier-Modi des Fehlers in einer iterativen Methode (aus Gründen der Argumentation sagen wir jacobi oder gauss seidel), die auf das ursprüngliche Problem des feinen Gitters angewendet wird. Wir würden sehen, dass in den ersten paar Iterationen die meisten hochfrequenten (stark oszillierenden) Fehler beseitigt sind! Das ist großartig, aber es gibt einen niederfrequenten (weniger schwingenden) Fehler, der immer noch auftritt und nicht schnell verschwindet. Tatsächlich verhindert ein Niederfrequenzfehler, dass eine standardmäßige iterative Methode schnell konvergiert.
Wenn wir das Problem in einem gröberen Raster lösen (z. B. durch eine iterative Methode wie Jacobi oder Gauß-Seidel), können wir Fehler mit niedrigeren Frequenzen wesentlich schneller (dh in weniger Iterationen) entfernen als in einem feinen Raster . Wenn wir also das Problem eines groben Gitters lösen, haben wir eine Lösung, deren Fehler bei niedrigeren Frequenzen erheblich verringert wurden. Somit wäre es als Ausgangspunkt für eine iterative Methode auf dem feineren Gitter nützlich.
Es gibt zwar verschiedene Multigrid-Methoden, die meisten funktionieren jedoch mit einer der folgenden Variationen:
- Beginnen Sie mit dem Problem des feinen Gitters
- Projekt auf ein grobes Gitter (auch als Einschränkung bezeichnet )
- Approximation der Lösung im Grobraster (mit einem anderen Löser)
- Projizieren Sie die Grobgitterlösung auf das feinere Gitter (auch als Verlängerung bezeichnet ).
- Lösen Sie das Problem des feinen Gitters mithilfe der Projektion von 4. als erste Vermutung mit einer iterativen Methode.
Der schwierigste Teil der Multigrid-Methode sind für mich die Projektionen zwischen Gittern. Die von @ChristianClason vorgeschlagenen Briggs-Tutorials behandeln dieses Thema viel besser als ich.
Diese Site ist möglicherweise kein guter Ort, um eine detaillierte Erklärung mit Pseudocode anzufordern (wie in den FAQ angegeben : "Wenn Sie sich ein ganzes Buch vorstellen können, das Ihre Frage beantwortet, fragen Sie zu viel.") Beginnen Sie mit einem der klassischen Bücher zu diesem Thema (siehe unten) und stellen Sie spezifische Fragen zu konkreten Details, mit denen Sie Probleme haben.
Briggs, Multigrid Tutorial , SIAM, 2000 (Sie können hier und hier Folien herunterladen ) Dies ist eine gelegentliche Quelle, die eine sanfte Einführung in die Multigrid-Prinzipien bietet, hauptsächlich für elliptische Probleme.
Brandt, Multigrid Techniques , überarbeitete Ausgabe, SIAM 2011 , (oder laden Sie das PDF herunter ). Dies ist eine großartige Entwicklung der Multigrid-Philosophie und der Multiskalen-Modellierung und bietet gute Chancen, Ihre Denkweise über implizite Löser grundlegend zu ändern. Achi Brandts Website enthält viele weitere Referenzen, einschließlich seines 2000 Review of Multiscale Scientific Computation .
Trottenberg, Oosterlee und Schueller, Multigrid , Academic Press, 2001 Dies hat mehr Beispiele als Brandt hervorgebracht, darunter viele Experimente und Details zu bestimmten Methoden, insbesondere im Zusammenhang mit der Fluiddynamik.
Hackbusch, Multigrid Methods and Applications , Springer, 1985 Dies liefert eine rigorose Konvergenztheorie, einschließlich "Multigrid der zweiten Art" für Fredholm-Integraloperatoren.
quelle
Ein weiterer Klassiker:
Beispielcodes finden Sie bei MGNet
quelle