第3章_非線性方程求根

1、1求方程f(x)=0的根是最常見的數(shù)學(xué)問題之一，當(dāng)f(x) 是一次多項式時，稱f(x)=0為線性方程，否則稱之為非線性方程.第第3 3章章 非線性方程求根非線性方程求根非線性方程的分兩類：. 01 : )., 1 , 0(R, 0, 0 , . 1301110 xxniaaaxaxaxainnnn如其中代數(shù)方程. 0 : , . 2xex如超越方程 ( )0 , ( ) , .f xxR f xC a b考慮單變量非線性方程的求根問題，其中2結(jié)束結(jié)束 當(dāng)當(dāng)f(x)=0=0是非線性方程時，是非線性方程時，對于不高于對于不高于4次的代次的代數(shù)方程已有求根公式，而高于數(shù)方程已有求根公式，而高于4次的

2、代數(shù)方程則無次的代數(shù)方程則無精確的求根公式，至于超越方程精確的求根公式，至于超越方程 就更無法求出其精就更無法求出其精確的解，確的解，但如果對任意的精度要求，能求出方程的但如果對任意的精度要求，能求出方程的近似根，則可以認(rèn)為求根的計算問題已經(jīng)解決，至近似根，則可以認(rèn)為求根的計算問題已經(jīng)解決，至少能滿足實際要求少能滿足實際要求. .因此，如何求得滿足一定精度因此，如何求得滿足一定精度要求的方程的近似根也就成為迫切需要解決的問題要求的方程的近似根也就成為迫切需要解決的問題，本章介紹幾種常見的非線性方程的近似求根方法本章介紹幾種常見的非線性方程的近似求根方法.3.1.1 引言本章主要討論本章主要討論

3、單變量非線性方程單變量非線性方程f(x)=0 (1.1)的求根問題，這里的求根問題，這里xR, 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)

4、m=1時，則稱時，則稱x*為單為單根，若根，若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( xfxfxfxfmmn=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) - 0+ - 0-+ 隔根區(qū)間(0,3)(3,4)9 設(shè)設(shè)f(x)

7、在在 a,b 上連續(xù)，若上連續(xù)，若f(a) f(b) 00, 0, f(b) 00或或 f(a) 0, 0.0.則根據(jù)則根據(jù)連續(xù)函數(shù)連續(xù)函數(shù)的介值定理的介值定理，在，在( (a,b) )內(nèi)至少存在一點內(nèi)至少存在一點 ，使，使f( ) =0.=0.3.2 二分法二分法 二分法是最簡單、最直觀的方法。二分法是最簡單、最直觀的方法。適用于求有限適用于求有限區(qū)間內(nèi)的單實根或奇重實根區(qū)間內(nèi)的單實根或奇重實根. 二分法的基本原理：二分法的基本原理： 二分法的具體方法如下：二分法的具體方法如下： 設(shè)設(shè)f(x)在區(qū)間在區(qū)間a, b上連續(xù)上連續(xù), f(a)f(b)0, 則在則在a, b 內(nèi)有方程的根內(nèi)有方程的根

8、. 取取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á)到了壓縮有根壓縮有根區(qū)間區(qū)間的目的的目的

9、. 對壓縮了的有根區(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ū)間必將最終收縮為一點點x* ，顯然，顯然x*就是所求的就是所求的根根. 若取區(qū)間若取區(qū)間an , bn的中點

10、的中點)(nnnbax 21作為作為x*的近似值，則有下述的近似值，則有下述誤差估計式誤差估計式11111 11*()()()22 22nnnnnnxxbabab a 只要只要 n 足夠大足夠大, (即區(qū)間二分次數(shù)足夠多即區(qū)間二分次數(shù)足夠多)，誤差就可，誤差就可足夠小足夠小.),(,*11 nnnbaxx 由于在偶重根附近曲線由于在偶重根附近曲線 y=f(x) 為上凹或下凸為上凹或下凸, 即即 f(a)與與f(b)的符號相同的符號相同, 因此因此不能用二分法求偶重根不能用二分法求偶重根. 例例2 用二分法求例用二分法求例1中方程中方程 f(x)=x3- -x- -1=0的實根的實根,要求誤差不

11、超過要求誤差不超過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 nn an bn xn f(xn)說明01234561.01251.31251.31251.320751.3751.34381.32811.32811.251.3751.31251.3

12、4381.32811.32031.3242-+-+-(1) f(a)0(2) 根據(jù)精 度要求，取到小數(shù)點后四位 即可.二分法的計算步驟二分法的計算步驟:步驟步驟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é)束，否則檢驗計算過

