W. Hackbusch

Die Lösung linearer Gleichungssysteme ist ein Grundproblem einer Vielzahl von Anwendungen. Bei Anwendungen mit physikalischen Hintergrund (z. B. Kontinuums- oder Strömungsmechanik) treten Gleichungssysteme als Diskretisierung partieller Differentialgleichungen auf. Ihre Dimension ist im wesentlichen nur durch den zur Verfügung stehenden Speicherplatz noch oben beschränkt. Zur Zeit steht die Lösung von bis zu Millionen von Gleichungen an. Hierzu können nur Verfahren verwendet werden, deren Aufwand proportional zur Dimension des Gleichungssystems steigt. Seit man Computer einsetzt, versucht man, effizientere Lösungsverfahren zu konstruieren. Mehrgitterverfahren waren die ersten, die dieses Ziel für eine große Klasse von Problemen erreichten.

Die Mehrgittermethode enthält Komponenten, die problemabhängig gewählt werden müssen. Es handelt sich also eher um eine Lösungsstrategie als um einen feststehenden Algorithmus.

1 Die Mehrgitterhierarchie

Das Mehrgitterverfahren ist eine Iteration zur Lösung linearer oder nichtlinearer Gleichungen, die als Diskretisierung partieller Differential-gleichungen (vornehmlich von elliptischem Typ) entstehen. Der Diskretisierungshintergrund ist entscheidend, da er zu einer Hierarchie von diskreten Gleichungen führt. Ein Randwertproblem (Differentialgleichung samt Randbedingung) sei notiert als \begin{eqnarray}\begin{array}{cc}Lu=f.\end{array}\end{eqnarray}

Im einfachsten Fall kann zur Diskretisierung ein Differenzenverfahren mit der Gitterweite h verwendet werden. Die diskrete Gleichung lautet \begin{eqnarray}\begin{array}{cc}{L}_{h}{u}_{h}={f}_{h}.\end{array}\end{eqnarray}

Sei h₀, h₁ = h₀/2, …, h_ℓ = h₀/2^ℓ, … eine Folge von Schrittweiten, die für die maximale Stufenzahl ℓ = ℓ_max die Schrittweite \(h={h}_{{\ell }_{\max }}\) aus (2) ergebe. Dann ist (2) die feinste Diskretisierung in der Diskretisierungshierarchie \begin{eqnarray}\begin{array}{cc}{L}_{0}{u}_{0}={f}_{0},\ldots, {L}_{\ell }{u}_{\ell }={f}_{\ell },\ldots\end{array}\end{eqnarray}

für ℓ = 0, …,ℓ_max, wobei L_ℓ die Abkürzung für \({L}_{{h}_{\ell }}\) ist (analog u_ℓ, f_ℓ).

Im Fall einer FE-Diskretisierung (“FE-” kürzt “Finite-Element-” ab) wird diese durch einen FE-Raum V beschrieben, der z. B. aus stückweise linearen Elementen über Dreiecken einer Triangulation 𝒯 bestehen kann. Falls diese Triangulation das letzte Element in einer Folge 𝒯₀, 𝒯₁, …, 𝒯_ℓ, …, \({\mathcal{T}}_{{\ell }_{\max }}\) ist, wobei 𝒯_ℓ+1 jeweils durch eine Verfeinerung der Triangulation 𝒯_ℓ entsteht, so gilt für die zugehörigen FE-Räume die Inklusion \begin{eqnarray}{V}_{0}\subset \cdots \subset {V}_{\ell -1}\subset {V}_{\ell }\subset \cdots \subset {V}_{{\ell }_{\max }}=V.\end{eqnarray}

Der größte FE-Raum \({V}_{{\ell }_{\max }}\) stimmt mit dem obigen Raum V überein, für den die FE-Diskretisierung gelöst werden soll. Jeder Raum V_ℓ führt zu einer Diskretisierung L_ℓu_ℓ = f_ℓ in der Hierarchie (3).

Mehrgitterverfahren lösen das Gleichungssystem \({L}_{{\ell }_{\max }}{u}_{{\ell }_{\max }}={f}_{{\ell }_{\max }}\), wobei sie von den Grobgitter-matrizen L_ℓ(0 ≤ ℓ < ℓ_max) Gebrauch machen. Die geschachtelte Iteration (siehe unten) löst sogar alle Gleichungen in (3).

2 Was leisten Mehrgitterverfahren?

