CG-Verfahren

Idee des CG-Verfahrens

Die Idee des CG-Verfahrens besteht darin, dass das Minimieren der quadratischen Form

äquivalent zum Lösen von Ax = b ist. Hierbei bezeichnet das euklidische Skalarprodukt.

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

.

Die Iterierten x_k des CG-Verfahrens werden dann so gewählt, dass sie das Minimum von E in dem affinen Raum V_k , der durch die Vektoren d₀ , ..., d_k aufgespannt und um x₀ verschoben wird, bilden:

V_k := x₀ + span{d₀ , ..., d_k-1 }

Es lässt sich zeigen, dass ebenfalls gilt:

V_k = x₀ + span{r₀ , Ar₀ ..., A^k-1 r₀ }

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

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 exakt gerechnet wird. Numerische Fehler können durch weitere Iterationen eliminiert werden. Hierzu betrachtet man den Gradienten r_k , 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 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.

Copyright- und Lizenzinformationen: Diese Seite basiert auf dem Artikel CG-Verfahren aus der freien Enzyklοpädιe Wιkιpedιa und steht unter der Lizenz Creative Commons CC-BY-SA 3.0 Unported (Kurzfassung). Liste der Autoren

Anbieterkennzeichnung