第2章 非線性方程與方程組的數(shù)值解法

1、第2章非線性方程與方程組的數(shù)值解法 本章重點(diǎn)介紹求解非線性方程 的幾種常見和有效的數(shù)值方法,同時(shí)也對(duì)非線性方程組 求解,簡(jiǎn)單介紹一些最基本的解法.無論在理論上,還是在實(shí)際應(yīng)用中,這些數(shù)值解法都是對(duì)經(jīng)典的解析方法的突破性開拓和補(bǔ)充,許多問題的求解,在解析方法無能為力時(shí),數(shù)值方法則可以借助于計(jì)算機(jī)出色完成.0)(xf), 2 , 1(0),(21nixxxfni2.1二分法求非線性方程0)(xf 確定方程的有根區(qū)間 計(jì)算根的近似值的根的方法分為兩步： 首先確定有限區(qū)間：依據(jù)零點(diǎn)定理。 設(shè) ，且 ，則方程 在區(qū)間 上至少有一個(gè)根。如果 在 上恒正或恒負(fù)，則此根唯一。,)(baCxf0)()(bfaf

2、0)(xf),(ba)(xf),(ba等步長掃描法求有根區(qū)間 用計(jì)算機(jī)求有根區(qū)間：等步長掃描法。 設(shè)h0是給定的步長，取 ，若 則掃描成功；否則令 ，繼續(xù)上述方法，直到成功。如果 則掃描失敗。再將h 縮小，繼續(xù)以上步驟。haxax10,0)()(10 xfxfhxxxx0110,bx 1等步長掃描算法 算法：（求方程 的有根區(qū)間）(1) 輸入 ；(2) ； (3) ，若 輸出失敗信息，停機(jī)。(4)若 。輸出 ，已算出方程的一個(gè)根，停機(jī)。0)(xfhba,)(0aff )(,1xffhaxbx 01fx等步長掃描算法(5) 若 。輸出 為有根區(qū)間，停機(jī)(6) ，轉(zhuǎn) 3）注：如果對(duì)足夠小的步長h掃

3、描失敗。說明：在 內(nèi)無根在 內(nèi)有偶重根010ff, ,xaxaxa ,ba,ba二分法 用二分法(將區(qū)間對(duì)平分)求解。 令 若 ，則 為有根區(qū)間，否則 為有根區(qū)間 記新的有根區(qū)間為 ， 則 且 )(,1121111bacbbaa0)()(11cfaf,11ca,11bc,22ba,2211baba)(112122abab二分法對(duì) 重復(fù)上述做法得且 ,22ba.,.,2211nnbababa)(211ababnnn二分法 設(shè) 所求的根為 ， 則 即 取 為 的近似解 x.2 , 1,nbaxnn.2 , 1nbxann0)(21lim)(lim1nababnnnnxbannnnlimlim)(2

4、1nnnbacxx求方程f(x)=0的根的二分法算法).(21)4(;endwhile.,;,0)()()2);(),(21)1|)3(;3,10)()()2(;,:)1 (baxbxbaelsexabathenxfafifxfbaxbawhileelsebathenbfafifbaba輸出計(jì)算令時(shí)做步轉(zhuǎn)第值輸入重新步返回第值及精度控制量的有根區(qū)間輸入求方程f(x)=0的全部實(shí)根的二分法算法);();(211|while)2endwhile;0)()(while) 1while) 3(;)2(;,:) 1 (11011111111111xfbaxabhabaabfafbbhabaahba計(jì)算時(shí)

5、做做時(shí)做輸入求方程f(x)=0的全部實(shí)根的二分法算法;endwhile;10;:)3;endwhile.,0)()(if3);3(0)(if2111111111100habhxaxbxbaelsexabathenxfafxf輸出轉(zhuǎn)例題例1 設(shè)方程 解：取h=0.1,掃描得： 又 即 在 有唯一根。 2 , 1 , , 1)(3baxxxf0344. 0)4 . 1 (061. 0)3 . 1 (ff.4 . 1 , 3 . 1 方程的有根區(qū)間為4 . 1 , 3 . 1 , 013)(2xxxf0)(xf4 . 1 , 3 . 1 2.2一般迭代法2.2.1 迭代法及收斂性 對(duì)于 有時(shí)可以寫成

6、 形式 如： 0)(xf)(xx3331101xxxxxxxxxxcos0cos迭代法及收斂性 考察方程 。這種方程是隱式方程，因而不能直接求出它的根，但如果給出根的某個(gè)猜測(cè)值 ， 代入 中的右端得到 ，再以 為一個(gè)猜測(cè)值，代入 的右端得 反復(fù)迭代得)(xx0 x)(xx)(01xx1x)(xx)(12xx,.1 , 0)(k1kkxx迭代法及收斂性 若 收斂，即 則得 是 的一個(gè)根kx xxkklimx)(xx)()lim()(limlim1nxxxxxnnnnn迭代法的幾何意義 交點(diǎn)的橫坐標(biāo) *x)()(xyxyxxy=x2x0 x1x簡(jiǎn)單迭代法 將 變?yōu)榱硪环N等價(jià)式 。選取 的某一近似值

