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

相关文章

来自专栏人工智能LeadAI

pyTorch自然语言处理简单例子

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

4127
来自专栏calmound

JOJ 2680 Problem F: Coin Game

题意:给你两组数,第一组按从大到小的顺序给出,第二组随机给,让你求挪动最小的次数使第二组的数字比第一组相对应位置的数字要小,挪动的顺序只能够相邻的挪动 分析:从...

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

TensorFlow系列专题(十一):RNN的应用及注意力模型

目前循环神经网络已经被应用在了很多领域,诸如语音识别(ASR)、语音合成(TTS)、聊天机器人、机器翻译等,近两年在自然语言处理的分词、词性标注等工作的研究中,...

701
来自专栏AI科技评论

开发|简单有趣的 NLP 教程:手把手教你用 PyTorch 辨别自然语言(附代码)

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

3047
来自专栏cs

NLP问题之word2vec

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

1602
来自专栏Python小屋

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

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

4844
来自专栏GIS讲堂

sde用sql实现erase

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

833
来自专栏机器之心

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

2835
来自专栏Brian

熵的理解

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

2956
来自专栏新智元

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

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

4135

扫码关注云+社区