Steven_MengのBlog

牛顿迭代法

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

问题

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

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

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

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

方法

牛顿迭代法分三步进行:

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

维基百科的图理解:
牛顿迭代

上图中蓝线是原函数,红线是切线

上面的三个步骤可以简化为一个递推:$\displaystyle x_{n+1}=x_{n}-\frac {f(\dfrac{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-\dfrac{f(x)}{f_2(x)}$迭代lambda次。这里lambda取100。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#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);
}

正确性

不会证

(能用就行?

 评论