數(shù)值分析 第4章解非線性方程迭代法

1、第第4 4章章 非線性方程求根非線性方程求根 本章討論求非線性方程 (x)=0 (4.1)的根的問題. 其中(x)是高次多項式函數(shù)或超越函數(shù).如 (x)=3x5-2x4+8x2-7x+1 (x)=e2x+1-xln(sinx)-2等等.1 二二 分分 法法 設(x)在區(qū)間a,b上連續(xù)且(a)(b)0,根據(jù)連續(xù)函數(shù)的介值定理,區(qū)間a,b上必有方程(x)=0的根,稱a,b為方程(x)=0的有根區(qū)間. ,得到新的有根區(qū)間a1,b1, 設(x)在區(qū)間a,b上連續(xù)且(a)(b)0 .0abyxy=(x) 記a0=a,b0=b,計算,2000bax若|(x0)| ,則取x0 ;否則,若(a0)(x0)0,

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

3、 . 在計算過程中,若出現(xiàn)|(xk)|1,或bk-ak2 .則可取xk作為方程(x)=0的近似根,終止運算.例例1 用二分法求x3+4x-10=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, .x9=1

4、.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ū)間兩端點函數(shù)值符號相反，二分法運算簡便、可靠、易于在計算機上實現(xiàn)。但是，若方程(x)=0在區(qū)間a，b上根多于1個時，也只能求出其中的一個根。另外，若方程(

5、x)=0在區(qū)間a，b有重根時，也未必滿足(a)(b)0. 而且由于二分法收斂的速度不是很快,一般不單獨使用,而多用于為其他方法提供一個比較好的初始近似值. 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 , ,建立迭代格式3123,0,1,2.kkxxk如果取初值x0=1.9 ,計算得kxkkxk0123451.91.894536471.893521141.893332331.893297221.893290696789101.893289471.893289251.893289211.893289201.89328920 由計算結(jié)果有，x10=x9，因此可取x10=1.89328920. 定義定義4.14.1 設(x)為定義在區(qū)

