固定点迭代法(Fixed Point Iteration)求解f(x)=0

求解f(x)=0还是很有用的,具体应用此不做讨论。这里将使用一系列专题阐述求解f(x)=0的各种方法。此次先讨论固定点迭代法(Fixed Point Iteration)。

下面先直接给出解法,后面再对原理进行阐述。

问题描述

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

解法如下

f(x)=0转换为同解方程g(x)=x

任取初值x_0,进行迭代

x_1=g(x_0)

x_2=g(x_1)

x_3=g(x_2)

...

x_n=g(x_{n-1})

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

示例

求解 f(x)=x^2-x-2=0

转换为

f(x)=x^2-x-2=0 ⇒ x^2=x+2 ⇒ x=\sqrt{x+2}

故可令 g(x)=\sqrt{x+2}

求解代码如下

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

double g(double x)
{
    return sqrt(x+2);
}

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

可以看到在误差范围内,此值与实际的解x=2非常接近

求解求解结果结果输出输出

原理

可以看到实际上,从f(x)=0转换为 g(x)=x 是有多种转换方式的。例如示例中的的 f(x)=x^2-x-2 也可以转换为 g(x)=x^2-2。但是,读者可以试一下,实际上如果使用 g(x)=x^2-2 是解不出来的,因为结果会发散。而详细的证明,可以得到必须 |f'(x)|<1,迭代结果才不会发散,其中x为真实解。

而实际上,这个解法看似简单,要证明却是非常复杂呢(简单的说就是笔者也不知道如何证明,手动哭)。

但是形而上的证明,读者可以参见此文 https://www3.nd.edu/~zxu2/acms40390F12/Lec-2.2.pdf

结语

对于固定点迭代法,笔者可以说是又爱又恨,爱在它非常容易记忆。恨在此法实际上用处不大,可以看到要使用此法,必须|f'(x)|<1,其中x为真实解,可是事先并不知道真实解(如果知道就不需要求了)。此方法更多的作用在于解释我们要做的事情(求解f(x)=0)。后续文章会继续介绍其他解法。

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

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

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏GIS讲堂

sde用sql实现erase

用原始数据data1和合并计算后的结果进行差异计算,所得的结果即为另一部分所要结果。

973
来自专栏企鹅号快讯

受限玻尔兹曼机

关注AI君,领略人工智能之美 受限玻尔兹曼机 Restricted Bolltzmann Machine 概述 各位读者,新年好! 在《技术词条》系列文章的上一...

3149
来自专栏AI研习社

手把手教你用 PyTorch 辨别自然语言(附代码)

最近在学pyTorch的实际应用例子。这次说个简单的例子:给定一句话,判断是什么语言。这个例子是比如给定一句话: Give it to me 判断是 ENGLI...

3655
来自专栏cs

NLP问题之word2vec

其用于有如下的 从「中文分词」、「词云画像」、「词性分析」到「自动摘要」、「关系挖掘」、「情感分析」、「知识图谱」等

2302
来自专栏灯塔大数据

每周学点大数据 | No.11亚线性算法

No.11期 亚线性算法 Mr. 王:从今天开始,我们正式讲解大数据算法的内容。首先谈谈关于亚线性算法的问题。 小可:我记得前面提到过亚线性算法,就是复杂度低...

3895
来自专栏小小挖掘机

算法面试太难?反手就是一波面经

八月参加了一些提前批的面试,包括阿里、百度、头条、贝壳、一点资讯等。整理了一些面试题,分享给大家。

2953
来自专栏计算机视觉战队

简单易懂的讲解深度学习(入门系列之五)

我们知道,《三字经》里开篇第一句就是:“人之初,性本善”。那么对于神经网络来说,这句话就要改为:“网之初,感知机”。感知机( Perceptrons ),基本上...

1091
来自专栏Python小屋

Python+sklearn使用DBSCAN聚类算法案例一则

DBSCAN聚类算法概述: DBSCAN属于密度聚类算法,把类定义为密度相连对象的最大集合,通过在样本空间中不断搜索最大集合完成聚类。 DBSCAN能够在带有噪...

5934
来自专栏新智元

自然语言处理中的Attention Model:是什么及为什么

要是关注深度学习在自然语言处理方面的研究进展,我相信你一定听说过Attention Model(后文有时会简称AM模型)这个词。AM模型应该说是过去一年来NLP...

4335
来自专栏人工智能LeadAI

pyTorch自然语言处理简单例子

最近在学pyTorch的实际应用例子。这次说个简单的例子:给定一句话,判断是什么语言。这个例子是比如给定一句话: Give it to me 判断是 ENGL...

4327

扫码关注云+社区

领取腾讯云代金券