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

相关文章

来自专栏大数据挖掘DT机器学习

R语言实现混合模型

普通的线性回归只包含两项影响因素,即固定效应(fixed-effect)和噪声(noise)。噪声是我们模型中没有考虑的随机因素。而固定效应是那些可预测因素,而...

5746
来自专栏机器之心

学界 | 密集对象网络:通过机器人操作学习密集的视觉对象描述符

作者:Peter R. Florence、Lucas Manuelli、Russ Tedrake

933
来自专栏人工智能LeadAI

TensorFlow从0到1丨 第五篇:TensorFlow轻松搞定线性回归

上一篇 第一个机器学习问题 其实是一个线性回归问题(line regression),呈现了用数据来训练模型的具体方式。本篇从平行世界返回,利用TensorFl...

3357
来自专栏TensorFlow从0到N

TensorFlow从0到1 - 5 - TensorFlow轻松搞定线性回归

上一篇 第一个机器学习问题 其实是一个线性回归问题(Linear Regression),呈现了用数据来训练模型的具体方式。本篇从平行世界返回,利用Tenso...

3488
来自专栏黄成甲

数据分析之时间序列分析

顾名思义,时间序列就是按照时间顺利排列的一组数据序列。时间序列分析就是发现这组数据的变动规律并用于预测的统计技术。该技术有以下三个基本特点:

1112
来自专栏机器之心

ACL 2018 | 神经语言模型如何利用上下文信息:长距离上下文的词序并不重要

1895
来自专栏新智元

DeepMind重磅:神经算术逻辑单元,Keras实现

【新智元导读】DeepMind最新提出“神经算术逻辑单元”,旨在解决神经网络数值模拟能力不足的问题。与传统架构相比,NALU在训练期间的数值范围内和范围外都得到...

512
来自专栏深度学习之tensorflow实战篇

开源|LightGBM基本原理,以及调用形式

5303
来自专栏AI研习社

文本分类又来了,用 Scikit-Learn 解决多类文本分类问题

在商业领域有很多文本分类的应用,比如新闻故事通常由主题来分类;内容或产品常常被打上标签;基于如何在线谈论产品或品牌,用户被分成支持者等等。

861
来自专栏AI科技大本营的专栏

前沿 | DeepMind 最新研究——神经算术逻辑单元,有必要看一下!

众所周知,神经网络可以学习如何表示和处理数字式信息,但是如果在训练当中遇到超出可接受的数值范围,它归纳信息的能力很难保持在一个较好的水平。为了推广更加系统化的数...

811

扫码关注云+社区