第2章方程的近似解法

1、第二章方程求根在許多實(shí)際問題中，常常會(huì)遇到方程 f(X)=0求解的問題。當(dāng)f(X)為一次多 項(xiàng)式時(shí)，f(X)=0稱為線性方程，否則稱為非線性方程。對(duì)于非線性方程，由于 f(X)的多樣性，求其根尚無一般的解析方法可以使用，因此研究非線性方程的數(shù) 值解法是十分必要的。本章匸要介紹求非線性方和根的一些常用方法。它們是增值界根法、二分 法、迭代法、牛頓法及割線法。這些方法均是知道根的初始近似值后，進(jìn)一步把 根精確化，直到達(dá)到所要求的 精度為止。也即求非線性方程根的數(shù)值方法。 第一節(jié)第一節(jié)增值尋根法與二分法2.1.1增值尋根法設(shè)非線性方程f(X)=0的根為X*，增值尋根法的基本思想是，從初始值 X0開

2、始，按規(guī)定 的一個(gè)初始步長h來增值。令Xn41 = Xn+h(n=0,1,2，)，同時(shí)計(jì)算 f( Xn卡)。在增值的計(jì)算過程中可能遇到三種情形：Xn杓=0，此時(shí)X卄即為方程的根X* 0 Xn )和( Xn巧同符號(hào)。這說明區(qū)間 Xn)和f( Xn異號(hào)，即冇f( Xn) f( Xn杓 V 0Xn, Xn出上連續(xù)時(shí)，方程f(X)=0f(f(f(異號(hào),Xn, Xn出內(nèi)無根。此時(shí)當(dāng)f(X)在區(qū)間根。也即我們用增值尋根法找到了方程根的存在區(qū)間， 近似值。下一步就是設(shè)法在該區(qū)間內(nèi)尋找根X*更精確的近似值，為此再用增值h尋根法 把Xn作為新的初始近似值，同時(shí)把步長縮小，例如選新步長100，這 樣會(huì)得到區(qū)間長度

3、更小的有根區(qū)間，從而也得到使f(X) 更接近零的Xn，作為X*更精確的近似值，若精度不夠，可重復(fù)使用增值尋根法，直到有根 區(qū)間的長度I Xn札Xn IV E (E為所要求的精度)為止。此時(shí)f( Xn)或f( Xn杓就可 近似認(rèn)為是零。Xn或Xn +就是滿足精度的方程的近似根(如圖 2-1 ).在Xn, XnF 一定有Xn或xn+均可以視為根的1例1用增值尋根法求方程f(x)= x3+4x2-10=0的有根區(qū)間。解取x0=-4，h=1，則計(jì)算結(jié)果如下表2-1 :表2-1f(a) f(b) 0,則由連續(xù)函數(shù)性質(zhì)知， 為以下討論方便，設(shè)(a,b)內(nèi)僅有唯一實(shí)0精度的根x的近似值，如圖2-2x11.1

4、1.21.21.4f(x)-5-3.829-2.512-1.0430. 584所以f(x)=O更進(jìn)一步的有根區(qū)間為(1.3 ,1.4)2.1.2二分法設(shè)f(x)在區(qū)間a,b 上連續(xù)，且方程f(x)=0在(a ,b)內(nèi)至少有一實(shí)根，根x 0 二分法的基本思想 就是逐步對(duì)分區(qū)間a,b :，通過判斷兩端點(diǎn)函數(shù)值乘積的符號(hào)，進(jìn)一步縮小有根區(qū)間，具體做法如下a +b用區(qū)間 a,b 的中點(diǎn)X1 2平分區(qū)間，并計(jì)算f( x1)，同時(shí)記(a1, b1)=(a,b)， 如果恰好有f( x1)=0，則我們已經(jīng)找到方程的根x*= X1o如若不然，f( x1)工0,如果 f(al) f(X1) 0,則記(a2,b2)

5、= (al,Xi),如果 f(x1) f( b) 0,貝U記(a2, b2)= ( X1, b1)，在后兩種情形區(qū)間(a2b2,)為新的有根區(qū) 間。它包含在舊 的有根區(qū)間(印，4)內(nèi)，其區(qū)間長度是原區(qū)間的一半。對(duì)區(qū)間(a2 , b2)施行同樣 的辦法。即平分區(qū)間，求中點(diǎn)判斷函數(shù)值乘積的符號(hào)，得到新的有根區(qū)間(a31 1,b3)，它包含在區(qū)間(去,)內(nèi)，其區(qū)間長度是(a2,b2)的2 , (a1, 4)的4。 如此重復(fù)n 次,如果還沒有找到方程的精確根X* ,此時(shí)我們得到方程的有根區(qū)間 序列：(a1,d) ,(a2, b2)，,(an,bn)，它溝足 (a1,b)二(,d 印 _ b - ab2

6、) =)=)(an,bn) 卅 f( an)f( bn)0bn- an= 2心 2“,n = 1,2,-n-1步n充分大時(shí)，(an,bn)的長度縮小到充分小，此時(shí) 它的中點(diǎn)Xn與X*夾在an與bn之間，它們的距離也充分小，且序列Xn滿足：Xn -X Clim n = x 即序列 Xn 。同時(shí)也表明序列 Xn 是X*的一個(gè) 近似 b a 尹n- :2n 此時(shí),我* bn -anb - a廠二上式表明總存在n,使Xn X值序列。因此對(duì)任意給定的精度0 ,們可以取Xn作為X*的近似值，即可滿足 精度3例2用二分法求方程f(x)= x+4x2-10= 0在1, 2.)以等比數(shù)列的收斂速度收斂于X要求滿

7、足精度 解 用二分法計(jì)*13xn -X -x102十算結(jié)果如表2-3 :nanbnXnf(Xn)11.02.01.52.37521.01.51.25-1.7968731.251.51.3750.1621141.251.3751.3125-0.8483951.31251.3751.34375-0.3509861.343751.3751.359375-0.0964171.3593751.3751.36718750.03236內(nèi)的一個(gè)實(shí)根，且81.3593751.36718751.36328125-0.0321591.363281251.36718751.3652343750.000072101.3

8、63281251.3652343751.364257813-0.01605111.3642578131.3652343751.364746094-0.00799迭代11次，近似根X11=1.364746O94即 為所求，其誤差X* 少1 -如=0.000488281*-X102 2這種方法的優(yōu)點(diǎn)是簡(jiǎn)單，對(duì)f(x)-只要求連續(xù)。它的收斂速度與 比值為2的等比級(jí)數(shù)相同，它的局限性是只能用 于求實(shí)根，不能用于求復(fù)根及偶數(shù)重根。迭代法的基本思想由函數(shù)方程f(x)=O，構(gòu)造一個(gè)等價(jià)方程：x=(x)(1)從某個(gè)近似根Xo出發(fā)， 令Xn+ N(Xn)，n=0,1,2，(2) 町即到序列 Xn ，若 Xn 收

9、斂，即V*苗limxn+=limW(x n)山(limx n)lim Xn = X只要W (X)連續(xù)，有孚4 nnTcn也即X* N(X*)從而可知X*是方程(1)的根，也就是f(x)=O的根。此時(shí) Xn 就是 方程(1)的一個(gè)近似解序列，n越大，Xn的近似程度就越好。若 Xn 發(fā)散，則 迭代法失敗。例1用迭代法求方程f(x)= x+ 4x2-10=0在1,2 內(nèi)的一個(gè)近似根，取初始 近似值Xo “5.表2-4n(1)(2)(3)01.51.51.51.51-0.8750.81651.286953771.3483997326.7322.99691.402540801.367376373-469

10、.712(-8.65)1.345458381.3649570141.03心081.375170251.3652647551.360094191.3652255961.367846971.36522305871.363887001.3652299481.365916731.3652300291.364878221.36523001101.36541006151.36522368201.36523024231.36522998251.3652300132(1) X = x-x -4x +10 (2)10X 七-4XX = 1 J10 -X32/ 10 X U+x對(duì)應(yīng)的迭代公式冇:(1) Xn+ -

11、 Xn-Xn -4Xn +10(2)xri解原方程的等價(jià)方程可以有以下不同形式:10-1.5，列表計(jì)算如表2-2。 與，而用二分法達(dá)到同樣的精度， 收斂速度也不盡相同，迭代函上節(jié)二分法比較，（3）、（4）都得到較好的結(jié)果 需要迭代27次，同時(shí)也看出迭代函數(shù)構(gòu)造不同，數(shù)構(gòu)造不當(dāng)（如（1） ， （2），序列 xn 就不收斂。二迭代法的幾何意義以lJ以右刮迭代法町能收斂，也對(duì)能不收斂一股來說從f（X）=0，構(gòu)造半（X） 不止一種，有的收斂，有的不收斂，這取決于的性 （x）態(tài)。方程x=的W（X）根, 在幾何上就是直線 y=x 與曲線y=%x）交點(diǎn)的橫坐標(biāo)X*,如圖2-3所示。三迭代法收斂的條件(d)X

12、0 B,迭代過程X附近局部收斂。定理1設(shè)x*=(x*),在X*的某個(gè)鄰域B內(nèi)W (X)連續(xù)，并且I(X)|w q1, 則對(duì)任何X0 B,由迭代公式Xn4t=W(Xn)決定的迭代序列 Xn 收斂于X*。nq且 I Xn - X* | 1 - q1X -x可定義1 如果在根X*的某個(gè)鄰域B= X1Xn+=W(Xn)，n=0,1,2，收斂，貝U稱迭代過程在Xi -XoXn+ -Xn* .I Xn - X I 1 - q證：由拉格朗日中值定理，存在匕B,Xn -X* 沁(X2)-(X*) N 徉)(Xn-X*)由已知 I WC) |w q ,從而得I*n|Xn_x I q I Xnj-x I qlim

13、 xn = *所以Y X這樣我們就證明了再由拉格朗日中值定理，存在* BI X0 - X I Xn 收斂于 X 。 ，使Xn+ Xn =W(Xn) -W(Xn4)= W 徉)(X - Xn )所以| X -Xnq Xn - Xnjqn I X1 Xo I 又由于 I Xnp-XnI = I (Xn 甘一 Xn 牌二)+ (Xnpj- Xn_p_2)+ . +(Xn 屮一Xn )|冬 I Xn4p -Xn 和丄+ XMP A - XMP -2 +. + xn+ -xn 1 -qP/+qP 工 +q + 1) I Xn卡-Xn I = 1 - q I Xn半-Xn I1所以 I-XnI (qp令p

14、7 +x ,有I X*-Xn1z*也即I Xn - X I 1 -q再由得I Xn-X* I I iq IIXn屮Xnnq1 -q IX1Xnd!Xoxn I這樣(4)式得證。I 這樣(3)式也得證。這個(gè)定理是一個(gè)很實(shí)用的收斂定理。一方面它可以判定我們所構(gòu)造的迭代函 數(shù)(X)是否收斂。另一方面(3)式還可以估計(jì)迭代次數(shù)。但結(jié)果偏保守，次數(shù)也 偏大，實(shí)際中很少用。通常由 式，當(dāng) 丨Xn出-Xn I 匕(巴為給定精度)時(shí)， 認(rèn)為IX - Xn I 匕Xn就是X滿足精度的一個(gè)近似解了。定理2HTSS對(duì)于方程 x=(x)，如果滿足(1)對(duì)任意X a,b ，有(x) a,b :對(duì)任意 X a,b ，有

15、I (x) I q1不收斂1 10 - 10珥x)=l(4x)2y-4)W(1.5)斂ZK4(1.5)A(X)= 4旨.1281不收3x2(10-X3)20.656V1收斂l 1(4 + x)2=p0- (X)M+x斂)上例說陰W(X0 )值越小，收斂速度就越快。四迭代法的收斂速度用迭代法求方和的近似根，我們不僅要構(gòu)造適出的(X)要求它收斂，而且還需要知道它的收斂速度。關(guān)于收斂速度，有如下定義：*Ji*定義2設(shè)序列 xn 收斂于X ,令:二X - xn，若存在某實(shí)數(shù)P1及正A(x) =一5(W 5)卜 0.122V1 收=C(6)Xn 是由XnH4 = W (xn)產(chǎn)生的，且P階收lim常數(shù)c

