數(shù)值分析ppt第7章 非線性方程求根

1、上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁第第7章章 非線性方程求根非線性方程求根 7.1 方程求根與二分法方程求根與二分法 7.2 迭代法及其收斂性迭代法及其收斂性 7.3 迭代收斂的加速方法迭代收斂的加速方法 7.4 牛頓法牛頓法 7.5 弦截法與拋物線法弦截法與拋物線法 7.6 解非線性方程組的牛頓迭代法解非線性方程組的牛頓迭代法上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁7.1 方程求根與二分法方程求根與二分法 例如例如代數(shù)方程代數(shù)方程 x5- -x3+24x+1=0, 超越方程超越方程 sin(5x2)+e- -x=0. 對于不高于對于不高于4次的代數(shù)方程已有求根公式，而次

2、的代數(shù)方程已有求根公式，而高于高于4次的代數(shù)方程則無精確的求根公式，至于超次的代數(shù)方程則無精確的求根公式，至于超越方程越方程 就更無法求出其精確的解，因此，如何求就更無法求出其精確的解，因此，如何求得滿足一定精度要求的方程的近似根也就成為迫得滿足一定精度要求的方程的近似根也就成為迫切需要解決的問題，為此，本章介紹幾種常見的切需要解決的問題，為此，本章介紹幾種常見的非線性方程的近似求根方法非線性方程的近似求根方法.上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁7.1.1 引言引言本章主要討論本章主要討論單變量非線性方程單變量非線性方程f(x)=0 (1.1)的求根問題，這里的求根問題，這里xr

