zu Kapitel 13

KAPITEL 13. Große dünnbesetzte LGS, iterative Löser
Erstes Beispielproblem: die diskretisierte Poisson-Gleichung
A1 x = b,
A1 ∈ Rm×m,
m := (n − 1)2 , nh = 1,
wobei

T
−I

−I T
1 
...
A1 = 2 
h 
 ∅

−I
...
−I



∅

...
,

T −I

−I
T
T
4

−1

=

 ∅


−1

4 −1
∅ 

... ... ...
.

−1 4 −1

−1 4
T ∈ R(n−1)×(n−1) und I ist die (n − 1) × (n − 1)-Identitätsmatrix.
Dahmen-Reusken
Kapitel 13
1
Zweites Beispielproblem:
die diskretisierte Konvektions-Diffusionsgleichung
A2x = b,
A2 ∈ Rm×m,
m := (n − 1)2 ,
wobei

T

−s̃I
1 
A2 = 2 
h 
 ∅

mit
−ñI
T −ñI
... ...
−s̃I
...
T
−s̃I


∅ 

,

−ñI

T

T
z̃

−w̃

=

 ∅


−õ

z̃ −õ
∅ 

... ... ...
,

−w̃ z̃ −õ

−w̃ z̃
ñ = ε − hŝ−, s̃ = ε + hŝ+ ,
õ = ε − hĉ−, w̃ = ε + hĉ+ ,
z̃ = ñ + s̃ + õ + w̃ = 4ε + h(|ĉ| + |ŝ|) ,
und
ĉ := cos(β), ĉ+ := max(ĉ, 0), ĉ− := min(ĉ, 0),
ŝ := sin(β), ŝ+ := max(ŝ, 0), ŝ− := min(ŝ, 0).
Dahmen-Reusken
Kapitel 13
2
13.2 Eigenschaften von Steifigkeitsmatrizen
Hochdimensionalität:
Anzahl der Unbekannten ist bei d Ortsvariablen proportional zu h−d.
Dünnbesetztheit:
Steifigkeitsmatrizen sind immer dünnbesetzt, d. h. nur eine gleichmäßig
beschränkte Anzahl von Einträgen pro Zeile ist von Null verschieden.
0
50
100
150
200
0
Dahmen-Reusken
50
100
nz = 1065
150
200
Kapitel 13
3
Blockstruktur:
Bei Diskretisierungen auf regelmäßigen Rechteckgittern haben die sich
ergebenden Steifigkeitsmatrizen oft eine regelmäßige Blockstruktur.
Schlechte Kondition:
Die Konditionszahl von Steifigkeitsmatrizen nimmt oft rasch zu, wenn
die Schrittweite des Gitters kleiner wird.
Symmetrie, Positiv-Definitheit:
Für ein symmetrisches elliptisches Randwertproblem ist die entprechende Steifigkeitsmatrix oft symmetrisch positiv definit.
Diagonaldominanz:
Die Matrizen A1 und A2 sind beide irreduzibel diagonaldominant.
Die durch Finite-Elemente-Methoden und Finite-Volumen-Verfahren
erzeugten Steifigkeitsmatrizen sind im allgemeinen nicht irreduzibel
diagonaldominant.
Dahmen-Reusken
Kapitel 13
4
Fill-in bei einem direkten Löser
Bemerkung 13.2. Als direkter Löser für ein Gleichungssystem mit der
Matrix A1 würde sich die Cholesky-Zerlegung A1 = LDLT anbieten.
Nichtnulleinträge der Matrizen A1 und L:
h
nz(A1 )
nz(L)
1/16
1065
3389
1/32
4681
29821
1/64
19593
250109
1/128
80137
2048509
≈ 5h−2
≈ h−3
Das Verhalten nz(L) ≈ h−3 gegenüber nz(A1 ) ≈ 5h−2 zeigt den ungünstigen Effekt des fill-in“.
”
Dahmen-Reusken
Kapitel 13
5
Nichtnullelemente von L bei der Cholesky-Zerlegung der Matrix A1 :
0
50
100
150
200
0
Dahmen-Reusken
50
100
nz = 3389
150
Kapitel 13
200
6
13.3 Lineare Iterationsverfahren
Aufgabe:
Für A ∈ Rn×n (nichtsingulär) und b ∈ Rn ist das Gleichungssystem
Ax = b
zu lösen. Wir nehmen an, daß n groß (n > 10000) und A dünnbesetzt ist.
Typische Beispiele sind die Matrizen A1 und A2.
Dahmen-Reusken
Kapitel 13
7
Einfacher Ansatz: das Gleichungssystem als Fixpunktgleichung
x = x + C(b − Ax) =: Φ(x),
wobei C ∈ Rn×n eine geeignet zu wählende nichtsinguläre Matrix ist.
Dies führt auf die Fixpunktiteration
xk+1 = Φ(xk ) = xk + C(b − Axk )
= (I − CA)xk + Cb,
k = 0, 1, 2, . . . .
Für den Fehler ek := xk − x∗ ergibt sich
ek+1 = xk+1 − x∗ = Φ(xk ) − Φ(x∗) = (I − CA)ek ,
also
ek = (I − CA)k e0,
Dahmen-Reusken
k = 0, 1, 2, . . .
Kapitel 13
.
8
Satz 13.3. Dieses Verfahren konvergiert für jeden Startwert x0
gegen die Lösung x∗ des Gleichungssystems genau dann, wenn
ρ(I − CA) < 1
gilt, wobei ρ(I − CA) der Spektralradius, also der betragsmäßig
größte Eigenwert, von I − CA ist.
Folgerung 13.5. Für eine beliebige Vektornorm k·k mit zugehöriger Operatornorm gilt:
kxk − x∗k ≤ kI − CAkk kx0 − x∗k,
k = 0, 1, 2, . . .
Die Konvergenz ist folglich für jeden Startwert x0 gesichert, falls
für irgendeine Norm die Bedingung
kI − CAk < 1
erfüllt ist.
Die Größe kI − CAk heißt die Kontraktionszahl der Fixpunktiteration.
Dahmen-Reusken
Kapitel 13
9
Konvergenzrate
ρ(I − CA) ist ein sinnvolles Maß für die Konvergenzgeschwindigkeit.
Je kleiner ρ(I − CA) ist, desto schneller wird der Fehler reduziert. Es
gilt:
σk =
kek k
ke0k
1
k
→ |λ1| = ρ(I − CA) für k → ∞.
Für eine hinreichend große Anzahl k von ausgeführten Iterationsschritten ist ρ(I − CA) etwa die mittlere Fehlerreduktion σk .
Um den Anfangsfehler ke0k um den Faktor 1e zu reduzieren, sind
k = (− ln σk )−1 Iterationsschritte nötig.
Die sogenannte asymptotische Konvergenzrate
− ln(ρ(I − CA))
Ist ein sinnvolles Maß für die asymptotische Konvergenzgeschwindigkeit.
Dahmen-Reusken
Kapitel 13
10
Wie sollte man C wählen?
Es geht um folgenden Balanceakt:
Zu A ∈ Rn×n wähle C ∈ Rn×n so, daß
• A−1 durch C genügend gut in dem Sinne approximiert wird, daß
ρ(I − CA) möglichst klein ist,
• die Operation
y 7→ Cy
mit möglichst geringem Aufwand durchführbar ist.
Beachte:
Bei den meisten iterativen Verfahren wird die Operation y 7→ Cy durchgeführt, ohne daß die Matrix C explizit berechnet wird.
Dahmen-Reusken
Kapitel 13
11
Komplexität eines iterativen Verfahrens
Um unterschiedliche Verfahren miteinander vergleichen zu können, gehen wir davon aus, daß
• eine Klasse von Gleichungssystemen Ax = b vorliegt
(z.B. A1x = b wie oben mit n = 1
h ∈ N beliebig),
• vorgegeben ist, mit welchem Faktor R ein (beliebiger) Startfehler
ke0 k
k
reduziert werden soll (ke k ≤ R ).
Komplexität eines iterativen Verfahrens: die Größenordnung der Anzahl arithmetischer Operationen, die benötigt werden, um für das vorliegende Problem (aus der Problemklasse) eine Fehlerreduktion um
den Faktor R zu bewirken.
Liegt dem Gleichungssystem eine Diskretisierung mit Gitterweite h und
einem Diskretisierungsfehler von der Ordnung O(hℓ ) zugrunde, wäre
R−1 ≈ hℓ sinnvoll.
Dahmen-Reusken
Kapitel 13
12
13.3.2 Das Jacobi-Verfahren
Beim Jacobi- oder Gesamtschrittverfahren:
C = (diag(A))−1.
Die Iterationsvorschrift lautet
xk+1 = (I − D−1A)xk + D−1b.
In Komponentenschreibweise ergibt sich:
Algorithmus 13.7 (Jacobi-Verfahren).
Gegeben: Startvektor x0 ∈ Rn. Für k = 0, 1, . . . berechne:
n
X
k+1
ai,ixi
ai,j xkj + bi,
=−
j=1
j6=i
i = 1, 2, . . . , n.
Beim Jacobi-Verfahren wird die i-te Gleichung nach der i-ten Unbekannten xi aufgelöst, wobei für die übrigen Unbekannten (xj , j 6= i)
Werte aus dem vorherigen Iterationsschritt verwendet werden.
Dahmen-Reusken
Kapitel 13
13
Rechenaufwand. Der Rechenaufwand pro Iterationsschritt ist beim
Jacobi-Verfahren angewandt auf eine dünnbesetzte Matrix A ∈ Rn×n
vergleichbar mit einer Matrix-Vektor-Multiplikation Ax, beansprucht
also O(n) Operationen.
Konvergenz
Satz 13.9. Für das Jacobi-Verfahren gelten folgende Konvergenzkriterien:
• Falls sowohl A als auch 2D − A symmetrisch positiv definit sind,
folgt
ρ(I − D−1A) < 1.
• Falls A irreduzibel diagonaldominant ist, gilt
ρ(I − D−1A) ≤ kI − D−1Ak∞ < 1.
Dahmen-Reusken
Kapitel 13
14
Beispiel 13.10.
Das Diffusionsproblem mit der Matrix A1 . Es gilt
ρ(I − CA) = ρ(I − D−1A1)
2
= max{ |1 − 1
4 h λ| | λ Eigenwert von A1 }
1 π 2h2 .
= 1 − 2 sin2( 1
πh)
=
cos(πh)
≈
1
−
2
2
Für die asymptotische Konvergenzrate gilt somit
2h2) ≈ 1 π 2h2.
π
− ln(ρ(I − D−1A1)) ≈ − ln(1 − 1
2
2
Um einen Startfehler um einen Faktor R zu reduzieren, sind etwa
− ln R
2
≈
ln R
−1
2
2
ln ρ(I − D A1 )
π h
Iterationsschritte erforderlich.
K=
Beachte: Die geschätzte Anzahl der notwendigen Iterationsschritte
wächst in Abhängigkeit der Schrittweite h wie die Konditionszahlen
der betreffenden Matrizen.
Dahmen-Reusken
Kapitel 13
15
Sei # die Anzahl von Iterationsschritten, die zur Reduktion des Startfehlers um einen Faktor R = 103 benötigt werden, und K die theoretische Schätzung von # aus:
− ln 103
2
K=
≈ 2 2 ln 103.
ln(cos πh)
π h
Ergebnisse:
h
#
K
1/40
2092
2237
1/80
8345
8956
1/160
33332
35833
1/320
133227
143338
Komplexität. Da m ∼ h−2, folgt, daß K ∼ m Iterationsschritte benötigt
werden. Da jeder Schritt einen zu m proportionalen Aufwand erfordert,
ergibt sich, daß die Komplexität des Jacobi-Verfahrens (für diese Problemstellung) etwa c m2 ist.
Dahmen-Reusken
Kapitel 13
16
Beispiel 13.11.
Das Konvektions-Diffusionsproblem mit der Matrix A2.
Wir führen für β = π
6 ein Experiment wie in Beispiel 13.10 durch.
Ergebnisse (#):
h
ε=1
ε = 10−2
ε = 10−4
1/40
2155
194
75
1/80
8611
587
148
1/160
34415
1967
293
1/320
137597
7099
597
Für den Fall ε = 1 (dominante Diffusion) gilt κ2(A2) ∼ h12 und für
ε = 10−4 (dominante Konvektion) gilt κ2(A2) ∼ 1
h.
Diese Beziehungen entsprechen den Wachstumsfaktoren 4 und 2 in
den Zeilen für ε = 1 bzw für ε = 10−4.
Dahmen-Reusken
Kapitel 13
17
13.3.3 Das Gauß-Seidel-Verfahren
Zerlegung:
A = D − L − U.
Mit C := (D − L)−1 ergibt sich:
Äquivalent:
xk+1 = (I − (D − L)−1A)xk + (D − L)−1b.
(D − L)xk+1 = Uxk + b.
In Komponentenschreibweise heißt dies
Algorithmus 13.12 (Gauß-Seidel-Verfahren).
Gegeben: Startvektor x0 ∈ Rn. Für k = 0, 1, . . . berechne:
−1
xk+1
=
a
i
i,i bi −
i−1
X
j=1
ai,j xk+1
−
j
n
X
ai,j xkj ,
j=i+1
i = 1, 2, . . . , n.
Bei der Berechnung der i-ten Komponente von xk+1 verwendet man
die bereits vorher berechneten Komponenten der neuen Annäherung.
Dahmen-Reusken
Kapitel 13
18
Rechenaufwand. Für eine dünnbesetzte Matrix A ∈ Rn×n ist
der Rechenaufwand pro Iterationsschritt bei der Gauß-SeidelMethode vergleichbar mit dem Aufwand beim Jacobi-Verfahren,
beträgt also O(n) Operationen.
Konvergenz
Satz 13.13. Für das Gauß-Seidel-Verfahren gelten folgende
Konvergenzkriterien:
• Falls A symmetrisch positiv definit ist, folgt
ρ(I − (D − L)−1A) < 1.
• Falls A irreduzibel diagonaldominant ist, gilt
ρ(I − (D − L)−1A) ≤ kI − (D − L)−1Ak∞ < 1.
Dahmen-Reusken
Kapitel 13
19
Beispiel 13.15.
Das Diffusionsproblem mit der Matrix A1 . Dafür gilt:
ρ(I − CA1) = ρ(I − (D − L)−1A1) = (ρ(I − D−1A1))2
Hieraus ergibt sich:
ρ(I − CA1) = cos2(πh) ≈ 1 − π 2h2 .
− ln(ρ(I − (D − L)−1A1)) ≈ − ln(1 − π 2h2) ≈ π 2h2.
Um einen Startfehler um einen Faktor R zu reduzieren sind (asymptotisch) etwa K Iterationsschritte erforderlich, wobei
K=
− ln R
1
≈
ln R.
−1
2
2
ln(ρ(I − (D − L) A1))
π h
Ergebnisse:
h
#
K
Dahmen-Reusken
1/40
1056
1119
1/80
4193
4478
1/160
16706
17916
Kapitel 13
1/320
66694
71669
20
Komplexität
Für das Gauß-Seidel-Verfahren angewandt auf die diskrete PoissonGleichung
A1x = b,
m×m
A1 ∈ R
,
2
m = (n − 1) ,
1
n=
h
ist die Komplexität c m2 Operationen.
Dahmen-Reusken
Kapitel 13
21
Beispiel 13.16.
Die Resultate des Gauß-Seidel-Verfahrens hängen von der Anordnung
der Unbekannten ab.
Beispiel: Die diskrete Konvektions-Diffusionsgleichung mit β = π
6.
1 , R = 103 und x0, b wie in Beispiel 13.11.
h = 160
Gauß-Seidel-Verfahren mit Standardanordnung:
ε
#
1
17197
10−2
856
10−4
14
Gitterpunkte in umgekehrter Reihenfolge:
ε
#
1
17220
10−2
1115
10−4
285
Für ein Problem, bei dem die Konvektion dominant ist, ist es für
das Gauß-Seidel-Verfahren vorteilhaft, bei der Anordnung der Unbekannten (Gitterpunkte) die Strömungsrichtung zu berücksichtigen.
Dahmen-Reusken
Kapitel 13
22
13.3.4. SOR-Verfahren
Der Iterationsschritt beim Gauß-Seidel Verfahren läßt sich auch als
i−1
n
X
X
k+1
−1
k
xk+1
=
x
a
x
ai,j xkj − bi ,
−
a
+
i,j j
i
i
i,i
j=1
j=i
i = 1, 2, . . . , n,
darstellen.
Algorithmus 13.17 (SOR-Verfahren).
Gegeben: Startvektor x0 ∈ Rn, Parameter ω ∈ (0, 2).
Für k = 0, 1, . . . berechne:
i−1
n
X
X
k+1
−1
k
k
xk+1
=
x
−
ωa
a
x
a
x
+
i,j j
i,j j − bi ,
i
i
i,i
j=1
j=i
i = 1, 2, . . . , n.
Das SOR-Verfahren hat folgende Matrix-Darstellung:
(D − ω L)xk+1 = Dxk − ω(D − U)xk + ω b
Dahmen-Reusken
Kapitel 13
23
Rechenaufwand. Beim SOR-Verfahren ist der Rechenaufwand
pro Iterationsschritt vergleichbar mit dem Aufwand beim GaußSeidel-Verfahren, also O(n) Operationen für ein dünnbesetztes
A ∈ Rn×n.
Konvergenz
1 D − L)−1A die Iterationsmatrix des
Satz 13.18. Sei Mω := I − ( ω
SOR-Verfahrens. Es gilt:
• ρ(Mω ) ≥ |ω − 1| .
• Für A s.p.d. gilt:
ρ(Mω ) < 1
für alle ω ∈ (0, 2).
• Sei A irreduzibel diagonaldominant mit ai,j ≤ 0 für alle i 6= j
und ai,i > 0 für alle i. Dann gilt:
ρ(Mω ) < 1
Dahmen-Reusken
für alle ω ∈ (0, 1].
Kapitel 13
24
Beispiel 13.19.
Die Diffusionsgleichung wie in den Beispielen 13.10 und 13.15 für den
1 .
Fall h = 160
Anzahl der Iterationen in Abhängigkeit von ω:
5
10
4
10
3
10
2
10
1
Dahmen-Reusken
1.1
1.2
1.3
1.4
1.5
1.6
1.7
Kapitel 13
1.8
1.9
2
25
Die Konvektions-Diffusionsgleichung wie in den Beispielen 13.11 und
1 .
13.16 für den Fall ε = 10−2, h = 160
Anzahl der Iterationen in Abhängigkeit von ω:
4
10
3
10
2
10
1
10
0.9
Dahmen-Reusken
1
1.1
1.2
1.3
1.4
1.5
1.6
Kapitel 13
1.7
1.8
1.9
26
Optimaler Wert von ω
Der optimale Wert von ω ist stark problemabhängig.
Für die meisten Probleme ist dieser optimale Wert nicht bekannt.
Eine Ausnahme bildet die diskretisierte Poisson-Gleichung (Matrix A1):
Satz 13.20.
Wir betrachten die diskretisierte Poisson-Gleichung A1x = b.
Sei µ := ρ(I − D−1A1) < 1 der Spektralradius der Iterationsmatrix
des Jacobi-Verfahrens.
Sei Mω die Iterationsmatrix des SOR-Verfahrens.
Dann ist ρ(Mω ) für den Relaxationsparameter
ωopt :=
optimal und
2
1+
q
1 − µ2

=1+

µ
1+
q
1 − µ2
2


ρ(Mωopt ) = ωopt − 1.
Dahmen-Reusken
Kapitel 13
27
Komplexität.
Für die diskretisierte Poisson-Gleichung A1x = b ergibt sich beim
SOR-Verfahren mit dem optimalen ω-Wert eine sehr große Komplexitätsverbesserung im Vergleich zum Jacobi- und zum Gauß-SeidelVerfahren.
ρ(Mωopt ) = ωopt − 1 =
cos(πh)
1 + sin(πh)
!2
1 − sin(πh)
=
≈ 1 − 2πh.
1 + sin(πh)
1
ln R √
ln R
≈
ln R ≈
m.
K=−
ln ρ(Mωopt )
2πh
2π
Da der Aufwand pro Iteration proportional zu m ist, hat dieses Verfahren eine Komplexität (für die vorliegende Problemstellung) von
c m1.5
Dahmen-Reusken
Operationen.
Kapitel 13
28
Beispiel 13.21.
Poisson-Gleichung A1x = b mit x0, b und R wie in Beispiel 13.10.
Wir verwenden das SOR-Verfahren mit ω = ωopt.
Ergebnisse:
h
#
K
Dahmen-Reusken
1/40 1/80 1/160 1/320
73
146
292
585
44
88
176
352
Kapitel 13
29
SSOR-Verfahren
Eine SSOR-Iteration sieht also wie folgt aus:
i−1
X
n
1
X
k+ 2
ai,j xkj − bi , i = 1, 2, . . . , n
+
ai,j xj
j=i
j=1
X
n
i
1
1
X
k+
k+
k+1
2 − ω a−1
xk+1
a
x
ai,j xj 2 − bi , n ≥ i ≥ 1
=
x
+
i,j j
i
i
i,i
j=1
j=i+1
1
k+ 2
= xki − ω a−1
xi
i,i
Die Iterationsmatrix dieser Methode ist
Mω = I − Cω A,
Cω := ω(2 − ω)(D − ω U)−1D(D − ω L)−1 .
Wenn die Matrix A symmetrisch positiv definit ist, ist für ω ∈ (0, 2)
die Matrix Cω in der Iterationsmatrix der SSOR-Methode auch symmetrisch positiv definit.
Dahmen-Reusken
Kapitel 13
30
13.4 Die Methode der konjugierten Gradienten
Wenn A ∈ Rn×n s.p.d. ist, gelten die folgenden zwei grundlegenden
Eigenschaften:
• Für x, y ∈ Rn definiert hx, yiA := xT Ay ein Skalarprodukt.
• Sei
T Ax − bT x,
f (x) := 1
x
2
b, x ∈ Rn.
Dann gilt, daß f ein eindeutiges Minimum hat und
Ax∗ = b ⇔ f (x∗ ) = minn f (x).
x∈R
Lemma 13.22. Sei f wie oben. Die Richtung des steilsten Abstiegs
von f an der Stelle x, d. h. s ∈ Rn so, daß die Richtungsableitung
s
d
s T
=
(∇f
(
x
))
f x+t
dt
ksk2 t=0
ksk2
minimal ist, wird durch s = −∇f (x) = b − Ax gegeben.
Dahmen-Reusken
Kapitel 13
31
Sei U ein Unterraum von Rn . Es gilt:
f (x̂) = min f (x)
x∈U
⇐⇒
kx̂ − x∗kA = min kx − x∗kA
x∈U
Das folgende Lemma zeigt, wie man eine solche Aufgabe löst.
Lemma 13.24. Sei Uk ein k-dimensionaler Teilraum von Rn,
0, p1, . . . , pk−1 eine A-orthogonale Basis dieses Teilraumes:
und
p
D
E
i
j
p ,p
= 0 für i 6= j. Sei v ∈ Rn, dann gilt für uk ∈ Uk :
A
kuk − vkA = min ku − vkA
u∈Uk
genau dann, wenn uk die A-orthogonale Projektion von v auf Uk ist.
Außerdem hat uk die Darstellung
uk =
k−1
X
j=0
Dahmen-Reusken
D
D
v , pj
E
pj , pj
EA
pj .
A
Kapitel 13
32
Herleitung der CG-Methode
Der Einfachheit halber: x0 = 0.
Die folgenden Teilschritte definieren die beim CG-Verfahren erzeugten
Näherungen x1, x2, . . . der Lösung x∗:
U1 := span{r0},
Für k = 1, 2, 3, . . . , falls rk−1 = b − Axk−1 6= 0 :
CGa : Bestimme A-orthogonale Basis p0, . . . , pk−1 von Uk .
CGb : Bestimme xk ∈ Uk , so daß
kxk − x∗kA = min kx − x∗kA.
x∈Uk
CGc : Erweiterung des Teilraumes:
Uk+1 := span{p0, . . . , pk−1, rk }, wobei rk := b − Axk .
Dahmen-Reusken
Kapitel 13
33
Erläuterung dieser Teilschritte:
CGa:
Die A-orthogonale Basis von Uk wird benötigt, um die Annäherung xk in Teilschritt CGb effizient und stabil zu berechnen.
CGb: xk ist die (bezüglich k · kA) optimale Approximation von x∗ in Uk .
CGc: Uk+1 = Uk ⊕ span{rk }:
Die Erweiterung des Raumes Uk ist optimal in dem Sinne, daß rk
an der Stelle xk die Richtung des steilsten Abstiegs von f ist
Dahmen-Reusken
Kapitel 13
34
Verfahren der konjugierten Gradienten (CG)
Es ergibt sich der berühmte
Algorithmus 13.27 (Verfahren der konjugierten Gradienten).
Gegeben: A ∈ Rn×n s.p.d., b ∈ Rn , Startvektor x0 ∈ Rn,
β−1 := 0. Berechne r0 = b − Ax0. Für k = 1, 2, . . . , falls rk−1 6= 0 :
D
pk−1 = rk−1 + βk−2pk−2, βk−2 = D
xk = xk−1 + αk−1pk−1,
rk = rk−1 − αk−1Apk−1.
rk−1, rk−1
E
E (k ≥ 2),
k−2
k−2
r
,r
D
E
k−1
k−1
r
,r
E,
αk−1 = D
k−1
k−1
p
, Ap
Die CG-Methode ist ein nichtlineares Verfahren:
ek+1 = ψ(ek ),
wobei ψ eine nichtlineare Funktion ist.
Dahmen-Reusken
Kapitel 13
35
Rechenaufwand. Im Algorithmus 13.27 werden pro Iterationsschritt nur eine Matrix-Vektor-Multiplikation, zwei Skalarprodukte und drei Vektor-Operationen der Form x + αy benötigt.
Der Aufwand pro Iterationsschritt ist vergleichbar mit dem des
Jacobi- oder Gauß-Seidel-Verfahrens, also O(n) Operationen für
ein dünnbesetztes A ∈ Rn×n.
Konvergenz
Satz 13.29. Gegeben sei Ax = b mit A ∈ Rn×n s.p.d. Sei x∗ die
Lösung von Ax = b. Dann gilt für die durch Algorithmus 13.27
gelieferten Näherungen xk
q
k
 κ2(A) − 1 
k
∗
0
∗
kx − x kA ≤ 2  q
 kx − x kA ,
κ2(A) + 1
Dahmen-Reusken
Kapitel 13
k = 0, 1, 2, . . . .
36
Beispiel 13.30.
Das Diffusionsproblem A1x = b.
Für die Konditionszahl der Matrix A1 gilt
cos2( 1
2 πh)
2 2
≈
κ2(A1) =
,
1
2
πh
sin ( 2 πh)
also
q
2 −1
1 πh
1
−
2
ρ̂ := q
≈ πh
=
≈ 1 − πh.
2 +1
1
1 + 2 πh
κ2(A) + 1
πh
κ2(A) − 1
K := −
Ergebnisse:
h
#
Dahmen-Reusken
1/40
65
1
ln(2R)
≈
ln(2R)
ln(1 − πh)
πh
1/80
130
1/160
262
Kapitel 13
1/320
525
37
Superlineare Konvergenz
1 wird die Fehlerreduktion in der Energie-Norm
Für den Fall h = 80
kxk − x∗kA
,
ρk :=
k−1
∗
kx
− x kA
in den ersten 250 Iterationsschritten dargestellt.
1
0.95
0.9
0.85
0.8
0.75
0.7
0.65
0
Dahmen-Reusken
50
100
150
200
Kapitel 13
250
38
Komplexität. Das CG-Verfahren für die diskrete Poissongleichung:
A1x = b,
A1 ∈ Rm×m,
m = (n − 1)2,
1
n= .
h
Als Fehlerreduktionsfaktor wird R = 103 gewählt.
Die Komplexität des CG-Verfahrens (für diese Problemstellung) ist
c m1.5
Operationen,
also von der gleichen Größenordnung wie beim SOR-Verfahren mit
optimalem ω-Wert.
Ein großer Vorteil der CG-Methode im Vergleich zum SOR-Verfahren
ist, daß sie keinen vom Benutzer zu wählenden Parameter enthält.
Dahmen-Reusken
Kapitel 13
39
13.5 Vorkonditionierung
Idee: Die Matrix A wird mit einer geeigneten zu wählenden symmetrisch positiv definiten Matrix W vorkonditioniert.
Da die Matrix W symmetrisch positiv definit ist, existiert die CholeskyZerlegung
W = LDLT =: L1LT1 ,
Wir betrachten das transformierte System
Ãx̃ = b̃
mit
−T
à := L−1
AL
1
1 ,
x̃ := LT1 x,
b̃ = L−1
1 b .
Die Matrix à ist symmetrisch positiv definit.
Der CG-Algorithmus ist also auf dieses Problem anwendbar.
Dahmen-Reusken
Kapitel 13
40
Wenn man den CG-Algorithmus für das transformierte System in die
ursprünglichen Variablen x = L−T
1 x̃ umschreibt, ergibt sich folgender
Algorithmus 13.32 (PCG-Verfahren).
Gegeben: A, W ∈ Rn×n s.p.d., b ∈ Rn , Startvektor x0 ∈ Rn,
β−1 := 0. Berechne r0 = b − Ax0, z0 = W−1r0 (löse Wz0 = r0).
Für k = 1, 2, 3, . . . , falls rk−1 6= 0 :
pk−1 = zk−1 + βk−2pk−2,
xk = xk−1 + αk−1pk−1,
D
βk−2 = D
αk−1 = D
zk−1, rk−1
E
zk−2, rk−2
D
E
k−1
k−1
z
,r
pk−1, Apk−1
rk = rk−1 − αk−1Apk−1,
zk = W−1rk
(löse Wzk = rk ).
(k ≥ 2),
E
E,
Beachte: nur die Matrizen A und W treten auf und nicht Ã, L̃1.
Dahmen-Reusken
Kapitel 13
41
Die Konvergenz des PCG-Verfahrens wird durch die Konditionszahl
−T
−1 A)
κ2(Ã) = κ2(L−1
AL
)
=
κ
(
W
2
1
1
bedingt.
Um eine gute Effizienz des PCG-Verfahrens zu gewährleisten, ist W
so zu wählen, daß
• κ2(W−1A) möglichst klein ist,
• die Lösung von
Wzk = rk
mit möglichst geringem Aufwand (O(n) Operationen) berechnet
werden kann.
Manchmal ist es schon hilfreich, W = diag(A) zu nehmen.
Dahmen-Reusken
Kapitel 13
42
Unvollständige Cholesky-Zerlegung als Vorkonditionierung
A läßt sich in der Form
A = L1LT1
mit einer unteren Dreiecksmatrix L1 zerlegen (Cholesky).
Um Dünnbesetztheit zu erhalten greift man auf eine unvollständige
Cholesky-Zerlegung zurück. Sei
E := {(i, j) | ai,j 6= 0}
Es wird eine näherungsweise Faktorisierung konstruiert:
A = L̃1L̃T1 + R,
mit:
• L̃1 eine untere Dreiecksmatrix,
• (L̃1)i,j = 0 für (i, j) ∈
/ E.
Die Konstruktion einer näherungsweisen Faktorisierung A ≈ L̃1L̃T
1 beruht auf der unvollständigen Durchführung einer Methode zur Berechnung der vollständigen Cholesky-Zerlegung.
Dahmen-Reusken
Kapitel 13
43
Algorithmus 13.34 (Unvollständige Cholesky-Methode).
Gegeben: A ∈ Rn×n s.p.d., Muster E.
Berechne für k = 1, 2, . . . , n :
l̃k,k =
1
X′
2
2
ak,k −
;
l̃k,j
j
für i = k + 1, . . . , n : falls (i, k) ∈ E,
l̃i,k = ai,k −
X′′
˜
li,j l̃k,j
j
l̃k,k ;
Hierbei sind die Summen nur über Indizes aus dem Muster zu führen:
X′
j
=
k−1
X
j=1,(k,j)∈E
,
X′′
j
=
k−1
X
.
j=1,(i,j)∈E,(k,j)∈E
Im PCG-Algorithmus: W = L̃1L̃T
1.
−T
Für viele Probleme: κ2(W−1A) = κ(L̃−1
A
L̃
1
1 ) ≪ κ(A).
k = rk sind einfach lösbar.
Die Systeme L̃1L̃T
z
1
Dahmen-Reusken
Kapitel 13
44
Algorithmus 13.36 (Modifiziertes unvollständiges Cholesky)
Gegeben: A ∈ Rn×n s.p.d., Muster E. Berechne für k = 1, 2, . . . , n :
l̂k,k = ak,k −
X′
ˆ
lk,j
j
1
2
;
für i = k + 1, . . . n :
falls (i, k) ∈ E :
l̂i,k = ai,k −
X′′
l̂i,j l̂k,j
j
l̂k,k ;
sonst:
ai,i = ai,i −
X′′
l̂i,jˆ
lk,j ;
j
Man kann zeigen, daß für L̂1 := (l̂i,j )1≤i,j≤n:
(L̂1L̂T
1 )i,j = ai,j
n
X
für (i, j) ∈ E, i 6= j,
n
X
T
(L̂1L̂1 )i,j =
ai,j
j=1
j=1
Dahmen-Reusken
für alle i.
Kapitel 13
45
Beispiel 13.37.
Die diskretisierte Poisson-Gleichung.
PCG-Verfahren:
ICCG: CG + unvollständige Cholesky Vorkonditionierung.
MICCG: CG + mod. unvollständige Cholesky Vorkonditionierung.
#: Anzahl der Iterationsschritte, die zur Reduktion des Startfehlers
kx0 − x∗k2 um einen Faktor R = 103 benötigt werden (x0 := 0).
Ergebnisse:
W = L̃1L̃T1 ,
W = L̂1L̂T1 ,
Dahmen-Reusken
h
#
#
1/40
20
8
1/80
40
11
1/160
79
14
Kapitel 13
1/320
157
20
46
Komplexität. PCG-Verfahren für die diskrete Poissongleichung.
Als Fehlerreduktionsfaktor wird R = 103 gewählt.
Die Konvergenz der ICCG-Methode ist schneller als die der Methode
ohne Vorkonditionierung. Die Komplexität ist aber für beide Methoden
c m1.5
Operationen,
wobei die Konstante c beim PCG-Verfahren kleiner ist.
Man kann zeigen, daß die MICCG-Methode die Komplexität
c m1.25
Operationen
hat.
Dahmen-Reusken
Kapitel 13
47
SSOR-Verfahren als Vorkonditionierung
Sei
xk+1 = xk + C(b − Axk ) ,
A symmetrisch positiv definit.
Man kann die Matrix C als eine Näherung für A−1 interpretieren.
Deshalb liegt der Ansatz
W = C−1
als Vorkonditionierung für das CG-Verfahren nahe.
Allerdings muß die Matrix W symmetrisch positiv definit sein.
Beispiele:
- die Jacobi-Methode, mit C−1 = diag(A).
- die SSOR-Methode.
In PCG muß zk = W−1rk also zk = Crk berechnet werden.
zk ist das Resultat einer Iteration des linearen iterativen Verfahrens
angewandt auf Az = rk mit Startvektor 0:
b = rk , x0 = 0
Dahmen-Reusken
⇒
x1 = Crk .
Kapitel 13
48
Beispiel 13.39.
Die diskretisierte Poisson-Gleichung.
Das PCG-Verfahren mit der SSOR-Methode als Vorkonditionierung.
Als Fehlerreduktionsfaktor wird R = 103 gewählt; x0 = 0.
Ergebnisse:
h
ω = 2/(1 + sin(πh))
#
Dahmen-Reusken
1/40
1.854
11
1/80
1.924
16
Kapitel 13
1/160
1.961
22
1/320
1.981
32
49