Levenberg-Marquardt算法如何以一种可理解的方式详细工作?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (66)

我是一名程序员,想要了解Levenberg-Marquardt曲线拟合算法的工作原理,以便我自己实现它。在任何地方都有一个很好的教程可以解释它是如何工作的,读者是程序员而不是数学家。

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

提问于
用户回答回答于

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

用户回答回答于

最小化函数就像试图找到曲面上的最低点。想想你自己走在丘陵的表面,你想要到达最低点。你会发现下坡的方向,直到它不再下坡。然后你会选择一个新的方向,下坡并向那个方向走,直到它不再下坡,等等。最终(希望)你会达到一个没有方向下坡的地步。那么你将处于(当地)最低限度。

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减少了多少来计算出近似函数有多好。如果它们接近,则近似函数是好的,我们可以采取更大的步骤。如果它们没有接近那么近似函数就不好了,我们应该退回并采取较小的步骤。

扫码关注云+社区

领取腾讯云代金券