Fixed point iteration
這裡我們介紹固定點迭代法 (Fixed point iteration)
首先我們介紹什麼是固定點 (Fixed point)
Definition: Fixed point
A fixed point of a function
is a number in its domain such that .
所以簡單來說, 把固定點這個數字丟進函數後會得到同樣的一個數字. 所以稱之為固定點.
那固定點重要性其一是在數值計算上有一種迭代方式叫做固定點迭代(Fixed point iteration). 假設我們想要求某個函數的固定點, 也就是滿足
如果夠幸運的,
舉個例子來說, 假設我們想要解
這樣的話如果數列收斂,
不過這裡有兩個問題.
-
為什麼這個數列會收斂?
-
原方程式的固定點迭代其實有無窮多種改寫方式, 例如也可寫為
. 如果收斂的話一樣會是原方程式的解. 那, 哪種改寫方式最好呢?
我們有以下這個定理
Theorem
If
is a differentiable function such that then has exactly one fixed point and the fixed point iteration converges to .
這個證明很簡單.
Proof
(Sketch, not complete, please full-in the details by yourself)
existence
Since the domain and the range of
are both , by Intermediate Value Theorem, there exists such that uniqueness
If there exits another fixed point
, , such that , then according to Mean Value Theorem(MVT), there exits between and such that which violate the assumption that . So the fixed point is unique. convergence of fixed point iteration
Based on MVT we have
所以如果在函數固定點
固定點迭代是求根問題(root finding problems)中很重要的一種迭代方式. 舉個例子來說, 假設我們想要找
那要如何改寫才會比較好呢? 其中一個最有名的就是牛頓法 (Newton’s method):
Newton’s iteration
我們可以定義
更進一步我們可以利用泰勒展開式(Taylor’s series expansion) 來證明牛頓法事實上有二次收斂,
依之前的例子我們想要解
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_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:
最後總結一下:
-
固定點迭代要收斂, 至少在固定點的微分值必須比
小. -
要取迭代函數, 如果知道如何對函數微分, 以牛頓法 Newton’s method 來取通常會有不錯的效果.
-
若無法得知微分函數, 可以用數值微分來逼近真實微分, 這樣會得到割線法 secant method, 收斂速度比牛頓法慢一點點.
Remark:
-
固定點定理保證在區間裡任意取點當初使迭代都會收斂, 不過要滿足定理的條件很強, 實務上不容易做到.
-
例如牛頓法, 我們能證明一定存在某個區間滿足固定點定理, 不過實際上這個區間有多大並不知道. 因此一般在討論牛頓法時都會要求初始值要離實際要求的固定點"夠近". 至於"夠近"什麼意思就只能用嘗試的.
-
由於牛頓法不保證收斂, 因此實務上要求根時會與一些保證收斂的方法, 如二分逼進法 (bisection method) 來合作. 如 Brent-Dekker method. 這樣既能保證收斂, 又兼有收斂快速的優點.