Wichtiger Hinweis zum Inhalt des Online-LexikonsBei den auf dieser Seite aufgeführten Texten/Artikeln/Inhalten handelt es sich ausschließlich um fremde Inhalte, die sich die Aschendorff Verlag GmbH & Co. KG ausdrücklich nicht zu Eigen macht. Diese fremden Inhalte, die keiner regelmäßigen Überprüfung unterliegen, sind ausnahmslos solche der freien Enzyklopädie Wikipedia, für die keinerlei Verantwortung übernommen wird.

---

Lizenzbestimmungen Der Text/Artikel/Inhalt auf dieser Seite innerhalb der Rubrik "Online Lexikon" basiert, soweit nicht anders angegeben, auf dem Artikel CG-Verfahren aus der freien Enzyklopädie Wikipedia. Die Inhalte stehen unter der GNU Lizenz für freie Dokumentation. Eine Liste der Autoren ist dort abrufbar.

CG-Verfahren

Das CG-Verfahren (von engl. conjugate gradients oder auch Verfahren der konjugierten Gradienten) ist eine effiziente numerische Methode zur Lösung von großen, symmetrischen, positiv_definiten Gleichungssystemen der Form $Ax=b$. Es gehört zur Klasse der Krylow-Unterraum-Verfahren. Das Verfahren konvergiert nach spätestens $m$ Schritten, wobei $m$ die Dimension der quadratischen Matrix $A$ ist. 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
:$E(x):=\backslash langle\; b,x\backslash rangle-\backslash frac12\backslash langle\; Ax,x\backslash rangle$
äquivalent zum Lösen von $Ax=b$ ist.

Der Gradient von $E$
an der Stelle $x^\{(k)\}$ ist gerade $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 $g^\{(k)\}$ in eine andere Richtung $d^\{(k)\}$ die Funktion $E$ zu maximieren. Die Richtungen $d^\{(k)\}$ sind dabei alle $A$-konjugiert, d.h. es gilt
:$\backslash langle\; Ad^\{(i)\},d^\{(j)\}\backslash rangle=0\backslash qquad\backslash forall\; i\backslash neq\; j$.
Weiter realisieren alle $x^\{(k)\}$ das Maximum von $E$ in dem affinen_Raum
:$V\_k:=x^\{(0)\}+\backslash operatorname\{span\}\backslash left(\backslash \{d^\{(1)\},\backslash ldots,d^\{(k)\}\backslash \}\backslash right)$.
Dabei handelt es sich also um den Vektorraum, der durch die Vektoren $d^\{(1)\},\backslash ldots,d^\{(k)\}$ aufgespannt und um $x^\{(0)\}$ verschoben wird.

Da die Vektoren $d^\{(k)\}$ alle $A$-konjugiert sind, ist die Dimension von $V\_k$ gerade $k$.
Ist also $A$ eine $m\backslash times\; m$-Matrix, so terminiert das Verfahren nach spätestens $m$ Schritten, falls korrekt gerechnet wird. Numerische Fehler können durch weitere Iterationen eliminiert werden. Hierzu betrachtet man den Gradienten $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 $\backslash mathbb\; R^m$ auf und minimiert in die jeweilige Richtung bestmöglich.

CG-Verfahren ohne Vorkonditionierung

Zunächst wählt man ein $x^\{(0)\}\backslash in\backslash mathbb\{R\}^m$ beliebig und berechnet:

:$g^\{(0)\}\; =\; b\; -\; A\; x^\{(0)\}$
:$d^\{(0)\}\; =\; -g^\{(0)\}$

Für $k\; =\; 0,1,...$ setzt man:

Finde von $x^\{(k)\}$ in Richtung $d^\{(k)\}$ das Minimum $x^\{(k+1)\}$ und aktualisiere den Gradienten bzw. das Residuum
:$\backslash alpha^\{(k)\}=\backslash frac\{g^\{(k)^T\}\backslash ,g^\{(k)\}\}\{d^\{(k)^T\}\backslash ,A\backslash ,d^\{(k)\}\}$
:$x^\{(k+1)\}=x^\{(k)\}-\backslash alpha^\{(k)\}\backslash ,d^\{(k)\}$
:$g^\{(k+1)\}=g^\{(k)\}+\backslash alpha^\{(k)\}\backslash ,A\backslash ,d^\{(k)\}$

Korrigiere die Suchrichtung $d^\{(k+1)\}$ mit Hilfe von $d^\{(k)\}$ und $g^\{(k+1)\}$
:$\backslash beta\_k=\backslash frac\{g^\{(k+1)^T\}\; g^\{(k+1)\}\}\{g^\{(k)^T\}\; g^\{(k)\}\}$
:$d^\{(k+1)\}=-g^\{(k+1)\}+\backslash beta\_k\; d^\{(k)\}$

