牛顿法(Newton Method)求解f(x)=0

今天继续探讨$f(x)=0$的解法，这次要介绍的是牛顿迭代法。

【问题描述】

已知$f(x)=0$，求使等式成立的$x$的值。

【解法如下】

求出$f(x)$的导函数$f\_d(x)=f'(x)$

任取初值$x_0$进行迭代

$x_1=x_0-f(x_0)/f'(x_0)$

$x_2=x_1-f(x_1)/f'(x_1)$

$x_3=x_2-f(x_2)/f'(x_2)$

...

$x_n=x_{n-1}-f(x_{n-1})/f'(x_{n-1})$

直到 $f(x_n)≈0$ (此处约等于的意思是两者的差值小于预设误差)

【示例】

求解 $f(x)=e^{-x}-x=0$

根据求导公式有 $f\_d(x)=f'(x)=-e^{-x}-1$

求解代码如下

#include <math.h>
#include <stdio.h>

double f(double x)
{
    return exp(-x)-x;
}

double f_d(double x)
{
    return -exp(-x)-1;
}

int main()
{
    double x = 0;
    while (f(x) > 1e-6) {
        x = x-f(x)/f_d(x);
    }
    printf("solution for function exp(-x)-x=0 is %lf\n", x);
    return 0;
}

求解结果如下：

牛顿迭代法求解结果

【原理】

我也不懂了……详细的可以参考维基百科

https://en.wikipedia.org/wiki/Newton%27s_method

这里仅解释下浅显的理解，而且对收敛性也不做证明。

根据高等数学里面学到的泰勒展开

约掉二阶及二阶以上的小量（至于详细的证明需要参照维基百科了，因为这里任取的初值实际上不一定是小量，这里仅仅是做一个简单解释），得到

故而可以推出，当 $f(x)=0$ 时

此即为牛顿迭代法中得迭代公式。