數(shù)值分析31二分法、迭代法及收斂性

1、第第3章章 非線性方程的數(shù)值解法非線性方程的數(shù)值解法 3.1 方程求根與二分法方程求根與二分法 3.2 迭代法及其收斂性迭代法及其收斂性 3.3 迭代收斂的加速方法迭代收斂的加速方法 3.4 牛頓法牛頓法 3.5 弦截法與拋物線法弦截法與拋物線法3.1.1 3.1.1 引言引言本章主要討論本章主要討論單變量非線性方程單變量非線性方程f(x)=0 (1.1)的求根問(wèn)題，這里的求根問(wèn)題，這里xR, f(x)Ca, b. 在科學(xué)與工程在科學(xué)與工程計(jì)算中有大量方程求根問(wèn)題，其中一類特殊的問(wèn)題計(jì)算中有大量方程求根問(wèn)題，其中一類特殊的問(wèn)題是多項(xiàng)式方程是多項(xiàng)式方程)2 . 1(),0()(01110 aax

2、axaxaxfnnnn其中系數(shù)其中系數(shù)ai(i=0,1,n)為實(shí)數(shù)為實(shí)數(shù).3.1 方程求根與二分法方程求根與二分法n=1,2時(shí)方程的根是大家熟悉的，時(shí)方程的根是大家熟悉的，n=3,4時(shí)雖有求時(shí)雖有求根公式但比較復(fù)雜，可在數(shù)學(xué)手冊(cè)中查到，但已不適根公式但比較復(fù)雜，可在數(shù)學(xué)手冊(cè)中查到，但已不適合數(shù)值計(jì)算，而合數(shù)值計(jì)算，而n5時(shí)就不能用公式表示方程的根時(shí)就不能用公式表示方程的根.因因此，通常對(duì)此，通常對(duì)n3的多項(xiàng)式方程求根與一般連續(xù)函數(shù)方的多項(xiàng)式方程求根與一般連續(xù)函數(shù)方程程(1.1)一樣都可采用迭代法求根一樣都可采用迭代法求根.方程方程f(x)=0的的根根 x*，又稱為函數(shù)又稱為函數(shù)f(x)的的零點(diǎn)

3、零點(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í)，則稱時(shí)，則稱x*為為單單根根，若，若m1稱稱x*為為(1.1)的的m重根重根，或，或x*為函數(shù)為函數(shù)f(x)的的m重零點(diǎn)重零點(diǎn). 若若x*是是f(x)的的m重零點(diǎn)重零點(diǎn)，則，則. 0)(, 0)()()()()1( xfxfxfxfmm注：注：3.1.2 3.1.2 二分法二分法如果如果 f(x) 在區(qū)間在區(qū)間a, b上連續(xù)上連續(xù), f(a)f(b)0, 則在則在a, b 內(nèi)有方程的根內(nèi)有方程的根. （ Bisection Me

4、thod ）二分法原理二分法原理二分法的實(shí)施過(guò)程二分法的實(shí)施過(guò)程取取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)度只有原有根區(qū)間長(zhǎng)度的一半長(zhǎng)度只有原有根區(qū)間長(zhǎng)

5、度的一半, 達(dá)到了達(dá)到了壓縮有根壓縮有根區(qū)間的目的區(qū)間的目的.如此反復(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)都不是根，則上述過(guò)程將無(wú)限進(jìn)行下去無(wú)限進(jìn)行下去. 當(dāng)當(dāng) n 時(shí)，區(qū)間必將最終收縮為一時(shí)，區(qū)間必將最終收縮為一點(diǎn)點(diǎn)x* ，顯然，顯然 x* 就是所求的就是所求的根根. 若取區(qū)間若取區(qū)間an , bn的中點(diǎn)的中點(diǎn))(nnnbax 21作為作

6、為x*的近似值，則有下述的近似值，則有下述111*()()22nnnnxxbaba 只要只要 n 足夠大足夠大, (即區(qū)間二分次數(shù)足夠多即區(qū)間二分次數(shù)足夠多)，誤差就可，誤差就可足夠小足夠小.),(,*11 nnnbaxx二分法的誤差估計(jì)二分法的誤差估計(jì)例例1 用二分法求方程用二分法求方程 f(x)=x3- -x- -1=0在在(1, 1.5)的實(shí)根的實(shí)根,要求誤差不超過(guò)要求誤差不超過(guò)0.005. 解解 由題設(shè)條件，即：由題設(shè)條件，即：則要?jiǎng)t要005. 021)15 . 1(21)(21211 nnnab|x*- -xn|0.005由此解得由此解得 取取 n=6, 按二分法計(jì)算過(guò)程見(jiàn)按二分法計(jì)

7、算過(guò)程見(jiàn)下表下表, x6 = 1.3242 為所求之近似根為所求之近似根., 6 . 512lg2 nn 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)是收

