Lexikon der Mathematik: Mehrgitterverfahren
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
Im einfachsten Fall kann zur Diskretisierung ein Differenzenverfahren mit der Gitterweite h verwendet werden. Die diskrete Gleichung lautet
Sei h0, h1 = h0/2, …, hℓ = h0/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
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 𝒯0, 𝒯1, …, 𝒯ℓ, …, \({\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
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
wirken als Glättungsiteration, d. h. sie reduzieren die oszillierenden Fehleranteile wesentlich besser als die glatten. Im symmetrisch positiv definiten Fall ist ∥Lh∥ = λn der größte Eigenwert. Die (oszillierenden) Eigenvektoren von Lh 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 Lh und LH.
Zuerst wird aus dem Startwert uh mit wenigen Glättungsschritten \({\tilde{u}}_{h}\) erzeugt. Die Zahl der Glättungsschritte ist oft 2 oder 3. Der Defekt
wird berechnet. Offenbar ist Lhδuh = dh die Gleichung für die exakte Korrektur: \({u}_{h}:={\tilde{u}}_{h}-\delta {u}_{h}\) erfüllt
Natürlich ist die direkte Lösung von Lhδuh = dh ebenso schwierig wie diejenige von Lhuh = fh. Da die Korrektur δuh aber gleichzeitig der Fehler \({\tilde{u}}_{h}-{u}_{h}^{exakt}\) und daher glatt ist, kann Lhδuh = dh näherungsweise im groben Gitter gelöst werden. Im Zweigitterfall wird
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
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 δuh ist und \({u}_{h}^{exakt}={\tilde{u}}_{h}-\delta {u}_{h}\) gilt, wird
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
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 Lhuh = fh. Am Rand des Quadrates 5 werden Dirichlet-Werte vorgeschrieben. fh und die Randwerte seien so gewählt, daß sich uh(x, y) = x2 + y2 als diskrete Lösung von Lhuh = fh ergibt. Da Lh positiv definit ist, kann die gröbstmögliche Schrittweite h0 := 1/2 als Schrittweite der Stufe ℓ = 0 gewählt werden. Die weiteren Gitterweiten sind daher hℓ = 2−1−
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
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 ℒ0(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
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
(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
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 − K0)−1f 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.
Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.