16、,使y則稱序列 xn P階收斂。如果序列 斂，則稱這種迭代過程是P階收斂的。當(dāng)P =1 ,且C 1時(shí)，稱為線性收斂；斂)；為1vpv2時(shí)，稱為超線性收斂。同前面一樣，設(shè),X仝(xn) , X*= (X為p=2時(shí)，稱為平方收斂(或二次收則有 X* - XnX( X* - X n) ( 在n十在X*與xn之間)所以匕卄=牡)5因而|唧=|()TA(x)若0W(x )0 (n Tx)Xn 十-X*/(xn)-(X*)=h(XnX ) 此時(shí)迭代過和為二階收斂C 定理3設(shè)(X)在x=(x)的根X*鄰近有連續(xù)的P階導(dǎo)數(shù)，當(dāng)I (X)I 1,且3 ( X )工0 H寸，迭代過SXnF=W( xn)為線性收斂

17、；而當(dāng)W ( X )=0， ( X ) 工0時(shí)為二階收斂。一般來說，若 W (x*)=“(x )=/(P 4(x*)=0，而 W(P)(x*)工 0,則稱 Xn+=(xn)在X附近為P階收斂。 第三節(jié)迭代收斂的加速 從f(x)=0構(gòu)造出的迭代格式 斂速度也取決于I W (X) I的大小，當(dāng)I 后兩種情形都影響迭代法的應(yīng)用。能否從 式，使收斂速度加快呢？ 一 松馳法 対x=(X)引入一個(gè)任意常數(shù) 邊加上kX,得(1+ k)x= kx+W(X) 于是若 (X)連續(xù)，則當(dāng)X在根X*附近時(shí)，(X)也在 (X*)附近，為此選取 k=-(X*)。這樣可以使 得|釈(X)I較小。但在求解過程中X*未知，故用

18、xn來代替，只要畑=-4( Xn)工-1,記豹n = 1 + kn，于是代入(1)有松弛法迭代1XnH! = 0 國 n )Xn + 國 nW(Xn ) X (n=0 1 2 )(4)Bn稱為松弛因子。松弛法的加速效果是明顯的，甚至不收斂的迭代函數(shù)經(jīng)加速 后一般也能獲得收斂。二埃特金方法公式：國 n = 1 - 9 (Xn )用松弛法計(jì)算時(shí)，要先算屮(xn)，在使用時(shí)有時(shí)不太方便，假若在求得 Xn以后，先求出 Xn14沁(Xn)篙沁(X器)再利用和X篙構(gòu)造格式羊21-號(hào))2xn冷-“n打+Xn由此得到埃特金(Altk en )公式： Z (2)(1)2(Xt Xn41)Xn =Xn鴛 xn?2