13、程結(jié)束，否則檢驗. 反復(fù)執(zhí)行步驟反復(fù)執(zhí)行步驟2和步驟和步驟3，直到區(qū)間，直到區(qū)間a, b長度小于長度小于允許誤差允許誤差，此時中點，此時中點(a+b)/2即為所求近似根即為所求近似根.16二分法求根的算法二分法求根的算法:%input:區(qū)間端點區(qū)間端點a,b(f(a)f(b)0);最大二分次數(shù)最大二分次數(shù)N；精度；精度tol.%output:近似根近似根x，二分次數(shù)，二分次數(shù)k.1. k=0;fa=f(a) ;%函數(shù)函數(shù)f需要事先定義需要事先定義2. For k=1:N 2.1 x= (a+b)/2 ; fx=f(x); 2.2 if fx=0|(b-a)/2tol break end 2.3

14、 if fa*fx0 b=x; else a=x; end 3. disp(x); disp(k) 17 可見，二分法的優(yōu)點是對函數(shù)的要求低可見，二分法的優(yōu)點是對函數(shù)的要求低(只要求只要求f(x)連續(xù)連續(xù))，方法簡便、可靠，程序設(shè)計容易，事先估計計算次數(shù)容易，方法簡便、可靠，程序設(shè)計容易，事先估計計算次數(shù)容易，收斂速度恒定；收斂速度恒定；缺點是不能求出偶重根，收斂速度較慢缺點是不能求出偶重根，收斂速度較慢. 取適當(dāng)?shù)牟介L取適當(dāng)?shù)牟介Lh =(b-a)/m逐一檢驗小區(qū)間逐一檢驗小區(qū)間 a+kh,a+(k+1)h,(k=0,1,2,m-1) 的兩端函數(shù)值是否異號，的兩端函數(shù)值是否異號，若異號，則按以

15、上二分法求出其中的根；若同號則不作求根若異號，則按以上二分法求出其中的根；若同號則不作求根而轉(zhuǎn)入檢查下一個區(qū)間，只要而轉(zhuǎn)入檢查下一個區(qū)間，只要h選得較小，則可求出本區(qū)間選得較小，則可求出本區(qū)間內(nèi)的所有奇重實根內(nèi)的所有奇重實根(包括單實根包括單實根).h選得過大，可能漏掉某些根選得過大，可能漏掉某些根； h選得過小，則計算量增大選得過小，則計算量增大. 二分法的思想方法還可用于搜索一個較大區(qū)間二分法的思想方法還可用于搜索一個較大區(qū)間a,b內(nèi)實根內(nèi)實根的分布情況的分布情況(不包括偶重實根不包括偶重實根)，實際的作法是：，實際的作法是：3.3 迭代法及其收斂性3.3.1 不動點迭代法不動點迭代法 將

16、方程將方程f(x)=0改寫為等價方程形式改寫為等價方程形式 x= (x). (3.1)若要求若要求x*滿足滿足f(x*)=0，則，則x*= (x*)；反之亦然，稱；反之亦然，稱x*為為函數(shù)函數(shù) (x)的一個的一個不動點不動點. 求求f(x)的零點就等于求的零點就等于求 (x)的的不動點不動點，選擇一個初始近似值，選擇一個初始近似值x0，將它代入，將它代入(3.1)右端右端，即可求得，即可求得 x1= (x0). .lim xxkk可以如此反復(fù)迭代計算可以如此反復(fù)迭代計算 xk+1= (xk) (k=0,1,2,). (3.2) (x)稱為迭代函數(shù)稱為迭代函數(shù). 如果對任何如果對任何x0a, b

