Levenberg-Marquardt-Algorithmus

11.11.2008, 17:50

Jayk

Auf diesen Beitrag antworten »

Levenberg-Marquardt-Algorithmus

Hallo,

ich hab mir schon die Seite dazu auf der englischen und auf der deutschen Wikipedia angeguckt, und verstehe irgendwie nur Bahnhof. Liegt möglicherweise auch daran, dass ich nicht weiß, was die Doppel-Pipes (||) bedeuten.

Würde sich sonst vielleicht jemand die Zeit nehmen, mir an einem kleinen Beispiel den Algorithmus zu erleutern?

Oder vielleicht kennt ja auch jemand eine gute Implementation in C oder Pascal? Würde mir auch helfen.

Edit (mY+): Bitte keine Hilferufe im Titel! Titel modifiziert.

11.11.2008, 19:58

system-agent

Auf diesen Beitrag antworten »

Diese "Doppelpipes" wie du es nennst ist das Symbol für die Norm.
Genauer:
Eine Norm ist eine Abbildung $\begin{eqnarray*} \|\cdot\|:\mathbb R^n\to\mathbb R \end{eqnarray*}$ mit gewissen Eigenschaften [die kannst du bei Wikipedia finden].
Der Witz einer Norm ist einfach, dass sie eine "Längenmessung" für Vektoren bietet.
Nehmen wir mal die Ebene $\begin{eqnarray*} \mathbb R^2 \end{eqnarray*}$ und definieren für einen Vektor $\begin{eqnarray*} x=(x_1,x_2)\in\mathbb R^2 \end{eqnarray*}$ die "2-Norm": $\begin{eqnarray*} \|x\|_2:=\sqrt{x_1^2+x_2^2} \end{eqnarray*}$ .
Dass dies wirklich eine Norm ist kann man leicht sehen und du stellst fest dass es genau das ist, was du unter der "Länge" von $\begin{eqnarray*} x \end{eqnarray*}$ kennst wenn du es mit Pythagoras bestimmst.

11.11.2008, 20:32

Jayk

Auf diesen Beitrag antworten »

Ah, OK, danke! Vielleicht hilft das ja schon.

EDIT: Bisher war mir nur die Euklidische L-2-Norm bekannt. Augenzwinkern

Augenzwinkern

11.11.2008, 20:42

system-agent

Auf diesen Beitrag antworten »

Nur so aus reiner Neugierde: Wieso kennst du die L2-Norm aber dann nicht eine einfache Vektornorm?

11.11.2008, 20:57

Jayk

Auf diesen Beitrag antworten »

Da ich (freizeitmäßig) in Delphi programmiere, habe ich mir mal die Math-Unit angeschaut. Und da gab's eine Funktion für die L-2-Norm.

Weil eigentlich war das noch nicht in der Schule dran. Augenzwinkern

Augenzwinkern

Also so von der Wikipedia hab ich's noch nicht verstanden, aber ich kann auch noch mal googlen, ob ich da ein paar Beispiele finde.

EDIT: Sehe ich das jetzt richtig, dass:

$\begin{eqnarray*} L-2-Norm = \mid \mid x \mid \mid _{2}^{2} \end{eqnarray*}$

11.11.2008, 21:04

system-agent

Auf diesen Beitrag antworten »

Du musst ein bischen mit den Bezeichnungen aufpassen, deshalb auch meine Frage:
Es gibt wirklich eine $\begin{eqnarray*} L_2 \end{eqnarray*}$ -Norm, aber die ist leicht komplizierter und in dem Wiki-Artikel über deinen Algorithmus auch garnicht gemeint.
Da ist wirklich nur die 2-Norm gemeint.

Anzeige

11.11.2008, 21:19

Jayk

Auf diesen Beitrag antworten »

OK, noch eine Frage:

Was ist die Jacobi-Matrix? Ich werde aus dem Wiki-Artikel da irgendwie gar nicht schlau. Weil ansonsten kapiere ich erst einmal ansatzweise den Gauß-Newton-Algorithmus. Angeblich baut Levenberg-Marquardt ja darauf auf?

11.11.2008, 21:20

tigerbine

Auf diesen Beitrag antworten »

Was weißt du denn über das Problem, dass der Algorithmus lösen will?

11.11.2008, 21:26

Jayk

Auf diesen Beitrag antworten »

Nun, ein Algorithmus für nichtlineare Least-Square-Probleme (bzw. deren Lösung), also nichtlineare Regression bzw. Curve-fitting.

11.11.2008, 21:39

tigerbine

Auf diesen Beitrag antworten »

Und du weißt wie diese Probleme gelöst werden? Augenzwinkern

Augenzwinkern

http://de.wikipedia.org/wiki/Jacobi-Matrix