7、間I I上的函數(shù), 且對任何xI I,均有(x)I I,則稱(x)為I I到自身上的映射到自身上的映射. 方程也可改寫成x=(x3-3)/2, 建立迭代格式 xk+1=(x3k-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 簡單迭代法的收斂條件簡單迭代法的收斂條件 定義定義4.24.2 設(x)為I I到自身上的映射,且存在0L1,使對任何x1,x2I,I,有|(x2)-(x1)| L|x2-x1|,則稱(x)為I I上的壓縮映射壓縮映射, L稱為Lip

8、schitzLipschitz常數(shù)常數(shù). 若(x)為I上的壓縮映射,則(x)在I上連續(xù). 定理定理4.24.2 若(x)為I到自身上的映射,且(x)C1(I), |(x)| L1,則(x)為I上的壓縮映射. 證證 對任意x1,x2I,有 |(x2)-(x1)|=|()|x2-x1| L|x2-x1| 定義定義4.34.3 若(x)為I到自身上的映射,且I I滿足,= (),則稱為(x)的不動點不動點. . 定理定理4.34.3 若(x)為I上的壓縮映射, 則(x)在I I上存在唯一的一個不動點,且對任何x0I,由迭代格式 xk+1=(xk) , k=0,1,2,產(chǎn)生的序列xk收斂于(x)的不動

9、點.定理定理4.1 證證 不妨設I=a,b,作函數(shù)(x)=(x)-x,由于xI時, (x)I,則(a)=(a)-a0,(b)=(b)-b0,由(x)的連續(xù)性, 必存在I, 使()=()-=0,即=(),就是(x)的不動點. 若,I均為(x)的不動點,則有 |-|=|()-()| L|-|-|所以只能=,即(x)在I上僅有一個不動點. 對任意x0I,有x1=(x0)I,遞推得xkI,設是(x)的不動點,則 |xk+1-|=|(xk)-()| L|xk-| L2|xk-1-| Lk+1|x0-|所以xk. 若=(),而在I=-,+上(x)滿足 |(x)-()| L|x-|這里L1為Lipschit

10、z常數(shù),則當x0-,+時,有 (1) 由迭代xk+1=(xk)產(chǎn)生的迭代序列xkI; 推論推論 若(x)C1a,b,且滿足 1.a(x)b, xa,b; 2.|(x)| L0, 使對任何xI=-, +都有|(x)| L1. 2.3 簡單迭代法的誤差分析與收斂階簡單迭代法的誤差分析與收斂階 推論推論 若=(),(x)在附近具有一階連續(xù)導數(shù),且|()|0, 當x0I=-, +時, 有 (1) 由迭代xk+1=(xk)產(chǎn)生的迭代序列xkI;lim)2(kkx (3) 是I上(x)的唯一不動點. 定理定理4.54.5 若(x)為I上壓縮映射,則x0I,由迭代 xk+1=(xk) , k=0,1,2,

11、產(chǎn)生的迭代序列xk滿足: 證證 |xk+1-xk|=|(xk)-(xk-1)| L|xk-xk-1| |xk+1-|=|(xk)-()| L|xk-|11kkkxxLLx011xxLLxkk |xk+1-xk|=|(xk+1-)-(xk-)| |xk-|-|xk+1-|(1-L)|xk-|01111.111xxLLxxLLxxLxkkkkkk 由誤差估計式可見,對任一0,要使|xk-|, 只要LxxLkln)1 (ln01 求方程xex-1=0在0.5附近的根,精度要求=10-3. 解解 可以驗證方程xex-1=0在區(qū)間0.5,0.6內(nèi)僅有一個根.例例3 改寫方程為x=e-x ,建立迭代格式,

12、 2 , 1 , 0,1kexkxk 由于(x)=e-x ,在0.5,0.6上有|(x)|e-0.50.61則稱序列xk是p p階收斂的階收斂的, 稱p是收斂階收斂階,C是漸近誤差常漸近誤差常數(shù)數(shù). p=1稱為線性收斂線性收斂;p1稱超線性收斂超線性收斂;p=2稱平方收斂平方收斂. 設(x)充分光滑, 由于 |ek+1|=|xk+1-|=|(xk)-()|=|(k)|ek|所以,當()0時,有0| )(|)(limlim1kkkkkee于是此時,迭代法是m階收斂的.所以,當()0時,簡單迭代法只具有線性收斂. 設()=()=(m-1)()=0,但(m)()0, 由于 |ek+1|=|xk+1-

13、|=|(xk)-()|mkkmem)(!1)(0| )(|!1)(!1limlim)()(1mkmkmkkkmmee所以mkkmmkmkkkxmxmxxx)(!1)()!1(1)(21)()()()(1)1(2 下面介紹AitkenAitken加速算法加速算法，此方法可對線性收斂的簡單迭代法起到加速作用，而且可應用于其它數(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 解得 kkkkkkxxxxxx12212

14、2kkkkkkxxxxxx12212)(則,序列注意, 如果第k步發(fā)生zk-2yk+xk=0, 就終止計算, 取xk .如果記 kkkkkkkxxxxxxx12212)( kx 要比序列x k更快地收斂于 , 可構(gòu)造如下的Aitken加速算法:, 2 , 1 , 0,2)(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.5

15、71091.599711.571380.02920.028910.028620.028330121.57079631.585472581.585471800.014676280.00000078 NewtonNewton迭代法迭代法是求方程根的重要方法之一,其最大優(yōu)點是在方程的單根附近具有平方收斂,而且Newton迭代法還可用來求方程的重根、復根及非線性方程組.3 Newton 迭代法迭代法 3.1 Newton迭代公式迭代公式 設(x)在有根區(qū)間a,b上二階連續(xù)可微, x0是根的某個近似值, 因為200000)(2)()()()(xxfxxxfxfxf 取(x)(x0)+(x0)(x-x0)

16、,方程(x)=0近似為 (x0)+(x0)(x-x0)=0若(x0)0, 其解為)()(0001xfxfxx得到根的新的近似值x1 ,一般地,在xk附近線性化方程為 (xk)+(xk)(x-xk)=0設(xk)0, 其解為)4 . 4(, 2 , 1 , 0,)()(1kxfxfxxkkkk迭代格式(4.4)稱為 NewtonNewton迭代法迭代法. . xyox0y=(x)x1x2直線 y=(x0)+(x0)(x-x0)就是 y-(x0)=(x0)(x-x0)Newton迭代法也叫切線法切線法. Newton迭代法相當于取迭代函數(shù)3.2 Newton迭代法的收斂性迭代法的收斂性)()()(

17、xfxfxx的簡單迭代法. 因為222)()()()()()()(1)(xfxfxfxfxfxfxfx 如果是(x)=0的單根, 即()=0, 但()0, 則有()=0, 從而可知Newton迭代法在根附近是收斂的.因為2)(2)()()()(kkkkxxfxxxfxfxf 所以2)(2)()()()(kkkkkxfxxfxff 于是有2)()(2)()()(kkkkkkxxffxfxfx 21)()(2)(kkkkxxffx 21)(limkkkxx)(2)(limkkkxff )(2)(ff 可見, Newton迭代法至少是平方收斂的. 若記其中(212mMC M2=max|(x)|,m1

18、=min|(x)|. 則有 |xk+1-| C|xk-|2因此 C|xk+1-| (C|xk-|)2 (C|xk-1-|)4 )1(20|)|(kxC可見,當C|x0-|1, 即|x0-|1/2max|(x)|時,簡化Newton迭代法對x0I收斂.通常取M=(x0). 簡化Newton迭代法一般只具有線性收斂. 2. 2.割線法割線法 因為, 2 , 1 , 0,)()()(11kxxxfxfxfkkkkkoxyy=(x)x0 x1x2x3 為了簡化計算(xk),采用迭代格式, 3 , 2 , 1,)()()()(111kxxxfxfxfxxkkkkkkk稱為割線割線法法. . 若(x)在根

19、附近二次連續(xù)可微,且()0,可以證明割線法是收斂的,且有)(2)(lim11ffeeekkkk 割線法收斂的階為.618. 1251p 3. 3.計算重根的計算重根的NewtonNewton迭代法迭代法 稱是方程(x)=0的m重根,是指(x)=(x-)m h(x),其中h(x)在x=處連續(xù)且h()0, 若h(x)在處充分可微,則 ()=()=(m-1)()=0,(m)()0由于mmxhxxf11)()()(可見,恰是方程0)(1mxf 的單根.應用Newton迭代法可得:)()(1)(1111kmkmkkkxfxfmxfxx, 2 , 1 , 0,)()(kxfxfmxkkk稱之為帶參數(shù)帶參數(shù)m m的的NewtonNewton迭代法迭代法, 它是求方程(x)=0的m重根的具有平方收斂的迭代法. 再看函數(shù):( )() ( )( )() ( )( )( ) () ( )f xxh xu xxh xf xmh xxh x可見,恰是方程u(x)=0的單根, 應用Newton迭代法有)()(1kkkkxuxuxx這是求方程(x)=0