數(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)的求根問題，這里的求根問題，這里xR, f(x)Ca, b. 在科學與工程在科學與工程計算中有大量方程求根問題，其中一類特殊的問題計算中有大量方程求根問題，其中一類特殊的問題是多項式方程是多項式方程)2 . 1(),0()(01110 aax

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

3、零點，它使得，它使得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重零點重零點. 若若x*是是f(x)的的m重零點重零點，則，則. 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 ）二分法原理二分法原理二分法的實施過程二分法的實施過程取取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ū)間長

5、度的一半, 達到了達到了壓縮有根壓縮有根區(qū)間的目的區(qū)間的目的.如此反復進行如此反復進行, 即可的一系列即可的一系列有根區(qū)間套有根區(qū)間套 ,11nnbababa 由于每一區(qū)間都是前一區(qū)間的一半，因此區(qū)間由于每一區(qū)間都是前一區(qū)間的一半，因此區(qū)間an , bn的長度為的長度為)(ababnnn 21若每次二分時所取區(qū)間中點都不是根，則上述過程將若每次二分時所取區(qū)間中點都不是根，則上述過程將無限進行下去無限進行下去. 當當 n 時，區(qū)間必將最終收縮為一時，區(qū)間必將最終收縮為一點點x* ，顯然，顯然 x* 就是所求的就是所求的根根. 若取區(qū)間若取區(qū)間an , bn的中點的中點)(nnnbax 21作為作

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

7、算過程見下表下表, x6 = 1.3242 為所求之近似根為所求之近似根., 6 . 512lg2 nn 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)點是算法簡單，且總是收斂的，是算法簡單，且總是收斂的，缺缺點點是收

8、斂的太慢，故一般不單獨將其用于求根，只是收斂的太慢，故一般不單獨將其用于求根，只是用其為根求得一個較好的近似值是用其為根求得一個較好的近似值.二分法的計算步驟二分法的計算步驟: :步驟步驟1 準備準備 計算函數(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即是根，即是根，

9、計算過程結(jié)束，否則檢驗計算過程結(jié)束，否則檢驗. 反復執(zhí)行步驟反復執(zhí)行步驟2和步驟和步驟3，直到區(qū)間，直到區(qū)間a, b長度小于長度小于允許誤差允許誤差，此時中點，此時中點(a+b)/2即為所求近似根即為所求近似根.3.2 迭代法及其收斂性迭代法及其收斂性3.2.1 3.2.1 不動點迭代法不動點迭代法 將方程將方程 f(x)=0 改寫為等價方程形式改寫為等價方程形式 x= (x). (2.1)若要求若要求 x* 滿足滿足 f(x*)=0，則，則 x*= (x*)；反之亦然，稱；反之亦然，稱 x*為函數(shù)為函數(shù) (x)的一個的一個. 求求 f(x) 的的就等于求就等于求 (x)的的，選擇一個初始近似

10、值，選擇一個初始近似值 x0，將它代入，將它代入(2.1)右右端，即可求得端，即可求得 x1= (x0). .lim xxkk可以如此反復迭代計算可以如此反復迭代計算 xk+1= (xk) (k=0,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ù)

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

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

13、x 26271.124123xx671.124123xxxyoy= (x)y=x解解x= (x)求求 y=x 與與y= (x)的的交點的橫坐標交點的橫坐標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注：迭代法的研究涉及四個問題：注：迭代法的研究涉及四個問題：(1)(1)迭代公式的選??；迭代公式的選?。?2)(2)迭代公式收斂性的判定；迭代公式收

14、斂性的判定；(3)(3)在收斂情況下，如何比較收斂速度；在收斂情況下，如何比較收斂速度；(4)(4)迭代停止的條件。迭代停止的條件。3.2.2 3.2.2 不動點的存在性與迭代法的收斂性不動點的存在性與迭代法的收斂性 首先考察首先考察 (x)在在a, b上不動點的存在唯一性上不動點的存在唯一性. 設(shè)設(shè) (x)Ca, b滿足以下兩個條件：滿足以下兩個條件：1 對任意對任意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)的不動點的不動點. 再證不動點的再證不動點的. 設(shè)設(shè)x1*, x2*a, b都是都是 (x)的不動點，則由的不動點，則由(2.4)得得.)()(21212121 xxxxLxxxx 引出矛盾，故引出矛盾，故 (x)的不動點只能是唯一的的不動點只能是唯一的. . 設(shè)設(shè) (x)Ca, b滿足定理滿足定理1中的兩個條件，中的兩個條件，則對任意則對任意x0a, b，由，由(2.2)得到的迭代序列得到的迭代序列xk收斂收斂到不動點到不動點x*，并有，并有)6 . 2(.1)5 . 2(.1101kkkkkxxLLxxxxLLxx 證明證明 設(shè)設(shè)x*a, b是是

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

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