解非線性方程的迭代法.ppt

第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ū)間.,得到新的有根區(qū)間a1,b1,設(shè)(x)在區(qū)間a,b上連續(xù)且(a)(b)0 .,0,a,b,y,x,y=(x),記a0=a,b0=b,計(jì)算,若|(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ì)算,若|(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.,此時(shí),再計(jì)算,或者有|(xk)| ,或者有,可見,k趨向無(wú)窮大時(shí),xk收斂于 .,而且,若要|xk-| ,只要,此時(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ì)誤差.,解 這里(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作為方程根的近似值,且有,只需k5ln210-115.61.即需取x16.,如果取精度=10-5,則要使,二分法要求函數(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è)比較好的初始近似值.,2.1 簡(jiǎn)單迭代法的一般形式,2 簡(jiǎn) 單 迭 代 法,首先把方程(x)=0改寫成等價(jià)(同解)形式 x=(x) (4.2),得到迭代序列xk , 如果xk ,則有=(), 即是方程(x)=0的根.,取一個(gè)合適的初始值x0,然后作迭代 xk+1=(xk) , k=0,1,2, (4.3),這種求方程根的方法稱為簡(jiǎn)單迭代法,或逐次逼近法.其中(x) 稱為迭代函數(shù) ,式(4.3)稱為迭代格式. 若迭代序列xk 收斂 , 則稱簡(jiǎn)單迭代法是收斂的.,解 改寫原方程為等價(jià)方程,求方程x3-2x-3=0在1,2內(nèi)的根.,例2,建立迭代格式,如果取初值x0=1.9 ,計(jì)算得,由計(jì)算結(jié)果有，x10=x9，因此可取x10=1.89328920.,定義4.1 設(shè)(x)為定義在區(qū)間I上的函數(shù), 且對(duì)任何xI,均有(x)I,則稱(x)為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 簡(jiǎn)單迭代法的收斂條件,定義4.2 設(shè)(x)為I到自身上的映射,且存在0L1,使對(duì)任何x1,x2I,有|(x2)-(x1)| L|x2-x1|,則稱(x)為I上的壓縮映射, L稱為L(zhǎng)ipschitz常數(shù).,若(x)為I上的壓縮映射,則(x)在I上連續(xù).,定理4.2 若(x)為I到自身上的映射,且(x)C1(I), |(x)| L1,則(x)為I上的壓縮映射.,證 對(duì)任意x1,x2I,有 |(x2)-(x1)|=|()|x2-x1| L|x2-x1|,定義4.3 若(x)為I到自身上的映射,且I滿足,= (),則稱為(x)的不動(dòng)點(diǎn).,定理4.3 若(x)為I上的壓縮映射, 則(x)在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,證 不妨設(shè)I=a,b,作函數(shù)(x)=(x)-x,由于xI時(shí), (x)I,則(a)=(a)-a0,(b)=(b)-b0,由(x)的連續(xù)性, 必存在I, 使()=()-=0,即=(),就是(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.,若=(),而在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)| L1, xa,b. 則迭代格式xk+1=(xk),k=0,1,2,x0a,b都收斂于方 程x=(x)在區(qū)間a,b的唯一根.,(3) 是I上(x)的唯一不動(dòng)點(diǎn).,定理4.4,實(shí)際上,由連續(xù)性知,存在0, 使對(duì)任何xI=-, +都有|(x)| L1.,2.3 簡(jiǎn)單迭代法的誤差分析與收斂階,推論 若=(),(x)在附近具有一階連續(xù)導(dǎo)數(shù),且 |()|0, 當(dāng)x0I=-, +時(shí), 有 (1) 由迭代xk+1=(xk)產(chǎn)生的迭代序列xkI;,(3) 是I上(x)的唯一不動(dòng)點(diǎn).,定理4.5 若(x)為I上壓縮映射,則x0I,由迭代 xk+1=(xk) , k=0,1,2, 產(chǎn)生的迭代序列xk滿足:,證 |xk+1-xk|=|(xk)-(xk-1)| L|xk-xk-1| |xk+1-|=|(xk)-()| L|xk-|,|xk+1-xk|=|(xk+1-)-(xk-)| |xk-|-|xk+1-|(1-L)|xk-|,由誤差估計(jì)式可見,對(duì)任一0,要使|xk-|, 只要,求方程xex-1=0在0.5附近的根,精度要求=10-3.,解 可以驗(yàn)證方程xex-1=0在區(qū)間0.5,0.6內(nèi)僅有一個(gè)根.,例3,改寫方程為x=e-x ,建立迭代格式,由于(x)=e-x ,在0.5,0.6上有|(x)|e-0.50.61.所以迭代法收斂.,取初值x0=0.5,計(jì)算得,所以,取近似根x10=0.56691滿足精度要求.,如果精度要求為=10-5, 則由,可知,需要迭代20次.,定義4.4 設(shè)迭代序列xk收斂于,記誤差ek=xk-,如果存在正實(shí)數(shù)p和非零常數(shù)C, 使得,或,|xk+1-|C|xk-|p , k1,則稱序列xk是p階收斂的, 稱p是收斂階,C是漸近誤差常數(shù).,p=1稱為線性收斂;p1稱超線性收斂;p=2稱平方收斂.,設(shè)(x)充分光滑, 由于,|ek+1|=|xk+1-|=|(xk)-()|=|(k)|ek|,所以,當(dāng)()0時(shí),有,于是,此時(shí),迭代法是m階收斂的.,所以,當(dāng)()0時(shí),簡(jiǎn)單迭代法只具有線性收斂.,設(shè)()=()=(m-1)()=0,但(m)()0, 由于,|ek+1|=|xk+1-|=|(xk)-()|,所以,下面介紹Aitken加速算法，此方法可對(duì)線性收斂的簡(jiǎn)單迭代法起到加速作用，而且可應(yīng)用于其它數(shù)值方法中。,假設(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, 就終止計(jì)算, 取xk .,如果記,要比序列x k更快地收斂于 ,可構(gòu)造如下的Aitken加速算法:,例4,分別用簡(jiǎn)單迭代法和Aitken加速算法求方程 x=1.6+0.99cosx在x0=/2附近的根.(=1.585471802),取x0= /2,計(jì)算結(jié)果如下,Newton迭代法是求方程根的重要方法之一,其最大優(yōu)點(diǎn)是在方程的單根附近具有平方收斂,而且Newton迭代法還可用來(lái)求方程的重根、復(fù)根及非線性方程組.,3 Newton 迭代法,3.1 Newton迭代公式,設(shè)(x)在有根區(qū)間a,b上二階連續(xù)可微, x0是根的某個(gè)近似值, 因?yàn)?取(x)(x0)+(x0)(x-x0),方程(x)=0近似為 (x0)+(x0)(x-x0)=0,若(x0)0, 其解為,得到根的新的近似值x1 ,一般地,在xk附近線性化方程為,(xk)+(xk)(x-xk)=0,設(shè)(xk)0, 其解為,迭代格式(4.4)稱為 Newton 迭代法.,x,y,o,x0,y=(x),x1,x2,直線 y=(x0)+(x0)(x-x0),就是 y-(x0)=(x0)(x-x0),Newton迭代法也叫切線法.,Newton迭代法相當(dāng)于取迭代函數(shù),3.2 Newton迭代法的收斂性,的簡(jiǎn)單迭代法. 因?yàn)?如果是(x)=0的單根, 即()=0, 但()0, 則有()=0, 從而可知Newton迭代法在根附近是收斂的.,因?yàn)?所以,于是有,可見, Newton迭代法至少是平方收斂的.,若記,M2=max|(x)|,m1=min|(x)|.,則有,|xk+1-| C|xk-|2,因此,C|xk+1-| (C|xk-|)2, (C|xk-1-|)4,可見,當(dāng)C|x0-|1, 即|x0-|2m1/M2 時(shí),Newton迭代法是收斂的.,設(shè)(x)在單根附近具有二階連續(xù)導(dǎo)數(shù),且 ，則對(duì)充分接近的初值x0,Newton迭代法產(chǎn)生的序列xk收斂于, 并且,定理4.6,取x0=0.5,計(jì)算結(jié)果如下:,例5 用Newton迭代法求方程xex-1=0在0.5附近的根,精度要求=10-5.,解 Newton迭代格式為,從結(jié)果可見 ,Newton迭代法迭代3次已獲得精確到小數(shù)點(diǎn)后五位的近似解,迭代4次已獲得精確到小數(shù)點(diǎn)后八位的近似解.與例3比較可見Newton迭代法收斂的確實(shí)快.,3.3 Newton迭代法的變形,1. 簡(jiǎn)化Newton迭代法,為了簡(jiǎn)化計(jì)算(xk),采用迭代格式,稱為簡(jiǎn)化Newton迭代法.,o,x,y,y=(x),x0,x1,x2,x3,在區(qū)間I=-,+上,取M與(x)同號(hào),且|M|1/2max|(x)|,時(shí),簡(jiǎn)化Newton迭代法對(duì)x0I收斂.通常取M=(x0).,簡(jiǎn)化Newton迭代法一般只具有線性收斂.,2.割線法,因?yàn)?o,x,y,y=(x),x0,x1,x2,x3,為了簡(jiǎn)化計(jì)算(xk),采用迭代格式,稱為割線法.,若(x)在根附近二次連續(xù)可微,且()0,可以證明割線法是收斂的,且有,割線法收斂的階為,3.計(jì)算重根的Newton迭代法,稱是方程(x)=0的m重根,是指(x)=(x-)m h(x),其中h(x)在x=處連續(xù)且h()0,若h(x)在處充分可微,則 ()=()=(m-1)()=0,(m)()0,由于,可見,恰是方程,的單根.應(yīng)用Newton迭代法可得:,稱之為帶參數(shù)m的Newton迭代法, 它是求方程(x)=0的m重根的具有平方收斂的迭代法.,再看函數(shù):,可見,恰是方程u(x)=0的單根, 應(yīng)用Newton迭代法有,這是求方程(x)=0重根的具有平方收斂的迭代法,而且不需知道根的重?cái)?shù).,例6 利用Newton迭代法求方程 (x)=x4-8.6x3-35.51x2+464.4x-998.46=0的正實(shí)根.,o,x,y,2,4,6,8,10,y=f(x),解 y=(x)的圖形為,可見,方程在x=4附近有一個(gè)重根,在x=7附近有一單根.,利用Newton迭代法,求方程的單根,取初值x0=7, 精度 =10-6, 計(jì)算可得: x4=7.34846923, x5=7.348469229, |x5-x4|=0.000000001,可見, 迭代5次就得到滿足精度的解x5=7.348469229,利用求重根的New