CG-Verfahren

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

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 $A x = b$ . Es gehört zur Klasse der Krylow-Unterraum-Verfahren. Das Verfahren konvergiert nach spätestens $m$ Schritten. Insbesondere ist es aber als iteratives Verfahren interessant, da der Fehler monoton fällt.

Inhaltsverzeichnis

1 Idee des CG-Verfahrens
2 CG-Verfahren ohne Vorkonditionierung
3 CG-Verfahren mit symmetrischer Vorkonditionierung (PCG-Verfahren)
4 Konvergenzrate CG-Verfahrens
5 Literatur

[Bearbeiten] Idee des CG-Verfahrens

Die Idee des CG-Verfahrens besteht darin, dass das Maximieren von

$E(x):=\langle b,x\rangle-\frac12\langle Ax,x\rangle$

äquivalent zum Lösen von $A x = b$ ist.

Der Gradient von $E$ an der Stelle $x (k)$ ist gerade $g (k) = b - A x (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

$\langle Ad^{(i)},d^{(j)}\rangle=0\qquad\forall i\neq j$ .

Weiter realisieren alle $x (k)$ das Maximum von $E$ in dem affinen Raum

$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 $d^{(1)},\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\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 $\mathbb R^m$ auf und minimiert in die jeweilige Richtung bestmöglich.

[Bearbeiten] CG-Verfahren ohne Vorkonditionierung

Zunächst wählt man ein $x^{(0)}\in\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

$\alpha^{(k)}=\frac{g^{(k)^T}\,g^{(k)}}{d^{(k)^T}\,A\,d^{(k)}}$

$x^{(k+1)}=x^{(k)}-\alpha^{(k)}\,d^{(k)}$

$g^{(k+1)}=g^{(k)}+\alpha^{(k)}\,A\,d^{(k)}$

Korrigiere die Suchrichtung $d (k + 1)$ mit Hilfe von $d (k)$ und $g (k + 1)$

$\beta_k=\frac{g^{(k+1)^T} g^{(k+1)}}{g^{(k)^T} g^{(k)}}$

d (k + 1) = - g (k + 1) + β k d (k)

bis das Residuum in der Norm kleiner als eine Toleranz ist ( $\|g^{(k+1)}\|<\mbox{tol}$ ).

[Bearbeiten] CG-Verfahren mit symmetrischer Vorkonditionierung (PCG-Verfahren)

Die Konvergenz des CG-Verfahren ist nur bei symmetrischen positiv definiten Matrizen gesichtert. Dies muss ein Vorkonditionierer berücksichtigen. Bei einer symmetrischen Vorkonditionierung wird das Gleichungssystem $A x = b$ mithilfe einer Vorkonditionierer-Matrix $C=KK^T\approx A^{-1}$ zu $K T A K y = K T b$ mit $y = K - 1 x$ transformiert, und darauf das CG-Verfahren angewandt.

Die Matrix $K T A K$ ist symmetrisch, da A symmetrisch ist. Sie ist ferner positiv definit, da nach dem Trägheitssatz von Sylvester $A$ und $K T A K$ 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)}\in\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

$\alpha_k=\frac{\langle g^{(k)}, h^{(k)}\rangle}{\langle d^{(k)}, A d^{(k)}\rangle}$

x (k + 1) = x (k) - α k d (k)

g (k + 1) = g (k) + α k A d (k)

(Residuum)

h (k + 1) = C g (k + 1)

Korrigiere die Suchrichtung $d (k + 1)$

$\beta_k=\frac{\langle g^{(k+1)}, h^{(k+1)}\rangle}{\langle g^{(k)}, h^{(k)}\rangle}$

d (k + 1) = - h (k + 1) + β k d (k)

bis das Residuum in der Norm kleiner als eine Toleranz ist ( $\|g^{(k+1)}\|<\mbox{tol}$ ).

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

[Bearbeiten] Konvergenzrate CG-Verfahrens

Man kann zeigen, dass die Konvergenz des CG-Algorithmus

$\|x_k-x\|_A \le 2\frac{\sqrt{\kappa(A)}-1}{\sqrt{\kappa(A)}+1}\|x_{k-1}-x\|_A$

ist. Hierbei ist $κ(A)$ die Kondition der Matrix $A$ , sowie $\|\cdot\|_A = \|A \cdot\|_2$ die $A$ -Norm.

$(\sqrt{\kappa(A)}-1)$ ist nicht negativ, da $A$ symmetrisch und positiv definit ist. Damit ist die Kondition

$\kappa(A) = \frac{\lambda_{max}(A)}{\lambda_{min}(A)}$

und es gilt

$0<\lambda_{min}(A) \le \lambda_{max}(A) \Rightarrow 1 \le \frac{\lambda_{max}}{\lambda_{min}}.$

[Bearbeiten] 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

Von „http://de.wikipedia.org../../../c/g/-/CG-Verfahren_c7bb.html“

Kategorie: Numerische lineare Algebra