9.6.1 Verfahren der konjugierten Gradienten (CG-Verfahren)

Verfahren der konjugierten Gradienten (CG-Verfahren) sind effiziente Lösungsalgorithmen für symmetrische, positiv definite Systeme . Sie basieren auf der Verwendung von "Korrekturrichtungen" bei der Aktualisierung der Iterationen und Residuen. Dabei muß jeweils nur eine geringe Anzahl von Vektoren gespeichert werden.

Damit bestimmte Orthogonalitätsbedingungen der Vektorfolgen erfüllt bleiben, werden bei jeder Iteration zwei innere Produkte zur Berechnung von skalaren Korrekturgrößen gebildet. Bei symmetrischen, positiv definiten linearen Systemen bewirken diese Bedingungen, daß der Abstand zur exakten Lösung in der verwendeten Norm minimiert wird.

Die Iterationsvektoren werden in jedem Schritt um den-fachen Korrekturvektor p⁽ⁱ⁾ verändert:

Dementsprechend werden die Residuen aktualisiert:

Die Parameterwahl

minimiert über alle . Die Korrekturrichtung wird unter der Verwendung der Residuen modifiziert:

Dabei sichert die Wahl

daß p⁽ⁱ⁾ und Ap^(i-1) und damit auch r⁽ⁱ⁾ und r^(i-1) orthogonal sind. Man kann sogar zeigen, daß auf diese Art die Orthogonalität von p⁽ⁱ⁾ bzw r⁽ⁱ⁾ zu allen vorhergehenden Ap⁽ⁱ⁾ bzw r⁽ⁱ⁾ und gewährleistet ist.

Theory

CG-Verfahren ohne Vorkonditionierrung konstruieren x⁽ⁱ⁾ als Element des um den Startvektor x ^(o) verschobenen Krylov-Raums K_i(r^(o), A)

durch x(i) minimiert wird, wobei x* die exakte Lösung von Ax = b bezeichnet. Die Existenz des Minimums

ist aber nur für symetrische und positiv definite Matrizen A gesichert.

Konvergenzverhalten

Wie hier festgestellt wurde, liefert das CG-Verfahren - soferne keine Rundungsfehlereffekte auftreten - in maximal n Schritten die exakte Lösung x* eines linearen Gleichungsystems mit symmetrischer und positiv definiter Matrix. Da aber in der Praxis Rundungsfehler nicht zu vermeiden sind, verwendet man das CG-Verfahren nicht als direktes, sondern als iteratives Verfahren, dessen Konvergenzgeschwindigkeit durch

charakterisiert ist (Deuflhard, Hohmann [41], Golub,Ortega [47]).

Vorkonditionierung

Die Konvergenzgeschwindigkeit des CG-Verfahrens hängt von der Kondition der Matrix A ab. Für eine Matrix mit der optimalen Kondition, und für. Je schlechter das Gleichungssystem konditioniert ist, desto langsamer wird also die Konvergenz des CG-Verfahrens. Die Idee der Vorkonditionierung beruht nun darauf, von dem ursprünglich gegebenen Gleichungssystem mit Hilfe einer regulären Matrix M zu einem äquivalenten System überzugehen:

.

Je besser M die Matrix A approximiert, desto kleiner wird und desto rascher konvergiert daß CG-Verfahren, wenn man es auf das neue Gleichungsystem anwendet. Für M = A gilt , nur ist diese Wahl sinnlos, da sie ebenfalls die Lösung eines linearen Gleichungssystem erfordert. Eine praktisch brauchbare Vorkonditionierung darf keinen unzulässig hohen Aufwand erfordern, muß aber eine signifikante Konvergenzbeschleunigung erzielen, Eine ausführliche Diskussion praktisch erprobter Methoden zur Vorkonditionierung findet sich hier .

Das CG-Verfahren mit Vorkonditionierung hat folgende Grundform:

Aus der Abschätzung erkennt man, daß die Anzahl der Iterationen zur relativen Reduktion des Fehlers um c proportional zu ist, also lineare Konvergenz des CG-Verfahrens vorliegt.

Besitzen größter und kleinster Eigenwert der Matrix M ^-1 A sehr unterschiedliche Größe, so ist häufig sogar überlineare Konvergenz feststellbar: die Konvergenzrate wächst pro Iteration. Dieses Phänomen ist dadurch erklärbar, daß CG-Verfahren dazu tendieren, zuerst Fehlerkomponenten zu reduzieren, die in der Richtung der zu den extremen Eigenwerten gehörigen Eigenvektoren liegen. Sind diese eliminiert, setzt sich das Verfahren so fort, als ob diese Eigenwerte nicht existierten, wodurch die Konvergenzrate von einem reduzierten System mit (viel) kleinerer Konditionszahl abhängt. Genaue Analysen dieses Phänomens findet man bei Van der Sluis, Van der Vorst [3841].