17、，由，由(3.2)得得到的序列到的序列xk有極限有極限則稱迭代方程則稱迭代方程(3.2)收斂收斂. 且且x*= (x*)為為 (x)的的不動點不動點，故稱故稱(3.2)為為不動點迭代法不動點迭代法. 上述迭代法是一種逐次逼近法，其基本思想是將上述迭代法是一種逐次逼近法，其基本思想是將隱式方程隱式方程(3.1)歸結(jié)為一組顯式的計算公式歸結(jié)為一組顯式的計算公式(3.2)，迭代，迭代過程實質(zhì)上是一個逐步顯式化過程過程實質(zhì)上是一個逐步顯式化過程.當(dāng)當(dāng) (x)連續(xù)時，連續(xù)時，顯然顯然x*就是方程就是方程x= (x)之之根根(不動點不動點). 于是可以從數(shù)列于是可以從數(shù)列xk中求得滿足精度要求的近似根中求

18、得滿足精度要求的近似根. 這種求根方法這種求根方法稱為稱為不動點迭代法不動點迭代法, 1()(0,1,2,)kkxxk 稱為稱為迭代格式迭代格式, (x)稱為稱為迭代函數(shù)迭代函數(shù), x0 稱為稱為迭代初值迭代初值,數(shù)列數(shù)列xk稱為稱為迭代序列迭代序列. 如果迭代序列收斂如果迭代序列收斂, 則稱迭則稱迭代格式代格式收斂收斂,否則稱為否則稱為發(fā)散發(fā)散. 1()(0,1,2,)kkxxk .lim xxkk 03224xxx分別按以上三種形式建立迭代公式，并取分別按以上三種形式建立迭代公式，并取x0=1進(jìn)行進(jìn)行迭代計算，結(jié)果如下：迭代計算，結(jié)果如下：14)(2 xxx 32)(243 xxxx 41

19、21)23()(xxxx 解解 對方程進(jìn)行如下三種變形：對方程進(jìn)行如下三種變形： 例例3 用迭代法求方程用迭代法求方程x4+2x2- -x- -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.1241

20、23xx 另參見書另參見書p44頁頁- -例例3- 3.3.2 迭代法的幾何解釋迭代法的幾何解釋以上可以看到迭代法可能收斂，也可能不收斂以上可以看到迭代法可能收斂，也可能不收斂. .一般說從一般說從f( (x)=0)=0構(gòu)造出的構(gòu)造出的x= (x)不止一種，有的收斂，有的不收斂不止一種，有的收斂，有的不收斂，這取決于，這取決于g(x)的性態(tài)的性態(tài). .將將x= (x)寫為寫為它的解它的解( (x* *, ,y * *) )中的中的x * *就是就是x= (x)的根的根. .如圖：如圖：圖圖3-3-2 2 圖圖3-3-3 3 圖圖3-3-4 4 圖圖3-53-5(3.3)( )

21、yxyxxyy = xxyy = xxyy = xxyy = xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)x0p0 x1p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p1圖圖3-3-2 2圖圖3-3-3 3 圖圖3-3-4 4 圖圖3-53-5 例例3表明原方程化為表明原方程化為(3.1)的形式不同，有的收斂的形式不同，有的收斂，有的發(fā)散，在收斂的方法中，收斂的快慢也不相，有的發(fā)散，在收斂的方法中，收斂的快慢也不相同。只有收斂的的迭代過程同。只有收斂的的迭代過程(3.2)才有意義，為此我才有意義，為此我們首先要研究們首先要研究 (x)的不定點的存在性及迭代法的

22、不定點的存在性及迭代法(3.2)的的收斂性收斂性. 首先考察首先考察 (x)在在a, b上不動點的存在唯一性上不動點的存在唯一性. 定理定理1 設(shè)設(shè) (x)Ca, b滿足以下兩個條件：滿足以下兩個條件：1 對任意對任意xa, b有有a (x)b. .( )( ).(3.4)xyL xy2 存在正數(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)的不動

