1、蘭州交通大學數理與軟件工程學院第2章 非線性方程的數值解法蘭州交通大學數理與軟件工程學院 代數方程求根問題是一古老的數學問題，十六世紀人們找到了求三次、四次方程根的公式，十九世紀證明了大于等于五次的代數方程沒有一般的求根公式。而科學技術研究及工程實踐中，常常會遇到求解高次代數方程或超越方程的問題，一般歸納為求解方程 f(x)0 (2.1) 其中f(x)是一元非線性實函數。本章研究這類非線性方程近似解的數值方法。蘭州交通大學數理與軟件工程學院2.1二分法 求非線性方程0)(xf的根的方法 確定方程的有根區間 計算根的近似值蘭州交通大學數理與軟件工程學院 首先確定有限區間：依據零點定理。 設 ，且

2、 ， 則方程 在區間 上至少有一個根。如果 在 上恒正或恒負，則此根唯一。,)(baCxf0)()(bfaf0)(xf)(xf),(ba),(ba蘭州交通大學數理與軟件工程學院等步長掃描法求有根區間 用計算機求有根區間：等步長掃描法 設h0是給定的步長，取 ，若 則掃描成功；否則令 ，繼續上述方法，直到成功。如果 則掃描失敗。再將h 縮小，繼續以上步驟。haxax10,0)()(10 xfxfhxxxx0110,bx 1蘭州交通大學數理與軟件工程學院等步長掃描算法 算法：（求方程 的有根區間）(1) 輸入 ；(2) ； (3) ，若 輸出失敗信息，停機。(4)若 。輸出 ，已算出方程的一個根，

3、停機。0)(xfhba,)(0aff)(,1xffhaxbx 01fx蘭州交通大學數理與軟件工程學院等步長掃描算法(5) 若 。輸出 為有根區間，停機(6) ，轉 3） 注：如果對足夠小的步長h掃描失敗。說明：在 內無根在 內有偶重根010ff, ,xaxaxa ,ba,ba蘭州交通大學數理與軟件工程學院二分法 用二分法(將區間對平分)求解。 令 若 ，則 為有根區間，否則 為有根區間 記新的有根區間為 ， 則 且 )(,1121111bacbbaa0)()(11cfaf,11ca,11bc,22ba,2211baba)(112122abab蘭州交通大學數理與軟件工程學院二分法 對 重復上述做

4、法得 且,22ba.,.,2211nnbababa)(211ababnnn蘭州交通大學數理與軟件工程學院二分法 設 所求的根為 ， 則 即 取 為 的近似解x.2 , 1,nbaxnn.2 , 1nbxann0)(21lim)(lim1nababnnnnxbannnnlimlim)(21nnnbacxx蘭州交通大學數理與軟件工程學院求方程f(x)=0的根的二分法算法).(21)4(;endwhile.,;,0)()()2);(),(21)1|)3(;3,10)()()2(;,:)1(baxbxbaelsexabathenxfafifxfbaxbawhileelsebathenbfafifbab

5、a輸出計算令時做步轉第值輸入重新步返回第值及精度控制量的有根區間輸入蘭州交通大學數理與軟件工程學院求方程f(x)=0的全部實根的二分法算法);();(211|while)2endwhile;0)()(while)1while)3(;)2(;,:)1(11011111111111xfbaxabhabaabfafbbhabaahba計算時做做時做輸入蘭州交通大學數理與軟件工程學院求方程f(x)=0的全部實根的二分法算法;endwhile;10;:)3;endwhile.,0)()(if3);3(0)(if2111111111100habhxaxbxbaelsexabathenxfafxf輸出轉蘭州

6、交通大學數理與軟件工程學院例題 例1 設方程 解：取h=0.1,掃描得： 又 即 在 有唯一根。 2 , 1 , , 1)(3baxxxf0344. 0)4 . 1 (061. 0)3 . 1 (ff.4 . 1 , 3 . 1 方程的有根區間為4 . 1 , 3 . 1 , 013)(2xxxf0)(xf4 . 1 , 3 . 1 蘭州交通大學數理與軟件工程學院2.2簡單迭代法 將 變為另一種等價形式 。選取 的某一近似值 ，則按遞推關系 產生的迭代序列 。這種方法算為簡單迭代法0)(xf)(xxx,0bax ,.1 , 0)(k1kkxxkx蘭州交通大學數理與軟件工程學院迭代法的幾何意義

7、交點的橫坐標)()(xyxyxx蘭州交通大學數理與軟件工程學院迭代法的收斂性設迭代函數 在閉區間 上滿足（1）（2） 滿足Lipschitz條件即 有且 。 )(x ,ba,)(,baxbax)(x,21baxx )()(2121xxLxx10 L蘭州交通大學數理與軟件工程學院簡單迭代收斂情況的幾何解釋蘭州交通大學數理與軟件工程學院例題在區間(1，2)內的實根。 解：由 建立迭代關系 k=10,1,2,3.計算結果如下:01)(3xxxf31xx311kkxx蘭州交通大學數理與軟件工程學院例題 精確到小數點后五位5102132472.1x蘭州交通大學數理與軟件工程學院例題 但如果由 建立迭代公

8、式 仍取 ，則有 ， 顯然結果越來越大， 是發散序列1x3x,.2 , 1131kxxkk 5 . 10 x 2.3751x 12.392x kx蘭州交通大學數理與軟件工程學院2.3迭代法的階及和加速法 考察方程 。這種方程是隱式方程，因而不能直接求出它的根，但如果給出根的某個猜測值 ， 代入 中的右端得到 ，再以 為一個猜測值，代入 的右端得 反復迭代得)(xx0 x)(xx)(01xx1x)(xx,.1 , 0)(k1kkxx0 x蘭州交通大學數理與軟件工程學院迭代法及收斂性若 收斂，即 則得 是 的一個根kx xxkklimx)(xx)()lim()(limlim1nxxxxxnnnnn

9、蘭州交通大學數理與軟件工程學院迭代法收斂的階迭代法收斂的階蘭州交通大學數理與軟件工程學院迭代法收斂的階迭代法收斂的階蘭州交通大學數理與軟件工程學院迭代法收斂的階迭代法收斂的階蘭州交通大學數理與軟件工程學院2.4 Newton迭代法 設x * 是方程f (x ) = 0的根，又x0 為x * 附近的一個值 ，將f (x ) 在x0附近做泰勒展式 令 ，則之間和在其中020000)()(21)()()()(xxfxxxfxxxfxf *xx )()(21)()()()(020*00*0*fxxxfxxxfxf 蘭州交通大學數理與軟件工程學院Newton迭代法及割線法去掉 的二次項，有：即以x1代替

10、x0重復以上的過程，繼續下去得：0*xx 0)()()(000*0 xfxxfxxf)()(0001*xfxfxxx蘭州交通大學數理與軟件工程學院Newton迭代法,.1 , 0)()(1nxfxfxxnnnn以此產生的序列Xn得到f(x)=0的近似解，稱為Newton法，又叫切線法。蘭州交通大學數理與軟件工程學院Newton迭代法幾何解釋 幾何意義蘭州交通大學數理與軟件工程學院例題解：由零點定理。0cos)(xxxf內有根。在)2, 0(0cosxx迭代公式得及由Newtonxxfsin1)(,.1 , 0sin1cos1nxxxxxnnnnn蘭州交通大學數理與軟件工程學院例題0851337

11、39.0739085133.0739085133.0739085178.0;73936133.044*43210 xxxxxxx故取得取蘭州交通大學數理與軟件工程學院例題解：20)(2aaxxf其中迭代公式得及由Newtonxxf2)(,.1 , 0)2(212221nxxxxxxnnnnnn。有十位有效數的近似值是已的精確值相比，。與，則取332102414213562. 1414215686. 11.416666675 . 1xxxxx蘭州交通大學數理與軟件工程學院Newton迭代法算法。輸出）轉（做輸入1101001001000:)4(;2)3;)2;/)1|while(3);();()

