第4章非線性方程求根的迭代法

1、第4章 非線性方程求根的迭代法 本章重點(diǎn)介紹求解非線性方程 的幾種常見和有效的數(shù)值方法.無(wú)論在理論上,還是在實(shí)際應(yīng)用中,這些數(shù)值解法都是對(duì)經(jīng)典的解析方法的突破性開拓和補(bǔ)充,許多問(wèn)題的求解,在解析方法無(wú)能為力時(shí),數(shù)值方法則可以借助于計(jì)算機(jī)出色完成.0)(xfnf(x)=0某個(gè)區(qū)間上可能有奇數(shù)重根或者有偶數(shù)重根，都可以轉(zhuǎn)換為討論單根的情形（具體數(shù)學(xué)細(xì)節(jié)不多加解釋）。所以此節(jié)我們考察單根情形。4.1二分法求非線性方程0)(xf 確定方程的有根區(qū)間 計(jì)算根的近似值的根的方法分為兩步：n首先確定有限區(qū)間：依據(jù)零點(diǎn)定理。 設(shè) ，且 ，則方程 在區(qū)間 上至少有一個(gè)根。如果 在 上恒正或恒負(fù)，則此根唯一。,)

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

3、6) ，轉(zhuǎn) 3）n注：如果對(duì)足夠小的步長(zhǎng)h掃描失敗。說(shuō)明：在 內(nèi)無(wú)根在 內(nèi)有偶重根010ff, ,xaxaxa ,ba,banQustion: 有沒(méi)有更直觀的方法呢？有沒(méi)有更直觀的方法呢？二分法 n用二分法(將區(qū)間對(duì)平分)求解。 令 若 ，則 為有根區(qū)間，否則 為有根區(qū)間 記新的有根區(qū)間為 ， 則 且 )(,1121111bacbbaa0)()(11cfaf,11ca,11bc,22ba,2211baba)(112122abab二分法n對(duì) 重復(fù)上述做法得n且 ,22ba.,.,2211nnbababa)(211ababnnn二分法 設(shè) 所求的根為 ， 則 即 取 為 的近似解 x.2 , 1,

4、nbaxnn.2 , 1nbxann0)(21lim)(lim1nababnnnnxbannnnlimlim)(21nnnbacxxn二分法特點(diǎn)：（1）條件簡(jiǎn)單，只需要滿足連續(xù)性即可。（2）收斂速度慢，精度要求比較高時(shí)，時(shí)間花費(fèi)比較大。例題n例1 設(shè)方程 2 , 1 , , 1)(3baxxxf4.2 基本迭代法n迭代法及收斂性 對(duì)于 有時(shí)可以寫成 形式 如： 0)(xf)(xx3331101xxxxxxxxxxcos0cos迭代法及收斂性 考察方程 。不能直接求出它的根，但如果給出根的某個(gè)猜測(cè)值 ， 代入 中的右端得到 ，再以 為一個(gè)猜測(cè)值，代入 的右端得 反復(fù)迭代得)(xx0 x)(xx)

