Up



Zum klassischen Mehrgitterverfahren


Die Diskretisierung der Randwertaufgabe

\begin{displaymath}- \Delta u ({\bf x}) = f ({\bf x}) , \qquad {\bf x}\in \Omega , \qquad u\Big\vert _{\partial \Omega} = g\end{displaymath} (7)

auf einem vorgegebenen Gitter \begin{displaymath}\Omega_{H} :=\{ {\bf x}^i \; :\; {\bf x}^i \mbox{ ist Knoten der Diskretisierung} \}\end{displaymath} ergebe ein Gleichungssystem

\begin{displaymath}A_H \, x_H = f_H\end{displaymath} (8)

mit positiv definiter Matrix AH. Durch Halbierung der Schrittweite H, d.h. Verfeinerung des Gitters$\Omega _H$, erhält man ein weiteres Gleichungssystem, das die gleiche Struktur wie (8), jedoch die 4-fache Dimension, aufweist. Die Approximation der Lösung von (7) durch den Ansatz verbessert sich, jedoch wächst der Aufwand zur Lösung des entsprechenden Gleichungssystems.

\includegraphics[width=8cm]{GrobGitter.ps}

GrobGitter $\Omega _H$

\includegraphics[width=8cm]{fineGitter.ps}

Verfeinerung $\Omega _h$mit h=H/2,.

Abbildung 1: Grob- und Feingitterpunkte

Sei nun $x_h^{\star}$ die Lösung des Gleichungssystems $A_h \, x_h = f_h$ im Gitter $\Omega _h$ und $\tilde{x}_h$ eine Näherung der Lösung. Es gilt somit

\begin{displaymath}A_h (\tilde{x}_h - x_h^{\star}) = A_h \, \tilde{x}_h - f_h := d_h.\end{displaymath}

Der Vektor dh ist der Defekt und \begin{displaymath}e_h := \tilde{x}_h - x_h^{\star} \end{displaymath} der Fehler zwischen Näherung und Lösung. Insbesondere folgt die Defektgleichung

\begin{displaymath}\index{Ersatzgleichungssystem}A_h \, e_h = d_h, \qquad \mbox{ bzw. } \qquad e_h = A_h^{-1} d_h .\end{displaymath} (9)

Ist durch Lösung des Ersatzgleichungssystems (9) der Fehler eh bekannt, so ergibt sich die gesuchte Lösung sofort durch \begin{displaymath}x_h^{\star} = \tilde{x}_h - e_h. \end{displaymath}Im Vergleich zur Ausgangssituation ist nichts gewonnen, da die Lösung von (9) genauso schwierig (aufwendig) ist, wie die der Gleichung $A_h \, x_h = f_h$.
Der entscheidende Gedanke ist nun, die Defektgleichung auf das grobe Gitter $\Omega _H$ mittels einer Abbildung
2 $r: \Omega_h \longrightarrow \Omega_H$ (Restriktion) zu übertragen:

\begin{displaymath}A_H \, e_H = (r \, d_h),\end{displaymath} (10)

und nach eH aufzulösen: $ e_H = A_H^{-1}r \, d_h$. Der Defekt dh wird also (in geeigneter Weise) auf das grobe Gitter ``transportiert''. Die anschließende Lösung des Gleichungsystems (10) ist weniger aufwendig, als die der ursprünglichen Gleichung ($\dim A_H = (\dim A_h)/4$). Eine neue Näherung ergibt sich nun durch

\begin{displaymath}x_h^{\rm new} := \tilde{x}_h - p \, e_H,\end{displaymath} (11)

wobei die Abbildung p (die Prolongation) die Korrektur eH auf das feine Gitter überträgt. Sind rh und ph die Matrixdarstellungen der Restriktion und Prolongation, so wird häufig

\begin{displaymath}r_h = \sigma \, p_h^T\end{displaymath} (12)

gewählt, dabei ist $\sigma$ ein Skalierungsfaktor. Implizit geht hier die Wahl der Diskretisierung (Finite-Elemente-Methode, Finite-Differenzen-Verfahren) und der Skalarprodukte für die Vektoren auf den verschiedenen Gittern ein.
 
 

\begin{figure}\centerline{\hbox{ \psfig{file=amg_plots/freq.ps,width=10cm}} }\end{figure}
Abbildung 2: eindimensionales Beispiel: (oben) glatte (niederfrequente) Gitterfunktion, gut darstellbar auf dem groben Gitter (= $\circ$); (unten) hochfrequente Gitterfunktion, nicht ``sichtbar'' im groben Gitter

Ausgehend vom groben Gitter $\Omega _H$ läßt sich die Menge der Vektoren Xh (auch Menge der Gitterfunktionen genannt) zum feinen Gitter $\Omega _h$in zwei Kategorien einordnen (vgl. Abbildung 3):

1.
die Menge der hochfrequenten Gitterfunktionen$X_{h,\rm oz}$: ``schlechte'' Darstellung auf dem groben Gitter und
2.
die Menge der niederfrequenten Gitterfunktionen $ X_{h,\rm glatt}= X_{h}\setminus X_{h,\rm oz}$: ``gute'' Darstellung auf dem groben Gitter.

Ein Vektor $x_h \in X_h$ kann also in hoch- und niederfrequente Anteile zerlegt werden

\begin{displaymath}x_h = \sum_{e_i \in X_{h,\rm glatt} } \alpha_i \, e_i +\sum_{e_j \in X_{h.\rm oz}} \alpha_j \, e_j .\end{displaymath}