7、 ，則按遞推關(guān)系 產(chǎn)生的迭代序列 。這種方法算為簡(jiǎn)單迭代法。0)(xf)(xxx,0bax ,.1 , 0)(k1kkxxkx例題 例2 試用迭代法求方程 在區(qū)間(1，2)內(nèi)的實(shí)根。 解：由 建立迭代關(guān)系 k=10,1,2,3.計(jì)算結(jié)果如下:31xx01)(3xxxf311kkxx例題精確到小數(shù)點(diǎn)后五位5102132472. 1x例題但如果由 建立迭代公式 仍取 ，則有 ， 顯然結(jié)果越來越大， 是發(fā)散序列。1x3x,.2 , 1131kxxkk 5 . 10 x 2.3751x 12.392x kx迭代法的收斂性定理（壓縮映像原理）設(shè)迭代函數(shù) 在閉區(qū)間 上滿足（1）（2） 滿足Lipschit

8、z條件即 有且 。 )(x ,ba,)(,baxbax)(x,21baxx )()(2121xxLxx10 L壓縮映像原理則 在 上存在 唯一解 ，且對(duì) ，由 產(chǎn)生的序列 收斂于 。 )(xx,0bax )(k1kxx.1kxx,bax壓縮映像原理證明：不失一般性,不妨設(shè) 否則 為方程的根。首先證明根的存在性 令 bbaa)(,)(ba或xxx)()(壓縮映像原理 則 ， 即 由條件2） 是 上的連續(xù)函數(shù) 是 上的連續(xù)函數(shù)。故由零點(diǎn)定理 在 上至少有一根0)()(aaa0)(b0)()(ba)(x,ba)(x所以,ba0)(x,ba),(bax 壓縮映像原理再證根的唯一性 設(shè)有 均為方程的根

9、則 因?yàn)?0L1 ，所以只可能 ， 即根是唯一的。,21baxx| )()(|212121xxLxxxx21xx壓縮映像原理最后證迭代序列的收斂性 與n 無關(guān)，而0L1 即| )()(|1xxxxnn由于|1xxLn|0 xxLn.xx ,0因?yàn)?lim|lim0nnnnLxxxx所以 xxnnlim壓縮映像原理誤差估計(jì) 若 滿足定理?xiàng)l件，則 這是事后估計(jì)，也就是停機(jī)標(biāo)準(zhǔn)。L越小，收斂速度越快。 這是事前估計(jì)。選取n，預(yù)先估計(jì)迭代次數(shù)。 )(xx|L1L|1nnxxxxn|L1L|01nxxxxn 對(duì)于方程 構(gòu)造的多種迭代格式 ，怎樣判斷構(gòu)造的迭代格式是否收斂？收斂是否與迭代的初值有關(guān)？根據(jù)數(shù)

10、學(xué)知識(shí)，我們可以直接利用以下收斂條件：（1） 當(dāng) 有（2） 在a,b上可導(dǎo)，并且存在正數(shù)L1時(shí)，稱為超線性收斂；當(dāng)p=2時(shí)，稱為平方收斂或二次收斂。迭代法收斂的階迭代法收斂的階定理定理 設(shè) 是方程 的不動(dòng)點(diǎn)， 若為足夠小的正數(shù) 。如果 且 ，則從任意 出發(fā)，由 產(chǎn)生的序列 收斂到 ，當(dāng) 時(shí)斂速是線性的。 *x)(xx,*xxCx)(1| )(|* x0 x)(1kkxx0nx*x0)( x 迭代法收斂的階迭代法收斂的階證明：滿足壓縮映像原理知，及由Cxx)(1|)(|*足夠小時(shí)，有)(1| )(|xLx|)(| )()(|)(|*xxxxxxxxx有因此，對(duì)于迭代法收斂的階迭代法收斂的階 斂速

11、是線性的 線性收斂到 。0)()()(limlim*1nxxxxxeennnnn因?yàn)椤Ｊ諗康焦?0 xxn滿足壓縮映像原理，所以即)(,)(xx0nx所以*xSteffensen迭代格式由線性收斂知 當(dāng)n充分大時(shí)有 即0limlim112nCeeeennnnnnnnneeee112*1*1*2xxxxxxxxnnnnSteffensen迭代格式展開有：nnnnnnxxxxxxx1221*2)(2*121*2)(2)(xxxxxxxxnnnn2*1212*2*2)(2)(xxxxxxxxxxxnnnnnn*121*2*22xxxxxxxxxnnnnnn21212*)2(nnnnnnxxxxxxx

12、Steffensen迭代格式已知 ，則 ，改成nx)(1nnxx)(2nnxx nnnnnnnnnnnxyzxyxxyzxy2)()()(21 n=0，1，2，Steffensen迭代格式也可以改寫成其中迭代函數(shù),.)1 , 0()(1nxxnnxxxxxxx)(2)()()(2Steffensen迭代法收斂的充要條件定理 ,)(*1xxCx，設(shè)函數(shù)。件是的不動(dòng)點(diǎn)的充分必要條是)()(*xxxxx，則為足夠小的正數(shù)，且1)(* xSteffensen迭代法收斂的充要條件證明：必要性的不動(dòng)點(diǎn)，是因?yàn)?(*xxx)(2)()()(2xxxxxxx由于，所以0)(lim*xxxx，故有0)(lim*

13、xxxx)(*xx即的不動(dòng)點(diǎn)。是所以)(*xxxSteffensen迭代法收斂的充要條件充分性的不動(dòng)點(diǎn)有是由)(*xxxxxxxxxxxxxx)(2)()(lim)(lim2*1)(2)()( 1)()( 2lim*xxxxxxxxoo型0 1)( 1)()( 2lim2*xxxxxx的不動(dòng)點(diǎn)。是所以)(*xxxSteffensen算法的收斂速度 !)()(lim)(0)(0)(.)()(,),1()(,)(*)(*1*010*)1(*)1(*pxxxxxxpxxxxxxxxxxpCxxxxppnnnnkkppp ，且階收斂速度收斂到，以列產(chǎn)生的序，由，則而如果為足夠小的正數(shù)的不動(dòng)點(diǎn)是設(shè)定理S

14、teffensen算法的收斂速度定理 在定理2.2.3假設(shè)下，若 產(chǎn)生的序列 至少平方收斂到 。,.2, 1 ,02)()()(21nxyzxyxxyzxySteffensennnnnnnnnnnn迭代格式則由 2C)(x0nx*x*xSteffensen算法的收斂速度的不動(dòng)點(diǎn)，是證明：)(*xxx。即)(*xx1)(11)(lim)(lim*xxxxxxxxooxx型又因?yàn)镾teffensen算法的收斂速度 *)(2)(lim*xxxxxxx及) 1)(2)()(lim*xxxxxoo型1)(2)()(*xxx2* 1)(xSteffensen算法的收斂速度 *)()(lim)(*xxxxx

15、xx于是有*2)(2)()(lim*xxxxxxxxxxx*2*)(2)()(lim1*xxxxxxxxxxx0 1)( 1)(12*2*xxSteffensen算法的收斂速度 由定理知 至少以平方速度收斂到 。 也就是說：簡(jiǎn)單迭代法是線性收斂；Steffensen迭代至少平方以上收斂（加速收斂）。0nx*x例題例試用Steffensen算法求解方程解法一、取 ，由013 xx31)(xxnnnnnnnnnnnxyzxyxxyzxy2)()()(21 n = 0，1，2，例題取初值 ，計(jì)算結(jié)果如下：5 . 10 xN XnYnZn0 1.51.3572088081.3308609591 1.3

16、248991811.3247523791.3247244962 1.3247179571.3247179571.324717957例題解法二、取 ，由對(duì)于該迭代函數(shù)在一般迭代法中是發(fā)散的，而Steffensen格式卻是收斂的。1)(3 xxnnnnnnnnnnnxyzxyxxyzxy2)()()(21 n=0，1，2，例題取初值 ，計(jì)算結(jié)果如下：N XnYnZn0 1.52.3751.2396484371 1.4162929751.8409219155.2388727692 1.3556504421.4913982792.3172706993 1.3289487771.3470628831.4

17、443512244 1.3248044891.3251735441.3271172815 1.3247179441.3247181521.3247189806 1.3247179575 . 10 xSteffensen迭代格式幾何解釋 Steffensen迭代算法 11002001200100210:)3(;)4);2/()()3;3|2|)2);();() 1| )(|while)2(;,) 1 (xendwhilexxxyzxyxxthenxyzifyzxyxxx輸出步做第做輸入Steffensen迭代算法 為松弛因子n 時(shí)，為直接迭代；n 時(shí)，迭代步長加大，加速迭代；n 時(shí)，迭代步長減小

18、，適合迭代發(fā)散；n 時(shí)，迭代反方向進(jìn)行。 松弛迭代法松弛迭代法通過選擇合適的松弛因子,就可以使迭代過程收斂。松弛法的迭代公式如下：)(1nnnkxxxx (2-7) 11100 松弛迭代法松弛迭代法 實(shí)例實(shí)例例 用（松弛）迭代法求解下面非線性方程組，并分析松弛因子對(duì)迭代次數(shù)及收斂過程的影響。已知迭代初值x和y均為0，收斂精度=0.001 。0201. 01 . 0011 . 002. 03222yyxyxxn解：取以下迭代表達(dá)式：)01. 01 . 02()1 . 002. 01 (321221nnnnnnnnnnyyxyyxyxxx若取松弛因子為1.1，則其迭代過程如表2-2。迭 代 次 數(shù)

19、 x y 0 0.0000 0.0000 1 1.1000 2.2000 1.4142 2 1.5490 2.2302 0.2902 3 1.5450 2.3629 0.0562 4 1.6122 2.3714 0.0418 5 1.6146 2.3955 0.0101 6 1.6271 2.3984 0.0078 7 1.6283 2.4031 0.0021 8 1.6308 2.4040 0.0016 9 1.6311 2.4050 0.0005 n若改變松弛因子,迭代過程及迭代所需的次數(shù)亦將發(fā)生變化，詳見表2-3。松弛因子 迭代次數(shù) 0.5 21 0.8 13 1 10 1.1 9 1.

20、2 11 1.3 17 1.4 29 1.5 81 1.55 454 1.56 發(fā)散 表2-2 迭代過程表2-3 松弛因子及迭代次數(shù)的變化，則為直接迭代法12.3 Newton迭代法設(shè)x * 是方程f (x ) = 0的根，又x0 為x * 附近的一個(gè)值 ，將f (x ) 在x0附近做泰勒展式 令 ，則 之間和在其中020000)()(21)()()()(xxfxxxfxxxfxf *xx )()(21)()()()(020*00*0*fxxxfxxxfxf Newton迭代法去掉 的二次項(xiàng)，有：即以x1代替x0重復(fù)以上的過程，繼續(xù)下去得：0*xx 0)()()(000*0 xfxxfxxf)

