牛顿迭代法

牛顿迭代法用于求函数的零点。

问题

考虑求一个函数的一个零点。
如果函数是一次函数$f\left(x\right)=kx+b$，则显然有零点$(-\frac{b}{k},0)$。

如果函数是二次函数呢？好像也不难，用求根公式即可。

现在问题来了：人类已经证明，五次以上的方程没有求根公式。如果拿到的方程极为奇怪，又该如何处理？

牛顿迭代法提出了解决方案。

方法

牛顿迭代法分三步进行： 1. 瞎猜一个值$p$
2. 求出$x=p$时函数的切线，即求$f\prime \left(p\right)$
3. 令$p$为切线的零点，返回步骤2。

以维基百科的图理解： 

上图中蓝线是原函数，红线是切线。

上面的三个步骤可以简化为一个递推：$x_{n+1}=x_n-\frac{f\left(x_n\right)}{f^{\prime }\left(x_n\right)}$

用途

正常向的用途，就是老老实实求零点。

但是还有一些东西可以用牛顿迭代做，例如求$\sqrt[m]{ma}$。
显然很难求，所以令$x=\sqrt[m]{ma}$，令$f\left(x\right)=x^m=a$。

显然$f\prime \left(x\right)=m\ast x^{m-1}$。然后就可以牛顿迭代出解了。

程序

例：求$f\left(x\right)=x^2+2x+1$的一个零点。

求导得：$f\prime \left(x\right)=2x+2$。
故可以：
$x=x-\frac{f\left(x\right)}{f_2\left(x\right)}$迭代lambda次。这里lambda取100。

#define f(x)   (x*x+2*x+1)     //原函数
#define f2(x)  (x*2+2)         //导函数
#define lambda (100)           //迭代次数

void Newton()
{
    double x=233;
    int i=0;

    for(i=0;i<lambda;i++)
        x=x-f(x)/f2(x);        //牛顿迭代法

    printf("%.8lf\n",x);
}

正确性

不会证

（能用就行？