Comment le Levenberg–Marquardt algorithme de travailler dans le détail, mais d'une manière compréhensible?

Question

Je suis un programmeur qui veut apprendre comment la Levenberg–Marquardt curvefitting algorithme fonctionne pour que je puisse l'appliquer moi-même.Est-il un bon tutoriel n'importe où qui peut expliquer comment cela fonctionne dans le détail avec le lecteur étant un programmeur et pas un mathémagicien.

Mon objectif est de mettre en œuvre cet algorithme en opencl pour que je puisse l'exécuter en charge l'accélération matérielle.

Answer 1

• http://en.wikipedia.org/wiki/Levenberg-Marquardt_algorithm
• PDF Tutorial de Ananth Ranganathan
• JavaNumerics a une implémentation assez lisible
• L'ICS a C / C ++ application

Answer 2

Minimisation fonction est comme essayer de trouver point le plus bas sur une surface. Pensez-vous marcher sur une surface vallonnée et que vous essayez d'obtenir au point le plus bas. Vous trouverez la direction qui descend et marcher jusqu'à ce qu'il ne va pas plus en descente. Ensuite, vous a choisi une nouvelle direction qui descend et marche dans cette direction jusqu'à ce qu'il ne va pas plus en descente, et ainsi de suite. Par la suite (je l'espère) vous atteindre un point où aucune direction descend plus. Vous seriez alors au minimum (local).

L'algorithme LM, et bien d'autres algorithmes de minimisation, utilisez ce schéma.

Supposons que la fonction étant réduite au minimum est F, et nous sommes au point x (n) dans notre itération. Nous voulons trouver le prochain itérer x (n + 1) tel que F (x (n + 1))

En premier lieu, calculer une approximation linéaire de F au point x (n). Il est facile de trouver le sens de la descente d'une fonction linéaire, donc nous utilisons la fonction d'approximation linéaire pour déterminer la direction de descente. Ensuite, il faut savoir jusqu'où on peut aller dans cette direction choisie. Si notre approximation fonction linéaire est une bonne approximation F pour une grande surface autour de x (n), nous pouvons faire un pas assez grand. Si c'est une bonne approximation que très proche de x (n), alors nous pouvons prendre seulement une étape très faible.

est ce que LM fait - calcule une approximation linéaire F à x (n), donnant ainsi le sens de la descente, il figure sur la taille d'une étape à prendre en fonction de la façon dont la fonction linéaire se rapproche de F à x (n ). LM chiffres sur la qualité de la fonction d'approximation est en prenant essentiellement un pas dans la direction ainsi déterminée en comparant la quantité de l'approximation linéaire de F a diminué au combien la fonction réelle F diminuée. Si elles sont proches, la fonction approchante est bonne et nous pouvons prendre un peu plus grand pas. Si elles ne sont pas proches alors la fonction d'approximation est pas bon et nous devrions reculer et faire un pas plus petit.

Answer 3

Les idées de base de l'algorithme de LM peut être expliqué, en quelques pages, mais pour une production de qualité de la mise en œuvre est rapide et robuste, de nombreuses optimisations sont nécessaires.État de l'art est encore la Minpack mise en œuvre par Moré et coll., documentées en détail par la Moré 1978 (http://link.springer.com/content/pdf/10.1007/BFb0067700.pdf) et dans le Minpack guide de l'utilisateur (http://www.mcs.anl.gov/~plus/ANL8074b.pdf).Pour étudier le code, mon C (traductionhttps://jugit.fz-juelich.de/mlz/lmfit) est sans doute plus accessible que l'original du code Fortran.

Answer 4

Recettes numérique (Levenberg-Marquardt est à la section 15.5). Il est disponible en ligne, et je trouve qu'ils expliquent des algorithmes d'une manière qui est détaillée (ils ont le code source complet, comment pouvez-vous beaucoup plus détaillée se ...), encore accessible.

Answer 5

ces notes d'un parcours à l'Université de Purdue pour coder un algorithme d'ajustement de courbe de Levenberg-Marquardt générique dans MATLAB qui calcule les dérivés numériques et admet donc une fonction de la forme f(x;p) où p est un vecteur de paramètres d'ajustement.