Ziel aller schnellen Iterationsverfahren ist es, ein Gleichungssystem mit n Gleichungen und Unbekannten mit einem (Zeit- bzw. Rechen-)Aufwand proportional zu n zu lösen. Da ein Iterationsschritt mit einer schwachbesetzen Matrix n Operationen kostet, muß die gewünschte Genauigkeit mit einer festen Anzahl von Iterationsschritten erreichbar sein. Dies bedeutet, daß die Konvergenzgeschwindigkeit nicht nur < 1, sondern auch unabhängig von n (d. h. unabhängig vom Diskretisierungsparameter h_ℓ bzw. der Dimension von V_ℓ) sein muß.

Diese optimale Konvergenz kann ein Mehrgitterverfahren in sehr allgemeinen Fällen erreichen. “Allgemein” heißt hier, daß keine speziellen algebraischen Eigenschaften der Matrix L_ℓ, insbesondere weder Symmetrie noch positive Definitheit, vorliegen müssen.

3 Struktur der Mehrgitteriteration

3.1 Glättungsiterationen

Übliche klassische Iterationsverfahren wie das Jacobi- oder das Gauß-Seidel-Verfahren oder die einfache Richardson-Iteration \begin{eqnarray}\begin{array}{cc}{\mathcal{S}}_{h}:({u}_{h},{f}_{h})\mapsto {u}_{h}-\frac{1}{||{L}_{h}||}({L}_{h}{u}_{h}-{f}_{h})\end{array}\end{eqnarray}

wirken als Glättungsiteration, d. h. sie reduzieren die oszillierenden Fehleranteile wesentlich besser als die glatten. Im symmetrisch positiv definiten Fall ist ∥L_h∥ = λ_n der größte Eigenwert. Die (oszillierenden) Eigenvektoren von L_h zu Eigenwerten in [λ_n/2, λ_n] werden durch (4) um den Faktor 0 ≤ 1 − ωλ_ν ≤ 1/2 reduziert. Wenn (4) nur langsam konvergiert, liegt es an den Fehler-komponenten von \({u}_{h}-{u}_{h}^{exakt}\), die zu den niedrigen Eigenwerten gehören.

Wenige Schritte einer Glättungsiteration liefern eine Näherung \({\tilde{u}}_{h}\), deren Fehler \({\tilde{u}}_{h}-{u}_{h}^{exakt}\) “glatt” ist und damit im Gitter der gröberen Schrittweite H repräsentiert werden kann.

3.2 Zweigitterverfahren

Das Zweigitterverfahren, obwohl nicht für die praktische Anwendung geeignet, ist der wesentliche Schritt zur Konstruktion und der Analyse des Mehrgitterverfahrens. Es werden nur die Stufen ℓ und ℓ − 1 betrachtet, die der feinen Schrittweite h und der groben Schrittweite H (z. B. H = 2h) entsprechen. Die zugehörigen Matrizen aus (3) seien L_h und L_H.

Zuerst wird aus dem Startwert u_h mit wenigen Glättungsschritten \({\tilde{u}}_{h}\) erzeugt. Die Zahl der Glättungsschritte ist oft 2 oder 3. Der Defekt \begin{eqnarray}{d}_{h}:={L}_{h}{\tilde{u}}_{h}-{f}_{h}\end{eqnarray}

wird berechnet. Offenbar ist L_hδu_h = d_h die Gleichung für die exakte Korrektur: \({u}_{h}:={\tilde{u}}_{h}-\delta {u}_{h}\) erfüllt \begin{eqnarray}{L}_{h}{u}_{h}={L}_{h}{\tilde{u}}_{h}-{L}_{h}\delta {u}_{h}={d}_{h}+{f}_{h}-{d}_{h}={f}_{h}.\end{eqnarray}

Natürlich ist die direkte Lösung von L_hδu_h = d_h ebenso schwierig wie diejenige von L_hu_h = f_h. Da die Korrektur δu_h aber gleichzeitig der Fehler \({\tilde{u}}_{h}-{u}_{h}^{exakt}\) und daher glatt ist, kann L_hδu_h = d_h näherungsweise im groben Gitter gelöst werden. Im Zweigitterfall wird \begin{eqnarray}\begin{array}{cc}{L}_{H}{\upsilon }_{H}=r{d}_{h}\end{array}\end{eqnarray}

direkt gelöst, wobei die Restriktion r eine geeignete lineare Abbildung vom Gitter der Schrittweite h in das gröbere Gitter H darstellt. Im eindimensionalen äquidistanten Fall mit H = 2h ist \begin{eqnarray}(r{d}_{h})(x):=\frac{1}{4}{d}_{h}(x-h)+\frac{1}{2}{d}_{h}(x)+\frac{1}{4}{d}_{h}(x+h)\end{eqnarray}

