計算方法 4方程求根的迭代法

1、第5章 方程求根的數(shù)值解法1 二分法二分法2 迭代法迭代法3 切線法切線法(牛頓法牛頓法)4 弦截法弦截法5 加速迭代法加速迭代法 1二分法二分法 我們已經(jīng)熟悉求解一元一次方程、一元二次方程以及某些特殊類型的高次代數(shù)方程或非線性方程的方法。這些方法都是代數(shù)解法,求出的根是方程的準(zhǔn)確根。但是在許多實際問題中遇到的方程,例如代數(shù)方程 x3-x-1=0 或超越方程 cos03xxe 等等,看上去形式簡單,但卻不易求其準(zhǔn)確根。為此,只能求方程達到一定精度的近似根。 方程的形式很多,我們主要討論一元非線性方程,也即 f(x)=0 (51) 方程(51)可以有實根,也可以有復(fù)根或者重根等。本章主要討論它的

2、實根的數(shù)值計算問題。 方程根的數(shù)值計算大致可分三個步驟進行: (1) 判定根的存在性。 (2)確定根的分布范圍,即將每一個根用區(qū)間隔離開來。 (3)根的精確化,即根據(jù)根的初始近似值按某種方法逐步精確化,直至滿足預(yù)先要求的精度為止。 設(shè)f(x)為定義在某區(qū)間上的連續(xù)函數(shù),方程(51)存在實根。雖然方程(51)的根的分布范圍一般比較復(fù)雜,但我們不難將函數(shù)f(x)的定義域分成若干個只含一個實根的區(qū)間。 例如考慮方程 x2-2x-1=0 由圖5.1所示,該方程的一個負實根在-1和0之間,另一個正實根在2和3之間。 圖 5.1 這樣,我們總可以假設(shè)方程(51)(a,b)內(nèi)有且僅有一個單實根x*。由連續(xù)函

3、數(shù)的介值定理知 f(a)f(b)0 若數(shù)值b-a較小,那么我們可在(a,b)上任取一點x0作為方程的初始近似根。 例如,方程 f(x)=x3-x-1=0 由于f(1)0,f(1.5)0,又f(x)在區(qū)間(1,1.5)上單調(diào)連續(xù),故可知在(1,1.5)內(nèi)有且僅有一個實根。于是可取某個端點或區(qū)間內(nèi)某一個點的值作為根的初始近似值。 設(shè)函數(shù)f(x)在區(qū)間a,b上單調(diào)連續(xù),且 f(a)f(b)0 則方程(51)在區(qū)間(a,b)內(nèi)有且僅有一個實根x。下面在有根區(qū)間(a,b)內(nèi)介紹二分法的基本思想。 計算f(a)與f(x0),若 f(a)f(x0)0 則根x(a,x0),令 a1=a,b1=x0 否則x(x

4、0,b),令 a1=x0,b1=b圖 5 .2 如此逐次往復(fù)下去,便得到一系列有根區(qū)間 (a,b),(a1,b1),(a2,b2),(ak,bk), 其中111()21()2kkkkkkkbabababa這里a0=a, b0=b顯然有 (52) 當(dāng)k時,區(qū)間(ak,bk)最終必收斂于一點,該點就是所求方程(51)的根x。 我們把每次二分后的有根區(qū)間(ak,bk)的中點 1()2kkkxab作為所求根x的近似值,這樣獲得一個近似根的序列 x0,x1,x2,xk,該序列必以根x為極限,即limkkxx111()2kkkkkxxbaba(53) 故對于預(yù)先給定的精度,若有11kkba 則結(jié)果xk就是

5、方程(51)滿足預(yù)給精度的近似根,也即kxx由式(52)和(53)還可得到誤差估計式為11()2kkxxba(54) 對于確定的精度,從式(54)易求得需要二等分的次數(shù)k。 二分法具有簡單和易操作的優(yōu)點。其計算步驟如下,框圖如圖5.3所示。1.計算步驟 輸入有根區(qū)間的端點a,b及預(yù)先給定的精度;(a+b)/2 x;若f(a)f(x)0,則xb,轉(zhuǎn)向;否則xa,轉(zhuǎn)向。若b-a,則輸出方程滿足精度的根x,結(jié)束;否則轉(zhuǎn)向。 2. 計算框圖 例1 求方程 f(x)=x3-x-1=0 在區(qū)間(1,1.5)內(nèi)的根。要求用四位小數(shù)計算,精確到10-2。 解 這里 a=1,b=1.5 取區(qū)間(1,1.5)的中

6、點01(1 1.5)1.252x 圖 5.3 由于f(1)0,f(1.25)0,則令 a1=1.25, b1=1.5 得到新的有根區(qū)間(1.25,1.5) 表 51 2 迭代法迭代法 迭代法的基本思想是:首先將方程(51)改寫成某種等價形式,由等價形式構(gòu)造相應(yīng)的迭代公式,然后選取方程的某個初始近似根x0,代入迭代公式反復(fù)校正根的近似值,直到滿足精度要求為止。迭代法是一種數(shù)值計算中重要的逐次逼近方法。 例如,求方程 x3-x-1=0 在x=1.5附近的一個根(用六位有效數(shù)字計算)。 首先將原方程改寫成等價形式31xx用初始近似根 x0=1.5 代入式(55)的右端可得3011.35721xx x

