15

我是一名程序员，想了解 Levenberg-Marquardt 曲线拟合算法的工作原理，以便我自己实现它。是否有一个很好的教程可以解释它如何与作为程序员而不是数学家的读者一起详细解释它的工作原理。

我的目标是在 opencl 中实现这个算法，这样我就可以让它运行硬件加速。

4

5 回答 5

28

最小化一个函数就像试图找到一个表面上的最低点。想象你自己走在一个丘陵表面，你正试图到达最低点。你会找到下坡的方向，然后一直走，直到它不再下坡。然后你会选择一个新的下坡方向，然后沿着那个方向走，直到它不再下坡，依此类推。最终（希望）你会到达一个不再有方向走下坡的地步。然后，您将处于（本地）最低限度。

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 降低的程度来计算近似函数的好坏程度。如果它们接近，则近似函数很好，我们可以采取更大的步骤。如果它们不接近，则近似函数不好，我们应该退后一步并采取更小的步骤。

于 2009-10-30T19:27:03.327 回答
13
于 2009-07-16T09:39:21.150 回答
5

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 代码更易于访问。

于 2013-08-01T09:31:32.713 回答
3

尝试数字配方（Levenberg-Marquardt 在第 15.5 节中）。它可以在线获得，我发现他们以一种详细的方式解释算法（他们有完整的源代码，你能得到多少详细信息......），但可以访问。

于 2009-07-16T09:38:56.737 回答
1

我使用普渡大学课程中的这些笔记在 MATLAB 中编写了一个通用的 Levenberg-Marquardt 曲线拟合算法，该算法计算数值导数，因此接受任何形式的函数，f(x;p)其中p是拟合参数的向量。

于 2009-10-30T22:20:15.550 回答