第四章解非線性方程的迭代法[章節(jié)講課]

1、第第4 4章章 解非線性方程的迭代法解非線性方程的迭代法 本章討論求非線性方程 (x)=0 (4.1) 的根的問(wèn)題. 其中(x)是高次多項(xiàng)式函數(shù)或超越函數(shù).如 (x)=3x5-2x4+8x2-7x+1 (x)=e2x+1-xln(sinx)-2 等等. 1 二二 分分 法法 設(shè)(x)在區(qū)間a,b上連續(xù)且(a)(b)0,根據(jù)連續(xù)函 數(shù)的介值定理,區(qū)間a,b上必有方程(x)=0的根,稱a,b 為方程(x)=0的有根區(qū)間. 1章節(jié)課件 ,得到新的有根區(qū)間a1,b1, 設(shè)(x)在區(qū)間a,b上連續(xù) 且(a)(b)0 . 0 a b y x y=(x) 記a0=a,b0=b,計(jì)算, 2 00 0 ba x

2、 若|(x0)| ,則取x0 ;否則, 若(a0)(x0)0,取a1=x0,b1=b0 而且有根區(qū)間a1,b1長(zhǎng)度是有根區(qū)間a0,b0長(zhǎng)度的一半, x0 再對(duì)有根區(qū)間a1,b1重復(fù)上面運(yùn)算, 即: 計(jì)算, 2 11 1 ba x 若|(x1)|, 則取x1; 否則,若(a1)(x1)0, 取a2=x1 ,b2=b1,得到新的有根區(qū) 間a2,b2. x1 而且有根區(qū)間a2,b2長(zhǎng)度是有根區(qū)間a1,b1 長(zhǎng)度的一半.一直進(jìn)行下去,直到求出有根區(qū)間ak,bk. 2章節(jié)課件 此時(shí),再計(jì)算 . 2 kk k ba x 或者有|(xk)| ,或者有 11 00 2 11 2222 kk kkkk k ab

3、ababab x 可見(jiàn),k趨向無(wú)窮大時(shí),xk收斂于 . 而且,若要|xk-| ,只要 1 2 k ab 1log 2 ab k或者 此時(shí)可取近似根xk . 在計(jì)算過(guò)程中,若出現(xiàn)|(xk)|1,或bk-ak2 .則可取 xk作為方程(x)=0的近似根,終止運(yùn)算. 例例1 用二分法求x3+4x-10=0在區(qū)間1,2內(nèi)根的近似 值,并估計(jì)誤差. 3章節(jié)課件 解解 這里(x)=x3+4x-7， (1)(2)=-180,所以(x)=0在1,2區(qū)間有唯一根. 取x0=1.5,由于(x0)=2.375,得新有根區(qū)間1,1.5, x1=1.25,由于(x1)=-0.0468,得新有根區(qū)間1.25,1.5, x

4、2=1.375,由于(x2)=1.0996,得新有根區(qū)間1.25,1.375, x3=1.3125,由于(x3)=0.511,得新有根區(qū)間1.25,1.3125, . x9=1.254882813,得有根區(qū)間1.254882813,1.255859375, x10=1.255371094, (x10)=-0.000105285 取x10=1.255371094作為方程根的近似值,且有 00049. 0 2 254882813. 1255859375. 1 2 | 1010 10 ab x4章節(jié)課件 只需k5ln210-115.61.即需取x16. 如果取精度=10-5,則要使 5 11 10

5、2 1 2 | kk k ab x 二分法要求函數(shù)在區(qū)間a，b上連續(xù)，且在區(qū)間兩端 點(diǎn)函數(shù)值符號(hào)相反，二分法運(yùn)算簡(jiǎn)便、可靠、易于在計(jì)算 機(jī)上實(shí)現(xiàn)。但是，若方程(x)=0在區(qū)間a，b上根多于1 個(gè)時(shí)，也只能求出其中的一個(gè)根。另外，若方程(x)=0在 區(qū)間a，b有重根時(shí)，也未必滿足(a)(b)0. 而且由于 二分法收斂的速度不是很快,一般不單獨(dú)使用,而多用于為 其他方法提供一個(gè)比較好的初始近似值. 5章節(jié)課件 2.1 簡(jiǎn)單迭代法的一般形式簡(jiǎn)單迭代法的一般形式 2 簡(jiǎn)簡(jiǎn) 單單 迭迭 代代 法法 首先把方程(x)=0改寫成等價(jià)(同解)形式 x=(x) (4.2) 得到迭代序列xk , 如果xk ,則有