7、1與x0相差較大,如果改用x1作為近似根代入式(55)的右端得32110,1,2,xxk 表 52 對于一般形式的方程(51),首先我們設(shè)法將其化為下列等價形式 x=g(x) (57) 然后按(57)構(gòu)造迭代公式 從給定的初始近似根x0出發(fā),按迭代公式(58)可以得到一個數(shù)列 x0,x1,x2,xk, 若這個數(shù)列xk有極限,則迭代公式(58)是收斂的。此時數(shù)列的極限1(),0,1,2,kkxg xklimkkxx 就是原方程(51)的根。 雖然迭代法的基本思想很簡單,但效果并不總是令人滿意的。對于上例,若按方程寫成另一種等價形式 x=x3-1 (59) 建立迭代公式 xk+1=x3k-1, k

8、=0,1,2, 仍取初始值x0=1.5, 則迭代結(jié)果為 x1=2.375 x2=12.3976 定理設(shè)方程x=g(x)在(a,b)內(nèi)有根x,g(x)滿足李普希茨(Lipschitz)條件:即對(a,b)內(nèi)任意的x1和x2都有1212()()g xg xq xx q為某個確定的正數(shù),若q1,則方程在(a,b)內(nèi)有唯一的根;且迭代公式 xk+1=g(xk) 對任意初始近似值x0均收斂于方程的根x;還有誤差估計式11011kkkkqqxxxxxxqq(511) 因為，對任意正整數(shù)p有 11211111()1kpkkpkpkkkkppkkpkkxxxxxxxxqqq xxqqxxq 當(dāng) 時，p11kk

9、kpkxxqqxx 證 由已知條件知,x為方程x=g(x)的根,即x=g(x)()()xg xyg y設(shè) 也是方程的根,即xy于是,由李普希茨條件得因為q1,所以上式矛盾,故必有xy*)()(yxqygxgyx 亦即方程在(a,b)內(nèi)有唯一的根。 再考慮迭代公式 x k+1=g(xk) , k=0,1,2, 由李普希茨條件10()()kkkxxg xg xq xx(512) 由(512)可得 10kkxxq xx(513) 因為q1,當(dāng)k時,qk0,即有 10kxxlimkkxx所以 也就是對任意初始值x0迭代公式收斂。利用李普希茨條件111)()(kkkkkkxxqxgxgxx 迭代法的幾何

10、意義:把方程(51)求根的問題改寫成(57)變?yōu)榍髷?shù)列xn的極限,實際上是把求根問題轉(zhuǎn)化為求( )yxyg x 圖 5.4 迭代過程(58)就是在x軸取初始近似值x0,過x0作y軸的平行線交曲線y=g(x)于p0,p0的橫坐標(biāo)為x0,縱坐標(biāo)為g(x0)(g(x0)=x1),也即 p0(x0,x1) 再在x軸上取x1作為新的近似值,過x1作y軸的平行線交曲線y=g(x)于p1,p1的橫坐標(biāo)為x1,縱坐標(biāo)為 g(x1)(g(x1)=x2),也即 p1(x1,x2) 而這相當(dāng)于過p0引平行于x軸的直線交y=x于 Q1(x1,x2) 再過Q1引平行于y軸的直線交曲線y=g(x)于 p1(x1,x2)

11、仿此可得到點列 p0(x0,x1),p1(x1,x2),p2(x2,x3), 若limlimkkkkppxx則迭代法收斂,見圖5.4(a);否則迭代法發(fā)散,見圖5.4(b)。 必須說明兩點: 要驗證g(x)是否滿足李氏條件一般比較困難,若g(x)可微,可用充分條件來代替。這里q1是非常重要的條件,否則不能保證迭代收斂。 對于收斂的迭代過程,誤差估計式(511)說明迭代值的偏差xk-xk-1相當(dāng)小,就能保證迭代誤差x-xk足夠小。因此在具體計算時常常用條件 xk-x k-1 (515) 來控制迭代過程結(jié)束。 ( )1g xq 迭代法的突出優(yōu)點是算法的邏輯結(jié)構(gòu)簡單,且在計算時,中間結(jié)果若有擾動,仍

12、不會影響計算結(jié)果。其計算步驟為: (1)確定方程f(x)=0的等價形式x=g(x),為確保迭代過程的收斂,要求g(x)滿足李普希茨條件(或g(x)q1); (2)選取初始值x0,按公式 x k+1=g(xk), k=0,1,2, 進行迭代; (3)若x k+1-xk,則停止計算,xx k+1。 例2 求方程 x=e-x 在x=0.5附近的一個根。按五位小數(shù)計算,計算結(jié)果 的精度要求為=10-3。 解 過x=0.5以步長h=0.1計算 f(x)=x-e-x 由于 f(0.5)0,f(0.6)0 故所求的根在區(qū)間(0.5,0.6)內(nèi),且在x=0.5附近()0.61xe 圖 5.5 表表 53 因此

