CG-Verfahren
 
  • Das CG-Verfahren (conjugate gradient -Verfahren) ist eine finite Methode, um ein Gleichungssystem Ax*=b mit symmetrischer und positiv definiter Matrix A zu lösen.
  • Dabei wird in jedem Schritt ein Punkt xk bestimmt, der die beste Approximation der Lösung x* auf einem Unterraum darstellt. Dieser Unterraum wird solange erweitert, bis schließlich die Lösung x* selbst bestimmt ist. Damit benötigt das CG-Verfahren nicht mehr als n Iterationen.
  • Die Richtungen, aus denen die Unterräume aufgebaut werden sind A-orthogonale, oder A-conjugierte Richtungen pi, für die gilt piTApj = 0 (i ungleich j).
  • Man kann das CG-Verfahren als Verfahren der quadratischen Optimierung interpretieren, da die Lösung x* das Minimum einer konvexen, quadratischen Funktion f(x) = ½ xTAx - bTx ist. Der Name CG-Verfahren kommt daher, daß in jedem Schritt der Gradient dieser Funktion Ax-b zur Konstruktion der nächsten Richtung mit verwendet wird. Wir wählen als Startwert der Iteration immer x0=0.
  • Durch Rundungsfehler verlieren die Richtungen pi allerdings die A-Orthogonalität. Deshalb bricht das Verfahren in der Praxis nicht nach n Schritten mit der exakten Lösung ab, vielmehr ist dann die Näherung unter Umständen noch sehr stark verfälscht. Dies hängt von der Konditionszahl und der Eigenwertverteilung der Matrix ab. Die Anwendung hier erlaubt ein detailliertes Studium dieser Effekte.
  • Sinnvoll einsetzbar ist diese Methode vor allem für große Gleichungssysteme, also dann, wenn direkte Löser, wie der Cholesky-Algorithmus, einen zu großen Aufwand bedeuten und wenn man einen guten sogenannten Präkonditionierer hat. Hier arbeiten wir wahlweise ohne einen Präkonditionierer, oder mit dem diagonalen Präkonditionierer D oder mit dem SSOR-ähnlichen
    M = (D + ω L)D-1(D + ω L)T
    , wobei die übliche additive Zerlegung
    A = L + D + LT,
    benutzt wird.
  • Das Konvergenzverhalten hängt entscheidend von der Verteilung der Eigenwerte der Matrix A ab.
 

Die Eingaben
 
  • Es kann zwischen einem festen Beispiel mit lediglich variabler Dimension und einem synthetisch konstruierten Beispiel gewählt werden.
    1. Das Balkenbiegungsproblem eines einseitig eingespannten Balkens. Dies führt auf eine Randwertaufgabe einer linearen Differentialgleichung 4. Ordnung, die mit dem Standarddifferenzenverfahren. diskretisiert wird. Die Konditionszahl der Matrix ist O(n4). Hier ist nur die Dimension zu wählen.
    2. Das synthetische Problem wird durch die Eingabe von Eigenwerten definiert. Dabei werden entweder n Eigenwerte angegeben, oder eine Eigenwertverteilung bei anzugebender Konditionszahl (Verhältnis zwischen größtem und kleinstem Eigenwert) gewählt. Intern wird dann eine orthonormale Eigenvektormatrix V gewählt mit den Komponenten sin(ij*pi/(n+1)) )*sqrt(2/(n+1)) und A wird berechnet aus A = V diag(lam_1,...,lam_n) V'
    3. Schliesslich kann man auch ein eigenes System direkt eingeben. und zwar als volles System oder in einem speziellen sparse Format.
    Beim synthetischen Beispiel ist zu wählen:
  • Die Dimension n des Problems.
  • Die Eigenwerte bzw. die Konditionszahl und die Eigenwertverteilung.
  • Koeffizienten zur Generierung der Lösung x* in Abhängigkeit von den erzeugten Eigenvektoren. Dazu wird ein Intervall [a,b] angegeben. Die Entwicklungskoeffizienten (zi) werden mittels eines Zufallszahlengenerators in diesem Intervall gewählt und es ist dann x*=Vz Die rechte Seite b ergibt sich automatisch aus der generierten Lösung und der generierten Matrix A.
  • Optional kann die Ausgabe der A-Orthogonalitäten gefordert werden.
 

Die Ausgaben
 
  • Den gewählten Fall.
  • Die Dimension n und die Anzahl der berechneten Iterationen.
  • Den Fehler in f(x) und den Fehler in x.
  • Eine Graphik, die den dekadischen Logarithmus des normierten Fehlers in f(x) veranschaulicht.
  • Eine Graphik, die den dekadischen Logarithmus des normierten Fehlers in x veranschaulicht.
  • Auf Wunsch eine Tabelle der dekadischen Logarithmen der Werte
    | piTApj|/(||pi|| ||pj ||).
 

Fragen ?!
 
  • Wie verhalten sich die Fehler in f(x) und x ?
  • Wie hängt die Konvergenz von der Verteilung der Eigenwerte ab ?
  • Wie steht es mit der A-Orthogonalität ?
 

Das Eingabeformular
 
 

Zurück: Lineare Gleichungssysteme
 Back to the top!

18.11.2010