1、第七章 非線性方程求根1110 ()0 ()0 , 1: ()sin0nnnnxfxffxnfxxa xaxa xae求 解 非 線 性 方 程是 非 線 性 函 數(shù) ， 例 ： 代 數(shù) 方 程。 例超 越 方 程 本章介紹一些求方程實根的近似值的有效方法，一般來說, 使用這些方法求非線性方程的實根可以分兩步進(jìn)行.第一步是確定某根的所在區(qū)間a,b，或給出根的近似值x0.第二步是對方程的根進(jìn)一步精確化,得到滿足精度要求的近似根. ( ) , , ( )( )0 ( )0, ( )0f xa ba bf af bf af b設(shè)在上連續(xù)且有且僅有一個根又。則可用對分法：不妨設(shè). ,2 2 02 ,

2、2 02 ,11111aababbbbaabafbaxbaf反之，令，否則：若輸出根若）,b ,a),ba2211 1 2）的計算，并產(chǎn)生區(qū)間重復(fù)對.2 02 ),3baxbafiiii則得到根，若1. 非線性方程實根的對分法(二分法)二分法的收斂性 11 , ,nna ba ba b二分法產(chǎn)生一個有根區(qū)間：11, 11 ()()22nnnnnnnbaa bbaba區(qū)間長度：，足夠大時，取近似值當(dāng)2 baxnnnn1 2nnbaxx誤 差 ：計 算 簡 便 ， 容 易 估 計 誤 差 ， 但 收 斂 較 慢 。a x* x0 b( )f x a1 b1以上公式可用于估計對分次數(shù)k.分析以上過程

3、不難知道，對分法的收斂速度與公比為1/2的等比級數(shù)相同.由于210=1024，可知大約對分10次，近似根的精度可提高三位小數(shù)位.對分法的收斂速度較慢，它常用來試探實根的分布區(qū)間，或求根的近似值.例例1 1 求求x3-3x+1=0的實根分布情況，并求的實根分布情況，并求0,10,1中的實根近中的實根近似值，精確到三位小數(shù)似值，精確到三位小數(shù). .解解: : 從從-4,4-4,4區(qū)間以步長為區(qū)間以步長為1 1計算計算f f( (x x)=)=x x3 3-3-3x x+1+1的函數(shù)值，列的函數(shù)值，列如下表如下表x-4-4-3-3-2-2-1-10 01 12 23 34 4f(x) -51-51

4、-17-17-1-13 31 1-1-13 319195353表表7-17-1可見，在可見，在(-2,-1)(-2,-1)區(qū)間、區(qū)間、(0,1)(0,1)區(qū)間、區(qū)間、(1,2)(1,2)區(qū)間各有一實根，區(qū)間各有一實根，下面求下面求(0,1)(0,1)區(qū)間上的實根區(qū)間上的實根, ,按二分法按二分法. .可得可得 x 0.347167968, 0.3474121090.347167968, 0.347412109若取若取 =0.0005, =0.0005, 當(dāng)當(dāng)k =13=13時時, ,bk -ak=0.0002441410.0005, =0.0002441410.0005, 此時過程結(jié)束此時過程