11.11.2008, 21:40

system-agent

Auf diesen Beitrag antworten »

Jetzt kommt gleich "mit dem Algorithmus" Big Laugh

Big Laugh

11.11.2008, 21:41

tigerbine

Auf diesen Beitrag antworten »

Big Laugh

Willkommen in der Warteschleife

12.11.2008, 19:09

Jayk

Auf diesen Beitrag antworten »

Zitat:

Original von tigerbine
Und du weißt wie diese Probleme gelöst werden? Augenzwinkern

Augenzwinkern

http://de.wikipedia.org/wiki/Jacobi-Matrix

Nein, ich kenne wie gesagt nur die Problemstellung. Sonst würde ich ja nicht fragen. Es gibt halt nirgens eine wirklich einfache Erklärung für sowas. Ich sehe gerade partielle Ableitung... Das verstehe ich nicht ganz. Die Ableitung ist doch die Steigung der Funktion, wie kann man das mit nur einem Parameter machen?Bei Wikipedia steht ja:

$\begin{eqnarray*} \frac{\partial f}{\partial x_i}(a) := \lim_{h\to 0} \frac{f(a_1,\ldots,a_i+h,\ldots,a_n) - f(a_1,\ldots,a_i,\ldots,a_n)}{h} \end{eqnarray*}$

Was ist jetzt $\begin{eqnarray*} x_{i} \end{eqnarray*}$ ? Und was ist h?

Und wenn ich sehe (Ausschnitt aus einem Physikbuch):

$\begin{eqnarray*} \frac{d}{dt} (t^{n}) \end{eqnarray*}$

Ist das dasselbe?

Ich glaube, mir fehlt da noch ein wenig Hintergrundwissen (wie gesagt, in der Schule war das noch nicht dran). Gibt's irgendwo eine gute Einleitung in Analysis?

12.11.2008, 19:17

tigerbine

Auf diesen Beitrag antworten »

Zitat:

Ich glaube, mir fehlt da noch ein wenig Hintergrundwissen (wie gesagt, in der Schule war das noch nicht dran). Gibt's irgendwo eine gute Einleitung in Analysis?

Meine Rückfrage war auch nicht böse gemeint. Nur sind wir mit dem Verfahren in der Mehrdimensionalen Analysis (meist Ana III), da kommen bei den Ableitungen dann Matrizen ins Spiel und partielle Ableitungen. In der Schule wird das imho gar nicht behandelt werden.

Ich will dir Überfliegerqualitäten nicht absprechen, aber wenn es dir hauptsächlich um das programmieren geht, würde ich mir im Moment ein anderes Thema suchen.

Zu diesem solltest du 3 Analysis-Skripte gelesen haben, und für Matrizen noch ein Grundwissen in linearer Algebra haben.

Wink

Wink

12.11.2008, 19:21

Jayk

Auf diesen Beitrag antworten »

Mir geht es nicht hauptsächlich ums Programmieren. Dass ich den Algo dann auch coden möchte, ist eine andere Sache. Wichtiger wäre es mir, die Mathematik dahinter zu verstehen. Und mich nervt das mit den partiellen Ableitungen schon ziemlich lange.

Ich werde mich mal dazu belesen...

12.11.2008, 19:33

system-agent

Auf diesen Beitrag antworten »

Du kennst schon Funktionen von einer Variablen, also zb
$\begin{eqnarray*} f:\mathbb R\to\mathbb R \end{eqnarray*}$ mit $\begin{eqnarray*} f(x)=x^2 \end{eqnarray*}$ .

