Up


Iterative Verfahren Aus der Diskretisierung einer elliptischen Randwertaufgabe (z.B. der stationären Wärmeleitungsgleichung) sei das lineare Gleichungssystem

Al xl = fl (1)

gegeben (xl ist dabei der zum Galerkin-Ansatz $T_l({\bf x})= \sum_i (x_l)_i \, \phi_i({\bf x})$ gehörende Knotenvektor; $\phi_i$ eine Basis). Da das Gleichungssystem (1) aus der Diskretisierung der partiellen Differentialgleichung mittels eines Differenzen-, Finite-Elemente- oder Finite-Volumen-Verfahrens hervorgeht, ist die Systemmatrix schwachbesetzt, d.h. in jeder Zeile treten nur wenige Einträge auf, die von Null verschieden sind.

Ist die Anzahl der Unbekannten in diesem Gleichungssystem nicht zu groß, so können zur Auflösung sowohl direkte als auch iterative Methoden benutzt werden. Eine naive Anwendung des Gaußschen Eliminationsverfahrens, d.h. Informationen über die Struktur der Matrix Al werden nicht benutzt, erfordert einen Rechenaufwand der proportional zu n3-Operationen ist. Weiterhin vergrößert sich mit wachsender Anzahl der Unbekannten nicht nur die Rechenzeit erheblich, sondern auch der Speicherbedarf durch den sogenannten ``fill in''. Detaillierte Beschreibungen des Gaußschen Verfahrens und auch effizientere Varianten finden sich z.B. in Bunse & Bunse-Gerstner[1] oder in Duff, Erisman & Reid[3].

Iterative Methoden zur Auflösung von (1) bestimmen ausgehend von einem Startvektor x(0)l, im Falle der Konvergenz des Verfahrens, eine Folge $x_l^{(1)}, x_l^{(2)}, \ldots$von Näherungen zur exakten Lösung: \begin{displaymath}x_l^{(m)} \rightarrow x_l , \qquad m \rightarrow \infty.\end{displaymath}

Jedes lineare iterative Verfahren kann durch die Vorschrift

\begin{displaymath}x_l^{(m+1)} = M_l x_l^{(m)} + N_l f_l , \qquad m\geq 0,\end{displaymath} (2)

beschrieben werden, wobei die Matrix Ml die Iterationsmatix ist. Ihr kommt entscheidende Bedeutung zu, denn das Verfahren (2) konvergiert genau dann, wenn der Spektralradius von Ml, das ist das Maximum der Beträge der Eigenwerte von Ml, kleiner als eins ist:

\begin{displaymath}% latex2htm id marker 647(\ref{ItVerfahren}) \mbox{ ist ......{ \vert\lambda\vert : \lambda \mbox{ ist EW von } M_l \} < 1.\end{displaymath}

Der Wert $\rho (M_l)$, die sogenannte Konvergenzrate, erlaubt nicht nur zu entscheiden, ob ein lineares Verfahren konvergent ist, sondern informiert auch über die Konvergenzgeschwindigkeit. Ist el(m):= xl(m) - xl der Fehler bzgl. der m-ten Iterierten, so gilt für den nächsten Fehler die Normabschätzung \begin{displaymath}\Vert e_l^{(m+1)} \Vert \leq \zeta_m \, \Vert e_l^{(m)} \Vert ,\end{displaymath}mit einer Kontraktionszahl $\zeta_m$, die sich asymptotisch der Konvergenzrate annähert (hierzu sei auf Hackbusch [9] verwiesen). Im Falle des Jacobi-Verfahrens und auch für das Gauß-Seidel-Verfahren zur Lösung der Gleichung (1) ist die Konvergenzrate stark von der Dimension $n= \dim A_l$ der Systemmatrix abhängig. Ist für ein zweidimensionales Problem hl

der Diskretisierungsparameter (typischer Abstand zweier Knoten der Diskretisierung), so ergibt sich die Konvergenzrate in der Größenordnung $1 - {\cal O}(h_l^{2})$, d.h. je kleiner die Schrittweite hl ist, also um so mehr Knoten vorhanden sind, desto näher liegt $\rho (M_l)$ bei eins. Es ist also nur eine langsame Konvergenz zu erwarten. Eine Verbesserung der Situation ergibt sich beim Einsatz des optimalen SOR-Verfahrens oder einer Variante des  cg-Verfahrens1. Eine ausführliche Diskussion dieser Verfahren findet sich wiederum in Hackbusch [9] oder auch Bunse[1]. Aber auch hier ist Konvergenzrate i.a. immer noch von der Größenordnung $1 - {\cal O}(h_l)$.

Mehrgitterverfahren  sind hier eindeutig überlegen, da sie für die betrachtete Situation, das Gleichungssystem stammt aus der Diskretisierung einer elliptischen Differentialgleichung, unter gewissen, hinlänglich allgemeinen Bedingungen, eine von der Schrittweite hl, bzw. von der Anzahl der Unbekannten, unabhängige Konvergenzrate sichern. Der Aufwand zur Lösung von (1) ist dann typischerweise in der Größenordnung ${\cal O}(n \, \log(n))$ (vgl. Hackbusch [9],[7]). Ein wesentlicher Aspekt des Mehrgitterverfahrens ist das Vorhandensein einer Hierarchie von (Ansatz- oder Finite-Element-) Räumen

\begin{displaymath}V_0 \subset V_1 \subset \ldots \subset V_l.\end{displaymath} (3)

Die Galerkin-Lösung Tl aus (siehe oben) liege dabei in Vl. In den ``kleineren'' Räumen $V_i, \, i=0,\ldots,l-1$, werden Hilfsprobleme gelöst. Die Forderung (3) spiegelt sich gerade in der Diskretisierung bzw. in einem entsprechenden Programm wider: es muß eine Struktur vorhanden sein, die den Zugriff auf die Räume Vii=0,..l , und Abbildungen

\begin{displaymath}P_i: V_i \longrightarrow V_{i+1} , \qquadR_{i+1}:V_{i+1} \longrightarrow V_i, \quad i=0,\ldots, l-1\end{displaymath}

zwischen diesen erlaubt. Konkret repräsentieren unterschiedlich feine, geschachtelte Gitter \begin{displaymath}\Omega_{h_0} \subset \Omega_{h_1} \subset \ldots \subset \Omega_{h_l}\end{displaymath} die Ansatzräume Vi und Rechtecksmatrizen die Transferabbildungen Pi und Ri.

Hat man die Absicht in einem Programmpaket, das ein Pre- und Postprozessing, sowie (Eingitter-) Algorithmen zur Lösung der Gleichung (1) enthält, die Vorteile des Mehrgitterverfahrens zu nutzen, so stößt die Integration der Struktur (3) auf erhebliche programmiertechnische Probleme oder ist sogar völlig unmöglich, da z.B. Eingriffe in den Source-Code (etwa bei kommerziellen Produkten) nicht erlaubt sind. Einen Ausweg bietet hier das algebraische Mehrgitterverfahren. Dabei werden die erforderlichen Abbildungen und Grobgitter nur aus der Kenntnis der Diskretisierungsmatrix Al konstruiert.
 
 


 Up  Next  Top    Home

Frank Liebau 1999-07-19