第四章解非線性方程的迭代法

1、.,第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 .,0,a,b,y,x,y=(x),記a0=a,b0=b,計算,若|(x0)|0,取a1=x0,b1=b0,而且有根區(qū)間a1,b1長度是

2、有根區(qū)間a0,b0長度的一半,x0,再對有根區(qū)間a1,b1重復上面運算, 即: 計算,若|(x1)|0, 取a2=x1 ,b2=b1,得到新的有根區(qū)間a2,b2.,x1,而且有根區(qū)間a2,b2長度是有根區(qū)間a1,b1長度的一半.一直進行下去,直到求出有根區(qū)間ak,bk.,.,此時,再計算,或者有|(xk)| ,或者有,可見,k趨向無窮大時,xk收斂于 .,而且,若要|xk-| ,只要,此時可取近似根xk .,在計算過程中,若出現(xiàn)|(xk)|1,或bk-ak2 .則可取xk作為方程(x)=0的近似根,終止運算.,例1,用二分法求x3+4x-10=0在區(qū)間1,2內根的近似值,并估計誤差.,.,解

3、這里(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.254882813,得有根區(qū)間1.254882813,1.255859375,x10=1.255371094, (x10)=-0.000105285,取x10=1.255371094作為方程

4、根的近似值,且有,.,只需k5ln210-115.61.即需取x16.,如果取精度=10-5,則要使,二分法要求函數(shù)在區(qū)間a，b上連續(xù)，且在區(qū)間兩端點函數(shù)值符號相反，二分法運算簡便、可靠、易于在計算機上實現(xiàn)。但是，若方程(x)=0在區(qū)間a，b上根多于1個時，也只能求出其中的一個根。另外，若方程(x)=0在區(qū)間a，b有重根時，也未必滿足(a)(b)0. 而且由于二分法收斂的速度不是很快,一般不單獨使用,而多用于為其他方法提供一個比較好的初始近似值.,.,2.1 簡單迭代法的一般形式,2 簡 單 迭 代 法,首先把方程(x)=0改寫成等價(同解)形式 x=(x) (4.2),得到迭代序列xk ,

5、如果xk ,則有=(), 即是方程(x)=0的根.,取一個合適的初始值x0,然后作迭代 xk+1=(xk) , k=0,1,2, (4.3),這種求方程根的方法稱為簡單迭代法,或逐次逼近法.其中(x) 稱為迭代函數(shù) ,式(4.3)稱為迭代格式. 若迭代序列xk 收斂 , 則稱簡單迭代法是收斂的.,.,解 改寫原方程為等價方程,求方程x3-2x-3=0在1,2內的根.,例2,建立迭代格式,如果取初值x0=1.9 ,計算得,.,由計算結果有，x10=x9，因此可取x10=1.89328920.,定義4.1 設(x)為定義在區(qū)間I上的函數(shù), 且對任何xI,均有(x)I,則稱(x)為I到自身上的映射.

6、,方程也可改寫成x=(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 簡單迭代法的收斂條件,定義4.2 設(x)為I到自身上的映射,且存在0L1,使對任何x1,x2I,有|(x2)-(x1)| L|x2-x1|,則稱(x)為I上的壓縮映射, L稱為Lipschitz常數(shù).,.,若(x)為I上的壓縮映射,則(x)在I上連續(xù).,定理4.2 若(x)為I到自身上的映射,且(x)C1(I), |(x)| L1,

7、則(x)為I上的壓縮映射.,證 對任意x1,x2I,有 |(x2)-(x1)|=|()|x2-x1| L|x2-x1|,定義4.3 若(x)為I到自身上的映射,且I滿足,= (),則稱為(x)的不動點.,定理4.3 若(x)為I上的壓縮映射, 則(x)在I上存 在唯一的一個不動點,且對任何x0I,由迭代格式 xk+1=(xk) , k=0,1,2, 產生的序列xk收斂于(x)的不動點.,定理4.1,.,證 不妨設I=a,b,作函數(shù)(x)=(x)-x,由于xI時, (x)I,則(a)=(a)-a0,(b)=(b)-b0,由(x)的連續(xù)性, 必存在I, 使()=()-=0,即=(),就是(x)的不

8、動點.,若,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為Lipschitz常數(shù),則當x0-,+時,有 (1) 由迭代xk+1=(xk)產生的迭代序列xkI;,推論 若(x)C1a,b,且滿足 1.a(x)b, xa,b; 2.|(x)| L1, xa,b. 則迭代格式xk+1

9、=(xk),k=0,1,2,x0a,b都收斂于方 程x=(x)在區(qū)間a,b的唯一根.,(3) 是I上(x)的唯一不動點.,定理4.4,.,實際上,由連續(xù)性知,存在0, 使對任何xI=-, +都有|(x)| L1.,2.3 簡單迭代法的誤差分析與 收斂階,推論 若=(),(x)在附近具有一階連續(xù)導數(shù),且 |()|0, 當x0I=-, +時, 有 (1) 由迭代xk+1=(xk)產生的迭代序列xkI;,(3) 是I上(x)的唯一不動點.,定理4.5 若(x)為I上壓縮映射,則x0I,由迭代 xk+1=(xk) , k=0,1,2, 產生的迭代序列xk滿足:,.,證 |xk+1-xk|=|(xk)-

10、(xk-1)| L|xk-xk-1| |xk+1-|=|(xk)-()| L|xk-|,|xk+1-xk|=|(xk+1-)-(xk-)| |xk-|-|xk+1-|(1-L)|xk-|,由誤差估計式可見,對任一0,要使|xk-|, 只要,.,求方程xex-1=0在0.5附近的根,精度要求=10-3.,解 可以驗證方程xex-1=0在區(qū)間0.5,0.6內僅有一個根.,例3,改寫方程為x=e-x ,建立迭代格式,由于(x)=e-x ,在0.5,0.6上有|(x)|e-0.50.61.所以迭代法收斂.,取初值x0=0.5,計算得,.,所以,取近似根x10=0.56691滿足精度要求.,如果精度要求

11、為=10-5, 則由,可知,需要迭代20次.,.,定義4.4 設迭代序列xk收斂于,記誤差ek=xk-,如果存在正實數(shù)p和非零常數(shù)C, 使得,或,|xk+1-|C|xk-|p , k1,則稱序列xk是p階收斂的, 稱p是收斂階,C是漸近誤差常數(shù).,p=1稱為線性收斂;p1稱超線性收斂;p=2稱平方收斂.,設(x)充分光滑, 由于,|ek+1|=|xk+1-|=|(xk)-()|=|(k)|ek|,所以,當()0時,有,.,于是,此時,迭代法是m階收斂的.,所以,當()0時,簡單迭代法只具有線性收斂.,設()=()=(m-1)()=0,但(m)()0, 由于,|ek+1|=|xk+1-|=|(x

12、k)-()|,所以,下面介紹Aitken加速算法，此方法可對線性收斂的簡單迭代法起到加速作用，而且可應用于其它數(shù)值方法中。,.,假設 (1)(2)，則有,由于,xk+1-=(1)(xk-),xk+2-=(2)(xk+1-),即,(xk+1-)2(xk-)(xk+2-),xk+12-2xk+1+2xkxk+2-(xk+xk+2)+2,解得,.,則,序列,注意, 如果第k步發(fā)生zk-2yk+xk=0, 就終止計算, 取xk .,如果記,要比序列x k更快地收斂于 ,可構造如下的Aitken加速算法:,例4,分別用簡單迭代法和Aitken加速算法求方程 x=1.6+0.99cosx在x0=/2附近的

13、根.(=1.585471802),.,取x0= /2,計算結果如下,.,Newton迭代法是求方程根的重要方法之一,其最大優(yōu)點是在方程的單根附近具有平方收斂,而且Newton迭代法還可用來求方程的重根、復根及非線性方程組.,3 Newton 迭代法,3.1 Newton迭代公式,設(x)在有根區(qū)間a,b上二階連續(xù)可微, x0是根的某個近似值, 因為,取(x)(x0)+(x0)(x-x0),方程(x)=0近似為 (x0)+(x0)(x-x0)=0,若(x0)0, 其解為,.,得到根的新的近似值x1 ,一般地,在xk附近線性化方程為,(xk)+(xk)(x-xk)=0,設(xk)0, 其解為,迭代

14、格式(4.4)稱為 Newton 迭代法.,x,y,o,x0,y=(x),x1,x2,直線 y=(x0)+(x0)(x-x0),就是 y-(x0)=(x0)(x-x0),Newton迭代法也叫切線法.,.,Newton迭代法相當于取迭代函數(shù),3.2 Newton迭代法的收斂性,的簡單迭代法. 因為,如果是(x)=0的單根, 即()=0, 但()0, 則有()=0, 從而可知Newton迭代法在根附近是收斂的.,因為,所以,.,于是有,可見, Newton迭代法至少是平方收斂的.,若記,M2=max|(x)|,m1=min|(x)|.,則有,|xk+1-| C|xk-|2,因此,C|xk+1-|

15、 (C|xk-|)2, (C|xk-1-|)4,可見,當C|x0-|1, 即|x0-|2m1/M2 時,Newton迭代法是收斂的.,.,設(x)在單根附近具有二階連續(xù)導數(shù), 則對充分接近的初值x0,Newton迭代法產生的序列xk收斂于, 并且,定理4.6,取x0=0.5,計算結果如下:,例5 用Newton迭代法求方程xex-1=0在0.5附近的根,精度要求=10-5.,解 Newton迭代格式為,.,從結果可見 ,Newton迭代法迭代3次已獲得精確到小數(shù)點后五位的近似解,迭代4次已獲得精確到小數(shù)點后八位的近似解.與例3比較可見Newton迭代法收斂的確實快.,3.3 Newton迭代法

16、的變形,1. 簡化Newton迭代法,.,為了簡化計算(xk),采用迭代格式,稱為簡化Newton迭代法.,o,x,y,y=(x),x0,x1,x2,x3,在區(qū)間I=-,+上,取M與(x)同號,且M1/2max|(x)|,時,簡化Newton迭代法對x0I收斂.通常取M=(x0).,簡化Newton迭代法一般只具有線性收斂.,2.割線法,因為,.,o,x,y,y=(x),x0,x1,x2,x3,為了簡化計算(xk),采用迭代格式,稱為割線法.,若(x)在根附近二次連續(xù)可微,且()0,可以證明割線法是收斂的,且有,割線法收斂的階為,3.計算重根的Newton迭代法,.,稱是方程(x)=0的m重根

17、,是指(x)=(x-)m h(x),其中h(x)在x=處連續(xù)且h()0,若h(x)在處充分可微,則 ()=()=(m-1)()=0,(m)()0,由于,可見,恰是方程,的單根.應用Newton迭代法可得:,稱之為帶參數(shù)m的Newton迭代法, 它是求方程(x)=0m重根的具有平方收斂的迭代法.,再看函數(shù):,.,可見,恰是方程u(x)=0的單根, 應用Newton迭代法有,這是求方程(x)=0重根的具有平方收斂的迭代法,而且不需知道根的重數(shù).,例6 利用Newton迭代法求方程 (x)=x4-8.6x3-35.51x2+464.4x-998.46=0的正實根.,o,x,y,2,4,6,8,10,y=f(x),解 y=(x)的圖形為,可見,方程在x=4附近有一個重根,在x=7附近有一單根.,.,利用Newton迭代法,求方程的單根,取初值x0=7, 精度 =10-6, 計算可得: x4=7.34846923, x5=7.348469229, |x5-x4|=0.000000001,可見, 迭代5次就得到滿足精度的解x5=7.348469229,利用求重根的Newton