www.wikidata.de-de.nina.az

Levenberg Marquardt Algorithmus Der benannt nach Kenneth Levenberg und Donald Marquardt ist ein numerischer Optimierungs

Levenberg-Marquardt-Algorithmus

Der Levenberg-Marquardt-Algorithmus, benannt nach Kenneth Levenberg und Donald Marquardt, ist ein numerischer Optimierungsalgorithmus zur Lösung nichtlinearer Ausgleichs-Probleme mit Hilfe der Methode der kleinsten Quadrate. Das Verfahren kombiniert das Gauß-Newton-Verfahren mit einer Regularisierungstechnik, die absteigende Funktionswerte erzwingt.

Der Levenberg-Marquardt-Algorithmus ist deutlich robuster als das Gauß-Newton-Verfahren, das heißt, er konvergiert mit einer hohen Wahrscheinlichkeit auch bei schlechten Startbedingungen, allerdings ist auch hier Konvergenz nicht garantiert. Ferner ist er bei Anfangswerten, die nahe dem Minimum liegen, oft etwas langsamer.

Beschreibung Bearbeiten

Für die nichtlineare Funktion soll das Kleinste-Quadrate-Minimierungsproblem (mit einer kleineren Anzahl von unabhängigen Variablen gegenüber der Zahl der Funktionskomponenten)

ausgehend von einer Startnäherung gelöst werden.

Wie beim Gauß-Newton-Verfahren wird F(x) in jedem Schritt durch eine Linearisierung ersetzt und das Ersatzproblem:

betrachtet. Dabei ist J die Jacobi-Matrix der Funktion F.

Der Standard Gauß-Newton-Schritt berechnet den neuen Punkt als Lösung eines linearen Gleichungssystems mit der Koeffizientenmatrix . Wenn diese Matrix schlecht konditioniert oder singulär ist, kann der Algorithmus nur einen suboptimalen (d. h. die Zielfunktion wird nicht verbessert) bzw. gar keinen Schritt machen. Besonders bei schlecht konditionierten und "fast singulären" Matrizen ergeben sich zudem erhebliche numerische Schwierigkeiten. Der Levenberg-Marquardt-Algorithmus umgeht diese Probleme, indem er die Koeffizientenmatrix des linearen Gleichungssystems auf die Form erweitert, wobei eine Diagonalmatrix ist die sicherstellt, dass der gesamte Term positiv definit ist.

Der vollständige Levenberg-Marquardt-Iterationsschritt lautet

wobei eine Schrittweite ist.

Eine weit verbreitete Form für die Diagonalmatrix ist , mit und der Einheitsmatrix. Diese Form wurde auch in den originalen Artikeln von Levenberg und Marquardt vorgeschlagen. Für den Fall reduziert sich der Levenberg-Marquardt Iterationsschritt zum Gauß-Newton Schritt. Im Fall dominiert hingegen die Einheitsmatrix gegenüber dem Term , und der Levenberg-Marquardt-Iterationsschritt reduziert sich zu einem Gradientenschritt. Mit der Wahl von kann somit stufenlos zwischen Gradientenschritt und Gauß-Newton Schritt gewählt werden.

Eine alternative Sichtweise ergibt sich aus der Beobachtung, dass das linearisierte Ersatzproblem nur in einer kleinen Umgebung des Linearisierungspunkts eine gute Annäherung an das Originalproblem darstellt. Eine unrestringierte Minimierung macht jedoch unter Umständen sehr große Schritte, die diese kleine Umgebung verlassen. Aus diesem Grund ersetzt man die unrestringierte Optimierung durch die restringierte Optimierung mit , d. h. man beschränkt die Optimierung auf eine kleine Nachbarschaft um den Linearisierungspunkt. Aus diesem Grund werden Methoden dieser Art häufig Trust-Region-Verfahren genannt. Man kann zeigen, dass die restringierte Optimierung genau auf die Form für die Koeffizientenmatrix des linearen Gleichungssystems führt.

Konvergenz Bearbeiten