für alle x = 2νh (ν ∈ ℤ) eine kanonische Wahl.

Anschließend wird die Lösung υ_H von (5) mittels einer Prolongation p (Interpolation) vom H-Gitter in das feinere h-Gitter transportiert. Im eindimensionalen Fall übernimmt man die Werte υ_H(2νh) und interpoliert dazwischen linear: \((p{\upsilon }_{H})(x):={\scriptstyle \frac{1}{2}}{\upsilon }_{H}(x-h)+{\displaystyle \frac{1}{2}}{\upsilon }_{H}(x+h)\) für alle x = (2ν + 1)h (ν ∈ ℤ). Da pυ_H ein Ersatz für δu_h ist und \({u}_{h}^{exakt}={\tilde{u}}_{h}-\delta {u}_{h}\) gilt, wird \begin{eqnarray}{u}_{h}^{neu}={\tilde{u}}_{h}-p{\upsilon }_{H}\end{eqnarray}

als neuer Iterationswert definiert. Oft ist p die adjungierte Abbildung zu r.

In algorithmischer Schreibweise lautet das Zweigitterverfahren der Stufe ℓ (h_ℓ = h, h_ℓ−1 = H):

function ZGM(ℓ, u, f): Gitterfunktion;

begin for i := 1 to ν do u := 𝒮_ℓ(u, f); (vgl. (4))

d := L_ℓ u − f; (Defektberechnung)

d := rd; (Restriktion auf Stufe ℓ − 1)

\(\upsilon :={L}_{l-1}^{-1}d;\) (exakte Lsg. der Grobgittergl.)

u = u − pυ; (Grobgitterkorrektur)

ZGM := u (neue Iterierte)

end;

Die Abbildungen 𝒮_ℓ, r und p sind im allgemeinen problemabhängig.

3.3 Mehrgitterverfahren

Im Zweigitterverfahren ZGM wird die Grobgittergleichung noch exakt gelöst. Im Mehrgitterfall ersetzt man die exakte Lösung durch Annäherung mittels γ Iterationen einer Zweigittermethode auf den Stufen ℓ − 1 und ℓ − 2. Gleiches geschieht auf der Stufe ℓ − 2, bis man auf der Stufe 0 (gröbstes Gitter, d. h. kleinste Anzahl von Gleichungen) exakt löst. Es entsteht der folgende rekursive Algorithmus:

function MGM(ℓ, u, f): Gitterfunktion;

if ℓ = 0 then \(u:={L}_{0}^{-1}f\) else

begin for i := 1 to ν do u := 𝒮_ℓ(u, f);

d := r(L_ℓ u − f); (Defektrestriktion)

υ := 0; (Startwert für Korrektur)

for i := 1 to γ do υ := MGM(ℓ − 1, υ, d);

u = u − pυ; (Grobgitterkorrektur)

MGM := u (neue Iterierte)

end;

Gängige Werte für γ sind γ = 1 (sogenannter V-Zyklus) und γ = 2 (W-Zyklus). Obwohl bei γ = 2 eine Iteration auf der Stufe ℓ zu zwei Iterationen auf Stufe ℓ − 1, υier Iterationen auf Stufe ℓ − 2 usw. führt, nimmt der Rechenaufwand ab (im zweidimensionalen Fall und h_ℓ−1 = 2h_ℓ viertelt sich jeweils der Rechenaufwand für die Durchführung von 𝒮_h, r und p.)

Der oben angegebene Algorithmus verwendet nur eine Vorglättung. Möglich ist auch die reine Nachglättung, d. h. u := 𝒮_ℓ(u, f) nach der Grobgitterkorrektur u = u − pυ oder eine symmetrische Vor- und Nachglättung.

3.4 Geschachtelte Iteration

Bei einer diskretisierten Differentialgleichung ist es unnötig, solange zu iterieren, bis die letzte Dezimalstelle fixiert ist. Es reicht, wenn der Iterations-fehler \({u}_{\ell }-{u}_{\ell }^{exakt}\) die Größenordnung des ohnehin unvermeidlichen Diskretisierungsfehlers hat. Die Schwierigkeit bei diesem Abbruchkriterium ist, daß man oft den Diskretisierungsfehler nicht genau genug kennt. Hier bietet die geschachtelte Iteration eine elegante Lösung. Auch ohne Kenntnis des Diskretisierungsfehler liefert der Algorithmus eine Approximation der richtigen Güte.

