Levenberg–Marquardt 算法如何以一种易于理解的方式详细地工作？
我是一名程序员，想要了解 Levenberg-Marquardt 曲线拟合算法的工作原理，以便我可以自己实现它。 有没有一个好的教程可以向作为程序员而不是数学魔术师的读者详细解释它是如何工作的。
我的目标是在 opencl 中实现这个算法，这样我就可以让它运行硬件加速。
Im a programmer that wants to learn how the Levenberg–Marquardt curvefitting algorithm works so that i can implement it myself. Is there a good tutorial anywhere that can explain how it works in detail with the reader beeing a programmer and not a mathemagician.
My goal is to implement this algorithm in opencl so that i can have it run hardware accelerated.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
最小化函数就像试图找到表面上的最低点。 想象一下你自己走在丘陵表面上，并且你正试图到达最低点。 你会找到下坡的方向，一直走，直到不再下坡为止。 然后你会选择一个下坡的新方向，并朝那个方向走，直到不再下坡，依此类推。 最终（希望）你会到达一个不再有下坡方向的点。 然后您将处于（本地）最小值。
LM 算法和许多其他最小化算法都使用这种方案。
假设被最小化的函数是 F，并且我们在迭代中处于点 x(n)。 我们希望找到下一个迭代 x(n+1) 使得 F(x(n+1)) < F(x(n))，即函数值较小。 为了选择 x(n+1)，我们需要两个东西，一个来自 x(n) 的方向和一个步长（沿该方向走多远）。 LM 算法按如下方式确定这些值 -
首先，计算点 x(n) 处 F 的线性近似值。 线性函数很容易找出下坡方向，因此我们使用线性逼近函数来确定下坡方向。
接下来，我们需要知道在这个选定的方向上我们能走多远。 如果我们的近似线性函数对于 x(n) 周围的大区域来说是 F 的良好近似，那么我们可以采取相当大的步长。 如果它是一个非常接近 x(n) 的良好近似值，那么我们只能采取非常小的一步。
这就是 LM 所做的 - 计算 x(n) 处 F 的线性近似值，从而给出下坡方向，然后根据线性函数在 x(n) 处逼近 F 的程度计算出要采取多大的步长。 LM 基本上通过在确定的方向上迈出一步并比较 F 的线性近似值减少了多少与实际函数 F 减少了多少来计算逼近函数的好坏。 如果它们很接近，则近似函数很好，我们可以采取更大的步长。 如果它们不接近，则近似函数不好，我们应该后退并采取更小的步长。
Minimizing a function is like trying to find lowest point on a surface. Think of yourself walking on a hilly surface and that you are trying to get to the lowest point. You would find the direction that goes downhill and walk until it doesn't go downhill anymore. Then you would chose a new direction that goes downhill and walk in that direction until it doesn't go downhill anymore, and so on. Eventually (hopefully) you would reach a point where no direction goes downhill anymore. You would then be at a (local) minimum.
The LM algorithm, and many other minimization algorithms, use this scheme.
Suppose that the function being minimized is F and we are at the point x(n) in our iteration. We wish to find the next iterate x(n+1) such that F(x(n+1)) < F(x(n)), i.e. the function value is smaller. In order to chose x(n+1) we need two things, a direction from x(n) and a step size (how far to go in that direction). The LM algorithm determines these values as follows -
First, compute a linear approximation to F at the point x(n). It is easy to find out the downhill direction of a linear function, so we use the linear approximating function to determine the downhill direction.
Next, we need to know how far we can go in this chosen direction. If our approximating linear function is a good approximation for F for a large area around x(n), then we can take a fairly large step. If it's a good approximation only very close to x(n), then we can take only a very small step.
This is what LM does - calculates a linear approximation to F at x(n), thus giving the downhill direction, then it figures out how big a step to take based on how well the linear function approximates F at x(n). LM figures out how good the approximating function is by basically taking a step in the direction thus determined and comparing how much the linear approximation to F decreased to the how much the the actual function F decreased. If they are close, the approximating function is good and we can take a little larger step. If they are not close then the approximation function is not good and we should back off and take a smaller step.
LM 算法的基本思想可以在几页内解释 - 但对于快速且稳健的生产级实现，许多微妙的优化是必要的。 最先进的仍然是 Moré 等人的 Minpack 实现，Moré 1978 详细记录了 (http://link.springer.com/content/pdf/10.1007/BFb0067700.pdf）和 Minpack 用户指南（http://www.mcs.anl.gov/~more/ANL8074b.pdf）。 为了研究代码，我的 C 翻译 (https://jugit.fz-juelich.de/mlz /lmfit）可能比原始 Fortran 代码更容易访问。
The basic ideas of the LM algorithm can be explained in a few pages - but for a production-grade implementation that is fast and robust, many subtle optimizations are necessary. State of the art is still the Minpack implementation by Moré et al., documented in detail by Moré 1978 (http://link.springer.com/content/pdf/10.1007/BFb0067700.pdf) and in the Minpack user guide (http://www.mcs.anl.gov/~more/ANL8074b.pdf). To study the code, my C translation (https://jugit.fz-juelich.de/mlz/lmfit) is probably more accessible than the original Fortran code.
尝试数字食谱（Levenberg-Marquardt 位于第 15.5 节）。 它可以在网上找到，我发现他们以一种详细的方式解释算法（他们有完整的源代码，你能得到多少详细信息......），但又易于理解。
Try Numerical Recipes (Levenberg-Marquardt is in Section 15.5). It's available online, and I find that they explain algorithms in a way that's detailed (they have complete source code, how much more detailed can you get...), yet accessible.
我使用了课程中的这些笔记普渡大学 在 MATLAB 中编写通用的 Levenberg-Marquardt 曲线拟合算法，该算法计算数值导数，因此接受
f(x;p)形式的任何函数，其中p是拟合参数的向量。I used these notes from a course at Purdue University to code up a generic Levenberg-Marquardt curve-fitting algorithm in MATLAB that computes numerical derivatives and therefore accepts any function of the form
f(x;p)wherepis a vector of fitting parameters.