數(shù)值計(jì)算方法

1、第二章非線性方程數(shù)值解法在科學(xué)計(jì)算中常需要求解非線性方程f(x)0即求函數(shù)f(x)的零點(diǎn).非線性方程求解沒有通用的解析方法，常采用數(shù)值求解算法.數(shù)值解法的基本思想是從給定的一個或幾個初始近似值出發(fā)，按某種規(guī)律產(chǎn)生一個收斂的迭代序列Xkk0,使它逐步逼近于方程的某個解.本章介紹非線性方程實(shí)根的數(shù)值求解算法：二分法、簡單迭代法、Newton迭代法及其變形，并討論它們的收斂性、收斂速度等.二分法一、實(shí)根的隔離定義設(shè)非線性方程中的f(x)是連續(xù)函數(shù).如果有X*使f(X*)0,則稱X*為方程的根，或稱為函數(shù)f(x)的零點(diǎn)；如果有f(x)(xx*)mg(x),且g(x)在x*鄰域內(nèi)連續(xù)，g(x*)0,m為

2、正整數(shù)，則稱x*為方程的m重根.當(dāng)m1時，稱x*為方程的單根.非線性方程根的數(shù)值求解過程包含以下兩步(1)用某種方法確定有根區(qū)間.稱僅存在一個實(shí)根的有根區(qū)間為非線性方程的隔根區(qū)間，在有根區(qū)間或隔根區(qū)間上任意值為根的初始近似值；(2)選用某種數(shù)值方法逐步提高根的精度，使之滿足給定的精度要求.對于第(1)步有時可以從問題的物理背景或其它信息判斷出根的所在位置，特別是對于連續(xù)函數(shù)f(x),也可以從兩個端點(diǎn)函數(shù)值符號確定出有根區(qū)間.當(dāng)函數(shù)f(x)連續(xù)時，區(qū)間搜索法是一種有效的確定較小有根區(qū)間的實(shí)用方法，其具體做法如下設(shè)a,b是方程的一個較大有根區(qū)間，選擇合適的步長h(ba)/n,xkakh,(k0,1

3、,L,n).由左向右逐個計(jì)算f(x),如果有f(xk)f(x1)0,則區(qū)間Xq練i就是方程的一個較小的有根區(qū)間.一般情況下，只要步長h足夠小，就能把方程的更小的有根區(qū)間分離出來；如果有根區(qū)間足夠小，例如區(qū)間長度小于給定的精度要求，則區(qū)間內(nèi)任意一點(diǎn)可視為方程的根的一個近似.例確定出方程f(x)X33X24x30的一個有根區(qū)間.解由f(x)3x26x43(x1)210知設(shè))為(，)上的單調(diào)遞增函數(shù)，進(jìn)而(刈在(，)內(nèi)最多只有一個實(shí)根.經(jīng)計(jì)算知f(0)0,f(2)0,所以f(x)0在區(qū)間0,2內(nèi)有惟一實(shí)根.如果希望將有根區(qū)間再縮小，可以取步長h0.5,在點(diǎn)x0.5,x1,x1.5計(jì)算出函數(shù)值的符號，

4、最后可知區(qū)間1.5,2內(nèi)有一個實(shí)根.二、二分法二分法是求非線性方程實(shí)根近似值的最簡單的方法.其基本思想是將有根區(qū)間分半，通過判別函數(shù)值的符號，逐步縮小有根區(qū)間，直到充分逼近方程的根，從而得到滿足一定精度要求的根的近似值.設(shè)f(x)在區(qū)間a,b上連續(xù)，f(a)f(b)0,且方程在區(qū)間(a,b)內(nèi)有惟一實(shí)根x.記aa,bb,中點(diǎn)x(aibi)/2將區(qū)間ai,bi分為兩個小區(qū)間a,x和xi,b,計(jì)算函數(shù)值f(x),根據(jù)如下3種情況確定新的有根區(qū)間：(1)如果f(x)0,則x是所要求的根;(2)如果f(ai)f(xi)0,取新的有根區(qū)間a2,b2a,x；(3)如果f(xi)f(bi)0,取新的有根區(qū)間

5、a2,b2xi,b.新有根區(qū)間&卜的長度為原有根區(qū)間ai,b1長度的一半.對有根區(qū)間ah施以同樣的過程，即用中點(diǎn)x2(a2d)/2將區(qū)間久再分為兩半，選取新的有根區(qū)間，并記為m,其長度為心的一半(如圖所示).重復(fù)上述過程，建立如下嵌套的區(qū)間序列a,bai,bi區(qū)上La-bjL其中每個區(qū)間的長度都是前一個區(qū)間長度的一半，因此法也的長度為ibkakjT7(ba)由xak,bk和%bk)/2,得*iixkx丑ak)r(ba)當(dāng)k時，顯然，有xkx*.總結(jié)得到如下收斂定理：定理設(shè)f(x)在隔根區(qū)間a,b上連續(xù)，且ff(b)0,則由二分法產(chǎn)生的序列Xkk0收斂于方程在a,b上的根x,并且有誤差估計(jì)*1,

6、、八.XkX(ba)(k1,2,L)2設(shè)預(yù)先給定根x*的絕對誤差限為,要求恢x*|,只要J(ba)成立，這樣求得對分次數(shù)2kln(ba)lnln2取k為大于(ln(ba)ln)/ln2的最小整數(shù).此時Xk是方程的滿足精度要求的根近似注：由于舍入誤差和截?cái)嗾`差存在，利用浮點(diǎn)運(yùn)算不可能精確計(jì)算函數(shù)值，二分法中的判斷f(Xk)0幾乎不可能滿足，取而代之為判斷條件f(Xk)0,其中0為根近似值的函數(shù)值允許誤差限.總結(jié)以上內(nèi)容，給出如下算法算法(二分法)輸入端點(diǎn)a,b、根的絕對誤差限、根近似值的函數(shù)值允許誤差限0；輸出近似解c或失敗信息；Step1用公式計(jì)算最大迭代次數(shù)k；Step2又tn1,L,k循環(huán)

7、執(zhí)行Step35;Step3c(ab)/2,計(jì)算f(c)；Step4若|f(c)0,則輸出c,end;Step5若f(c)f(b)0,則ac,否則bc.例用二分法求f(x)X34X2100在1,2上的根x*的近似值，要求Xkx*1103.2解由于在區(qū)間1,2上，f(1)5,f(2)14,f(x)3x28xx(3x8)0,故f(x)0在1,2上有惟一實(shí)根x*.確定循環(huán)次數(shù)為k11,利用二分法計(jì)算結(jié)果見表.表二分法計(jì)算結(jié)果k有根區(qū)間回,員Xkf(Xk)1,2,-3,4,-5,-6,-7,8,-9 ,10 ,1.11 1.,分法具有如下特點(diǎn)(1)優(yōu)點(diǎn)：計(jì)算簡單，對函數(shù)f(x)的光滑性要求不高，只要它

8、連續(xù)，且在兩端的函數(shù)值異號，算法收斂就可以保證；(2)缺點(diǎn)：只能求單實(shí)根和奇數(shù)重實(shí)根，收斂較慢，與1/2為公比的等比級數(shù)相同.當(dāng)函數(shù)f(x)連續(xù)時，方程的實(shí)重根可轉(zhuǎn)換為f(x)0的實(shí)單根.f(x)一般在求方程根近似值時不單獨(dú)使用二分法，而常用它為其它數(shù)值方法提供初化簡單迭代法簡單迭代法是求解非線性方程根的近似值的一類重要數(shù)值方法.本節(jié)將介紹簡單迭代法的基本思想、收斂條件、收斂速度以及相應(yīng)的加速算法.一、簡單迭代法的基本思想簡單迭代法采用逐步逼近的過程建立非線性方程根的近似值.首先給出方程根的初始近似值，然后用所構(gòu)造出的迭代公式反復(fù)校正上一步的近似值，直到滿足預(yù)先給出的精度要求為止.在給定的有根

9、區(qū)間a,b上，將方程等價變形為x(x)在a,b上選取天作為初始近似值，用如下迭代公式xk1(xk)(k0,1,2,L)建立序列凡k0.如果有l(wèi)im%x,并且迭代函數(shù)(x)在x的鄰域內(nèi)連續(xù)，對式k兩邊取極限，得*x(x)因而x是的根，從而也是的根.稱(x)為迭代函數(shù)，所得序列xJk。為迭代序列.將這種求方程根近似值的方法稱為簡單迭代法，簡稱迭代法.例試用方程f(x)x3x10的不同形式的變形建立迭代公式，并試求其在1.5附近根的近似值.解利用方程的變形建立如下4種迭代公式(1)Xk131Xk,(2)Xk1x：1取初值Xo1.5,迭代計(jì)算，結(jié)果見表.表迭代法計(jì)算結(jié)果k012345678公式(1)公

10、式(2)公式(3)公式(4)1091029108810265inf1012103810114inf例表明非線性方程的不同等價形式對應(yīng)不同的迭代過程，從某一初值出發(fā)，有的迭代收斂快，有的收斂慢，甚至不收斂.那么迭代函數(shù)(x)滿足什么條件時才能保證迭代序列收斂迭代序列Xjk。的誤差如何估計(jì)怎樣才能建立收斂速度快的迭代公式定理若函數(shù)(X)在區(qū)間a,b上具有一階連續(xù)導(dǎo)數(shù)，且滿足條件 對任意xa,b,有(x)a,b; 存在常數(shù)L：0L1,使得對任意xa,b有|(x)L成立.則(1)方程x(x)在a,b上有惟一實(shí)根x*對任意Xoa,b,迭代公式收斂，且JmXkxk迭代公式有誤差估計(jì)式*XkX*XkXL1L

11、LkXkXk1g(b)b(b)a,b時,(4)kimXk*(X)構(gòu)造函數(shù)g(X)x(x),由條件知g(a)a0,因此g(x)0在a,b上至少存在一個實(shí)根，又由條件(a)篤0,知當(dāng)g(x)1(x)1L0,所以g(x)0在a,b內(nèi)存在惟一實(shí)根，即(x)在a,b內(nèi)存在惟一實(shí)根,記為x*.(2)由X0a,b及條件知，%(x*),二者作差，并由微分中值定理得a,b(k1,2,L),并且有Xk1(Xk),其中，k介于為與x*Xk1X之間.結(jié)合條件，(Xk)覆*(X)k)(XkX)(k1,2,L)Xk1.*LXkx(k1,2,L)反復(fù)遞推，有0因0LXk11,故|im%由式得*X*XLXkL2XkLk1X0

12、(k1,2,L)從而又由于*XkXXkxk1xk1XkXk1Xk1XkLXkXkXk1XkXk1Xk|I(Xk)(Xk1)1I(k)(XkLXk其中k介于Xk和Xk1之間.綜合式及式得誤差估計(jì)X1Xk1(k1,2,L)由式反復(fù)遞推，得XkXk1并代入式得誤差估計(jì)Xk(4)由式得兩端取極限，并注意到*XkXXkXk1|LXk1Xk2LLk1X1X0Xk1LkX1%1L(k1,2,L)*Xk1XXk(X)的連續(xù)性和kimXk1*Xlimk*X(k)X*(因?yàn)閗介于X與Xk之間)，得*(X)誤差估計(jì)稱為后驗(yàn)誤差估計(jì)，也稱為誤差漸進(jìn)估計(jì),誤差估計(jì)稱為先驗(yàn)誤差估計(jì).定理?xiàng)l件成立時，對任意Xa,b,迭代序

13、列均收斂，故稱定理為全局收斂性定理.下面討論X*鄰近的收斂性，即局部收斂性.定理設(shè)存在方程X(X)根X*的閉鄰域U(x*,)X*,x*(0)以及小于1的正數(shù)L,使得(x)連續(xù)且|(x)L1.則對任意%U(x,),迭代Xki(凡)收斂.證明由(X)在U(x*,)內(nèi)連續(xù)，且有|(x)L1,則對任意xU(x*,),有(X)X*(x)(x*)(*)|xx*L由定理知迭代過程Xki(Xk)對任意初值XoU(x,)均收斂.二、迭代法的收斂階為刻畫迭代法收斂速度的快慢，引進(jìn)收斂序列的收斂階概念.定義設(shè)迭代序列Xkk0收斂到x,記ekXkx,如果存在常數(shù)c0和實(shí)數(shù)p1,使得lim-ek4ckekp則稱序列Xk

14、ko是P階收斂的.當(dāng)P1時，稱Xkk0為線性收斂的，此時要求0c1；p1為超線性收斂.p越大，序列Xkk0收斂到x*越快.c稱為漸進(jìn)常數(shù)，c越小，收斂越快.所以迭代法的收斂階是對迭代法收斂速度的一種度量.顯然，由定理(4)知，當(dāng)(X)0時簡單迭代法線性收斂，漸進(jìn)常數(shù)*c(X).算法(簡單迭代法)輸入初始值X0、容許誤差；輸出近似解X1或失敗信息；Step1又tn1,L,m循環(huán)執(zhí)行Step23;Step2x(%);Step3若X0I,則輸出x1,end;否則X0X1,轉(zhuǎn)向Step2.例求方程f(x)2xlgx70的最大實(shí)根的近似值，要求絕對誤差不超過1 1032 ,解(1)確定有根區(qū)間.方程等價

15、形式為2x7lgx作函數(shù)y2x7和ylgx的圖形，如圖所示，知方程的最大實(shí)根在區(qū)間3,4內(nèi).(2)建立迭代公式，判別收斂性.將方程等價變形為1,、x(lgx7)21迭代函數(shù)(x)1(lgx7),迭代公式Xk1-(lgXk7).2由（x）-0,x3,4,知（x）在區(qū)間3,4內(nèi)僅有一根.又2ln10x（3）3.74,（4）3.80,所以，當(dāng)x3,4時，（x）3,4.圖函數(shù)y2x7和ylgx的圖形因?yàn)長3rruax4|(x)0.07,所以對于一切x3,4有(x)(3)0.071由定理知，迭代法收斂.迭代計(jì)算.取4.0,有xi=3.801030,x2=3.789951,x3=3.789317,乂=3.

16、789280因?yàn)閰^(qū)x33103,所以方程的最大根x*x43.789280.三、迭代法的加速對于收斂的迭代序列，理論上迭代次數(shù)足夠多時，就可以使計(jì)算結(jié)果滿足任意給定的精度要求.但在應(yīng)用中，有的迭代過程收斂極為緩慢，計(jì)算量很大，因此研究迭代格式的加速方法是非常必要的.1 .線性收斂序列的Aitken加速法設(shè)xkk0是一個線性收斂的序列，極限為x.即有小于1的正數(shù)c使得x1x*kimrrc由于它線性收斂，誤差減少的速度較慢，值得采用加速技術(shù).下面介紹Aitken加速法.對充分大的k,有*xk1x次2x-c,rC人xxk1x由上面兩式得*xk1xxk2x*xkxxk1x解得2*XkXk2X1XXk22

17、xk1利用上式右端的值可定義另一序列XkXkykkYkXk2(Xk1Xk)Xk22Xk1Xk0,即得Aitken加速公式(Xk1Xk)2Xk22Xk1Xk它仍然收斂到X,但收斂速度更快.證明請參考文獻(xiàn)19.2.Steffensen迭代法Aitken加速方案是對任意線性收斂序列Xkk0構(gòu)建的，并不限定得.將Aitken加速方法用于簡單迭代法產(chǎn)生迭代序列時，得到著名的迭代法，具體迭代公式如下Xkk0如何獲SteffensenXk1(Xk)(s)(sXk)2Xkt2sXk(k0,1,2,L)或者直接寫成2(Xk)Xk)xk1Xk-(Xk)2(Xk)Xk(k0,1,2,L)可以證明Steffensen

18、迭代法在一定的條件下與原簡單迭代法的迭代序列具有相同的極限，但Steffensen迭代法收斂速度更快，可以達(dá)到二階收斂.證明請參考文獻(xiàn)19.例對例用Steffensen迭代法求方程根的近似值，要求xk1xk1108解(1)簡單迭代法將原方程化成x(10/(41210Xk14Xk易驗(yàn)證該迭代公式在區(qū)間1,2上滿足定理的條件,1、X)尸，建立迭代公式產(chǎn)生的迭代序列收斂.(2)Steffensen迭代法加速公式為12Xk1104Xk11024s(sXk)2xkt2sXk(k0,1,2,L)(1)取初值X01.5,簡單迭代法和Steffensen迭代法計(jì)算結(jié)果見表.注意：Steffensen迭代法每一

19、迭代步的計(jì)算量大約是原簡單迭代法計(jì)算量的兩倍.表簡單迭彳法和Steffensen迭代法計(jì)算結(jié)果k迭代法xk|Xk1Xk|Steffensen法Xk%1xj0110110121021053103101241045105610671078108910810109Newton迭代法Newton迭代法是求解非線性方程根的近似值的一種重要數(shù)值方法.其基本思想是將非線性函數(shù)f(x)逐步線性化，從而將非線性方程近似地轉(zhuǎn)化為一系列線性方程來求解.下面討論其格式的構(gòu)造、收斂性、收斂速度以及有關(guān)變形.設(shè)凡是方程的某根的一個近似值，將函數(shù)f(x)在點(diǎn)Xk處作Taylor展開f()2Xk)2!(xXk)Xk)0一、N

20、ewton迭代法的構(gòu)造f(x)f(Xk)f(Xk)(X取前兩項(xiàng)近似代替f(X),即用線性方程f(Xk)f(Xk)(X近似非線性方程.設(shè)f(Xk)0,則用線性方程的根作為非線性方程根的新近似值，即定義f(%)f(Xk)上式即是著名的Newton迭代公式.它也是一種簡單迭代法，其中迭代函數(shù)/、f(X)(x)Xf(X)即為曲Newton迭代法具有明顯的幾何意義(如圖所示).方程f(X)0的根x*線yf(x)與x軸的交點(diǎn)的橫坐標(biāo).設(shè)Xk是x*的某個近似值，過曲線yf(x)上相應(yīng)的點(diǎn)(Xk，f(Xk)作切線，其方程為yf(Xk)f(Xk)(xXk)它與X軸的交點(diǎn)橫坐標(biāo)就是Xki.只要初值X0取得充分靠近

21、根X,序列Xkk0就會很快收斂到X.所以Newton迭代法也稱為切線法.、收斂性定理設(shè)X*是方程的單根，在X*的鄰域上f(X)連續(xù)且f0,當(dāng)X0U(x,)x,x時，Newton法產(chǎn)生的序列xjk(X)0.則存在至少二階收斂.證明(1)Newton法迭代函數(shù)的導(dǎo)數(shù)為(X)f(x)f(j)f(X)2X*的某個閉鄰域U(x,顯然，(X)在X*鄰域上連續(xù).又(X*)0,一定存在當(dāng)xU(x,)時,有(X)L1從而Newton法產(chǎn)生白序列x/k0收斂.將f(x)在處作一階Taylor展開.*_0f(X)f(%)f(Xk)(xXk)f(k)(X2!Xk)2其中k介于x*與Xk之間.又由Newton迭代公式有

22、f(Xk)f(練)(練1Xk)式與式相減從而kim*Xk1X*2(XkX)*f(X)*2f(x)由迭代法收斂階的定義知，Newton迭代法至少具有二階收斂速度.上述定理給出了Newton法局部收斂性，它對初值要求較高，初值必須充分靠近方程根時才可能收斂，因此在實(shí)際應(yīng)用Newton法時，常常需要試著尋找合適的初值.下面的定理則給出Newton法在有根區(qū)間上全局收斂的一個充分條件.定理設(shè)x*是方程在區(qū)間a,b上的根且f(x)在a,b上存在，如果對于任意xa,b有，f(x)0f(x)0;(2)選取初值xoa,b,使f(xo)f(xo)0.則Newton法產(chǎn)生的迭代序列x0單調(diào)收斂于x*,并具有二階收

23、斂速度.證明滿足定理?xiàng)l件(1)共有4種情形，如圖所示.下面僅以圖(a)情況進(jìn)行證明，此時滿足對任意xa,b有，f(x)0,f(x)0,初值xx.首先用數(shù)學(xué)歸納法證明x30有下界x.當(dāng)k0時，%x*成立.假設(shè)kn時，不等式xnx*成立.將f(x)在x.處作一階Taylor展開，得*T()*2*f(x)f(xn)f(xn)(xxn)(x%)0,n(x,x.)于是xnf(xn)f(n)(x/f(xn)2f(xn)()又由Newton迭代公式，有式右端的第二項(xiàng)大于零，因此其次證明8k0單調(diào)遞減.Xn1X*,由數(shù)學(xué)歸納法知由f(x)0,Xkx,f(x)0知，f(Xk)0,f(x)式的第二項(xiàng)大于零，從而*

24、f(n)*2xxn127K5(xxn)xkx,(k0,1,2,L).0,于是Newton迭代公xkxk1故迭代序列xJk0單調(diào)減少.序列xkk0單調(diào)減少有下界x*,它必有極限，記為父,它滿足x*?x。，進(jìn)而有a,b.對a1xkf(x)兩端取極限，并利用f(x),f(x)的連續(xù)性，得f(練)f(?)=0.結(jié)合函數(shù)f(x)在a,b上的單調(diào)性知?x*.因此，Newton法產(chǎn)生的迭代序列5冊單調(diào)收斂于x,利用式及式知該Newton迭代序列二階收斂.算法(Newton迭代法)輸入初始近似值小、容許誤差；輸出近似解為或失敗信息；Step1又tn1,L,m循環(huán)執(zhí)行Step23;Step2x%f(%)/f(x

25、o);Step3若xol,則輸出x1，end;否則xx1,轉(zhuǎn)向step2.例利用非線性方程x230的Newton迭代公式計(jì)算J3的近似值，使得xn%J108,并證明對任意解(1)建立計(jì)算公式xk1(0,)，xk1一(xk2x232xkxk(k0,1,2,L)其中0.(2)判斷收斂性在區(qū)間(0,)內(nèi)，f(x)2x在足夠大的M,使得x而,M.收斂于石.當(dāng)選取初值%(0,同時，x10,f(x)由定理知,20,當(dāng)選取初值xo,)時，存該迭代公式產(chǎn)生的迭代序列xkk0都2(x0$這樣，從x起，以后的練(k2)都大于布.故該迭代公式對任何初值為0都收斂.(3)取初值為2,迭代計(jì)算，結(jié)果見表.從表可見，迭代

26、4步后已經(jīng)滿足精度要求，精確解,31.7320508075B888L表Newton法計(jì)算結(jié)果nXnXnXn10212.510121.785714310-239.204712810-442.445850010-8三、Newton迭代法的變形Newton迭代格式構(gòu)造容易，迭代收斂速度快，但對初值的選取比較敏感，要求初值充分接近真解，另外對重根收斂速度較慢(僅有線性收斂速度)，而且當(dāng)函數(shù)復(fù)雜時，導(dǎo)數(shù)計(jì)算工作量大.下面從不同的角度對Newton法進(jìn)行改進(jìn).1Newton下山算法Newton迭代法的收斂性依賴于初值m的選取，如果m偏離x*較遠(yuǎn)，則Newton迭代法有可能發(fā)散，從而在實(shí)際應(yīng)用中選出較好的初

27、值有一定難度，而Newton下山法則是一種降低對初值要求的修正Newton迭代法.方程的根X*也是f(x)的最小值點(diǎn)，若把|f(x)看成f(x)在X處的高度，則X是山谷的最低點(diǎn).若序列Xkk0滿足單調(diào)性條件f(Xk1)|f(Xk)則稱Xkk0為稱為f(x)的下山序列.在Newton迭代法中引入下山因子(0,1,將Newton迭代公式修正為Xk1Xk-f(k0,1,2,L)f(Xk)適當(dāng)選取下山因子，使得單調(diào)性條件成立，即稱為Newton下山法.對下山因子的選取是逐步探索進(jìn)行的.一般地，從1開始反復(fù)將因子的值減半進(jìn)行試算，一旦單調(diào)性條件成立，則稱下山成功；反之，如果在上述過程中找不到使條件成立的

28、下山因子，則稱下山失敗”，這時可對Xk進(jìn)行擾動或另選初值X。，重新計(jì)算.2針對重根情形的加速算法假設(shè)X是方程的m(2)重根，并且存在函數(shù)g(x),使得有-，、，*、m，、，*、一f(X)(XX)g(x),g(x)0式中g(shù)(x)在x*的某鄰域內(nèi)可導(dǎo)，則Newton迭代函數(shù)*m*/f(X)(XX)g(X)(XX)g(x)(X)XX*、m1,、*、mX*、f(x)m(xx)g(x)(xx)g(x)mg(x)(xx)g(x)其導(dǎo)數(shù)在x*處的值*(X)lim.-(:xxxx*(X)Xlim.一，*、，、(XX)g(x)v*xmg(x)(xx)g(x)lim.1XXXXg(x)*XX11mg(x)(xx)

29、g(x)m由定理知Newton迭代法此時只有線性收斂速度.為了加速收斂，可以采用如下兩種方法方法一令(X)f獨(dú)，則X.是方程f(X)(x)0的單根，將Newton迭代函數(shù)修(x)X兇X(X)f(x)f(X)f(X)2f(x)f(X)因此有重根加速迭代公式Xk1Xk-ff(Xk)f(Xk)(Xk)f(Xk)f(Xk)(k0,1,2,L)它至少二階收斂.方法二將Newton迭代函數(shù)改為(X)這時(x)0,由此得到加速迭代公式Xk1f(Xk)Xkmf(Xk)(k0,1,2,L)3割線法Newton法每步需要計(jì)算導(dǎo)數(shù)值f(X).如果函數(shù)f(X)比較復(fù)雜時，導(dǎo)數(shù)的計(jì)算量比較大，此時使用Newton法不方

30、便.為了避免計(jì)算導(dǎo)數(shù)，可以改用平均變化率ff(Xk1)替換Newton迭代公XkXk1式中的導(dǎo)數(shù)f(Xk),即使用如下公式Xk1Xkf(Xk)(XkXk1)f(Xk)f(Xk1)上式即是割線法的迭代公式.依次用割線方程割線法也具有明顯的幾何意義，如圖所示,yf(Xk)f(Xk)f(Xk1)(xXk)XkXk1的零點(diǎn)逐步近似曲線方程f(x)0的零點(diǎn).割線法的收斂速度比Newton法稍慢一點(diǎn)，可以證明其收斂階約為，證明請參考文獻(xiàn)4.此外在每一步計(jì)算時需要前兩步的信息天,Xk1,即這種迭代法也是兩步法.兩步法在計(jì)算前需要提供兩個初始值x。與x.圖割線法的幾何意義例已知方程f(x)X44X240有一個二重根夜，分別用Newton法和重根Newton法和求其近似值，要求區(qū)xn解f(x)4x3Newton法得Newton法得Newton法得8x,f(x)12x212f(x)106(x)2X4xXk1XkXkxk1Xk利用上述三種迭代格式，取初值2Xk4Xk_2_3xk24Xk(k0,1,2,L)Xk(x22)x224%X22(k0,1,2,L)X22XkX22Xk(k0,1,2,L)Xo1.4,分別計(jì)算，結(jié)果見表.Newton法和重根Newton法計(jì)算結(jié)果k0123M10M1415式Xk式Xk式Xk知識結(jié)構(gòu)圖非線性方程數(shù)值解法基本概念(單根