12、2(;,)1(xendwhilexxffxxfxffxffx蘭州交通大學數理與軟件工程學院Newton迭代法收斂性 若初值 滿足 時，由Newton法產生的序列收斂到 在a,b上的唯一根。,)(2baCxf上恒正或恒負。在,)()3);,( ,0)()2;0)()()1baxfbaxxfbfaf ,0bax 0)()(00 xfxf0)(xf蘭州交通大學數理與軟件工程學院Newton迭代法收斂性證明： 根的存在性 根的唯一性內至少有一個根。在知）及由條件（),(0)(,)(1baxfbaCxf。記此根為內有唯一根在上嚴格單調函數，因此是故保號，知及由*,),(0)(,)()(,bCa,)(,

13、0)(xbaxfbaxfxfxfxf蘭州交通大學數理與軟件工程學院Newton迭代法收斂性 收斂性)()(0)()(0)(, 0)(, 0)(,0)()(0)(, 0)(, 0)(, 0)(010000001000*000 xxxfxfxxfxfxxxfxfxfbxxxfxfxfxfbfaf 即有，所以知，由，不妨設蘭州交通大學數理與軟件工程學院Newton迭代法收斂性繼續上述推理有代替。再以因此有兩式相減展式由另一方面0101*20*01*20*0*00*0)()()(21)(21)()()(0 Taylor,xxxxxxxxffxxxxfxxxfxfxf 蘭州交通大學數理與軟件工程學院Ne

14、wton迭代法收斂性。，由根的唯一性知可得時當由。故必有極限，記。是單調減有下界的序列故序列*10011*0)(,.2 , 1)()(lim.xaafnnxfxfxxaxxxxxxxnnnnnnnnn蘭州交通大學數理與軟件工程學院Newton迭代法收斂性故結論成立。之間，則與介于其中，證明，一般有類似定理證明0)()(21lim)()()(211 . 3 . 2* 21*2*1n* xfxfeexxxxxffxxnnnnnnnn蘭州交通大學數理與軟件工程學院代數方程的Newton迭代法 代數方程的Newton迭代法推導設n次代數方程用Newton迭代法求有限區間的實根，則要計算 ，一般采用秦九

15、韶算法。,.2 , 1)()(1nxfxfxxnnnn)0(0)(0110 aaxaxaxfnnn)(),(nnxfxf蘭州交通大學數理與軟件工程學院代數方程的Newton迭代法 由Taylor展式) 2(!)()(.! 2)()()()( ) 1 ()()()(!)()(.! 2)()()()()()()(1)(2nxfxxxfxxxfxQxQxxxfnxfxxxfxxxfxxxfxfnnnnnnnnnnnnnnnnnn 其中蘭州交通大學數理與軟件工程學院代數方程的Newton迭代法);()(1)() 1 (nnxfxQnxfxx，余式為次多項式為，得商）去除式表示，用（)3()()()()

16、(),()()2(12110 nnnnnnnbxbxbxQxQxxxfxfxQ的余式，令除以為且式知，由蘭州交通大學數理與軟件工程學院nnnnnnnnnaxaxaxabxbxbxxxfxf 111012110.)()()(1)3(）式得式代入（),.,2, 1()(100nkxxfbbababxnnnkkk的同次冪系數得比較等式兩邊蘭州交通大學數理與軟件工程學院代數方程的Newton迭代法同理 )()()()()(xRxxxfxQxQxxnnn有取除以用) 4()(23120 nnncxcxcxR令12211023120.)()()() 3 () 4( nnnnnnnnnbxbxbxbcxcx

17、cxxxfxQ式得式代入蘭州交通大學數理與軟件工程學院代數方程的Newton迭代法比較x的同次冪系數得：故代數方程的Newton迭代公式) 1,.,2 , 1()(1100nkxxfccbcbcnnnkkk,.)2 , 1(11ncbxxnnnn蘭州交通大學數理與軟件工程學院代數方程的Newton迭代法步。返回第停止計算輸出做對計算輸入2)(,;,|(4);)(3;1,.,2, 1)2;)1);(),()2(;,),.,2, 1 ,0(:)1(101*01100101010000100000 xxelsexxthenxxifffxxxfffxfafnkffafxfxfxniaki蘭州交通大學數

18、理與軟件工程學院割線法 Newton迭代法有一個較強的要求是 且存在。因此，用弦的斜率 近似的替代0)( xf)(xf )()()()()(,(P)(,(P,)(10101111100010*xxxxxfxfxfyxfxxfxbxaxxbaxf得弦的方程及則過，取上有唯一零點在設蘭州交通大學數理與軟件工程學院割線法 令y=0,解得弦與x軸的交點是坐標x2.,.)2 , 1()()()(.,)()()(0)()()()(00132010101121201011稱之為定端點弦截法計算再由解得nxfxfxfxxxxxxxxfxfxfxxxxxxxxxfxfxfnnnnn蘭州交通大學數理與軟件工程學院割線法.,.)2 , 1()()()(,111321又稱快速弦截法稱之為變端點弦截法以此類推計算若由nxfxfxfxxxxxxxnnnnnnn蘭州交通大學數理與軟件工程學院割線法的幾何解釋蘭州交通大學數理與軟件工程學院弦截法收斂定理則其中如果的根是為足夠小的正數設定理0| )(|max|,)(|max12,0)(, , ,)(1 .4 .21212*2 xfmxfMmMqxfxxxbabaCxfbxabxa蘭州交通大學數理與軟件工程學院弦截法收斂定理。的斂速收斂到以確