21、()(0001*xfxfxxxNewton迭代法,.1 , 0)()(1nxfxfxxnnnn以此產(chǎn)生的序列Xn得到f(x)=0的近似解，稱為Newton法，又叫切線法。Newton迭代法幾何解釋幾何意義例題例2.3.1 用Newton法求 的近似解。解：由零點(diǎn)定理。0cos)(xxxf內(nèi)有根。在)2, 0(0cosxx迭代公式得及由Newtonxxfsin1)(,.1 , 0sin1cos1nxxxxxnnnnn例題085133739. 0739085133. 0739085133. 0739085178. 0;73936133. 044*43210 xxxxxxx故取得取例題例2.3.2

22、用Newton法計(jì)算 。解：220)(2aaxxf其中迭代公式得及由Newtonxxf2)(,.1 , 0)2(212221nxxxxxxnnnnnn。有十位有效數(shù)的近似值是已的精確值相比，。與，則取332102414213562. 1414215686. 11.416666675 . 1xxxxxNewton迭代法算法框圖Newton迭代法算法。輸出）轉(zhuǎn)（做輸入1101001001000:)4(;2) 3;)2;/) 1|while(3);();()2(;,) 1 (xendwhilexxffxxfxffxffxNewton迭代法收斂性定理2.3.1 設(shè)函數(shù) ，且滿足 若初值 滿足 時(shí)，由N

23、ewton法產(chǎn)生的序列收斂到 在a,b上的唯一根。,)(2baCxf上恒正或恒負(fù)。在,)() 3);,( , 0)()2; 0)()() 1baxfbaxxfbfaf ,0bax 0)()(00 xfxf0)(xfNewton迭代法收斂性證明： 根的存在性根的唯一性內(nèi)至少有一個(gè)根。在知）及由條件（),(0)(,)(1baxfbaCxf。記此根為內(nèi)有唯一根在上嚴(yán)格單調(diào)函數(shù)，因此是故保號(hào)，知及由*,),(0)(,)()(,bCa,)(, 0)(xbaxfbaxfxfxfxfNewton迭代法收斂性收斂性)()(0)()(0)(, 0)(, 0)(,0)()(0)(, 0)(, 0)(, 0)(01

24、0000001000*000 xxxfxfxxfxfxxxfxfxfbxxxfxfxfxfbfaf 即有，所以知，由，不妨設(shè)Newton迭代法收斂性 繼續(xù)上述推理有代替。再以因此有兩式相減展式由另一方面0101*20*01*20*0*00*0)()()(21)(21)()()(0 Taylor,xxxxxxxxffxxxxfxxxfxfxf Newton迭代法收斂性。，由根的唯一性知可得時(shí)當(dāng)由。故必有極限，記。是單調(diào)減有下界的序列故序列*10011*0)(,.2 , 1)()(lim.xaafnnxfxfxxaxxxxxxxnnnnnnnnnNewton迭代法收斂性推論 在定理2.3.1條件下

25、， Newton迭代法具有平方收斂速度。故結(jié)論成立。之間，則與介于其中，證明，一般有類似定理證明0)()(21lim)()()(211 . 3 . 2* 21*2*1n* xfxfeexxxxxffxxnnnnnnnn代數(shù)方程的Newton迭代法代數(shù)方程的Newton迭代法推導(dǎo)設(shè)n次代數(shù)方程用Newton迭代法求有限區(qū)間的實(shí)根，則要計(jì)算 ，一般采用秦九韶算法。,.2 , 1)()(1nxfxfxxnnnn)0(0)(0110 aaxaxaxfnnn)(),(nnxfxf代數(shù)方程的Newton迭代法由Taylor展式)2(!)()(.! 2)()()()( ) 1 ()()()(!)()(.!

26、2)()()()()()()(1)(2nxfxxxfxxxfxQxQxxxfnxfxxxfxxxfxxxfxfnnnnnnnnnnnnnnnnnn 其中代數(shù)方程的Newton迭代法 )3()()()()(),()()2(12110 nnnnnnnbxbxbxQxQxxxfxfxQ的余式，令除以為且式知，由);()(1)() 1 (nnxfxQnxfxx，余式為次多項(xiàng)式為，得商）去除式表示，用（ nnnnnnnnnaxaxaxabxbxbxxxfxf 111012110.)()()(1)3(）式得式代入（),.,2 , 1()(100nkxxfbbababxnnnkkk的同次冪系數(shù)得比較等式兩邊

27、代數(shù)方程的Newton迭代法同理 )()()()()(xRxxxfxQxQxxnnn有取除以用)4()(23120 nnncxcxcxR令12211023120.)()()() 3 () 4( nnnnnnnnnbxbxbxbcxcxcxxxfxQ式得式代入代數(shù)方程的Newton迭代法比較x的同次冪系數(shù)得：故代數(shù)方程的Newton迭代公式) 1,.,2 , 1()(1100nkxxfccbcbcnnnkkk,.)2 , 1(11ncbxxnnnn代數(shù)方程的Newton迭代法算法步。返回第停止計(jì)算輸出做對(duì)計(jì)算輸入2)(,;,|(4);)(3;1,.,2 , 1)2;) 1);(),()2(;,)

