Levenberg-Marquardt-Algorithmus
aus Wikipedia, der freien Enzyklopädie
Der Levenberg-Marquardt-Algorithmus, benannt nach Kenneth Levenberg und Donald Marquardt ist ein numerischer Optimierungsalgorithmus. Diese Lösungsstrategie 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.
Inhaltsverzeichnis |
[Bearbeiten] Beschreibung
Für die Funktion soll das Minimierungsproblem
ausgehend von einer Startnäherung x0 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.
Zusätzlich fordert man beim Levenberg-Marquardt-Algorithmus allerdings, dass .
Durch diese Zusatzbedingung kann man eine Verkleinerung von in jedem Schritt erzwingen. Dazu wird der Parameter rk entsprechend angepasst.
[Bearbeiten] Konvergenz
Das Levenberg-Marquardt-Verfahren geht lokal in das Newton-Verfahren über. Damit ist die Konvergenz lokal quadratisch.
[Bearbeiten] Anwendungsgebiete
Das Hauptanwendungsgebiet des Levenberg-Marquardt-Algorithmus liegt in der Lösung eines nichtlinearen Minimum-Quadrat-Problems.
[Bearbeiten] Literatur
- Levenberg, K. "A Method for the Solution of Certain Problems in Least Squares." Quart. Appl. Math. 2, 164-168, 1944.
- Marquardt, D. "An Algorithm for Least-Squares Estimation of Nonlinear Parameters." SIAM J. Appl. Math. 11, 431-441, 1963.
- P. Gill, W. Murray & M. Wright, "Practical Optimization", 1981
[Bearbeiten] Weblinks
Frei verfügbare Implementierungen des Levenberg-Marquardt-Algorithmus finden sich unter