牛顿法(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 条评论
登录 后参与评论

相关文章

来自专栏张俊红

python数据科学-单变量数据分析

总第85篇 01|背景: 我们在做机器学习之前,需要自己先对数据进行深入的了解(这些数据是什么类型,总共有多少数据,有没有缺失值,均值是多少之类的),只有自己对...

3805
来自专栏机器之心

NIPS 2018 | 程序翻译新突破:UC伯克利提出树到树的程序翻译神经网络

程序是构建计算机应用、IT 产业和数码世界的主要工具。为了方便程序员为不同的应用开发程序,人们发明了各种编程语言。与此同时,当程序员想要将用不同语言编写的程序组...

1071
来自专栏量子位

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

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

2333
来自专栏新智元

【ICLR 2016最佳论文】DeepMind 开发 NPI,有望取代初级程序员(附下载)

【新智元导读】特征学习和深度学习重要会议 ICLR 2016 最佳论文,DeepMind 团队开发了一个“神经编程解释器”(NPI),能自己学习并且编辑简单的程...

3166
来自专栏智能算法

数据分析小实验(上)

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

4738
来自专栏机器之心

教程 | 如何利用C++搭建个人专属的TensorFlow

30510
来自专栏磐创AI技术团队的专栏

【Github 4K星】BAT头条滴滴小米等笔试面经+深度学习/算法/NLP资源汇总!

最近,在GitHub上有位id为imhuay的热心人带头建立了一个关于国内知名互联网企业笔试和面试经验的资源库,光从名称上就能看出其内容有多丰富:《2018/2...

2373
来自专栏AI派

【Github 5K星】BAT头条滴滴小米等笔试面经+深度学习/算法/NLP资源汇总!

最近,在GitHub上有位id为imhuay的热心人带头建立了一个关于国内知名互联网企业笔试和面试经验的资源库,光从名称上就能看出其内容有多丰富:《2018/2...

1231
来自专栏和蔼的张星的图像处理专栏

暗通道去雾改进算法及实现

上次搞的暗通道去雾的算法交给老师就算是交差了,当时也就是个调研而已。前几天又被老师叫过去说还是需要720p(1280*720)图像的实时处理,看能不能再做一些优...

3532
来自专栏编程微刊

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

3504

扫码关注云+社区

领取腾讯云代金券