23、點，則由的不動點，則由(3.4)得得.)()(21212121 xxxxLxxxx 引出矛盾，故引出矛盾，故 (x)的不動點只能是唯一的的不動點只能是唯一的. .證畢證畢. . 對定理對定理1條件條件2可以改為導(dǎo)數(shù)，即在使用時如果可以改為導(dǎo)數(shù)，即在使用時如果 (x)Ca, b且對任意且對任意xa, b有有( )1.(3.5)xL則由微分中值定理可知對任意則由微分中值定理可知對任意x, ya, b有有).,(, )()()()(bayxLyxyx 故定理中的條件故定理中的條件2是成立的是成立的. 見書見書p45. 在在 (x)的不動點存在唯一的情況下，可得到迭代的不動點存在唯一的情況下，可得到迭

24、代法法(3.2)收斂的一個收斂的一個充分條件充分條件.29定理定理3.23.2 設(shè)迭代函數(shù)設(shè)迭代函數(shù) (x) Ca,b，且滿足，且滿足 (1) 對任意對任意x a,b，有，有a (x) b(b(映內(nèi)性映內(nèi)性) )； (2) (2) (x)在在( (a,b) )可導(dǎo)，并存在常數(shù)可導(dǎo)，并存在常數(shù)0L10L1，使得，使得對任意對任意x a,b，有，有 | (x)| | L1 ( L1 (壓縮性壓縮性) )則則 (x)在在a,b內(nèi)存在唯一不動點。內(nèi)存在唯一不動點。例例 判別判別 (x)=3=3-x 在在0, 1區(qū)間是否存在唯一不動點。區(qū)間是否存在唯一不動點。這是充分條件，不是必要條件。這是充分條件，不

25、是必要條件。（滿足條件（滿足條件1 1，不滿足條件，不滿足條件2 2，但該問題在，但該問題在00，11有有唯一不動點）唯一不動點）ln(3) = 1.0986122886681 ln(3) = 1.0986122886681 定理定理3.33.3 已知方程已知方程x= (x) ， (x)在在a,b連續(xù)，在連續(xù)，在(a,b)內(nèi)可內(nèi)可導(dǎo)；導(dǎo)；且滿足：且滿足：(1)(1)對任意的對任意的x a,b,有有 (x) a,b.(2)(2)對任意的對任意的x a,b,有有| | (x)| | L11，則對任意的，則對任意的x0 a,b ，迭代，迭代xk+1= (xk)生成的序列生成的序列 xk 必收斂于必收

26、斂于x= (x)的的根根x*，且，且*10|(3.6)1kkLxxxxL30*1|(3.7)1kkkLxxxxL或或稱為全局收斂稱為全局收斂。 證明證明 設(shè)設(shè)x*a, b是是 (x)在在a, b上的唯一不動點上的唯一不動點, ,由條件由條件1，可知，可知xka, b，再由，再由(3.4)得得.)()(011xxLxxLxxxxkkkk 因因0L1，故當(dāng)，故當(dāng)k時序列時序列xk收斂到收斂到x*.下面證明估計式下面證明估計式(3.6)，由，由(3.4)有有111)()( kkkkkkxxLxxxx .01212xxLxxLkkk 于是對任意正整數(shù)于是對任意正整數(shù)p有有.11)1()(0101012

27、11211xxLLxxLLLxxLLLxxxxxxxxkpkkpkpkkkpkpkpkpkkpk 上述令上述令p, 注意到注意到limxk+p=x* (p)即得即得(3.6)式式. 又由于對任意正整數(shù)又由于對任意正整數(shù)p有有.1111)(111211211kkkkpkkppkkpkpkpkpkkpkxxLxxLLxxLLLxxxxxxxx 上述令上述令p, 及及l(fā)imxk+p=x* (p)即得即得(3.7)式式. 證畢證畢. 迭代過程是個極限過程迭代過程是個極限過程. 在用迭代法進(jìn)行時，必在用迭代法進(jìn)行時，必須按精度要求控制迭代次數(shù)須按精度要求控制迭代次數(shù). 誤差估計式誤差估計式(3.6)原則

28、上原則上確定迭代次數(shù)，但它由于含有信息確定迭代次數(shù)，但它由于含有信息L而不便于實際應(yīng)而不便于實際應(yīng)用用. 而誤差估計式而誤差估計式(3.7)是實用的，只要是實用的，只要相鄰兩次計算相鄰兩次計算結(jié)果的偏差結(jié)果的偏差足夠小即可保證近似值足夠小即可保證近似值xk具有足夠精度具有足夠精度.34注注1 1：(3.6)式可用來估計迭代次數(shù)，但結(jié)果偏保守，次數(shù)偏式可用來估計迭代次數(shù)，但結(jié)果偏保守，次數(shù)偏大，一般用得不多。稱為事前誤差估計。大，一般用得不多。稱為事前誤差估計。注注2：(3.7)式可用在程序中置退出迭代的條件，式可用在程序中置退出迭代的條件，即當(dāng)即當(dāng)|xk-xk-1| 時，認(rèn)為時，認(rèn)為|x*-x

29、k-1|1時稱時稱超線性收斂超線性收斂，p=2時稱時稱平方收斂平方收斂. 3.5 迭代法的收斂階迭代法的收斂階 定理定理3-6 對于迭代過程對于迭代過程xk+1= (xk)，如果，如果 ( (p) )(x)在在所求根所求根x*的鄰近連續(xù)，并且的鄰近連續(xù)，并且(1)( )()()()0,()0. (3.8)ppxxxx則該迭代過程在則該迭代過程在x*的鄰近是的鄰近是p階收斂的階收斂的. 證明證明 由于由于(x*)=0，根據(jù)定理，根據(jù)定理3立即可以斷定迭立即可以斷定迭代過程代過程xk+1= (xk)具有局部收斂性具有局部收斂性. 再將再將 (xk)在根在根x*處做泰勒展開處做泰勒展開, 利用條件利

30、用條件(3.8), 則有則有.,)(!)()()()(之間之間與與在在 xxxxpxxkpkpk 注意到注意到 (xk)=xk+1， (x*)= x*，由上式得，由上式得,)(!)()(1pkpkxxpxx 因此對迭代誤差，令因此對迭代誤差，令k時有時有這表明迭代過程這表明迭代過程xk+1= (xk)確實為確實為p階收斂階收斂. 證畢證畢. .!)()(1pxeeppkk 上述定理告訴我們，迭代過程的收斂速度依賴于上述定理告訴我們，迭代過程的收斂速度依賴于迭代函數(shù)迭代函數(shù) (x)的選取的選取. 如果如果xa, b但但 (x)0時，則時，則該迭代過程只可能是線性收斂該迭代過程只可能是線性收斂.)