8、斂的太慢，故一般不單獨(dú)將其用于求根，只是收斂的太慢，故一般不單獨(dú)將其用于求根，只是用其為根求得一個(gè)較好的近似值是用其為根求得一個(gè)較好的近似值.二分法的計(jì)算步驟二分法的計(jì)算步驟: :步驟步驟1 準(zhǔn)備準(zhǔn)備 計(jì)算函數(shù)計(jì)算函數(shù)f(x)在區(qū)間在區(qū)間a, b端點(diǎn)處的值端點(diǎn)處的值f(a), f(b). 若若f(a)f(a+b)/2)0, 則以則以(a+b)/2代替代替b ，否則以，否則以(a+b)/2代替代替a.步驟步驟2 二分二分 計(jì)算函數(shù)計(jì)算函數(shù)f(x)在區(qū)間中點(diǎn)在區(qū)間中點(diǎn)(a+b)/2處的處的值值f(a+b)/2).步驟步驟3 判斷判斷 若若f(a+b)/2)=0，則，則(a+b)/2即是根，即是根，

9、計(jì)算過(guò)程結(jié)束，否則檢驗(yàn)計(jì)算過(guò)程結(jié)束，否則檢驗(yàn). 反復(fù)執(zhí)行步驟反復(fù)執(zhí)行步驟2和步驟和步驟3，直到區(qū)間，直到區(qū)間a, b長(zhǎng)度小于長(zhǎng)度小于允許誤差允許誤差，此時(shí)中點(diǎn)，此時(shí)中點(diǎn)(a+b)/2即為所求近似根即為所求近似根.3.2 迭代法及其收斂性迭代法及其收斂性3.2.1 3.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*)；反之亦然，稱；反之亦然，稱 x*為函數(shù)為函數(shù) (x)的一個(gè)的一個(gè). 求求 f(x) 的的就等于求就等于求 (x)的的，選擇一個(gè)初始近似

10、值，選擇一個(gè)初始近似值 x0，將它代入，將它代入(2.1)右右端，即可求得端，即可求得 x1= (x0). .lim xxkk可以如此反復(fù)迭代計(jì)算可以如此反復(fù)迭代計(jì)算 xk+1= (xk) (k=0,1,2,). (2.2) (x)稱為迭代函數(shù)稱為迭代函數(shù). 如果對(duì)任何如果對(duì)任何x0a, b，由，由(2.2)得得到的序列到的序列xk有極限有極限則稱迭代方程則稱迭代方程(2.2)收斂收斂. 且且x*= (x*)為為 (x)的的不動(dòng)點(diǎn)不動(dòng)點(diǎn)，故稱故稱(2.2)為為不動(dòng)點(diǎn)迭代法不動(dòng)點(diǎn)迭代法.當(dāng)當(dāng) (x)連續(xù)時(shí)，連續(xù)時(shí)，顯然顯然x*就是方程就是方程 x= (x)之之根根(不動(dòng)點(diǎn)不動(dòng)點(diǎn)). 于是可以從數(shù)

11、列于是可以從數(shù)列xk中求得滿足精度要求的近似根中求得滿足精度要求的近似根. 這種求根方法稱為這種求根方法稱為不動(dòng)點(diǎn)迭代法不動(dòng)點(diǎn)迭代法, 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)行迭代計(jì)算，結(jié)果如下：迭代計(jì)算，結(jié)果如下：

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

