Fixed point iteration

這裡我們介紹固定點迭代法 (Fixed point iteration)

首先我們介紹什麼是固定點 (Fixed point)

Definition: Fixed point

A fixed point of a function $f(x)$ is a number $c$ in its domain such that $f(c)=c$.

所以簡單來說, 把固定點這個數字丟進函數後會得到同樣的一個數字. 所以稱之為固定點.

那固定點重要性其一是在數值計算上有一種迭代方式叫做固定點迭代(Fixed point iteration). 假設我們想要求某個函數的固定點, 也就是滿足 $c=f(c )$ 的這些 $c$, 那我們可以定義一個迭代式 $$ x_{n+1} = f(x_n). $$

如果夠幸運的, $\{x_{n}\}$ 這串數字收斂了, 那把它收斂到的數字稱為 $\bar{c}$ 我們就有 $\bar{c}=f(\bar{c})$, 也就是固定點.

舉個例子來說, 假設我們想要解 $x=\cos(x)$ 這個方程式, 那我們可以定義一個固定點迭代為 $$ x_{n+1} = \cos(x_n). $$

這樣的話如果數列收斂, $\{x_{n}\}\to \bar{x}$, 那我們就有 $\bar{x}=\cos(\bar{x})$, 那就解出來了!!

不過這裡有兩個問題.

1. 為什麼這個數列會收斂?

2. 原方程式的固定點迭代其實有無窮多種改寫方式, 例如也可寫為 $x_{n+1} = \cos^{-1}(x_n)$. 如果收斂的話一樣會是原方程式的解. 那, 哪種改寫方式最好呢?

我們有以下這個定理

Theorem

If $f:[a, b]\to [a,b]$ is a differentiable function such that $$ |f'(x)|\leq \alpha<1, \quad \forall x\in[a, b],$$ then $f$ has exactly one fixed point $c$ and the fixed point iteration converges to $c$.

這個證明很簡單.

Proof

(Sketch, not complete, please full-in the details by yourself)

existence

Since the domain and the range of $f$ are both $[a, b]$, by Intermediate Value Theorem, there exists $c$ such that $c=f(c ).$

uniqueness

If there exits another fixed point $\bar{c}$, $\bar{c}\ne c$, such that $\bar{c}=f(\bar{c} )$, then according to Mean Value Theorem(MVT), there exits $z$ between $c$ and $\bar{c}$ such that $$f'(z) = \frac{f(c ) - f(\bar{c})}{c-\bar{c}}=\frac{c - \bar{c}}{c-\bar{c}} = 1,$$ which violate the assumption that $|f'|\leq \alpha<1$. So the fixed point is unique.

convergence of fixed point iteration

Based on MVT we have $$|x_{n+1} - c| = |f(x_n) - f(c )| = |f'(c_i)(x_n-c)|\leq\alpha |x_n-c|\leq\alpha^n|x_1-c|\to 0.$$

所以如果在函數固定點 $c$ 的微分小於 $1$, 那就存在一個包含 $c$ 的小區間使得函數的微分都在這區間內小於 $1$, 那根據這定理固定點迭代就會收斂.

固定點迭代是求根問題(root finding problems)中很重要的一種迭代方式. 舉個例子來說, 假設我們想要找 $g(x)$ 這個函數的根, 那我們可以定義 $$ f(x) = x + g(x). $$ 這樣的話 $f$ 的固定點就會是 $g$ 的根了. 不過這種最簡單的改寫方式完全不保證會收斂.

那要如何改寫才會比較好呢? 其中一個最有名的就是牛頓法 (Newton’s method):

Newton’s iteration

$$x_{n+1} = x_n - \frac{g(x_n)}{g'(x_n)}.$$

我們可以定義 $f(x) = x - \frac{g(x)}{g'(x)}$, 這樣上面這個式子就是個固定點迭代. 接著我們可以發現, 如果 $c$ 是 $g$ 函數的根, 也就是 $g(c )=0$, 那 $f'(c ) = 0$. 所以根據上面的定理就存在某個包含 $c$ 的小區間使得迭代會收斂.

更進一步我們可以利用泰勒展開式(Taylor’s series expansion) 來證明牛頓法事實上有二次收斂, $$ |x_{n+1} - c| \approx \beta |x_n-c|^2. $$ 這個證明我們這邊就先略過不寫. 不過接著我們來看一下牛頓法究竟有多快.

依之前的例子我們想要解 $x=\cos(x)$, $x\in[0, \pi]$. 最簡單的固定點迭代為 $$ x_{n+1} = \cos(x_n), $$ 也就是求 $g(x) = \cos(x)-x$ 的根. 我們以 $x_0=1$ 當初始值, 發現需要 $80$ 個迭代才能使誤差在 $10^{-14}$ 之下.

    x_new= 0.5403023058681398		error= 0.31725090997825367
    x_new= 0.8575532158463934		error= 0.2032634253486143
    x_new= 0.6542897904977791		error= 0.13919056824478648
    x_new= 0.7934803587425656		error= 0.0921115851198091
    x_new= 0.7013687736227565		error= 0.06259090927789768
    ⋮
    x_new= 0.7390851332151851		error= 4.0967229608668276e-14
    x_new= 0.7390851332151441		error= 2.7644553313166398e-14
    x_new= 0.7390851332151718		error= 1.865174681370263e-14
    x_new= 0.7390851332151531		error= 1.2545520178264269e-14
    x_new= 0.7390851332151657		error= 8.43769498715119e-15
    Total number of iterations=80

若是使用牛頓法迭代則迭代式為 $$ x_{n+1} = x_n + \frac{cos(x_n)- x_n}{\sin(x_n)+1}. $$ 一樣以 $x_0=1$ 當初始值, 發現只需要 $4$ 個迭代就能使誤差在 $10^{-14}$ 之下. 比上個例子快上許多.

    x_new= 0.7503638678402439		error= 0.018923073822117442
    x_new= 0.7391128909113617		error= 4.6455898990771516e-5
    x_new= 0.739085133385284		error= 2.847205804457076e-10
    x_new= 0.7390851332151607		error= 0.0
    Total number of iterations=4

Summary:

最後總結一下:

• 固定點迭代要收斂, 至少在固定點的微分值必須比 $1$ 小.

• 要取迭代函數, 如果知道如何對函數微分, 以牛頓法 Newton’s method 來取通常會有不錯的效果.

• 若無法得知微分函數, 可以用數值微分來逼近真實微分, 這樣會得到割線法 secant method, 收斂速度比牛頓法慢一點點.

Remark:

• 固定點定理保證在區間裡任意取點當初使迭代都會收斂, 不過要滿足定理的條件很強, 實務上不容易做到.

• 例如牛頓法, 我們能證明一定存在某個區間滿足固定點定理, 不過實際上這個區間有多大並不知道. 因此一般在討論牛頓法時都會要求初始值要離實際要求的固定點"夠近". 至於"夠近"什麼意思就只能用嘗試的.

• 由於牛頓法不保證收斂, 因此實務上要求根時會與一些保證收斂的方法, 如二分逼進法 (bisection method) 來合作. 如 Brent-Dekker method. 這樣既能保證收斂, 又兼有收斂快速的優點.