3、, f(x)ca, b. 在科學(xué)與工程在科學(xué)與工程計算中有大量方程求根問題，其中一類特殊的問題計算中有大量方程求根問題，其中一類特殊的問題是多項式方程是多項式方程)2 . 1(),0()(01110 aaxaxaxaxfnnnn其中系數(shù)其中系數(shù)ai(i=0,1,n)為實數(shù)為實數(shù).上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁方程方程f(x)=0的的根根x*，又稱為函數(shù)又稱為函數(shù)f(x)的的零點零點，它使得，它使得f(x*)=0，若，若f(x)可分解為可分解為f(x)=(x- -x*)mg(x)，其中其中m為正整數(shù)，且為正整數(shù)，且g(x*)0. 當(dāng)當(dāng)m=1時，則稱時，則稱x*為單為單根，若根，

4、若m1稱稱x*為為(1.1)的的m重根重根，或，或x*為函數(shù)為函數(shù)f(x)的的m重零點重零點. 若若x*是是f(x)的的m重零點重零點，且，且g(x)充分光滑，則充分光滑，則當(dāng)當(dāng)f(x)為代數(shù)多項式為代數(shù)多項式(1.2)時，根據(jù)代數(shù)基本定理時，根據(jù)代數(shù)基本定理可知，可知，n次代數(shù)方程次代數(shù)方程f(x)=0在復(fù)數(shù)域有且只有在復(fù)數(shù)域有且只有n個根個根(含含復(fù)根，復(fù)根，m重根為重根為m個根個根). 0)(, 0)()()()()1( xfxfxfxfmm上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁n=1,2時方程的根是大家熟悉的，時方程的根是大家熟悉的，n=3,4時雖有求時雖有求根公式但比較復(fù)雜

5、，可在數(shù)學(xué)手冊中查到，但已不適根公式但比較復(fù)雜，可在數(shù)學(xué)手冊中查到，但已不適合數(shù)值計算，而合數(shù)值計算，而n5時就不能用公式表示方程的根時就不能用公式表示方程的根.因因此，通常對此，通常對n3的多項式方程求根與一般連續(xù)函數(shù)方的多項式方程求根與一般連續(xù)函數(shù)方程程(1.1)一樣都可采用迭代法求根一樣都可采用迭代法求根.迭代法要求給出根迭代法要求給出根x*的一個近似，若的一個近似，若f(x)ca, b且且f(a)f(b)0，根據(jù)連續(xù)函數(shù)性質(zhì)中的介值定理可知方，根據(jù)連續(xù)函數(shù)性質(zhì)中的介值定理可知方程程f(x)=0在在(a, b)內(nèi)至少有一個實根，這時稱內(nèi)至少有一個實根，這時稱a, b為方為方程程(1.1)

6、的的有根區(qū)間有根區(qū)間，通?？赏ㄟ^，通?？赏ㄟ^逐次搜索法逐次搜索法求得方程求得方程(1.1)的有根區(qū)間的有根區(qū)間.上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁 若若 f(x)在在a,b內(nèi)連續(xù)內(nèi)連續(xù), 且且 f(a) f(b)0, f(0)=10, f(3)=- -260. 可見可見f(x)僅有兩個實根僅有兩個實根, 分別位于分別位于(0, 3), (3, +), 又又f(4)=10, 所以第二根的隔根區(qū)間可縮小為所以第二根的隔根區(qū)間可縮小為(3, 4). 以上分析可用下表表示以上分析可用下表表示x(- -,0) 0 (0,3) 3 (3,4) 4 (4,+) f (x) f (x) - -

7、0+ - - 0- -+ + 隔根區(qū)間隔根區(qū)間(0,3)(3,4)上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁2. 逐步搜索法逐步搜索法 從區(qū)間從區(qū)間a, b的左端點的左端點 a 出發(fā)出發(fā), 按選定的步長按選定的步長h 一步步向右搜索，若一步步向右搜索，若f(a+jh)f(a+(j+1)h)0 (j=0,1,2,)則區(qū)間則區(qū)間a+jh, a+(j+1)h內(nèi)必有根內(nèi)必有根. 搜索過程也可從搜索過程也可從b開開始，這時應(yīng)取步長始，這時應(yīng)取步長 h0.上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁7.1.2 二分法二分法 設(shè)設(shè)f(x)在區(qū)間在區(qū)間a, b上連續(xù)上連續(xù), f(a)f(b)0, 則

8、在則在a, b 內(nèi)有方程的根內(nèi)有方程的根. 取取a, b的中點的中點 將區(qū)間一分為二將區(qū)間一分為二. 若若 f (x0)=0, 則則x0就是方程的根就是方程的根, 否則判別根否則判別根 x*在在 x0 的的左側(cè)左側(cè)還是還是右側(cè)右側(cè)., )(210bax 若若f(a) f(x0)0, 則則x*(a, x0), 令令 a1= a, b1=x0;若若f(x0) f(b)0, 則則x*(x0 , b), 令令 a1=x0, b1=b. . 不論出現(xiàn)哪種情況不論出現(xiàn)哪種情況, (a1, b1)均為均為新的有根區(qū)間新的有根區(qū)間, 它它的的長度只有原有根區(qū)間長度的一半長度只有原有根區(qū)間長度的一半, 達(dá)到了達(dá)

9、到了壓縮有根壓縮有根區(qū)間區(qū)間的目的的目的.上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁 對壓縮了的有根區(qū)間對壓縮了的有根區(qū)間, 又可實行同樣的步驟又可實行同樣的步驟, 再壓再壓縮縮. 如此反復(fù)進(jìn)行如此反復(fù)進(jìn)行, 即可的一系列即可的一系列有根區(qū)間套有根區(qū)間套 ,11nnbababa 由于每一區(qū)間都是前一區(qū)間的一半，因此區(qū)間由于每一區(qū)間都是前一區(qū)間的一半，因此區(qū)間an , bn的長度為的長度為)(ababnnn 21若每次二分時所取區(qū)間中點都不是根，則上述過程將若每次二分時所取區(qū)間中點都不是根，則上述過程將無限進(jìn)行下去無限進(jìn)行下去. 當(dāng)當(dāng) n 時，區(qū)間必將最終收縮為一時，區(qū)間必將最終收縮為一點

10、點x* ，顯然，顯然x*就是所求的就是所求的根根.上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁 若取區(qū)間若取區(qū)間an , bn的中點的中點)(nnnbax 21作為作為x*的近似值，則有下述的近似值，則有下述誤差估計式誤差估計式111*()()22nnnnxxbaba 只要只要 n 足夠大足夠大, (即區(qū)間二分次數(shù)足夠多即區(qū)間二分次數(shù)足夠多)，誤差就可，誤差就可足夠小足夠小.),(,*11 nnnbaxx 由于在偶重根附近曲線由于在偶重根附近曲線 y=f(x) 為上凹或下凸為上凹或下凸, 即即 f(a)與與f(b)的符號相同的符號相同, 因此因此不能用二分法求偶重根不能用二分法求偶重根.上

11、頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁 例例2 用二分法求例用二分法求例1中方程中方程 f(x)=x3- -x- -1=0的實根的實根,要求誤差不超過要求誤差不超過0.005. 解解 由例由例1可知可知x*(1, 1.5), 要想滿足題意，即：要想滿足題意，即：則要則要005. 021)15 . 1(21)(21211 nnnab|x*- -xn|0.005由此解得由此解得 取取n=6, 按二分法計算過程見按二分法計算過程見下表下表, x6 = 1.3242 為所求之近似根為所求之近似根., 6 . 512lg2 n上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁n an bn xn

12、f(xn)說明說明01234561.01.251.251.31251.31251.31251.32031.51.51.3751.3751.34381.32811.32811.251.3751.31251.34381.32811.32031.3242- -+ +- -+ + +- - -(1) f(a)0(2) 根據(jù)精根據(jù)精 度要求，度要求，取到小數(shù)取到小數(shù)點后四位點后四位 即可即可. 二分法的二分法的優(yōu)點優(yōu)點是算法簡單，且總是收斂的，是算法簡單，且總是收斂的，缺缺點點是收斂的太慢，故一般不單獨將其用于求根，只是收斂的太慢，故一般不單獨將其用于求根，只是用其為根求得一個較好的近似值是用其為根求得

13、一個較好的近似值.上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁二分法的計算步驟二分法的計算步驟:步驟步驟1 準(zhǔn)備準(zhǔn)備 計算函數(shù)計算函數(shù)f(x)在區(qū)間在區(qū)間a, b端點處的值端點處的值f(a), f(b). 若若f(a)f(a+b)/2)0, 則以則以(a+b)/2代替代替b ，否則以，否則以(a+b)/2代替代替a.步驟步驟2 二分二分 計算函數(shù)計算函數(shù)f(x)在區(qū)間中點在區(qū)間中點(a+b)/2處的處的值值f(a+b)/2).步驟步驟3 判斷判斷 若若f(a+b)/2)=0，則，則(a+b)/2即是根，即是根，計算過程結(jié)束，否則檢驗計算過程結(jié)束，否則檢驗. 反復(fù)執(zhí)行步驟反復(fù)執(zhí)行步驟2和步驟

14、和步驟3，直到區(qū)間，直到區(qū)間a, b長度小于長度小于允許誤差允許誤差，此時中點，此時中點(a+b)/2即為所求近似根即為所求近似根.上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁7.2 迭代法及其收斂性迭代法及其收斂性7.2.1 不動點迭代法不動點迭代法 將方程將方程f(x)=0改寫為等價方程形式改寫為等價方程形式 x= (x). (2.1)若要求若要求x*滿足滿足f(x*)=0，則，則x*= (x*)；反之亦然，稱；反之亦然，稱x*為為函數(shù)函數(shù) (x)的一個的一個不動點不動點. 求求f(x)的零點就等于求的零點就等于求 (x)的的不動點不動點，選擇一個初始近似值，選擇一個初始近似值x0，將

