sehr effektives Iterationsverfahren zur Lösung eines linearen Gleichungssystems Ax = b, wobei A ∈ ℝ^n×n eine symmetrisch, positiv definite Matrix sei.

Da im Laufe der Berechnungen lediglich Matrix-Vektor-Multiplikationen benötigt werden, ist das Verfahren besonders für große sparse MatrizenA geeignet.

Die Idee des Verfahren beruht auf der Feststel-lung, daß die exakte Lösung x von Ax = b gerade die Lösung der Minimierungsaufgabe \begin{eqnarray}\mathop{\min }\limits_{z\in {\mathbb{R}}^{n}}F(z)\end{eqnarray}

mit \begin{eqnarray}F(z)=\frac{1}{2}{z}^{T}Az-{b}^{T}z\end{eqnarray}

ist. Zur Lösung dieser Minimierungsaufgabe berechnet man ausgehend von einem beliebigen Startvektor x⁽⁰⁾ eine Folge von Näherungslösungen x⁽¹⁾, x⁽²⁾, …. Dazu führt man im (k + 1)-ten Schritt eine (k + 1)-dimensionale Minimierung \begin{eqnarray}\mathop{\min }\limits_{{u}_{0},\ldots, {u}_{k}\in {\mathbb{R}}}F({x}^{(k)}+{u}_{0}{r}^{(0)}+\cdots +{u}_{k}{r}^{(k)})\end{eqnarray}

durch. Dabei ist r^(j) = b − Ax^(j). Man setzt dann \begin{eqnarray}{x}^{(k+1)}={x}^{(k)}+{u}_{0}{r}^{(0)}+\cdots +{u}_{k}{r}^{(k)}.\end{eqnarray}

Die Berechnung der x^(k+1) ist dabei recht einfach:

Pro Iterationsschritt sind nur eine Matrix-VektorMultiplikation Ap^(k) und einige Skalarprodukte durchzuführen; der Gesamtaufwand ist daher insbesondere für sparse Matrizen A sehr gering. Bei der Berechnung der (k + 1)-ten Iterierten wird lediglich Information aus dem k-ten Schritt benötigt. Der Speicheraufwand ist also konstant und wächst nicht mit k an.

Theoretisch ist bei exakter Rechnung spätestens r⁽ⁿ⁾ = 0 und damit x⁽ⁿ⁾ die gesuchte Lösung. Doch aufgrund von Rundungsfehlern ist das berechnete r⁽ⁿ⁾ in der Regel von Null verschieden. In der Praxis setzt man das Verfahren einfach solange fort, bis r^(k) genügend klein ist.

Der Name „konjugiertes Gradientenverfahren“ für das beschriebene Vorgehen beruht auf den folgenden beiden Beobachtungen: Die Residuen r^(j) = b − Ax^(j) lassen sich als Gradienten der Funktion F auffassen: r^(j) = grad F(x^(j)). Die Richtungsvektoren p^(k) sind paarweise konjugiert, d. h. (p^(k))^TAp^(j) = 0 für j = 1, 2, …, k − 1.

Das konjugierte Gradientenverfahren ist ein Krylow-Raum-Verfahren zur Lösung eines symmetrisch positiv definiten Gleichungssystems. Für die Näherungslösungen x^(k) gilt \begin{eqnarray}{x}^{(k)}\in \{{x}^{(0)}\}+{\mathscr{K}}_{k}(A,{r}^{0}),\end{eqnarray}

wobei der Krylow-Raum 𝒦_k(A, r⁽⁰⁾) definiert ist als \begin{eqnarray}\begin{array}{l}{{\mathscr{K}}}_{k}(A,{r}^{(0)})\\ =\text{Span}\{{r}^{(0)},A{r}^{(0)},{A}^{2}{r}^{(0)},\ldots, {A}^{k-1}{r}^{(0)}\}.\end{array}\end{eqnarray}