bis das Residuum in der Norm kleiner als eine Toleranz ist ().

CG-Verfahren mit symmetrischer Vorkonditionierung (PCG-Verfahren)

Die Konvergenz des CG-Verfahren ist nur bei symmetrischen positiv definiten Matrizen gesichert. Dies muss ein Trägheitssatz_von_Sylvester $A$ und $K^TAK$ die gleichen Anzahlen positiver und negativer Eigenwerte besitzen.

Das resultierende Verfahren ist das sog. PCG-Verfahren (von engl. Preconditioned Conjugate Gradient):

Zunächst wählt man ein $x^\{(0)\}\backslash in\backslash mathbb\{R\}^m$ beliebig und berechnet:
:$g^\{(0)\}\; =\; b\; -\; A\; x^\{(0)\}$
:$h^\{(0)\}\; =\; C\; g^\{(0)\}$
:$d^\{(0)\}\; =\; -h^\{(0)\}$

Für $k\; =\; 0,1,...$ setzt man:

Finde von $x^\{(k)\}$ in Richtung $d^\{(k)\}$ das Minimum $x^\{(k+1)\}$ und aktualisiere Gradienten und vorkonditionierten Gradienten
:$\backslash alpha\_k=\backslash frac\{\backslash langle\; g^\{(k)\},\; h^\{(k)\}\backslash rangle\}\{\backslash langle\; d^\{(k)\},\; A\; d^\{(k)\}\backslash rangle\}$
:$x^\{(k+1)\}=x^\{(k)\}-\backslash alpha\_k\; d^\{(k)\}$
:$g^\{(k+1)\}=g^\{(k)\}+\backslash alpha\_k\; A\; d^\{(k)\}$ (Residuum)
:$h^\{(k+1)\}=C\; g^\{(k+1)\}$

Korrigiere die Suchrichtung $d^\{(k+1)\}$
:$\backslash beta\_k=\backslash frac\{\backslash langle\; g^\{(k+1)\},\; h^\{(k+1)\}\backslash rangle\}\{\backslash langle\; g^\{(k)\},\; h^\{(k)\}\backslash rangle\}$
:$d^\{(k+1)\}=-h^\{(k+1)\}+\backslash beta\_k\; d^\{(k)\}$

bis das Residuum in der Norm kleiner als eine Toleranz ist ().

]]
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 $C=D^\{-1\}$, wobei $D$ die Hauptdiagonale von $A$ ist, und der SSOR-Vorkonditionierer
$C=(\backslash frac\{1\}\{2-\backslash omega\}(\backslash frac\{1\}\{\backslash omega\}D+L)(\backslash frac\{1\}\{\backslash omega\}D)^\{-1\}(\backslash frac\{1\}\{\backslash omega\}D+L)^T)^\{-1\}$ mit $\backslash omega\; \backslash in\; (0,\; \backslash ,2)$, wobei $D$ die Hauptdiagonale und $L$ die strikte untere Dreiecksmatrix von $A$ ist.

Konvergenzrate CG-Verfahrens

Man kann zeigen, dass die Konvergenz des CG-Algorithmus
::$\backslash |x\_k-x\backslash |\_A\; \backslash le\; 2\backslash frac\{\backslash sqrt\{\backslash kappa(A)\}-1\}\{\backslash sqrt\{\backslash kappa(A)\}+1\}\backslash |x\_\{k-1\}-x\backslash |\_A$
ist. Hierbei ist $\backslash kappa(A)$ die Kondition der Matrix $A$, sowie
$\backslash |\backslash cdot\backslash |\_A\; =\; \backslash |A\; \backslash cdot\backslash |\_2$ die $A$-Norm.

$(\backslash sqrt\{\backslash kappa(A)\}-1)$ ist nicht negativ, da $A$ symmetrisch und positiv definit ist. Damit ist die Kondition
:$\backslash kappa(A)\; =\; \backslash frac\{\backslash lambda\_\{max\}(A)\}\{\backslash lambda\_\{min\}(A)\}$
und es gilt
:

Literatur

*P. Knabner, L. Angermann: Numerik partieller Differentialgleichungen, Springer, ISBN 3-540-66231-6
*A. Meister: Numerik linearer Gleichungssysteme, Vieweg 1999, ISBN 3-528-03135-2
*William H., Teukolsky, Saul A.:Numerical Recipes in C++, Cambridge University Press 2002, ISBN 0-521-75033-4.

       VIDEO-NEWS UND ANGEBOTE