牛顿拉夫逊法(Newton-Raphson Method)
| 分类： computerVision |
牛顿迭代法（Newton's method）又称为牛顿-拉夫逊（拉弗森）方法（Newton-Raphson method），它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法。多数方程不存在求根公式，因此求精确根非常困难，甚至不可能，从而寻找方程的近似根就显得特别重要。方法使用函数f(x）的泰勒级数的前面几项来寻找方程f(x) = 0的根。牛顿迭代法是求方程根的重要方法之一，其最大优点是在方程f(x) = 0的单根附近具有平方收敛，而且该法还可以用来求方程的重根、复根，此时线性收敛，但是可通过一些方法变成超线性收敛。另外该方法广泛用于计算机编程中。
其核心思想是沿着导数方向连续性的逼近一个实函数的根值。
http://blog.****.net/lttclaw_/article/details/37316663
二分法基本思想就是在每次将解的可能范围减半，如猜价格游戏就可以很好体现这点。一个物品价格在0到10000间，猜中点然后根据反馈是高了还是低了将猜测范围减半，这样下来，必然能不断趋近于正确结果。
牛顿-拉夫逊法为数学上求近似解的方法，也称牛顿法，切线法，是给一个初始值，这个初始值对应函数的切线与x轴交点为下一个跟接近解的值，依次继续，直到误差小到要求的程度
其实这个方法还是很简单的，比如求解一个非线性方程的根： f(x) = 0。
假设r是这个方程的根，那么:
f(r) = 0
牛顿法的思路就是找到一个离r非常近的x，但是因为r实际上是不知道的，因此也没有办法一开始就可以设置一个很接近于r的x，因此先随机设定一个x0,=》 r = x0 + h，使用taylor展开，下面就是找到一个足够小的h和xn满足上面这个公式，如果h足够小了，那么说明xn就是非常接近r了。
如果f'(xn)=0,那么就表示h就是足够小。
使用上面的方法反复的进行迭代逼近，可以得到一个收敛的解。
求方程f (x ) = cos(x ) − x 3 的根。两边求导，得f '(x ) = −sin(x ) − 3x 2 。由于cos(x ) ≤ 1（对于所有x ），以及x 3 > 1（对于x >1），可知方程的根位于0和1之间。我们从x 0 = 0.5开始。
- 泰勒公式的推导：
公式推导
我们知道，根据拉格朗日中值定理导出的有限增量定理有：
于是：
其中误差α是在Δx→0即x→x0的前提下才趋向于0，所以在近似计算中往往不够精确。于是我们需要一个能够足够精确的且能估计出误差的多项式：
来近似地表示函数f(x）且要写出其误差f(x)-P(x）的具体表达式。设函数P(x)满足 ：
于是可以依次求出A0、A1、A2、……、An，显然有：
至此，多项的各项系数都已求出，得：
以上就是函数 
的泰勒展开式。
接下来就要求误差的具体表达式了。设 
，令 
得到：
进而：
根据柯西中值定理：
其中θ1在x和x0之间；
继续使用柯西中值定理得到：
其中θ2在θ1和x0之间；
连续使用n+1次后得到：
其中θ在x和x0之间；
同时：
而： 
进而：
综上可得：
麦克劳林展开
函数的麦克劳林展开指上面泰勒公式中x0取0的情况，即是泰勒公式的特殊形式，若f(x)在x=0处n阶连续可导，则下式成立：
其中 
表示f(x)的n阶导数。
当 
，其中δ在0与x之间时，公式称为拉格朗日型余项的n阶麦克劳林公式；
当 
时公式称为带佩亚诺型余项的n阶麦克劳林公式