31、0( aa的三階方法的三階方法. 假設(shè)假設(shè) x0 充分靠近充分靠近 x*, 求求31)(limkkkxaxa 證明證明 首先由泰勒展式可得首先由泰勒展式可得113311limlim()()3!4()kkkkkkaxeaeaax 例子例子 證明迭代公式證明迭代公式 xk+1=xk(xk2+3a)/(3xk2+a)是求是求而而1/4a00，故此故此迭代公式是三階方法迭代公式是三階方法.3.4 牛 頓 法3.4.1 牛頓法及其收斂性)()()(000 xxxfxfxf 對于方程對于方程f(x)=0，如果，如果f(x)是線性函數(shù)，則它的是線性函數(shù)，則它的求根是容易的求根是容易的. 牛頓法實質(zhì)上是一種線

32、性化方法，其牛頓法實質(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- -x0)=0. (3.4.1)解此線性方程得解此線性方程得)()(000 xfxfxx 得迭代公式得迭代公式此式稱為此式稱為牛頓牛頓(Newton)迭代

33、公式迭代公式.1()(0,1,),(3.4.2)()kkkkf xxxkfx牛頓法有顯然的牛頓法有顯然的幾何意義幾何意義，方程，方程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)軸交點的橫坐標(biāo)xk+1作為作為x*的新的的新的近似值近似值. 注意到切線方程為注意到切線方程為這樣求得的值這樣求得的值xk+1必滿足必滿足(3.4.1), 從而就是牛頓公式從而就是牛頓公式(3.4.2)的計