6、=(), 即是方 程(x)=0的根. 取一個(gè)合適的初始值x0,然后作迭代 xk+1=(xk) , k=0,1,2, (4.3) 這種求方程根的方法稱為簡(jiǎn)單迭代法簡(jiǎn)單迭代法,或逐逐 次逼近法次逼近法.其中(x) 稱為迭代函數(shù)迭代函數(shù) ,式(4.3)稱為迭代格式迭代格式. 若迭代序列xk 收斂 , 則稱簡(jiǎn)單迭代法是收斂的簡(jiǎn)單迭代法是收斂的. 6章節(jié)課件 解解 改寫原方程為等價(jià)方程 求方程x3-2x-3=0在1,2內(nèi)的根. 例例2 3 32 xx , ,建立迭代 格式 , 2 , 1 , 0,32 3 1 kxx kk 如果取初值x0=1.9 ,計(jì)算得 kxkkxk 0 1 2 3 4 5 1.9

7、1.89453647 1.89352114 1.89333233 1.89329722 1.89329069 6 7 8 9 10 1.89328947 1.89328925 1.89328921 1.89328920 1.89328920 7章節(jié)課件 由計(jì)算結(jié)果有，x10=x9，因此可取x10=1.89328920. 定義定義4.14.1 設(shè)(x)為定義在區(qū)間I I上的函數(shù), 且對(duì)任何 xI I,均有(x)I I,則稱(x)為I I到自身上的映射到自身上的映射. 方程也可改寫成x=(x3-3)/2, 建立迭代格式 xk+1=(xk3-3)/2 , k=0,1,2, 仍取初值x0=1.9, 則

8、有 x1=1.9295, x2=2.0917, x3=3.0760, x4=13.0529 可見(jiàn),xk,此迭代格式是發(fā)散的. 2.2 簡(jiǎn)單迭代法的收斂條件簡(jiǎn)單迭代法的收斂條件 定義定義4.24.2 設(shè)(x)為I I到自身上的映射,且存在0L1, 使對(duì)任何x1,x2I,I,有|(x2)-(x1)| L|x2-x1|,則稱(x) 為I I上的壓縮映射壓縮映射, L稱為L(zhǎng)ipschitzLipschitz常數(shù)常數(shù). 8章節(jié)課件 若(x)為I上的壓縮映射,則(x)在I上連 續(xù). 定理定理4.24.2 若(x)為I到自身上的映射,且(x)C1(I), |(x)| L1,則(x)為I上的壓縮映射. 證證

9、對(duì)任意x1,x2I,有 |(x2)-(x1)|=|()|x2-x1| L|x2-x1| 定義定義4.34.3 若(x)為I到自身上的映射,且I I滿足,= (),則稱為(x)的不動(dòng)點(diǎn)不動(dòng)點(diǎn). . 定理定理4.34.3 若(x)為I上的壓縮映射, 則(x)在I I上存 在唯一的一個(gè)不動(dòng)點(diǎn),且對(duì)任何x0I,由迭代格式 xk+1=(xk) , k=0,1,2, 產(chǎn)生的序列xk收斂于(x)的不動(dòng)點(diǎn). 定理定理4.1 9章節(jié)課件 證證 不妨設(shè)I=a,b,作函數(shù)(x)=(x)-x,由于xI時(shí), (x)I,則(a)=(a)-a0,(b)=(b)-b0,由(x)的連 續(xù)性, 必存在I, 使()=()-=0,即

10、=(),就是 (x)的不動(dòng)點(diǎn). 若,I均為(x)的不動(dòng)點(diǎn),則有 |-|=|()-()| L|-|-| 所以只能=,即(x)在I上僅有一個(gè)不動(dòng)點(diǎn). 對(duì)任意x0I,有x1=(x0)I,遞推得xkI,設(shè)是(x) 的不動(dòng)點(diǎn),則 |xk+1-|=|(xk)-()| L|xk-| L2|xk-1-| Lk+1|x0-| 所以xk. 10章節(jié)課件 若=(),而在I=-,+上(x)滿足 |(x)-()| L|x-| 這里L(fēng)1為L(zhǎng)ipschitz常數(shù),則當(dāng)x0-,+時(shí),有 (1) 由迭代xk+1=(xk)產(chǎn)生的迭代序列xkI; 推論推論 若(x)C1a,b,且滿足 1.a(x)b, xa,b; 2.|(x)|

