# Fixed point iteration

## Definition: Fixed point

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

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$.

### (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.$$

## Newton’s iteration

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

    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:

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

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

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

Remark:

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

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

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

##### Te-Sheng Lin (林得勝)
###### Associate Professor

The focus of my research is concerned with the development of analytical and computational tools, and further to communicate with scientists from other disciplines to solve engineering problems in practice.