Die Residuen r^(k) und die Richtungsvektoren p^(k) spannen jeweils gerade diesen Krylow-Raum auf \begin{eqnarray}\begin{array}{lll}{{\mathscr{K}}}_{k}(A,{r}^{(0)}) & = & \text{Span}\{{r}^{(0)},{r}^{(1)},\ldots, {r}^{(k-1)}\}\\ & = & \text{Span}\{{\rho }^{(0)},{\rho }^{(1)},\ldots, {\rho }^{(k-1)}\}.\end{array}\end{eqnarray}

Weiter gilt \begin{eqnarray}{r}^{(k)}\perp {K}_{k}(A,{r}^{(0)}),\end{eqnarray}

d. h. die r^(k) bilden eine orthogonale Basis des Krylow-Raums 𝒦_k(A, r⁽⁰⁾).

Das konjugierte Gradientenverfahren läßt sich auch als ein Verfahren interpretieren, welches spaltenweise eine Matrix Q_k ∈ ℝ^n×k mit orthonormalen Spalten berechnet, die A auf eine (k × k)-Tridiagonalmatrix projiziert, d. h. \begin{eqnarray}A{Q}_{k}={Q}_{k}\left(\begin{array}{lllll}{\gamma }_{1} & {\delta }_{1} & & & \\ {\delta }_{1} & {\gamma }_{2} & {\delta }_{2} & & \\ & {\delta }_{2} & \ddots & \ddots & \\ & & \ddots & \ddots & {\delta }_{k-1}\\ & & & {\delta }_{k-1} & {\gamma }_{k}\end{array}\right)+{r}_{k+1}{e}_{k}^{T}.\end{eqnarray}

Diese Eigenschaft nutzt das Lanczos-Verfahren zur Berechnung einiger Eigenwerte großer, sparser symmetrischer Matrizen aus.

Für das Konvergenzverhalten des Verfahrens, d. h. für eine Aussage, wie schnell die Iterierten x^(k) gegen die gesuchte Lösung x konvergieren, ist die Konditionszahl von A von entscheidender Bedeutung. Hat A eine kleine Konditionszahl, so wird die Konvergenz i. a. recht schnell sein. Ist die Konditionszahl von A hingegen groß, so wird die Konvergenz nur sehr langsam sein. In diesem Fall sollte man versuchen, die Konvergenzeigenschaften durch Vorkonditionierung zu verbessern.

Man versucht dabei, eine symmetrisch positiv definite Matrix C ∈ ℝ^n×n so zu finden, daß das zu Ax = b äquivalente Gleichungssystem \(\tilde{A}\tilde{x}=\tilde{b}\) mit \(\tilde{A}={C}^{-1}A{C}^{-1},\tilde{x}=Cx\), und \(\tilde{b}={C}^{-1}b\) schnellere Konvergenz liefert. Im Prinzip kann das konjugierte Gradientenverfahren nun direkt auf das vorkonditionierte Gleichungssystem \(\tilde{A}\tilde{x}=\tilde{b}\) angewendet werden. Dann ist am Schluß aus der resultierenden Näherungslösung \(\tilde{x}\) die Näherungslösung x des gegeben Systems Ax = b durch Lösen eines Gleichungssystems \(Bx=\tilde{x}\) zu bestimmen.

Es ist jedoch üblich und zweckmäßiger, das konjugierte Gradientenverfahren so umzuformulieren, daß direkt mit den gegebenen Daten A, b und C gerechnet wird, und eine Folge von Näherungslösungen x(^k) erzeugt wird, welche Näherungen an die gesuchte Lösung x darstellen. Man erhält dann das vorkonditionierte konjugierte Gradientenverfahren:

Eine Variante des konjugierten Gradientenverfahrens besteht darin, konjugierte Richtungen nicht von Beginn an, sondern erst während des Optimierungsprozesses (Minimierungsprozesses) zu berechnen. Ein Beispiel für dieses Vorgehen liefert die Vorschrift des Verfahrens von Fletcher-Reeves.

Eine Reihe dieser Verfahren können auch auf allgemeinere Zielfunktionen erweitert werden; dann sind die berechneten Richtungen aber i. allg. nicht mehr konjugiert.