11、L0, 使對(duì)任何xI=-, +都有|(x)| L1. 2.3 簡(jiǎn)單迭代法的誤差分析與簡(jiǎn)單迭代法的誤差分析與 收斂階收斂階 推論推論 若=(),(x)在附近具有一階連續(xù)導(dǎo)數(shù),且 |()|0, 當(dāng)x0I=-, +時(shí), 有 (1) 由迭代xk+1=(xk)產(chǎn)生的迭代序列xkI; ;lim)2( k k x (3) 是I上(x)的唯一不動(dòng)點(diǎn). 定理定理4.54.5 若(x)為I上壓縮映射,則x0I,由迭代 xk+1=(xk) , k=0,1,2, 產(chǎn)生的迭代序列xk滿足: 12章節(jié)課件 證證 |xk+1-xk|=|(xk)-(xk-1)| L|xk-xk-1| |xk+1-|=|(xk)-()| L|

12、xk-| 1 1 kkk xx L L x 01 1 xx L L x k k |xk+1-xk|=|(xk+1-)-(xk-)| |xk-|-|xk+1-|(1-L)|xk-| 0111 111 1 xx L L xx L L xx L x k kkkkk 由誤差估計(jì)式可見(jiàn),對(duì)任一0,要使|xk-|, 只要 L xx L kln )1 ( ln 01 13章節(jié)課件 求方程xex-1=0在0.5附近的根,精度要求=10-3. 解解 可以驗(yàn)證方程xex-1=0在區(qū)間0.5,0.6內(nèi)僅有一 個(gè)根. 例例3 改寫方程為x=e-x ,建立迭代格式 , 2 , 1 , 0, 1 kex k x k 由于

13、(x)=e-x ,在0.5,0.6上有|(x)|e-0.50.61 則稱序列xk是p p階收斂的階收斂的, 稱p是收斂階收斂階,C是漸近誤差常漸近誤差常 數(shù)數(shù). p=1稱為線性收斂線性收斂;p1稱超線性收斂超線性收斂;p=2稱平方收斂平方收斂. 設(shè)(x)充分光滑, 由于 |ek+1|=|xk+1-|=|(xk)-()|=|(k)|ek| 所以,當(dāng)()0時(shí),有 0| )(|)(limlim 1 k k k k k e e 16章節(jié)課件 于是 此時(shí),迭代法是m階收斂的. 所以,當(dāng)()0時(shí),簡(jiǎn)單迭代法只具有線性收斂. 設(shè)()=()=(m-1)()=0,但(m)()0, 由于 |ek+1|=|xk+1

14、-|=|(xk)-()| m kk m e m )( ! 1 )( 0| )(| ! 1 )( ! 1 limlim )()(1 m k m k m k k k mm e e 所以 m kk mm k m kkk x m x m xxx )( ! 1 )( )!1( 1 )( 2 1 )()()( )(1)1( 2 下面介紹AitkenAitken加速算法加速算法，此方法可對(duì)線性收斂的簡(jiǎn) 單迭代法起到加速作用，而且可應(yīng)用于其它數(shù)值方法中。 17章節(jié)課件 假設(shè) (1)(2)，則有 由于 xk+1-=(1)(xk-) xk+2-=(2)(xk+1-) 12 1 k k k k x x x x 即

15、(xk+1-)2(xk-)(xk+2-) xk+12-2xk+1+2xkxk+2-(xk+xk+2)+2 解得 kkk kkk xxx xxx 12 2 12 2 kkk kk k xxx xx x 12 2 1 2 )( 18章節(jié)課件 則,序列 注意, 如果第k步發(fā)生zk-2yk+xk=0, 就終止計(jì)算, 取xk . 如果記 kkk kk kk xxx xx xx 12 2 1 2 )( k x 要比序列x k更快地收斂于 , 可構(gòu)造如下的 Aitken加速算法: , 2 , 1 , 0, 2 )( 2 1 k xyz xy xx kkk kk kk )( kk xy )( kk yz 例例

16、4 分別用簡(jiǎn)單迭代法和Aitken加速算法求方程 x=1.6+0.99cosx在x0=/2附近的根.(=1.585471802) 19章節(jié)課件 取x0= /2,計(jì)算結(jié)果如下 k 簡(jiǎn)單迭代法 k Aitken算法 xk|xk-xk-1|xk|xk-xk-1| 0 1 2 3 4 1.57080 1.6 1.57109 1.59971 1.57138 0.0292 0.02891 0.02862 0.02833 0 1 2 1.5707963 1.58547258 1.58547180 0.01467628 0.00000078 20章節(jié)課件 NewtonNewton迭代法迭代法是求方程根的重要方

17、法之一,其最大優(yōu) 點(diǎn)是在方程的單根附近具有平方收斂,而且Newton迭代法 還可用來(lái)求方程的重根、復(fù)根及非線性方程組. 3 Newton 迭代法迭代法 3.1 Newton迭代公式迭代公式 設(shè)(x)在有根區(qū)間a,b上二階連續(xù)可微, x0是根的 某個(gè)近似值, 因?yàn)?2 0 0 000 )( 2 )( )()()(xx f xxxfxfxf 取(x)(x0)+(x0)(x-x0),方程(x)=0近似為 (x0)+(x0)(x-x0)=0 若(x0)0, 其解為 21章節(jié)課件 )( )( 0 0 01 xf xf xx 得到根的新的近似值x1 ,一般地,在xk附近線性化方程為 (xk)+(xk)(x

18、-xk)=0 設(shè)(xk)0, 其解為 )4 . 4(, 2 , 1 , 0, )( )( 1 k xf xf xx k k kk 迭代格式(4.4)稱為 NewtonNewton 迭代法迭代法. . x y ox0 y=(x) x1x2 直線 y=(x0)+(x0)(x-x0) 就是 y-(x0)=(x0)(x-x0) Newton迭代法也叫切線法切線法. 22章節(jié)課件 Newton迭代法相當(dāng)于取迭代函數(shù) 3.2 Newton迭代法的收斂性迭代法的收斂性 )( )( )( xf xf xx 的簡(jiǎn)單迭代法. 因?yàn)?22 2 )( )()( )( )()()( 1)( xf xfxf xf xfx

19、fxf x 如果是(x)=0的單根, 即()=0, 但()0, 則有 ()=0, 從而可知Newton迭代法在根附近是收斂的. 因?yàn)?2 )( 2 )( )()()( kkkk xx f xxxfxfxf 所以 2 )( 2 )( )()()( k k kkk x f xxfxff 23章節(jié)課件 于是有 2 )( )(2 )( )( )( k k k k k k x xf f xf xf x 2 1 )( )(2 )( k k k k x xf f x 2 1 )( lim k k k x x )(2 )( lim k k k xf f )(2 )( f f 可見(jiàn), Newton迭代法至少是平

20、方收斂的. 若記其中( 2 1 2 m M C M2=max|(x)|,m1=min|(x)|. 則有 |xk+1-| C|xk-|2 因此 C|xk+1-| (C|xk-|)2 (C|xk-1-|)4 1 2 0 |)|( K xC 可見(jiàn),當(dāng)C|x0-|1, 即|x0-|1/2max|(x)| 時(shí),簡(jiǎn)化Newton迭代法對(duì)x0I收斂.通常取M=(x0). 簡(jiǎn)化Newton迭代法一般只具有線性收斂. 2. 2.割線法割線法 因?yàn)?, 2 , 1 , 0, )()( )( 1 1 k xx xfxf xf kk kk k 27章節(jié)課件 o x y y=(x) x0 x1x2 x3 為了簡(jiǎn)化計(jì)算(

21、xk),采用迭代格式 , 3 , 2 , 1,)( )()( )( 1 1 1 kxx xfxf xf xx kk kk k kk 稱為割線割線法法. . 若(x)在根附近二次連 續(xù)可微,且()0,可以證明 割線法是收斂的,且有 )(2 )( lim 1 1 f f ee e kk k k 割線法收斂的階為.618. 1 2 51 p 3. 3.計(jì)算重根的計(jì)算重根的NewtonNewton迭代法迭代法 28章節(jié)課件 稱是方程(x)=0的m重根,是指(x)=(x-)m h(x),其 中h(x)在x=處連續(xù)且h()0, 若h(x)在處充分可微,則 ()=()=(m-1)()=0,(m)()0 由于

22、 mm xhxxf 11 )()()( 可見(jiàn),恰是方程 0)( 1 m xf 的單根.應(yīng)用Newton迭代法可得: )()( 1 )( 1 1 1 1 k m k m k kk xfxf m xf xx , 2 , 1 , 0, )( )( k xf xf mx k k k 稱之為帶參數(shù)帶參數(shù)m m的的NewtonNewton迭代法迭代法, 它是求方程(x)=0m重根 的具有平方收斂的迭代法. 再看函數(shù): 29章節(jié)課件 )()()( )()( )( )( )( xhxxmh xhx xf xf xu 可見(jiàn),恰是方程u(x)=0的單根, 應(yīng)用Newton迭代法有 )( )( 1 k k kk xu xu xx 這是求方程(x