5.2.1 Das klassische CG-Verfahren

,,On a typical hard problem [from laser fusion physics], the new method [ICCG] is about 8000 times faster than the point Gauß-Seidel method, 200 times faster than the alternating direction implicit method, and 30 times faster than the block successive overrelaxation method with optimum relaxation factor.``
David S. Kershaw [55]

Über das ,,Verfahren konjugierter Gradienten`` von Magnus Hestenes und Eduard Stiefel ist seit seiner Entdeckung 1952 [46], aber insbesondere seit seiner ,,Wiederentdeckung`` durch J.K. Reid [87][88] eine Unzahl wissenschaftlicher Publikationen erschienen. Selbst die Entdeckungs- und Entwicklungsgeschichte samt einer ausführlichen Bibliographie wurde bereits dokumentiert [33]. Eine Herleitung des Algorithmus aus der ,,Methode des steilsten Abstiegs`` - aus dieser Methode erhielten ihn auch die beiden Erfinder - findet man z.B. in [32], wo auch die Beziehung zum Lanczos Algorithmus [58] hergestellt wird. Zum Konvergenzverhalten konsultiere man [92][104][115][116][123]. Die Beziehung zu orthogonalen Polynomen ist in [105] zu finden und die Beeinträchtigung der Konvergenz durch endliche Genauigkeit der Zahlendarstellung in [124].
CG ist anwendbar auf symmetrische, positiv-definite lineare Gleichungssysteme. Der Algorithmus bildet rekursiv eine -konjugierte Basis. Aus diesem Grund terminiert der Algorithmus mit der exakten Lösung nach endlich vielen Schritten. Die Anzahl der Schritte ist kleiner oder gleich der Dimension des nichtsingulären Gleichungssystems, insbesondere geringer, wenn mehrfache Eigenwerte auftreten. In der Praxis nimmt in Abhängigkeit der Eigenwertverteilung auf der positiven, reellen Achse der Fehler in der Näherungslösung rasch ab. Man erhält nach wenigen Iterationen eine Lösung, die der gewünschten Genauigkeit entspricht. Vernachlässigt man die Abhängigkeit von der gesamten Eigenwertverteilung und zieht man zur Abschätzung der Konvergenz bloß den Quotient der extremalen Eigenwerte, die spektrale Konditionszahl =/, heran, so kann die für eine gewünschte relative Genauigkeit erforderliche Iterationszahl in folgender Weise abgeschätzt werden [50]. Man definiert zuerst als Genauigkeitsmaß das normierte Residuum

wobei die zu unterschreitende relative Genauigkeit ist. Dann wird das durch den CG-Algorithmus über dem Eigenwertspektrum konstruierte Polynom durch ein (normiertes) Tschebyscheff-Polynom

abgeschätzt. Da für Tschebyscheff-Polynome erster Art die Ungleichung

gilt, läßt sich die Abschätzung vereinfachen auf

Mit der Definition der Tschebyscheff-Polynome für

findet man die nötige Iterationszahl zur Reduktion des relativen Fehlers:

Umgekehrt reduzieren Iterationen den relativen Fehler auf

In der Praxis überschätzt die Formel (5.27) die nötige Iterationszahl. Wesentlich ist jedoch, daß die spektrale Konditionszahl mit ihrer Wurzel in (5.27) eingeht, wodurch zu ersehen ist, in welcher Weise sich Methoden, die diese Konditionszahl verkleinern - die sogenannten Vorkonditionierungsmethoden - auf die Konvergenz des Verfahrens auswirken.
Der eigentliche Durchbruch des CG-Algorithmus gelang Meijerink und van der Vorst mit dem ICCG-Verfahren [63]. Ihre Leistung war die Vorkonditionierung durch eine unvollständige Faktorisierung der Koeffizientenmatrix. Dieser Typ von Vorkonditionierung ist bis heute der robusteste und schnellste und löste eine Menge anderer Vorkonditionierungsmethoden, wie z.B. Block-SSOR [6] oder die zyklische Block-Jacobi-Methode [88], ab.