Conjugate Gradient
Die Methode der konjugierten Gradienten löst symmetrische positiv definite Systeme Ax=b und konvergiert in n Schritten (in exakter Arithmetik) mittels A-konjugierter Richtungen.
Zweck
Große, dünnbesetzte symmetrisch positiv definite lineare Systeme effizient und iterativ lösen.
Mechanismus
Sie sucht entlang A-konjugierter (nicht orthogonaler) Richtungen, wobei jeder Schritt im Krylov-Unterraum optimal ist. Sie benötigt kein explizites A, nur Matrix-Vektor-Produkte. Vorkonditioniertes CG beschleunigt die Konvergenz. Komplexität O(√κ log(1/ε)).
Anwendungsfälle
- Großskalige lineare Löser
- Optimierungsalgorithmen
- Wissenschaftliches Rechnen