5、結(jié)束, , 取取 xk=(0.347167968+0.347412109)/2=0.347290038=(0.347167968+0.347412109)/2=0.347290038 0.3470.347可見，對分法的優(yōu)點是對函數(shù)的要求低可見，對分法的優(yōu)點是對函數(shù)的要求低(只要求只要求f(x)連續(xù)連續(xù))，方法，方法簡便、可靠，程序設(shè)計容易，事先估計計算次數(shù)容易，收斂速簡便、可靠，程序設(shè)計容易，事先估計計算次數(shù)容易，收斂速度恒定；缺點是不能求出偶重根，收斂速度較慢度恒定；缺點是不能求出偶重根，收斂速度較慢.取適當(dāng)?shù)牟介L取適當(dāng)?shù)牟介Lh =(b-a)/m 逐一檢驗小區(qū)間逐一檢驗小區(qū)間a+kh,a+(

6、k+1)h,(k=0,1,2,m-1) 的兩端函數(shù)值是否異號，的兩端函數(shù)值是否異號，若異號，則按以上二分法求出其中的根；若同號則不作求根而若異號，則按以上二分法求出其中的根；若同號則不作求根而轉(zhuǎn)入檢查下一個區(qū)間，只要轉(zhuǎn)入檢查下一個區(qū)間，只要h選得較小，則可求出本區(qū)間內(nèi)的選得較小，則可求出本區(qū)間內(nèi)的所有奇重實根所有奇重實根(包括單實根包括單實根).h選得過大，可能漏掉某些根；選得過大，可能漏掉某些根； h選得過小，則計算量增大選得過小，則計算量增大.對分法的思想方法還可用于搜索一個較大區(qū)間對分法的思想方法還可用于搜索一個較大區(qū)間a,b內(nèi)實根的分內(nèi)實根的分布情況布情況(不包括偶重實根不包括偶重實根

7、)，實際的作法是：，實際的作法是：2. 迭代法及其收斂性 連續(xù)。且改寫方程： )(0)( xxxfxxxnnn )( 1，得到序列建立迭代格式：1 (0 )(limlimlimnnnnnnnfxxxxx則 若收斂必收斂到）的根：* * ()()0limnnnxxxf xxx 若收斂，即，則：也稱作不動點迭代法 P265 迭代過程的幾何表示 ) :)(xyxyxx交點即真根。( )yxy xO x* x2 x1 x0 xy0P1Q1P2P*P2Q3*0331k ( )10 1.5. 1 1 1(0,1,2) k 0 1 2 7 8 x 1.51.35721 1.330861.324kkf xxx

8、xxxxxxk 例：求方程 在附近的根解：（ ） 將方程改寫為由此建立迭代公式331k721.32472 2 11.k 0 1 2 x1.52.37512.39 kkxxxx迭代收斂。（ ） 若將方程改寫為建立迭代公式 迭代不收斂。P266表7-2*1*. ( ) ,1 ,( );(2)01, , ( )()( ) , , ()(0,1,) nnxa bxa baxbLx ya bxyL xyxxa bxa bxxnx0定 理設(shè) 函 數(shù)在 區(qū) 間上 滿 足 條 件（ ） 對 任 意， 都 有存 在 常 數(shù)使 得 對 一 切都 有則 方 程在內(nèi) 有 唯 一 的 根且 對 任 何初 值 x迭 代

9、序 列均 收 斂 于， 并 有*10 x1nnLxxxL 不動點的存在性與迭代法的收斂性 （ P267 定理1，）連續(xù)，且滿足 2( ) , ( )( ),( ) , ( )( )0,( )( )0 , 0,( ) , xa bxxxxa baaabbba bxxa b 證：由條件（ ）知在上連續(xù)。令則在上連續(xù)，且故存在，使得 （ ）即（ ）,所以方程在內(nèi)有根。*12*12121212 ( ) , ,2()()xxa bxxxxxxL xxxx假設(shè)方程在內(nèi)有兩個根由條件（ ），有導(dǎo)出矛盾，唯一性得證。0*11*0*0*1111 , ,()() 01, limx , , ()()nnnnnnnn

10、kkkkkkkxa bxxxxL xxxxLxxLxxa bxxkxxxxL xxLx 對 任 意由 迭 代 公 式 有依 此 類 推 ， 得因 所 以即 對 任 意 初 值迭 代 序 列均 收斂 到 方 程 的 根。類 似 地 ， 對 任 意 正 整 數(shù),有0 x112112101010121010*10, ,(1)1 1, 1 npnnpnpnpnpnnnpnpnnpppnnnn pLpLxLxxxxxxxxxxxxxxLLLxxL LLLxxLxxx 于是，對任意正整數(shù)有令得*1*. ( ) , 1 , ( );(2)01, , , ( )( ) , , , , ()(0,1,) xnn

11、xa bxa baxbLxa bxLxxa bxa bxxnx0定理 設(shè)函數(shù)在區(qū)間上滿足條件（ ）對任意，都有存在常數(shù)使得對一切都有則方程在內(nèi)有唯一的根且對任何初值x迭代序列均收斂于，并有101nnLxxxL改變定理條件（）可得以下結(jié)論 , , , ( )( )( )()( )( )( )()( )2x ya bx yxyxyxyxyL xyx 證：設(shè)為上任意兩點，由微分中值定理，在之間至少存在一點 ，使得即滿足上一定理的條件（ ），故結(jié)論成立。*10 x1( )( ) , nnLxxxLLxxa b誤差估計式表明，常數(shù) 越小，簡單迭代法收斂越快。因而構(gòu)造迭代函數(shù)的原則是使在有根區(qū)間上有盡可能

12、小的上界。11211211111111*, 1 npnnpnpnpnpnnppnnnnnnnnnpLpLxxxxxxxxLxxxxLxxxxxx 對任意正整數(shù) 有）令得可通過檢查來判斷迭代過程應(yīng)否終止。（21112 ( )10 (1.5)0.250, (2)10 1.5,2 11( ) 1.51.51( )212111( )3.162212 2.51(2) 1( ) f xxxffxxxxxxxxx 例：用簡單迭代法求方程的根。解：因為有根區(qū)間。（ ）因且2222011 1.51( )1221.5111 ( )1.52.25 1.5,2,xxxx 因且根據(jù)定理，任取由這兩種等價方程所構(gòu)造的簡單

13、迭代方法都收斂，且第一種所產(chǎn)生的迭代序列收斂較快。 局部收斂性 (P269)*01* ()(,)()()1, () (0,1, 2,).nnxxO xxxxxxxxxxnx 定 理 ： 如 果 函 數(shù)在的 一 鄰 域內(nèi) 連 續(xù) 可 微 ，為 方 程的 根 ， 且則 存 在 正 數(shù)使 得 對 任 意迭 代 序 列收 斂 于設(shè)有不動點，如存在的某個領(lǐng)域?qū)θ我獾牡a(chǎn)生的序列且收斂到，則稱迭代法是局部收斂的)(x*x*x*:xxRRx 0)(1kkxx*xkx定義定理3局部收斂 *x*1 ()(,)()1,1, ()1(), ()()()(),()nnxO xxLxxxxLxxxxxxL xxxxx

14、xxx證 ： 因在內(nèi) 連 續(xù) ， 且故 存在 正 數(shù)使 得 對， 有另 一 方 面 ， 由又 有即。 由 上 面 定 理 知 ， 迭 代 序 列收 斂 于。 實際用迭代法計算時，先用對分區(qū)間法求較好的初值，然后再進(jìn)行迭代。1*1()( ) (0112kkkkkpkxxxxxexxkeCCepppp 定義：設(shè)迭代過程收斂于方程的根,如果迭代誤差當(dāng)時成立下列漸進(jìn)關(guān)系式為常數(shù)）則稱該迭代過程是 階收斂的。為線性收斂，為超線性收斂，為平方收斂。迭代法收斂速度定義(P271)()1*(1)*()* (),( ) ()()()0;()0pkkppxxxxxxxxxp定理：對于迭代過程如果在所求根的鄰近連續(xù)

15、，并且則該迭代過程在點鄰近是 階收斂的。*1*()*()()*11()01,()()( ) ()()()!( )()()!kkkppkkpppkkkpkxxxxxxxxxpexxxxxpep證：由于故具有局部收斂性。將在根處展開，由條件有定理4: 3.迭代收斂的加速方法*01021*1010*2121*1021*12 () () ()()()()()()()()( ),()()xxxxxxxxxxxxxxxxxxxLxxL xxxxL xxxxxx設(shè)是 根的 某 個 預(yù) 測 值 ， 通 過 兩 次 迭 代 校 正有 由 微 分 中 值 定 理 ， 有假 定改 變 不 大 ， 近 似 地 取 某

16、 個 近 似 值則 由*2*0212*1012()2xxxxxxxxxxx此 種 加 速 需 用 兩 次 迭 代 值 進(jìn) 行 加 工 。埃特金(Aitken)方法(P273)1112111111 () ()() 2kkkkkkkkkkkxxxxxxxxxxx如 果 將 一 次 改 進(jìn) 值 作 為 一 步 ，則 計 算 公 式 如 下 ：校 正再 校 正改 進(jìn)可以證明0lim*1xxxxkkk表明kxkx即為斯蒂芬森(Steffensen)迭代法 (P273)的收斂速度比的收斂速度快, 且為2階收斂的020000( )0 02f x xTaylor()f(x)f() (x-)()!fxxfxxx

17、x在真根附近點展開成級數(shù)：4. 牛頓(Newton)法 非線性問題的最簡單解法是線性近似. 將非線性方程線性化，以線性方程的解逐步逼近非線性方程的解，這就是Newton法的基本思想)0( 000011)()()f(xxxfxfxxx：作為近似根解出 , 2 , 1 , 0 ),()( Newton 1nfxfxxxnnnn法：依次產(chǎn)生迭代格式，稱00 000 xx)(xf)f(x:f(x)取線性部分近似代替 Newton 法的幾何解釋 )x(f)x(fxxx)y01011 0( x：為第二個近似根軸交點與000000 ,() ( ) ()()()ff xyfxxxxfxxx當(dāng)在取后（在真根附近

18、），過作的切線，則切線方程：)(xfy 0 x1x2x*x故也稱切線法 12* ( ) , ( )0,() ()( ) ( ) ( )( )( ) ( ) ( )( )(kkkkxxa bxfxxxfxfxxxfxfx fxxfxxfxfx迭代過程的收斂速度依賴于迭代函數(shù)的選取。如果當(dāng)時則該迭代過程只可能是線性收斂。 對牛頓公式其迭代函數(shù)為由于假定是的一個單根，即*)0,()0,()0,fxxx則由上式知由上述定理知，牛頓法在根的鄰近至少是平方收斂的。410 10. ( ) 1,( )(1)( ) ( )( )1 10.5kxxxxxkkkkxef xxefxexf xxexxxfxxxexx

19、xx例：用牛頓法解方程解：牛頓法迭代函數(shù)為牛頓公式為可先用二分法或經(jīng)驗確定迭代初值，再按牛頓公式進(jìn)行迭代。 Newton法具有收斂快，穩(wěn)定性好，精度高等優(yōu)點，是求解非 線性方程的有效方法之一。但它每次迭代均需計算函數(shù)值與 導(dǎo)數(shù)值，故計算量較大。而且當(dāng)導(dǎo)數(shù)值提供有困難時， Newton法無法進(jìn)行。(見P277表7-5)牛頓法應(yīng)用舉例21 01 ().2kkkCxCCCxxx對于給定正數(shù)，應(yīng)用牛頓法解二次方程即導(dǎo)出求開方值的計算程序02211221010202000 11 () ()22. ,2.1 0,1. kkkkkkkkkkkkkkkkkxxCxCxCxCxxxCxCxCxCxCxCxCxC

20、xCqqxCCxCqxqkxC 現(xiàn)證此迭代公式對于初值都是收斂的。由迭代公式得記對任意總有，故當(dāng)時，注 牛頓法每次計算)()(kkxfxf計算量較大1。簡化牛頓法（平行弦法）0)(1CxCfxxkkk若1)(1)(xfCx即2)(0 xfC在根x*附近成立，則迭代為局部收斂。P2802。牛頓下山法 即在牛頓迭代法的基礎(chǔ)上附加一個條件)()(1kkxfxf計算公式：)()(1kkkkxfxfxxkkkxxx)1 (11)()(1kkkkxfxfxx即5.弦截法與拋物線法11111 (),(),() ,( )0(),(),(),( ),( )0( )0 kkkkkkrkkkrrrkkf xf xf

21、xxxxf xf xf xf xpxpxf xxx基本思想：利用一些函數(shù)值來回避導(dǎo)數(shù)值的計算。設(shè)是的一組近似根，利用函數(shù)值構(gòu)造插值多項式并適當(dāng)選取的一個根作為的新的近似根，這就確定了一個迭代過程，記迭代函數(shù)為 ：1(,). 12kkkrxxxrr當(dāng)時為弦截法，當(dāng)時為拋物線法。一、弦截法 （P283）111111111111 ,( )0(),()( )( )0( )0.()() ( )()()() ().()()()kkkkkkkkkkkkkkkkkkkkkxxf xf xf xpxpxf xxf xf xpxf xxxxxf xxxxxf xf xf xxxf設(shè)是的近似根，利用構(gòu)造一次插值多項

22、式，并用的根作為的新的近似根由此迭代公式可看作牛頓公式11()()()( )kkkkkxf xf xfxxx中的導(dǎo)數(shù)用差商取代的結(jié)果。弦截法的幾何表示x0Xx*x1 x2 x3Y f(x)0P0P2 P111011 ,.,kkkkkxxxxxxx弦截法在求時要用到前面兩步的結(jié)果需兩個初值，而牛頓切線法在計算時，只用到前一步的值。弦截法收斂性定理 （P285）*01111* ( ):( )0,() ().()()151.618.2kkkkkkkf xxxxxfxxxf xxxxxf xf xpx定理：假設(shè)在根 的鄰域內(nèi)具有二階連續(xù)導(dǎo)數(shù)，且對任意有又初值那么當(dāng)鄰域 充分小時，弦截法將按階收斂到根1

23、1*11111*11111.11*1 ,()0( ),() ( )( )()()2()()()()()22 ( )0()kkkkkkkkkkkkxxxfxpxxxffxpxxxxxffpxxxxxe expxpx 證：用數(shù)學(xué)歸納法證明迭代值全屬于。首先證明當(dāng)時必屬于。設(shè)，是以為節(jié)點的插值多項式。由又由于是的根，故有*11111*11211()()( )()()()()().kkkkkkkkpxpxpxxfxfxxxfexx 1112121112111101().2(),m ax(),. .2 m in(),1, . . ,kkkkkkkxxkkkkkkfee efxxxxfxMfxMxxeMe

24、eMxxx 對 上 兩 個 式 子 聯(lián) 立由 于故 當(dāng)時記選 取 鄰 域充 分 小 以 保 證則 當(dāng)與屬 于時因由 數(shù) 學(xué) 歸 納 法 知kx一 切全 屬 于23224111223*111112* 1 ()0, () 2()().2()1kkkkkkkkkkkkkkkkkeM eeMeeMeeeMMkekfee eeMeeffxMfxeM 由遞推不等式故當(dāng)時有收斂性得證。當(dāng) 充分大時，由這里 令11.*,kzkkkdzzz則有差分方程111 11 111121211221212111* 101.618,0.618; , ,111 () kkkkkkkkkkkkkzcckzzzzzccc ckz

25、cedddMMM 方程是一差分方程，考慮的特解，其特征方程 為故差分方程的通解為（為任意常數(shù)） 由于當(dāng) 充分大時故 而1 1111*11*1*111 1 1.618.kkzckkkkkeddMMeeMeMMe，故有（）此說明弦截法收斂的階 迭代法加速（埃特金方法）*01021*1010*2121*1021*12 () () ()()()()()()()()( ),()()xxxxxxxxxxxxxxxxxxxLxxL xxxxL xxxxxx 設(shè)是根的某個預(yù)測值，通過兩次迭代校正有 由微分中值定理，有假定改變不大，近似地取某個近似值則由*2*0212*1012()2xxxxxxxxxxx此種加

26、速需用兩次迭代值進(jìn)行加工。用弦截法給出埃特金算法的幾何解釋( ) xx用弦截法討論形如得方程，給出埃特金算法的幾何解釋。 yx( )yx*P3P2P0P1P*x2x1x3x0 x332131301020213012*2013 ()2. ,.Pxxxxxxxxxx xxxxxxxxxxx點的坐標(biāo)滿足由此解出此即為加速埃特金公式從圖上可知 盡管迭代值比和更遠(yuǎn)偏離了但按上式定出的卻明顯地扭轉(zhuǎn)了這種發(fā)散的趨勢二、拋物線法 （P285）12221 ( )0,( ),( ),.kkkkf xxxxpxpxx設(shè)已知方程的三個近似根以這三點為節(jié)點構(gòu)造二次插值多項式并適當(dāng)選取的一個零點作為新的近似根 這樣確定的

27、迭代過程稱拋物線法 也稱密勒法( )f x2( )P x*x1kxkx1kx2kx拋物線法計算公式2112112112122 ( )(),() + ,()().,+ ,()()( )()kkkkkkkkkkkkkkkkkkkkkkkkkpxfxf xxxxf xxxxxxxaf xxxbf xxf xxxxxcfxpxaxx插 值 多 項 式令 22*2112()4224,.2sgn() 4kkkkkkkkkkkkkkkkkkkkkkkkkkkkkbxxcbba ccxxxabba cxxxxxxxxcbxxbba c在三 個 近 似 根 中 假 定更 接 近 根故 新 的 近似 根 應(yīng) 在鄰

28、 近 即較 小 于 是 拋 物 線 計 算 公 式 為*012* ,(), ()01.84 fxxxxxxxfxx可 以 證 明 如 果在 其 零 點鄰 近 三 階 連續(xù) 可 微 且 初 值充 分 接 近則 拋 物 線 法是 收 斂 的 。特 別 地 ， 若是 方 程的 單 根 ，收 斂 解 為。另 一 方 面 ， 在 收 斂 性 的 證 明 中 雖 然 要 求 初始 值 充 分 接 近 根， 但 實 際 計 算 表 明 ， 拋 物 線法 對 初 值 要 求 并 不 苛 刻 ， 在 初 值 不 太 好 的 情 況下 常 常 也 能 收 斂 。 缺 點 是 程 序 較 復(fù) 雜 ， 并 在 計算 實 根 的 過 程 中 ， 也 常 常 需 要 采 用 復(fù) 數(shù) 計 算 ，增 加()0fx了 工 作 量 。 因 此 ， 拋 物 線 法 適 用 于 當(dāng) 初 值不 太 好 時 求 方 程的 復(fù) 根 的 情 況 。三、代數(shù)方程的牛頓法01