數(shù)值分析第7章ppt課件

1、1第第7 7章章 非線性方程與方程組的數(shù)值解法非線性方程與方程組的數(shù)值解法7.1 方程求根與二分法 7.2 不動點(diǎn)迭代法及其收斂性 7.3 迭代收斂的加速方法 7.4 牛頓法 7.5 弦截法與拋物線法 7.6 求根問題的敏感性與多項式的零點(diǎn)7.7 非線性方程組的數(shù)值解法27.1 方程求根與二分法方程求根與二分法 7.1.1 引言引言0)(xf（1.1） 本章主要討論求解單變量非線性方程 其中 也可以是無窮區(qū)間. ,)(,RbabaCxfx 如果實(shí)數(shù) 滿足 ，則稱 是方程(1.1)的根，或稱 是 的零點(diǎn).*x)(xf0*)(xf*x*x3假設(shè) 可分解為 )(xf),(*)()(xgxxxfm 假

2、設(shè) 是 的 重零點(diǎn)，且 充分光滑，那么*x)(xfm)(xg,0*)(*)(*)()1(xfxfxfm.0*)()(xfm其中 為正整數(shù)，且 則稱 為方程(1.1)的 重根，或 為 的 重零點(diǎn)， 時為單根.m.0*)(xg1m*xm*x)(xfm 如果函數(shù) 是多項式函數(shù)，即),0()(01110aaxaxaxaxfnnnn（1.2）)(xf其中 為實(shí)數(shù)，則稱方程(1.1)為 次代數(shù)方程. ), 1 ,0(,00niaain4,010sine10/xx 根據(jù)代數(shù)基本定理可知, 次方程在復(fù)數(shù)域有且只有 個根含重根， 重根為 個根）. mmnn 時的求根公式是熟知的， 時的求根公式可在數(shù)學(xué)手冊中查到

3、，但比較復(fù)雜不適合數(shù)值計算，當(dāng) 時就不能用公式表示方程的根，所以 時求根仍用一般的數(shù)值方法5n2, 1n4, 3n3n 另一類是超越方程，例如它在整個 軸上有無窮多個解，假設(shè) 取值范圍不同，解也不同，因此討論非線性方程(1.1)的求解必須強(qiáng)調(diào) 的定義域，即 的求解區(qū)間xxxx.,ba5 非線性問題一般不存在直接的求解公式，故沒有直接方法求解，都要使用迭代法. 迭代法要求先給出根 的一個近似，假設(shè) 且 ，根據(jù)連續(xù)函數(shù)性質(zhì)可知 在 內(nèi)至少有一個實(shí)根，這時稱 為方程(1.1)的有根區(qū)間.*x,)(baCxf0)()(bfaf0)(xf),(ba,ba 通常可通過逐次搜索法求得方程 的有根區(qū)間.0)(

4、xf6 解 根據(jù)有根區(qū)間定義，對 的根進(jìn)行搜索計算，結(jié)果如下： 0)(xf 例1 求方程 的有根區(qū)間.077.418 .381 .11)(23xxxxf 7-1 0123456()xfx表計 算 結(jié) 果的 符 號由此可知方程的有根區(qū)間為 .6,5,4,3,2,177.1.2 二分法二分法 考察有根區(qū)間 ，取中點(diǎn) 將它分為兩半，,ba2/)(0bax假設(shè)中點(diǎn) 不是 的零點(diǎn)，然后進(jìn)行根的搜索.0 x)(xf 檢查 與 是否同號，如果同號，說明所求的根 在 的右側(cè),這時令否則 必在 的左側(cè)，這時令見圖7-1. *x0 x)(0 xf)(af*x0 x,01xa ;1bb ,1aa .01xb 圖7-

5、1 不管出現(xiàn)哪一種情況，新的有根區(qū)間 的長度僅為 的一半. ,11ba,ba8 對壓縮了的有根區(qū)間 又可施行同樣的方法，即用中點(diǎn) 將區(qū)間 再分為兩半，然后通過根的搜索判定所求的根在 的哪一側(cè)，從而又確定一個新的有根區(qū)間 ，其長度是 的一半.2/)(111bax,11ba,11ba1x,22ba,11ba 如此反復(fù)二分下去，即可得出一系列有根區(qū)間 ,2211kkbabababa其中每個區(qū)間都是前一個區(qū)間的一半，因而 的長度 ,kkbakkkabab2/)(當(dāng) 時趨于零.k9 就是說，如果二分過程無限地繼續(xù)下去，這些區(qū)間最終必收縮于一點(diǎn) ，該點(diǎn)顯然就是所求的根.*x作為根的近似，則在二分過程中可以

6、獲得一個近似根的序列 ,210kxxxx該序列必以根 為極限.*x 每次二分后，設(shè)取有根區(qū)間 的中點(diǎn) ,kkba2/)(kkkbax10 由于 只要二分足夠多次即 充分大），便有 k,*kxx這里 為預(yù)定的精度.（1.3）1*() / 2() / 2,kkkkxxbaba11 解 這里 ，而5.1,0.1ba 取 的中點(diǎn) ，將區(qū)間二等分，由于 ，即 與 同號，故所求的根 必在 右側(cè)，這時應(yīng)令 ，而得到新的有根區(qū)間,ba25. 10 x0)(0 xf)(0 xf)(af*x0 x5.1,25.1101bbxa 如此反復(fù)二分下去, 按誤差估計1.3式,欲使0)(,0)(bfaf.,11ba（1.3

7、）,2/ )(*1kkabxx只需 ，即只要二分6次，便能達(dá)到預(yù)定的精度. 6k2/ )(*kkkabxx12/ )(kab,005.021211k 例2 求方程 在區(qū)間 內(nèi)的一個實(shí)根，要求準(zhǔn)確到小數(shù)點(diǎn)后第2位.01)(3xxxf5 .1 , 0 .1 12 計算結(jié)果如表7-2. 72()01.01.51.2511.251.51.37521.251.3751.312531.31251.3751.343841.31251.34381.328151.31251.32811.320361.32031.32811.3242kkkkkabxfx符 號 表13 二分法是計算機(jī)上的一種常用算法，計算步驟為：

8、 步驟1 準(zhǔn)備 計算 在有根區(qū)間 端點(diǎn)處的值 )(xf).(),(bfaf,ba 步驟2 二分 計算 在區(qū)間中點(diǎn) 處的值 )(xf2ba ).2(baf 步驟3 判斷 假設(shè) ，那么 即是根，計算過程結(jié)束，否則檢驗. 0)2( baf2ba 假設(shè) ，則以 替代 ，否則以0)()2(afbaf2ba b替代 . 2ba a14此時中點(diǎn) 即為所求近似根. 2ba 誤差 ， 反復(fù)執(zhí)行步驟2和步驟3，直到區(qū)間 長度小于允許,ba157.2 不動點(diǎn)迭代法及其收斂性不動點(diǎn)迭代法及其收斂性 7.2.1 不動點(diǎn)與不動點(diǎn)迭代法不動點(diǎn)與不動點(diǎn)迭代法 將方程1.1改寫成等價的形式 ).(xx（2.1）假設(shè) 滿足 ，那

9、么 ；反之亦然，稱為函數(shù) 的一個不動點(diǎn). *x0*)(xf*)(*xx*x)(x 求 的零點(diǎn)就等價于求 的不動點(diǎn).)(xf)(x 選擇一個初始近似值 ，將它代入(2.1)右端，即可求得0 x).(01xx0)(xf（1.1）16如此反復(fù)迭代計算 )., 1 ,0()(1kxxkk（2.2） 稱為迭代函數(shù).)(x 如果對任何 ，由2.2得到的序列 有極限 ,0bax kx.*limxxkk則稱迭代方程(2.2)收斂，且 為 的不動點(diǎn)，故稱2.2為不動點(diǎn)迭代法.*)(*xx)(x17 方程 的求根問題在 平面上就是要確定曲線 與直線 的交點(diǎn) )(xxxy)(xyxy .*P 就是說，迭代過程實(shí)質(zhì)上

10、是一個逐步顯示化的過程. 對于 的某個近似值 ，在曲線 上可確定一點(diǎn) ，它以 為橫坐標(biāo)，而縱坐標(biāo)則等于 *x0 x)(xy0P0 x.)(10 xx過 引平行 軸的直線，設(shè)此直線交直線 于點(diǎn) ，0Pxxy 1Q然后過 再作平行于 軸的直線，1Qy與曲線 的交點(diǎn))(xy 上述迭代法是一種逐次逼近法，其基本思想是將隱式方程 歸結(jié)為一組顯式的計算公式 .)(xx)(1kkxx18記作 ，1P則點(diǎn) 的橫坐標(biāo)為 ，1P1x.)(21xx縱坐標(biāo)則等于在曲線 上得到點(diǎn)列，)(xy12,PP ，其橫坐標(biāo)分別為19 例3 求方程 01)(3xxxf（2.3）在 附近的根 5.10 x.*x 解 設(shè)將方程2.3改

11、寫成下列形式 . 13xx依公式 求得的迭代值)(1kkxx.,21xx 如果點(diǎn)列 趨向于點(diǎn) ，則相應(yīng)的迭代值 收斂到所求的根 kP*Pkx.*x據(jù)此建立迭代公式 207-301.551.3247611.3572161.3247321.3308671.3247231.3258881.3247241.32494kkkxkx 表).,2,1 ,0(131kxxkk各步迭代的結(jié)果見表7-3. 認(rèn)為 實(shí)際上已滿足方程(2.3)，即為所求的根.7x 如果僅取6位數(shù)字，那么結(jié)果 與 完全相同，這時可以7x8x21但若采用方程2.3的另一種等價形式13 xx建立迭代公式 .131kkxx仍取迭代初值 ，則有

12、 5 .10 x.39.12,375.221xx結(jié)果會越來越大，不可能趨于某個極限. 這種不收斂的迭代過程稱作是發(fā)散的.如圖7-3. 一個發(fā)散的迭代過程，縱使進(jìn)行了千百次迭代，其結(jié)果也是毫無價值的.227.2.2 不動點(diǎn)的存在性與迭代法的收斂性不動點(diǎn)的存在性與迭代法的收斂性 首先考察 在 上不動點(diǎn)的存在唯一性. ,ba)(x 定理1 設(shè) 滿足以下兩個條件：,)(baCx 1. 對任意 有 ,bax bxa)( 2. 存在正常數(shù) ，使對任意 都有 1L,bayx.)()(yxLyx（2.4）那么 在 上存在唯一的不動點(diǎn) )( x,ba.*x 證明 略 23.1*01xxLLxxkk（2.5） 定

13、理2 設(shè) 滿足定理1中的兩個條件，那么對任意 ，由2.2得到的迭代序列 收斂到 的不動點(diǎn) ，并有誤差估計 ,)(baCx ,0baxkx)( x*x)., 1 ,0()(1kxxkk（2.2） 在不動點(diǎn)存在唯一的情況下，可以得到迭代法2.2）收斂的一個充分條件. 證明 略 24,1)(Lx（2.7）表明定理1中的條件2可用2.7替代. 對定理2和定理1中的條件2，假如且對任意 有 ,bax ,)(1baCx 25 例3中，當(dāng) 時， ,在區(qū)間 中， ，故2.7成立.31)(xx3/2)1(31)(xx2, 114131)(3/1 x 又因 ，故定理1中條件1也成立.所以迭代法是收斂的. 23)(

14、2133x 而當(dāng) 時， ，在區(qū)間 中 不滿足定理條件.1)(3 xx23)(xx2, 11)( x,1)(Lx（2.7）267.2.3 局部收斂性與收斂階局部收斂性與收斂階 定理的條件有時不易檢驗，實(shí)際應(yīng)用時通常只在不動點(diǎn) 的鄰近考察其收斂性，即局部收斂性.*x 上面給出了迭代序列 在區(qū)間 上的收斂性，kx,ba通常稱為全局收斂性. 定義1 設(shè) 有不動點(diǎn) ，如果存在 的某個鄰域 對任意 ，迭代2.2產(chǎn)生的序列 且收斂到 ，則稱迭代法2.2局部收斂.)( x*x,*: xxRRx 0,Rxk*x*x)., 1 ,0()(1kxxkk（2.2）27 證明 略 定理3 設(shè) 為 的不動點(diǎn)， 在 的某個

15、鄰域連續(xù)，且 ，則迭代法2.2局部收斂.*x)(x)( x*x1*)( x)., 1 ,0()(1kxxkk（2.2）28 現(xiàn)在討論迭代序列的收斂速度. 例4 用不同方法求方程 的根 032x.3* x 解 這里 ，可改寫為各種不同的等價形式 其不動點(diǎn)為 由此構(gòu)造不同的迭代法：3)(2 xxf),( xx.3* x,3)1(21kkkxxx,12)(xx.1132)3(*)(x,3)(2xxx,3)2(1kkxx,3)(xx ,3)(2xx.1*)( x),3(41)3(21kkkxxx),3(41)(2xxx,211)(xx.1134.0231*)( x29取 ，對上述4種迭代法，計算三步所

16、得的結(jié)果如下表. 20 x),3(21)4(1kkkxxx),3(21)(xxx),31(21)(2xx.0)3(*)(x01237402222131.51.751.752921.734751.7321433871.51.7323611.732051kkxxxxx 表計算結(jié)果迭代法迭代法迭代法迭代法(1)(2)(3)(4)30 從計算結(jié)果看到迭代法1及2均不收斂，且它們均不滿足定理3中的局部收斂條件. 注意 .7320508.13 迭代法3和4滿足局部收斂條件，且迭代法4比3收斂快，原因在于迭代法4中 . 0*)( x012302222131.51.751.752921.734751.7321

17、433871.51.7323611.732051kkxxxxx迭代法迭代法迭代法迭代法(1)(2)(3)(4)31),0常數(shù)(1CCeepkk則稱該迭代過程是 階收斂的. p 特別地, 時稱線性收斂，)1(1Cp 定義2 設(shè)迭代過程 收斂于方程的根 ，如果迭代誤差 當(dāng) 時成立下列漸近關(guān)系式)(1kkxx)(xx*x*xxekkk1p時稱超線性收斂，2p時稱平方收斂. 32 定理4 對于迭代過程 ，假如 在所求根 的鄰近連續(xù)，并且 )(1kkxx)()(xp*x則該迭代過程在點(diǎn) 鄰近是 階收斂的. *xp,0*)(*)(*)()1( xxxp（2.8）,0*)(xp 證明 略. 如果當(dāng) 時 ，則

18、該迭代過程只可能是線性收斂. 上述定理說明，迭代過程的收斂速度依賴于迭代函數(shù) 的選取. )( x,bax 0)( x33 在例4中，迭代法3的 ，故它只是線性收斂.0*)( x 而迭代法4的 ，而 由定理4知 ，該迭代過程為2階收斂. 0*)( x.032*)( x2p,6)(3xx 347.3 迭代收斂的加速方法迭代收斂的加速方法 7.3.1 埃特金加速收斂方法埃特金加速收斂方法 設(shè) 是根 的某個近似值，用迭代公式迭代一次得 0 x*x)(01xx由微分中值定理，有 其中 介于 與 之間.0 x*x 假定 改變不大，近似地取某個近似值 ，)( xL*).(*01xxLxx（3.1）*)()(

19、*01xxxx*),)(0 xx 則有 35),(12xx由于 *),(*12xxLxx.*1021xxxxxxxx由此推知 在計算了 及 之后，可用上式右端作為 的新近似，記作 . 1x2x*x1x若將校正值 再迭代一次，又得 )(01xx將它與3.1式聯(lián)立，消去未知的 ，L有 01221202*xxxxxxx.2)(0122010 xxxxxx*).(*01xxLxx（3.1）36 可以證明 .0*lim1xxxxkkk它表明序列 的收斂速度比 的收斂速度快.kxkxkkkkkkkxxxxxxx122112)(（3.2）)., 1 ,0(/)(22kxxxkkk 一般情形是由 計算 ，kx

20、21,kkxx記 (3.2)稱為埃特金Aitken） 加速方法.2377.3.2 斯蒂芬森迭代法斯蒂芬森迭代法 埃特金方法不管原序列 是怎樣產(chǎn)生的，對 進(jìn)行加速計算，得到序列 . kxkxkx 如果把埃特金加速技巧與不動點(diǎn)迭代結(jié)合，則可得到如下的迭代法： 稱為斯蒂芬森(Steffensen)迭代法. ),(kkxy(),kkz y（3.3）)., 1 ,0(2)(21kxyzxyxxkkkkkkk38,)()(xxx, 0*)(*)(xxx知 的近似值 及 ，其誤差分別為 *xkxky,)()(kkkkkxyxxx.)()(kkkkkyzyyy 過 及 兩點(diǎn)做線性插值函數(shù).)(,(kkxx)(

21、,(kkyy它與 軸交點(diǎn)就是3.3中的 ，即方程 x1kx0)()()()(kkkkkkxxxyxyx的解 它的理解為，要求 的根 ，)(xx*x令39 實(shí)際上3.3是將不動點(diǎn)迭代法2.2計算兩步合并成一步得到的，可將它寫成另一種不動點(diǎn)迭代 ), 1 ,0()(1kxxkk（3.4）)()()()(kkkkkkxyxyxxxkkkkkkxyzxyx2)(2.1kx其中 .)(2)()()(2xxxxxxx（3.5）)., 1 ,0()(1kxxkk（2.2）（3.3）)., 1 ,0(2)(21kxyzxyxxkkkkkkk),(kkxy(),kkz y40 定理5 假設(shè) 為3.5定義的迭代函

22、數(shù) 的不動點(diǎn)，那么 為 的不動點(diǎn).反之，假設(shè) 為 的不動點(diǎn)，設(shè) 存在， ，那么 是 的不動點(diǎn)，且斯蒂芬森迭代法3.3是二階收斂的.*x)( x*x)(x*x)(x)( x 1*)( x*x)( x 解 例3中已指出, 下列迭代 131kkxx是發(fā)散的，現(xiàn)用(3.3)計算，取 .1)(3 xx 例5 用斯蒂芬森迭代法求解方程 . 01)(3xxxf計算結(jié)果如下表. （3.3）)., 1 ,0(2)(21kxyzxyxxkkkkkkk),(kkxy(),kkz y417501 .52 .3 7 5 0 01 2 .3 9 6 511 .4 1 6 2 91 .8 4 0 9 25 .2 3 8 8

23、 821 .3 5 5 6 51 .4 9 1 4 02 .3 1 7 2 831 .3 2 8 9 51 .3 4 7 1 01 .4 4 4 3 541 .3 2 4 8 01 .3 2 5 1 81 .3 2 7 1 451 .3 2 4 7 2kkkkxyz 表計 算 結(jié) 果 計算表明它是收斂的，這說明即使迭代法2.2不收斂，用斯蒂芬森迭代法3.3仍可能收斂. 更進(jìn)一步還可知：假設(shè)2.2為 p 階收斂，那么3.3為1p 階收斂.1()(0,1,).kkx xk（2.2）（3.3）21()(0,1,).2kkkkkkkyxxxkzyx(),kky x(),kkz y42 例6 求方程 在

24、 中的解.0e3)(2xxxf4, 3 解 由方程得等價形式 ，取對數(shù)得 23exx).(3lnln23ln2xxxx由此構(gòu)造迭代法 , 3lnln21kkxx且當(dāng) 時， ，4,3x4, 3)(x由于 , ,2)(xx 132)(max43xx根據(jù)定理2此迭代法是收斂的. 43 若取 迭代16次得 ，有六位有效數(shù)字.5.30 x73307.316x 若用3.3進(jìn)行加速，計算結(jié)果如下 ： 03.53.604143.6627813.738353.735903.7345923.73308kkkkxyz 這里計算2步相當(dāng)于2.2迭代4步結(jié)果與 一樣，16x說明用迭代法3.3的收斂速度比迭代法2.2快得

25、多.447.4 牛頓法牛頓法 7.4.1 牛頓法及其收斂性牛頓法及其收斂性 設(shè)已知方程 有近似根 （假定 )，kx0)(xf0)(kxf將函數(shù) 在點(diǎn) 展開，有 )(xfkx),)()()(kkkxxxfxfxf于是方程 可近似地表示為 0)(xf.0)()(kkkxxxfxf（4.1） 牛頓法是一種線性化方法，其基本思想是將非線性方程 逐步歸結(jié)為某種線性方程來求解.0)(xf45這是個線性方程，記其根為 ，1kx那么 的計算公式為 1kx),1 ,0()()(1kxfxfxxkkkk（4.2）這就是牛頓法. 牛頓法的幾何解釋. 方程 的根 可解釋為0)(xf*x曲線 與 軸的交點(diǎn)的橫坐標(biāo))(

26、xfy x（圖7-4). 46 設(shè) 是根 的某個近似值，過曲線 上橫坐標(biāo)為 的點(diǎn) 引切線，并將該切線與 軸的交點(diǎn)的橫坐標(biāo) 作為 的新的近似值. kx*x)( xfy kxkPx1kx*x 注意到切線方程為 ).)()(kkkxxxfxfy這樣求得的值 必滿足4.1），從而就是牛頓公式（4.2的計算結(jié)果. 1kx 由于這種幾何背景，牛頓法亦稱切線法.),1 ,0()()(1kxfxfxxkkkk（4.2）.0)()(kkkxxxfxf（4.1）47,)()()(xfxfxx由于 .)()()()(2xfxfxfx 由定理4得到，對(4.2)的迭代函數(shù)為 假定 是 的一個單根，即 ，則由上式知 于

27、是依據(jù)定理4可以斷定，牛頓法在根 的鄰近是平方收斂的. )( xf*x0*)(,0*)(xfxf0*)( x*x),1 ,0()()(1kxfxfxxkkkk（4.2）48 例7 用牛頓法解方程 .01exx（4.4） 解 這里牛頓公式為 ,1e1kxkkkxxxxk取迭代初值 ，迭代結(jié)果列于表7-6中. 5.00 x 所給方程4.4實(shí)際上是方程 的等價形式. xx e 若用不動點(diǎn)迭代到同一精度要迭代17次，可見牛頓法的收斂速度是很快的.7700.510.5710220.5671630.56714kkx表計算結(jié)果49牛頓法的計算步驟：牛頓法的計算步驟： 步驟1 準(zhǔn)備 選定初始近似值 ，計算 0

28、 x).(00 xff),(00 xff 步驟2 迭代 按公式 迭代一次，得新的近似值 ，計算 0001/ ffxx1x).(),(1111xffxff50 此處 是允許誤差，而 21,，；時當(dāng)時當(dāng)1101101CxxxxCxxx其中 是取絕對誤差或相對誤差的控制常數(shù)，可取C1.C 步驟4 修改 如果迭代次數(shù)達(dá)到預(yù)先指定的次數(shù) ，N或者 ，則方法失??；01f 否則以 替代 轉(zhuǎn)步驟2繼續(xù)迭代.),(111ffx),(000ffx 步驟3 控制 假如 滿足 或 ，則終止迭代，以 作為所求的根；否則轉(zhuǎn)步驟4. 1x1x121f517.4.2 牛頓法應(yīng)用舉例牛頓法應(yīng)用舉例 對于給定的正數(shù) ，應(yīng)用牛頓法

29、解二次方程 C,02 Cx可導(dǎo)出求開方值 的計算程序 C).(211kkkxCxx（4.5）這種迭代公式對于任意初值 都是收斂的. 00 x5278010110.750000210.723837310.723805410.723805kkx 表計算結(jié)果 解解 取初值取初值 ，對，對 按按(4.5)(4.5)式迭代式迭代3 3次便得次便得到精度為到精度為 的結(jié)果見表的結(jié)果見表7-8).7-8).100 x115C610 例8 求 . 115).(211kkkxCxx（4.5） 由于公式4.5對任意初值 均收斂，并且收斂的速度很快，因此可取確定的初值如 編成通用程序. 用這個通用程序求 ，也只需要

30、迭代7次便得到上面的結(jié)果10.723805.00 x10 x115537.4.3 簡化牛頓法與牛頓下山法簡化牛頓法與牛頓下山法 （1） 簡化牛頓法，也稱平行弦法.其迭代公式為 .,1 ,00)(1kCxCfxxkkk（4.7）迭代函數(shù) ).()(xCfxx 牛頓法的優(yōu)點(diǎn)是收斂快，缺點(diǎn)一是每步迭代要計算 及 ，計算量較大且有時 計算較困難，)(kxf)(kxf )(kxf 二是初始近似 只在根 附近才能保證收斂，如 給的不合適可能不收斂.為克服這兩個缺點(diǎn)，通?？捎孟率龇椒?0 x*x0 x54 若在根 附近成立 ，即取*x1)(1)(xfCx,2)(0 xfC則迭代法4.7局部收斂. 在4.7中

31、取 ，則稱為簡化牛頓法。)(10 xfC 這類方法計算量省，但只有線性收斂，其幾何意義是用平行弦與 軸交點(diǎn)作為 的近似. x*x55 （2 2牛頓下山法牛頓下山法. . 牛頓法收斂性依賴初值牛頓法收斂性依賴初值 的選取的選取. . 假如 偏離所求根 較遠(yuǎn)，則牛頓法可能發(fā)散.0 x*x 例如，用牛頓法求方程 .013 xx（4.8）在 附近的一個根 . 5.1x*x 設(shè)取迭代初值 ，用牛頓法公式 5.10 x131231kkkkkxxxxx（4.9）計算得 0 x56.32472.1,32520.1,34783.1321xxx迭代3次得到的結(jié)果 有6位有效數(shù)字. 3x 為了防止迭代發(fā)散，對迭代過

32、程再附加一項要求，即具有單調(diào)性： .)()(1kkxfxf（4.10）滿足這項要求的算法稱下山法. 131231kkkkkxxxxx（4.9） 但如果改用 作為迭代初值，則依牛頓法公式（4.9迭代一次得 這個結(jié)果反而比 更偏離了所求的根6.00 x.9.171x6 .00 x*1.32472.x 57 將牛頓法與下山法結(jié)合起來使用，即在下山法保證函數(shù)值穩(wěn)定下降的前提下，用牛頓法加快收斂速度. 將牛頓法的計算結(jié)果 )()(1kkkkxfxfxx與前一步的近似值 適當(dāng)加權(quán)平均作為新的改進(jìn)值 kx,)1(11kkkxxx（4.11）其中 稱為下山因子，(01),1 ,0()()(1kxfxfxxkk

33、kk（4.12）(4.12)稱為牛頓下山法. （4.11即為 58 選擇下山因子時從 開場，逐次將 減半進(jìn)行試算，1直到能使下降條件4.10成立為止. 若用此法解方程4.8），當(dāng) 時由4.9求得6.00 x ，它不滿足條件4.10）.9.171x 通過 逐次取半進(jìn)行試算，當(dāng) 時可求得32/1,140625.11x此時有 ，656643.0)(1xf顯然 . )()(01xfxf384.1)(0 xf而 由 計算 時 , 均能使條件4.10）成立. 計算結(jié)果如下 ： 1x,32xx1.)()(1kkxfxf（4.10）131231kkkkkxxxxx（4.9）.013 xx（4.8）59;186

34、6.0)(,36181.122xfx 即為 的近似.一般情況只要能使條件4.10成立，則可得到 ，從而使 收斂. 4x*x0)(limkkxfkx;00667.0)(,32628.133xfx.0000086.0)(,32472.144xfx.)()(1kkxfxf（4.10）607.4.4 重根情形重根情形 設(shè) ，整數(shù) ，那么 為方程 的 重根，此時有 )(*)()(xgxxxfm0*)(,2xgm*x0)(xfm.0*)(,0*)(*)(*)()1(xfxfxfxfmm只要 仍可用牛頓法4.2計算，此時迭代函數(shù) 0)(kxf)()()(xfxfxx的導(dǎo)數(shù)為 011*)(mx且 ，所以牛頓法

35、求重根只是線性收斂. 1*)( x),1 ,0()()(1kxfxfxxkkkk（4.2）61,)()()(xfxfmxx),1 ,0()()(1kxfxfmxxkkkk（4.13）求 重根，則具有2階收斂，但要知道 的重數(shù) . mm*x 構(gòu)造求重根的迭代法，還可令 ，)(/)()(xfxfx假設(shè) 是 的 重根，那么 *x0)(xfm,)(*)()()(*)()(xgxxxmgxgxxx若取 那么 . 0*)( x用迭代法 622()()()().()()()() xfxfx xxxxfxfxfx從而可構(gòu)造迭代法 ), 1 ,0()()()()()(21 kxfxfxfxfxfxxkkkkkk

36、k（4.14）它是二階收斂的. 對它用牛頓法，其迭代函數(shù)為 故 是 的單根. *x0)(x63 例9 方程 的根 是二重根，用上述三種方法求根.04424xx2* x （1） 牛頓法 .42844423241kkkkkkkkkxxxxxxxxx （2） 用4.13式 .22,221kkkkxxxxm （3） 用4.14式 .2)2(221kkkkkxxxxx取初值 ，計算結(jié)果如表7-9. 5 .10 x),1 ,0()()()()()(21 kxfxfxfxfxfxxkkkkkkk 解先求出三種方法的迭代公式： ,44)(24xxxf),1 ,0()()(1kxfxfmxxkkkk（4.13）

37、641239(1)(2)(3)11.458333333 1.416666667 1.41176470621.436607143 1.414215686 1.41421143831.425497619 1.414213562 1.414213562kkxxxx 三種方法數(shù)值結(jié)果方法方法方法 表7 從結(jié)果看出，經(jīng)過三步計算，方法2及3均達(dá)到10位有效數(shù)字，而由于牛頓法只有線性收斂，所以要達(dá)到同樣精度需迭代30次. 657.5 弦截法與拋物線法弦截法與拋物線法 當(dāng)函數(shù) 比較復(fù)雜時，計算 往往較困難，)( xf)(xf 值 的計算. )(kxf 為此可以利用已求函數(shù)值 來回避導(dǎo)數(shù)),(),(1kkxf

38、xf還要算 .)(kxf 用牛頓法求方程 的根，每步除計算 外，)(kxf0)(xf667.5.1 弦截法弦截法 設(shè) 是 的近似根，1,kkxx0)(xf利用 )(),(1kkxfxf構(gòu)造一次插值多項式 ，并用 的根作為新的近似根 . )(1xp0)(1xp1kx).()()()(111kkkkkkxxxxxfxfxfxp（5.1） 由于 因此有 ).()()()(111kkkkkkkxxxfxfxfxx（5.2）67（5.2可以看做將牛頓公式 )()(1kkkkxfxfxx中的導(dǎo)數(shù) 用差商 取代的結(jié)果.)(kxf 11)(kkkkxxxfxf 現(xiàn)在解釋這種迭代過程的幾何意義. 曲線 上橫坐標(biāo)

39、為 的點(diǎn)分別記為 ，)( xfy 1,kkxx1,kkPP則弦線 的斜率等于差商值 , 1kkPP11)(kkkkxxxfxf).()()()(111kkkkkkkxxxfxfxfxx（5.2）68 按5.2)式求得的 實(shí)際上是弦線 與 軸交點(diǎn)的橫坐標(biāo). 1kx1kkPPx 這種算法因此而稱為弦截法. ).()()(11kkkkkkxxxxxfxfxfy其方程為).()()()(111kkkkkkkxxxfxfxfxx（5.2）69 弦截法與切線法牛頓法都是線性化方法，但兩者有本質(zhì)的區(qū)別. 切線法在計算 時只用到前一步的值 .kx1kx 而弦截法5.2），在求 時要用到前面兩步的結(jié)果 ，1kx1,kkxx因此使用這種方法必須先給出兩個開始值 .01, xx).()()()(111kkkkkkkxxxfxfxfxx（5.2）70 例10 用弦截法解方程 .01e)(xxxf71000.510.620.5653230.5670940.56714kkx表計 算 結(jié) 果 解 設(shè)取 作為開始值，用弦截法求得的結(jié)果見表7-10，6 .0,5 .010 xx 比較例7牛頓法的計算結(jié)果可以看出，弦截法的收斂速度也是相當(dāng)快的. 71 實(shí)際上，弦截法具有超線性的收斂性. 這里 是方程 的正根. 618.1251p012 定理6