固定點疊代法(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）。後續文章會繼續介紹其他解法。