19、X2 +Xn(5)(2)xn + XH-Xn1)1(Xn)X(2) X(1) Xn斗二屮(Xn屮)(n=0,1,2 ，)它的加速效果也十分明顯。埃特金法求方程x-4x2-10=0在初 值x。.5附近的一 110蘋tl4+x丿解用松弛法計(jì)算，取0(x)=(4 + x)寧r1n 師 唱1+ (4 +Xn)2因此松弛法的迭代公式為IXn十=0 -叫)Xn +叫(Xn)列表計(jì)算伽卜：表2- 3例1分別用松弛法、X =個(gè)根，取迭代格式X01 p1014 + x丿n01230.8908036860.8871231410.887130869Xn1.51.3649539161.3652300121.36523

20、0013n=0,1,2用埃特金方法計(jì)算，迭代格式為xn1(料4 + Xnx(2)( 10 )2L x(2)昭上1；)lXn 卡Xn+xLXn+-2X Xn n=0,1,2，列表計(jì)算如下：表2-4n0123嘰0.8908036860.8871231410.887130869Xn1.51.3649539161.3652300121.365230013與上節(jié)例1中 與 相比收斂 速度明顯加 第四節(jié) 第四節(jié) 牛頓法解非線性方程 f(x)=0的牛頓(Newton)法，就是將非線性方程線性化的一種方法。它是解代數(shù)方程和超越方程的有效方法之一。一牛頓法的基本思想把非線性函數(shù)f(x)在x0處展開成泰勒級(jí)數(shù)f

