解非線性方程的迭代法(4)課件

1、第第4 4章章 解非線性方程的迭代法解非線性方程的迭代法 本章討論求非線性方程 (x)=0 (4.1)的根的問題. 其中(x)是高次多項式函數(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ū)間. ,得到新的有根區(qū)間a1,b1, 設(shè)(x)在區(qū)間a,b上連續(xù)且(a)(b)0 .0abyxy=(x) 記a0=a,b0=b,計算,2000bax若|(x0)| ,則取x0 ;否則,若(a0)

2、(x0)0,取a1=x0,b1=b0 而且有根區(qū)間a1,b1長度是有根區(qū)間a0,b0長度的一半,x0再對有根區(qū)間a1,b1重復(fù)上面運(yùn)算, 即: 計算,2111bax若|(x1)|, 則取x1; 否則,若(a1)(x1)0, 取a2=x1 ,b2=b1,得到新的有根區(qū)間a2,b2. x1 而且有根區(qū)間a2,b2長度是有根區(qū)間a1,b1長度的一半.一直進(jìn)行下去,直到求出有根區(qū)間ak,bk. 或者有|(xk)| ,或者有此時,再計算.2kkkbax11002112222kkkkkkkababababx可見,k趨向無窮大時,xk收斂于 .而且,若要|xk-| ,只要12kab1log2abk或者此時可

