zu Kapitel 13
Transcrição
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