21、(X0)f(x)=f(X0)+(x- X0)f ( X0)+(x- X0) 22!+ 取其線性部分，作為非線性方程f(x)=0的近似方程，則有(X0 )=0f( X0)+(x- X0) ff(X0)X 1 = X0 - f (xo)(1)取其線性部分為f(X)=0的近似方程，若設(shè)f (Xo)豐0，則其解為再把f(x)在X1處展開為泰勒級(jí)數(shù)， f (Xi)f (X 1)工0,則得X2 = X1-(xj如此繼續(xù)下去，得到牛頓法的迭代公式：f(Xn)XnHt=Xn- f (Xn)(n=0,1,2,)(2)例1用牛頓法求方程f(X)=X 3+4x2-10=0在1,2 :內(nèi)一個(gè)實(shí)根，取初始近似值X0=1

22、.5：|解 f (x)=3x 2+8x 所以迭代公式為：2Xn + = X n.3Xn +8焉列表計(jì)算如下：x； +4x7 -10n=0,1,2，n0123Xn1.51.37333331.365262011.36523001牛頓法的幾何意義方程f(x)=0的根就是曲線y=f(x)與X軸交點(diǎn)的橫坐標(biāo)X*，當(dāng)初始近似值Xo 選取后，過(xo,f(Xo)作切線，其切線方程為：y- f(Xo)=f(Xo)(x-Xo)f(Xo)它與x軸交點(diǎn)的橫坐標(biāo)為x1 = x0 - f (Xo)一般地，設(shè)Xn是x*的第n次近似值，過(Xn,f( Xn)作y=f(x)的切線，其切f (Xn)線與X軸交點(diǎn)的橫坐標(biāo)為：Xn

23、 + = Xn_ f (Xn)即用切線與 X軸交點(diǎn)的橫坐標(biāo)近似 代2-4。牛頓法的收斂性及收斂速度設(shè)f(x)在a,b 滿足f(a) f(b)0 , xo、x a,b ，則方程 f(x)=0 在a,b 上有且只有 一個(gè)實(shí)根，由牛頓法迭代公式計(jì)算得到的近似解序列 xn 收斂于方 程f(x)=0 的根x*。由方程f(x)=0得到的牛頓迭代形式f(x )導(dǎo)數(shù)存在。四牛頓二階導(dǎo)數(shù)法這里將簡(jiǎn)單介紹一下牛頓二階導(dǎo)數(shù)法。對(duì)其幾何意義及收斂性不作詳細(xì)的敘 述，讀者可仿照牛頓法進(jìn)行討論，其基本思想是：將f(x)在X0處展開泰勒級(jí)數(shù)丄f(x)=f( X0)+f ( x0 )(x-取右端前三項(xiàng)近似代替2 +的近似方程

24、為x0)+ 2! f ( x0)(x- x0)f(x)，于是得 f(x)=0丄f( X0)+f ( X0)(x-Xo)+ 2! f ( Xo )(x- Xo) 2 =0也即 f( Xo)+(x- X0)f ( X0)+ 2 f (Xo)(x- Xo) =0 (3)f (X0)f(X0)i殳其解為X1.利用(1) ， Xi-Xo=- f(Xo)，代入中括號(hào)內(nèi)Xi-Xo,則得f( Xo)+( Xi- xo) f ( Xo)+ 2 f ( xo)f X0) =0f(Xo)f,(X0)_f“(X0)f(X0)丁是僻出 Xi，得 Xi=X0-2f (X0)f (Xn)f(Xn) -皿血重復(fù)以上過程得：X

25、n + = Xn-2f (Xn)于是得牛頓二階導(dǎo)數(shù)法的迭代公式為：2f(Xn)廠(Xn)XnHl = Xn- 2 f (Xn)2 - f (Xn”(X.)n=。上， 上式與牛頓法迭代公式(2)相比，利用此公式求根收斂更快，迭代次數(shù)更少。其 缺點(diǎn)是要求f(x)的二階導(dǎo)數(shù)存在。第五節(jié)割線法用牛頓方法解非 線性方程f(x)=0，雖然在單根附近有較高的收斂速度，但 需要計(jì)算f (X)。若f(x)比較復(fù)雜時(shí)，每次計(jì)算f (X)帶來很多不便；如果用 不計(jì)算導(dǎo)數(shù)的迭代方法，往往只有線性收斂的速度。本節(jié)我們介紹割線法，采取 在迭代過程中不僅用前一步Xn處的函數(shù)值，而且還使用X2處的函數(shù)值來構(gòu)造迭 代函數(shù)。這樣做能提高迭代的收斂速度。一割線法的基本思想設(shè)非線性方程f(x)=0，其中f(x)為a,b 上的連續(xù)函數(shù)，且f(a) f(b)0。設(shè)Xo, xi為f(x)=0的根X*的兩個(gè)初始近似值，過(Xo ,f( Xo)和(xi ,f( Xi)作一 f (Xi) - f (Xo)直線，其方程為：y=f( xi)+xi -Xo(X- xi)f (Xi)當(dāng) f( X1)工f( Xo)時(shí)，此直線與 X 軸交點(diǎn)為 X2=X1- f (xj- f (Xo)( X1-