固定点迭代法(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 条评论
登录 后参与评论

相关文章

来自专栏AI研习社

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

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

3405
来自专栏GIS讲堂

sde用sql实现erase

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

723
来自专栏灯塔大数据

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

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

3645
来自专栏Python小屋

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

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

3924
来自专栏AI科技评论

干货 | 完全图解RNN、RNN变体、Seq2Seq、Attention机制

AI科技评论按:本文作者何之源,原文载于知乎专栏AI Insight,AI科技评论获其授权发布。 本文主要是利用图片的形式,详细地介绍了经典的RNN、RNN几个...

4154
来自专栏人工智能LeadAI

机器学习实战 | 数据探索

数据的输入质量决定了输出的最后结果,数据的探索、预处理、特征选择、降维等特征工程占了项目的70%的时间。那么如果我们确定了商业目的,该如何一步一步渐进式进行特征...

3535
来自专栏Brian

熵的理解

---- 熵 熵在信息论中代表随机变量不确定度的度量。一个离散型随机变量X的熵H(X)定义为: image.png 明确定义的科学名词且与内容无关,而且不随信息...

2866
来自专栏人工智能LeadAI

pyTorch自然语言处理简单例子

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

3887
来自专栏专知

【干货】一文读懂什么是变分自编码器

【导读】本文是工程师Irhum Shafkat的一篇博文,主要梳理了变分自编码器的相关知识。我们知道,变分自编码器是一种生成模型,在文本生成、图像风格迁移等诸多...

1.2K10
来自专栏机器之心

教程 | 如何使用贪婪搜索和束搜索解码算法进行自然语言处理

2745

扫码关注云+社区