5、(01xx1x)(xx)(12xx,.1 , 0)(k1kkxx迭代法及收斂性 若 收斂，即 則得 是 的一個(gè)根kx xxkklimx)(xx)()lim()(limlim1nxxxxxnnnnn基本迭代法 上述方法稱為 基本迭代法將 變?yōu)榱硪环N等價(jià)形式 。選取 的某一近似值 ，則按遞推關(guān)系 產(chǎn)生的迭代序列 。這種方法算為簡(jiǎn)單迭代法。0)(xf)(xxx,0bax ,.1 , 0)(k1kkxxkx 若 收斂，即 稱迭代法收斂，否則稱迭代法發(fā)散kx xxkklim迭代法的幾何意義n 交點(diǎn)的橫坐標(biāo) *x)()(xyxyxxy=x2x0 x1x例題 例 試用迭代法求方程 在區(qū)間(1，2)內(nèi)的實(shí)根。

6、 解：由 建立迭代關(guān)系 k=10,1,2,3.計(jì)算結(jié)果如下:31xx01)(3xxxf311kkxx例題n精確到小數(shù)點(diǎn)后五位5102132472. 1x例題n但如果由 建立迭代公式 仍取 ，則有 ， 顯然結(jié)果越來(lái)越大， 是發(fā)散序列1x3x,.2 , 1131kxxkk 5 . 10 x 2.3751x 12.392x kxn下面考慮如下兩個(gè)問(wèn)題：n什么時(shí)候收斂？n收斂速度怎么刻畫？迭代法的收斂性n定理（壓縮映像原理）（了解）設(shè)迭代函數(shù) 在閉區(qū)間 上滿足（1）（2） 滿足Lipschitz條件即 有且 。 )(x ,ba,)(,baxbax)(x,21baxx )()(2121xxLxx10 L

7、壓縮映像原理則 在 上存在 唯一解 ，且對(duì) ，由 產(chǎn)生的序列 收斂于 。 )(xx,0bax )(k1kxx.1kxx,bax關(guān)于壓縮映像，教材上有另外一種形式Th4.2.1 則基本迭代格式收斂的充要條件是：*/( )(),( )xxxxx xxx是的根，U設(shè)連續(xù)，*10()(kkx基本迭代格式xx 的初始值xU）( )1xL例題n例例 證明函數(shù) 在區(qū)間1，2上滿足迭代收斂條件。n證明：31)x(x上嚴(yán)格單調(diào)增函數(shù)。是區(qū)間所以因?yàn)?)(2 , 1 0) 1(31)x(32baxxx例題 2 , 1 1431|) 1(31| )(|332xLxx又23)2(12) 1 (33，而）。滿足條件（，

8、所以即1)(2 , 1 )2(),1 (x）。滿足條件（所以2)(x滿足壓縮映像原理。在故2 , 1 1)x(3x例題n若取迭代函數(shù) ， 不滿足壓縮映像原理，故不能肯定 收斂到方程的根。 1)x(3 x2 , 1 3|3| )(|2xxx因?yàn)?.1 , 0)(1nxxnn簡(jiǎn)單迭代收斂情況的幾何解釋 是否取到合適的初值，是否構(gòu)造合適的迭代格式，對(duì)于是否收斂是關(guān)鍵的。對(duì)于初值，實(shí)際操作時(shí)，可以先畫出函數(shù)圖形，然后，觀察根大概在什么地方。對(duì)于迭代格式，可以對(duì) 求導(dǎo)，看看 是否小于1（ x）/0()x n迭代法收斂的階迭代法收斂的階 定義定義 設(shè)序列 收斂到 ，若有實(shí)數(shù) 和非零常數(shù)C，使得 其中， ，

9、則稱該序列是p 階收斂的，0nx*x1pCeepnnn1lim*xxenn迭代法收斂的階迭代法收斂的階當(dāng)p=1時(shí)，稱為線性收斂；當(dāng)p1時(shí)，稱為超線性收斂；當(dāng)p=2時(shí)，稱為平方收斂或二次收斂。n誤差估計(jì) n若 滿足定理?xiàng)l件，則n )(xx1L|1Lkkkxxxx0L|1 Lkkkxxxx*/11110( )LL,LkkkkkkkkLxxxxxxxxx是根附近（x的某鄰域）上的最大值，實(shí)際中，我們可以如下估計(jì) 及 ，L下面定理給出判別迭代收斂階的一個(gè)方法n定理： 記 是 的根， ，設(shè) 在 附近連續(xù)，若對(duì) ，有則基本迭代法 是P階連續(xù)的。( )xx*()xx( )( )px*x1p /*/*(1)*

10、( )*()()()0,()0,ppxxxx1()kkxx*x基本迭代法的matlab實(shí)現(xiàn)nfunction k,piancha,xk=diedai1(x0,k)n% 輸入的量-x0是初始值,k是迭代次數(shù)nx(1)=x0; nfor i=1:kn x(i+1)=fun1(x(i);%程序中調(diào)用的fun1.m為函數(shù)y=(x) n piancha= abs(x(i+1)-x(i); ni=i+1;xk=x(i);(i-1) piancha xknendMatlab中與或非，分別是：& | 與或非 nif (piancha 1)&(k3)n disp(請(qǐng)用戶注意：此迭代序列發(fā)散，請(qǐng)重

11、新輸入新的迭代公式)n return;n endn if (piancha 3)n disp(祝賀您！此迭代序列收斂，且收斂速度較快)n return;n endnp=(i-1) piancha xk;關(guān)于程序里面的fun1,可以如下類似定義nfunction y1=fun1(x) y1=(10-x2)/2;作業(yè)： 1. 編程求方程 在區(qū)間(1，2)內(nèi)的實(shí)根。2. 習(xí)題4.4（P104） 01)(3xxxf4.3 Newton迭代法n設(shè)x * 是方程f (x ) = 0的根，又x0 為x * 附近的一個(gè)值 ，將f (x ) 在x0附近做泰勒展式 令 ，則 之間和在其中020000)()(21)

12、()()()(xxfxxxfxxxfxf *xx )()(21)()()()(020*00*0*fxxxfxxxfxf Newton迭代法即以x1代替x0重復(fù)以上的過(guò)程，繼續(xù)下去得：0)()()(000*0 xfxxfxxf*000()()f xxxfx0100()()fxxxfxNewton迭代法,.1 , 0)()(1nxfxfxxnnnn以此產(chǎn)生的序列Xn得到f(x)=0的近似解，稱為Newton法，又叫切線法。Newton迭代法幾何解釋n幾何意義例題例 用Newton法求 的近似解。解：由零點(diǎn)定理。0cos)(xxxf內(nèi)有根。在)2, 0(0cosxx迭代公式得及由Newtonxxfs

13、in1)(,.1 , 0sin1cos1nxxxxxnnnnn例題085133739. 0739085133. 0739085133. 0739085178. 0;73936133. 044*43210 xxxxxxx故取得取例題n例 用Newton法計(jì)算 。解：22( )02f xxaa其中迭代公式得及由Newtonxxf2)(21212()0,1,.22nnnnnnxxxxnxx。有十位有效數(shù)的近似值是已的精確值相比，。與，則取332102414213562. 1414215686. 11.416666675 . 1xxxxxNewton迭代法算法。輸出）轉(zhuǎn)（做輸入110100100100

14、0:)4(;2) 3;)2;/) 1|while(3);();()2(;,) 1 (xendwhilexxffxxfxffxffxNewton迭代法收斂性定理4.3.1給定方程 ，若滿足條件：（1）在根附近，f(x)二次連續(xù)可微。（2） 則Newton迭代法是局部二階收斂的。（即初值取根附近的值時(shí)，是二階收斂的）( )0f x /*()0fxn定理告訴我們：定理告訴我們：?jiǎn)胃浇嵌A收斂的單根附近是二階收斂的Newton法的matlab實(shí)現(xiàn)nfunction k,xk,yk,piancha,xdpiancha=newtonqx(x0,tol,ftol,gxmax)nx(1)=x0; Newt

15、on法的matlab實(shí)現(xiàn)nfor i=1: gxmaxn x(i+1)=x(i)-fnq(x(i)/(dfnq(x(i)+eps); piancha=abs(x(i+1)-x(i);n xdpiancha= piancha/( abs(x(i+1)+eps); i=i+1;nxk=x(i);yk=fnq(x(i); (i-1) xk yk piancha xdpianchanif (abs(yk)ftol)&(pianchatol)|(xdpianchagxmaxn disp(請(qǐng)注意：迭代次數(shù)超過(guò)給定的最大值gxmax。)n k=i-1; xk=x(i);(i-1) xk yk pia

16、ncha xdpianchan return;nendn (i-1),xk,yk,piancha,xdpiancha;重根情形Newton 迭代重根時(shí)僅有線性收斂速度，經(jīng)修改后可以有二階收斂性。設(shè)重?cái)?shù)為m.（1）m已知時(shí)，迭代公式修改為：1/()()kkkkf xxxmfxn（2）m未知時(shí)，在根的附近 有單根，對(duì) 構(gòu)造newton迭代公式： ( )0( )f xfx/1/2/()()()()()kkkkkkkf xfxxxfxf xfx( )0( )f xf x求重根的matlab實(shí)現(xiàn)n（一）（一） 已知方程根的重?cái)?shù)已知方程根的重?cái)?shù)n供名為供名為newtonxz.m的的M文件：文件：nfunc

17、tion k,piancha,xdpiancha,xk,yk=newtonxz(m,x0,tol,ftol,gxmax)nx(1)=x0;nfor i=1: gxmaxnx(i+1)=x(i)-m*fnq(x(i)/(dfnq(x(i)+eps); npiancha=abs(x(i+1)-x(i);nxdpiancha=piancha/( abs(x(i+1)+eps); i=i+1; nxk=x(i);yk=fnq(x(i); (i-1) piancha xdpiancha xk yk;n if (pianchatol)|(xdpiancha tol)&(abs(yk)gxmaxn

18、disp(請(qǐng)注意：迭代次數(shù)超過(guò)給定的最大值請(qǐng)注意：迭代次數(shù)超過(guò)給定的最大值gxmax.)n k=i-1; xk=x(i); yk=fnq(x(i); n(i-1) piancha xdpiancha xk yk;nreturn;nend求重根的matlab實(shí)現(xiàn)n（二）（二） 未知方程根的重?cái)?shù)未知方程根的重?cái)?shù)nfunction k,piancha,xdpiancha,xk,yk=newtonxz1(x0,tol,ftol,gxmax)nx(1)=x0;nfor i=1: gxmaxnu(i)=fnq(x(i)/dfnq(x(i);ndu(i)=1-fnq(x(i)*ddfnq(x(i)/(dfn

19、q(x(i)2+eps);nx(i+1)=x(i)-u(i)/du(i); piancha=abs(x(i+1)-x(i);nxdpiancha=piancha/( abs(x(i+1)+eps); i=i+1; xk=x(i);yk=fnq(x(i);n if (pianchatol)|(xdpiancha tol)&(abs(yk)gxmaxn disp(請(qǐng)注意：迭代次數(shù)超過(guò)給定的最大值gxmax.)nk=i-1; xk=x(i); yk=fnq(x(i); (i-1) piancha xdpiancha xk yk ;nreturn;nendn例例 用牛頓切線法求方程 在 附近的

20、近似根，要求精度 .n解解 n在MATLAB工作窗口輸入程序k,xk,yk,piancha,xdpiancha=newtonqx(-0.4,0.001, 0.001,100)n k,xk,yk,piancha,xdpiancha=newtonqx(-0.4,0.001, 0.001,100)013223 xx00.4x 310nfunction k=fnq(x)n k=2*x3-3*x2+1;n%計(jì)算x處的函數(shù)值nfunction k=dfnq(x)nk=6*x2-6*x;n%計(jì)算x處的一階導(dǎo)數(shù)值作業(yè)1： 求 ，要求精度為 .要求（1）寫出牛頓迭代格式，并分析其收斂速度（可仿照p97例4.3.1） （2）寫出matlab實(shí)現(xiàn)程序（寫清程序newtonqx(x0,tol,ftol,