Mehrgitterverfahren

Es ist seit langem bekannt, daß bestimmte iterative Verfahren (zum Beispiel das oben besprochene Gauß-Seidel-Verfahren) bei elliptischen Randwertaufgaben eine ''fehlerglättende'' Wirkung haben. Wir benutzen für solche Verfahren im folgenden den im Mehrgitterkontext gebräuchlichen Ausdruck Relaxationsverfahren.

Das Gauß-Seidel-Verfahren vermag z.B. die hochfrequenten Schwingungen bei der Lösung der Laplacegleichung mit jedem Iterationsschritt um einen Faktor 0.5 zu reduzieren. Langwellige Schwingungen werden dagegen, was wir in diesem Abschnitt zeigen wollen, um einen Faktor $1-O(h2)$ reduziert - bei kleinem $h$ also extrem langsam. Anhand von Abbildung 46 verdeutlicht sich die ''glättende'' Wirkung dieser Verfahren. Bereits nach wenigen Iterationen besteht der Fehler hauptsächlich aus niederfrequenten Anteilen. Man hat also insgesamt keine gute Fehlerverkleinerung - und daher langsame Konvergenz - aber sehr gute Fehlerglättung (Abbildung 47). Das Konvergenzverhalten iterativer Gleichungslöser muß daher genaugenommen in Abhängigkeit von der Fehlerfreqenz beurteilt werden.

Abbildung 46: Residuenverlauf in Abhängigkeit der Iterationsanzahl  

Abbildung 47: Räumlicher Residuenverlauf beim Gauß-Seidel-Verfahren, Ausgangsverteilung sowie Verteilung nach 5 und 10 Iterationen  

Auf einem groben numerischen Gitter ''$GH$'' der Maschenweite $H$ kann eine finite Differenzenapproximation mit sehr viel weniger Rechenaufwand gelöst werden, als auf einem feinen, knotenpunktärmeren Gitter ''$Gh$'' der Maschenweite $h$. Allerdings ergibt sich auf dem groben $H$-Gitter im allgemeinen auch eine geringere Genauigkeit. Die Approximation einer $h$-diskretisierten Aufgabe durch eine $H$-diskretisierte ist daher mit einem deutlichen Informationsverlust verbunden. Hochfrequente Komponenten der Fourierreihenentwicklung vermag das grobe Gitter nicht mehr aufzulösen. Die niederfrequenten Komponenten lassen sich dagegen auf dem $H$-Gitter gut erfassen. Hat man durch die vorangegangene Relaxation auf einem feinen Gitter $Gh$ eine Fehlerglättung erreicht, dann setzt sich der Fehler auf diesem Gitter im wesentlichen aus niederfrequenten Anteilen zusammen. Die Approximation des $h$-diskretisierten Problems durch ein $H$-diskretisiertes ist somit nun ohne wesentlichen Informationsverlust möglich. Im einfachsten Falle handelt sich um ein iteratives Verfahren, das auf einer Sequenz von mehreren Gittern abläuft. Auf jedem Gitter wird relaxiert, um die dort hochfrequenten Fehlerkomponenten zu verkleinern. Die Verbindung zwischen den verschiedenen Gittern wird durch ''Interpolations-'' und ''Restriktionsoperatoren'' hergestellt.

Die voranstehenden Aussagen über die glättende Wirkung eines Relaxationsverfahren wollen wir in einem kurzen Beispiel herleiten. Betrachtet wird dazu die PDG

welche wir auf einem quadratischen Gitter der Maschenabmessung $(\; h\; x\; h)$ durch zentrale Differenzenquotienten (2.12) diskretisieren wollen.

(5.73)

Verwenden wir zur Glättung das Punkt-Gauß-Seidel-Verfahren, so ergibt sich für den $k$-ten Relaxationsschritt:

(5.74)

Subtrahiert man (5.74) von (5.73) dann erhält man

(5.75)

wobei mit $e$_i,j^k der lokale Fehler zwischen der jeweiligen Näherung $u$_i,j^k und der diskreten Lösung $u$_i,j gemeint ist. Wir definieren die Relation der Fehlerverstärkung

analog zu den in Kapitel 3 gemachten Aussagen, und erhalten aus der lokalen Entwicklung des Fehlers in einer diskreten Fourierreihe für randferne Gitterpunkte

mit

(5.76)

Führt man (5.76) in (5.75) ein, so erhält man nur ein Summenglied (siehe auch Abschnitt 3.3)

(5.77)

bzw.

(5.78)

Kürzt man nun noch den Ausdruck , dann erhält man für den Fehlervergrößerungsfaktor

(5.79)

Unter Verwendung der Eulerbeziehung besser abschätzen:

(5.80)

Man beachte, daß für $$ = (₁, ₂) (0, 0), $G$ gegen $1$ strebt, in diesem Falle also keine Konvergenz mehr vorliegt. Die erste nicht triviale Kombination $$₁, ₂ 0 liegt für $n=1$ vor. Beschränken wir uns der Einfachheit halber auf ein Integrationsgebiet vom Durchmesser $O(1)$, dann sind $$₁ bzw. $$₂ im ersten nicht trivialen Fall von gleicher Größenordnung.

Für gewöhnlich ist die Schrittweite (des feinsten Gitters) $h$ wesentlich kleiner als eins, so daß wir die Reihenentwicklung der trigonometrischen Glieder in (5.80) frühzeitig abbrechen können. Zudem unterdrücken wir im Sinne einer Größenordnungsabschätzung die Nennerfakultäten:

(5.81)

Schätzt man den verbliebenen Nenner gegen eins ab, so ergibt sich tatsächlich für den niederfrequenten Fehler die auf einem feinen Gitter äußerst ungünstige Glättungsrate

Im folgenden werden die Schwingungeskomponenten als ''hochfrequent'' auf einem Gitter der Schrittweite $h$ bezeichnet, wenn ihnen ein Wert zugeordnet ist. Dies sind gerade diejenigen Frequenzen, welche auf den nächstgröberen Gitter der Schrittweite $H=2h$ nicht mehr approximiert werden können und demzufolge auf $Gh$ geglättet werden müssen.

Abbildung 48: Fehlerglättung durch Relaxation

 
• Mehrgitterprinzip
• Zweigitterbeschleunigungsverfahren
• Mehrgitterverfahren mit V- und W-Zyklus
• Full multigrid (FMG) Algorithmus
• Restriktions- und Prolongationsoperator
• Rechenablauf des Mehrgitterverfahrens