Diskussion:CG-Verfahren

Völlig unverständlich

Ich habe noch nie etwas von dem CG-Verfahren gehört. Aufgrund der Erklärung ist für mich nicht ersichtlich wozu das Verfahren dienen soll. Die Formeln sind mir gänzlich unverständlich. Ich denke, dass so ein Artikel nicht in eine Enzyklopädie gehört, da er absolut nicht allgemeinverständlich ist.

Benutzer:Fsswsb 02.05.06

Ich hoffe, dass nun zumindest die Idee einigermaßen verständlich rüberkommt.

--V4len 21:09, 4. Jun 2006 (CEST)

Es muss doch auch nicht jeder alles verstehen, oder? Ich beantrage jedenfalls auch nicht die Löschung einiger Kernphysik-Artikel, bloß weil das nicht mein Spezialgebiet ist.80.138.126.111 09:00, 29. Sep 2006 (CEST)

Also, ich versteh es nicht... :-(

Vielleicht kannst Du da etwas konkreter werden, was Du nicht verstehst.

--V4len 21:43, 10. Jul 2006 (CEST)

Ich habe bei Wikipedia den Begriff Enzyklopädie nachgeschaut. Dass in einer Enzyklopädie alles immer allgemeinverständlich sein soll, habe ich dort nicht gefunden. Wenn man hingegen in einer Enzyklopädie "das gesamte Wissen der Menscheit" darstellen möchte, wird man um enen solchen Artikel nicht herumkommen.

--

Siehe Abschnitt Kritik: "Zwar haben Enzyklopädien normalerweise den Anspruch, allgemeinverständlich auch für Laien zu sein, können ihn aber gerade bei naturwissenschaftlichen Themen nicht immer einhalten. Spezialisten neigen dazu, in ihren Artikeln zu sehr ins Detail zu gehen, anstatt die allgemeinen Aspekte darzustellen.[257]" Wikipedia richtet sich nicht (nur) an Mathematiker. --217.91.139.42 16:41, 2. Okt. 2013 (CEST)

2013

Ich bin mir sicher, dass sich die Unverständlichkeit von Wikipedia-Artikeln oft auch daraus ergibt, dass sie schlicht falsch sind. Wer lernen möchte, was Conjugate Gradients sind, soll sich ein gutes Mathematikbuch kaufen, und danach den Artikel verbessern. Der Englische Artikel ist übrigens viel besser verständlich als dieser hier. Was er besser macht: Begriffe statt Variablennamen benutzen (r0: erste Iteration, das wird nirgendwo geschrieben, sondern einfach nur vom Leser erwartet, dass er sich das selber herleitet); weniger "Protzerei" mit Fachbegriffen, die es zu Verlinken gilt. Anstatt von einem "Unterraum" zu sprechen wird mit einer einfachen Summenformel gezeigt, wie sich die Lösung x* aus den Vektoren di zusammensetzt; Schachtelsätze? Zuordnung von Formeln zu Absätzen? Da passt ja Vieles nicht im Deutschen Artikel. (nicht signierter Beitrag von 83.64.213.152 (Diskussion) 10:28, 14. Aug. 2013 (CEST))

Hi, das ist doch mal was Konkretes. r_0 wird nicht erklärt. Wenn man es zurückverfolgt, dann wird zwar schon r_k definiert, aber der gesamte Abschnitt leidet darunter, dass nicht erklärt wird, dass man eine Iteration betrachtet, dass iterativ eine Folge von Näherungen x_k konstruiert wird; das erste x_k fällt wirklich vom Himmel, auf x_0 wird nicht eingegangen. Sollte beim Erklären der Idee wirklich auf die Iteration eingegangen werden oder einfach nur die quadratische Funktion erklärt werden und wie man mittels Gradientenabstiegs einen tiefer liegenden Punkt findet?--LutzL (Diskussion) 11:51, 15. Aug. 2013 (CEST)

zu erledigen

• Wiederholungen im PCG-Verfahren auf eine elegante Art auslassen.
• eventuell eine Grafik, welche die Wahl der Suchrichtung verdeutlicht
• etwas zur Herleitung und evtl. Geschichte
• etwas zur Analyse: Konvergenzgeschw. etc.

Titel

Wäre Verfahren der konjugierten Gradienten oder Methode der konjugierten Gradienten ein besserer Titel, wobei der jetzige als Redirect beibehalten wird? --LutzL 8. Jul 2005 09:02 (CEST)

• Also in der Literatur wird es meines Wissens nach häufiger als CG-Verfahren bezeichnet.--80.138.88.162 8. Jul 2005 09:14 (CEST)
• Ich finde das bleibt sich gleich. In der (mir geläufigen) Literatur wird es sowohl als Verfahren der konjugierten Gradienten als auch als CG-Verfahren bezeichnet. Untereinander redirection ist aber auf alle fälle sinnvoll! --138.232.1.229 15:12, 18. Jan 2006 (CET)

Definition

Das CG_Verfahren wird als Methode zum Lösen von Gleichungssystemen definiert. Ist es nicht eher ein Verfahren der ( nichlinearen ) Optimierung? Siehe auch zur Idee im Artikel. Da Optimierungsverfahren in ihrer Güte an quadratischen Problemen gemessen werden, hat das (ein) CG-Verfahren mit seiner endlichen Schrittzahl "günstige" Eigenschaften.

Nein, eigentlich wird es fast ausschliesslich in der numerischen linearen Algebra eingesetzt. Allerdings stimmt ich Dir zu, dass die Herleitung etwas kurz ist und auf den Aspekt mehr eingegangen werden koennte. --P. Birken 12:38, 8. Feb. 2007 (CET)

maximieren

moin! auch auf die gefahr hin, mich als tölpel zu outen: will man E(x) nicht minimieren? im artikel steht maximieren Philipp

Hallo Phillip, die 2.Ableitung ist -A also negativ definit und das mit dem maximieren hat seine Richtigkeit. grüße --Mathemaduenn 10:03, 3. Mär. 2007 (CET)

Dann bitte aber auch die erklärende Zeichnung mit maximieren erklären, da ist von minimieren die Rede. Im Übrigen kenne ich die Funktion E(x) auch so gegeben, dass man danach ein minimierunsproblem hat (also alles einfach negativ) --Flo0815 14:30, 11. Aug. 2008 (CEST)

Done. --P. Birken 19:11, 11. Aug. 2008 (CEST)

Ich sehe auch zum ersten Mal, dass das CG-Verfahren versucht, ein quadratisches Funktional zu maximieren - mir ist E(x) aber auch als $E(x)=1/2<Ax,x>-<b,x>$ bekannt, welches man dann eben minimieren will, wie z.B. in dem berühmten painless CG Artikel oder bei Wolfram Mathworld. Nicht umsonst zählt man CG, seine kleine Schwester Gradientenverfahren und die Methode des steilsten Abstiegs (steepest descend method) zur Klasse der sog. Abstiegs-Verfahren -- so, wie es momentan im Artikel steht, wäre CG eher ein Aufstiegs-Verfahren. Alhexx 2009-01-17

Ich habs nach einem Blick in weitere Bücher mal aufs Minimieren umgestellt, bitte mal gucken ob ich irgendwo was vergessen habe. --P. Birken 22:42, 25. Jan. 2009 (CET)

Alpha muss erst erklärt oder definiert werden

Das Alpha taucht mitten im Algorithmus auf, ohne vorher erwähnt oder definiert zu werden. Außerdem wird zwar gesagt, dass die Idee des CG-Verfahrens die Äquivalenz des Maximierens und des eigentlichen Lösens ist - aber nicht, ob die Idee stimmt, oder woher sie kommt oder woraus sie sich ergibt.

Beides erschwert das Lesen und Verstehen des Artikels für Neulinge, denke ich. --141.35.185.149 18:15, 24. Apr. 2007 (CEST)

Hallo 141.35.185.149,

es wird erklärt, dass das Minimum der Funtion von $x$ in Richtung $d$ gesucht wird. Damit ergibt sich zwangsläufig, dass das Minimum die Gestalt $x+\alpha \cdot d$ haben muss. Ich halte es daher für überflüssig, den Text im Algorithmus zu erweitern. Allerdings wäre sicherlich eine Skizze sehr hilfreich. Hat jemand Zeit und Lust sowas zu erstellen? --V4len 11:54, 25. Apr. 2007 (CEST)

Bild ist unverständlich

Ich habe immer gedacht, dass beim CG-Verfahren aufeinanderfolgende Richtungsvektoren orthogonal zueinander wären. Die roten Linien stehen aber nicht senkrecht aufeinander. Ich denke, diese Grafik müsste optimiert werden...

Nein, die Vektoren sind A-konjugiert. --P. Birken 09:11, 7. Jul. 2008 (CEST)

Das kommt ganz auf die Definition von "orthogonal zueinander" an. Sie sind "orthogonal zueinander", allerdings im Skalar-Produkt < d_i, A d_j >, und nicht im Standard-Skalarprodukt < d_i, d_j >, welches bildlich dargestellt hieße, dass sie einen rechten Winkel einschließen würden. Alhexx, 2009-01-17

Urheber

Das Hestenes, Stiefel die Methode einführten steht z.B. in Golub, Ortega Scientific computing and differential equations, Academic Press, S.305, oder Gutknecht, contributions to numerical analysis in the 1950s, postscript datei--Claude J 14:45, 23. Aug. 2010 (CEST)

Ist nicht $K^TAK$ trivial positiv definit, wegen $x^TK^TAKx = (Kx)^TAKx$? Wozu da der Sylvestersche Trägheitssatz (nicht signierter Beitrag von 82.113.98.175 (Diskussion) 16:07, 19. Feb. 2013 (CET))

Transponierte Matrizen

Im Abschnitt "Erweiterung auf unsymmetrische Matrizen" wird geschrieben: "Beide Verfahren haben den Nachteil, dass zum einen $A^{T}$ zur Verfügung stehen muss, was nicht immer gegeben ist".

Ist nicht aber die Bestimmung der transponierten Matrix $A^{T}$ wegen $(A^{T})_{ij}=A_{ji}$ ($i,j=1,...,n$) stets möglich und das Auslesen eines Eintrages genau so leicht wie das Auslesen eines Eintrages aus $A$? Kann jemand ein Beispiel angeben, wo die Bestimmung von $A^{T}$ nur schwer möglich ist? Ansonsten schlage ich eine Änderung des Satzes vor. (MfG, Marcel) --2001:4C80:40:480:21D:9FF:FE1D:6963 07:46, 10. Jul. 2013 (CEST)

Für eine dünn kodierte Matrix, deren Kodierung auf die Auswertung von Ax optimiert ist, ist die Auswertung der Transpoierten auf jeden Fall aufwändiger. In Anwendungen bei partiellen Differentialgleichungen kann aber auch die Auswertung von Ax einfach als Prozedur im Code mit Aufwand O(n) vorliegen, so dass die Transponierte bzw. der Zugriff auf alle Matrixeinträge nur mit Aufwand von n Aufrufen der Prozedur und damit O(n^2) erfolgen kann. Für große n kann das zur Einschätzung "unpraktikabel" führen. Man denke z.B. an Jacobi-Matrizen im Newton-Verfahren, wo Richtungsableitungen mit dem Vorwärtsmodus des Automatischen Differenzierens einfach bestimmt werden können. Nicht immer ist der Rückwärtsmodus verfügbar, und er ist immer aufwändiger.--LutzL (Diskussion) 12:17, 15. Aug. 2013 (CEST)

Vergleich zu anderen Methoden

Ist es richtig, dass MinRes für spd-Matrizen maximal denselben Residuenverlauf um zwei Iterationen nach rechts verschoben hat? Also wenn man den Residuenverlauf über die Iterationen aufträgt für CG und MinRes, entspricht die Kurve von MinRes der von CG, aber um (höchstens) zwei Iterationen nach rechts verschoben. Ist das richtig? Erscheint es auch anderen sinnvoll, Bezug zwischen CG und anderen Kryov-Methoden herzustellen? Im englischen Wiki haben sie beispielsweise einen kompletten Artikel dazu (http://en.wikipedia.org/wiki/Derivation_of_the_conjugate_gradient_method). VG (nicht signierter Beitrag von 88.78.116.253 (Diskussion) 22:53, 19. Aug. 2014 (CEST))