牛顿法(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 时

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