第2章 方程的近似解法.doc

第二章方程求根在許多實(shí)際問題中，常常會遇到方程f(x)=0求解的問題。當(dāng)f(x)為一次多項(xiàng)式時(shí)，f(x)=0稱為線性方程，否則稱為非線性方程。對于非線性方程，由于f(x)的多樣性，求其根尚無一般的解析方法可以使用，因此研究非線性方程的數(shù)值解法是十分必要的。本章主要介紹求非線性方程根的一些常用方法。它們是增值尋根法、二分法、迭代法、牛頓法及割線法。這些方法均是知道根的初始近似值后，進(jìn)一步把根精確化，直到達(dá)到所要求的 精度為止。也即求非線性方程根的數(shù)值方法。第一節(jié) 第一節(jié) 增值尋根法與二分法2.1.1 增值尋根法 設(shè)非線性方程f(x)=0的根為，增值尋根法的基本思想是，從初始值開始，按規(guī)定 的一個(gè)初始步長h來增值。令 =+h(n=0,1,2，)，同時(shí)計(jì)算f()。 在增值的計(jì)算過程中可能遇到三種情形：(1) f()=0，此時(shí)即為方 程的根。(2) f()和f()同符號。這說明區(qū)間, 內(nèi)無根。(3) f()和f()異號，即有f()f()0 此時(shí)當(dāng)f(x)在區(qū)間, 上連續(xù)時(shí)，方程f(x)=0在, 一定有根。也即我們用增值尋根法找到了方程根的存在區(qū)間，或均可以視為根的近似值。下一步就是設(shè)法在該區(qū)間內(nèi)尋找根 更精確的近似值，為此再用增值尋根法 把作為新的初始近似值，同時(shí)把步長縮小，例如選新步長，這 樣會得到區(qū)間長度更小的有根區(qū)間，從而也得到使f(x)更接近于零的，作為更 精確的近似值，若精度不夠，可重復(fù)使用增值尋根法，直到有根區(qū)間的長度-(為所要求的精度)為止。此時(shí)f()或f()就可近似認(rèn)為是零。或就是滿足精度的方程的近似根（如圖2-1）. 21例1 用增值尋根法求方程f(x)=-10=0的有根區(qū)間。解 取=-4，h=1，則計(jì)算結(jié)果如下表2-1：表 2-1x-4-3-2-1012f(x)-10-1-2-7-10-514所以f(x)=0的有根區(qū)間為(1，2).再取=1，h=0.1，計(jì)算結(jié)果如表2-2： 表2-2x11.11.21.21.4f(x)-5-3.829-2.512-1.0430. 584所以 f(x)=0 更進(jìn)一步的有根區(qū)間為(1.3，1.4)2.1.2 二分法 設(shè)f(x)在區(qū)間a,b上連續(xù)，且f(a)f(b)0，則由連續(xù)函數(shù)性質(zhì)知，方程f(x)=0在(a ,b)內(nèi)至少有一實(shí)根，為以下討論方便，設(shè)(a,b)內(nèi)僅有唯一實(shí)根。二分法的基本思想 就是逐步對分區(qū)間a,b，通過判斷兩端點(diǎn)函數(shù)值乘積的符號，進(jìn)一步縮小有根區(qū)間，將有根區(qū)間的長度縮小到充分小，從而求出滿足精度的根的近似值，如圖。 2-2 具體做法 如下：用區(qū)間a,b的中點(diǎn)平分區(qū)間，并計(jì)算f()，同時(shí)記(,)=(a,b)，如果恰好有f()=0，則我們已經(jīng)找到方程的根= 。如若不然，f()0，如果f()f()0，則記(,)=(, ),如果f() f()0，則記(,)=(, )，在后兩種情形區(qū)間(,)為新的有根區(qū) 間。它包含在舊的有根區(qū)間(,)內(nèi)，其區(qū)間長度是原區(qū)間的一半。對區(qū)間(，)施行同樣的辦法。即平分區(qū)間，求中點(diǎn)判斷函數(shù)值乘積的符號，得到新的有根區(qū)間(,)，它包含在區(qū)間(,)內(nèi)，其區(qū)間長度是(,)的，(,)的。如此重復(fù)n次，如果還沒有找到方程的精確根，此時(shí)我們得到方程的有根區(qū)間序列：(,)，(,)，,()，它滿足(,)(, ) ()f()f()0-=,n=1,2,n-1當(dāng)n充分大時(shí)，()的長度縮小到充分小，此時(shí) 它的中點(diǎn)與夾在與之間，它們的距離也充分小，且序列滿足： 上式表明=(2)即 序列以等比數(shù)列的收斂速度收斂于。同時(shí)也表明序列是的一個(gè) 近似值序列。因此對任意給定的精度0，總存在n，使此時(shí),我們可以取作為的近似值，即可滿足 精度。例2 用二分法求方程f(x)=0在1，2內(nèi)的一個(gè)實(shí)根，且要求滿足精度解 用二分法計(jì)算結(jié)果如表2-3：nf()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. 3671875 0.0323681.3593751.36718751.36328125-0.0321591.363281251.36718751.3652343750.000072101.363281251.3652343751.364257813-0.01605111.3642578131.3652343751.364746094-0.00799迭代11次，近似根=1.364746094即為所求，其誤差這種方法的優(yōu)點(diǎn)是簡單，對f(x)只要求連續(xù)。它的收斂速度與 比值為的等比級數(shù)相同，它的局限性是只能用于求實(shí)根，不能用于求 復(fù)根及偶數(shù)重根。迭代法的基本思想由函數(shù)方程f(x)=0，構(gòu)造一個(gè)等價(jià)方程：x=(1)從某個(gè)近似根出發(fā)，令， n=0,1,2， (2)可得到序列，若收斂，即lim=只要連續(xù)，有也即從而可知是方程(1)的根，也就是f(x)=0的根。此時(shí)就是 方程(1)的一個(gè)近似解序列，n越大，的近似程度就越好。若發(fā)散，則迭代 法失敗。例1用迭代法求方程f(x)=-10=0在1,2 內(nèi)的一個(gè)近似根，取初始近似值.表2-4 n(1)(2)(3)(4)01.51.51.51.51-0.8750.81651.286953771.3483997326.7322.99691.402540801.367376373-469.7(-8.651.345458381.3649570141.031.375170251.3652647551.360094191.3652255961.367846971.36522305871.363887001.3652299481.365916731.3652300291.364878221.36523001101.36541006151.36522368201.36523024231.36522998251.36523001解原方程的等價(jià)方 程可以有以下不同形式：(1)(2)(3)(4)對應(yīng)的迭代公式有：(1) (2 ) (3) (4) 取，列表計(jì)算如表2-2。 與上節(jié)二分法比較，(3)、(4)都得到較好的結(jié)果 ，而用二分法達(dá)到同樣的精度，需要迭代27次，同時(shí)也看出迭代函數(shù)構(gòu)造不同，收斂速度也不盡相同，迭代函數(shù)構(gòu)造不當(dāng)(如(1)，(2)，序列就不收斂。 二 迭代法的幾何意義以上可以看到迭代法可能收斂，也可能不收斂。一般來說從f(x)=0，構(gòu)造不止一種，有的收斂，有的不收斂，這取決于的性態(tài)。方程x=的根，在幾何上就是直線 y=x與曲線y=交點(diǎn)的橫坐標(biāo),如圖2-3所示。 （a） （b） （c） （d）圖2-3中(1)、(2)收斂，(3)、(4)發(fā)散。 三 迭代法收斂的條件定義1 如果在根的某個(gè)鄰域B=B，迭代過程，n=0,1,2，收斂，則 稱迭代過程在附近局部收斂。定理1 設(shè)=()，在的某個(gè)鄰域B內(nèi)連續(xù)，并且q1，則對任何 B，由迭代公式?jīng)Q定的迭代序列收斂于。且-(3)-(4)證：由拉格朗日中值定理，存在B，使由已知q,從而得-q- 所以這樣我們就證明了收斂于。再由拉格朗日中值定理，存在，使=()所以qq (5) 又由于=()+() +()+所以(q+q+q+1)=令p+,有-也即- 這樣(4)式得證。再由(5)得- 這樣(3)式也得證。這個(gè)定理是一個(gè)很實(shí)用的收斂定理。一方面它可以判定我們所構(gòu)造的迭代函數(shù)是否收斂。另一方面(3)式還可以估計(jì)迭代次數(shù)。但結(jié)果偏保守，次數(shù)也偏大，實(shí)際中很少用。通常由(4)式，當(dāng)(為給定精度)時(shí)，認(rèn)為-就是滿足精度的一個(gè)近似解了。定理2HTSS對于方程x=,如果滿足(1)對任意x a,b，有a,b(2)對任意xa,b，有(x) q1不收斂(2) 5.1281不收斂ZK (3) 0.6561 收斂 (4) 0.1221收斂)上例說明值越小，收斂速度就越快。四 迭代法的收斂速度用迭代法求方程的近似根，我們不僅要構(gòu)造適當(dāng)?shù)囊笏諗?，而且還需要知道它的收斂速度。關(guān)于收斂速度，有如下定義：定義2 設(shè)序列x收斂于，令=- x，若存在某實(shí)數(shù)p1 及正常數(shù)C，使(6)則稱序列x階收斂。如果序列x是由=(x) 產(chǎn)生的，且p階收斂，則稱這種迭代過程是p階收斂的。當(dāng)p=1 ，且C 1時(shí)，稱為線性收斂；當(dāng)p=2時(shí)，稱為平方收斂(或二次收斂)；當(dāng)1p2時(shí)，稱為超線性收斂。同前面一樣，設(shè), =(x) ,=()則有-=(- x) (在在與x之間)所以=因而=|(n)若00 (n)此時(shí)迭代過程為二階收斂。定 理3 設(shè)在x=的根鄰近有連續(xù)的p階導(dǎo)數(shù)，當(dāng)1，且()0時(shí)，迭代過程=( x)為線性收斂；而當(dāng)()=0， ()0時(shí)為二階收斂。一般來說，若()=()=()=0，而()0，則稱=(x)在附近為p階收斂。第三節(jié) 迭代收斂的加速從f(x)=0構(gòu)造出的迭代格式x=(x)可能收斂也可能不收斂，在收斂的情形，收斂速度也取決于(x)的大小，當(dāng)(x)接 近于1時(shí)，收斂可能很慢。后兩種情形都影響迭代法的應(yīng)用。能否從x=(x)出發(fā)構(gòu)造出 新的迭代形式，使收斂速度加快呢?一 松馳法對x=(x)引入一個(gè)任意常數(shù)作為參數(shù),并假設(shè)-1，在方程兩邊加上x,得(1+)x=x+(x) 于是x=(x) (1)顯然方程 (1)與方程x=(x) 等價(jià)，若令(x)=(x)，(1)可寫成x=(x) (2)為了使得用x=(x)作迭代比用x=( x)作迭代收斂的更快，我們希望|(x)比(x)更小，又由于 (x)=(3)若(x)連續(xù)，則當(dāng)x在根x*附近時(shí)， (x)也在(x*)附近，為此選取=-(x*)。這樣可以使 得 |(x)較小。但在求解過程中x*未知，故用x來代替，只要-()-1，記，于是代入(1)有松弛法迭代公式： x(n=0,1,2,) (4) 稱為松弛因子。松弛法的加速效果是明顯的，甚至不收斂的迭代函數(shù)經(jīng)加速后一般也能獲得收斂。二 埃特金方法用松弛法計(jì)算時(shí)，要先算(x)，在使用時(shí)有時(shí)不太方便，假若在求 得x以后，先求出和再利用和構(gòu)造格式-由此得到埃特金（Altk en）公式：= =() -(n=0,1, 2，) (5)它的加速效果也十分明顯。例1 分別用松弛法、 埃特金法求方程-10=0在初 值附近的一個(gè)根，取迭代格式解用松弛法計(jì)算，取因此松弛法的迭代公式為 n=0,1,2，列表計(jì)算如下：表2- 3n01230.8908036860.8871231410.8871308691.51.3649539161.3652300121.365230013用埃特金方法計(jì) 算，迭代格式為n=0,1,2， 列表計(jì)算如下：表2-4n01230.8908036860.8871231410.8871308691.51.3649539161.3652300121.365230013與上節(jié)例1中(3)與(4)相比收斂 速度明顯加第四節(jié) 第四節(jié) 牛頓法解非線性方程f(x)=0的牛頓(Newton) 法，就是將非線性方程線性化的一種方法。它是解代數(shù)方程和超越方程的有效方法之 一。一 牛頓法的基本思想把非線性函數(shù)f(x)在處展開成 泰勒級數(shù)f(x)=f()+(x-)f()+(x-)+ 取其線性部分，作為非線性方程f(x)=0的近似方程，則有f()+(x-) f()=0設(shè)f()0，則其解為x=- (1)再把f(x)在x處展開為泰勒級數(shù)，取其線性部分為f(x)=0的近似方程，若f(x) 0，則得x=-如此繼續(xù)下去，得到牛頓法的迭代公式：x=- (n=0,1,2,) (2)例1 用牛頓法求方程f(x)=x+4x-10=0在1,2內(nèi)一個(gè)實(shí)根，取初始近似值x=1.5。 解 f(x)=3x+8x所以迭代公式為：x=- n=0,1, 2，列表計(jì)算如下：n01231.51.37333331.365262011.36523001二 牛頓法的幾何意義方程f(x)=0的根就是曲線y=f(x)與x軸交點(diǎn)的橫坐標(biāo)x*，當(dāng)初始近似值選取后，過(,f()作切線，其切線方程為：y- f()=f()(x-)它與x軸交點(diǎn)的橫坐標(biāo)為x=-一般地，設(shè)是x*的第n次近似值，過(,f()作y=f(x)的切線，其切線與x軸交點(diǎn)的橫坐標(biāo)為：x=-即用切線與x軸交點(diǎn)的橫坐標(biāo)近似代曲線與x軸交點(diǎn)的橫坐標(biāo)，如圖2-4。2-4 牛頓法正因?yàn)橛写嗣黠@的幾何意義，所以也叫切線法。三 牛頓法的收斂性及收斂速度定理 設(shè)f(x)在a,b 滿足(1) (1) f(a)f(b)0，、xa,b，則方程f(x)=0在a,b上有且只有一個(gè)實(shí)根，由牛頓法迭代公式計(jì)算得到的近似解序列收斂于方 程f(x)=0的根x*。由方程f(x)=0得到的牛頓迭代形式x=x-= =1- =由于f(x*)=0，所以當(dāng)f(x*)0時(shí)，(x* )= 0，牛頓法至少是二階收斂的，即牛頓法在單根附近至少是二階收斂的，在重根附近是線性收斂的。牛頓法收斂很快，而且可求復(fù)根，缺點(diǎn)是對重根收斂較慢，要求函數(shù)的一階導(dǎo)數(shù)存在。四 牛頓二階導(dǎo)數(shù)法這里將簡單介紹一下牛頓二階導(dǎo)數(shù)法。對其幾何意義及收斂性不作詳細(xì)的敘述，讀者可仿照牛頓法進(jìn)行討論，其基本思想是： 將f(x)在處展開泰勒級數(shù)f(x)=f()+f()(x-)+f()(x-)+取右端前三項(xiàng)近似代替f(x)，于是得f(x)=0的近似方程為f()+f()(x-)+f()(x-)=0也即f()+(x-)f()+f()(x-) =0 (3)設(shè)其解為.利用(1)，-=-，代入(3)中括號內(nèi)-,則得f()+(-) f()+f() =0于是解出，得=-重復(fù)以上過程得：=-于是得牛頓二階導(dǎo)數(shù)法的迭代公式為：=- n=0,1,