\({u}_{0}:={L}_{0}^{-1}{f}_{0};\) (Lösung auf gröbstem Gitter)

for ℓ := 1 to ℓ_max do begin u_ℓ := pu_ℓ−1; (Startwert auf Stufe ℓ)

for i := 1 to m do u_ℓ := MGM(ℓ, u_ℓ, f_ℓ)

end;

Der entscheidende Punkt ist, daß der Startwert bereits einen Fehler in der Größenordnung des Diskretisierungsfehlers \({u}_{\ell }^{exakt}-p{u}_{\ell -1}^{exakt}\) besitzt. Als Iterationsanzahl reicht oft m = 1 aus! Im Prinzip kann die Mehrgitteriteration MGM durch jede andere ersetzt werden, wenn die Konvergenzrate nur unabhängig von der Dimension (d. h. von ℓ) ist.

Die geschachtelte Iteration liefert Resultate für alle Stufen ℓ := 1, …, ℓ_max. Trotzdem ist der Rechenaufwand für ℓ < ℓ_max nur ein Bruchteil des ohnehin auftretenden Aufwandes für ℓ_max.

4 Beispiel

Einfachstes Testbeispiel ist die Poisson-Gleichung \begin{eqnarray}-\Delta u:=-{u}_{xx}-{u}_{yy}=f{\quad}in\,\Omega =(0,1)\times (0,1)\end{eqnarray}

diskretisiert durch den 5-Punkt-Differenzenstern −Δ_hu := 4u(x, y) − u(x − h, y) − u(x + h, y) − u(x, y − h) − u(x, y + h) oder durch die FE-Methode mit stückweise linearen Funktionen auf einer regelmäßigen Triangulierung. Beide Verfahren führen bis auf einen Faktor zur gleichen Matrix in L_hu_h = f_h. Am Rand des Quadrates 5 werden Dirichlet-Werte vorgeschrieben. f_h und die Randwerte seien so gewählt, daß sich u_h(x, y) = x² + y² als diskrete Lösung von L_hu_h = f_h ergibt. Da L_h positiv definit ist, kann die gröbstmögliche Schrittweite h₀ := 1/2 als Schrittweite der Stufe ℓ = 0 gewählt werden. Die weiteren Gitterweiten sind daher h_ℓ = 2^−1−ℓ. Die folgende Tabelle zeigt den Iterationsfehler \({e}_{m}:=||{u}_{\ell }^{(m)}-{u}_{\ell }^{exakt}|{|}_{\infty }\) nach m Mehrgitteriterationsschritten (Start mit \({u}_{\ell }^{(0)}=0\), W-Zyklus, 2 Vorglättungsschritte mit den Gauß-Seidel-Verfahren) auf der Stufe ℓ = 7 (entspricht h_ℓ = 1/256 und 65025 Unbekannten).

Die letzte Spalte zeigt die Fehlerverbesserung, die der Konvergenzrate 0.067 entspricht. Ähnliche Raten ergeben sich für andere Schrittweiten. Die obigen Resultate werden nur zur Demonstration der Konvergenzgeschwindigkeit mit \({u}_{\ell }^{(0)}=0\) gestartet. Billiger ist die geschachtelte Iteration.

5 Nichtlineare Gleichungen

Die Kombination des Newton-Verfahrens mit dem oben beschriebenen Mehrgitterverfahren für das entstehende lineare System ist eine naheliegende Möglichkeit. Die Berechnung der Funktionalmatrix läßt sich aber sogar vermeiden, wenn man das nichtlineare System ℒ(u) = f mit dem nichtlinearen Mehrgitterverfahren löst. Sei \begin{eqnarray}{ {\mathcal L} }_{\ell }({u}_{\ell })={f}_{\ell }{\quad}f\ddot{u}r\,\ell =0,\cdots, {\ell }_{\max }\end{eqnarray}

die Hierarchie der diskreten Probleme. Die geschachtelte Iteration bestimmt neben den Näherungen \({\tilde{u}}_{\ell }\) auch deren Defekt \({\tilde{f}}_{\ell }:={ {\mathcal L} }_{\ell }({\tilde{u}}_{\ell })\):

löse \({ {\mathcal L} }_{0}({\tilde{u}}_{0})={f}_{0}\) approximativ; (zB mit Newton)

for ℓ := 1 to ℓ_max do

