數(shù)值分析3(不動點迭代)

1、1/25迭代法回顧迭代法回顧11-1-1111110.5(), () ()0()0.5(), () ()0nnnnnnnnnnxaf xf axxxbf xf b 如如果果如如果果二分法二分法: 設(shè)設(shè)f(x) = 0的根為的根為 x*,通過迭代計算產(chǎn)生序列通過迭代計算產(chǎn)生序列: 0101()()nnxxxxx *limnnxx 15:062/25設(shè)設(shè)f(x) = 0的根為的根為 x*,通過迭代計算通過迭代計算,產(chǎn)生序列產(chǎn)生序列: 迭代的思想迭代的思想0101()()nnxxxxx 迭代法研究包括方面迭代法研究包括方面: :迭代初值迭代初值迭代格式迭代格式判別收斂及收斂速度判別收斂及收斂速度*l

2、imnnxx 15:063/25數(shù)值分析3不動點迭代法不動點迭代法不動點迭代的收斂性不動點迭代的收斂性迭代序列的收斂速度迭代序列的收斂速度序列收斂加速方法序列收斂加速方法15:064/25引子引子 選擇任意的數(shù)字選擇任意的數(shù)字x。Matlab中輸入命令中輸入命令x=your number。例如。例如x = 3。 Matlab中輸入命令中輸入命令x=sqrt(1+x)。命令計算。命令計算(1+x)1/2并用最新的結(jié)果替代以前的結(jié)果。重復上并用最新的結(jié)果替代以前的結(jié)果。重復上述過程述過程(up-arrow鍵鍵), 得到如下結(jié)果得到如下結(jié)果: 3 2 1.7321 1.6529 1.6288 1.6

3、213 1.6191 1.6184 1.6181 1.6181 1.6180 1.6180 1.61805/25 Matlab中等號是賦值算子。即計算等式右邊的中等號是賦值算子。即計算等式右邊的值并將值存儲到左邊的變量。命令計算值并將值存儲到左邊的變量。命令計算(1+x)1/2并并用最新的結(jié)果替代以前的結(jié)果。重復上述過程得用最新的結(jié)果替代以前的結(jié)果。重復上述過程得到如下最后結(jié)果為到如下最后結(jié)果為1.6180(黃金比例黃金比例 )。 而數(shù)學中等號的意思有所不同。方程而數(shù)學中等號的意思有所不同。方程 的根稱為函數(shù)的根稱為函數(shù) f(x)=(1+x)1/2的不動點。函數(shù)的不動點。函數(shù)f(x)有一個不動

4、點有一個不動點(1+(5)1/2)/2。1xx啟示啟示: 兩種不同的思路計算方程的根兩種不同的思路計算方程的根: 1) 尋尋找根的顯式計算公式找根的顯式計算公式; 2)通過重復簡單的不通過重復簡單的不動點計算并賦值來逐步逼近方程的解。動點計算并賦值來逐步逼近方程的解。6/25等價變換等價變換f (x) 的根的根的不動點的不動點不動點迭代不動點迭代(Fixed Point Iteration)對于對于f(x)=0, 不動點可以構(gòu)造為不動點可以構(gòu)造為:( )( )xxf x ( )( ) ( )xxx f x*()xx ( )x 1()nnxx x*稱為不稱為不 動點動點15:06*()0f x

5、7/25不動點迭代不動點迭代(Fixed Point Iteration)選擇適當?shù)某跏贾颠x擇適當?shù)某跏贾祒0,按照如下的迭代格式計算按照如下的迭代格式計算:( )xx 1(), =0,1,2,nnxxn 如果數(shù)列如果數(shù)列xn有極限有極限 , 則稱迭代是收則稱迭代是收斂的。斂的。 是非線性方程的根和是非線性方程的根和 的不動點。的不動點。*x( )x *limnnxx 基本思想是將非線性方程求解歸結(jié)為一系列顯基本思想是將非線性方程求解歸結(jié)為一系列顯式的函數(shù)值計算。式的函數(shù)值計算。8/25例例1 方程方程 x3 + 4x2 10 = 0 在在 1, 2 上有一個上有一個根根, 構(gòu)造求根的不動點迭

