Levenberg

在讲Levenberg-Marquardt算法之前我想先谈下牛顿法和高斯牛顿法。

如果有一点数值计算知识的同学对牛顿迭代法并不陌生，先贴个经典例图来镇楼。

一般来说我们利用牛顿法来求f(x)=0的解。求解方法如下： 先对f(x)一阶泰勒展开： f ( x 0 + Δ ) = f ( x 0 ) + f ′ ( x 0 ) Δ = 0 　 　 　 　 ( 1 ) f(x_0+\Delta)=f(x_0)+f'(x_0)\Delta=0　　　　(1) f(x0​+Δ)=f(x0​)+f′(x0​)Δ=0　　　　(1) 其中 Δ = x − x 0 \Delta=x-x_0 Δ=x−x0​, 所以我们有 Δ = x − x 0 = − f ( x 0 ) f ′ ( x 0 ) , 即 x = x 0 − f ( x 0 ) f ′ ( x 0 ) 　 　 　 　 ( 2 ) \Delta=x-x_0=-\frac{f(x_0)}{f'(x_0)},即x=x_0-\frac{f(x_0)}{f'(x_0)}　　　　(2) Δ=x−x0​=−f′(x0​)f(x0​)​,即x=x0​−f′(x0​)f(x0​)​　　　　(2)

由式(2)可知，当 Δ \Delta Δ 非常小时，我们可将 f ( x ) = 0 f(x)=0 f(x)=0 的解析解近似于 x 0 x_0 x0​。但是由上图可知 x 0 x_0 x0​ 是任意的初始值，所以可能会导致初始 Δ \Delta Δ 非常大，因此可采用牛顿迭代公式逐步逼近解析解： x n = x n − 1 − f ( x n − 1 ) f ′ ( x n − 1 ) ,   u n t i l    ∣ x n − x n − 1 ∣ < ϵ 　 　 　 　 ( 3 ) x_n=x_{n-1}-\frac{f(x_{n-1})}{f'(x_{n-1})} ,\ until\ \ |x_n-x_{n-1}|< \epsilon　　　　(3) xn​=xn−1​−f′(xn−1​)f(xn−1​)​, until  ∣xn​−xn−1​∣