3、取近似根xk . 在計算過程中,若出現(xiàn)|(xk)|1,或bk-ak2 .則可取xk作為方程(x)=0的近似根,終止運(yùn)算.例例1 用二分法求x3+4x-7=0在區(qū)間1,2內(nèi)根的近似值,并估計誤差. 解解 這里(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,x2=1.375,由于(x2)=1.0996,得新有根區(qū)間1.25,1.375,x3=1.3125,由于(x3)=0.511,得新有根區(qū)間1.25,1.3125,

4、.x9=1.254882813,得有根區(qū)間1.254882813,1.255859375,x10=1.255371094, (x10)=-0.000105285取x10=1.255371094作為方程根的近似值,且有 00049. 02254882813. 1255859375. 12|101010abx只需k5ln210-115.61.即需取x16. 如果取精度=10-5,則要使51110212|kkkabx 二分法要求函數(shù)在區(qū)間a，b上連續(xù)，且在區(qū)間兩端點(diǎn)函數(shù)值符號相反，二分法運(yùn)算簡便、可靠、易于在計算機(jī)上實(shí)現(xiàn)。但是，若方程(x)=0在區(qū)間a，b上根多于1個時，也只能求出其中的一個根。另外

5、，若方程(x)=0在區(qū)間a，b有重根時，也未必滿足(a)(b)0. 而且由于二分法收斂的速度不是很快,一般不單獨(dú)使用,而多用于為其他方法提供一個比較好的初始近似值. 2.1 簡單迭代法的一般形式簡單迭代法的一般形式2 簡簡 單單 迭迭 代代 法法 首先把方程(x)=0改寫成等價(同解)形式 x=(x) (4.2)得到迭代序列xk , 如果xk ,則有=(), 即是方程(x)=0的根.取一個合適的初始值x0,然后作迭代 xk+1=(xk) , k=0,1,2, (4.3) 這種求方程根的方法稱為簡單迭代法簡單迭代法,或逐逐次逼近法次逼近法.其中(x) 稱為迭代函數(shù)迭代函數(shù) ,式(4.3)稱為迭代

6、格式迭代格式. 若迭代序列xk 收斂 , 則稱簡單迭代法是收斂的簡單迭代法是收斂的. 解解 改寫原方程為等價方程 求方程x3-2x-3=0在1,2內(nèi)的根.例例2 332 xx , ,建立迭代格式, 2 , 1 , 0,3231kxxkk如果取初值x0=1.9 ,計算得kxkkxk0123451.91.894536471.893521141.893332331.893297221.893290696789101.893289471.893289251.893289211.893289201.89328920 由計算結(jié)果有，x10=x9，因此可取x10=1.89328920. 方程也可改寫成x=(

7、x3-3)/2, 建立迭代格式 xk+1=(xk3-3)/2 , k=0,1,2, 仍取初值x0=1.9, 則有 x1=1.9295, x2=2.0917, x3=3.0760, x4=13.0529可見,xk,此迭代格式是發(fā)散的.2.2 簡單迭代法的收斂條件及收斂階簡單迭代法的收斂條件及收斂階 首先，(x)應(yīng)使初值 x0 產(chǎn)生的序列xka, b,即(x)的值域落在定義域內(nèi). 另外,從幾何上看:x xo oy yy=xy=xy=(x)x x0 0 x x1 1x x2 2 x xo oy yy=xy=xy=(x)x x0 0 x x1 1x x2 2x xo oy yy=xy=xy=(x)x

8、x0 0 x x1 1x x2 2x xo oy yy=xy=xy=(x)x x0 0 x x1 1x x2 2 x x4 4x x3 3 1.a(x)b, xa,b; 2.|(x)| L0,要使|xk-|, 只要 證證 記(x)=(x)-x,則(a)=(a)-a0, (b)=(b)-b0,由(x)的連續(xù)性,必存在I,使()=()-=0,即=(),又(x)=(x)-10, 所以(x)=0的根唯一. |xk+1-xk|=|(xk)-(xk-1)|=|()(xk-xk-1)|L|xk-xk-1| |xk+1-|=|(xk)-()|=|()(xk-)|L|xk-| |xk+1-xk|=|(xk+1-

9、)-(xk-)| |xk-|-|xk+1-|(1-L)|xk-|01111111xxLLxxLLxxLxkkkkkk 求方程xex-1=0在0.5附近的根,精度要求=10-3. 解解 可以驗(yàn)證方程xex-1=0在區(qū)間0.5,0.6內(nèi)僅有一個根.例例3 改寫方程為x=e-x ,建立迭代格式, 2 , 1 , 0,1kexkxk 由于(x)=e-x ,在0.5,0.6上有|(x)|e-0.50.61.所以迭代法收斂. 取初值x0=0.5,計算得kxk|xk-xk-1|kxk|xk-xk-1|0123450.50.606530.545240.579700.560060.571170.106530.0

10、61290.034460.019640.011116789100.564860.568440.566410.567560.566910.006310.003580.002030.001150.00065 所以,取近似根x10=0.56691滿足精度要求. 如果精度要求為=10-5, 則由LxxLkln)1 (ln0195.196 . 0ln10653. 0104 . 0ln5可知,需要迭代20次. 實(shí)際上,方程在區(qū)間0.55,0.6上有唯一根，而在區(qū)間0.55,0.6上有|(x)|e-0.550.581。若取L=0.58，則有 注意：這里迭代次數(shù)20是充分的但不是必要的。LxxLkln)1 (

11、ln0150.42 10lnln0.5818.60.10653可知,需要迭代19次. 推論推論 若=(),(x)在附近具有一階連續(xù)導(dǎo)數(shù),且|()|0，當(dāng)x0I=-， +時，迭代格式xk+1=(xk),k=0,1,2,都收斂于方程x=(x)在區(qū)間I上的唯一根。 實(shí)際上，由連續(xù)性可知,存在L0，0，使對任何xI=-，+都有|(x)| L1. 而且，對任何xI=-，+，都有 |(x)-|=|(x)-()|=|()(x-)|L|x-|1則稱序列xk是p p階收斂的階收斂的, 稱p是收斂階收斂階,C是漸近誤差常漸近誤差常數(shù)數(shù). p=1稱為線性收斂線性收斂;p1稱超線性收斂超線性收斂;p=2稱平方收斂平方

12、收斂. 設(shè)(x)充分光滑, 由于 |ek+1|=|xk+1-|=|(xk)-()|=|(k)|ek|所以,當(dāng)()0時,有0| )(|)(limlim1kkkkkee于是此時,迭代法是m階收斂的.所以,當(dāng)()0時,簡單迭代法只具有線性收斂. 設(shè)()=()=(m-1)()=0,但(m)()0, 由于 |ek+1|=|xk+1-|=|(xk)-()|mkkmem)(!1)(0| )(|!1)(!1limlim)()(1mkmkmkkkmmee所以mkkmmkmkkkxmxmxxx)(!1)()!1(1)(21)()()()(1)1(2 下面介紹AitkenAitken加速算法加速算法，此方法可對線性

13、收斂的簡單迭代法起到加速作用，而且可應(yīng)用于其它數(shù)值方法中。假設(shè) (1)(2)，則有 由于 xk+1-=(1)(xk-) xk+2-=(2)(xk+1-)121kkkkxxxx即 (xk+1-)2(xk-)(xk+2-) xk+12-2xk+1+2xkxk+2-(xk+xk+2)+2 解得 kkkkkkxxxxxx122122kkkkkkxxxxxx12212)( 要比序列x k更快地收斂于 , 可構(gòu)造如下的Aitken加速算法:則,序列注意, 如果第k步發(fā)生zk-2yk+xk=0, 就終止計算, 取xk .如果記 kkkkkkkxxxxxxx12212)( kx , 2 , 1 , 0,2)(

14、21kxyzxyxxkkkkkkk)(kkxy)(kkyz例例4 分別用簡單迭代法和Aitken加速算法求方程x=1.6+0.99cosx在x0=/2附近的根.(=1.585471802)取x0= /2,計算結(jié)果如下k簡單迭代法kAitken算法xk|xk-xk-1|xk|xk-xk-1|012341.570801.61.571091.599711.571380.02920.028910.028620.028330121.57079631.585472581.585471800.014676280.00000078 NewtonNewton迭代法迭代法是求方程根的重要方法之一,其最大優(yōu)點(diǎn)是在方

15、程的單根附近具有平方收斂,而且Newton迭代法還可用來求方程的重根、復(fù)根及非線性方程組.3 Newton 迭代法迭代法 3.1 Newton迭代公式迭代公式 設(shè)(x)在有根區(qū)間a,b上二階連續(xù)可微, x0是根的某個近似值, 因?yàn)?00000)(2)()()()(xxfxxxfxfxf 取(x)(x0)+(x0)(x-x0),方程(x)=0近似為 (x0)+(x0)(x-x0)=0若(x0)0, 其解為)()(0001xfxfxx得到根的新的近似值x1 ,一般地,在xk附近線性化方程為 (xk)+(xk)(x-xk)=0設(shè)(xk)0, 其解為)4 . 4(, 2 , 1 , 0,)()(1kx

16、fxfxxkkkk迭代格式(4.4)稱為 NewtonNewton迭代法迭代法. . xyox0y=(x)x1x2直線 y=(x0)+(x0)(x-x0)就是 y-(x0)=(x0)(x-x0)Newton迭代法也叫切線法切線法. Newton迭代法相當(dāng)于取迭代函數(shù)3.2 Newton迭代法的收斂性迭代法的收斂性)()()(xfxfxx的簡單迭代法. 因?yàn)?22)()()()()()()(1)(xfxfxfxfxfxfxfx 如果是(x)=0的單根, 即()=0, 但()0, 則有()=0, 從而可知Newton迭代法在根附近是收斂的.因?yàn)?)(2)()()()(kkkkxxfxxxfxfxf

17、 所以2)(2)()()()(kkkkkxfxxfxff 于是有2)()(2)()()(kkkkkkxxffxfxfx 21)()(2)(kkkkxxffx 21)(limkkkxx)(2)(limkkkxff )(2)(ff 可見, Newton迭代法至少是平方收斂的. 若記其中(212mMC M2=max|(x)|,m1=min|(x)|. 則有 |xk+1-| C|xk-|2因此 C|xk+1-| (C|xk-|)2 (C|xk-1-|)4 120|)|(KxC可見,當(dāng)C|x0-|1, 即|x0-|1/2max|(x)|時,簡化Newton迭代法對x0I收斂.通常取M=(x0). 簡化N

18、ewton迭代法一般只具有線性收斂. 2. 2.割線法割線法 因?yàn)? 2 , 1 , 0,)()()(11kxxxfxfxfkkkkkoxyy=(x)x0 x1x2x3 為了簡化計算(xk),采用迭代格式, 3 , 2 , 1,)()()()(111kxxxfxfxfxxkkkkkkk稱為割線割線法法. . 若(x)在根附近二次連續(xù)可微,且()0,可以證明割線法是收斂的,且有)(2)(lim11ffeeekkkk 割線法收斂的階為.618. 1251p 3. 3.計算重根的計算重根的NewtonNewton迭代法迭代法 稱是方程(x)=0的m重根,是指(x)=(x-)m h(x),其中h(x)

19、在x=處連續(xù)且h()0, 若h(x)在處充分可微,則 ()=()=(m-1)()=0,(m)()0由于mmxhxxf11)()()(可見,恰是方程0)(1mxf 的單根.應(yīng)用Newton迭代法可得:)()(1)(1111kmkmkkkxfxfmxfxx, 2 , 1 , 0,)()(kxfxfmxkkk稱之為帶參數(shù)帶參數(shù)m m的的NewtonNewton迭代法迭代法, 它是求方程(x)=0m重根的具有平方收斂的迭代法. 再看函數(shù):)()()()()()()()(xhxxmhxhxxfxfxu可見,恰是方程u(x)=0的單根, 應(yīng)用Newton迭代法有)()(1kkkkxuxuxx這是求方程(x)=0重根的具有平方收斂的迭代法,而且