Per*_*eng 14 c algorithm curve-fitting opencl
我是一名程序员,想要了解Levenberg-Marquardt曲线拟合算法的工作原理,以便我自己实现它.在任何地方都有一个很好的教程可以解释它是如何工作的,读者是程序员而不是数学家.
我的目标是在opencl中实现这个算法,这样我就可以让它运行硬件加速.
小智 27
最小化函数就像试图找到曲面上的最低点.想想你自己走在丘陵的表面,你想要到达最低点.你会发现下坡的方向,直到它不再下坡.然后你会选择一个新的方向,下坡并向那个方向走,直到它不再下坡,等等.最终(希望)你会达到一个没有方向下坡的地步.那么你将处于(当地)最低限度.
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减少了多少来计算近似函数有多好.如果它们接近,则近似函数是好的,我们可以采取更大的步骤.如果它们没有接近那么近似函数就不好了,我们应该退回并采取较小的步骤.
but*_*ken 13
LM 算法的基本思想可以在几页中得到解释——但是对于快速和健壮的生产级实现，许多微妙的优化是必要的。最先进的技术仍然是莫雷等人的 Minpack 实现，由莫雷 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 代码更易于访问。