Verfahren der konjugierten Gradienten

Das CG-Verfahren (von engl. \(\displaystyle \bm{c}\)onjugate \(\displaystyle \bm{g}\)radients oder auch Verfahren der konjugierten Gradienten) ist eine effiziente numerische Methode zur Lösung von großen, symmetrischen, positiv definiten Gleichungssystemen der Form \(\displaystyle Ax=b\). Es gehört zur Klasse der Krylow-Unterraum-Verfahren. Das Verfahren konvergiert nach spätestens \(\displaystyle m\) Schritten. Insbesondere ist es aber als iteratives Verfahren interessant, da der Fehler monoton fällt.
 
 

Idee des CG-Verfahrens

Die Idee des CG-Verfahrens besteht darin, dass das Maximieren von
\(\displaystyle E(x):=\langle b,x\rangle-\dfrac12\langle Ax,x\rangle\)
äquivalent zum Lösen von \(\displaystyle Ax=b\) ist.
Der Gradient von \(\displaystyle E\) an der Stelle \(\displaystyle x^{(k)}\) ist gerade \(\displaystyle g^{(k)}=b-Ax^{(k)}\) und somit bei großen, dünn besetzten Matrizen schnell zu berechnen. Die Idee des CG-Verfahrens ist es nun, anstelle in Richtung \(\displaystyle g^{(k)}\) in eine andere Richtung \(\displaystyle d^{(k)}\) die Funktion \(\displaystyle E\) zu maximieren. Die Richtungen \(\displaystyle d^{(k)}\) sind dabei alle \(\displaystyle A\)-konjugiert, d.h. es gilt
\(\displaystyle \langle Ad^{(i)},d^{(j)}\rangle=0\qquad\forall i\neq j\).
Weiter realisieren alle \(\displaystyle x^{(k)}\) das Maximum von \(\displaystyle E\) in dem affinen Raum
\(\displaystyle V_k:=x^{(0)}+\operatorname{span}\left(\{d^{(1)},\ldots,d^{(k)}\}\right)\).
Dabei handelt es sich also um den Vektorraum, der durch die Vektoren \(\displaystyle d^{(1)},\ldots,d^{(k)}\) aufgespannt und um \(\displaystyle x^{(0)}\) verschoben wird.
Da die Vektoren \(\displaystyle d^{(k)}\) alle \(\displaystyle A\)-konjugiert sind, ist die Dimension von \(\displaystyle V_k\) gerade \(\displaystyle k\). Ist also \(\displaystyle A\) eine \(\displaystyle m\times m\)-Matrix, so terminiert das Verfahren nach spätestens \(\displaystyle m\) Schritten, falls korrekt gerechnet wird. Numerische Fehler können durch weitere Iterationen eliminiert werden. Hierzu betrachtet man den Gradienten \(\displaystyle g^{(k)}\), der den numerischen Fehler, d.h. das Residuum angibt. Unterschreitet die Norm dieses Residuums einen gewissen Schwellenwert, wird das Verfahren abgebrochen.
Das Verfahren baut sukzessive eine orthogonale Basis für den \(\displaystyle \mathbb R^m\) auf und minimiert in die jeweilige Richtung bestmöglich.

CG-Verfahren ohne Vorkonditionierung

Zunächst wählt man ein \(\displaystyle x^{(0)}\in\mathbb{R}^m\) beliebig und berechnet:
\(\displaystyle g^{(0)} = b - A x^{(0)}\)
\(\displaystyle d^{(0)} = -g^{(0)} \)
Für \(\displaystyle k = 0,1,\dots \) setzt man:
Finde von \(\displaystyle x^{(k)}\) in Richtung \(\displaystyle d^{(k)}\) das Minimum \(\displaystyle x^{(k+1)}\) und aktualisiere den Gradienten bzw. das Residuum
\(\displaystyle \alpha^{(k)}=\dfrac{g^{(k)^T}\,g^{(k)}}{d^{(k)^T}\,A\,d^{(k)}}\)
\(\displaystyle x^{(k+1)}=x^{(k)}-\alpha^{(k)}\,d^{(k)}\)
\(\displaystyle g^{(k+1)}=g^{(k)}+\alpha^{(k)}\,A\,d^{(k)}\)
Korrigiere die Suchrichtung \(\displaystyle d^{(k+1)}\) mit Hilfe von \(\displaystyle d^{(k)}\) und \(\displaystyle g^{(k+1)}\)
\(\displaystyle \beta_k=\dfrac{g^{(k+1)^T} g^{(k+1)}}{g^{(k)^T} g^{(k)}}\)
\(\displaystyle d^{(k+1)}=-g^{(k+1)}+\beta_k d^{(k)}\)
bis das Residuum in der Norm kleiner als eine Toleranz ist \(\displaystyle (\|g^{(k+1)}\|<\text{tol})\).

CG-Verfahren mit symmetrischer Vorkonditionierung (PCG-Verfahren)

