固定点迭代法(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）。后续文章会继续介绍其他解法。