begin \({\tilde{f}}_{\ell -1}:={ {\mathcal L} }_{\ell -1}({\tilde{u}}_{\ell -1});\) (Defekt von \({\tilde{u}}_{\ell -1}\)\({\tilde{u}}_{\ell }:=p{\tilde{u}}_{\ell -1};\) (Startwert auf Stufe ℓ)

for i := 1 to m do \({\tilde{u}}_{\ell }\) := NMGM(ℓ \({\tilde{u}}_{\ell }\), f_ℓ)

end;

Die nachfolgend definierte Iteration NMGM verwendet \({\tilde{u}}_{\ell -1}{\tilde{f}}_{\ell -1}\) als Bezugspunkt der Stufe ℓ − 1.

function NMGM(ℓ, u, f): Gitterfunktion;

if ℓ = 0 then ”löse ℒ₀(u)= f approximativ”

else begin for i := 1 to ν do u := 𝒮_ℓ(u, f);

d := r(ℒ_ℓ(u_ℓ) − f_ℓ); (Defektrestriktion)

ϵ := ϵ(d); (kleiner positiver Faktor)

\(\delta :={\tilde{f}}_{\ell -1}-\varepsilon * d;\)

\(\upsilon :={\tilde{u}}_{\ell -1};\) (Startwert für Korrektur)

for i := 1 to γ do v := NMGM(ℓ − 1, υ, δ);

\(u=u+p(\upsilon +{\tilde{u}}_{\ell -1})/\varepsilon;\);(Grobgitterkorrektur)

NMGM := u (neue Iterierte)

end;

Dabei ist 𝒮_ℓ(u, f) eine nichtlineare Glättungsiteration für ℒ_ℓ(u_ℓ) = f_ℓ. Das Analogon von (4) lautet \begin{eqnarray}{S}_{\ell }({u}_{\ell },{f}_{\ell })={u}_{h}-({ {\mathcal L} }_{\ell }({u}_{\ell })-{f}_{\ell })/||{ {\mathcal L} }_{\ell }||,\end{eqnarray}

wobei L_ℓ(u_ℓ)= ∂ℒ_ℓ(u_ℓ)/∂u_ℓ. Der Faktor ϵ(d) kann z. B. als σ/||d|| mit kleinem σ gewählt werden.

Wenn L_ℓ(u_ℓ)Lipschitz-stetig ist und weitere technische Bedingungen erfüllt sind, läßt sich zeigen, daß die Iteration NMGM asymptotisch mit der Geschwindigkeit konvergiert, mit der die lineare Iteration MGM konvergiert, wenn sie auf das linearisierte Problem mit den Matrizen \({L}_{\ell }:=\partial {L}_{\ell }({u}_{\ell }^{exakt})/\partial {u}_{\ell }\) angewandt wird. Es sind auch andere Festsetzungen von \({\tilde{u}}_{\ell -1},{\tilde{f}}_{\ell -1},\varepsilon \) (wie im FAS-Verfahren) möglich (vgl. [1,§9]).

6 Eigenwertprobleme

Das kontinuierliche Eigenwertproblem zum Differentialoperator L aus (1) lautet Lu = λu, wobei u homogene Randbedingungen erfülle. Die Hierarchie diskreter Eigenwertaufgaben ist \begin{eqnarray}{L}_{\ell }{u}_{\ell }=\lambda {u}_{\ell }{\quad}f\ddot{u}r\,\ell =0,\ldots, {\ell }_{\max }\end{eqnarray}

(evtl. statt λI auch mit der Massematrix in λM_ℓ). Wieder basiert das Zweigitterverfahren auf einer Glättung und einer Grobgitterkorrektur mit Hilfe des Defektes d_ℓ = L_ℓu_ℓ − λu_ℓ, nur ist die Interpretation von d_ℓ als rechte Seite für die Bestimmung der Korrektur δu_ℓ aus (L_ℓ − λI)δu_ℓ = d_ℓ problematisch, da L_ℓ − λI für den Eigenwert λ singulär ist. Trotzdem ist (L_ℓ − λI)δu_ℓ = d_ℓ lösbar, da die rechte Seite d_ℓ im Bildraum liegt. Die Unbestimmtheit von δu_ℓ ist harmlos, da sie gerade im Eigenraum liegt. Für die restringierte Ersatzgleichung (L_{ℓ − 1} − λI)υ_{ℓ − 1} = rd_{ℓ − 1} gilt diese Aussage nur näherungsweise, deshalb sind geeignete Projektionen erforderlich. Falls L_ℓ nicht symmetrisch ist, können die Rechts- und Linkseigenvektoren simultan berechnet werden. In der Kombination mit dem Ritz-Verfahren kann eine Gruppe von Eigenpaaren gemeinsam behandelt werden (vgl. [1,§12]).

7 Lösung von Integralgleichungen

Fredholmsche Integralgleichungen zweiter Art haben die Gestalt λu = Ku + f (λ ≠ 0) mit dem Integraloperator \begin{eqnarray}(Ku)(x):=\displaystyle \mathop{\int }\limits_{D}k(x,y)u(y)dy{\quad}f\ddot{u}r\,x\in D,\end{eqnarray}

wobei der Kern k und die Inhomogenität f gegeben sind.

Die Picard-Iteration \(u\mapsto {u}^{neu}:={\displaystyle \frac{1}{\lambda }}(Ku-f)\) konvergiert nur für |λ| > ϱ(K), hat aber in vielen wichtigen Anwendungsfällen eine glättende Wirkung: Nichtglatte Funktionen e werden in nur einem Schritt in ein glattes \({\displaystyle \frac{1}{\lambda }}Ke\) abgebildet. Dies ermöglicht die folgende Mehrgitteriteration zweiter Art, wobei von der Hierarchie λu_ℓ = K_ℓu_ℓ + f_ℓ diskreter Gleichungen ausgegangen wird.

function MGM(ℓ, u, f): Gitterfunktion;

if ℓ = 0 then u := (λI − K₀)⁻¹f else

begin \(u:={\displaystyle \frac{1}{\lambda }}({K}_{\ell }* u+f);\) (Picard-Iteration)

d := r(λu_ℓ − K_ℓu − f_ℓ); (Defektrestriktion)

υ := 0; (Startwert für Korrektur)

for i := 1 to 2 do υ := MGM(ℓ − 1, υ, d);

u = u − pυ; (Grobgitterkorrektur)

MGM := u (neue Iterierte)

end; {vgl. [1,§16]}

Wegen der starken Glättung zeigt diese Iteration Konvergenzraten \(O({h}_{\ell }^{\alpha })\) mit α > 0, die bei steigender Dimension (fallender Schrittweite h_ℓ) immer schneller werden.

Der Operator K muß kein Integraloperator mit bekanntem Kern k sein. Die obige Iteration hat die gleichen Eigenschaften für die Fixpunktgleichung λu = Ku + f, solange K entsprechende glättende Wirkung besitzt.

Die nichtlineare Fixpunktgleichung λu = 𝒦(u) läßt sich mit dem Analogon des nichtlinearen Verfahrens aus Abschnitt 5 lösen.

8 Abschließende Bemerkungen

Es gibt eine reiche Literatur zur Mehrgitterbehandlung von Problemen, die von weiteren kritischen Parametern abhängen und mit speziellen Glättungen oder speziellen Grobgittern behandelt werden.

Verschiedene Mehrgittervarianten können (z. B. für positiv definite L_ℓ) auch im Rahmen der Teilraum-Iterationen diskutiert werden. In diesem Falle sind die obigen Algorithmen die multiplikativen Entsprechungen der additiven Teilraum-Iterationen. Letztere haben deutlich andere Eigenschaften, was die Rolle der Glättung betrifft.

Mehrgitterverfahren lassen sich parallelisieren.

Im Falle lokaler (adaptiver) Gitterverfeinerungen läßt sich der Algorithmus anpassen.

Das erste Zweigitterverfahren wurde 1960 von Brakhage für Integralgleichungen beschrieben. Weiteres zur Geschichte der Mehrgitterverfahren findet sich in der Monographie [1] aus dem Jahr 1985. Der Band [3] zur ersten Mehrgitterkonferenz von 1981 enthält einen allgemeinen Einführungsteil. Die Monographie [4] geht auf strömungsdynamische Probleme ein. In [2] ist den Mehrgitterverfahren ein umfangreiches Kapitel gewidmet.

Literatur

[1] W. Hackbusch: Multi-Grid Methods and Applications. SCM 4. Springer-Verlag Berlin, 1985.

[2] W. Hackbusch: Iterative Lösung großer schwachbesetzter Gleichungssysteme, 2. Auflage. Teubner Stuttgart, 1993.

[3] W. Hackbusch und U. Trottenberg (Hrsg.): Multigrid Methods. Lecture Notes in Mathematics 960. Springer-Verlag Berlin, 1982.

[4] P. Wesseling: An Introduction to Multigrid Methods. Wiley Chichester, 1991.