34、算結(jié)果的計算結(jié)果. 由于這由于這種幾何背景，所以牛頓迭種幾何背景，所以牛頓迭代法也稱代法也稱切線法切線法.xyx*xky=f(x)xk+1PkPk+1xk+2).)()(kkkxxxfxfy .0 的根用牛頓法求方程xex例7例710 , 0,1,2, 1 0.5,kxkkkkNewtonxexxkxx迭代公式為:取初值計算結(jié)果如表kxk01230.50.571020.567160.567142 , 0115.CNewtonxCC對于給定正數(shù)應(yīng)用迭代法于方程，導(dǎo)出求的迭代公式，并計算的近似值例例8 800.x可以證明，迭代公式皆平方收斂21 1 22kkkkkkxCCxxxxx0115, 10

35、Cx取初值，計算結(jié)果如表kxk012341010.75000010.72383710.72380510.723805( ),xf xxe解：( )1xfxe 2( ),( )2f xxC fxx解：牛頓迭代法的收斂性牛頓迭代法的收斂性)()()(xfxfxx 設(shè)設(shè)x*是是f(x)的一個單根，即的一個單根，即f(x*)=0，f (x*)0, 有有. 0)()()(, 0)()()()(2* xfxfxxfxfxfx 牛頓迭代法的迭代函數(shù)為牛頓迭代法的迭代函數(shù)為由定理由定理3-6可得式可得式. 0)(2)()(! 21)()(lim)(lim22!2121 xfxfxxxxxxxxxkkkkkk

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

37、 xfxfxxxxkkk牛頓法的牛頓法的優(yōu)點優(yōu)點是收斂快，是收斂快，缺點缺點每步迭代要計算每步迭代要計算f(xk)及及f (xk)，計算量較大，且有時，計算量較大，且有時f (xk)計算較困難；計算較困難；導(dǎo)數(shù)不存在不能用。導(dǎo)數(shù)不存在不能用。初始近似值初始近似值x0只在根只在根x*附近才附近才能保證收斂，如能保證收斂，如x0給的不合適可能不收斂給的不合適可能不收斂. 為克服這為克服這兩個缺點，通常可用下述方法兩個缺點，通?？捎孟率龇椒?1 牛頓下山法牛頓下山法, 牛頓法收斂性依賴初值牛頓法收斂性依賴初值x0的選取的選取, 如果如果x0偏離所求根偏離所求根x*較遠(yuǎn)較遠(yuǎn), 則牛頓法可能發(fā)散則牛頓法

38、可能發(fā)散.Newtons Method收斂性依賴于收斂性依賴于x0的選取的選取.x*x0 x0 x03.4.2牛頓迭代法的變形牛頓迭代法的變形例如例如，用牛頓法求解方程，用牛頓法求解方程 x3- -x- -1=0. (3.4.4)此方程在此方程在x=1.5附近的一個根附近的一個根x*. 設(shè)取迭代初值設(shè)取迭代初值x0=1.5，用牛頓迭代法公式，用牛頓迭代法公式 3121.(3.4.5)31kkkkkxxxxx計算得計算得 x1=1.34783, x2=1.32520, x3=1.32472.迭代迭代3次得到的結(jié)果次得到的結(jié)果x3有有6位有效數(shù)字位有效數(shù)字.但是，如取但是，如取x0=0.6，用，用

39、(3.4.5)式迭代式迭代1次得次得 計算得計算得 x1=17.9.這個結(jié)果反而比這個結(jié)果反而比x0=0.6更偏離了所求的根更偏離了所求的根x*=1.32472. 為了防止迭代發(fā)散，我們對迭代過程再附加一項為了防止迭代發(fā)散，我們對迭代過程再附加一項要求，即具有單調(diào)性要求，即具有單調(diào)性.1()() .(3.4.6)kkf xf x滿足這項要求的算法稱為滿足這項要求的算法稱為下山法下山法.我們將牛頓法與下山法結(jié)合起來使用，即在下山我們將牛頓法與下山法結(jié)合起來使用，即在下山法保證函數(shù)值穩(wěn)定下降的前提下，用牛頓法加快收斂法保證函數(shù)值穩(wěn)定下降的前提下，用牛頓法加快收斂速度速度. 為此，我們將牛頓法的結(jié)果

40、為此，我們將牛頓法的結(jié)果)()(1kkkkxfxfxx 與前一項的近似值與前一項的近似值xk適當(dāng)加權(quán)平均作為新的改進(jìn)值適當(dāng)加權(quán)平均作為新的改進(jìn)值11(1),(3.4.7)kkkxxx其中其中(00)重根重根時，則時，則f(x)可表為可表為 f(x)=(x- -x*)mg(x).其中其中g(shù)(x*)0，此時用牛頓迭代法，此時用牛頓迭代法(3.4.2)求求x*仍然收斂仍然收斂，只是，只是收斂速度將大大減慢收斂速度將大大減慢. 事實上，因為迭代公式事實上，因為迭代公式)()()()()()()(*1kkkkkkkkkkxgxxxmgxgxxxxfxfxx 令令ek=xkx*，則，則)()()(*11k

41、kkkkkkkxgexmgxgeexxe 可見用牛頓法求方程的重根時僅為可見用牛頓法求方程的重根時僅為線性收斂線性收斂. 011)()()(1limlim1 mxgexmgxgeekkkkkkkk從而有從而有兩種兩種提高求重根的收斂速度提高求重根的收斂速度的的方法方法：1) ) 取如下迭代函數(shù)取如下迭代函數(shù). 0)(,)()()( xxfxfmxx 則則1( )(0,1,).(3.4.10)( )kkkkf xxxmkf x得到迭代公式得到迭代公式.m Newtonm稱為帶參數(shù) 的迭代法它具有平方收斂，但重數(shù) 一般是未知的.下面介紹一個下面介紹一個求重數(shù)求重數(shù)m的方法的方法，令，令211 kk

42、kkkxxxx 則則112121111kkkkkkkkkkkeeeeeeeeee 求求m重根具有重根具有2階收斂階收斂. 但要知道但要知道x*的的重數(shù)重數(shù)m.由式由式11lim1kkkeem .111limmmmkk 得得因此得估計因此得估計m的式子為的式子為.11km 對對f(x)=(x- -x*)mg(x), g(x*)0，令函數(shù)，令函數(shù).)()()()()()()()(xgxxxmgxgxxxfxfx 則為求則為求(x)=0的單根的單根x*的問題，對它用牛頓法是二階的問題，對它用牛頓法是二階(平方平方)收斂的收斂的. 其迭代函數(shù)為其迭代函數(shù)為2) ) 將求重根問題化為求單根問題將求重根問