28、,.,2 , 1 , 0(:) 1 (101*01100101010000100000 xxelsexxthenxxifffxxxfffxfafnkffafxfxfxniaki 2.4弦截法Newton迭代法有一個(gè)較強(qiáng)的要求是 且存在。因此，用弦的斜率 近似的替代 。 0)( xf)(xf )()()()()(,(P)(,(P,)(10101111100010*xxxxxfxfxfyxfxxfxbxaxxbaxf得弦的方程及則過，取上有唯一零點(diǎn)在設(shè)弦截法令y=0,解得弦與x軸的交點(diǎn)是坐標(biāo)x2.,.)2 , 1()()()(.,)()()(0)()()()(0013201010112120101

29、1稱之為定端點(diǎn)弦截法計(jì)算再由解得nxfxfxfxxxxxxxxfxfxfxxxxxxxxxfxfxfnnnnn弦截法.,.)2 , 1()()()(,111321又稱快速弦截法稱之為變端點(diǎn)弦截法以此類推計(jì)算若由nxfxfxfxxxxxxxnnnnnnn弦截法的幾何解釋例題例2.4.1 用快速弦截法求方程在區(qū)間（1，2）內(nèi)的實(shí)根。解：取x0=1,x1=2,代入公式2.4.2計(jì)算結(jié)果,如表2.4.1所示。01)(3xxxfkxkf(xk)01-112521.166666667-0.5787036931.253112023-0.2853630241.3372064440.05388057951.32

30、3850096-0.003698116861.324707936-4.273521*10E-571.3247179653.79*10E-8弦截法收斂定理則其中如果的根是為足夠小的正數(shù)設(shè)定理0| )(|max|,)(|max12,0)(, , ,)(1 . 4 . 21212*2 xfmxfMmMqxfxxxbabaCxfbxabxa弦截法收斂定理。的斂速收斂到以確定的序列由線性收斂到確定的序列由*011*001215,.2 , 1)()()()2(;,.2 , 1)()()() 1 (xpxnxfxfxfxxxxxxnxfxfxfxxxxnnnnnnnnnnnnn求解方程f(x)=0的快速弦截

31、法。輸出停止計(jì)算輸出失敗信息時(shí)做輸入LxNLffffxxxxLLxfffffxxxxfxffxffLNxx,)4(;endwhile,thenif)3;)2; 1);(;) 1|while)3();(),(, 0)2(;,:) 1 (2211021022101011211100102.5 非線性方程組的牛頓方法非線性方程組的牛頓方法設(shè)二階方程組0),(0),(21yxfyxfyxuyxfyxfuF其中,),(),()(21),(),(21yxfyxf，n其中x,y為自變量。為了方便起見，將方程組寫成向量形式：n將 在（x0,y0）附近進(jìn)行二元泰勒展開，并取其線性部分，得到下面方程組：0),()

32、(),()(),(0),()(),()(),(0020002002001000100010yyxfyyxyxfxxyxfyyxfyyxyxfxxyxf2.5 非線性方程組的牛頓方法非線性方程組的牛頓方法令 則有,0000yyyxxx),(),(),(),(),(),(0020020002000100100010yxfyyxfyxyxfxyxfyyxfyxyxfx如果,0| ),(|00),(22110000yxyfxfyfxfyxJyx，解出00000001yyxxyxuu再將原方程組在u1處進(jìn)行二元泰勒展開，并取其線性部分2.5 非線性方程組的牛頓方法非線性方程組的牛頓方法得到下面方程組： ),()(),()(),(),()(),()(),(1121112111211111111111yxfyyyyxfxxxyxfyxfyyyyxfxxxyxf解出,1111yyyxxx11112yyxxukkkkkkkkk