13、x 26271.124123xx671.124123xxxyoy= (x)y=x解解x= (x)求求 y=x 與與y= (x)的的交點(diǎn)的橫坐標(biāo)交點(diǎn)的橫坐標(biāo)x*x0(x0 , x1)(x1 , x2)(x1 , x1)x1x2迭代法的幾何意義迭代法的幾何意義xyy = xxyy = xxyy = xxyy = xx*x*x*x*y= (x)y= (x)y= (x)y= (x)x0p0 x1p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p1注：迭代法的研究涉及四個(gè)問(wèn)題：注：迭代法的研究涉及四個(gè)問(wèn)題：(1)(1)迭代公式的選?。坏降倪x??；(2)(2)迭代公式收斂性的判定；迭代公式收

14、斂性的判定；(3)(3)在收斂情況下，如何比較收斂速度；在收斂情況下，如何比較收斂速度；(4)(4)迭代停止的條件。迭代停止的條件。3.2.2 3.2.2 不動(dòng)點(diǎn)的存在性與迭代法的收斂性不動(dòng)點(diǎn)的存在性與迭代法的收斂性 首先考察首先考察 (x)在在a, b上不動(dòng)點(diǎn)的存在唯一性上不動(dòng)點(diǎn)的存在唯一性. 設(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)= (b)- -b0, 由連續(xù)函數(shù)性質(zhì)可知存在由連續(xù)函數(shù)性質(zhì)可知存在 x*(a, b) 使使 f(x*)=0，

15、即，即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)只能是唯一的. . 設(shè)設(shè) (x)Ca, b滿足定理滿足定理1中的兩個(gè)條件，中的兩個(gè)條件，則對(duì)任意則對(duì)任意x0a, b，由，由(2.2)得到的迭代序列得到的迭代序列xk收斂收斂到不動(dòng)點(diǎn)到不動(dòng)點(diǎn)x*，并有，并有)6 . 2(.1)5 . 2(.1101kkkkkxxLLxxxxLLxx 證明證明 設(shè)設(shè)x*a, b是是

16、 (x)在在a, b上的唯一不動(dòng)點(diǎn)上的唯一不動(dòng)點(diǎn), ,由條件由條件1，可知，可知xka, b，再由，再由(2.4)得得.)()(011xxLxxLxxxxkkkk 因因0L1時(shí)稱時(shí)稱超線性收斂超線性收斂，p=2 時(shí)稱時(shí)稱平方收斂平方收斂. 對(duì)于迭代過(guò)程對(duì)于迭代過(guò)程 xk+1= (xk)，如果，如果 ( (p) )(x)在在所求根所求根 x* 的鄰近連續(xù)（的鄰近連續(xù)（ p 1），并且），并且)8 . 2(. 0)(, 0)()()()()1( xxxxpp 則該迭代過(guò)程在則該迭代過(guò)程在 x* 的鄰近是的鄰近是 p 階收斂的階收斂的. 由于由于(x*)=0，根據(jù)定理，根據(jù)定理3立即可以斷定迭立即可

17、以斷定迭代過(guò)程代過(guò)程xk+1= (xk)具有局部收斂性具有局部收斂性. 再將再將 (xk)在根在根x*處做泰勒展開(kāi)處做泰勒展開(kāi), 利用條件利用條件(2.8), 則有則有.,)(!)()()()(之間之間與與在在 xxxxpxxkpkpk 注意到注意到 (xk)=xk+1， (x*)= x*，由上式得，由上式得,)(!)()(1pkpkxxpxx 因此對(duì)迭代誤差，令因此對(duì)迭代誤差，令k時(shí)有時(shí)有這表明迭代過(guò)程這表明迭代過(guò)程xk+1= (xk)確實(shí)為確實(shí)為 p 階收斂階收斂. 證畢證畢. ( )1|()|.!pkpkexep上述定理告訴我們，迭代過(guò)程的收斂速度依賴于上述定理告訴我們，迭代過(guò)程的收斂速度依賴于迭代函數(shù)迭代函數(shù) (x)的選取的選取. 如果如果xa, b但但 (x)0 時(shí)，則時(shí)，則該迭代過(guò)程只可能是線性收斂該迭代過(guò)程只可能是線性收斂.)0( aa的三階方法的三階方法. 假設(shè)假設(shè) x0 充分靠近充分靠近 x*, 求求13|lim|() |kkkaxax 提示：提示： 設(shè)設(shè) (x) =x(x2+3a)/(3x2+