為什麼不動點迭代法的收斂與其導數有關？

01-07

吳勃英數值分析中的有關不動點迭代法的內容里，關於迭代函數收斂的問題中的這個

「顯然，要使迭代收斂，必須要有 $|varphi (x)$ 「不是很明白，
1）這裡的 L 是指什麼？
2）為什麼迭代函數的收斂與其導數有關，大於會怎麼樣

xiexieyaoqing~~

問題一：這裡的L（Lipschitz常數）指的是介於0到1之間的一個常數；

滿足 $left| varphi left( x_{1} ight)-varphi left( x_{2} ight) ight|leq Lleft| x_{1}-x_{2} ight| left( 0<L<1 ight)$ 的映射稱為壓縮映射。由壓縮映射的性質可以保證迭代函數存在唯一的不動點（存在唯一性）並且迭代是收斂的（全局收斂性），同時還可以得到先驗誤差和後驗誤差估計~

問題二：與導數有關是因為中值定理 $left| varphi left( x_{1} ight)-varphi left( x_{2} ight) ight|leq left| varphi ^{$

你看，如果導數小於L，就保證了 $varphi left( x ight)$ 是一個壓縮映射，故而得到上面的存在唯一性和收斂性等結論~

由於該條件是充分的，所以如果大於（不滿足條件）則不能保證迭代是收斂的。。。

我就回答這麼多吧~題主可以看看壓縮映射和不動點原理這兩個知識~因為不動點迭代的核心就是把方程的根轉化為求函數（映射）的一個不動點~~

一個不太確切的比喻。假設你和你未來的老婆在這個世界上以自己的規律生活，x_1是你的位置，x_2是你老婆的位置。phi 每迭代一次，時間就往前推進一個小時，你們在世界上的位置就更新為 phi(x_1) 和phi(x_2).

秒速五厘米：我要以怎樣的速度生活，才能和你相遇？

現在是Lipchitz條件的用處。雖然你和你老婆的生活規律沒有特定的聯繫，但是你們堅信，有緣的人終究會相見，所以每過一個小時，你們倆之間的距離就會變成一小時前的0.9倍，也就是縮短10%。那麼經過兩個小時，你們的距離就縮短為兩小時前的0.9^2。經過三個小時變成原來的0.9^3。以此類推，因為0.9^n終究會趨近於0。也就是說總有一天你們之間的距離可以無限小。

這就是你們遇見的那一刻。無論一開始你們身在何處（x_1,x_2），只要朝著緣分的指向（導數上界），你們的距離就能不斷靠近，最終相遇。

相遇之後呢？你們就一直待在那裡不動了，不用再為了尋找真愛而在世界上漂泊。

這就是壓縮映射的不動點定理喲。

所以，壓縮映射的關鍵條件就是Lipchitz係數要嚴格小於1，這樣保證了它的高次方會趨近於0。而導數的這個上界，就是你們的緣分係數吧。如果大於等於1了，那你們就可能永遠不會相遇。

如果一個數列 $left{ x_n ight}$ 的兩項間距逐漸縮小，即 $left| x_{n+1}-x_n ight| leqslant Lleft| x_n - x_{n-1} ight|,,0<L<1$ ，那麼數列一定收斂。這就是數列的「壓縮映射」原理。

（這是因為： $left| x_{n+p}-x_n ight| leqslant sum_{k=n+1}^{n+p}{left| x_{k}-x_{k-1} ight|}leqslant sum_{k=n+1}^{n+p}{L^{k-1}left| x_{1}-x_{0} ight|}=left| x_1 -x_0 ight|frac{L^n -L^{n+p}}{1-L}leqslantleft| x_1 -x_0 ight|frac{L^n}{1-L}$

由D"Alembert判別法以及Cauchy準則知道 $left{ x_n ight}$ 收斂。）

那如果 $left{ x_n ight}$ 是經由 $f(x)$ 迭代而出來的數列，也就是說，給一個初值， $left{ x_n ight}$ 是用遞推公式 $x_{n+1}=f(x_n),,(n=0,1,cdots)$ 給出來的，要使這個數列收斂，這個迭代函數 $f$ 得滿足一定的性質。如果 $f$ 滿足了： $left| f$ ，就能保證 $left{ x_n ight}$ 收斂。因，利用微分中值定理：