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 linearen Gleichungssystemen der Form ${\displaystyle Ax=b}$ mit symmetrischer, positiv definiter Systemmatrix ${\displaystyle A}$.

Das Verfahren liefert, in exakter Arithmetik, nach spätestens ${\displaystyle m}$ Schritten die exakte Lösung, wobei ${\displaystyle m}$ die Größe der quadratischen Matrix ${\displaystyle A\in \mathbb {R} ^{m\times m}}$ ist. Insbesondere ist es aber als iteratives Verfahren interessant, da der Fehler monoton fällt. Das CG-Verfahren kann in die Klasse der Krylow-Unterraum-Verfahren eingeordnet werden.

Es wurde zuerst 1952 von Eduard Stiefel und Magnus Hestenes vorgeschlagen.^[1] Ein für bestimmte Gleichungssysteme äquivalentes Verfahren schlug auch Cornelius Lanczos Anfang der 1950er Jahre mit dem Lanczos-Verfahren vor.

1. ↑ M. R. Hestenes, E. Stiefel: Methods of conjugate gradients for solving linear systems. In: Journal of Research of the National Bureau of Standards. Bd. 49, 1952, S. 409–436. doi:10.6028/jres.049.044