15、它代入，將它代入(2.1)右端，右端，即可求得即可求得 x1= (x0). 上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁.lim xxkk可以如此反復(fù)迭代計算可以如此反復(fù)迭代計算 xk+1= (xk) (k=0,1,2,). (2.2) (x)稱為迭代函數(shù)稱為迭代函數(shù). 如果對任何如果對任何x0a, b，由，由(2.2)得得到的序列到的序列xk有極限有極限則稱迭代方程則稱迭代方程(2.2)收斂收斂. 且且x*= (x*)為為 (x)的的不動點不動點，故稱故稱(2.2)為為不動點迭代法不動點迭代法. 上述迭代法是一種逐次逼近法，其基本思想是將上述迭代法是一種逐次逼近法，其基本思想是將隱式方程

16、隱式方程(2.1)歸結(jié)為一組顯式的計算公式歸結(jié)為一組顯式的計算公式(2.2)，迭代，迭代過程實質(zhì)上是一個逐步顯式化過程過程實質(zhì)上是一個逐步顯式化過程.上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁當(dāng)當(dāng) (x)連續(xù)時，連續(xù)時，顯然顯然x*就是方程就是方程x= (x)之之根根(不動點不動點). 于是可以從數(shù)列于是可以從數(shù)列xk中求得滿足精度要求的近似根中求得滿足精度要求的近似根. 這種求根方法這種求根方法稱為稱為不動點迭代法不動點迭代法, 1()(0,1,2,)kkxxk 稱為稱為迭代格式迭代格式, (x)稱為稱為迭代函數(shù)迭代函數(shù), x0 稱為稱為迭代初值迭代初值,數(shù)列數(shù)列xk稱為稱為迭代序列迭

17、代序列. 如果迭代序列收斂如果迭代序列收斂, 則稱迭則稱迭代格式代格式收斂收斂,否則稱為否則稱為發(fā)散發(fā)散. （幾何意義的解釋見書幾何意義的解釋見書p265頁頁）1()(0,1,2,)kkxxk .lim xxkk上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁 03224xxx分別按以上三種形式建立迭代公式，并取分別按以上三種形式建立迭代公式，并取x0=1進(jìn)行進(jìn)行迭代計算，結(jié)果如下：迭代計算，結(jié)果如下：14)(2 xxx 32)(243 xxxx 4121)23()(xxxx 解解 對方程進(jìn)行如下三種變形：對方程進(jìn)行如下三種變形： 例例3 用迭代法求方程用迭代法求方程x4+2x2- -x- -

18、3=0 在區(qū)間在區(qū)間1, 1.2內(nèi)的實根內(nèi)的實根.上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁準(zhǔn)確根準(zhǔn)確根 x* = 1.124123029, 可見可見迭代公式不同迭代公式不同, 收斂情收斂情況也不同況也不同. 第二種公式比第一種公式收斂快得多第二種公式比第一種公式收斂快得多, 而而第三種公式第三種公式不收斂不收斂.73496,8.49530710 xx12()41kkkxxx 4213()23kkkkxxxx 12411()(32)kkkkxxxx 26271.124123xx671.124123xx 參見書參見書p266頁頁- -例例3.上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁

19、 例例3表明原方程化為表明原方程化為(2.1)的形式不同，有的收斂，的形式不同，有的收斂，有的不收斂，有的發(fā)散，只有收斂的的迭代過程有的不收斂，有的發(fā)散，只有收斂的的迭代過程(2.2)才有意義，為此我們首先要研究才有意義，為此我們首先要研究 (x)的不定點的存的不定點的存在性及迭代法在性及迭代法(2.2)的收斂性的收斂性.上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁7.2.2 不動點的存在性與迭代法的收斂性不動點的存在性與迭代法的收斂性 首先考察首先考察 (x)在在a, b上不動點的存在唯一性上不動點的存在唯一性. 定理定理1 設(shè)設(shè) (x)ca, b滿足以下兩個條件：滿足以下兩個條件：1

20、對任意對任意xa, b有有a (x)b. .)4 . 2(.)()(yxlyx 2 存在正數(shù)存在正數(shù)la及及 (b)0, f(b)= (b)- -b0, 由連續(xù)函數(shù)性質(zhì)可知存在由連續(xù)函數(shù)性質(zhì)可知存在 x*(a, b) 使使 f(x*)=0，即，即x*= (x*)，x*即為即為 (x)的不動點的不動點. 再證不動點的再證不動點的唯一性唯一性. 設(shè)設(shè)x1*, x2*a, b都是都是 (x)的不動點，則由的不動點，則由(2.4)得得.)()(21212121 xxxxlxxxx 引出矛盾，故引出矛盾，故 (x)的不動點只能是唯一的的不動點只能是唯一的. .證畢證畢. . 在在 (x)的不動點存在唯一

21、的情況下，可得到迭代的不動點存在唯一的情況下，可得到迭代法法(2.2)收斂的一個收斂的一個充分條件充分條件.上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁 定理定理2 設(shè)設(shè) (x)ca, b滿足定理滿足定理1中的兩個條件，中的兩個條件，則對任意則對任意x0a, b，由，由(2.2)得到的迭代序列得到的迭代序列xk收斂收斂到的不動點到的不動點x*，并有，并有誤差估計式誤差估計式)6 . 2(.1)5 . 2(.1101kkkkkxxllxxxxllxx 證明證明 設(shè)設(shè)x*a, b是是 (x)在在a, b上的唯一不動點上的唯一不動點, ,由條件由條件1，可知，可知xka, b，再由，再由(2.4

22、)得得.)()(011xxlxxlxxxxkkkk 因因0l1時稱時稱超線性收斂超線性收斂，p=2時稱時稱平方收斂平方收斂.上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁 定理定理4 對于迭代過程對于迭代過程xk+1= (xk)，如果，如果 ( (p) )(x)在在所求根所求根x*的鄰近連續(xù)，并且的鄰近連續(xù)，并且)8 . 2(. 0)(, 0)()()()()1( xxxxpp 則該迭代過程在則該迭代過程在x*的鄰近是的鄰近是p階收斂的階收斂的. 證明證明 由于由于(x*)=0，根據(jù)定理，根據(jù)定理3立即可以斷定迭立即可以斷定迭代過程代過程xk+1= (xk)具有局部收斂性具有局部收斂性. 再

23、將再將 (xk)在根在根x*處做泰勒展開處做泰勒展開, 利用條件利用條件(2.4), 則有則有.,)(!)()()()(之間之間與與在在 xxxxpxxkpkpk 注意到注意到 (xk)=xk+1， (x*)= x*，由上式得，由上式得上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁,)(!)()(1pkpkxxpxx 因此對迭代誤差，令因此對迭代誤差，令k時有時有這表明迭代過程這表明迭代過程xk+1= (xk)確實為確實為p階收斂階收斂. 證畢證畢. .!)()(1pxeeppkk 上述定理告訴我們，迭代過程的收斂速度依賴于上述定理告訴我們，迭代過程的收斂速度依賴于迭代函數(shù)迭代函數(shù) (x)的

24、選取的選取. 如果如果xa, b但但 (x)0時，則時，則該迭代過程只可能是線性收斂該迭代過程只可能是線性收斂. 對例對例4的討論見書的討論見書p272.上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁)0( aa的三階方法的三階方法. 假設(shè)假設(shè) x0 充分靠近充分靠近 x*, 求求31)(limkkkxaxa 證明證明 首先由泰勒展式可得首先由泰勒展式可得113311limlim()()3!4()kkkkkkaxeaeaax 例子例子 證明迭代公式證明迭代公式 xk+1=xk(xk2+3a)/(3xk2+a)是求是求而而1/4a00，故此故此迭代公式是三階方法迭代公式是三階方法.上頁上頁上頁

25、上頁上頁上頁下頁下頁下頁下頁下頁下頁7.3 迭代收斂的加速方法迭代收斂的加速方法7.3.1 埃特金加速收斂方法埃特金加速收斂方法 對于收斂的迭代過程，只要迭代足夠多次，就可對于收斂的迭代過程，只要迭代足夠多次，就可以使結(jié)果達(dá)到任意的精度，但是有時迭代過程收斂較以使結(jié)果達(dá)到任意的精度，但是有時迭代過程收斂較慢，從而使計算量變得很大，因此迭代過程的加速是慢，從而使計算量變得很大，因此迭代過程的加速是個重要的課題個重要的課題. 設(shè)設(shè)x0是根是根x*的某個近似值的某個近似值, 用迭代公式校正一次得用迭代公式校正一次得 x1= (x0)而由微分中值定理，有而由微分中值定理，有.),)()()(0001之

26、間之間與與在在xxxxxxxx 上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁假設(shè)假設(shè) (x)改變不大改變不大, 近似地取某個近似值近似地取某個近似值l, 則有則有由于由于 x2- -x*l(x1- -x*).)1 . 3().(01 xxlxx 若將校正值若將校正值x1= (x0)再校正一次，又得再校正一次，又得 x2= (x1)將它與將它與(3.1)式聯(lián)立，消去未知的式聯(lián)立，消去未知的l，有，有 xxxxxxxx1021由此推知由此推知.2)(201220100122120 xxxxxxxxxxxxx 上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁. 0lim1 xxxxkkk在計算了

27、在計算了x1及及x2之后，可用上式右端作為之后，可用上式右端作為x*的新近似的新近似,記作記作x1，一般情形是由，一般情形是由xk計算計算xk+1, xk+2，記，記它表明序列它表明序列xk的收斂速度比的收斂速度比xk的收斂速度快的收斂速度快.)2 . 3()., 1 , 0()(2)(2212211 kxxxxxxxxxxkkkkkkkkkk (3.1)式稱為式稱為埃特金埃特金(aitken) 2加速方法加速方法. 可以證明可以證明上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁也稱為也稱為埃特金埃特金 ( aitken ) 外推法外推法. 可以證明可以證明:)(1kkxx 為線性收斂為線性

28、收斂,則埃特金法為平方收斂則埃特金法為平方收斂； 這個加速迭代法也可寫成下面格式這個加速迭代法也可寫成下面格式(1)1(2)(1)11(2)(1)2(2)1111(2)(1)11()()()2kkkkkkkkkkkxxxxxxxxxxx 若若)(1kkxx 為為 p ( p 1)階收斂，階收斂，)(x 導(dǎo)數(shù)連續(xù)，則埃特金法為導(dǎo)數(shù)連續(xù)，則埃特金法為 2p1 階收斂階收斂.的的 p 階階若若上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁 例題例題 求方程求方程 x = e x 在在 x=0.5 附近的根附近的根. 解解 取取 x0=0.5, 迭代格式迭代格式x25=x26=0.5671433 若

29、對此格式用埃特金法若對此格式用埃特金法, 則則kxkex 1 得得(1)1(1)(2)12(2)(1)2(2)1111(2)(1)11()2kkxxkkkkkkkkkxexexxxxxxx 上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁(2)(1)2(2)1111(2)(1)11()2kkkkkkkxxxxxxx 仍取仍取 x0=0.5 , 得得5671433. 05671433. 05671433. 05671433. 05672979. 05668708. 05676279. 05452392. 06065307. 03)2(3)1(32)2(2)1(21)2(1)1(1 xxxxxxx

30、xx由此可見由此可見, 埃特金法加速收斂效果是相當(dāng)顯著的埃特金法加速收斂效果是相當(dāng)顯著的.(1)1(1)(2)12kkxxkkxexe 上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁7.3.2 斯蒂芬森斯蒂芬森(steffensen)迭代法迭代法 埃特金方法埃特金方法不管原序列不管原序列xk是怎樣產(chǎn)生的，對是怎樣產(chǎn)生的，對xk進(jìn)行加速計算，得到序列進(jìn)行加速計算，得到序列xk. 如果把如果把埃特金加速技埃特金加速技巧與不定點迭代結(jié)合巧與不定點迭代結(jié)合，則可得到如下的迭代法：，則可得到如下的迭代法：),(),(kkkkyzxy )3 . 3()., 1 , 0(2)(21 kxyzxyxxkkk

31、kkkk稱為稱為斯蒂芬森斯蒂芬森(steffensen)迭代法迭代法. 它可以這樣理解，它可以這樣理解，我們要求我們要求x= (x)的根的根x*，令誤差，令誤差(x)= (x)- -x，有等式，有等式(x*)= (x*)- -x*=0，已知，已知x*的近似值的近似值xk及及yk，其誤差分，其誤差分別為別為上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁,)()(kkkkkxyxxx .)()(kkkkkyzyyy 把誤差把誤差(x)“外推到零外推到零”，即過，即過(xk,(xk)及及(yk,(yk)兩點兩點做線性插值函數(shù)，它與做線性插值函數(shù)，它與x軸交點就是軸交點就是(3.3)中的中的xk+1

32、，即，即方程方程. 0)()()()( kkkkkkxxxyxyx 的解的解)()()()()(kkkkkkxyxyxxx .2)(12 kkkkkkkxxyzxyx上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁 實際上實際上(3.3)是將不定點迭代法是將不定點迭代法(2.2)計算兩步合并計算兩步合并成一步得到的，可將它寫成另一種不動點迭代成一步得到的，可將它寫成另一種不動點迭代)4 . 3(), 1 , 0()(1 kxxkk )5 . 3(.)(2)()()(2xxxxxxx 其中其中 對不動點迭代對不動點迭代(3.5)有以下局部收斂性定理有以下局部收斂性定理. 定理定理5 若若x*為為

33、(3.5)定義的迭代函數(shù)定義的迭代函數(shù)(x)的不動點，的不動點，則則x*為為 (x)的不定點的不定點. 反之，若反之，若x*為為 (x)的不動點，的不動點，設(shè)設(shè)(x)存在，存在，(x)1，則，則x*是是(x)的不動點，且的不動點，且斯斯蒂芬森迭代法蒂芬森迭代法(3.3)是是2階收斂的階收斂的. 證明可見證明可見2.上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁 例例5 見書見書p274. 例例6 見書見書p275.上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁7.4 牛牛 頓頓 法法7.4.1 牛頓法及其收斂性牛頓法及其收斂性)()()(000 xxxfxfxf 對于方程對于方程f(x)=

34、0，如果，如果f(x)是線性函數(shù)，則它的是線性函數(shù)，則它的求根是容易的求根是容易的. 牛頓法實質(zhì)上是一種線性化方法，其牛頓法實質(zhì)上是一種線性化方法，其基本思想是將非線性方程基本思想是將非線性方程f(x)=0逐步歸結(jié)為某種線性逐步歸結(jié)為某種線性方程來求解方程來求解. 設(shè)已知方程設(shè)已知方程f(x)=0有近似根有近似根x0，且在，且在 x0附近附近f(x)可可用一階泰勒多項式近似，表示為用一階泰勒多項式近似，表示為上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁當(dāng)當(dāng)f (x0)0時，方程時，方程f(x)=0可用線性方程可用線性方程(切線切線) 近似代近似代替，即替，即 f(x0)+f (x0)(x-

35、 -x0)=0. (4.1)解此線性方程得解此線性方程得)()(000 xfxfxx 得迭代公式得迭代公式此式稱為此式稱為牛頓牛頓(newton)迭代公式迭代公式.)2 . 4(), 1 , 0()()(1 kxfxfxxkkkk上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁牛頓法有顯然的牛頓法有顯然的幾何意義幾何意義，方程，方程f(x)=0的根的根x*可可解釋為曲線解釋為曲線y=f(x)與與x軸交點的橫坐標(biāo)軸交點的橫坐標(biāo). 設(shè)設(shè)xk是根是根x*的的某個近似值，過曲線某個近似值，過曲線y=f(x)上橫坐標(biāo)為上橫坐標(biāo)為xk的點的點pk引切引切線，并將該切線與線，并將該切線與x軸交點的橫坐標(biāo)軸交

36、點的橫坐標(biāo)xk+1作為作為x*的新的的新的近似值近似值. 注意到切線方程為注意到切線方程為這樣求得的值這樣求得的值xk+1必滿足必滿足(4.1), 從而就是牛頓公式從而就是牛頓公式(4.2)的計算結(jié)果的計算結(jié)果. 由于這由于這種幾何背景，所以牛頓迭種幾何背景，所以牛頓迭代法也稱代法也稱切線法切線法.xyx*xky=f(x)xk+1pkpk+1xk+2).)()(kkkxxxfxfy 上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁牛頓迭代法的收斂性牛頓迭代法的收斂性)()()(xfxfxx 設(shè)設(shè)x*是是f(x)的一個單根，即的一個單根，即f(x*)=0，f (x*)0, 有有. 0)()()(

37、, 0)()()()(2* xfxfxxfxfxfx 牛頓迭代法的迭代函數(shù)為牛頓迭代法的迭代函數(shù)為由定理由定理4的的(2.9)式可得式可得(4.3)式式. 0)(2)()(! 21)()(lim)(lim22!2121 xfxfxxxxxxxxxkkkkkk 上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁由此得到，當(dāng)由此得到，當(dāng)x*為為單根單根時，牛頓迭代法在根時，牛頓迭代法在根x*的的鄰近是鄰近是二階二階(平方平方)收斂收斂的的.關(guān)于關(guān)于x*為為重根重根時，牛頓迭代法在根時，牛頓迭代法在根x*的鄰近的收的鄰近的收斂性在后面討論斂性在后面討論.定理定理(局部收斂性局部收斂性) 設(shè)設(shè)f c2a

38、, b, 若若x*為為f(x)在在a, b上的根，且上的根，且f (x*) 0，則存在，則存在x*的鄰域的鄰域u, 使得任取初使得任取初值值x0 u，牛頓法產(chǎn)生的序列，牛頓法產(chǎn)生的序列xk收斂到收斂到x*，且滿足，且滿足即有下面的局部收斂性定理即有下面的局部收斂性定理.)(2)()(lim21 xfxfxxxxkkk上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁 解解 將原方程化為將原方程化為xex= 0，則，則牛頓迭代公式為牛頓迭代公式為kkxxkkkeexxx 11取取 x0=0.5，迭代得，迭代得x1=0.566311, x2=0.5671431, x3=0.5671433. f(x)

39、=xex， f (x)=1+ex， 例例7 用牛頓迭代法求方程用牛頓迭代法求方程x=ex在在x=0.5附近的根附近的根.參見書參見書p277的的例例7.牛頓法的計算步驟見書牛頓法的計算步驟見書p278.上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁7.4.2 牛頓法應(yīng)用舉例牛頓法應(yīng)用舉例對于給定的正數(shù)對于給定的正數(shù)c，應(yīng)用牛頓法解二次方程，應(yīng)用牛頓法解二次方程, 02 cx我們現(xiàn)在證明，這種迭代公式對于任意初值我們現(xiàn)在證明，這種迭代公式對于任意初值x00都是收斂的都是收斂的.可導(dǎo)出求開方值可導(dǎo)出求開方值 的計算程序的計算程序c.21)()()(,)(2 xcxxfxfxxcxxf )5 .

40、4(.211 kkkxcxx上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁事實上，對事實上，對(4.5)式施行配方整理，易知式施行配方整理，易知 .2121cxxcxkkk 以上兩式相除得以上兩式相除得.211 cxcxcxcxkkkk據(jù)此反復(fù)遞推有據(jù)此反復(fù)遞推有)6 . 4(.200kcxcxcxcxkk 上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁記記.200kcxcxq 整理整理(4.6)式，得式，得.1222kkqqccxk 對任意初值對任意初值x00，總有，總有|q|1，故由上式推知，當(dāng)，故由上式推知，當(dāng)k時時 ，即迭代過程恒收斂，即迭代過程恒收斂.cxk參見書參見書p279的

41、的例例8.上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁7.4.3 簡化牛頓法與牛頓下山法簡化牛頓法與牛頓下山法牛頓法的牛頓法的優(yōu)點優(yōu)點是收斂快，是收斂快，缺點缺點每步迭代要計算每步迭代要計算f(xk)及及f (xk)，計算量較大，且有時，計算量較大，且有時f (xk)計算較困難；計算較困難；初始近似值初始近似值x0只在根只在根x*附近才能保證收斂，如附近才能保證收斂，如x0給給的不合適可能不收斂的不合適可能不收斂. 為克服這兩個缺點，通常可用為克服這兩個缺點，通?？捎孟率龇椒ㄏ率龇椒?(1) 簡化牛頓法簡化牛頓法，也稱，也稱平行弦法平行弦法，其迭代公式為，其迭代公式為)7 . 4(., 1

42、 , 0, 0)(1 kcxcfxxkkk迭代函數(shù)為迭代函數(shù)為 (x)=x- -cf(x). 上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁若若| (xk)|=|1- -cf (x)|1，即取，即取0cf (x)2. 在根在根x*附近成立，則迭代法附近成立，則迭代法(4.7)局部收斂局部收斂.在在(4.7)中取中取c=1/f (x0)，則稱為簡化牛頓法，這類，則稱為簡化牛頓法，這類方法計算量省，但只有線性收斂，其方法計算量省，但只有線性收斂，其幾何意義幾何意義是用平是用平行弦與行弦與x軸交點作為軸交點作為x*的近似，見下圖的近似，見下圖.y=f(x)x0 x1x2x*上頁上頁上頁上頁上頁上頁

43、下頁下頁下頁下頁下頁下頁(2) 牛頓下山法牛頓下山法, 牛頓法收斂性依賴初值牛頓法收斂性依賴初值x0的選取的選取, 如果如果x0偏離所求根偏離所求根x*較遠(yuǎn)較遠(yuǎn), 則牛頓法可能發(fā)散則牛頓法可能發(fā)散.newtons method收斂性依賴于收斂性依賴于x0的選取的選取.x*x0 x0 x0上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁例如例如，用牛頓法求解方程，用牛頓法求解方程 x3- -x- -1=0. (4.8)此方程在此方程在x=1.5附近的一個根附近的一個根x*. 設(shè)取迭代初值設(shè)取迭代初值x0=1.5，用牛頓迭代法公式，用牛頓迭代法公式 )9 . 4(.131231 kkkkkxxxx

44、x計算得計算得 x1=1.34783, x2=1.32520, x3=1.32472.迭代迭代3次得到的結(jié)果次得到的結(jié)果x3有有6位有效數(shù)字位有效數(shù)字.但是，如取但是，如取x0=0.6，用，用(4.9)式迭代式迭代1次得次得 計算得計算得 x1=17.9.這個結(jié)果反而比這個結(jié)果反而比x0=0.6更偏離了所求的根更偏離了所求的根x*=1.32472. 上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁為了防止迭代發(fā)散，我們對迭代過程再附加一項為了防止迭代發(fā)散，我們對迭代過程再附加一項要求，即具有單調(diào)性要求，即具有單調(diào)性.)10. 4(. )()(1kkxfxf 滿足這項要求的算法稱為滿足這項要求的

45、算法稱為下山法下山法.我們將牛頓法與下山法結(jié)合起來使用，即在下山我們將牛頓法與下山法結(jié)合起來使用，即在下山法保證函數(shù)值穩(wěn)定下降的前提下，用牛頓法加快收斂法保證函數(shù)值穩(wěn)定下降的前提下，用牛頓法加快收斂速度速度. 為此，我們將牛頓法的結(jié)果為此，我們將牛頓法的結(jié)果)()(1kkkkxfxfxx 與前一項的近似值與前一項的近似值xk適當(dāng)加權(quán)平均作為新的改進(jìn)值適當(dāng)加權(quán)平均作為新的改進(jìn)值)11. 4(,)1(11kkkxxx 上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁其中其中(01)稱為稱為下山因子下山因子，(4.11)即為即為)12. 4()., 1 , 0()()(1 kxfxfxxkkkk 稱

46、為稱為牛頓下山法牛頓下山法.選擇下山因子時從選擇下山因子時從= =1開始，逐次將開始，逐次將減半進(jìn)行試減半進(jìn)行試算，直到能使下降條件算，直到能使下降條件(4.10)成立為止成立為止. 若用此法解方程若用此法解方程(4.8)，當(dāng)，當(dāng)x0=0.6時由時由(4.9)式求得式求得x1=17.9，它不滿足條件，它不滿足條件(4.10)，通過，通過逐次減半進(jìn)行試逐次減半進(jìn)行試算算,當(dāng)當(dāng)=1/32時可求得時可求得x1=1.140625. 有有f(x0)=-1-1.384, f(x1)=- -0.656643, 顯然顯然|f(x1)|0)重根重根時，則時，則f(x)可表為可表為 f(x)=(x- -x*)mg

47、(x).其中其中g(shù)(x*)0，此時用牛頓迭代法，此時用牛頓迭代法(4.2)求求x*仍然收斂，仍然收斂，只是只是收斂速度將大大減慢收斂速度將大大減慢. 事實上，因為迭代公式事實上，因為迭代公式)()()()()()()(*1kkkkkkkkkkxgxxxmgxgxxxxfxfxx 令令ek=xkx*，則，則)()()(*11kkkkkkkkxgexmgxgeexxe 上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁可見用牛頓法求方程的重根時僅為可見用牛頓法求方程的重根時僅為線性收斂線性收斂. 011)()()(1limlim1 mxgexmgxgeekkkkkkkk從而有從而有兩種兩種提高求重根

48、的收斂速度提高求重根的收斂速度的的方法方法：1) ) 取如下迭代函數(shù)取如下迭代函數(shù). 0)(,)()()( xxfxfmxx 則則)13. 4()., 1 , 0()()(1 kxfxfmxxkkkk得到迭代公式得到迭代公式上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁下面介紹一個下面介紹一個求重數(shù)求重數(shù)m的方法的方法，令，令211 kkkkkxxxx 則則112121111kkkkkkkkkkkeeeeeeeeee 求求m重根具有重根具有2階收斂階收斂. 但要知道但要知道x*的的重數(shù)重數(shù)m.由式由式11lim1kkkeem .111limmmmkk 得得因此得估計因此得估計m的式子為的式子

49、為.11km 上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁對對f(x)=(x- -x*)mg(x), g(x*)0，令函數(shù)，令函數(shù).)()()()()()()()(xgxxxmgxgxxxfxfx 則為求則為求(x)=0的單根的單根x*的問題，對它用牛頓法是二階的問題，對它用牛頓法是二階(平方平方)收斂的收斂的. 其迭代函數(shù)為其迭代函數(shù)為2) ) 將求重根問題化為求單根問題將求重根問題化為求單根問題. .)()()()()()()()(2xfxfxfxfxfxxxxx )14. 4()., 1 , 0()()()()()(21 kxfxfxfxfxfxxkkkkkkk從而構(gòu)造出迭代方法為從

50、而構(gòu)造出迭代方法為上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁 例例8 用牛頓迭代法求函數(shù)用牛頓迭代法求函數(shù) f(x)=(x- -1)sin(x- -1)+3x- -x3+1=0 在在0.95附近之根附近之根. 解解 取取x0 = 0.95 用牛頓迭代法求用牛頓迭代法求得的得的xk見右表見右表. 可可見見xk收斂很慢收斂很慢.kxk km01234560.950.97442790.98705830.99348780.99673280.99835760.99919010.50900.50470.50070.51252.03692.01902.00282.0511上頁上頁上頁上頁上頁上頁下頁下

51、頁下頁下頁下頁下頁由重根數(shù)由重根數(shù)m=2, 用用(4.13)式加速法，作式加速法，作求得求得 x0=0.95, x1=0.9988559, x2=x3=1.收斂速度大大加快于直接用牛頓迭代公式收斂速度大大加快于直接用牛頓迭代公式.1()()kkkkf xxxmf x 參見書參見書p283的的例例9.上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁7.5 弦截法與拋物線法弦截法與拋物線法用牛頓法求方程用牛頓法求方程f(x)=0的根，每步除計算的根，每步除計算f(xk)外外還要算還要算f (xk)，當(dāng)函數(shù)，當(dāng)函數(shù)f(x)比較復(fù)雜時，計算比較復(fù)雜時，計算f (x)往往往往比較困難，為此可以利用已求函

52、數(shù)值比較困難，為此可以利用已求函數(shù)值f(xk),f(xk- -1),來來回避導(dǎo)數(shù)值回避導(dǎo)數(shù)值f (xk)的計算的計算. 這類方法是建立在插值原理這類方法是建立在插值原理基礎(chǔ)上的，下面介紹兩種常用方法基礎(chǔ)上的，下面介紹兩種常用方法.上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁7.5.1 弦截弦截(割線割線)法法設(shè)設(shè)xk,xk- -1是是f(x)=0的近似根，我們利用的近似根，我們利用f(xk),f(xk- -1)構(gòu)造一次插值多項式構(gòu)造一次插值多項式p1(x)，并用，并用p1(x)=0的根作為方程的根作為方程f(x)=0的新的近似根的新的近似根xk+1，由于，由于)1 . 5().()()()

53、()(111kkkkkkxxxxxfxfxfxp 因此有因此有)2 . 5().()()()(111 kkkkkkkxxxfxfxfxx上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁這樣導(dǎo)出的迭代公式這樣導(dǎo)出的迭代公式(5.2)可以看做牛頓公式可以看做牛頓公式.)()(1kkkkxfxfxx 11)()( kkkkxxxfxf中的導(dǎo)數(shù)中的導(dǎo)數(shù) 用用差商差商 取代的結(jié)果取代的結(jié)果.)(kxf (5.2)式有明顯的式有明顯的幾何意義幾何意義： 設(shè)曲線設(shè)曲線y=f(x)上橫坐標(biāo)為上橫坐標(biāo)為xk- -1和和xk的點分別為的點分別為p0和和pk, 則差商則差商 表示弦表示弦 的斜率的斜率, 弦弦 的方

54、程為的方程為11)()( kkkkxxxfxfkkpp1 kkpp1 )()()()(00kkkkxxxxxfxfxfy 上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁ox*xk+1xkpkxk- -1yxpk- -1因此，按因此，按(5.2)式求得式求得xk+1實際上是兩點弦實際上是兩點弦線線 與與x軸交點軸交點的橫坐標(biāo)的橫坐標(biāo)(令令y=0解出解出x即可即可).這種算法因此這種算法因此而形象地稱為而形象地稱為弦截弦截(割線割線)法法.kkpp1 參見書參見書p285的的例例10.上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁弦截法與切線法弦截法與切線法(牛頓法牛頓法)都是線性化分法，但兩

55、都是線性化分法，但兩者有本質(zhì)的區(qū)別者有本質(zhì)的區(qū)別. 切線法在計算切線法在計算xk+1時只用到前一步時只用到前一步的值的值xk，而弦截法要用到前面兩步的結(jié)果，而弦截法要用到前面兩步的結(jié)果xk- -1,xk，因，因此使用這種方法必須先給出兩個開始值此使用這種方法必須先給出兩個開始值x0, x1.定理定理6 假設(shè)假設(shè)f(x)在根在根x*的鄰域內(nèi)的鄰域內(nèi): |x- -x*|具有具有二階連續(xù)導(dǎo)數(shù)，且對任意二階連續(xù)導(dǎo)數(shù)，且對任意x 有有f (x)0，所取的初，所取的初值值x0, x1 ，那么當(dāng)鄰域，那么當(dāng)鄰域充分小時，弦截法充分小時，弦截法(5.2)將將按階按階.618. 1251 p收斂到收斂到x*.

56、這里這里p是方程是方程2- - -1=0的正根的正根.定理證明可見定理證明可見2.上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁因為因為(5.2)式用到前兩點式用到前兩點xk- -1和和xk的值，故此方法的值，故此方法又稱為又稱為雙點割線法雙點割線法.).()()()(0001xxxfxfxfxxkkkk 每步只用一個新點每步只用一個新點xk的值，此方法稱為的值，此方法稱為單點割線法單點割線法.如果把如果把(5.2)式中的式中的xk- -1改為改為x0，即迭代公式為，即迭代公式為上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁例題例題 用牛頓迭代法和割線法求方程用牛頓迭代法和割線法求方程 f

57、(x)=x4+2x2x3=0， 在區(qū)間在區(qū)間(1, 1.5)內(nèi)之根內(nèi)之根(誤差為誤差為10- -9). 解解 取取x0=1.5，用牛頓法，用牛頓法, 可得可得x6=1.12412303030；取取x0=1.5, x1=1，用，用雙點割線法雙點割線法，迭代，迭代6次得到同樣的次得到同樣的結(jié)果，而采用結(jié)果，而采用單點割線法單點割線法，則迭代，則迭代18次得次得x18=1.124123029.上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁 例題例題 用快速弦截法求方程用快速弦截法求方程xex- -1=0的根的根. 設(shè)方程設(shè)方程的兩個初始近似根為的兩個初始近似根為x0=0.5 , x1=0.6.計算

58、結(jié)果表計算結(jié)果表k xk xk- -xk- -10 0.5 1 0.6 0.12 0.56532 - -0.034683 0.56709 0.001774 0.56714 0.00005 與與例例7(p277)中牛中牛頓法的計算結(jié)果相比頓法的計算結(jié)果相比較，可以看出快速弦較，可以看出快速弦截法的收斂速度也是截法的收斂速度也是相當(dāng)快的，迭代到第相當(dāng)快的，迭代到第4步就得到精度步就得到精度 的結(jié)果的結(jié)果.410 上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁7.5.2 拋物線法拋物線法設(shè)已知方程設(shè)已知方程f(x)=0的三個近似根的三個近似根xk,xk- -1,xk- -2，我們，我們以這三點為節(jié)

59、點構(gòu)造二次插值多項式以這三點為節(jié)點構(gòu)造二次插值多項式p2(x)，并適當(dāng)選，并適當(dāng)選取取p2(x)的一個零點的一個零點xk+1作為新的近似根，這樣確定的作為新的近似根，這樣確定的迭代過程稱為迭代過程稱為拋物線法拋物線法，亦稱為，亦稱為密勒密勒(mller)法法. 在在幾何圖形上幾何圖形上, 這種方法的基本思想是用拋物線這種方法的基本思想是用拋物線y=p2(x)與與x軸的交點軸的交點xk+1作為所求根作為所求根x*的近似位置的近似位置.上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁ox*xk+1xky=p2(x)xk- -2yxy=f(x)xk- -1拋物線法的拋物線法的幾何意義幾何意義見下面圖

60、形見下面圖形.上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁現(xiàn)在推導(dǎo)拋物線法的計算公式現(xiàn)在推導(dǎo)拋物線法的計算公式. 插值多項式插值多項式).)(,)(,)()(12112 kkkkkkkkkxxxxxxxfxxxxfxfxp有兩個零點有兩個零點).(,1211 kkkkkkkxxxxxfxxf )3 . 5(.,)(4)(22121 kkkkkkkxxxfxfxfxx 式中式中因了在因了在(5.3)式定出一個值式定出一個值xk+1，我們需要討論根，我們需要討論根式前正負(fù)號的取舍問題式前正負(fù)號的取舍問題.在在xk, xk- -1, xk- -2三個近似值中，自然假定三個近似值中，自然假定xk更