Das Levenberg-Marquardt-Verfahren geht lokal in das Gauß-Newton-Verfahren über. Damit ist die Konvergenz lokal linear und nahe dem Optimum sogar quadratisch.

Literatur Bearbeiten

  • K. Levenberg: A Method for the Solution of Certain Problems in Least Squares, Quart. Appl. Math. 2, 164-168, 1944.
  • D. Marquardt: An Algorithm for Least-Squares Estimation of Nonlinear Parameters, SIAM J. Appl. Math. 11, 431-441, 1963.
  • Jorge J. Moré: The Levenberg-Marquardt algorithm: Implementation and theory. In G. A. Watson (ed.): Numerical Analysis. Dundee 1977, Lecture Notes Math. 630, 1978, S. 105–116
  • P. Gill, W. Murray und M. Wright: Practical Optimization, Academic Press 1981
  • J. E. Dennis, Jr., und R. B. Schnabel: Numerical methods for unconstrained optimization and nonlinear equations. Prentice-Hall Series in Computational Mathematics, Englewood Cliffs 1983

Weblinks Bearbeiten

Frei verfügbare Implementierungen des Levenberg-Marquardt-Algorithmus:

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Der Levenberg Marquardt Algorithmus benannt nach Kenneth Levenberg und Donald Marquardt ist ein numerischer Optimierungsalgorithmus zur Losung nichtlinearer Ausgleichs Probleme mit Hilfe der Methode der kleinsten Quadrate Das Verfahren kombiniert das Gauss Newton Verfahren mit einer Regularisierungstechnik die absteigende Funktionswerte erzwingt Der Levenberg Marquardt Algorithmus ist deutlich robuster als das Gauss Newton Verfahren das heisst er konvergiert mit einer hohen Wahrscheinlichkeit auch bei schlechten Startbedingungen allerdings ist auch hier Konvergenz nicht garantiert Ferner ist er bei Anfangswerten die nahe dem Minimum liegen oft etwas langsamer Inhaltsverzeichnis 1 Beschreibung 2 Konvergenz 3 Literatur 4 WeblinksBeschreibung BearbeitenFur die nichtlineare Funktion F R m R n m lt n displaystyle F mathbb R m to mathbb R n m lt n nbsp soll das Kleinste Quadrate Minimierungsproblem mit einer kleineren Anzahl von unabhangigen Variablen gegenuber der Zahl der Funktionskomponenten min x R m F x 2 2 displaystyle min x in mathbb R m F x 2 2 nbsp ausgehend von einer Startnaherung x 0 displaystyle x 0 nbsp gelost werden Wie beim Gauss Newton Verfahren wird F x in jedem Schritt durch eine Linearisierung ersetzt und das Ersatzproblem min x R m F x k J x k x x k 2 2 displaystyle min x in mathbb R m F x k J x k x x k 2 2 nbsp betrachtet Dabei ist J die Jacobi Matrix der Funktion F Der Standard Gauss Newton Schritt berechnet den neuen Punkt x k 1 displaystyle x k 1 nbsp als Losung eines linearen Gleichungssystems mit der Koeffizientenmatrix J T J displaystyle J T J nbsp Wenn diese Matrix schlecht konditioniert oder singular ist kann der Algorithmus nur einen suboptimalen d h die Zielfunktion wird nicht verbessert bzw gar keinen Schritt machen Besonders bei schlecht konditionierten und fast singularen Matrizen ergeben sich zudem erhebliche numerische Schwierigkeiten Der Levenberg Marquardt Algorithmus umgeht diese Probleme indem er die Koeffizientenmatrix des linearen Gleichungssystems auf die Form J T J D displaystyle J T J Delta nbsp erweitert wobei D displaystyle Delta nbsp eine Diagonalmatrix ist die sicherstellt dass der gesamte Term positiv definit ist Der vollstandige Levenberg Marquardt Iterationsschritt lautet x k 1 x k a k J x k T J x k D k 1 J x k T F x k displaystyle x k 1 x k alpha k left J x k T J x k Delta k right 1 J x k T F x k nbsp wobei a k gt 0 displaystyle alpha k gt 0 nbsp eine Schrittweite ist Eine weit verbreitete Form fur die Diagonalmatrix ist D k b k I displaystyle Delta k beta k I nbsp mit b k 0 displaystyle beta k geq 0 nbsp und I displaystyle I nbsp der Einheitsmatrix Diese Form wurde auch in den originalen Artikeln von Levenberg und Marquardt vorgeschlagen Fur den Fall b k 0 displaystyle beta k 0 nbsp reduziert sich der Levenberg Marquardt Iterationsschritt zum Gauss Newton Schritt Im Fall b k 0 displaystyle beta k gg 0 nbsp dominiert hingegen die Einheitsmatrix gegenuber dem Term J T J displaystyle J T J nbsp und der Levenberg Marquardt Iterationsschritt reduziert sich zu einem Gradientenschritt Mit der Wahl von b k displaystyle beta k nbsp kann somit stufenlos zwischen Gradientenschritt und Gauss Newton Schritt gewahlt werden Eine alternative Sichtweise ergibt sich aus der Beobachtung dass das linearisierte Ersatzproblem min x R m F x k J x k x x k 2 2 displaystyle min x in mathbb R m F x k J x k x x k 2 2 nbsp nur in einer kleinen Umgebung des Linearisierungspunkts eine gute Annaherung an das Originalproblem darstellt Eine unrestringierte Minimierung macht jedoch unter Umstanden sehr grosse Schritte die diese kleine Umgebung verlassen Aus diesem Grund ersetzt man die unrestringierte Optimierung durch die restringierte Optimierung min x x k lt r k F x k J x k x x k 2 2 displaystyle min x x k lt r k F x k J x k x x k 2 2 nbsp mit r k gt 0 displaystyle r k gt 0 nbsp d h man beschrankt die Optimierung auf eine kleine Nachbarschaft um den Linearisierungspunkt Aus diesem Grund werden Methoden dieser Art haufig Trust Region Verfahren genannt Man kann zeigen dass die restringierte Optimierung genau auf die Form J T J b k I displaystyle J T J beta k I nbsp fur die Koeffizientenmatrix des linearen Gleichungssystems fuhrt Konvergenz BearbeitenDas Levenberg Marquardt Verfahren geht lokal in das Gauss Newton Verfahren uber Damit ist die Konvergenz lokal linear und nahe dem Optimum sogar quadratisch Literatur BearbeitenK Levenberg A Method for the Solution of Certain Problems in Least Squares Quart Appl Math 2 164 168 1944 D Marquardt An Algorithm for Least Squares Estimation of Nonlinear Parameters SIAM J Appl Math 11 431 441 1963 Jorge J More The Levenberg Marquardt algorithm Implementation and theory In G A Watson ed Numerical Analysis Dundee 1977 Lecture Notes Math 630 1978 S 105 116 P Gill W Murray und M Wright Practical Optimization Academic Press 1981 J E Dennis Jr und R B Schnabel Numerical methods for unconstrained optimization and nonlinear equations Prentice Hall Series in Computational Mathematics Englewood Cliffs 1983Weblinks BearbeitenFrei verfugbare Implementierungen des Levenberg Marquardt Algorithmus gnuplot freies Grafikprogramm lmdif in Fortran klassische Implementierung aus Netlib Minpack Lizenz Public Domain lmfit an Netlib Minpack lmfid angelehnte in sich geschlossene C Bibliothek fur allgemeine Minimierung und fur Kurvenanpassung nach der Methode der kleinsten Quadrate FreeBSD Lizenz levmar in C C mit Schnittstellen fur Matlab Perl und Python Lizenz GPL mpfit Implementierung in IDL csmpfit C Portierung von mpfit minpack lm Implementierung in R Abgerufen von https de wikipedia org w index php title Levenberg Marquardt Algorithmus amp oldid 231455267