牛顿法(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)=f(x_0)+(x-x_0)f'(x_0) +\frac{(x-x_0)^2}{2}f''(x_0)+\frac{(x-x_0)^3}{3!}f^{(3)}(x_0)+\frac{(x-x_0)^4}{4!}f^{(4)}(x_0)+...+\frac{(x-x_0)^n}{n!}f^{(n)}(x_0)

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

f(x)≈f(x_0)+(x-x_0)f'(x_0)

故而可以推出,当 f(x)=0

x≈x_0-\frac{f(x_0)}{f'(x_0)}

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

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏生信技能树

R语言的各种统计分布函数

http://www.bio-info-trainee.com/1656.html

2303
来自专栏企鹅号快讯

仅需15分钟,使用OpenCV+Keras轻松破解验证码

选自Medium 作者:Adam Geitgey 参与:李泽南、蒋思源 登录网站时必须输入的图片验证码可以用来识别访问者到底是人还是机器——这同时也是某种程度上...

36911
来自专栏iOSDevLog

《 Julia 数据科学应用》各章思考题答案

1.如果你以前没有用过 Julia,那么 Juno 是最安全的选择。如果不使用 Juno,那么带有最新 Julia 内核(在 IJulia 界面右上方)的 IJ...

814
来自专栏人工智能LeadAI

TensorFlow应用实战-17-Qlearning实现迷宫小游戏

总共有12个状态,s1到s12.对于每一个状态会有四个动作。对于每个状态下的每个动作会有一个Q的值。

2681
来自专栏编程微刊

人工智能面试题86问,新手找工作必备!

2734
来自专栏智能算法

数据分析小实验(上)

目录 一、数据准备 二、缺失值处理 三、清洗数据 四、聚类分析 五、结果评估与分析 一、数据准备 本次实验,是通过实验方...

4128
来自专栏量子位

亚马逊发布新版MXNet:支持英伟达Volta和稀疏张量

安妮 编译自 AWS官博 量子位 出品 | 公众号 QbitAI Apache MXNet v0.12来了。 今天凌晨,亚马逊宣布了MXNet新版本,在这个版本...

3816
来自专栏牛客网

腾讯应用研究一面 武汉

腾讯应用研究武汉现场一面 一共20分钟。 (比我内推的三轮面试都缺少一点技术含量,内推面试会问我项目,跟我有交流或者提建议,这次就感觉随便找点东西问问,然后最后...

46716
来自专栏量子位

有笔记本就能玩的体感游戏!TensorFlow.js实现体感格斗教程

小时候的你在游戏中搓着手柄,在现实中是否也会模仿这《拳皇》的动作?用身体控制游戏角色的体感游戏很早就已出现,但需要体感手柄(Wii)或体感摄像头(微软Kinec...

1673
来自专栏人工智能LeadAI

文本数据处理的终极指南-[NLP入门]

简介 实现任何程度或者级别的人工智能所必需的最大突破之一就是拥有可以处理文本数据的机器。值得庆幸的是,全世界文本数据的数量在最近几年已经实现指数级增长。这也迫切...

4046

扫码关注云+社区