Man kann auch Funktionen betrachten die von mehr als einer Variablen abhängen. Nehmen wir mal eine die von 2 Variablen abhängt und wir schreiben vor, dass diese Variablen nicht negativ sein dürfen, dann schreibt man zb.
$\begin{eqnarray*} f:[0,\infty[\times[0,\infty[\to\mathbb R \end{eqnarray*}$ definiert durch
$\begin{eqnarray*} f(x,y)=x\cdot y \end{eqnarray*}$

Solche Funktionen kennst du schon, zb ist die Formel für die Fläche eines Rechtecks so eine Funktion: Sie braucht zwei Angaben um ein Ergebnis zu liefern.

Nun kann man das Spiel weitertreiben und auch $\begin{eqnarray*} n \end{eqnarray*}$ Variablen nehmen.
Man nummeriert diese dann eben einfach durch: $\begin{eqnarray*} x_1,x_2,...,x_n \end{eqnarray*}$ und schreibt
$\begin{eqnarray*} f(x_1,...,x_n) \end{eqnarray*}$ , wobei man noch sagen muss was $\begin{eqnarray*} f \end{eqnarray*}$ tut und den genauen Definitionsbereich braucht man auch noch.
Hält man nun alle Variablen bis auf eine, zb $\begin{eqnarray*} x_1 \end{eqnarray*}$ , fest, dann hat man eine Funktion von nur noch einer Variablen und man kann nach dieser ableiten und schreibt
$\begin{eqnarray*} \frac{\partial f}{\partial x_1} \end{eqnarray*}$
Das ist in etwa die Idee der partiellen Ableitung.

Nehmen wir mal $\begin{eqnarray*} f:\mathbb R\times\mathbb R\to\mathbb R \end{eqnarray*}$ definiert durch $\begin{eqnarray*} f(x,y)=\sin(x)\cdot y+y^2 \end{eqnarray*}$ .
Dann ist
$\begin{eqnarray*} \frac{\partial f}{\partial x}=\cos(x)\cdot y \end{eqnarray*}$
$\begin{eqnarray*} \frac{\partial f}{\partial y}=\sin(x)+2y \end{eqnarray*}$

12.11.2008, 19:40

Jayk

Auf diesen Beitrag antworten »

Zum Beispiel:

d yx² (y) = 2xy ?

Ist das so richtig?

12.11.2008, 19:42

system-agent

Auf diesen Beitrag antworten »

Das musst du nochmal schreiben, ich kann weder die Funktion erkennen noch nach was abgeleitet wird.

12.11.2008, 20:10

Jayk

Auf diesen Beitrag antworten »

Sry, ich meine:

$\begin{eqnarray*} \frac{\partial (yx^{2})}{\partial y} = 2 \cdot xy \end{eqnarray*}$

?

12.11.2008, 20:16

system-agent

Auf diesen Beitrag antworten »

Nein, du leitest nach $\begin{eqnarray*} y \end{eqnarray*}$ ab. Betrachte dabei alle anderen Variablen als Konstanten.

12.11.2008, 20:19

Jayk

Auf diesen Beitrag antworten »

Achso, ich hab gedacht, y ist die Konstante (aber beim Ableiten nach x wäre es richtig, oder?). Augenzwinkern

Augenzwinkern

Dann also 0? Ableitung von f(y) = y ist ja 0, und 0 x² ist auch 0?

12.11.2008, 20:23

system-agent

Auf diesen Beitrag antworten »

Alles falsch.

Das was du hingeschrieben hast, war $\begin{eqnarray*} \frac{\partial (yx^2)}{\partial x} \end{eqnarray*}$ .

Die partielle Ableitung nach $\begin{eqnarray*} y \end{eqnarray*}$ ist nicht Null.

12.11.2008, 20:25

Jayk

Auf diesen Beitrag antworten »

Ich glaub heute hab ich ein Brett vor'm Kopf. Ich probier's morgen nochmal.

12.11.2008, 20:34

Jayk

Auf diesen Beitrag antworten »

Zitat:

Original von system-agent
Die partielle Ableitung nach $\begin{eqnarray*} y \end{eqnarray*}$ ist nicht Null.

Was denn?

geschockt

12.11.2008, 20:40

system-agent

Auf diesen Beitrag antworten »

Du solltest dir erstmal angewöhnen Funktionen ordentlich aufzuschreiben. Gerade im Mehrdimensionalen ist das wichtig. Also du hast
$\begin{eqnarray*} f:\mathbb R\times\mathbb R\to\mathbb R \end{eqnarray*}$ gegeben durch $\begin{eqnarray*} (x,y)\mapsto yx^2 \end{eqnarray*}$ .

Dann ist
$\begin{eqnarray*} \frac{\partial f}{\partial x}(x,y)=2yx^2 \end{eqnarray*}$
denn man betrachtet alle Variablen ausser $\begin{eqnarray*} x \end{eqnarray*}$ als Konstanten.
Ähnlich:
$\begin{eqnarray*} \frac{\partial f}{\partial y}(x,y)=x^2 \end{eqnarray*}$
denn $\begin{eqnarray*} x^2 \end{eqnarray*}$ ist eine Konstante.

12.11.2008, 20:47

Elan

Auf diesen Beitrag antworten »

@ Jayk

Du hast eine PN, wenn du magst, melde dich mal. Augenzwinkern

Augenzwinkern

13.11.2008, 14:07

Jayk

Auf diesen Beitrag antworten »

Zitat:

Original von system-agent
Du solltest dir erstmal angewöhnen Funktionen ordentlich aufzuschreiben. Gerade im Mehrdimensionalen ist das wichtig. Also du hast
$\begin{eqnarray*} f:\mathbb R\times\mathbb R\to\mathbb R \end{eqnarray*}$ gegeben durch $\begin{eqnarray*} (x,y)\mapsto yx^2 \end{eqnarray*}$ .

OK, ich werd's mir angewöhnen (Problem war eher LaTeX, weil ich nicht wusste wie die Zeichen aussehen.

Zitat:

Original von system-agent
Dann ist
$\begin{eqnarray*} \frac{\partial f}{\partial x}(x,y)=2yx^2 \end{eqnarray*}$
denn man betrachtet alle Variablen ausser $\begin{eqnarray*} x \end{eqnarray*}$ als Konstanten.
Ähnlich:
$\begin{eqnarray*} \frac{\partial f}{\partial y}(x,y)=x^2 \end{eqnarray*}$
denn $\begin{eqnarray*} x^2 \end{eqnarray*}$ ist eine Konstante.

Ah, OK, jetzt hab ich's fast kapiert, jedenfalls das Prinzip. Aber

Funktion yx^2 und alles außer x ist eine Konstante. Also hätte man dann nicht 2xy? Wie kommst du auf $\begin{eqnarray*} 2yx^{2} \end{eqnarray*}$ ?

@Elan: Schon geschehen.

13.11.2008, 16:36

system-agent

Auf diesen Beitrag antworten »

Ich habe da einen Fehler, es müsst natürlich

$\begin{eqnarray*} \frac{\partial f}{\partial x}(x,y)=2yx \end{eqnarray*}$

heissen. Freude

Freude

13.11.2008, 17:29

Jayk

Auf diesen Beitrag antworten »

Ah, OK. Jetzt hab ich's kapiert. smile

smile

Jetzt sieht auch die Beschreibung auf Wikipedia nicht mehr so kryptisch aus. Danke euch! Wink

Wink

15.11.2008, 19:32

Jayk

Auf diesen Beitrag antworten »

Hallo,

ich hab noch eine Frage zur partiellen Ableitung. Und ich bin mir nicht ganz sicher, ob ich das, was ich bei diesem Beispiel gemacht hab, wirklich machen darf (zweite Rechnung).

$\begin{eqnarray*} f: \mathbb R \times \mathbb R \to \mathbb R \\ f(x, y) = y \cdot \frac{x}{y}^2 \\ \frac{\partial f}{\partial x}(x, y) = \frac{2x}{y} \\ \frac{\partial f}{\partial y}(x, y)=x^2 \cdot \left( -\frac{1}{y^2} \right) \end{eqnarray*}$

15.11.2008, 20:19

system-agent

Auf diesen Beitrag antworten »

Es sind sogar beide partiellen Ableitungen falsch.
Ausserdem: wo hast du denn diese Funktion aufgegabelt? Man kann mit $\begin{eqnarray*} y \end{eqnarray*}$ vereinfachen....
Das heisst du betrachtes eigentlich ein
$\begin{eqnarray*} f^*:\mathbb R\times\mathbb R\setminus\{0\}\to\mathbb R \end{eqnarray*}$
mit $\begin{eqnarray*} (x,y)\mapsto x^2 \end{eqnarray*}$ .

Dann ist $\begin{eqnarray*} \frac{\partial f^*}{\partial x}(x,y)=2x \end{eqnarray*}$ und $\begin{eqnarray*} \frac{\partial f^*}{\partial y}(x,y)=0 \end{eqnarray*}$ .
Man muss aber auf den Definitionsbereich aufpassen !

15.11.2008, 21:27

Jayk

Auf diesen Beitrag antworten »

Was bedeutet das \ {0} ? Wegen dem 1/y? Genau das hat mich so verunsichert...

15.11.2008, 21:51

system-agent

Auf diesen Beitrag antworten »

Die Definition ist
$\begin{eqnarray*} \mathbb R\setminus\{0\}:=\{x\in\mathbb R\quad:\quad x\neq0\} \end{eqnarray*}$ .

16.11.2008, 10:05

Jayk

Auf diesen Beitrag antworten »

Aha, also eine rationale Zahl <> 0? Weil y nicht null sein darf (x/0 = n. l.)?

Gibt's dafür irgendeinen Namen? Also für das \ {0}, dass ich mich darüber noch etwas belesen kann?

16.11.2008, 16:39

system-agent

Auf diesen Beitrag antworten »

Da brauchst du keinen Namen:
Sei $\begin{eqnarray*} X \end{eqnarray*}$ eine Menge und $\begin{eqnarray*} A \end{eqnarray*}$ eine Untermenge von $\begin{eqnarray*} X \end{eqnarray*}$ . Dann definiert man
$\begin{eqnarray*} X\setminus A:=\{x\in X\quad :\quad x\notin A\} \end{eqnarray*}$ .

Vielleicht nennen das gewisse Leute einfach Differenzmenge, wäre möglich.

17.11.2008, 18:17

Jayk

Auf diesen Beitrag antworten »

Achso. Danke!

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »