Multigrid-Methode zur Lösung von PDE

15

Ich brauche eine einfache Erklärung der Multigrid-Methode oder Literatur dazu.

Ich kenne mich mit iterativen Methoden wie BiCGStab, CG, GS, Jacobi und Vorkonditionierung aus, bin aber Anfänger mit Multigrid-Methoden.

Kann jemand dies im Detail erklären oder zumindest klar Pseudocode oder Quellcode liefern, auch mit guter Literatur für Anfänger? Vielen Dank!

Nurlan
quelle

Antworten:

15

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:

  1. Beginnen Sie mit dem Problem des feinen Gitters
  2. Projekt auf ein grobes Gitter (auch als Einschränkung bezeichnet )
  3. Approximation der Lösung im Grobraster (mit einem anderen Löser)
  4. Projizieren Sie die Grobgitterlösung auf das feinere Gitter (auch als Verlängerung bezeichnet ).
  5. 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.

Paul
quelle
Vielen Dank für die ausführliche Antwort! Jetzt habe ich einige Grundkenntnisse über die Multigrammethode. Jetzt habe ich spezielle Fragen zu Restriktions- und Verlängerungsprozessen. Ich habe gelesen, dass einige Restriktionsmatrix R und Interpolationsmatrix M und Formeln wie A2 = RAI verwendet wurden, um Projektionen zwischen Gittern durchzuführen. Aber ich verstand nicht, wie man Matrizen R und I konstruiert. Gibt es irgendwelche Ideen dazu?
Nurlan
Schauen Sie sich die Folien 45-57 des von ChristianClason veröffentlichten Briggs-Multigrid-Tutorials (Teil 1) an. Dort beschreibt Briggs den Prozess für die geometrische Multigrid-Methode. Das ist die einfachste Erklärung, die ich finden kann. Wenn Sie weitere Fragen dazu haben, können Sie gerne eine neue Frage stellen! :)
Paul
15

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.

Christian Clason
quelle
2
Briggs ist wirklich gut!
vanCompute
5

Ein weiterer Klassiker:

  • Wesseling, Eine Einführung in Multigrid-Methoden, John Wiley & Sons, 1992.

Beispielcodes finden Sie bei MGNet

chris
quelle