第二節(jié) 迭代法及其收斂性1

1、數(shù)值計算方法數(shù)值計算方法對于一般的非線性方程對于一般的非線性方程, ,沒有通常所說的求根公式求其精沒有通常所說的求根公式求其精確解確解, ,需要設(shè)計近似求解方法需要設(shè)計近似求解方法, ,即即迭代法迭代法。它是一種逐次。它是一種逐次逼近的方法逼近的方法, ,用某個固定公式反復校正根的近似值用某個固定公式反復校正根的近似值, ,使之使之逐步精確化，最后得到滿足精度要求的結(jié)果。逐步精確化，最后得到滿足精度要求的結(jié)果。10.2 迭代法及其收斂性迭代法及其收斂性 10.2.1 10.2.1 不動點迭代法的基本概念和迭代格式的構(gòu)造不動點迭代法的基本概念和迭代格式的構(gòu)造 將方程（1.1）改寫成等價的形式 )

2、.(xgx （2.1）若要求 滿足 ，則 ；反之亦然，稱 為函數(shù) 的一個不動點. *x0*)(xf*)(*xgx*x)(xg 求 的零點就等價于求 的不動點，選擇一個初始近似值 ，將它代入(2.1)右端，即可求得 )(xf)(x0 x).(01xgx 如此反復迭代計算 )., 1 ,0()(1kxgxkk（2.2）)(xg 稱為迭代函數(shù).如果對任何 ，由（2.2）得到的迭代序列 有極限 ,0baxkx.*limxxkk則稱迭代方程(2.2)收斂，且 為 的不動點，故稱（2.2）為不動點迭代法不動點迭代法. *)(*xgx)(xg 上述迭代法是一種逐次逼近法，其基本思想是將隱式方程（2.1）歸結(jié)

3、為一組顯式的計算公式（2.2），就是說，迭代過程實質(zhì)上是一個逐步顯示化的過程. 方程 的求根問題在 平面上就是要確定曲線 與直線 的交點 )(xgx xy)(xyxy .*P 對于 的某個近似值 ，在曲線 上可確定一點 ，它以 為橫坐標，而縱坐標則等于 *x0 x)( xgy 0P0 x.)(10 xxg過 引平行 軸的直線，設(shè)此直線交直線 于點 ，然后過 再作平行于 軸的直線，它與曲線 的交點記作 ，則點 的橫坐標為 ，縱坐標則等于0Pxxy 1Q1Qy)(xy1P1P1x)(1x.2x圖1-2 例例1 1 求方程 01)(3xxxf（2.3）在 附近的根 5.10 x.*x 解解 設(shè)將方程

4、（2.3）改寫成下列形式 .13xx 按圖1-2中箭頭所示的路徑繼續(xù)做下去，在曲線 上得到點列 ，其橫坐標分別為依公式 求得的迭代值)(xgy 21, PP)(1kkxgx.,21xx據(jù)此建立迭代公式 如果點列 趨向于點 ，則相應(yīng)的迭代值 收斂得到所求的根 kP*Pkx.*x32494.1432472.1832588.1332472.1733086.1232473.1635721.1132476.155.1027kkxkxk表).,2, 1 ,0(131kxxkk各步迭代的結(jié)果見表. 如果僅取6位數(shù)字，那么結(jié)果 與 完全相同，這時可以認為 實際上已滿足方程(2.3)，即為所求的根.7x8x7x

5、但若采用方程（2.3）的另一種等價形式13 xx建立迭代公式 .131kkxx仍取迭代初值 ，則有 5.10 x.39.12,375.221xx結(jié)果會越來越大，不可能趨于某個極限. 這種不收斂的迭代過程稱作是發(fā)散發(fā)散的. 一個發(fā)散的迭代過程，縱使進行了千百次迭代，其結(jié)果也是毫無價值的.xyy = xxyy = xxyy = xxyy = xx*x*x*x*y= (x)y= (x)y= (x)y= (x)x0p0 x1p1x0p0 x1p1 x0p0 x1p1x0p0 x1p1x2 10.2.2 10.2.2 不動點的存在性與迭代法的收斂性不動點的存在性與迭代法的收斂性 首先考察 在 上不動點的

6、存在唯一性. ,ba)(xg定理定理1 1 設(shè) 滿足以下兩個條件：,)(baCxg1 映內(nèi)性映內(nèi)性 對任意 有 ,bax bxga)(2 壓縮性壓縮性 存在正常數(shù) ,使對 都有 10 L,21baxx.)()(2121xxLxgxg（2.4）,L其中 稱為，或稱為。壓壓縮縮系系數(shù)數(shù)李李普普希希茲茲常常數(shù)數(shù)( ) , .g xa bx則函數(shù)在上存在的不動點唯唯 一一 證明證明 先證不動點存在性. 若 或 ，顯然 在 上存在不動點. aag)(bbg)()( xg,ba 因 ，以下設(shè) 及 ，定bxga)(aag)(bbg)(義函數(shù).)()(xxgxf顯然 ，且滿足 ，由連續(xù)函數(shù)性質(zhì)可知存在 使 ，

7、即 即為 的不動點.,)(baCxf)(,0)()(bfaagaf0)( bbg),(*bax0*)(xf*),(*xxgx)( xg 再證唯一性. 設(shè) 都是 的不動點，則由(2.4)得 ,21baxx)( x.)()(21212121xxxxLxgxgxx引出矛盾. 故 的不動點只能是唯一的. 證畢.)( xgkx定理定理.2 .2 設(shè) 滿足定理1中的兩個條件，則對任意 ，由（2.2）得到的迭代序列 收斂收斂到 的不動點 ，并有誤差估計誤差估計 ,)(baCxg,0bax)( xg*x.1*01xxLLxxkk（2.5） 證明證明 設(shè) 是 在 上的唯一不動點，由條件1，可知 ，再由（2.4）

8、得 ,ba,*bax)( xg,baxk.*)()(*011xxLxxLxgxgxxkkkk因 ，故當 時序列 收斂到 .10 Lkkx*x 再證明估計式（2.5），由李普希茲條件有 .)()(111kkkkkkxxLxgxgxx（2.6）反復遞推得 .011xxLxxkkk于是對任意正整數(shù) 有p.1)(0101211211xxLLxxLLLxxxxxxxxkkpkpkkkpkpkpkpkkpk在上式令 ，注意到 即得式（2.5）證畢.p*limxxpkp 迭代過程是個極限過程. 在用迭代法實際計算時，必須按精度要求控制迭代次數(shù). 誤差估計式（2.5）原則上可用于確定迭代次數(shù)，但它由于含有信息

9、 而不便于實際應(yīng)用. L 根據(jù)式（2.6），對任意正整數(shù) 有 p1211(1)1.1ppkpkkkpkkxxLLxxLxxL在上式中令 知 p.11*1kkkxxLxx 由此可見，只要相鄰兩次計算結(jié)果的偏差 足夠小即可保證近似值 具有足夠精度.kkxx1kx 對上述定理中的壓縮性， 在使用時如果 且對任意 有 ,)(1baCxg,bax , 1)(Lxg（2.7）則由中值定理可知對 有 ,bayx).,(,)()()(212121baxxLxxgxgxg表明定理中的壓縮性條件可用（2.7）代替. 例7.2.3中，當 時， ,在區(qū)間 中， ，故（2.7）成立. 31)(xxg3/2)1(31)(

10、xxg2,114131)(3/1 xg又因 ，故定理1中條件1也成立.所以迭代法是收斂的. 23)(2133xg而當 時， 在區(qū)間 中 不滿足定理條件.1)(3 xxg23)(xxg2, 11)( xg10.3 10.3 局部收斂性與收斂階局部收斂性與收斂階 上面給出了迭代序列 在區(qū)間 上的收斂性，通常稱為全局收斂性. 定理的條件有時不易檢驗，實際應(yīng)用時通常只在不動點 的鄰近考察其收斂性，即局部收斂性.kx,ba*x 定義定義7.2.1 7.2.1 設(shè) 有不動點 ，如果存在 的某個鄰域 ，對任意 ，迭代（2.2）產(chǎn)生的序列 ，且收斂到 ，則稱迭代法（2.2）局部收斂局部收斂.)( x*x*x*

11、:xxRRx0Rxk*x定理定理7.2.3 7.2.3 設(shè) 為 的不動點， 在 的某個鄰域連續(xù)，且 ，則迭代法（2.2）局部收斂.*x)( x)( x*x1*)( x 證明證明 由連續(xù)函數(shù)的性質(zhì)，存在 的某個鄰域 ，使對于任意 成立 *x*:xxRRx .1)(Lx此外，對于任意 ，總有 ，這是因為 Rx Rx )(.*)()(*)(xxxxLxxxx于是依據(jù)定理7.2.2可以斷定迭代過程 對于任意初值 均收斂. )(1kkxxRx 0證畢. 解解 這里 ，可改寫為各種不同的等價形式 ，其不動點為 由此構(gòu)造不同的迭代法：3)(2 xxf)( xgx .3* x. 1132)3(*)(, 12)

12、(gxgxxg 例例7.2.2 7.2.2 用不同方法求方程 的根 032x.3* x 討論迭代序列的收斂速度. , 3)(, 3) 1 (221xxxgxxxkkk.1*)(,3)(2xgxxg,3)(,3)2(1xxgxxkk.1134.0231*)(,211)(xgxxg.0)3(*)(),31(21)(2xgxxg取 ，對上述4種迭代法，計算三步所得的結(jié)果如下表. 20 x),3(21)(),3(21)4(1xxxgxxxkkk),3(41)(),3(41)3(221xxxgxxxkkk732051.1732361.15.1873732143.173475.129275.175.15.

13、13122220)4()3()2()1(373210 xxxxxkk迭代法迭代法迭代法迭代法計算結(jié)果表 注意 ，從計算結(jié)果看到迭代法（1）及（2）均不收斂，且它們均不滿足定理3中的局部收斂條件，迭代法（3）和（4）均滿足局部收斂條件，且迭代法（4）比（3）收斂快，因在迭代法（4）中 . 7320508.13 0*)( xg 定義定義7.2.2 7.2.2 設(shè)迭代過程 收斂于方程 的根 ，如果迭代誤差 當 時成立下列漸近關(guān)系式 )(1kkxgx)( xgx *x*xxekkk),1,0(1pCCeepkk常數(shù)則稱該迭代過程是 階收斂階收斂的,C為漸進誤差常數(shù)漸進誤差常數(shù).特別地, 時稱線性收斂線

14、性收斂， 時稱超線性收斂超線性收斂， 時稱平方收斂平方收斂. p1p1p2p111: ()()()()(), limlim()().kkkkkkkkkkkkkkexxg xg xgxxgexxeggxe由微分中值定理可得其中在與之間 再由局部收斂可知故迭代格式是線性收斂的證證明明 ( ),()0()0()1),.g xgxgxgx若迭代函數(shù)除了滿足上述定理的條件之外 還滿足即滿足則迭代格式是線性收斂的推推論論7 7. .2 2. .2 2 ()(1)()()1 ( ),1,( ),( *)( *)( *)0,( *)0, (2.8)() lim!ppppkkkxg xpgxxxpgxgxgxg

15、xegxep設(shè)是迭代函數(shù)的不動點 整數(shù)在的鄰域上連續(xù) 則迭代格式在的鄰域上是 階收斂的充分必要條件為且有定定理理7 7. .2 2. .3 3 證明證明 先證充分性先證充分性由于 ，據(jù)定理7.2.3立即可以斷定迭代過程 具有局部收斂性. 0*)( xg)(1kkxgx 再將 在根 處做泰勒展開，利用條件（2.8），則有 )(kxg*x.*,*)(!)(*)()()(之間與在xxxxpgxgxgkkpkkpk注意到 ，由上式得 *)(,)(1xxgxxgkk,*)(!)(*)(1pkkpkxxpgxx因此對迭代誤差，當 時有 k.!*)()(1pxgeeppkk（2.9）這表明迭代過程 確實為

16、階收斂. 證畢. )(1kkxgxp000(1)()0 ,(2.8),( *)( *)( *)0,( *)0,.(2.8).ppxpppg xgxgxgxp設(shè)迭代格式在 的鄰域上是 階收斂的 若不成立 則必存在不等于 最小正整數(shù)使得又由充分性證明過程可知上述迭代格式的收斂階為矛盾故成立證畢再再證證必必要要性性 上述定理說明，迭代過程的收斂速度依賴于迭代函數(shù) 的選取. 如果當 時 ，則該迭代過程只可能是線性收斂. )( xg,bax 0)( xg 在例7.2.2中，迭代法（3）的 ，故它只是線性收斂，而迭代法（4）的 ，而 由定理4知 ，即該迭代過程為2階收斂. 0*)( xg0*)( xg,6

17、)(3xxg .032*)( xg2p333124( )-2 -50,1( )25( )(-5),2, 10f xxxxg xxxgxx已知方程內(nèi)有一實根 分別選取及作為迭代函數(shù) 試判斷對應(yīng)的迭代公式是否收斂 并用一個收斂的迭代公式求方程的根 精度要求為例例7 7. .2 2. .3 311.52.5,2( )2.2xg x解：（）由于當時122332121( )33(25)(21.55)0.16671,1.5,2.5gxxx又由于4545 0.000 05102.094 54,2.094 551 481 50.xxxxx由上表知 ，故可取而方程的準確解是 13110( ) ()252kkkk

18、g xxg xxxx所以迭代函數(shù)對應(yīng)的迭代公式產(chǎn)生的序列收斂于方程的唯一根，取，計算結(jié)果見表k02.000 0012.080 080.080 0822.092 350.012 2732.094 20.001 8742.094 49 0.000 2752.094 540.000 05kx1kkxx222231233(2)( )1.53.3751(1.5,2.5)22( )1()(-5)2kkkgxxxgxxgxx由于，所以迭代函數(shù)對應(yīng)的迭代公式 發(fā)散。v10.3迭代收斂的加速1( )1( ),( ),1111( )( ),11(1)(),kknnnnnnxxxxxxxxxxxxx 松弛法：對方程兩邊加上整理得令求導記：得到迭代方程是松弛因子，這就是松弛法。(1)(2)(1)111(1)1(2)(1)(1)2111(1)1(2)(1)