6、代格式。構(gòu)造求根的不動點迭代格式。(1)10 /4xxx ( )10/4xxx 5 . 1)(01 xxxnn ( n = 0, 1, 2, )5 . 1)(01 xxxnn ( n = 0, 1, 2, )4/(10)( xx (2)4/(10 xx15:069/254101 nnxx 1.5000 0.8165 2.9969 (-8.65)1/2 0.5487 1.6317 0123n xn | xn x* | 1.5000 1.3484 1.3674 1.3650 1.3653 1.3652 1.3652 0.0168 0.0022 2.0e-04 1.0e-04 0 00123456n

7、 xn | xn - x* |110 /4nnnxxx 什么樣的迭代格式收斂？什么樣的迭代格式收斂？15:0610/25中值定理中值定理: 若函數(shù)若函數(shù)f(x) 滿足滿足:(i)在在a,b連續(xù)連續(xù);(ii)在在(a,b)可導可導;則在則在 (a, b) 內(nèi)至少存在一點內(nèi)至少存在一點 ,使得使得 ( )( )( )f bf afba 15:0611/25*2.1( ) , (1) ( ) (2) |( )|1( ) , xabaxbxLxa bx 引引理理 如如果果在在上上具具有有連連續(xù)續(xù)的的一一階階導導數(shù)數(shù)且且滿滿足足條條件件和和 則則在在有有唯唯一一的的不不動動點點。證證 若若 或或 ,顯然

8、顯然 有不動點有不動點aa )( bb )( )(x 設(shè)設(shè) , 則有則有 ,aa )( bb )( aa )( bb )( 記記 則有則有xxx )()( 0)()( ba 所以所以, 存在存在 x*使得使得即即 , 故故 x* 是是 的不動點。的不動點。0*)( x )(*xx )(x 15:0612/2515:0613/25如果如果 有兩個不同的不動點有兩個不同的不動點 則有則有)(x *2*1xx )(*1*1xx )(*2*2xx 兩式相減得兩式相減得)()(*2*1*2*1xxxx 由拉格朗日中值定理知由拉格朗日中值定理知, 存在存在 介于介于 和和 之間之間*1x*2x )()()

9、(*2*1*2*1*2*1xxxxxx *121212| |( )| |xxxxL xx 與與L1 條件矛盾條件矛盾故不動點唯一。故不動點唯一。15:0614/25證證 )()(*1xxxxnn | )(| )()(|*1*1*xxxxxxnnn |*1*xxLxxnn 15:060+1*12.2( ) , (1) ( ) (2) |( )|1 , ,(),1 |1nnnnnnxabaxbxLxa bxxxxxxxxL 引引理理 如如果果在在上上具具有有連連續(xù)續(xù)的的一一階階導導數(shù)數(shù)且且滿滿足足條條件件和和。則則對對任任意意的的迭迭代代格格式式產(chǎn)產(chǎn)生生的的序序列列收收斂斂到到不不動動點點且且滿滿

10、足足壓縮映像壓縮映像15/25|*0*xxLxxnn0|lim|lim*0* xxLxxnnnn( 0L0 , p0 使得使得1|*|lim|*|npnnxxaxx 則稱數(shù)列則稱數(shù)列xn p 階收斂。階收斂。特別特別: (1) 收斂階收斂階p =1時時,稱為線性收斂稱為線性收斂; (2) 收斂階收斂階p 1時時,稱為超線性收斂稱為超線性收斂; (3) 收斂階收斂階p =2 時時,稱為平方收斂。稱為平方收斂。序列的收斂階數(shù)越高序列的收斂階數(shù)越高, 則收斂速度越快。則收斂速度越快。18/251*()( *)( )(*)nnnxxxxxx 1|*|lim|( *)| 0|*|nnnxxxxx 15:

11、0621(1)()1( *)*()( *)( *)(*)(*)2( *)( ) +(*)(*)(1)!nnnnppppnnxxxxxxxxxxxxxxxpp 19/25定理定理2.6 設(shè)設(shè)x*是是 的不動點的不動點,且且)(x0*)(*)(*)()1( xxxp 而而 則則 p階收斂階收斂0*)()( xp )(1nnxx | )(|!|*|*)()(|*|)(1nppnnnpxxxxxx 由由Taylor公式公式其中其中, 介于介于xn和和x*之間之間. 所以所以n |*)(|!1| )(|lim!1|*|*|lim)()(1xppxxxxpnpnpnnn 故迭代法故迭代法p階收斂。階收斂。

12、15:0620/25例例2 用不同迭代格式求方程用不同迭代格式求方程 x2-3=0的根。的根。214( )(3)xxx (a)*3122()1, ()10.1341xxx 則則312( )()xxx (b)2*312()(1), ()0 xxx 則則2( )3xxx (c)*()21, ()2311xxx 則則( )3 /xx (d)*()1x 則則21/25xk(a)(b)(c)(d) x02222 x11.75001.750031.5000 x21.7344 1.732192 x31.73241.7321871.5000 x4 1.73211.73217653222/25*lim()nnx

13、x 0101()()nnxxxxx 不動點框架不動點框架:15:06收斂性收斂性 收斂速度收斂速度(1)()( *)( *)( *)0 ( *)0ppxxxx |( )| 1x 23/25 Everyone loves a good cup of coffee, mathematicians especially. But did you know there is a beautiful pure mathematics theorem at work every time you make yourself a mug of that deliciously addictive stuff

14、? 一個數(shù)學家就是一臺把咖啡轉(zhuǎn)化為數(shù)學定理的機器。一個數(shù)學家就是一臺把咖啡轉(zhuǎn)化為數(shù)學定理的機器。 P. Erdos24/25 Brouwers Fixed Point Theorem says precisely “every continuous function from a compact subset in n-dimensional Euclidean space to the same subset has a fixed point”. Well take your mug and fill it up with coffee, give it a good old stir and then let it come to rest again. This theorem guarantees that there is at least one point in the cup (what we call the “fixed point”) that ends up in the exact same position as the position it started in.25/25Aitken加速方法加速方法(松弛思想松弛思想)21112()2nnnnnnnxxy