Warum braucht das Verfahren der konjugierten Gradienten eine symmetrische positiv definite Matrix?

S.p.d. macht die quadratische Funktion streng konvex und definiert das A-Skalarprodukt für die konjugierten Richtungen. Ohne diese Eigenschaften greifen die klassischen Garantien des Verfahrens nicht.

Warum ist das zweidimensionale System nach zwei Schritten gelöst?

In exakter Arithmetik minimiert das Verfahren über den wachsenden Krylow-Unterraum und endet nach höchstens n Iterationen für ein n-dimensionales s.p.d.-System. In der zweidimensionalen Demonstration reicht die Lösung nach höchstens zwei unabhängigen Richtungen.

Worin sind konjugierte Gradienten dem steilsten Abstieg überlegen?

Der steilste Abstieg geht längs −∇f und zickzackt auf langgestreckten Ellipsen. Konjugierte Richtungen wiederholen bereits gewählte A-Richtungen nicht, daher ist die Konvergenz in der schlecht konditionierten Mulde deutlich schneller.

Verfahren der konjugierten Gradienten

S.p.d.-System Ax=b als Minimierung der quadratischen Form: Niveaulinien, konjugierte Gradienten gegen steilsten Abstieg, Residuumsnorm und Konditionszahl.

In exakter Arithmetik erreicht CG die 2D-Lösung nach höchstens zwei Iterationen. Zusätzliche Iterationen zeigen hier vor allem das Residuum auf Rundungsniveau und den Unterschied der Bahn zum steilsten Abstieg.

Diagramme

Zum Modell

Das System Ax = b mit symmetrischer positiv definiter Matrix ist äquivalent zur Minimierung von f(x) = ½ xᵀ A x − bᵀ x. Im zweidimensionalen Beispiel sind die Niveaulinien Ellipsen, die exakte Lösung ist ihr Mittelpunkt, das Residuum ist b − Ax. Das Verfahren der konjugierten Gradienten wählt A-konjugierte Suchrichtungen. Zum Vergleich startet vom selben Punkt der steilste Abstieg: auf langgestreckten Ellipsen zickzackt er. Die Konditionszahl κ = λ_max/λ_min bestimmt, wie stark die Mulde gestreckt ist. In exakter Arithmetik endet das Verfahren der konjugierten Gradienten nach höchstens n Schritten für ein n-dimensionales s.p.d.-System.

Für wen: Numerische lineare Algebra, wissenschaftliches Rechnen, Optimierung und Löser partieller Differentialgleichungen.

Wichtige Begriffe

konjugierte gradienten
s.p.d.-matrix
residuumsnorm
quadratische minimierung
konditionszahl
steilster abstieg

So funktioniert es

Für eine symmetrische positiv definite Matrix ist das System Ax=b äquivalent zur Minimierung von f(x)=1/2 x^T A x − b^T x. Die Niveaulinien dieser Funktion sind Ellipsen, die Lösung x* liegt in ihrem Mittelpunkt. Das Verfahren der konjugierten Gradienten baut Richtungen p_k, die im Skalarprodukt (·,·)_A konjugiert sind, und wählt die Schrittweite α_k=(r_k^T r_k)/(p_k^T A p_k). Im Zweidimensionalen genügen bei exakter Arithmetik zwei Iterationen; ein großes κ streckt die Ellipsen und verlangsamt verwandte Verfahren, etwa den steilsten Abstieg.

Wichtige Gleichungen

CG löst Ax=b durch Minimierung von f(x)=1/2 x^T A x − b^T x für s.p.d. A

α_k=(r_k^T r_k)/(p_k^T A p_k), β_k=(r_{k+1}^T r_{k+1})/(r_k^T r_k)

Häufige Fragen

Warum braucht das Verfahren der konjugierten Gradienten eine symmetrische positiv definite Matrix?: S.p.d. macht die quadratische Funktion streng konvex und definiert das A-Skalarprodukt für die konjugierten Richtungen. Ohne diese Eigenschaften greifen die klassischen Garantien des Verfahrens nicht.
Warum ist das zweidimensionale System nach zwei Schritten gelöst?: In exakter Arithmetik minimiert das Verfahren über den wachsenden Krylow-Unterraum und endet nach höchstens n Iterationen für ein n-dimensionales s.p.d.-System. In der zweidimensionalen Demonstration reicht die Lösung nach höchstens zwei unabhängigen Richtungen.
Worin sind konjugierte Gradienten dem steilsten Abstieg überlegen?: Der steilste Abstieg geht längs −∇f und zickzackt auf langgestreckten Ellipsen. Konjugierte Richtungen wiederholen bereits gewählte A-Richtungen nicht, daher ist die Konvergenz in der schlecht konditionierten Mulde deutlich schneller.

Machen Sie mit verwandten Themen in dieser Kategorie weiter — oder alle 85 in „Mathematische Visualisierung“.

Ganze Kategorie →

NeuSchule

Gradientenverfahren (2D)

Simulation starten

Niveaulinien von f(x, y) und Bahn (x, y) ← (x, y) − η∇f; Schale oder elliptische Mulde.

NeuHochschule / Forschung

FEM: Poisson-Gleichung (2D)

Simulation starten

Dreieckige P1-Elemente für −Δu = f auf dem Quadrat: Aufbau der Steifigkeitsmatrizen, festgehaltene Dirichlet-Knoten oder natürlicher Neumann-Fluss, Lösung mit konjugierten Gradienten, Potenzial als eingefärbte Membran.

NeuHochschule / Forschung

Geometrie der Hauptkomponentenanalyse (PCA) / SVD

Simulation starten

Kovarianzellipse und Dimensionsreduktion über die Singulärwertzerlegung: Hauptkomponenten, erklärte Varianz und Rekonstruktionsfehler vom Rang 1.

NeuHochschule / Forschung

Optimierer des Gradientenverfahrens

Simulation starten

Vergleich von SGD, Momentum und Adam auf einem zweidimensionalen Relief der Verlustfunktion: Schrittweite, Krümmung, Stabilität und Iterationsbahnen.

NeuHochschule / Forschung

Teilchen im Strömungsfeld

Simulation starten

Synthetisches Feld v(x, y, t); Transport mit periodischen Rändern; optional ein Pfeilgitter.

NeuHochschule / Forschung

Wärmeleitungsgleichung: finite Differenzen

Simulation starten

Eindimensionales u_t = αu_xx: explizites FTCS und implizites Euler-Verfahren rückwärts; r = αΔt/Δx², Explosion des expliziten Verfahrens bei r > 1/2 und Vergleich der numerischen Diffusion.

Verfahren der konjugierten Gradienten

Diagramme

Zum Modell

So funktioniert es

Wichtige Gleichungen

Häufige Fragen

Ähnliche Simulationen

Gradientenverfahren (2D)

FEM: Poisson-Gleichung (2D)

Geometrie der Hauptkomponentenanalyse (PCA) / SVD

Optimierer des Gradientenverfahrens

Teilchen im Strömungsfeld

Wärmeleitungsgleichung: finite Differenzen

Verfahren der konjugierten Gradienten

Diagramme

Zum Modell

So funktioniert es

Wichtige Gleichungen

Häufige Fragen