Steven_Meng's Blog

#牛顿迭代法

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

问题

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

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

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

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

方法

牛顿迭代法分三步进行：

1. 瞎猜一个值$p$
2. 求出$x=p$时函数的切线，即求$f\prime(p)$
3. 令$p$为切线的零点，返回步骤2。

以维基百科的图理解：

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

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

用途

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

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

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

程序

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

求导得：$f\prime(x)=2x+2$。
故可以：
$x=x-\frac{f(x)}{f_2(x)}$迭代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);
}

正确性

不会证

（能用就行？