Das Levenberg-Marquardt-Verfahren

• Das Levenberg-Marquardt-Verfahren ist ein Verfahren zur Lösung nichtlinearer Ausgleichsaufgaben. Hier wird zu einem Satz von Daten t_i,y_i eine Funktion (Fit) f(t,x) gesucht, so daß die Summe der Fehlerquadrate S(x) = ||F(x)||₂² minimal wird. Die Komponenten des Vektors F(x) sind dabei die "Fehler" F_i(x) = f(t_i,x) - y_i. Die Funktion f(t,x) kann nichtlinear vom ''Parametervektor'' x abhängen.
• Ausgehend von einem Startvektor x₀ wird iteriert: x_k+1 = x_k+d_k.
  Hierbei ist d_k die Lösung einer ungleichungsrestringierten linearen Ausgleichsaufgabe:
  ||F(x_k) + J_F(xk)d ||² = min_d mit ||D_kd|| <= delta_k (D_k ist hier eine Diagonalmatrix mit positiven Einträgen)
• J_F ist die Jacobimatrix von F und wird mittels des Vorwärtsdifferenzenquotienten angenähert. Der sogenannte "Vertrauensbereichradius" delta_k wird adaptiv aus der Übereinstimmung zwischen den Differenzen ||F(x_k)||²-||F(x_k+1)||² und ||F(x_k)||²-||F(x_k) + J_F(xk)d_k ||² gesteuert. rho in der graphischen Ausgabe (3. Bild) ist der Quotient zwischen diesen Differenzen. Mit rho nahe bei 1 wird delta_k vergrößert, sonst verkleinert.
• Die Lösung des restringierten linearen Ausgleichsmodells führt schliesslich auf ein Gleichungssystem
  2(A^TA+lambda*D_k)d_k = -grad(||F(x)||²)
  mit A = J_F(xk) und x=x_k. Dabei hängt lambda von delta_k ab. lambda = 0 ergibt das Gauss-Newton-Verfahren. Durch diese Steuerung wird auch die Behandlung einer rangdefizienten Jacobimatrix möglich, die Konvergenz ist aber für lambda ungleich null immer sehr langsam.
• Hier wird die Implementierung von Jorge J. More verwendet.

Die Eingaben

• Einzugeben ist die Anzahl n der Koeffizienten der Funktion f. (also dim(x).) Wichtig : 1 <= n <= 10 !
• Die Anzahl m der Datenpunkte. Wichtig : 1 <= m <=100 und n <= m !
• Die Datenpunkte (m Einträge der Form t(i),y(i), wobei mindestens n der t(i) verschieden sein müssen.)
• Der Shift, um den t(i) transformiert werden soll. tti = t(i) - shift. Achtung: Die Funktion hängt von tti und nicht von t(i) ab. Shift=0 muss angegeben werden.
• Die Funktion f. Hierbei muß darauf geachtet werden, daß die Funktion von den Koeffizienten x(k), k=1,...,n, und von der transformierten Variablen tti = t(i) - shift abhängt. Es ist also die Formel von f(tti,x(1),...,x(n)) einzugeben.
• Desweiteren die Startwerte der x(k), k=1,...,n.
• Sie können entweder Standardabbruchkriterien wählen oder eigene Kriterien angeben. Letzteres bedeutet dann noch die Angabe von Abbruchtoleranzen bezüglich x, dem Residuum und der Änderung in der Fehlerquadratsumme.

Die Ausgaben

• Ausgegeben wird eine Graphik, welche den dekadischen Logarithmus von ||F(x_k)||-||F_min|| darstellt. Hierbei bedeutet der Wert -99 "null".
• Eine Graphik mit dem dekadischen Logarithmus des maximalen Winkels zwischen Residuum und Spalten der Jacobimatrix. (-20 bedeutet "null".) Dies ist der sogenannte skalierte Gradient. Außerdem ist noch der dekadische Logarithmus von delta_k dargestellt.
• Und eine dritte Graphik zeigt die dekadischen Logarithmen von rho und lambda. Auch hier bedeutet -20 "null" bzw. -unendlich.

Das Eingabeformular

Zurück: Unrestringierte Minimierung