13、用迭代公式 由表可見1xkkex 10 xxxxe為方程 最后,我們給出一個說明,在將方程(51)化為等價形式(57)時,g(x)的形式是多種多樣的,選取不當(dāng),迭代公式(58)就不會收斂。最一般的形式可以寫成 x=x+(x)f(x) (516) 這里(x)為任意一個正(或負)的函數(shù)。于是 g(x)=x+(x)f(x) (517) 這樣可根據(jù)式(517)選取(x),使得迭代公式 (58)滿足收斂條件 ( )11( )( )g xqa xfx 特別當(dāng)取 (518) 時,由式(516)構(gòu)造的迭代公式為下面要介紹的切線迭代公式;當(dāng)取11( ),1,2,( )()kkxxa xkf xf x (519)

14、 時,可得到弦截迭代公式。 3 切線法切線法(牛頓法牛頓法) 切線法是求解方程(51)的一種重要迭代方法。如圖5.6,曲線y=f(x)與x軸的交點x就是方程(51)的根。 圖圖 5.6 與x軸的交點為x k+1,其方程為1()()()0()()()kkkkkkkyf xfxxxf xfxxx 點xk+1滿足該切線方程,即可得到切線迭代公式(或牛頓迭代公式)1(),0,1,2,()kkkkf xxxkfx(520) 切線法是非線性方程線性化的方法。其計算步驟為: 給出初始近似根x0及精度。 計算 若x1-x0,則轉(zhuǎn)向;否則x1x0,轉(zhuǎn)向。 輸出滿足精度的根x1,結(jié)束。 切線法的計算框圖見圖5.7

15、。 0010()()f xxxfx圖 5.7 例3 用切線法求方程 xex-1=0 的根(取五位小數(shù)計算)。 取x0=0.5,迭代結(jié)果如表54所示。 由于11kxkkkkxexxxxxe 表表 54 切線迭代公式(520)對應(yīng)著(51)的等價方程( )( )( )f xxxg xfx由于 2( )( )( )( )f x fxg xfx(521) 若 是方程(51)的一個單實根,即x()0,()0()0f xfxg x 所以,在點 附近切線法收斂,而且收斂速度比較快。 根據(jù)式(521)易得切線迭代公式的收斂條件為 x2( )( )( )1( )f x fxg xfx4 弦截法弦截法 切線法迭代

16、簡單,收斂速度也較快,但就是需要計算導(dǎo)數(shù)f(x),有時使用會帶來麻煩。這一節(jié)介紹的弦截法就避免了切線法的不足。 點xk+1滿足該弦的方程,即有11()()()()kkkkkkf xf xyf xxxxx111()()0()()kkkkkkkf xf xf xxxxx從而可求得弦截迭代公式 111()()()()kkkkkkkf xxxxxf xf x(523) 圖 5.8 表 55 例4 用弦截法解方程 xex-1=0 解 取x0=0.5,x1=0.6作為初始近似根,令 f(x)=x-e-x=0 利用公式(523)得到弦截迭代公式為1111()()()kkkxkkkkkxxkkxexxxxxx

17、xe計算結(jié)果見表55。 與切線法的計算結(jié)果比較,可以看出弦截法的收斂速度也是比較快的。 5 加速迭代法加速迭代法 已知方程(51)的近似根xk,按迭代公式(58)可求得x k+1?，F(xiàn)考慮把x k+1作為過渡值,記為1()kkxg x(524) 11kkkxmxnx(525) 還是設(shè)x為方程(51)的一個實根,即 由式(524)和(526)得到 ()xg x11()()( )()kkkkxxg xg xxxgxx也即 11()1111,11kkkkkxxa xxaxxxaaamnxaa整理得到 于是,只要取 (527) (528) (529) 這樣可得到加速迭代公式 111()111kkkkkx

18、g xaxxxaa(530) 例5 用加速迭代公式求方程 x=e-x 在x=0.5附近的一個根。 解 因為在x=0.5附近 g(x)=-e-x g(0.5)=-e-0.5-0.6 故加速迭代公式的具體形式為11110.61.61.6kxkkkkxexxx表 56 圖 5.9 與例2比較,同一例用一般迭代法要迭代十次才能得到滿足精度=10-3的結(jié)果,而這里僅迭代三次便可達到=10-5的高精度結(jié)果。這種加速過程取得的效果極為顯著。 為了避免計算導(dǎo)數(shù)ag(x),下面介紹埃特金(Aitken)迭代方法。它也是一種加速迭代法。 11111()()()()kkkkkxg xxxg xg xa xx(531) 將式(527)與式(531)聯(lián)立消去a得到1