Diskussion:Gauß-Newton-Verfahren

D ist Jacobi-Matrix des Systems (2007)

Ich fände es hilfreich, wenn unter "Aufbau der Matrizen für die Iteration: D = (...)" erwähnt wird, dass es sich bei D um eine Jacobi-Matrix handelt. Zudem fände ich einen Link auf den Wikipedia-Artikel hilfreich (http://de.wikipedia.org/wiki/Jacobi-Matrix). Die Schreibweise der partiellen Ableitungen sollten einheitlich sein (ich ziehe die Darstellung mit d/dx vor). (Leider kenne ich mich nicht ausreichend mit Wikipedia aus, um das selbst zu ändern). 85.226.244.254 15:17, 01. Mai 2007 (CEST)

Allgemeine Beschreibung und Konvergenz (2005)

Der Artikel braucht statt des Beispiels eine vernünftige Beschreibung des Verfahrens für den allgemeinen Fall und dazu Aussagen über Konvergenzgeschwindigkeit etc. Viele Gruesse --DaTroll 14:17, 10. Apr 2005 (CEST)

Ja, das ist jetzt der zweite Artikel, den ich hier neu angelegt habe und den Du mir wegen Deiner Erweiterungswünsche als Überarbeitung kennzeichnest. Wie wäre es mit einem eigenen Beitrag zu dem Thema? Die allgemeine Formulierung ist sehr aufwendig und abstrakt, Deine Hilfe wäre also außerordentlich Willkommen. Ralf Pfeifer 14:39, 17. Apr 2005 (CEST)

Anregungen, zu klärende Details, Quadrat von Matrizen (2005)

Anregungen:

• Ich finde den ersten Satz etwas unklar. Was ist die eigentliche Aufgabe?
• Wogegen konvergiert die Iteration? Wird

$\sum (f(x_{i,1},x_{i,2})-y_{i})^{2}$

minimiert? Das kann ich raten, aber explizit formuliert habe ich das nicht gefunden.

• Die Beispielfunktion ist affin in $\ln a_{1}$ und $a_{2}$, dann sollte eine einfache lineare Regression genügen?
• Ist $\mathbf {D} ^{T}\cdot \mathbf {D}$ invertierbar, wenn ja, wieso?

--Gunther 18:20, 22. Apr 2005 (CEST)

Na, ich hoffe, jetzt ist es gut. Aus der Literatur weiß ich, dass $\mathbf {D} ^{T}\cdot \mathbf {D}$ stets symmetrisch und positiv definit ist, damit also lösbar. Die Herleitung kenne ich allerdings nicht, vermutlich ist $\mathbf {D} ^{T}\cdot \mathbf {D}$ so etwas wie das Quadrat einer Matrix. Ralf Pfeifer 19:44, 23. Apr 2005 (CEST)

das Quadrat einer Matrix ist im Allgemeinen definiert als $A^{2}:=\mathbf {A} \cdot \mathbf {A}$ -- 85.197.2.247 20:13, 23. Apr 2005 (CEST)

Ich habe nicht gesagt, dass irgendetwas schlecht ist. "Anregungen" war durchaus wörtlich gemeint. Damit das mit $\mathbf {D} ^{T}\cdot \mathbf {D}$ funktioniert, muss $\mathbf {D}$ trivialen Kern haben. Vielleicht ist das klar, ich überschaue das nicht. In der Einleitung ist mir immer noch nicht klar, wieso die Probleme erst aus der Methode der kleinsten Quadrate entstehen. Ich hätte gedacht, das Ausgleichsproblem ist die primäre Fragestellung, und die Methode der kleinsten Quadrate definiert, was unter einer Lösung des Problems zu verstehen ist.--Gunther 20:07, 23. Apr 2005 (CEST)

Soweit ich mich erinnere, gibt es beim Quadrat wohl zwei Richtungen in der Mathematik: Eine, die Deine Definition bevorzugt und eine andere, die meine bevorzugt. Mit dem "Na, ich hoffe, jetzt ist es gut" meinte ich auch die Mängel, die mir selbst nicht gefallen haben.

Ich bin nicht ganz sicher, ob ich das, was Du mit "wieso die Probleme erst aus der Methode der kleinsten Quadrate entstehen" meinst. Wie würdest Du die Einleitung schreiben? Ralf Pfeifer 22:34, 23. Apr 2005 (CEST)

Der Satz mit dem Quadrat oben stammt nicht von mir. Ich würde es so sehen, wie Du schreibst, beides hat je nach Kontext seine Berechtigung. Für nichtquadratische Matrizen kann man $A^{2}$ ja auch gar nicht bilden.

Ich verstehe einfach nicht ganz, was Du mit "Ausgleichsproblemen, die aus ... entstehen" meinst. Mein Gedankengang wäre: Daten --> vermutete Formel --> Ausgleichsproblem, und erst dann die kleinsten Quadrate. Wäre es ein Verlust, den Nebensatz "die aus ... entstehen" einfach wegzulassen?--Gunther 23:00, 23. Apr 2005 (CEST)

Also wenn ihr meint, dass man gelegentlich auch A^2 := A^T * A definiert würde mich interessieren wo man sowas braucht.. sobald man mit der Transponiereten agiert könnte man ja alternativ auch immer A^2 := A * A^T definieren was dann für nicht quad. Matrizen was anderes wäre...

A^2 := A * A is ja z.B. beim Einsetzen von Matrizen die Endomorphismen beschreiben in Polynome (z.B. Minimalpolynom) Standard.. -- 85.197.2.247 08:57, 24. Apr 2005 (CEST)

Ich weiß nicht mehr, wo ich es mit dem Quadtar her habe, ich glaube es wurde in einer Anleitung für einen matrixfähigen HP Taschenrechner (15C, 28, 48) vorgestellt. Wenn man sich für $\mathbf {D} ^{T}\cdot \mathbf {D}$ entscheidet, dann kann man jede Matrix quadrieren. Ralf Pfeifer 09:30, 24. Apr 2005 (CEST)

Es wollte niemand $A^{2}$ für dieses Quadrat schreiben, und wenn ich "Quadrat einer Matrix" höre, denke ich an $A^{2}=A\cdot A$. Trotzdem ist $A^{T}\cdot A$ eine sinnvolle Verallgemeinerung des Quadrates einer reellen Zahl: für $1\times 1$-Matrizen stimmt es mit dem Quadrat des Eintrages überein, und es ist stets positiv semidefinit, während z.B. ${\begin{pmatrix}0&1\\-1&0\end{pmatrix}}^{2}=-1$ ist.--Gunther 11:17, 24. Apr 2005 (CEST)

Taylor-Polynom fehlt

Bei der Erklärung des Verfahrens fehlt jeder Hinweis auf die eigentliche Idee hinter dem Verfahren (also die lineare Approximation mittels Taylor-Polynom 1ten Grades, analog zur Tangente bei Newton). Das wird dann erst im Vergleich am Ende des Artikels erwähnt. Ich hab' jetzt mal an den Anfrang einen Hinweis auf Taylor rein geschrieben, aber das überschneidet sich jetzt natürlich mit dem Abschnitt über die Unterschiede zum Newton-Verfahren. Ich finde aber, dass das auf jeden Fall an den Anfang muss, weil sonst wohl kaum jemand versteht, woher plötzlich die Jacobi-Matrix kommt. (nicht signierter Beitrag von Juergen861 (Diskussion | Beiträge) 15:04, 8. Mär. 2010 (CET))

Seite überarbeiten?

Im Vergleich zu anderen ähnlichen Seiten (siehe z.B. Gauß-Verfahren) wirkt diese Seite sehr irritierend. Es werden konkrete Rechenregeln erörtert, ohne auf die Hintergründe einzugehen (obwohl sich dieses Verfahren sehr anschaulich erklären läßt). Ich finde die englische Fassung wesentlich aufschlußreicher und würde dafür stimmen, diese ins Deutsche zu übertragen. -- 95.116.77.114 13:21, 28. Feb. 2011 (CET)

QR-Zerlegung statt Normalengleichungen

Für den Iterationsschritt werden in diesem Artikel die sehr schlecht konditionierten Normalengleichungen verwenden, obwohl mit der QR-Zerlegung eine Alternative existiert, welche numerisch stabiler und wohl auch schneller ist. Ist es hier die Absicht das Vefahren für die Berechung von Hand darzulegen oder sollten nicht auch numerische Aspekte berücksichtigt werden? --Betsim 16:27, 4. Jul. 2011 (CEST)

Nochmal zum Überarbeiten

Nachdem Leute nun schon so irritiert wurden, dass sie das mehrdimensionale Newton-Verfahren für falsch halten, ist eine klare Darstellung im Artikel von ein paar Grundaussagen angebracht. Diese sollten enthalten:

• Ausgangspunkt ist ein überbestimmtes nichtlineares Gleichungssystem F(x)=y. Dass y extra aufgeführt wird, dient der Anschaulichkeit, dies Konstanten könnten auch in die Funktionen F absorbiert werden.

• Die Grundidee des Verfahrens ist die Bestimmung des nächsten Schrittes durch Minimieren des (Quadratsummen-)Residuums der linearen Näherung, d.h., von

$\|F(x)+F'(x)s-y\|_{2}^{2}.$

• Es ist direkt sichtbar, dass dieses Verfahren, angewandt auf ein reguläres quadratisches System, wieder zum Newton-Verfahren zurückführt.

• Minimieren des quadratischen Ausdrucks führt direkt auf die Bedingung

$F'(x)^{T}F'(x)s=F'(x)^{T}(y-F(x))$

und damit die Lösungsformel

$s=F'(x)^{\oplus }(y-F(x)).$

mit der Moore-Penrose-Pseudo-Inversen

$F'(x)^{\oplus }=(F'(x)^{T}F'(x))^{-1}F'(x)^{T}.$

Diese kann mit SVD oder QR-Zerlegung von F'(x) bestimmt werden, ohne die numerisch instabile Multiplikation von F'(x) mit sich selbst auszuführen. D.h., diese Multiplikation gefolgt von einer Cholesky-Zerlegung, wie derzeit im Artikel propagiert, ist die numerisch schlechteste Variante.

• Mit einer QR-Zerlegung F'(x)=QR kann aber auch direkt die der Schritt aus dem Gleichungssystem

$Rs=Q^{T}(y-F(x))$

bestimmt werden, unter Weglassen der unteren Zeilen des transformierten Gleichungssystems, also dort, wo R Nullzeilen hat.

• Optimierung mit Newton-Verfahren angewandt auf das Residuum

$\|F(x+s)\|_{2}^{2}$

geht von der quadratischen Näherung

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \|F(x)\|_2^2+2F(x)^TF'(x)s+s^TF'(x)^TF'(x)s+F(x)^TF''(x)[s,s]}

aus, die zweite Ableitungen des Gleichungssystems enthält und damit ein von Gauß-Newton verschiedenes Verfahren darstellt.

Es ist zu diskutieren, ob eine Darstellung in Matrixkomponenten, wie jetzt im Artikel, aus pädagogischer Sicht sinnvoll ist und erhalten bleiben sollte, neben der oben angesprochenen Kurzfassung der Operationen.--LutzL (Diskussion) 18:50, 6. Nov. 2013 (CET)

Ich habe auf meiner Benutzerseite begonnen den Artikel komplett neu zu schreiben, mit dem Ziel die derzeitige Fassung zu ersetzen. Wer Zeit und Lust hat kann sich den aktuellen Stand ja mal ansehen - Verbesserungsvorschläge jederzeit willkommen. --Pingpong128 (Diskussion) 21:55, 6. Mai 2019 (CEST)

In der Optimierungspraxis (auch für Studenten und Berufsanfänger) ist die Lineare-Algebra-Variante so ziemlich Standard, daher finde ich die Matrixnotation schon sinnvoll... --Megid (Diskussion) 10:38, 25. Mär. 2021 (CET)

Falls sich jemand im Detail auskennt: Mir fehlt im Abstiegsschritt ein bisschen die Intuition für die Unterschiede von gradient descent bis hin zu Gauss-Newton. Man könnte z.B. average(Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle J} , axis=0) runtergehen, oder Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle J^T \cdot r} , oder wie bei GN Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (J^T J)^{-1} \cdot J^T \cdot r} . Welche Auswirkungen hat jeder Zwischenschritt, oder jede Komponente? Das ist mir von der Intuition her ziemlich unklar. --Megid (Diskussion) 10:38, 25. Mär. 2021 (CET)

Ich verstehe die Frage leider nicht ganz. Meinst du wie man die Abstiegsrichtung berechnet? Auf der Seite zum Gradientenverfahren#Bestimmen_der_Abstiegsrichtung sind verschiedene Methoden angeführt, u.a. das GN Verfahren. Du kannst eine allgemeine Funktion immer mit dem Verfahren des steilsten Abstiegs optimieren, aber wenn das Problem mehr Struktur hat dann gibt es u.U. schnellere Methoden. Für Probleme mit der speziellen Struktur "Summe von Quadraten von Funktionen" ist der GN Algorithmus eine solche schnellere Methode. Der Abstiegsschritt ergibt sich hier wie im Artikel erklärt aus dem Ansatz, eine lineare Approximation des ursprünglichen Problems zu minimieren. --193.83.51.169 14:10, 27. Apr. 2021 (CEST)