Up   Home
 



cg-Verfahren

Zur iterativen Lösung eines linearen Gleichungssystems

\begin{displaymath}A x = b , \qquad A \in \mathbbm{C}^{n \times n} , \quad x,b \in \mathbbm{C}^n\end{displaymath} (4)

mit hermitescher (im reellen Fall symmetrischer) positiv definiter Matrix wird häufig das CG-Verfahren eingesetzt. Es minimiert ein zu (4) äquivalentes quadratisches Funktional sukzessive bzgl. bestimmter Richtungen, den sogenannten konjugierten Gradienten (conjugate gradient). Das CG-Verfahren zeichnet sich dadurch aus, daß es nach maximal n Schritten (bei rundungsfehlerfreier Arithmetik) sogar die exakte Lösung liefern würde. Jedoch ist im allgemeinen die Iterierte nach m<<n Schritten bereits eine hinreichend gute Näherung der exakten Lösung, wodurch das Verfahren einen iterativen Charakter bekommt. Dem CG-Verfahren ``verwandte'' Methoden sind die Algorithmen Orthomin, Orthomin(j), Orthdir, Minres und das Lanczos-Verfahren (vgl. hierzu auch Greenbaum[4], Krylov-Raum-Approximationen). Literatur zum CG-Verfahren: z.B. Hackbusch[9], Bunse & Bunse-Gerstner[1], Großmann & Terno[5], Greenbaum[4], Kelley[10] und viele andere.
 
 

\begin{algorithm}% latex2htm id marker 285\caption[{\sc cg}--Algorithmus]{ ...... $p := r + \rho /\rho_{\rm old} \, p;$\ENDWHILE\end{algorithmic}\end{algorithm}

Eine Verallgemeinerung des CG-Verfahrens für Systeme mit nichtsymmetrischer Matrix ist das BICG-Verfahren bzw. die numerisch stabilere Variante BICGSTAB, Algorithmus 2. Auf eine genauere Darstellung des BICGSTAB-Verfahrens sei an dieser Stelle verzichtet und auf van der Vorst[12] verwiesen. Bemerkenswert ist, daß dieser Algorithmus ohne Kenntnis der transponierten Matrix auskommt, d.h eine Matrix-Vektor-Operation der Form $A^H\, x$ ist nicht notwendig (die Multiplikation mit der transponierten Matrix kann durchaus zu Problemen im Zusammenhang mit der gewählten Struktur für die Sparse-Matrizen führen). Pro Iterationsschritt sind zwei Matrix-Vektor-Multiplikationen, zwei Aufrufe des Präkonditionierers und vier Skalarprodukte zu berechnen.

 

\begin{algorithm}% latex2htm id marker 316\caption[{\sc Bicgstab}--Algorith......rm old }} \left( p - \omega v\right);$\ENDWHILE\end{algorithmic}\end{algorithm}

 


 Up  Pre Next   Top    Home

Frank Liebau
1999-07-19