Da es (hochfrequente) Feingitterfunktionen gibt, die das grobe Gitter nicht ``sieht''3, bildet das durch (11) gegebene Verfahren i.a. keine konvergente Iteration. Die folgende Beobachtung hilft an dieser Stelle entscheidend weiter: Klassische Iterationsverfahren, wie etwa das Gauß-Seidel-Verfahren, haben gerade Probleme die niederfrequenten Anteile in der Lösung zu erfassen, reduzieren aber die hochfrequenten Fehleranteile gut.

Darstellung des Fehler zu einem 1D-Modellproblem bgzl. des Jacobi-Verfahrens : der hochfrequenten Anteil wird schnell gedämft, die niederfrequenten Anteile in der Lösung hingegen nur langsam (unten: eh(x,y), wobei y die Nummer der Jacobi-Iteration ist).

Eine Kombination aus klassischem Iterationsverfahren und der Grobgitterkorrektur (11) ergibt das Zweigitterverfahren:

1.
Glättung: führe einige Schritte (meist weniger als vier) mit einem geeigneten Iterationsverfahren durch,
2.
Grobgitterkorrektur: anschließend wird eine neue Näherung mittels (11) berechnet
3.
falls $\Vert A_h x_h^{\rm new} - f_h\Vert < {\rm tol}$ oder eine maximale Anzahl von Iterationen überschritten ist: Stop; sonst gehe zu 1.

Algorithmus 3 beschreibt ein Unterprogramm, das einen Zweigitterschritt ausführt, und Algorithmus 4 die Zweigitteriteration.

\begin{algorithm}% latex2htm id marker 469\caption[Zweigitterschritt]{ zgmst......, e_H$ ; \hfill \COMMENT{ Grobgitterkorrektur }\end{algorithmic}\end{algorithm}
 
 

\begin{algorithm}% latex2htm id marker 484\caption{Zweigitterverfahren } \i......m $<$\space tol) or (step $>$\space stepmax)};\end{algorithmic}\end{algorithm}

Dabei ist \begin{displaymath}{\cal S}_l (x_h,f_h) := S_h \ x_h + N_h \, f_h\end{displaymath}

eine konsistente Iteration, die zur Glättung benutzt wird. Ist diese die Jacobi-Iteration, so gilt (Dh die Diagonale von Ah)

\begin{displaymath}S_h =I_h - D_h^{-1} A_h , \qquad N_h=D_h^{-1}.\end{displaymath}

Ausgehend von einer Näherung x(i) kann ein Schritt (also die Berechnung der nächsten Iterierten) im eben beschriebenen Zweigitterverfahren (Algorithmus 4) auch als lineares Iterationsverfahren

\begin{displaymath}x^{(i+1)} = S_h x^{(i)} - p_h A_H^{-1} r_h\left(A_h S_h x_h^{(i)} - \tilde{f}_h \right)\end{displaymath}

geschrieben werden. Die Iterationsmatrix des Zweigitterverfahrens ist also

\begin{displaymath}M_h^{\rm ZGM} := \left( I_h - p_h \ A_H^{-1} \, r_h \, A_h \right) \, S_h.\end{displaymath}

Mit Hilfe von Annahmen über die Regularität der Lösung4 der zu Grunde liegenden partiellen Differentialgleichung, weiterer Voraussetzungen an die Diskretisierung (geschachtelte Unterräume, Approximationseigenschaften) und an die Glättungsiteration ${\cal S}_l$ kann gezeigt werden, daß der Spektralradius der Iterationsmatrix$M_h^{\rm ZGM}$unabhängig von der Schrittweite h ist:

\begin{displaymath}\rho( M_h^{\rm ZGM}) \leq \zeta(\alpha) < 1 , \qquad \mbox{f.a.} \quad \alpha \geq \alpha_0.\end{displaymath} (13)

Das Verfahren 4 konvergiert demnach, unter hier nicht näher genannten Voraussetzungen, unabhängig von h. Der Übergang vom Zweigitter- zum Mehrgitterverfahren ist jetzt nur noch ein kleiner Schritt: das exakte Lösen der Grobgittergleichung wird nun wiederum durch ein Zweigitterverfahren ersetzt, usw. Die sehr guten Konvergenzeigenschaften bleiben dabei erhalten und es zeigt sich, daß der Aufwand optimal ist ([9]). Das Unterprogramm, das einen Mehrgitterschritt ausführt kann folgendermaßen beschrieben werden
 
 

\begin{algorithm}% latex2htm id marker 516\caption[Mehrgitterschritt]{ mgmst......alpha_2$\space Nachgl\uml {a}ttungen }\ENDIF\end{algorithmic}\end{algorithm}

Die Mehrgitteriteration ist dann

\begin{algorithm}% latex2htm id marker 542\caption[Mehrgitterverfahren]{Mg-......m $<$\space tol) or (step $>$\space stepmax)};\end{algorithmic}\end{algorithm}

Die angesprochenen Themenbereiche können in Hackbusch[9] nachgelesen werden. Eine tiefergehende Darstellung der Mehrgitterverfahren findet sich in Hackbusch[7].

 

Beispiel: 2D-Modellproblem (7) mit W=[0,1]2, g=0 und f(x,y)= sin(x*p)*sin(y*p).

 


 

 Up  Pre  Next   Top    Home


Frank Liebau
1999-07-19