Wie funktioniert das CG-Verfahren?

29.07.2009, 15:19	hyperbel	Auf diesen Beitrag antworten »
Wie funktioniert das CG-Verfahren? Hallo Leute. Ich muss mich in das CG-Verfahren (Conjugent Gradient Method) einarbeiten, habe damit allerdings Schwierigkeiten. Z.B. aus Wikipedia: "Das CG-Verfahren (von engl. conjugate gradients oder auch Verfahren der konjugierten Gradienten) ist eine effiziente numerische Methode zur Lösung von großen, symmetrischen, positiv definiten Gleichungssystemen der Form Ax = b." Wenn ich richtig verstanden habe, ist es eine Methode, um Gleichungssysteme der Form Ax=b zu lösen. Aber warum gerade dieses Verfahren und nicht z.B. das Gaußsche Eliminationsverfahren verwenden??? Gibt es hier etwa keine exakten Lösungen? Wozu die Angabe symmetrisch? Damit meinen die sicherlich, dass A eine symmetrische Matrix ist, aber was hat das für Auswirkungen auf ein Gleichungssystem? Und was bedeutet positiv definit? Die Erklärung im Wiki verstehe ich net . Kann mir bitte jemand helfen?
29.07.2009, 15:29	hyperbel	Auf diesen Beitrag antworten »
Ich habe in einem Buch noch folgendes gelesen: "...for solving non-linear equatations..." Das CG-Verfahren kann also nichtlineare Gleichungen auflösen, wenn ich richtig verstanden habe. Aber werden die Koeffizienten einer nichtlinearen Gleichung wie bei linearen Gleichungen so in die Matrix reingeschrieben oder gibt es dafür Verfahren?
31.07.2009, 08:34	Dunkit	Auf diesen Beitrag antworten »
Hallo! Bevor wir hier cg diskutieren können, müssen wir uns denke ich zunächst mal über einige grundlegendere Sachen unterhalten. Du hast schon richtig verstanden, dass es sich um ein Verfahren handelt, das die Lösung eines linearen Gleichungssystems bestimmen kann. Lässt man Rundungsfehler (die ein Computer immer macht) mal weg, dann liefert cg sogar die exakte Lösung des linearen Gleichungssystems in $\begin{eqnarray} N \end{eqnarray}$ Schritten (wobei $\begin{eqnarray} N \end{eqnarray}$ die Anzahl der Unbekannten sei). Wie du aber sicher auch schon bemerkt hast, ist cg ein iteratives Verfahren. Man könnte es zwar $\begin{eqnarray} N \end{eqnarray}$ Schritte ausführen lassen, um die exakte Lösung zu erhalten, in der Praxis ist es aber so, dass $\begin{eqnarray} N \gg 1 \end{eqnarray}$ und es sich kaum lohnt, so viele Iterationen durchzuführen. Man bricht das Verfahren also irgendwann ab, wenn man für den jeweiligen Zweck "nah genug" an der Lösung ist. Warum nicht das Gauss-Verfahren: Ganz einfach: Es ist viel zu langsam. Im Allgemeinen braucht das Gauss-Verfahren (wenn ich mich recht entsinne) $\begin{eqnarray} O(n^3) \end{eqnarray}$ Operationen, um die exakte Lösung zu berechnen. Das cg Verfahren ist hier wesentlich schneller (genauen Wert habe ich gerade nicht im Kopf). Symmetrisch positiv definit. Du wirst in diesem Zusammenhang oft die Forderung "Sei $\begin{eqnarray} A \end{eqnarray}$ spd" (Also symmetrisch, positiv definit) lesen. Was symmetrisch bedeutet ist klar. Positiv definit heißt, dass $\begin{eqnarray} xAx^T > 0 \quad \forall x \in \mathbb{R} \end{eqnarray}$ . Aus der positiven Definitheit folgen eine ganze Menge Sachen, insbesondere bzgl der Eigenwerte. Es sei dazu auf die Vorlesung "Lineare Algebra" verwiesen. Beides sind Forderungen, die meist für die theoretische Belegbarkeit der Verfahren gemacht werden. Mir ist aber zumindest von anderen Verfahren, bei denen in der Theorie diese Forderungen gestellt werden, bekannt, dass sie in der Praxis aus ohne diese Forderungen auskommen. Ich nehme an das wird beim cg-Verfahren ähnlich sein. Nichtlineare Gleichungssysteme: Generell ist CG erstmal für lineare Gleichungssysteme gedacht. Es spricht aber nichts dagegen, es zum Beispiel zusammen mit dem Newton-Verfahren auch für nicht-lineare Probleme zu benutzen. Damit würde ich mich an deiner Stelle aber erst später beschäftigen. CG ist eigentlich ein "Spezialfall" der Krylov-Unterraum-Verfahren. Wenn du wirklich ein solides Grundwissen über CG erhalten willst, würde ich dir daher raten, "oben" anzufangen, und dir erstmal die Idee dieser Gruppe von Verfahren anzueignen.
31.07.2009, 10:14	tigerbine	Auf diesen Beitrag antworten »
Will mich in die Diskussion nicht einmischen. Hier steht ein bisschen was über das Verfahren. Der Beweis bei CG ist i.A. "unangenehm lang". Katalog: Workshops & Aufgaben & Videos
31.07.2009, 12:14	Dunkit	Auf diesen Beitrag antworten »
Mist, hätte ich den Artikel gekannt hätte ich mir ja das Blättern im Skript sparen können Aber naja ich glaube wir müssen hier sowieso erstmal ein paar Grundlagen schaffen

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »