非線性方程組的數(shù)值解法

1、第六章非線性方程組的迭代解法 6.4 非線性方程組的數(shù)值解法非線性方程組的數(shù)值解法6.4.3非線性方程組的非線性方程組的Newton法法6.4.2 非線性方程組的非線性方程組的Newton法法6.4.1 非線性方程組的不動(dòng)點(diǎn)迭代法非線性方程組的不動(dòng)點(diǎn)迭代法第六章非線性方程組的迭代解法 第六章非線性方程組的迭代解法 1.2學(xué)習(xí)目標(biāo)：學(xué)習(xí)目標(biāo)： 第六章非線性方程組的迭代解法 TnxfxfxfxF)(),(),()(21 設(shè)含有設(shè)含有n個(gè)未知數(shù)的個(gè)未知數(shù)的n個(gè)方程的非線性方程組為個(gè)方程的非線性方程組為 (6,4,1)其中其中 為為n維列向量，維列向量，0)( xFTnxxxx),(21 6.4.1

2、非線性方程組的不動(dòng)點(diǎn)迭代法非線性方程組的不動(dòng)點(diǎn)迭代法),2, 1)(nixfi 中至少有一個(gè)是中至少有一個(gè)是x的非線性函數(shù)，的非線性函數(shù)，并假設(shè)自變量和函數(shù)值都是實(shí)數(shù)。多元非線性方程組并假設(shè)自變量和函數(shù)值都是實(shí)數(shù)。多元非線性方程組(6.4.1)與一元非線性方程與一元非線性方程f(x)=0具有相同的形式，可以具有相同的形式，可以與一元非線性方程并行地討論它的迭代解法。例如不動(dòng)與一元非線性方程并行地討論它的迭代解法。例如不動(dòng)點(diǎn)迭代法和點(diǎn)迭代法和Newton型迭代法。但是，這里某些定理的型迭代法。但是，這里某些定理的證明較為復(fù)雜，我們將略去其證明。證明較為復(fù)雜，我們將略去其證明。第六章非線性方程組的

3、迭代解法 Tnxxxxx)(,),(),()(21(6.4.2)并構(gòu)造不動(dòng)點(diǎn)迭代法并構(gòu)造不動(dòng)點(diǎn)迭代法 , 1 , 0),()()1(kxxkk(6.4.3)把方程組把方程組(6.4.1)改寫成下面便于迭代的等價(jià)形式：改寫成下面便于迭代的等價(jià)形式：的解。的解。是方程組是方程組從而從而的不動(dòng)點(diǎn)，的不動(dòng)點(diǎn)，是迭代函數(shù)是迭代函數(shù)即即滿足滿足連續(xù)函數(shù)連續(xù)函數(shù). .則則的的是自變量是自變量是連續(xù)的是連續(xù)的, ,即即且且收斂，收斂，若由此生成的序列若由此生成的序列對(duì)于給定的初始點(diǎn)對(duì)于給定的初始點(diǎn)) 1 . 4 . 6()(),(,)(,),(),()(,*2121) 0 (xxxxxxxxxxxxxxnnf

4、 ff f f f KK kx*)(limxxkk 第六章非線性方程組的迭代解法 例例6.11 設(shè)有非線性方程組設(shè)有非線性方程組081008102122122121xxxxxxx(6.4.4)把它寫成等價(jià)形式把它寫成等價(jià)形式 )8(101),()8(101),(1211212222212111xxxxxxxxxxx并由此構(gòu)造不動(dòng)點(diǎn)迭代法并由此構(gòu)造不動(dòng)點(diǎn)迭代法 8)(101),( 8)()(101),()(122)(1)(2)(12) 1(22)(22)(1)(2)(11) 1(1kkkkkkkkkkkxxxxxxxxxxx, 1 , 0k(6.4.5)第六章非線性方程組的迭代解法 )(1kx)

5、(2kx取初始點(diǎn)取初始點(diǎn) 。計(jì)算結(jié)果列于表。計(jì)算結(jié)果列于表69，可見迭代收斂到，可見迭代收斂到方程的解方程的解Tx)0 , 0()0(Tx) 1 , 1 (*表表 6-9k012 18 1900.80.9280.9999999720.99999998900.80.9310.9999999720.999999989 函數(shù)也稱映射，若函數(shù)函數(shù)也稱映射，若函數(shù) 的定義域?yàn)榈亩x域?yàn)?，則可，則可用映射符號(hào)用映射符號(hào) 簡(jiǎn)便地表示為簡(jiǎn)便地表示為 。為了討論不動(dòng)。為了討論不動(dòng)點(diǎn)迭代法（點(diǎn)迭代法（6.4.3）的收斂性，先定義向量值函數(shù)的映內(nèi)性）的收斂性，先定義向量值函數(shù)的映內(nèi)性和壓縮性。和壓縮性。)(xnR

6、DnnRRD:第六章非線性方程組的迭代解法 定義定義6.3 設(shè)有函數(shù)設(shè)有函數(shù) 若若 則稱則稱 在在D D上是映內(nèi)的，記做上是映內(nèi)的，記做 ，又若存在常數(shù)，又若存在常數(shù) ，使得，使得nnRRD:DxDx,)()(xDD )()1 ,0(LDyxyxLyx,)()(則稱則稱 在在D上是壓縮的，上是壓縮的，L稱為壓縮系數(shù)稱為壓縮系數(shù))(x 壓縮性與所用的向量范數(shù)有關(guān)，函數(shù)壓縮性與所用的向量范數(shù)有關(guān)，函數(shù) 對(duì)某種范數(shù)是壓對(duì)某種范數(shù)是壓縮的，對(duì)另一種范數(shù)可能不是壓縮的?？s的，對(duì)另一種范數(shù)可能不是壓縮的。)(x定理定理6.7（Brouwer不動(dòng)點(diǎn)定理不動(dòng)點(diǎn)定理）若）若 在有界凸集在有界凸集 上連上連續(xù)并且

7、映內(nèi)，則續(xù)并且映內(nèi)，則 在內(nèi)在內(nèi) 存在不動(dòng)點(diǎn)。存在不動(dòng)點(diǎn)。DD 00D定理定理6.8（壓縮映射定理壓縮映射定理）設(shè)函數(shù)）設(shè)函數(shù) 在閉集在閉集 上是映內(nèi)的，并且對(duì)某一種范數(shù)是壓縮的，壓縮系數(shù)上是映內(nèi)的，并且對(duì)某一種范數(shù)是壓縮的，壓縮系數(shù)為為L(zhǎng)，則，則（1） 在在 上存在唯一的不動(dòng)點(diǎn)上存在唯一的不動(dòng)點(diǎn) 。 （2）對(duì)任何初值）對(duì)任何初值 迭代法（迭代法（6.4.3）生成的序列）生成的序列 且收斂到且收斂到 ，并且有誤差估計(jì)式，并且有誤差估計(jì)式nnRRD:DD 0)(x0D*x0)0(Dx0)(Dxk*x第六章非線性方程組的迭代解法 )1()(*)(1kkkxxLLxx例例6.12 對(duì)于例對(duì)于例6.1

8、1，設(shè)，設(shè) 試證：對(duì)任何初始點(diǎn)試證：對(duì)任何初始點(diǎn) ，由迭代法（，由迭代法（6.4.5）生成的序列的都）生成的序列的都收斂到方程（收斂到方程（6,4.4）在）在 中的唯一解中的唯一解 5.1,5.1:),(21210 xxxxDT0)0(Dx0DTx) 1 , 1 (*0D證：首先容易算出，對(duì)于任何證：首先容易算出，對(duì)于任何 ，都有，都有 因此，迭代函數(shù)因此，迭代函數(shù) 在在 上是映內(nèi)的。進(jìn)而，對(duì)于任何上是映內(nèi)的。進(jìn)而，對(duì)于任何都有都有021),(DxxxT25. 1),(8 . 0211xx2875. 1),(3125. 0212xx021),(DxxxT021),(DyyyT)()(101)(

9、)(2222111111yxyxyxyxyx122113.0)(103yxyxyx第六章非線性方程組的迭代解法 2222211122101)()(yyxxyxyx22122122122111101yyxyxyxxyx)()(1 (101222211122yxyxyyxx)5 . 425. 3(1012211yxyx145. 0yx 從而從而)()()()()()(22211yxyxyxyx 75. 0 可見，函數(shù)可見，函數(shù) 在上在上 是壓縮的。因此，由定理是壓縮的。因此，由定理6.8得知得知結(jié)論成立。結(jié)論成立。 0D 以上討論了迭代法在以上討論了迭代法在 的收斂性，下面討論局部收斂的收斂性，下

10、面討論局部收斂性。性。0D第六章非線性方程組的迭代解法 定義定義6.4 設(shè)設(shè) 為為 的不動(dòng)點(diǎn)，若存在的不動(dòng)點(diǎn)，若存在 的一個(gè)領(lǐng)域的一個(gè)領(lǐng)域 ，對(duì)一切，對(duì)一切 ， 由（由（6.4.3）式產(chǎn)生的序列）式產(chǎn)生的序列 且且 ，則稱，則稱 具有局部收斂性。具有局部收斂性。*x*xDS Sx)0(Sxk)(*)(limxxkk)(kx則則 稱為稱為p階收斂階收斂 。定義定義6.5 設(shè)設(shè) 收斂于收斂于 ，存在常數(shù)，存在常數(shù) 及常數(shù)及常數(shù)c0,使使 )(kx*x2pcxxxxkkk*)(*)1(lim)(kx定理定理6.9 設(shè)設(shè) ， 為為 的不動(dòng)點(diǎn)，若存在開的不動(dòng)點(diǎn)，若存在開球球 ，常數(shù)，常數(shù) ，使，使則由則

11、由(6.4.3)產(chǎn)生的序列產(chǎn)生的序列 局部收斂至局部收斂至 nnRRD:0*Dx DxxxxSS*:),() 1 , 0(LSxxxLxx,)()(*)(kx*x證：任給證：任給 ，一般的，設(shè)，一般的，設(shè) ，即，即 ，則，則Sx)0(Sxk)(*xx)()(*)(*)1(xxxxkkLxxLk*)(第六章非線性方程組的迭代解法 得知得知 ，從而有，從而有 。于是，由定義。于是，由定義6.4知知迭代法（迭代法（6.4.3）在點(diǎn)）在點(diǎn) 處局部收斂。定理得證。處局部收斂。定理得證。 與單個(gè)方程的情形類似，有時(shí)可以用關(guān)于導(dǎo)數(shù)的條件代替與單個(gè)方程的情形類似，有時(shí)可以用關(guān)于導(dǎo)數(shù)的條件代替壓縮條件來判別收斂

12、性壓縮條件來判別收斂性 0lim*)(xxkk*)(limxxkk*x定理定理6.10 設(shè)設(shè) ， 在在D內(nèi)有一不動(dòng)點(diǎn)內(nèi)有一不動(dòng)點(diǎn) ，且，且 在在 處處可導(dǎo)，且譜半徑可導(dǎo)，且譜半徑 ，則迭代法（，則迭代法（6.4.3）在點(diǎn)）在點(diǎn) 處處局部收斂，其中，函數(shù)局部收斂，其中，函數(shù) 的導(dǎo)數(shù)為的導(dǎo)數(shù)為Jacobi矩陣（見矩陣（見*式）式）利用譜半徑與范數(shù)的關(guān)系利用譜半徑與范數(shù)的關(guān)系 ，我們可用，我們可用 代替定理代替定理6.10中的條件中的條件nnRRD:*x*x1)( (*x*x)(xAA )( 1* x1)( (* x第六章非線性方程組的迭代解法 nnnnnnTnTTxxxxxxxxxxxxxxxxx

13、xxxxx21222121211121)()()()()()()()( （*）例如，對(duì)于例例如，對(duì)于例6.11有有對(duì)于例對(duì)于例6 .12所取的區(qū)域所取的區(qū)域 的不動(dòng)點(diǎn)的不動(dòng)點(diǎn) 在它的內(nèi)部。容易驗(yàn)在它的內(nèi)部。容易驗(yàn) 證，在證，在 上有上有 ，因此，迭代法（，因此，迭代法（6.4.5）在點(diǎn)）在點(diǎn) 處處局部收斂。局部收斂。2122212212101)( xxxxxx,0D*x0D 75. 0* x*x第六章非線性方程組的迭代解法 對(duì)于非線性方程組，也可以構(gòu)造類似于一元方程的對(duì)于非線性方程組，也可以構(gòu)造類似于一元方程的Newton迭代迭代法。設(shè)法。設(shè) 是方程組（是方程組（6.4.1）的解，）的解， 是

14、方程組的一個(gè)近似解。是方程組的一個(gè)近似解。用點(diǎn)用點(diǎn) 處的一階處的一階Taylaor展開式近似每一個(gè)分量函數(shù)值展開式近似每一個(gè)分量函數(shù)值 ，有有*x)(kx)(kx0)(* xfi njkjjjkikiinixxxxfxfxf1)(*)()(*, 2 , 1),()()()(其中其中 為為 的的Jacobi矩陣矩陣 在的在的 值，而值，而寫成向量形式有寫成向量形式有)( )()()(*)()(*kjkkxxxFxFxF )( )(kxF)(xF)( xF)(kx6.4.2 非線性方程組的非線性方程組的Newton法法第六章非線性方程組的迭代解法 nnnnnnTnTTxxfxxfxxfxxfxxf

15、xxfxxfxxfxxfxfxfxfxF21222121211121)()()()()()()()( 若矩陣若矩陣 非奇異，則可以用使（非奇異，則可以用使（6.4.6）右端為零的向量作）右端為零的向量作為為 新的一個(gè)近似值，記為新的一個(gè)近似值，記為 ，于是得到，于是得到Newton迭代法迭代法)( )(kxF*x)1( kx, 2 , 0),()( (1)()1(kxFxFxxkk（6.4.7)0(x)()(1kkxx其中其中 是給定的初值向量。如果寫成一般不動(dòng)點(diǎn)迭代是給定的初值向量。如果寫成一般不動(dòng)點(diǎn)迭代 的形式，則的形式，則Newton迭代函數(shù)為迭代函數(shù)為 )()( ()(1xFxFxx(

16、6.4.8)第六章非線性方程組的迭代解法 在在Newton法實(shí)際計(jì)算過程中，第法實(shí)際計(jì)算過程中，第k步是先解線性方程組步是先解線性方程組解出解出 后，再令后，再令 ，其中包括了計(jì)算向量，其中包括了計(jì)算向量 和矩陣和矩陣 )()( )()()(kkkxFxxF(6.4.9)(kxkkkxxx )1()()(kxF)( )(kxF例例6.13 用用Newton法解例法解例6.11的方程組（的方程組（6.4.4）解解 對(duì)該方程組有對(duì)該方程組有取初始向量取初始向量 ，解方程組，解方程組 ，即，即810810)(2122122121xxxxxxxxF10212102)(212221xxxxxxFTx)0

17、 , 0()0()()( )0()0()0(xFxxF88101010)0(x第六章非線性方程組的迭代解法 求出求出 后，后， 。同理計(jì)算。同理計(jì)算 結(jié)果結(jié)果列于表列于表610。可見，?？梢姡琋ewton法的收斂速度比例法的收斂速度比例6.11中的迭代中的迭代法（法（6.4.5）要快的多。）要快的多。)0(xTxxx)88. 0 , 8 . 0()0()0()1(,)2(x表表 6-10kx2kx1k01 2 3 400.800.9917872210.9999752291.0000000000.880.9917117370.9999685241.00000000關(guān)于關(guān)于Newton法的收斂性，

18、有下面的局部收斂性定理法的收斂性，有下面的局部收斂性定理第六章非線性方程組的迭代解法 定理定理6.11 設(shè)設(shè) ， 滿足滿足 。若有。若有 的開鄰的開鄰域域 ， 在其上連續(xù)，在其上連續(xù)， 可逆，則可逆，則nnRRDF:*x0)(*xF*xDS 0)( xF)( *xF (2)Newton迭代序列迭代序列 在在S上收斂于上收斂于 ，且是超線性收斂，且是超線性收斂 。)(kx*x(1) (1) 存在以存在以 為中心，為中心， 為半徑的閉球?yàn)榘霃降拈]球 , ,使使 （6.4.8）式中的）式中的 對(duì)所有對(duì)所有 都有意義，并且都有意義，并且 。*x00*),(SxSS)(xSxSx )(0（3）若還有常數(shù)

19、若還有常數(shù) ，使，使 則則Newton迭代序列迭代序列 至少二階收斂于至少二階收斂于 。 SxxxxFxF,)( )( *)(kx*x 雖然雖然Newton法具有二階局部收斂性，但它要求法具有二階局部收斂性，但它要求 非奇非奇異。如果矩陣異。如果矩陣 奇異或病態(tài)，那么奇異或病態(tài)，那么 也可能奇異或病也可能奇異或病態(tài)，從而可能導(dǎo)致數(shù)值計(jì)算失敗或產(chǎn)生數(shù)值步穩(wěn)定。這時(shí)可采態(tài)，從而可能導(dǎo)致數(shù)值計(jì)算失敗或產(chǎn)生數(shù)值步穩(wěn)定。這時(shí)可采用用“阻尼阻尼Newton法法”，即把（，即把（6.4.9）改成）改成)( *xF)( *xF)( )(kxF第六章非線性方程組的迭代解法 其中的參數(shù)其中的參數(shù) 稱為阻尼因子，稱

20、為阻尼因子， 稱為阻尼項(xiàng)，解出稱為阻尼項(xiàng)，解出 后，后，令令 。加進(jìn)阻尼項(xiàng)的目的，是使線性方程的系數(shù)矩。加進(jìn)阻尼項(xiàng)的目的，是使線性方程的系數(shù)矩陣非奇異并良態(tài)。當(dāng)陣非奇異并良態(tài)。當(dāng) 選的很合適時(shí)，阻尼選的很合適時(shí)，阻尼Newton法時(shí)線性法時(shí)線性收斂的。收斂的。kIk)(kx)()()1(kkkxxxk例例614 用用Newton法和阻尼法和阻尼Newton法求解方程法求解方程 ，其，其中中0)(xF2102310)(2122122121xxxxxxxxF解：易知該方程有一個(gè)解是解：易知該方程有一個(gè)解是 。由于。由于 Tx) 1 , 4(*, 1 , 0),()( )()()(kxFxIxFkk

21、kk第六章非線性方程組的迭代解法 2222)( *xF，），（法有按）（TxNewton438461538.1538461538.31Tkx)5 .2,5 .2(.10)0(5若取是奇異的，取阻尼因子。，Tx)000000025.1 ,000000025.4()25(,)438461083.1 ,538463160.3()1(TxNewton法計(jì)算有在按阻尼。Tx)000000286.1,000000286.4(,)29(定性問題，沒有出現(xiàn)奇異或數(shù)值穩(wěn)法仍非奇異，奇異，只要可見，即使矩陣NewtonxFxFk)( )( )(*法并小，。因?yàn)榇卫}的維數(shù)太收斂，但收斂是線形的Newton第六章非

22、線性方程組的迭代解法 作用，反而使迭代法不僅沒有顯示出它的從而阻尼 Newton法是線形收斂的。，阻尼次數(shù)更多。但可以看出Newton初值關(guān)重要。程時(shí)，初始值的選取至用迭代法求解非線形方斂到不同的解。同的初值可能收，而當(dāng)方程有解時(shí)，不不僅影響迭代是否收斂。1)5 .0()2(1)(2221221xxxxxF15.6例其中法求解用,0)(xFNewton21221)201xxx與圓（物線該方程組的實(shí)數(shù)解是拋解,)0000. 1,0625. 1 (,)0 , 0()1()0(KTTxx那么有如果取初時(shí)向量。和TTx)391176313. 1,546342883. 1 ()139227667. 0,

23、067346086. 1 (*2201)5 . 0(xx的交點(diǎn)。這兩個(gè)實(shí)根是第六章非線性方程組的迭代解法 。計(jì)算結(jié)果收斂到*)5(,)391176313. 1 ,546342883. 1 (,xxT。計(jì)算結(jié)果收斂到*)5(,)139221092.0 ,067343609.1 (xxT,)583333333. 1 ,645833333. 1 (,)2 , 2()1()0(TTxx則有若取初值)10.4 .6(, 1 ,0),()(1)()1(。kxFAxxkkkk迭代公式是法的代替我們用較簡(jiǎn)單的矩陣),( )(kkxFNewtonA是困難的。所以，比較復(fù)雜時(shí)，求導(dǎo)數(shù)值的分量函數(shù)特別是當(dāng))()(x

24、fxFi是不方便的，是每步都要計(jì)算法有較好的收斂性，但)( )(kxFNewton當(dāng)取在所代的收斂性，初始值應(yīng)一般說來，為了保證迭。這是個(gè)相當(dāng)困難的問題學(xué)的角度講，預(yù)估一個(gè)近似解。從數(shù)有的則可以用某些方法經(jīng)驗(yàn)取初值，。有的實(shí)際問題可以憑求解的足夠小的鄰域內(nèi)6.4.3非線性方程組的非線性方程組的Newton法法第六章非線性方程組的迭代解法 )11.4 .6()()()()()1()()1(1kkkkkxFxFxxA11()kkAfx下 一 步 是 要 確 定。 若 是 單 個(gè) 方 程 ， 割 線 中可 用 差 商于是取具有性質(zhì)是向量，代替。方程組的情形，)()1(11)/()()(kkkkkkx

25、xxxxfxf方法。時(shí)，稱為秩方法。為秩221m法，）稱為擬的迭代法（為增量矩陣，由此得到稱NewtonAk10.4 .6時(shí)，稱。當(dāng)或方程。通常?。┓Q為擬（12111.4.6mmmNewton)12.4 .6(1)(,1。mArankAAAkkkk已知和。在多元情形下，當(dāng)法中的代替的矩陣)1()()1(1)( kkkkxxxFNewtonA一個(gè)可行的途徑是令，需要附加其他條件。因此，為了確定矩陣1kA個(gè)未知量）。個(gè)方程中含有）不能確定矩陣時(shí)，由方程（nnnAk211(11.4.6第六章非線性方程組的迭代解法 。（），即（kkTkkysvuAk)11. 4 . 6方程滿足擬，使得矩陣和選擇New

26、tonAAAvukkkkk1。)()(,)()1()()1(kkkkkkxFxFyxxs的方法。增量矩陣的情形為例，說明確定下面一秩kA1為列向量。記nTkkTkkkRvuvuAAk,1其中總可以表示為的矩陣秩為，則由此可解出若0kTksv有代入和述kkkAuv。把上時(shí)總有即迭代尚未終止），這0(22)()1(kkTkkkssvxx因?yàn)橹灰囊粋€(gè)自然取法是令唯一確定。向量由即,kkkkksvvvu，)(1kkkkTksAysvuk第六章非線性方程組的迭代解法 。TkkkkkkssAysA)(122）（。13. 4 . 6, 1 , 0,)(1),()(,),(221)()1(1)(1)()1(kssAysAAxFxFyxxsxFAxxTkkkkkkkkkkkkkkkkk的迭代法于是得到求解方程0)(xF做矩陣運(yùn)算即可證明。引理的結(jié)論只要直接降為運(yùn)算量可將解方程組的直接法)()(23nOnO）中的矩陣求逆，從而避免方法（利用下面的引理，可以13. 4 . 6)( 1)0(0)0(xFAxBtoyden可取為給定，方法，其中的初始值秩稱之為或單位矩陣。第六章非線性方程組的迭代解法 ）（。（14. 4 . 61)11111uAvAuvAAuvATTT非奇異的則非奇異，若矩陣引理TT