Die Konvergenz des CG-Verfahren ist nur bei symmetrischen positiv definiten Matrizen gesichert. Dies muss ein Vorkonditionierer berücksichtigen. Bei einer symmetrischen Vorkonditionierung wird das Gleichungssystem \(\displaystyle Ax=b\) mithilfe einer Vorkonditionierer-Matrix \(\displaystyle C=KK^T\approx A^{-1}\) zu \(\displaystyle K^TAKy=K^Tb\) mit \(\displaystyle y=K^{-1}x\) transformiert, und darauf das CG-Verfahren angewandt.
Die Matrix \(\displaystyle K^TAK\) ist symmetrisch, da A symmetrisch ist. Sie ist ferner positiv definit, da nach dem Trägheitssatz von Sylvester \(\displaystyle A\) und \(\displaystyle K^TAK\) die gleichen Anzahlen positiver und negativer Eigenwerte besitzen.
Das resultierende Verfahren ist das sogenannte PCG-Verfahren (von engl. \(\displaystyle \bm{P}\)reconditioned \(\displaystyle \bm C\)onjugate \(\displaystyle \bm{G}\)radient):
Zunächst wählt man ein \(\displaystyle x^{(0)}\in\mathbb{R}^m\) beliebig und berechnet:
\(\displaystyle g^{(0)} = b - A x^{(0)}\)
\(\displaystyle h^{(0)} = C g^{(0)}\)
\(\displaystyle d^{(0)} = -h^{(0)}\)
Für \(\displaystyle k = 0,1,\dots \) setzt man:
Finde von \(\displaystyle x^{(k)}\) in Richtung \(\displaystyle d^{(k)}\) das Minimum \(\displaystyle x^{(k+1)}\) und aktualisiere Gradienten und vorkonditionierten Gradienten
\(\displaystyle \alpha_k=\dfrac{\langle g^{(k)}, h^{(k)}\rangle}{\langle d^{(k)}, A d^{(k)}\rangle}\)
\(\displaystyle x^{(k+1)}=x^{(k)}-\alpha_k d^{(k)}\)
\(\displaystyle g^{(k+1)}=g^{(k)}+\alpha_k A d^{(k)}\) (Residuum)
\(\displaystyle h^{(k+1)}=C g^{(k+1)}\)
Korrigiere die Suchrichtung \(\displaystyle d^{(k+1)}\)
\(\displaystyle \beta_k=\dfrac{\langle g^{(k+1)}, h^{(k+1)}\rangle}{\langle g^{(k)}, h^{(k)}\rangle}\)
\(\displaystyle d^{(k+1)}=-h^{(k+1)}+\beta_k d^{(k)}\)
bis das Residuum in der Norm kleiner als eine Toleranz ist \(\displaystyle (\|g^{(k+1)}\|<\text{tol})\).
ICCG-CG-comparison.png
Vergleich von ICCG mit CG anhand der 2D-Poisson-Gleichung
Ein häufiger Vorkonditionierer im Zusammenhang mit CG ist die unvollständige Cholesky-Zerlegung. Diese [!Kombination] wird auch als ICCG bezeichnet und wurde in den 1970ern von Meijerink und van der Vorst eingeführt.
Zwei weitere für das PCG-Verfahren zulässige Vorkonditionierer sind der Jacobi-Vorkonditionierer \(\displaystyle C=D^{-1}\), wobei \(\displaystyle D\) die Hauptdiagonale von \(\displaystyle A\) ist, und der SSOR-Vorkonditionierer \(\displaystyle C=(\dfrac{1}{2-\omega}(\dfrac{1}{\omega}D+L)(\dfrac{1}{\omega}D)^{-1}(\dfrac{1}{\omega}D+L)^T)^{-1}\) mit \(\displaystyle \omega \in (0, \,2)\), wobei \(\displaystyle D\) die Hauptdiagonale und \(\displaystyle L\) die strikte untere Dreiecksmatrix von \(\displaystyle A\) ist.

Konvergenzrate CG-Verfahrens

Man kann zeigen, dass die Konvergenz des CG-Algorithmus
\(\displaystyle \|x_k-x\|_A \le 2\dfrac{\sqrt{\kappa(A)}-1}{\sqrt{\kappa(A)}+1}\|x_{k-1}-x\|_A\)
ist. Hierbei ist \(\displaystyle \kappa(A)\) die Kondition der Matrix \(\displaystyle A\), sowie \(\displaystyle \|\cdot\|_A = \|A \cdot\|_2\) die \(\displaystyle A\)-Norm.
\(\displaystyle (\sqrt{\kappa(A)}-1)\) ist nicht negativ, da \(\displaystyle A\) symmetrisch und positiv definit ist. Damit ist die Kondition
\(\displaystyle \kappa(A) = \dfrac{\lambda_{max}(A)}{\lambda_{min}(A)}\)
und es gilt
\(\displaystyle 0<\lambda_{min}(A) \le \lambda_{max}(A) \Rightarrow 1 \le \dfrac{\lambda_{max}}{\lambda_{min}}\, \)

Literatur

Die Mathematik muß man schon deswegen studieren, weil sie die Gedanken ordnet.

M. W. Lomonossow

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel CG-Verfahren aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе