Methode der konjugierten Gradienten

Methode der konjugierten Gradienten
Ein Vergleich des einfachen Gradientenverfahren mit optimaler Schrittlänge (in grün) mit dem CG-Verfahren (in rot) für die Minimierung der quadratischen Form eines gegebenen linearen Gleichungssystems. CG konvergiert nach 2 Schritten, die Größe der Systemmatrix ist m=2).

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.

Inhaltsverzeichnis

Idee des CG-Verfahrens

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

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

äquivalent zum Lösen von Ax = b ist. Hierbei bezeichnet \langle \cdot,\cdot \rangle das euklidische Skalarprodukt.

Der Gradient von E an der Stelle xk ist gerade rk = Axkb und somit bei großen, dünn besetzten Matrizen schnell zu berechnen. Die Idee des CG-Verfahrens ist es nun, anstelle in Richtung rk wie beim Verfahren des steilsten Abstiegs in eine andere Richtung dk die Funktion E über einen Unterraum zu minimieren. Die Richtungen dk sind dabei alle A-konjugiert, das heißt es gilt

\langle Ad_i,d_j\rangle=0\qquad\forall i\neq j.

Die Iterierten xk des CG-Verfahrens werden dann so gewählt, dass sie das Minimum von E in dem affinen Raum Vk, der durch die Vektoren d_0,\ldots,d_k aufgespannt und um x0 verschoben wird, bilden:

V_k:=x_0+\operatorname{span}\{d_0,\ldots,d_{k-1}\}.

Es lässt sich zeigen, dass ebenfalls gilt:

V_k = x_0+\operatorname{span}\{r_0, Ar_0\ldots,A^{k-1}r_0\}.

Der letzte Teil zeigt, dass die Suchrichtungen den Krylow-Unterraum zu A und r0 aufspannen. Das CG-Verfahren lässt sich deswegen alternativ direkt als Krylow-Unterraum-Verfahren definieren.

Da die Vektoren dk alle A-konjugiert sind, ist die Dimension von Vk gerade k. Ist also A eine m\times m-Matrix, so terminiert das Verfahren nach spätestens m Schritten, falls exakt gerechnet wird. Numerische Fehler können durch weitere Iterationen eliminiert werden. Hierzu betrachtet man den Gradienten rk, der das Residuum angibt. Unterschreitet die Norm dieses Residuums einen gewissen Schwellenwert, wird das Verfahren abgebrochen.

Das Verfahren baut sukzessive eine A-orthogonale Basis für den \mathbb R^m auf und minimiert in die jeweilige Richtung bestmöglich.

Das Problem bei dem iterativen Verfahren ist das Finden der optimalen Schrittweite. Um die Güte eines Punktes zu bestimmen ist jeweils eine vollständige Matrixmultiplikation notwendig, welche nebenbei gleich einen neuen Gradienten liefert. Ist die Schrittweite entlang eines vorgegebenen Gradienten zu ungenau, entspricht die Methode eher einem einfachen Downhill-Algorithmus.

Varianten

Es existieren verschiedene Varianten des Verfahrens, z. B. Fletcher-Reeves, Hestenes-Stiefel, Davidon-Fletcher-Powell und Polak-Ribiere.

  • βk + 1 = (gk + 1)Tgk + 1 / (gk)Tgk (Fletcher-Reeves)
  • βk + 1 = (gk + 1)T(gk + 1gk) / (gk)Tgk (Polak-Ribiere)
  • βk + 1 = (gk + 1)T(gk + 1gk) / (dk)T(gk + 1gk) (Hestenes-Stiefel)

CG-Verfahren ohne Vorkonditionierung

Zunächst wählt man ein x_0 \in \mathbb{R}^m beliebig und berechnet:

r0 = bAx0
d0 = r0

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

Finde von xk in Richtung dk das Minimum xk + 1 und aktualisiere den Gradienten bzw. das Residuum

\alpha_k=\frac{r_k^T r_k} {d_k^T A d_k}
xk + 1 = xk + αkdk
r_{k+1}=r_k-\alpha_k A\,d_k

Korrigiere die Suchrichtung dk + 1 mit Hilfe von dk und rk + 1

\beta_k=\frac{r_{k+1}^T r_{k+1}}{r_k^T r_k}
dk + 1 = rk + 1 + βkdk

bis das Residuum in der Norm kleiner als eine Toleranz ist (\|r_{k+1}\|<\mbox{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 Ax = b mit Hilfe einer Vorkonditionierer-Matrix C=KK^T\approx A^{-1} zu KTAKy = KTb mit y = K − 1x transformiert, und darauf das CG-Verfahren angewandt.

Die Matrix KTAK ist symmetrisch, da A symmetrisch ist. Sie ist ferner positiv definit, da nach dem Trägheitssatz von Sylvester A und KTAK die gleichen Anzahlen positiver und negativer Eigenwerte besitzen.

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

Zunächst wählt man ein x_0 \in \mathbb{R}^m beliebig und berechnet:

r0 = bAx0
h0 = Cr0
d0 = h0

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

Finde von xk in Richtung dk das Minimum xk + 1 und aktualisiere Gradienten und vorkonditionierten Gradienten

\alpha_k=\frac{\langle r_k, h_k\rangle}{\langle d_k, A d_k\rangle}
xk + 1 = xk + αkdk
rk + 1 = rk − αkAdk (Residuum)
hk + 1 = Crk + 1

Korrigiere die Suchrichtung dk + 1

\beta_k=\frac{\langle r_{k+1}, h_{k+1}\rangle}{\langle r_k, h_k\rangle}
dk + 1 = hk + 1 + βkdk

bis das Residuum in der Norm kleiner als eine Toleranz ist (\|r_{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.

Konvergenzrate des CG-Verfahrens

Man kann zeigen, dass die Konvergenzgeschwindigkeit des CG-Algorithmus durch

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

beschrieben wird. Hierbei ist κ(A) die Kondition der Matrix A, sowie \|x\|_A = \sqrt{x^T A x} die Energienorm von A. \sqrt{\kappa(A)}-1 ist nicht negativ, da A symmetrisch und positiv definit ist. Ferner ist deswegen die Kondition

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

Aus der Minimierungseigenschaft lässt sich ferner herleiten, dass

\frac{\|x_k-x^*\|_A}{\|x_0-x^*\|_A} \leq \max_{z \in \sigma(A)}|p_k(z)|,

wobei pk(z) ein beliebiges Polynom vom Grad 1 ist mit pk(0) = 1 und x * die Lösung. Mit σ(A) ist das Spektrum, also die Menge der Eigenwerte der Matrix A gemeint. Daraus folgt, dass CG ein System zu einer Matrix mit nur k Eigenwerten in k Schritten löst und dass CG für Systeme, bei denen die Eigenwerte in kleinen Umgebungen konzentriert sind, sehr schnell konvergiert. Dies wiederum liefert einen Anhaltspunkt für sinnvolle Vorkonditionierer: Ein Vorkonditionierer ist dann gut, wenn er dafür sorgt, dass die Eigenwerte konzentriert werden.

Erweiterung auf unsymmetrische Matrizen

Ist die Systemmatrix A unsymmetrisch, aber regulär, so kann das CG-Verfahren auf die Normalgleichungen

ATAx = ATb

angewendet werden, da ATA für eine reguläre Matrix A symmetrisch und positiv definit ist. Dieses Verfahren nennt sich auch CGNR, da bei diesem Vorgehen die Norm des Residuums von bAx minimiert wird. Alternativ gibt es das Verfahren CGNE, welches

AATy = b

löst mit x = ATy. Hierbei wird der Fehler (Error) minimiert.

Beide Verfahren haben den Nachteil, dass zum Einen AT zur Verfügung stehen muss, was nicht immer gegeben ist und zum Anderen die Kondition von A bei diesem Ansatz quadriert wird, was zur Verlangsamung der Konvergenz führen kann.

Literatur

  • C. T. Kelley: Iterative Methods for Linear and Nonlinear Equations, SIAM, ISBN 0-89871-352-8
  • 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.
  • www.cs.cmu.edu An Introduction to the Conjugate Gradient Method Without the Agonizing Pain (PDF)

Wikimedia Foundation.

Игры ⚽ Нужно сделать НИР?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Verfahren der konjugierten Gradienten — Ein Vergleich des einfachen Gradientenverfahren mit optimaler Schrittlänge (in grün) mit dem CG Verfahren (in rot) für die Minimierung der quadratischen Form eines gegebenen linearen Gleichungssystems. CG konvergiert nach 2 Schritten, die Größe… …   Deutsch Wikipedia

  • Methode der finiten Elemente — Die Finite Elemente Methode (FEM) ist ein numerisches Verfahren zur näherungsweisen Lösung, insbesondere elliptischer partieller Differentialgleichungen mit Randbedingungen. Sie ist auch ein weit verbreitetes modernes Berechnungsverfahren im… …   Deutsch Wikipedia

  • Finite-Elemente-Methode — Die Finite Elemente Methode (FEM), auch „Methode der finiten Elemente“ genannt, ist ein numerisches Verfahren zur Lösung von partiellen Differentialgleichungen. Sie ist ein weit verbreitetes modernes Berechnungsverfahren im Ingenieurwesen und ist …   Deutsch Wikipedia

  • CG-Verfahren — Ein Vergleich des einfachen Gradientenverfahren mit optimaler Schrittlänge (in grün) mit dem CG Verfahren (in rot) für die Minimierung der quadratischen Form eines gegebenen linearen Gleichungssystems. CG konvergiert nach 2 Schritten, die Größe… …   Deutsch Wikipedia

  • Gradientenverfahren — Das Verfahren des steilsten Abstiegs, auch Gradientenverfahren genannt, ist ein Verfahren, das in der Numerik eingesetzt wird, um allgemeine Optimierungsprobleme zu lösen. Dabei geht man (am Beispiel eines Minimierungsproblemes) von einem… …   Deutsch Wikipedia

  • Numerische Verfahren — Die Liste numerischer Verfahren führt Verfahren der numerischen Mathematik nach Anwendungsgebieten auf. Inhaltsverzeichnis 1 Lineare Gleichungssysteme 2 Nichtlineare Gleichungssysteme 3 Numerische Integration 4 Approximation und Interpolation …   Deutsch Wikipedia

  • Liste numerischer Verfahren — Die Liste numerischer Verfahren führt Verfahren der numerischen Mathematik nach Anwendungsgebieten auf. Inhaltsverzeichnis 1 Lineare Gleichungssysteme 2 Nichtlineare Gleichungssysteme 3 Numerische Integration …   Deutsch Wikipedia

  • Quadratisches Sieb — ist ein Begriff aus dem Bereich Zahlentheorie der Mathematik und bezeichnet einen der schnellsten bekannten Algorithmen zur Faktorisierung großer natürlicher Zahlen. Es ist ein allgemeines Faktorisierungsverfahren, d.h. die Laufzeit hängt nur von …   Deutsch Wikipedia

  • Krylov-Unterraum-Verfahren — Krylow Unterraum Verfahren sind iterative Verfahren zum Lösen großer, dünnbesetzter linearer Gleichungssysteme, wie sie bei der Diskretisierung von partiellen Differentialgleichungen entstehen oder von Eigenwertproblemen. Sie sind benannt nach… …   Deutsch Wikipedia

  • Krylov-Unterraumverfahren — Krylow Unterraum Verfahren sind iterative Verfahren zum Lösen großer, dünnbesetzter linearer Gleichungssysteme, wie sie bei der Diskretisierung von partiellen Differentialgleichungen entstehen oder von Eigenwertproblemen. Sie sind benannt nach… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”