Inhalt

Grundlagen der Mathematik

Diskrete Mathematik

Differentialgleichungen

Funktionalanalysis

Differentialgeometrie

Topologie

Numerik

Numerische Verfahren

Kondition

Stabilität

Konsistenz

Lineare Gleichungssysteme

Cholesky-Zerlegung

QR-Zerlegung

Splitting-Verfahren

Krylow-Unterraum-

Verfahren

CG-Verfahren

Mehrgitterverfahren

Vorkonditionierung

Nichtlineare

Gleichungssysteme

Interpolation

Approximation

Numerische Integration

Optimierung

Stochastik

Unsortiertes

Anbieterkennzeichnung

Weiterbildung für alle! Über 200 Fernlehrgänge an Deutschlands größter Fernschule!

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. 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

ä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

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

Dabei handelt es sich also um den Vektorraum, der durch die Vektoren d⁽¹⁾ , ..., d^(k) aufgespannt und um x⁽⁰⁾ verschoben wird.

Da die Vektoren d^(k) alle A-konjugiert sind, ist die Dimension von V_k gerade k. Ist also A eine -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 auf und minimiert in die jeweilige Richtung bestmöglich.

CG-Verfahren ohne Vorkonditionierung

Zunächst wählt man ein beliebig und berechnet:

g⁽⁰⁾ = b - Ax⁽⁰⁾

d⁽⁰⁾ = - g⁽⁰⁾

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

Korrigiere die Suchrichtung d^{(k + 1)} mit Hilfe von d^(k) und g^{(k + 1)}

bis das Residuum in der Norm kleiner als eine Toleranz ist (||g^{(k + 1)} || < 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 mithilfe einer Vorkonditionierer-Matrix zu K^T AKy = K^T b mit y = K^-1 x transformiert, und darauf das CG-Verfahren angewandt.

Die Matrix K^T AK ist symmetrisch, da A symmetrisch ist. Sie ist ferner positiv definit, da nach dem Trägheitssatz von Sylvester A und K^T AK 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 beliebig und berechnet:

g⁽⁰⁾ = b - Ax⁽⁰⁾

h⁽⁰⁾ = Cg⁽⁰⁾

d⁽⁰⁾ = - h⁽⁰⁾

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

(Residuum)

h^{(k + 1)} = Cg^{(k + 1)}

Korrigiere die Suchrichtung d^{(k + 1)}

bis das Residuum in der Norm kleiner als eine Toleranz ist (||g^{(k + 1)} || < 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 mit , 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

ist. Hierbei ist die Kondition der Matrix A, sowie die A-Norm.

ist nicht negativ, da A symmetrisch und positiv definit ist. Damit ist die Kondition

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.

Man darf nicht das, was uns unwahrscheinlich und unnatürlich erscheint, mit dem verwechseln, was absolut unmöglich ist.

Carl Friedrich Gauß

Druckansicht

Impressum: Wurzelzieher Mathepedia • Thomas Steinfeld • Dorfplatz 25 • 17237 Blankensee • Tel.: 01734332309 (Vodafone/D2) • Email: matһе@wυrzеlzιeher.de

Amazon.de empfiehlt: