第7章 非線性方程和方程組的數(shù)值解法(一)

1、上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)第第7章章 非線性方程和方程組的數(shù)非線性方程和方程組的數(shù)值解法求根值解法求根 7.1 方程求根的二分法方程求根的二分法 7.2 不動(dòng)點(diǎn)迭代法不動(dòng)點(diǎn)迭代法 7.3 牛頓法、弦截法與拋物線法牛頓法、弦截法與拋物線法 7.4 非線性方程組的數(shù)值解法非線性方程組的數(shù)值解法上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè) 例如例如代數(shù)方程代數(shù)方程 x5- -x3+24x+1=0, 超越方程超越方程 sin(5x2)+e- -x=0. 對(duì)于不高于對(duì)于不高于4次的代數(shù)方程已有求根公式，而次的代數(shù)方程已有求根公式，而高于高于4次的代數(shù)方程則無(wú)精確的求根公式，至于

2、超次的代數(shù)方程則無(wú)精確的求根公式，至于超越方程越方程 就更無(wú)法求出其精確的解，因此，如何求就更無(wú)法求出其精確的解，因此，如何求得滿足一定精度要求的方程的近似根也就成為迫得滿足一定精度要求的方程的近似根也就成為迫切需要解決的問(wèn)題，為此，本章介紹幾種常見(jiàn)的切需要解決的問(wèn)題，為此，本章介紹幾種常見(jiàn)的非線性方程的近似求根方法非線性方程的近似求根方法.7.0 引言引言上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)主要討論主要討論單變量非線性方程單變量非線性方程f(x)=0 (1.1)的求根問(wèn)題，這里的求根問(wèn)題，這里xR, f(x)Ca, b. )2 . 1(),0()(01110 aaxaxaxaxf

3、nnnn其中系數(shù)其中系數(shù)ai(i=0,1,n)為實(shí)數(shù)為實(shí)數(shù). 在科在科 學(xué)與工程計(jì)算中有大量方程求根問(wèn)題，其學(xué)與工程計(jì)算中有大量方程求根問(wèn)題，其中一類(lèi)特殊的問(wèn)題是多項(xiàng)式方程中一類(lèi)特殊的問(wèn)題是多項(xiàng)式方程上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)方程方程f(x)=0的的根根x*，又稱(chēng)為函數(shù)又稱(chēng)為函數(shù)f(x)的的零點(diǎn)零點(diǎn)，它使得，它使得f(x*)=0，若，若f(x)可分解為可分解為f(x)=(x- -x*)mg(x)，其中其中m為正整數(shù)，且為正整數(shù)，且g(x*)0. 當(dāng)當(dāng)m=1時(shí)，則稱(chēng)時(shí)，則稱(chēng)x*為單為單根，若根，若m1稱(chēng)稱(chēng)x*為為(1.1)的的m重根重根，或，或x*為函數(shù)為函數(shù)f(x)的的m

4、重零點(diǎn)重零點(diǎn). 若若x*是是f(x)的的m重零點(diǎn)重零點(diǎn)，且，且g(x)充分光滑，則充分光滑，則當(dāng)當(dāng)f(x)為代數(shù)多項(xiàng)式為代數(shù)多項(xiàng)式(1.2)時(shí)，根據(jù)代數(shù)基本定理時(shí)，根據(jù)代數(shù)基本定理可知，可知，n次代數(shù)方程次代數(shù)方程f(x)=0在復(fù)數(shù)域有且只有在復(fù)數(shù)域有且只有n個(gè)根個(gè)根(含含復(fù)根，復(fù)根，m重根為重根為m個(gè)根個(gè)根). 0)(, 0)()()()()1( xfxfxfxfmm上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)n=1,2時(shí)方程的根是大家熟悉的，時(shí)方程的根是大家熟悉的，n=3,4時(shí)雖有求時(shí)雖有求根公式但比較復(fù)雜，可在數(shù)學(xué)手冊(cè)中查到，但已不適根公式但比較復(fù)雜，可在數(shù)學(xué)手冊(cè)中查到，但已不適合數(shù)

5、值計(jì)算，而合數(shù)值計(jì)算，而n5時(shí)就不能用公式表示方程的根時(shí)就不能用公式表示方程的根.因因此，通常對(duì)此，通常對(duì)n3的多項(xiàng)式方程求根與一般連續(xù)函數(shù)方的多項(xiàng)式方程求根與一般連續(xù)函數(shù)方程程(1.1)一樣都可采用迭代法求根一樣都可采用迭代法求根.迭代法要求給出根迭代法要求給出根x*的一個(gè)近似，若的一個(gè)近似，若f(x)Ca, b且且f(a)f(b)0，根據(jù)連續(xù)函數(shù)性質(zhì)中的介值定理可知方，根據(jù)連續(xù)函數(shù)性質(zhì)中的介值定理可知方程程f(x)=0在在(a, b)內(nèi)至少有一個(gè)實(shí)根，這時(shí)稱(chēng)內(nèi)至少有一個(gè)實(shí)根，這時(shí)稱(chēng)a, b為方為方程程(1.1)的的有根區(qū)間有根區(qū)間.上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè) 設(shè)設(shè)f(

6、x)在區(qū)間在區(qū)間a, b上連續(xù)上連續(xù), f(a)f(b)0, 則在則在a, b 內(nèi)有方程的根內(nèi)有方程的根. 取取a, b的中點(diǎn)的中點(diǎn) 將區(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ū)間, 它它的的長(zhǎng)度

7、只有原有根區(qū)間長(zhǎng)度的一半長(zhǎng)度只有原有根區(qū)間長(zhǎng)度的一半, 達(dá)到了達(dá)到了壓縮有根壓縮有根區(qū)間區(qū)間的目的的目的.7.1 方程求根的二分法方程求根的二分法上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè) 對(duì)壓縮了的有根區(qū)間對(duì)壓縮了的有根區(qū)間, 又可實(shí)行同樣的步驟又可實(shí)行同樣的步驟, 再壓再壓縮縮. 如此反復(fù)進(jìn)行如此反復(fù)進(jìn)行, 即可的一系列即可的一系列有根區(qū)間套有根區(qū)間套 ,11nnbababa 由于每一區(qū)間都是前一區(qū)間的一半，因此區(qū)間由于每一區(qū)間都是前一區(qū)間的一半，因此區(qū)間an , bn的長(zhǎng)度為的長(zhǎng)度為)(ababnnn 21若每次二分時(shí)所取區(qū)間中點(diǎn)都不是根，則上述過(guò)程將若每次二分時(shí)所取區(qū)間中點(diǎn)都不是

8、根，則上述過(guò)程將無(wú)限進(jìn)行下去無(wú)限進(jìn)行下去. 當(dāng)當(dāng) n 時(shí)，區(qū)間必將最終收縮為一時(shí)，區(qū)間必將最終收縮為一點(diǎn)點(diǎn)x* ，顯然，顯然x*就是所求的就是所求的根根.上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè) 若取區(qū)間若取區(qū)間an , bn的中點(diǎn)的中點(diǎn))(nnnbax 21作為作為x*的近似值，則有下述的近似值，則有下述誤差估計(jì)式誤差估計(jì)式111*()()22nnnnxxbaba 只要只要 n 足夠大足夠大, (即區(qū)間二分次數(shù)足夠多即區(qū)間二分次數(shù)足夠多)，誤差就可，誤差就可足夠小足夠小.),(,*11 nnnbaxx 由于在偶重根附近曲線由于在偶重根附近曲線 y=f(x) 為上凹或下凸為上凹或下凸,

9、 即即 f(a)與與f(b)的符號(hào)相同的符號(hào)相同, 因此因此不能用二分法求偶重根不能用二分法求偶重根.上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè) 例例2 用二分法求例用二分法求例1中方程中方程 f(x)=x3- -x- -1=0的實(shí)根的實(shí)根,要求誤差不超過(guò)要求誤差不超過(guò)0.005. 解解 由例由例1可知可知x*(1, 1.5), 要想滿足題意，即：要想滿足題意，即：則要?jiǎng)t要005. 021)15 . 1(21)(21211 nnnab|x*- -xn|0.005由此解得由此解得 取取n=6, 按二分法計(jì)算過(guò)程見(jiàn)按二分法計(jì)算過(guò)程見(jiàn)下表下表, x6 = 1.3242 為所求之近似根為所求之近

10、似根., 6 . 512lg2 n上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)n an bn xn f(xn)說(shuō)明說(shuō)明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ù)點(diǎn)后四位點(diǎn)后四位 即可即可. 二分法的二分法的優(yōu)點(diǎn)優(yōu)點(diǎn)是算法簡(jiǎn)單，且總是收斂的，是算法簡(jiǎn)單，且總是收斂的，缺缺點(diǎn)點(diǎn)是收斂的太慢，故一般不單

11、獨(dú)將其用于求根，只是收斂的太慢，故一般不單獨(dú)將其用于求根，只是用其為根求得一個(gè)較好的近似值是用其為根求得一個(gè)較好的近似值.上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)逐步搜索法逐步搜索法 從區(qū)間從區(qū)間a, b的左端點(diǎn)的左端點(diǎn) a 出發(fā)出發(fā), 按選定的步長(zhǎng)按選定的步長(zhǎng)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)必有根. 搜索過(guò)程也可從搜索過(guò)程也可從b開(kāi)開(kāi)始，這時(shí)應(yīng)取步長(zhǎng)始，這時(shí)應(yīng)取步長(zhǎng) h0.上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)7.2 不動(dòng)點(diǎn)迭代法及其收斂性不動(dòng)點(diǎn)迭代法及其收

12、斂性7.2.1 不動(dòng)點(diǎn)迭代法不動(dòng)點(diǎn)迭代法 將方程將方程f(x)=0改寫(xiě)為等價(jià)方程形式改寫(xiě)為等價(jià)方程形式 x= (x). (2.1)若要求若要求x*滿足滿足f(x*)=0，則，則x*= (x*)；反之亦然，稱(chēng)；反之亦然，稱(chēng)x*為為函數(shù)函數(shù) (x)的一個(gè)的一個(gè)不動(dòng)點(diǎn)不動(dòng)點(diǎn). 求求f(x)的零點(diǎn)就等于求的零點(diǎn)就等于求 (x)的的不動(dòng)點(diǎn)不動(dòng)點(diǎn)，選擇一個(gè)初始近似值，選擇一個(gè)初始近似值x0，將它代入，將它代入(2.1)右端，右端，即可求得即可求得 x1= (x0). 上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè).lim xxkk可以如此反復(fù)迭代計(jì)算可以如此反復(fù)迭代計(jì)算 xk+1= (xk) (k=0,

13、1,2,). (2.2) (x)稱(chēng)為迭代函數(shù)稱(chēng)為迭代函數(shù). 如果對(duì)任何如果對(duì)任何x0a, b，由，由(2.2)得得到的序列到的序列xk有極限有極限則稱(chēng)迭代方程則稱(chēng)迭代方程(2.2)收斂收斂. 且且x*= (x*)為為 (x)的的不動(dòng)點(diǎn)不動(dòng)點(diǎn)，故稱(chēng)故稱(chēng)(2.2)為為不動(dòng)點(diǎn)迭代法不動(dòng)點(diǎn)迭代法. 上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)當(dāng)當(dāng) (x)連續(xù)時(shí)，連續(xù)時(shí)，顯然顯然x*就是方程就是方程x= (x)之之根根(不動(dòng)點(diǎn)不動(dòng)點(diǎn)). 于是可以從數(shù)列于是可以從數(shù)列xk中求得滿足精度要求的近似根中求得滿足精度要求的近似根. 這種求根方法這種求根方法稱(chēng)為稱(chēng)為不動(dòng)點(diǎn)迭代法不動(dòng)點(diǎn)迭代法, 1()(0,1,

14、2,)kkxxk 稱(chēng)為稱(chēng)為迭代格式迭代格式, (x)稱(chēng)為稱(chēng)為迭代函數(shù)迭代函數(shù), x0 稱(chēng)為稱(chēng)為迭代初值迭代初值,數(shù)列數(shù)列xk稱(chēng)為稱(chēng)為迭代序列迭代序列. 如果迭代序列收斂如果迭代序列收斂, 則稱(chēng)迭則稱(chēng)迭代格式代格式收斂收斂,否則稱(chēng)為否則稱(chēng)為發(fā)散發(fā)散. （幾何意義的解釋見(jiàn)下幾何意義的解釋見(jiàn)下頁(yè)頁(yè)）1()(0,1,2,)kkxxk .lim xxkk上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)y=x上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)y=x上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè) 03224xxx分別按以上三種形式建立迭代公式，并取分別按以上三種形式建立迭代公式，并取x0=1

15、進(jìn)行進(jìn)行迭代計(jì)算，結(jié)果如下：迭代計(jì)算，結(jié)果如下：14)(2 xxx 32)(243 xxxx 4121)23()(xxxx 解解 對(duì)方程進(jìn)行如下三種變形：對(duì)方程進(jìn)行如下三種變形： 例例1 用迭代法求方程用迭代法求方程x4+2x2- -x- -3=0 在區(qū)間在區(qū)間1, 1.2內(nèi)的實(shí)根內(nèi)的實(shí)根.上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)準(zhǔn)確根準(zhǔn)確根 x* = 1.124123029, 可見(jiàn)可見(jiàn)迭代公式不同迭代公式不同, 收斂情收斂情況也不同況也不同. 第二種公式比第一種公式收斂快得多第二種公式比第一種公式收斂快得多, 而而第三種公式第三種公式不收斂不收斂.73496,8.495307 10

16、xx12()41kkkxxx 4213()23kkkkxxxx 12411()(32)kkkkxxxx 26271.124123xx671.124123xx上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè) 當(dāng)方程有多個(gè)解時(shí)，同一個(gè)迭代法的當(dāng)方程有多個(gè)解時(shí)，同一個(gè)迭代法的不同初值不同初值也也可能收斂到可能收斂到不同的根不同的根.上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè) 例例1 表明原方程化為表明原方程化為 x= (x) 的形式不同，有的的形式不同，有的收斂，有的不收斂，有的發(fā)散收斂，有的不收斂，有的發(fā)散. 例例2 表明同一個(gè)迭代法的不同初值可能收斂到表明同一個(gè)迭代法的不同初值可能收斂到不

17、同的根不同的根. 只有收斂的的迭代過(guò)程才有意義，為此我們首只有收斂的的迭代過(guò)程才有意義，為此我們首先要研究先要研究 (x)的不定點(diǎn)的存在性及迭代法的收斂性的不定點(diǎn)的存在性及迭代法的收斂性.上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)7.2.2 不動(dòng)點(diǎn)的存在性與迭代法的收斂性不動(dòng)點(diǎn)的存在性與迭代法的收斂性 首先考察首先考察 (x)在在a, b上不動(dòng)點(diǎn)的存在唯一性上不動(dòng)點(diǎn)的存在唯一性. 定理定理1 設(shè)設(shè) (x)Ca, b滿足以下兩個(gè)條件：滿足以下兩個(gè)條件：1 對(duì)任意對(duì)任意xa, b有有a (x)b. .)4 . 2(.)()(yxLyx 2 存在正數(shù)存在正數(shù)La及及 (b)0, f(b)= (

18、b)- -b0, 由連續(xù)函數(shù)性質(zhì)可知存在由連續(xù)函數(shù)性質(zhì)可知存在 x*(a, b) 使使 f(x*)=0，即，即x*= (x*)，x*即為即為 (x)的不動(dòng)點(diǎn)的不動(dòng)點(diǎn). 再證不動(dòng)點(diǎn)的再證不動(dòng)點(diǎn)的唯一性唯一性. 設(shè)設(shè)x1*, x2*a, b都是都是 (x)的不動(dòng)點(diǎn)，則由的不動(dòng)點(diǎn)，則由(2.4)得得.)()(21212121 xxxxLxxxx 引出矛盾，故引出矛盾，故 (x)的不動(dòng)點(diǎn)只能是唯一的的不動(dòng)點(diǎn)只能是唯一的. .證畢證畢. . 在在 (x)的不動(dòng)點(diǎn)存在唯一的情況下，可得到迭代的不動(dòng)點(diǎn)存在唯一的情況下，可得到迭代法法(2.2)收斂的一個(gè)收斂的一個(gè)充分條件充分條件.上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)

19、下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè) 定理定理2 設(shè)設(shè) (x)Ca, b滿足定理滿足定理1中的兩個(gè)條件，中的兩個(gè)條件，則對(duì)任意則對(duì)任意x0a, b，由，由(2.2)得到的迭代序列得到的迭代序列xk收斂收斂到的不動(dòng)點(diǎn)到的不動(dòng)點(diǎn)x*，并有，并有誤差估計(jì)式誤差估計(jì)式)6 . 2(.1)5 . 2(.1101kkkkkxxLLxxxxLLxx 證明證明 設(shè)設(shè)x*a, b是是 (x)在在a, b上的唯一不動(dòng)點(diǎn)上的唯一不動(dòng)點(diǎn), ,由條件由條件1，可知，可知xka, b，再由，再由(2.4)得得.)()(011xxLxxLxxxxkkkk 因因0L1時(shí)稱(chēng)時(shí)稱(chēng)超線性收斂超線性收斂，p=2時(shí)稱(chēng)時(shí)稱(chēng)平方收斂平方收斂.上頁(yè)上頁(yè)上頁(yè)

20、上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè) 定理定理4 對(duì)于迭代過(guò)程對(duì)于迭代過(guò)程xk+1= (xk)，如果，如果 ( (p) )(x)在在所求根所求根x*的鄰近連續(xù)，并且的鄰近連續(xù)，并且)8 . 2(. 0)(, 0)()()()()1( xxxxpp 則該迭代過(guò)程在則該迭代過(guò)程在x*的鄰近是的鄰近是p階收斂的階收斂的. 證明證明 由于由于(x*)=0，根據(jù)定理，根據(jù)定理3立即可以斷定迭立即可以斷定迭代過(guò)程代過(guò)程xk+1= (xk)具有局部收斂性具有局部收斂性. 再將再將 (xk)在根在根x*處做泰勒展開(kāi)處做泰勒展開(kāi), 利用條件利用條件(2.8), 則有則有.,)(!)()()()(之間之間與與在在

21、 xxxxpxxkpkpk 注意到注意到 (xk)=xk+1， (x*)= x*，由上式得，由上式得上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè),)(!)()(1pkpkxxpxx 因此對(duì)迭代誤差，令因此對(duì)迭代誤差，令k時(shí)有時(shí)有這表明迭代過(guò)程這表明迭代過(guò)程xk+1= (xk)確實(shí)為確實(shí)為p階收斂階收斂. 證畢證畢. .!)()(1pxeeppkk 上述定理告訴我們，迭代過(guò)程的收斂速度依賴(lài)于上述定理告訴我們，迭代過(guò)程的收斂速度依賴(lài)于迭代函數(shù)迭代函數(shù) (x)的選取的選取. 如果如果xa, b但但 (x)0時(shí)，則時(shí)，則該迭代過(guò)程只可能是線性收斂該迭代過(guò)程只可能是線性收斂.上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)

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

23、 上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)假設(shè)假設(shè) (x)改變不大改變不大, 近似地取某個(gè)近似值近似地取某個(gè)近似值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 上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè). 0lim1 xxxxkkk在計(jì)算了在計(jì)算了x1及及x2之后，可用

24、上式右端作為之后，可用上式右端作為x*的新近似的新近似,記作記作x1，一般情形是由，一般情形是由xk計(jì)算計(jì)算xk+1, xk+2，記，記它表明序列它表明序列xk的收斂速度比的收斂速度比xk的收斂速度快的收斂速度快.22121122121()()(3.2)22(0,1,).kkkkkkkkkkkkkxxxxxxxxxxxxxk (3.2)式稱(chēng)為式稱(chēng)為埃特金埃特金(Aitken) 2加速方法加速方法. 可以證明可以證明或者或者上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)也稱(chēng)為也稱(chēng)為埃特金埃特金 ( Aitken ) 外推法外推法. 可以證明可以證明:)(1kkxx 為線性收斂為線性收斂,則埃特

25、金法為平方收斂則埃特金法為平方收斂； 這個(gè)加速迭代法也可寫(xiě)成下面格式這個(gè)加速迭代法也可寫(xiě)成下面格式(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 階階若若上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè) 例題例題 求方程求方程 x = e x 在在 x=0.5 附近的根附近的根. 解解 取取 x0=0.5, 迭代格式迭代格式x25=x26=0.5671433 若對(duì)此格式用埃

26、特金法若對(duì)此格式用埃特金法, 則則kxkex 1 得得(1)1(1)(2)11(2)(1)2(2)1111(2)(1)11()2kkxxkkkkkkkkkxexexxxxxxx 上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)(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 xxxxxxxxx由此可見(jiàn)

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

28、森斯蒂芬森(Steffensen)迭代法迭代法. 上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè) 實(shí)際上實(shí)際上(3.3)是將不定點(diǎn)迭代法計(jì)算兩步合并成一是將不定點(diǎn)迭代法計(jì)算兩步合并成一步得到的，可將它寫(xiě)成另一種不動(dòng)點(diǎn)迭代步得到的，可將它寫(xiě)成另一種不動(dòng)點(diǎn)迭代)4 . 3(), 1 , 0()(1 kxxkk )5 . 3(.)(2)()()(2xxxxxxx 其中其中 對(duì)不動(dòng)點(diǎn)迭代對(duì)不動(dòng)點(diǎn)迭代(3.5)有以下局部收斂性定理有以下局部收斂性定理. 定理定理5 若若x*為為(3.5)定義的迭代函數(shù)定義的迭代函數(shù)(x)的不動(dòng)點(diǎn)，的不動(dòng)點(diǎn)，則則x*為為 (x)的不定點(diǎn)的不定點(diǎn). 反之，若反之，若x*為

29、為 (x)的不動(dòng)點(diǎn)，的不動(dòng)點(diǎn)，設(shè)設(shè)(x)存在，存在，(x)1，則，則x*是是(x)的不動(dòng)點(diǎn)，且的不動(dòng)點(diǎn)，且斯斯蒂芬森迭代法蒂芬森迭代法(3.3)是是2階收斂的階收斂的. 上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)7.3 一元方程的常用迭代法一元方程的常用迭代法7.3.1 牛頓法及其收斂性牛頓法及其收斂性)()()(000 xxxfxfxf 對(duì)于方程對(duì)于方程f(x)=0，如果，如果f(x)是線性函數(shù)，則它的是線性函數(shù)，則它的求根是容易的求根是容易的. 牛頓法實(shí)質(zhì)上是一種線性化方法，其牛頓法實(shí)質(zhì)上是一種線性化方法，其基本思想是將非線性方程基本思

30、想是將非線性方程f(x)=0逐步歸結(jié)為某種線性逐步歸結(jié)為某種線性方程來(lái)求解方程來(lái)求解. 設(shè)已知方程設(shè)已知方程f(x)=0有近似根有近似根x0，且在，且在 x0附近附近f(x)可可用一階泰勒多項(xiàng)式近似，表示為用一階泰勒多項(xiàng)式近似，表示為上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)當(dāng)當(dāng)f (x0)0時(shí)，方程時(shí)，方程f(x)=0可用線性方程可用線性方程(切線切線) 近似代近似代替，即替，即 f(x0)+f (x0)(x- -x0)=0. (3.1)解此線性方程得解此線性方程得)()(000 xfxfxx 得迭代公式得迭代公式此式稱(chēng)為此式稱(chēng)為牛頓牛頓(Newton)迭代公式迭代公式.1()(0,1

31、,),(3.2)()kkkkf xxxkfx 上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)牛頓法有顯然的牛頓法有顯然的幾何意義幾何意義，方程，方程f(x)=0的根的根x*可可解釋為曲線解釋為曲線y=f(x)與與x軸交點(diǎn)的橫坐標(biāo)軸交點(diǎn)的橫坐標(biāo). 設(shè)設(shè)xk是根是根x*的的某個(gè)近似值，過(guò)曲線某個(gè)近似值，過(guò)曲線y=f(x)上橫坐標(biāo)為上橫坐標(biāo)為xk的點(diǎn)的點(diǎn)Pk引切引切線，并將該切線與線，并將該切線與x軸交點(diǎn)的橫坐標(biāo)軸交點(diǎn)的橫坐標(biāo)xk+1作為作為x*的新的的新的近似值近似值. 注意到切線方程為注意到切線方程為這樣求得的值這樣求得的值xk+1必滿足必滿足(3.1), 從而就是牛頓公式從而就是牛頓公式(3

32、.2)的計(jì)算結(jié)果的計(jì)算結(jié)果. 由于這由于這種幾何背景，所以牛頓迭種幾何背景，所以牛頓迭代法也稱(chēng)代法也稱(chēng)切線法切線法.xyx*xky=f(x)xk+1PkPk+1xk+2).)()(kkkxxxfxfy 上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)牛頓迭代法的收斂性牛頓迭代法的收斂性)()()(xfxfxx 設(shè)設(shè)x*是是f(x)的一個(gè)的一個(gè)單根單根，即，即f(x*)=0，f (x*)0, 有有. 0)()()(, 0)()()()(2* xfxfxxfxfxfx 牛頓迭代法的迭代函數(shù)為牛頓迭代法的迭代函數(shù)為可得可得2112!22( )()1()limlim()0.()()2!2()kkkkk

33、kxxxxfxxxxxxfx 上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)由此得到，當(dāng)由此得到，當(dāng)x*為為單根單根時(shí)，牛頓迭代法在根時(shí)，牛頓迭代法在根x*的的鄰近是鄰近是二階二階(平方平方)收斂收斂的的.關(guān)于關(guān)于x*為為重根重根時(shí)，牛頓迭代法在根時(shí)，牛頓迭代法在根x*的鄰近的收的鄰近的收斂性在后面討論斂性在后面討論.定理定理(局部收斂性局部收斂性) 設(shè)設(shè)f C2a, b, 若若x*為為f(x)在在a, b上的根，且上的根，且f (x*) 0，則存在，則存在x*的鄰域的鄰域U, 使得任取初使得任取初值值x0 U，牛頓法產(chǎn)生的序列，牛頓法產(chǎn)生的序列xk收斂到收斂到x*，且滿足，且滿足即有下面的

34、局部收斂性定理即有下面的局部收斂性定理.)(2)()(lim21 xfxfxxxxkkk上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)Newton法的收斂性依賴(lài)于法的收斂性依賴(lài)于x0 的選取。的選取。 局部收斂定理對(duì)初始值局部收斂定理對(duì)初始值 x0 要求較高。要求較高。x*x0 x0 x0 上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè) 解解 將原方程化為將原方程化為xex= 0，則，則牛頓迭代公式為牛頓迭代公式為kkxxkkkeexxx 11取取 x0=0.5，迭代得，迭代得x1=0.566311, x2=0.5671431, x3=0.5671433. f(x)=xex， f (x)=

35、1+ex， 例例1 用牛頓迭代法求方程用牛頓迭代法求方程x=ex在在x=0.5附近的根附近的根.上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)牛頓法應(yīng)用舉例牛頓法應(yīng)用舉例例例2 對(duì)于給定的正數(shù)對(duì)于給定的正數(shù)C，應(yīng)用牛頓法解二次方程，應(yīng)用牛頓法解二次方程, 02 Cx我們現(xiàn)在證明，這種迭代公式對(duì)于任意初值我們現(xiàn)在證明，這種迭代公式對(duì)于任意初值x00都是收斂的都是收斂的.可導(dǎo)出求開(kāi)方值可導(dǎo)出求開(kāi)方值 的計(jì)算程序的計(jì)算程序C.21)()()(,)(2 xCxxfxfxxCxxf 11.(3.3)2kkkCxxx 上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)事實(shí)上，對(duì)事實(shí)上，對(duì)(3.3)式施行配

36、方整理，易知式施行配方整理，易知 .2121CxxCxkkk 以上兩式相除得以上兩式相除得.211 CxCxCxCxkkkk據(jù)此反復(fù)遞推有據(jù)此反復(fù)遞推有200.(3.4)kkkxCxCxCxC 上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)記記00.xCqxC 整理整理(3.4)式，得式，得.1222kkqqCCxk 對(duì)任意初值對(duì)任意初值x00，總有，總有|q|0)重根重根時(shí)，則時(shí)，則f(x)可表為可表為 f(x)=(x- -x*)mg(x).其中其中g(shù)(x*)0，此時(shí)用牛頓迭代法，此時(shí)用牛頓迭代法(3.2)求求x*仍然收斂，仍然收斂，只是只是收斂速度將大大減慢收斂速度將大大減慢. 事實(shí)上，

37、因?yàn)榈绞聦?shí)上，因?yàn)榈?()()()()()()(*1kkkkkkkkkkxgxxxmgxgxxxxfxfxx 令令ek=xkx*，則，則)()()(*11kkkkkkkkxgexmgxgeexxe 上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)可見(jiàn)用牛頓法求方程的重根時(shí)僅為可見(jiàn)用牛頓法求方程的重根時(shí)僅為線性收斂線性收斂. 011)()()(1limlim1 mxgexmgxgeekkkkkkkk從而有從而有兩種兩種提高求重根的收斂速度提高求重根的收斂速度的的方法方法：1) ) 取如下迭代函數(shù)取如下迭代函數(shù). 0)(,)()()( xxfxfmxx 則則1()(0,1,).(3.6

38、)()kkkkf xxxmkf x 得到迭代公式得到迭代公式求求m重根具有重根具有2階收斂階收斂. 但要知道但要知道x*的的重?cái)?shù)重?cái)?shù)m.上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)對(duì)對(duì)f(x)=(x- -x*)mg(x), g(x*)0，令函數(shù)，令函數(shù).)()()()()()()()(xgxxxmgxgxxxfxfx 則為求則為求(x)=0的單根的單根x*的問(wèn)題，對(duì)它用牛頓法是二階的問(wèn)題，對(duì)它用牛頓法是二階(平方平方)收斂的收斂的. 其迭代函數(shù)為其迭代函數(shù)為2) ) 將求重根問(wèn)題化為求單根問(wèn)題將求重根問(wèn)題化為求單根問(wèn)題. .)()()()()()()()(2xfxfxfxfxfxxxxx

39、12()()(0,1,). (3.7)()()()kkkkkkkf xfxxxkfxf xfx 從而構(gòu)造出迭代方法為從而構(gòu)造出迭代方法為上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè) 例例3 用牛頓迭代法求函數(shù)用牛頓迭代法求函數(shù) f(x)=(x- -1)sin(x- -1)+3x- -x3+1=0 在在0.95附近之根附近之根. 解解 取取x0 = 0.95 用牛頓迭用牛頓迭代法求得的代法求得的xk見(jiàn)右表見(jiàn)右表. 可見(jiàn)可見(jiàn)xk收斂很慢收斂很慢.kxk01234560.950.97442790.98705830.99348780.99673280.99835760.9991901上頁(yè)上頁(yè)上頁(yè)上

40、頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)由重根數(shù)由重根數(shù)m=2, 用用(3.7)式加速法，作式加速法，作求得求得 x0=0.95, x1=0.9988559, x2=x3=1.收斂速度大大加快于直接用牛頓迭代公式收斂速度大大加快于直接用牛頓迭代公式.1()()kkkkf xxxmf x 上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)簡(jiǎn)化牛頓法簡(jiǎn)化牛頓法牛頓法的牛頓法的優(yōu)點(diǎn)優(yōu)點(diǎn)是收斂快，是收斂快，缺點(diǎn)缺點(diǎn)每步迭代要計(jì)算每步迭代要計(jì)算f(xk)及及f (xk)，計(jì)算量較大，且有時(shí)，計(jì)算量較大，且有時(shí)f (xk)計(jì)算較困難；計(jì)算較困難；初始近似值初始近似值x0只在根只在根x*附近才能保證收斂，如附近才能

41、保證收斂，如x0給給的不合適可能不收斂的不合適可能不收斂. 為克服這兩個(gè)缺點(diǎn)，通常可用為克服這兩個(gè)缺點(diǎn)，通常可用下述方法下述方法. 簡(jiǎn)化牛頓法簡(jiǎn)化牛頓法，也稱(chēng)，也稱(chēng)平行弦法平行弦法，其迭代公式為，其迭代公式為1()0,0,1,.(3.5)kkkxxCf xCk 迭代函數(shù)為迭代函數(shù)為 (x)=x- -Cf(x). 上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)若若| (xk)|=|1- -Cf (x)|1，即取，即取0Cf (x)2. 在根在根x*附近成立，則迭代法附近成立，則迭代法(3.5)局部收斂局部收斂.在在(3.5)中取中取C=1/f (x0)，則稱(chēng)為簡(jiǎn)化牛頓法，這類(lèi)，則稱(chēng)為簡(jiǎn)化牛頓法

42、，這類(lèi)方法計(jì)算量省，但只有線性收斂，其方法計(jì)算量省，但只有線性收斂，其幾何意義幾何意義是用平是用平行弦與行弦與x軸交點(diǎn)作為軸交點(diǎn)作為x*的近似，見(jiàn)下圖的近似，見(jiàn)下圖.y=f(x)x0 x1x2x*上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)用牛頓法求方程用牛頓法求方程f(x)=0的根，每步除計(jì)算的根，每步除計(jì)算f(xk)外外還要算還要算f (xk)，當(dāng)函數(shù)，當(dāng)函數(shù)f(x)比較復(fù)雜時(shí)，計(jì)算比較復(fù)雜時(shí)，計(jì)算f (x)往往往往比較困難，為此可以利用已求函數(shù)值比較困難，為此可以利用已求函數(shù)值f(xk),f(xk- -1),來(lái)來(lái)回避導(dǎo)數(shù)值回避導(dǎo)數(shù)值f (xk)的計(jì)算的計(jì)算. 這類(lèi)方法是建立在插值原理

43、這類(lèi)方法是建立在插值原理基礎(chǔ)上的，下面介紹兩種常用方法基礎(chǔ)上的，下面介紹兩種常用方法.7.3.2 割線法和拋物線法割線法和拋物線法上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)1. 割線割線 (弦截弦截)法法設(shè)設(shè)xk,xk- -1是是f(x)=0的近似根，我們利用的近似根，我們利用f(xk),f(xk- -1)構(gòu)造一次插值多項(xiàng)式構(gòu)造一次插值多項(xiàng)式p1(x)，并用，并用p1(x)=0的根作為方程的根作為方程f(x)=0的新的近似根的新的近似根xk+1，由于，由于)1 . 5().()()()()(111kkkkkkxxxxxfxfxfxp 因此有因此有111().(5.2)()()kkkkkk

44、kxxxxf xf xf x 上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)這樣導(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的點(diǎn)分別為的點(diǎn)分別為Pk-1和和Pk, 則差商則差商 表示弦表示弦 的斜率的斜率, 弦弦 的方程為的方程為11)()( kkkkxxxfxfkkPP1 kkPP1 11()()()()kkkkkk

45、f xf xyf xx xxx 上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)Ox*xk+1xkPkxk- -1yxPk- -1因此，按因此，按(5.2)式求得式求得xk+1實(shí)際上是兩點(diǎn)弦實(shí)際上是兩點(diǎn)弦線線 與與x軸交點(diǎn)軸交點(diǎn)的橫坐標(biāo)的橫坐標(biāo)(令令y=0解出解出x即可即可).這種算法因此這種算法因此而形象地稱(chēng)為而形象地稱(chēng)為割線割線 (弦截弦截)法法.kkPP1 上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)割線法與牛頓法割線法與牛頓法 (切線法切線法)都是線性化分法，但兩都是線性化分法，但兩者有本質(zhì)的區(qū)別者有本質(zhì)的區(qū)別.牛頓法在計(jì)算牛頓法在計(jì)算xk+1時(shí)只用到前一步的時(shí)只用到前一步的值值x

46、k，而割線法要用到前面兩步的結(jié)果，而割線法要用到前面兩步的結(jié)果xk- -1,xk，因此，因此使用這種方法必須先給出兩個(gè)開(kāi)始值使用這種方法必須先給出兩個(gè)開(kāi)始值x0, x1.定理定理6 假設(shè)假設(shè)f(x)在根在根x*的鄰域內(nèi)的鄰域內(nèi): |x- -x*|具有具有二階連續(xù)導(dǎo)數(shù)，且對(duì)任意二階連續(xù)導(dǎo)數(shù)，且對(duì)任意x 有有f (x)0，所取的初，所取的初值值x0, x1 ，那么當(dāng)鄰域，那么當(dāng)鄰域充分小時(shí)，弦截法充分小時(shí)，弦截法(5.2)將將按階按階15618.21.p 收斂到收斂到x*. 這里這里p是方程是方程2- - -1=0的正根的正根.上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)因?yàn)橐驗(yàn)?5.2)式用

47、到前兩點(diǎn)式用到前兩點(diǎn)xk- -1和和xk的值，故此方法的值，故此方法又稱(chēng)為又稱(chēng)為雙點(diǎn)割線法雙點(diǎn)割線法.010().()()kkkkkxxxxf xf xf x 每步只用一個(gè)新點(diǎn)每步只用一個(gè)新點(diǎn)xk的值，此方法稱(chēng)為的值，此方法稱(chēng)為單點(diǎn)割線法單點(diǎn)割線法.如果把如果把(5.2)式中的式中的xk- -1改為改為x0，即迭代公式為，即迭代公式為上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)例題例題 用牛頓迭代法和割線法求方程用牛頓迭代法和割線法求方程 f(x)=x4+2x2x3=0， 在區(qū)間在區(qū)間(1, 1.5)內(nèi)之根內(nèi)之根(誤差為誤差為10- -9). 解解 取取x0=1.5，用牛頓法，用牛頓法,

48、可得可得x6=1.12412303030取取x0=1.5, x1=1，用，用雙點(diǎn)割線法雙點(diǎn)割線法，迭代，迭代6次得到同樣的次得到同樣的結(jié)果，而采用結(jié)果，而采用單點(diǎn)割線法單點(diǎn)割線法，則迭代，則迭代18次得次得 x18=1.124123029.上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)xyx*xky=f(x)xk+1PkPk+1xk+2y=f(x)x0 x1x2x*Ox*xk+1xkPkxk- -1yxPk- -1Ox*xk+1xky=P2(x)xk- -2yxy=f(x)xk- -1y=f(x)牛頓法牛頓法簡(jiǎn)化牛頓法簡(jiǎn)化牛頓法割線法割線法拋物線法拋物線法上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)

49、下頁(yè)下頁(yè)下頁(yè)2 拋物線法拋物線法設(shè)已知方程設(shè)已知方程f(x)=0的三個(gè)近似根的三個(gè)近似根xk,xk- -1,xk- -2，我們，我們以這三點(diǎn)為節(jié)點(diǎn)構(gòu)造二次插值多項(xiàng)式以這三點(diǎn)為節(jié)點(diǎn)構(gòu)造二次插值多項(xiàng)式p2(x)，并適當(dāng)選，并適當(dāng)選取取p2(x)的一個(gè)零點(diǎn)的一個(gè)零點(diǎn)xk+1作為新的近似根，這樣確定的作為新的近似根，這樣確定的迭代過(guò)程稱(chēng)為迭代過(guò)程稱(chēng)為拋物線法拋物線法，亦稱(chēng)為，亦稱(chēng)為密勒密勒(Mller)法法. 在在幾何圖形上幾何圖形上, 這種方法的基本思想是用拋物線這種方法的基本思想是用拋物線y=p2(x)與與x軸的交點(diǎn)軸的交點(diǎn)xk+1作為所求根作為所求根x*的近似位置的近似位置.上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)

50、上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)Ox*xk+1xky=P2(x)xk- -2yxy=f(x)xk- -1拋物線法的拋物線法的幾何意義幾何意義見(jiàn)下面圖形見(jiàn)下面圖形.上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)現(xiàn)在推導(dǎo)拋物線法的計(jì)算公式現(xiàn)在推導(dǎo)拋物線法的計(jì)算公式. 插值多項(xiàng)式插值多項(xiàng)式).)(,)(,)()(12112 kkkkkkkkkxxxxxxxfxxxxfxfxp有兩個(gè)零點(diǎn)有兩個(gè)零點(diǎn)1121,().kkkkkkkkf xxf xxxxx 12122 ().(5.3)4 () ,kkkkkkkkkf xxxf xf xxx 式中式中上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)為了在為了在

51、(5.3)式定出一個(gè)值式定出一個(gè)值xk+1，我們需要討論根，我們需要討論根式前正負(fù)號(hào)的取舍問(wèn)題式前正負(fù)號(hào)的取舍問(wèn)題.在在xk, xk- -1, xk- -2三個(gè)近似值中，自然假定三個(gè)近似值中，自然假定xk更接近更接近所求的根所求的根x*，這時(shí)，為了保證精度，我們選，這時(shí)，為了保證精度，我們選(5.3)式中式中接近接近xk的一個(gè)值作為新的近似根的一個(gè)值作為新的近似根xk+1. 為此，為此，只要取根只要取根式前的符號(hào)與式前的符號(hào)與的符號(hào)相同的符號(hào)相同.12122 ().4 () ),sgn(kkkkkkkkkkf xxxf xf xxx 上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)上頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè)下頁(yè) 例例 用拋物線法求解方程用拋物線法求解方程f(x)=xex- -1=0. 解解 取取x0=0.5, x1=0.6, x2=0.56532開(kāi)始，計(jì)算得開(kāi)始，計(jì)算得f(x0)=- -0.175639, f(x1)=0.093271, f(x2)=- -0.005031.fx1,x0=2.68910, fx2,x1=2.83373, fx2,x1,x0=2.21418.故故.75694. 2)(,1201212 xxxxxfxxf 代入代入(5.3)式求得式求得.56714. 0,)(4)(201222223