牛顿迭代法

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

问题

考虑求一个函数的一个零点。
如果函数是一次函数$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);
}

正确性

不会证

(能用就行?


CC0协议 @ ruanxingzhi 2017. CC0是啥玩意?
Home apps close