43、題化為求單根問題. .)()()()()()()()(2xfxfxfxfxfxxxxx 12()()(0,1,). (3.4.11)()()()kkkkkkkf xf xxxkf xf xfx從而構(gòu)造出迭代方法為從而構(gòu)造出迭代方法為()().kkfxfx該迭代格式仍具有平方收斂，但需要計算和4210 440*2.xxx用上述三種方法求的二重根例例 212 4kkkkxxxx：牛頓法；解解212 (3.4.10) 2kkkkxxxx；212(2) (3.4.11) .2kkkkkxxxxx計算結(jié)果如下： kxk(1)(2)(3)0123x0 x1x2x31.51.4583333331.43660

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

45、式校正一次得 x1= (x0)而由微分中值定理，有而由微分中值定理，有.),)()()(0001之間之間與與在在xxxxxxxx 假設(shè)假設(shè) (x)改變不大改變不大, 近似地取某個近似值近似地取某個近似值L, 則有則有由于由于 x2- -x*L(x1- -x*).10().(3.5.1)xxL xx 若將校正值若將校正值x1= (x0)再校正一次，又得再校正一次，又得 x2= (x1)將它與將它與(3.5.1)式聯(lián)立，消去未知的式聯(lián)立，消去未知的L，有，有 xxxxxxxx1021由此推知由此推知.2)(201220100122120 xxxxxxxxxxxxx . 0lim1 xxxxkkk在計算了在計算了x1及及x2之后，可用上式右端作為之后，可用上式右端作為x*的新近似的新近似,記作記作x 1，一般情形是由，一般情形是由xk計算計算xk+1, xk+2，記，記它表明序列它表明序列xk的收斂速度比的收斂速度比xk的收斂速度快的收斂速度快.2112122()2()(0,1,).(3.5.2)kkkkkkkkkkxxxxxxxxxkx(3.5.1)式稱為式稱為埃特金埃特金(Aitken) 2加速方法加速方法. 可以證明可以證明也稱為也稱為埃特金埃特金 ( Aitken ) 外推法外推法. 可以證明可以證明:)(1kkxx 為線性收