Ein iterativer Algorithmus zum Lösen großer symmetrischer positiv-definiter linearen Systeme Ax = b und zur Minimierung quadratischer Funktionen, indem A-konjugierte Suchrichtungen erzeugt werden, die in exakter Arithmetik spätestens nach n Schritten zur exakten Lösung konvergieren.

Prinzip

Suchrichtungen konstruieren, die bezüglich der Matrix A konjugiert sind, sodass Korrekturen entlang aufeinanderfolgender Richtungen orthogonale Fehlerkomponenten entfernen; kurze Rekurrenzen verwenden, um Lösung, Residuum und Richtung zu aktualisieren, ohne eine vollständige Krylov-Basis zu speichern.

Demonstration

Löse eine diskretisierte Poisson-Gleichung auf einem Gitter: den Laplace-Operator als dünnbesetzte SPD-Matrix A darstellen und konjugierte Gradienten anwenden, um die Energienorm des Fehlers iterativ zu reduzieren, bis Residual- oder Energie-Toleranzen erreicht sind, und Präconditioning zur Beschleunigung nutzen.

Fehlanwendung

Den unveränderten konjugierten Gradienten bei nichtsymmetrischen oder indefiniten Matrizen anwenden (ohne auf GMRES oder MINRES zu wechseln) oder schlechte Präconditioner verwenden, was zu Stagnation, Breakdown oder langsamer Konvergenz führen kann.

Konsequenz

Für große dünnbesetzte SPD-Probleme liefert CG speichereffiziente iterative Lösungen mit schneller Konvergenz, wenn Eigenwerte gebündelt sind oder gute Präconditioner vorliegen; in exakter Arithmetik führt CG zu einer Endgültigen Lösung in finit vielen Schritten, und praktisch liefert es schnelle Näherungen.

Umkehrung

Direkte Verfahren wie die Cholesky-Faktorisierung berechnen exakte Lösungen mittels Matrixzerlegung und Pivotierung, vermeiden Iteration, verursachen aber höheren Speicher- und Faktorisationsaufwand für sehr große dünnbesetzte Systeme im Vergleich zu CG.

Abgrenzung

Gedacht für symmetrische positiv-definite Systeme oder äquivalente quadratische Minimierungen; schließt nichtsymmetrische, stark indefinitive oder schwer schlecht konditionierte Probleme aus, sofern nicht durch Präconditioning, Reorthogonalisierung oder Wechsel zu allgemeineren Krylov-Methoden angepasst.

Semantische Spannung

Spannung zwischen CG und anderen Krylov-Methoden (GMRES, BiCGStab) in Bezug auf Symmetrie und Speicher: CG ist optimal für SPD-Systeme mit minimalem Speicherbedarf und kurzen Rekurrenzen, während andere Methoden Nicht-Symmetrie zulassen, dafür aber mehr Speicher oder komplexere Abläufe benötigen.

Synthese

Der konjugierte Gradientenalgorithmus wandelt die lineare Lösung in eine Folge von eindimensionalen Minimierungen entlang A-konjugierter Richtungen um und erzielt so speichereffiziente und schnelle Konvergenz für dünnbesetzte SPD-Systeme; seine praktische Leistung hängt stark von der Spektralstruktur und Präconditionierung ab.