方程求根的迭代法(19-20)

1、重慶大學(xué)數(shù)理學(xué)院數(shù)數(shù) 值值 分分 析析第第十講十講主講教師主講教師： 譚譚 宏宏第四章第四章 非線性方程求根非線性方程求根1 1教學(xué)內(nèi)容：教學(xué)內(nèi)容： 二分法、迭代法的一般原理 、NEWTON迭代法 2 2重點難點：重點難點：重點：重點：牛頓迭代法及局部收斂性難點：難點：迭代法及收斂性定理3 3教學(xué)目標(biāo)：教學(xué)目標(biāo)： 掌握迭代法的一般原理、對給出的方程球根問題，能利用一般迭代法或者牛頓迭代法進行數(shù)值求解0tg xx0sin8889. 4tg25. 0 xx 在中學(xué)時，我們很熟悉一次、二次代數(shù)方程以及某些特殊的高次方程或超越方程的解法。這些方法都是代數(shù)解法，也是精確法。但在實際中，有許多方程問題無法

2、求出公式解。例如超越方程 看起來很簡單，卻不容易求得精確解。至于解三次、四次代數(shù)方程，盡管存在著求解公式，卻不實用，而對一般的五次或五次以上的代數(shù)方程，根本沒有求根公式。另一方面，在實際應(yīng)用中，只要能獲得具有預(yù)先給定的誤差限內(nèi)的近似值就可以了。因此，需要引進能夠達到一定精度要求的求方程近似值的方法。 求方程0)(xf的根也叫求函數(shù))(xf的零點。需要解決的幾個問題：1根的存在性。方程有沒有根？如果有根，有幾個根？根的存在性。方程有沒有根？如果有根，有幾個根？2這些根大致在哪里？如何把根隔離開來？這些根大致在哪里？如何把根隔離開來？3根的精確化根的精確化定理定理1：設(shè)函數(shù)設(shè)函數(shù) f (x) 在區(qū)

3、間在區(qū)間a, b上連續(xù)上連續(xù)，如果如果f (a) f (b) 0， 則方程則方程 f (x) = 0 在在a, b內(nèi)至少有一實根內(nèi)至少有一實根x*。 二分法的基本思想是： 逐步將有根區(qū)間分半，通過判別函數(shù)值的符號，進一步搜索有根區(qū)間，將有根區(qū)間縮小到充分小，從而求出滿足給定精度的根的近似值。 執(zhí)行步驟執(zhí)行步驟1計算計算f (x)在有解區(qū)間在有解區(qū)間a, b端點處的值端點處的值，f (a)，f (b)。2計算計算f (x)在區(qū)間中點處的值在區(qū)間中點處的值f (x1)。3判斷若判斷若f (x1) = 0，則則x1即是根，否則檢驗即是根，否則檢驗：（1）若若f (x1)與與f (a)異號異號，則知解

4、位于區(qū)間則知解位于區(qū)間a, x1， b1=x1, a1=a;（2）若若f (x1)與與f (a)同號同號，則知解位于區(qū)間則知解位于區(qū)間x1, b， a1=x1, b1=b。反復(fù)執(zhí)行步驟反復(fù)執(zhí)行步驟2、3，便可得到一系列有根區(qū)間便可得到一系列有根區(qū)間：(a, b), (a1, b1), , (ak, bk), 4、當(dāng)當(dāng)11kkab時時)(211kkkbax5、則、則即為根的近似即為根的近似簡單簡單; 對對f (x) 要求不高要求不高(只要連續(xù)即可只要連續(xù)即可) .無法求復(fù)根及偶重根無法求復(fù)根及偶重根 收斂慢收斂慢 Yx0*xab)(xfy 21bax1a1b2xYx0*xab誤差估計：)(21|

5、*abxxkk由于：*limxxkk所以，二分法可以求得任意精度的根。對于任意給定的精度要求：0由)(21|*abxxkk得：2lnln)ln(abk即：只要二分K次，就可得到指定精度的根。例： 求方程在 區(qū)間1, 1.5內(nèi)的 實根。要求準(zhǔn)確到小數(shù)點后第2位。 01)(3xxxf 用二分法，這里a = 1, b = 1.5， 且f (a) 0。取區(qū)間a, b的中點x0 = 1.25將區(qū)間二等分， 由于f (x0)0f (a) f (b)=0f (a) =0打印打印b, k打印打印a, k結(jié)束結(jié)束是是是是是是否否否否否否m=(a+b)/2|a-b|0打印打印m, ka=mb=m結(jié)束結(jié)束k=K+1

6、是是是是否否否否輸入輸入 ,bak = 0二分法程序流程圖1、迭代法的設(shè)計思想 迭代法是一種逐次逼近法，這種方法使用某個固定公式所謂迭代公式反復(fù)校正根的近似值，使之逐步精確化，直至滿足精度要求的結(jié)果。 迭代法的求根過程分成兩步，第一步先提供根的某個猜測值，即所謂迭代初值，然后將迭代初值逐步加工成滿足精度要求的根。迭代法的設(shè)計思想是：f (x) = 0等價變換等價變換)(xx迭代函數(shù)把根的某個猜測值0 x=()代入迭代函數(shù)得)(01xx0 x1x1x2x2x3x一般地：)(1kkxxkx得到序列的根：收斂就必收斂到則若0)(xfxk)lim()(limlim1kkkkkkxxx)(*xx 迭代過

7、程的幾何表示 ) : )(xyxyxx交點即真根。( )yxy xO x* x2 x1 x0 xy0P1Q1P2P*P2Q例：例：求方程求方程0210)(xxxf的一個根的一個根210 xx解：解：)2lg( xx等價變換等價變換迭代格式迭代格式)2lg(1kkxxx1 = 0.4771x2 = 0.3939x6 = 0.3758x7 =0.3758取初始值x0 = 1，可逐次算得 迭代法的設(shè)計思想是：f (x) = 0等價變換等價變換)(xx迭代函數(shù))(1kkxx問題：？1、怎樣選取迭代函數(shù)2、怎樣保證迭代收斂3、怎樣加速迭代收斂3*0331k ( )10 1.5. 1 1 1(0,1,2)

8、 k 0 1 2 7 8 x 1.51.35721 1.330861.324kkf xxxxxxxxxk 例：求方程 在附近的根解：（ ） 將方程改寫為由此建立迭代公式331k721.32472 2 11.k 0 1 2 x1.52.37512.39 kkxxxx迭代收斂。（ ） 若將方程改寫為建立迭代公式 迭代不收斂。xyy = 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 x1p11| )( |x1| )( |x1| )( |x1| )( |x3、壓縮映像原理定

9、理定理1：如果：如果 (x)滿足下列條件滿足下列條件（1 1）當(dāng)）當(dāng)x a, b時，時， (x) a, b（2 2）當(dāng)任意）當(dāng)任意x a, b，存在，存在0 L 1，使，使 則方程則方程x = (x)在在a, b上有唯一的根上有唯一的根x*, ,且對任意初值且對任意初值 x0 a, b時，迭代序列時，迭代序列xk+1= (xk) (k = 0, 1, )收斂于收斂于x*。1)( Lx(6)kkkxxLxx1*1101*1xxLLxxkk且有下列誤差估計且有下列誤差估計(7)(8)證：)( )()(*1*kkkxxxxxx其中 在x*與xk之間， 設(shè)x*是方程的根，即x*= (x*)，由微分中值

10、定理0*11*2*1*)( )()(xxLxxLxxLxxxxxxkkkkkk由條件（2）得因為0 L 1，由知0lim1kkL)(01*kxxk所以*limxxkk即 xk+1 = (xk)收斂因為：| )1 (|*1*1kkkkkkkxxLxxLxxxxxxxx所以：kkkxxLxx1*11012121111)( )()(xxLxxLxxLxxxxxxkkkkkkkkkkk而：所以：01*11xxLxxk 據(jù)（7）式，只要 充分小，就可以保證足夠小。因此可用條件 來控制迭代過程的結(jié)束。kkxx1kxx *kkxx1例：求方程 在0, 0.5內(nèi)的根，精確到10-5。0133 xx)() 1(

11、313xxx0)( 2 xx125. 05 . 0)( max2xL解：將方程變形因為，在0, 0.5內(nèi) 為增函數(shù)，所以滿足收斂條件，取x0 = 0.25，算得x1 = (0.25) = 0.3385416 x2 = (x1) = 0.3462668x3 = (x2) =0.3471725 x4 = (x3) =0.3472814x5 = (x4) =0.3472945 x6 = (x5) =0.3472961x7 = (x6) =0.3472963因為66710|3472961. 03472963. 0| xx取近似根為x* = 0.34729621112 ( )10 (1.5)0.250,

12、 (2)10 1.5,2 11( ) 1.51.5 1( )2 12111( )3.162212 2.51(2) 1( ) f xxxffxxxxxxxxx 例：用簡單迭代法求方程的根。解：因為有根區(qū)間。（ ）因且2222011 1.5 1( )1221.5111 ( )1.52.25 1.5,2,xxxx 因且根據(jù)定理，任取由這兩種等價方程所構(gòu)造的簡單迭代方法都收斂，且第一種所產(chǎn)生的迭代序列收斂較快。4、迭代過程的局部收斂性在實際應(yīng)用迭代法時，通常首先在根 的鄰近考察。*x 稱一種迭代過程在根 鄰近收斂，如果存在鄰域 ，使迭代過程對于任意初值 均收斂，這種在根的鄰近所具有的收斂性被稱為局部局

13、部收斂性收斂性。*x*: xx0 x 定理定理2 設(shè) 在 的根 鄰近有連續(xù)導(dǎo)數(shù)，且 成立 則迭代過程 在 鄰近具有局部收 斂性。 x xx*x *1x1kkxx*x5、迭代過程的收斂速度 設(shè)由某方法確定的序列設(shè)由某方法確定的序列xk收斂于方程的根收斂于方程的根x*，如果存在正實數(shù)如果存在正實數(shù)p，使得，使得定義：定義：Cxxxxpkkk*1*lim（C C為非零常數(shù)）為非零常數(shù)）則稱序列則稱序列xk收斂于收斂于x*的收斂速度是的收斂速度是p階的，或稱該方法階的，或稱該方法具有具有p 階斂速。當(dāng)階斂速。當(dāng)p = 1時，稱該方法為線性（一次）收斂；時，稱該方法為線性（一次）收斂；當(dāng)當(dāng)p = 2時，

14、稱方法為平方（二次）收斂；當(dāng)時，稱方法為平方（二次）收斂；當(dāng)1 p 2時，時，稱方法為超線性收斂。稱方法為超線性收斂。對于在根 鄰近收斂的迭代公式，由于)( *1*kkxxxx式中 介于 與 之間，故有：kx*x|)( |1*1*kkxxxx所以：)( lim*1*1*xxxxxkkk因此，若 則該迭代過程為線性收斂。)( *x0)( *x若將)(kx在 處泰勒展開有：*x2*2*)(2)( )()(2)( )( )()(xxxxxxxxxxkkkk1kx*x所以，2)( )(2*1xxxxkk故2)( lim*2*1*xxxxxkkk即當(dāng)0)( *x0)( ,*x迭代過程為平方收斂的。星期三晚 設(shè) 是根 的某個近似值，用迭代公式校正一次得kx*x1kkxx假設(shè) 在所考察的范圍內(nèi)改變不大，其估計值為L， 則有 x*1kkxxL xx據(jù)此可導(dǎo)出如下加速公式： 其一步分為兩個