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

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

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

3、nnnn其中系數(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. 當當m=1時，則稱時，則稱x*為單為單根，若根，若m1稱稱x*為為(1.1)的的m重根重根，或，或x*為函數(shù)為函數(shù)f(x)的的m

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

5、值計算，而合數(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)的的有根區(qū)間有根區(qū)間.上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁 設設f(

6、x)在區(qū)間在區(qū)間a, b上連續(xù)上連續(xù), f(a)f(b)0, 則在則在a, b 內(nèi)有方程的根內(nèi)有方程的根. 取取a, b的中點的中點 將區(qū)間一分為二將區(qū)間一分為二. 若若 f (x0)=0, 則則x0就是方程的根就是方程的根, 否則判別根否則判別根 x*在在 x0 的的左側左側還是還是右側右側., )(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ū)間, 它它的的長度

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

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

9、 即即 f(a)與與f(b)的符號相同的符號相同, 因此因此不能用二分法求偶重根不能用二分法求偶重根.上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁 例例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 為所求之近似根為所求之近

10、似根., 6 . 512lg2 n上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁n an bn xn 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)點是算法簡單，且總是收斂的，是算法簡單，且總是收斂的，缺缺點點是收斂的太慢，故一般不單

11、獨將其用于求根，只是收斂的太慢，故一般不單獨將其用于求根，只是用其為根求得一個較好的近似值是用其為根求得一個較好的近似值.上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁逐步搜索法逐步搜索法 從區(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開開始，這時應取步長始，這時應取步長 h0.上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁7.2 不動點迭代法及其收斂性不動點迭代法及其收

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

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

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

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

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

17、同的根不同的根. 只有收斂的的迭代過程才有意義，為此我們首只有收斂的的迭代過程才有意義，為此我們首先要研究先要研究 (x)的不定點的存在性及迭代法的收斂性的不定點的存在性及迭代法的收斂性.上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁7.2.2 不動點的存在性與迭代法的收斂性不動點的存在性與迭代法的收斂性 首先考察首先考察 (x)在在a, b上不動點的存在唯一性上不動點的存在唯一性. 定理定理1 設設 (x)Ca, b滿足以下兩個條件：滿足以下兩個條件：1 對任意對任意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)的不動點的不動點. 再證不動點的再證不動點的唯一性唯一性. 設設x1*, x2*a, b都是都是 (x)的不動點，則由的不動點，則由(2.4)得得.)()(21212121 xxxxLxxxx 引出矛盾，故引出矛盾，故 (x)的不動點只能是唯一的的不動點只能是唯一的. .證畢證畢. . 在在 (x)的不動點存在唯一的情況下，可得到迭代的不動點存在唯一的情況下，可得到迭代法法(2.2)收斂的一個收斂的一個充分條件充分條件.上頁上頁上頁上頁上頁上頁下頁

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

20、上頁上頁上頁下頁下頁下頁下頁下頁下頁 定理定理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)具有局部收斂性具有局部收斂性. 再將再將 (xk)在根在根x*處做泰勒展開處做泰勒展開, 利用條件利用條件(2.8), 則有則有.,)(!)()()()(之間之間與與在在

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

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

23、 上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁假設假設 (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在計算了在計算了x1及及x2之后，可用

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

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

26、特金法若對此格式用埃特金法, 則則kxkex 1 得得(1)1(1)(2)11(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 xxxxxxxxx由此可見

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

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

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

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

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

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

33、kxxxxfxxxxxxfx 上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁由此得到，當由此得到，當x*為為單根單根時，牛頓迭代法在根時，牛頓迭代法在根x*的的鄰近是鄰近是二階二階(平方平方)收斂收斂的的.關于關于x*為為重根重根時，牛頓迭代法在根時，牛頓迭代法在根x*的鄰近的收的鄰近的收斂性在后面討論斂性在后面討論.定理定理(局部收斂性局部收斂性) 設設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上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁Newton法的收斂性依賴于法的收斂性依賴于x0 的選取。的選取。 局部收斂定理對初始值局部收斂定理對初始值 x0 要求較高。要求較高。x*x0 x0 x0 上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁 解解 將原方程化為將原方程化為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附近的根附近的根.上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁牛頓法應用舉例牛頓法應用舉例例例2 對于給定的正數(shù)對于給定的正數(shù)C，應用牛頓法解二次方程，應用牛頓法解二次方程, 02 Cx我們現(xiàn)在證明，這種迭代公式對于任意初值我們現(xiàn)在證明，這種迭代公式對于任意初值x00都是收斂的都是收斂的.可導出求開方值可導出求開方值 的計算程序的計算程序C.21)()()(,)(2 xCxxfxfxxCxxf 11.(3.3)2kkkCxxx 上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁事實上，對事實上，對(3.3)式施行配

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

37、因為迭代公式事實上，因為迭代公式)()()()()()()(*1kkkkkkkkkkxgxxxmgxgxxxxfxfxx 令令ek=xkx*，則，則)()()(*11kkkkkkkkxgexmgxgeexxe 上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁可見用牛頓法求方程的重根時僅為可見用牛頓法求方程的重根時僅為線性收斂線性收斂. 011)()()(1limlim1 mxgexmgxgeekkkkkkkk從而有從而有兩種兩種提高求重根的收斂速度提高求重根的收斂速度的的方法方法：1) ) 取如下迭代函數(shù)取如下迭代函數(shù). 0)(,)()()( xxfxfmxx 則則1()(0,1,).(3.6

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

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

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

41、保證收斂，如x0給給的不合適可能不收斂的不合適可能不收斂. 為克服這兩個缺點，通?？捎脼榭朔@兩個缺點，通?？捎孟率龇椒ㄏ率龇椒? 簡化牛頓法簡化牛頓法，也稱，也稱平行弦法平行弦法，其迭代公式為，其迭代公式為1()0,0,1,.(3.5)kkkxxCf xCk 迭代函數(shù)為迭代函數(shù)為 (x)=x- -Cf(x). 上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁若若| (xk)|=|1- -Cf (x)|1，即取，即取0Cf (x)2. 在根在根x*附近成立，則迭代法附近成立，則迭代法(3.5)局部收斂局部收斂.在在(3.5)中取中取C=1/f (x0)，則稱為簡化牛頓法，這類，則稱為簡化牛頓法

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

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

44、kxxxxf xf xf x 上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁這樣導出的迭代公式這樣導出的迭代公式(5.2)可以看做牛頓公式可以看做牛頓公式.)()(1kkkkxfxfxx 11)()( kkkkxxxfxf中的導數(shù)中的導數(shù) 用用差商差商 取代的結果取代的結果.)(kxf (5.2)式有明顯的式有明顯的幾何意義幾何意義： 設曲線設曲線y=f(x)上橫坐標為上橫坐標為xk- -1和和xk的點分別為的點分別為Pk-1和和Pk, 則差商則差商 表示弦表示弦 的斜率的斜率, 弦弦 的方程為的方程為11)()( kkkkxxxfxfkkPP1 kkPP1 11()()()()kkkkkk

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

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

47、到前兩點式用到前兩點xk- -1和和xk的值，故此方法的值，故此方法又稱為又稱為雙點割線法雙點割線法.010().()()kkkkkxxxxf xf xf x 每步只用一個新點每步只用一個新點xk的值，此方法稱為的值，此方法稱為單點割線法單點割線法.如果把如果把(5.2)式中的式中的xk- -1改為改為x0，即迭代公式為，即迭代公式為上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁例題例題 用牛頓迭代法和割線法求方程用牛頓迭代法和割線法求方程 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，用，用雙點割線法雙點割線法，迭代，迭代6次得到同樣的次得到同樣的結果，而采用結果，而采用單點割線法單點割線法，則迭代，則迭代18次得次得 x18=1.124123029.上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁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)牛頓法牛頓法簡化牛頓法簡化牛頓法割線法割線法拋物線法拋物線法上頁上頁上頁上頁上頁上頁下頁下頁下頁

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

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

51、(5.3)式定出一個值式定出一個值xk+1，我們需要討論根，我們需要討論根式前正負號的取舍問題式前正負號的取舍問題.在在xk, xk- -1, xk- -2三個近似值中，自然假定三個近似值中，自然假定xk更接近更接近所求的根所求的根x*，這時，為了保證精度，我們選，這時，為了保證精度，我們選(5.3)式中式中接近接近xk的一個值作為新的近似根的一個值作為新的近似根xk+1. 為此，為此，只要取根只要取根式前的符號與式前的符號與的符號相同的符號相同.12122 ().4 () ),sgn(kkkkkkkkkkf xxxf xf xxx 上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁 例例 用拋物線法求解方程用拋物線法求解方程f(x)=xex- -1=0. 解解 取取x0=0.5, x1=0.6, x2=0.56532開始，計算得開始，計算得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