計(jì)算方法4方程求根的迭代法課件

第5章方程求根的數(shù)值解法§1二分法§2迭代法§3切線法(牛頓法)§4弦截法§5加速迭代法第5章方程求根的數(shù)值解法§1二分法§1二分法

我們已經(jīng)熟悉求解一元一次方程、一元二次方程以及某些特殊類型的高次代數(shù)方程或非線性方程的方法。這些方法都是代數(shù)解法,求出的根是方程的準(zhǔn)確根。但是在許多實(shí)際問(wèn)題中遇到的方程,例如代數(shù)方程

x3-x-1=0

或超越方程

§1二分法我們已經(jīng)熟悉求解一

等等,看上去形式簡(jiǎn)單,但卻不易求其準(zhǔn)確根。為此,只能求方程達(dá)到一定精度的近似根。方程的形式很多,我們主要討論一元非線性方程,也即

f(x)=0(5―1)等等,看上去形式簡(jiǎn)單,但卻不易求其準(zhǔn)

方程(5―1)可以有實(shí)根,也可以有復(fù)根或者重根等。本章主要討論它的實(shí)根的數(shù)值計(jì)算問(wèn)題。方程根的數(shù)值計(jì)算大致可分三個(gè)步驟進(jìn)行:(1)判定根的存在性。

(2)確定根的分布范圍,即將每一個(gè)根用區(qū)間隔離開來(lái)。

(3)根的精確化,即根據(jù)根的初始近似值按某種方法逐步精確化,直至滿足預(yù)先要求的精度為止。方程(5―1)可以有實(shí)根,也可以有復(fù)

設(shè)f(x)為定義在某區(qū)間上的連續(xù)函數(shù),方程(5―1)存在實(shí)根。雖然方程(5―1)的根的分布范圍一般比較復(fù)雜,但我們不難將函數(shù)f(x)的定義域分成若干個(gè)只含一個(gè)實(shí)根的區(qū)間。例如考慮方程

x2-2x-1=0

由圖5.1所示,該方程的一個(gè)負(fù)實(shí)根在-1和0之間,另一個(gè)正實(shí)根在2和3之間。設(shè)f(x)為定義在某區(qū)間上的連續(xù)函數(shù)

圖5.1圖5.1

這樣,我們總可以假設(shè)方程(5―1)(a,b)內(nèi)有且僅有一個(gè)單實(shí)根x*。由連續(xù)函數(shù)的介值定理知

f(a)·f(b)＜0

若數(shù)值b-a較小,那么我們可在(a,b)上任取一點(diǎn)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)有且僅有一個(gè)實(shí)根。于是可取某個(gè)端點(diǎn)或區(qū)間內(nèi)某一個(gè)點(diǎn)的值作為根的初始近似值。這樣,我們總可以假設(shè)方程(5―1)

設(shè)函數(shù)f(x)在區(qū)間［a,b］上單調(diào)連續(xù),且

f(a)·f(b)＜0

則方程(5―1)在區(qū)間(a,b)內(nèi)有且僅有一個(gè)實(shí)根x。下面在有根區(qū)間(a,b)內(nèi)介紹二分法的基本思想。計(jì)算f(a)與f(x0),若

f(a)·f(x0)＜0

則根x∈(a,x0),令

a1=a,b1=x0

否則x∈(x0,b),令

a1=x0,b1=b設(shè)函數(shù)f(x)在區(qū)間［a,b］上單調(diào)連圖5.2圖5.2

如此逐次往復(fù)下去,便得到一系列有根區(qū)間

(a,b),(a1,b1),(a2,b2),…,(ak,bk),…

其中這里a0=a,b0=b顯然有(5―2)

當(dāng)k→∞時(shí),區(qū)間(ak,bk)最終必收斂于一點(diǎn),該點(diǎn)就是所求方程(5―1)的根x。如此逐次往復(fù)下去,便得到一系列有根區(qū)間這里a0

我們把每次二分后的有根區(qū)間(ak,bk)的中點(diǎn)

作為所求根x的近似值,這樣獲得一個(gè)近似根的序列

x0,x1,x2,…,xk,…該序列必以根x為極限,即(5―3)故對(duì)于預(yù)先給定的精度ε,若有我們把每次二分后的有根區(qū)間(ak,bk)的中點(diǎn)作

則結(jié)果xk就是方程(5―1)滿足預(yù)給精度ε的近似根,也即由式(5―2)和(5―3)還可得到誤差估計(jì)式為(5―4)

對(duì)于確定的精度ε,從式(5―4)易求得需要二等分的次數(shù)k。二分法具有簡(jiǎn)單和易操作的優(yōu)點(diǎn)。其計(jì)算步驟如下,框圖如圖5.3所示。則結(jié)果xk就是方程(5―1)滿足預(yù)給1.計(jì)算步驟①輸入有根區(qū)間的端點(diǎn)a,b及預(yù)先給定的精度ε;②(a+b)/2x;③若f(a)f(x)＜0,則xb,轉(zhuǎn)向④;否則xa,轉(zhuǎn)向④。④若b-a＜ε,則輸出方程滿足精度的根x,結(jié)束;否則轉(zhuǎn)向②。1.計(jì)算步驟2.計(jì)算框圖例1求方程

f(x)=x3-x-1=0

在區(qū)間(1,1.5)內(nèi)的根。要求用四位小數(shù)計(jì)算,精確到10-2。解這里

a=1,b=1.5

取區(qū)間(1,1.5)的中點(diǎn)2.計(jì)算框圖

圖5.3圖5.3

由于f(1)＜0,f(1.25)＜0,則令

a1=1.25,b1=1.5

得到新的有根區(qū)間(1.25,1.5)由于f(1)＜0,f(1.25)＜0,則令

表5―1表5―1§2迭代法

迭代法的基本思想是:首先將方程(5―1)改寫成某種等價(jià)形式,由等價(jià)形式構(gòu)造相應(yīng)的迭代公式,然后選取方程的某個(gè)初始近似根x0,代入迭代公式反復(fù)校正根的近似值,直到滿足精度要求為止。迭代法是一種數(shù)值計(jì)算中重要的逐次逼近方法。例如,求方程

x3-x-1=0§2迭代法迭代法的基本思想

在x=1.5附近的一個(gè)根(用六位有效數(shù)字計(jì)算)。首先將原方程改寫成等價(jià)形式用初始近似根

x0=1.5代入式(5―5)的右端可得在x=1.5附近的一個(gè)根(用六位有效數(shù)字計(jì)算)。x1與x0相差較大,如果改用x1作為近似根代入式(5―5)的右端得x1與x0相差較大,如果改用x1作

表5―2表5―2

對(duì)于一般形式的方程(5―1),首先我們?cè)O(shè)法將其化為下列等價(jià)形式

x=g(x)(5―7)

然后按(5―7)構(gòu)造迭代公式從給定的初始近似根x0出發(fā),按迭代公式(5―8)可以得到一個(gè)數(shù)列

x0,x1,x2,…,xk,…

若這個(gè)數(shù)列｛xk｝有極限,則迭代公式(5―8)是收斂的。此時(shí)數(shù)列的極限對(duì)于一般形式的方程(5―1),首先我

就是原方程(5―1)的根。雖然迭代法的基本思想很簡(jiǎn)單,但效果并不總是令人滿意的。對(duì)于上例,若按方程寫成另一種等價(jià)形式

x=x3-1(5―9)

建立迭代公式

xk+1=x3k-1,k=0,1,2,…

仍取初始值x0=1.5,則迭代結(jié)果為

x1=2.375x2=12.3976

就是原方程(5―1)的根。

定理設(shè)方程x=g(x)在(a,b)內(nèi)有根x,g(x)滿足李普希茨(Lipschitz)條件:即對(duì)(a,b)內(nèi)任意的x1和x2都有q為某個(gè)確定的正數(shù),若q＜1,則方程在(a,b)內(nèi)有唯一的根;且迭代公式

xk+1=g(xk)

對(duì)任意初始近似值x0均收斂于方程的根x;還有誤差估計(jì)式(5―11)定理設(shè)方程x=g(x)在(a,b)

因?yàn)?，?duì)任意正整數(shù)p有

當(dāng)時(shí)，因?yàn)椋瑢?duì)任意正整數(shù)p有當(dāng)

證由已知條件知,x為方程x=g(x)的根,即x=g(x)設(shè)也是方程的根,即于是,由李普希茨條件得因?yàn)閝＜1,所以上式矛盾,故必有證由已知條件知,x為方程x=g(x)的根,

亦即方程在(a,b)內(nèi)有唯一的根。再考慮迭代公式

xk+1=g(xk),k=0,1,2,…

由李普希茨條件(5―12)由(5―12)可得(5―13)亦即方程在(a,b)內(nèi)有唯一的根。(5―12)

因?yàn)閝＜1,當(dāng)k→∞時(shí),qk→0,即有所以也就是對(duì)任意初始值x0迭代公式收斂。利用李普希茨條件因?yàn)閝＜1,當(dāng)k→∞時(shí),qk→0,即有所以

迭代法的幾何意義:把方程(5―1)求根的問(wèn)題改寫成(5―7)變?yōu)榍髷?shù)列｛xn｝的極限,實(shí)際上是把求根問(wèn)題轉(zhuǎn)化為求迭代法的幾何意義:把方程(5―1)求

圖5.4圖5.4

迭代過(guò)程(5―8)就是在x軸取初始近似值x0,過(guò)x0作y軸的平行線交曲線y=g(x)于p0,p0的橫坐標(biāo)為x0,縱坐標(biāo)為g(x0)(g(x0)=x1),也即

p0(x0,x1)

再在x軸上取x1作為新的近似值,過(guò)x1作y軸的平行線交曲線y=g(x)于p1,p1的橫坐標(biāo)為x1,縱坐標(biāo)為

g(x1)(g(x1)=x2),也即

p1(x1,x2)

而這相當(dāng)于過(guò)p0引平行于x軸的直線交y=x于

Q1(x1,x2)迭代過(guò)程(5―8)就是在x軸取初始近

再過(guò)Q1引平行于y軸的直線交曲線y=g(x)于

p1(x1,x2)

仿此可得到點(diǎn)列

p0(x0,x1),p1(x1,x2),p2(x2,x3),…

若則迭代法收斂,見(jiàn)圖5.4(a);否則迭代法發(fā)散,見(jiàn)圖5.4(b)。再過(guò)Q1引平行于y軸的直線交曲線y=g(x)于則迭代法必須說(shuō)明兩點(diǎn):①要驗(yàn)證g(x)是否滿足李氏條件一般比較困難,若g(x)可微,可用充分條件來(lái)代替。這里q＜1是非常重要的條件,否則不能保證迭代收斂。②對(duì)于收斂的迭代過(guò)程,誤差估計(jì)式(5―11)說(shuō)明迭代值的偏差｜xk-xk-1｜相當(dāng)小,就能保證迭代誤差｜x-xk｜足夠小。因此在具體計(jì)算時(shí)常常用條件｜xk-xk-1｜＜ε(5―15)

來(lái)控制迭代過(guò)程結(jié)束。必須說(shuō)明兩點(diǎn):

迭代法的突出優(yōu)點(diǎn)是算法的邏輯結(jié)構(gòu)簡(jiǎn)單,且在計(jì)算時(shí),中間結(jié)果若有擾動(dòng),仍不會(huì)影響計(jì)算結(jié)果。其計(jì)算步驟為:(1)確定方程f(x)=0的等價(jià)形式x=g(x),為確保迭代過(guò)程的收斂,要求g(x)滿足李普希茨條件(或｜g′(x)｜≤q＜1);(2)選取初始值x0,按公式

xk+1=g(xk),k=0,1,2,…

進(jìn)行迭代;(3)若｜xk+1-xk｜＜ε,則停止計(jì)算,x≈xk+1。迭代法的突出優(yōu)點(diǎn)是算法的邏輯結(jié)構(gòu)簡(jiǎn)單

例2求方程

x=e-x

在x=0.5附近的一個(gè)根。按五位小數(shù)計(jì)算,計(jì)算結(jié)果的精度要求為ε=10-3。解過(guò)x=0.5以步長(zhǎng)h=0.1計(jì)算

f(x)=x-e-x

由于

f(0.5)＜0,f(0.6)＞0

故所求的根在區(qū)間(0.5,0.6)內(nèi),且在x=0.5附近例2求方程

圖5.5圖5.5

表5―3表5―3

因此用迭代公式

由表可見(jiàn)為方程因此用迭代公式為方程

最后,我們給出一個(gè)說(shuō)明,在將方程(5―1)化為等價(jià)形式(5―7)時(shí),g(x)的形式是多種多樣的,選取不當(dāng),迭代公式(5―8)就不會(huì)收斂。最一般的形式可以寫成

x=x+α(x)f(x)(5―16)

這里α(x)為任意一個(gè)正(或負(fù))的函數(shù)。于是

g(x)=x+α(x)f(x)(5―17)

這樣可根據(jù)式(5―17)選取α(x),使得迭代公式

(5―8)滿足收斂條件特別當(dāng)取(5―18)最后,我們給出一個(gè)說(shuō)明,在將方程(5

時(shí),由式(5―16)構(gòu)造的迭代公式為下面要介紹的切線迭代公式;當(dāng)取(5―19)時(shí),可得到弦截迭代公式。時(shí),由式(5―16)構(gòu)造的迭代公式為§3切線法(牛頓法)

切線法是求解方程(5―1)的一種重要迭代方法。如圖5.6,曲線y=f(x)與x軸的交點(diǎn)x就是方程(5―1)的根。§3切線法(牛頓法)切線法

圖5.6圖5.6

與x軸的交點(diǎn)為xk+1,其方程為

點(diǎn)xk+1滿足該切線方程,即可得到切線迭代公式(或牛頓迭代公式)(5―20)與x軸的交點(diǎn)為xk+1,其方程為點(diǎn)xk+

切線法是非線性方程線性化的方法。其計(jì)算步驟為:①給出初始近似根x0及精度ε。②計(jì)算③若｜x1-x0｜＜ε,則轉(zhuǎn)向④;否則x1x0,轉(zhuǎn)向②。④輸出滿足精度的根x1,結(jié)束。切線法的計(jì)算框圖見(jiàn)圖5.7。切線法是非線性方程線性化的方法。其計(jì)算步驟為:圖5.7圖5.7

例3用切線法求方程

xex-1=0

的根(取五位小數(shù)計(jì)算)。取x0=0.5,迭代結(jié)果如表5―4所示。由于例3用切線法求方程

表5―4表5―4

切線迭代公式(5―20)對(duì)應(yīng)著(5―1)的等價(jià)方程由于(5―21)若是方程(5―1)的一個(gè)單實(shí)根,即切線迭代公式(5―20)對(duì)應(yīng)著(5―1)的等價(jià)方

所以,在點(diǎn)附近切線法收斂,而且收斂速度比較快。根據(jù)式(5―21)易得切線迭代公式的收斂條件為

所以,在點(diǎn)附近切線法收斂,而且收斂速度比§4弦截法

切線法迭代簡(jiǎn)單,收斂速度也較快,但就是需要計(jì)算導(dǎo)數(shù)f′(x),有時(shí)使用會(huì)帶來(lái)麻煩。這一節(jié)介紹的弦截法就避免了切線法的不足?！?弦截法切線法迭代簡(jiǎn)單,

點(diǎn)xk+1滿足該弦的方程,即有從而可求得弦截迭代公式(5―23)點(diǎn)xk+1滿足該弦的方程,即有從而可求得弦截迭

圖5.8圖5.8表5―5表5―5

例4用弦截法解方程

xex-1=0

解取x0=0.5,x1=0.6作為初始近似根,令

f(x)=x-e-x=0

利用公式(5―23)得到弦截迭代公式為計(jì)算結(jié)果見(jiàn)表5―5。與切線法的計(jì)算結(jié)果比較,可以看出弦截法的收斂速度也是比較快的。例4用弦截法解方程計(jì)算結(jié)果見(jiàn)表5―5。

§5加速迭代法

已知方程(5―1)的近似根xk,按迭代公式(5―8)可求得xk+1?，F(xiàn)考慮把xk+1作為過(guò)渡值,記為(5―24)(5―25)

§5加速迭代法

已知方程(5

還是設(shè)x為方程(5―1)的一個(gè)實(shí)根,即由式(5―24)和(5―26)得到還是設(shè)x為方程(5―1)的一個(gè)實(shí)根,即也即整理得到于是,只要取(5―27)(5―28)(5―29)也即整理得到于是,只要取(5―27)(5―28)(

這樣可得到加速迭代公式(5―30)這樣可得到加速迭代公式(5―30)

例5用加速迭代公式求方程

x=e-x

在x=0.5附近的一個(gè)根。解因?yàn)樵趚=0.5附近

g′(x)=-e-xg′(0.5)=-e-0.5≈-0.6

故加速迭代公式的具體形式為例5用加速迭代公式求方程表5―6表5―6

圖5.9圖5.9

與例2比較,同一例用一般迭代法要迭代十次才能得到滿足精度ε=10-3的結(jié)果,而這里僅迭代三次便可達(dá)到ε=10-5的高精度結(jié)果。這種加速過(guò)程取得的效果極為顯著。為了避免計(jì)算導(dǎo)數(shù)a≈g′(x),下面介紹埃特金(Aitken)迭代方法。它也是一種加速迭代法。(5―31)與例2比較,同一例用一般迭代法要迭代

將式(5―27)與式(5―31)聯(lián)立消去a得到可解出(5―32)(5―33)將式(5―27)與式(5―31)聯(lián)立消去a得到

這樣得到埃特金迭代公式(5―33)這樣得到埃特金迭代公式(5―33)

例6用埃特金迭代法求

x3-x-1=0

在(1,1.5)內(nèi)的根。解前面已經(jīng)提到,迭代公式

xk+1=x3k-1,k=0,1,2,…

是發(fā)散的?，F(xiàn)用埃特金算法來(lái)求根,其迭代公式為例6用埃特金迭代法求仍取x0=1.5,計(jì)算結(jié)果見(jiàn)表5―7。仍取x0=1.5,計(jì)算結(jié)果見(jiàn)表5―7。表5―7表5―7謝謝觀看！2020

謝謝觀看！第5章方程求根的數(shù)值解法§1二分法§2迭代法§3切線法(牛頓法)§4弦截法§5加速迭代法第5章方程求根的數(shù)值解法§1二分法§1二分法

我們已經(jīng)熟悉求解一元一次方程、一元二次方程以及某些特殊類型的高次代數(shù)方程或非線性方程的方法。這些方法都是代數(shù)解法,求出的根是方程的準(zhǔn)確根。但是在許多實(shí)際問(wèn)題中遇到的方程,例如代數(shù)方程

x3-x-1=0

或超越方程

§1二分法我們已經(jīng)熟悉求解一

等等,看上去形式簡(jiǎn)單,但卻不易求其準(zhǔn)確根。為此,只能求方程達(dá)到一定精度的近似根。方程的形式很多,我們主要討論一元非線性方程,也即

f(x)=0(5―1)等等,看上去形式簡(jiǎn)單,但卻不易求其準(zhǔn)

方程(5―1)可以有實(shí)根,也可以有復(fù)根或者重根等。本章主要討論它的實(shí)根的數(shù)值計(jì)算問(wèn)題。方程根的數(shù)值計(jì)算大致可分三個(gè)步驟進(jìn)行:(1)判定根的存在性。

(2)確定根的分布范圍,即將每一個(gè)根用區(qū)間隔離開來(lái)。

(3)根的精確化,即根據(jù)根的初始近似值按某種方法逐步精確化,直至滿足預(yù)先要求的精度為止。方程(5―1)可以有實(shí)根,也可以有復(fù)

設(shè)f(x)為定義在某區(qū)間上的連續(xù)函數(shù),方程(5―1)存在實(shí)根。雖然方程(5―1)的根的分布范圍一般比較復(fù)雜,但我們不難將函數(shù)f(x)的定義域分成若干個(gè)只含一個(gè)實(shí)根的區(qū)間。例如考慮方程

x2-2x-1=0

由圖5.1所示,該方程的一個(gè)負(fù)實(shí)根在-1和0之間,另一個(gè)正實(shí)根在2和3之間。設(shè)f(x)為定義在某區(qū)間上的連續(xù)函數(shù)

圖5.1圖5.1

這樣,我們總可以假設(shè)方程(5―1)(a,b)內(nèi)有且僅有一個(gè)單實(shí)根x*。由連續(xù)函數(shù)的介值定理知

f(a)·f(b)＜0

若數(shù)值b-a較小,那么我們可在(a,b)上任取一點(diǎn)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)有且僅有一個(gè)實(shí)根。于是可取某個(gè)端點(diǎn)或區(qū)間內(nèi)某一個(gè)點(diǎn)的值作為根的初始近似值。這樣,我們總可以假設(shè)方程(5―1)

設(shè)函數(shù)f(x)在區(qū)間［a,b］上單調(diào)連續(xù),且

f(a)·f(b)＜0

則方程(5―1)在區(qū)間(a,b)內(nèi)有且僅有一個(gè)實(shí)根x。下面在有根區(qū)間(a,b)內(nèi)介紹二分法的基本思想。計(jì)算f(a)與f(x0),若

f(a)·f(x0)＜0

則根x∈(a,x0),令

a1=a,b1=x0

否則x∈(x0,b),令

a1=x0,b1=b設(shè)函數(shù)f(x)在區(qū)間［a,b］上單調(diào)連圖5.2圖5.2

如此逐次往復(fù)下去,便得到一系列有根區(qū)間

(a,b),(a1,b1),(a2,b2),…,(ak,bk),…

其中這里a0=a,b0=b顯然有(5―2)

當(dāng)k→∞時(shí),區(qū)間(ak,bk)最終必收斂于一點(diǎn),該點(diǎn)就是所求方程(5―1)的根x。如此逐次往復(fù)下去,便得到一系列有根區(qū)間這里a0

我們把每次二分后的有根區(qū)間(ak,bk)的中點(diǎn)

作為所求根x的近似值,這樣獲得一個(gè)近似根的序列

x0,x1,x2,…,xk,…該序列必以根x為極限,即(5―3)故對(duì)于預(yù)先給定的精度ε,若有我們把每次二分后的有根區(qū)間(ak,bk)的中點(diǎn)作

則結(jié)果xk就是方程(5―1)滿足預(yù)給精度ε的近似根,也即由式(5―2)和(5―3)還可得到誤差估計(jì)式為(5―4)

對(duì)于確定的精度ε,從式(5―4)易求得需要二等分的次數(shù)k。二分法具有簡(jiǎn)單和易操作的優(yōu)點(diǎn)。其計(jì)算步驟如下,框圖如圖5.3所示。則結(jié)果xk就是方程(5―1)滿足預(yù)給1.計(jì)算步驟①輸入有根區(qū)間的端點(diǎn)a,b及預(yù)先給定的精度ε;②(a+b)/2x;③若f(a)f(x)＜0,則xb,轉(zhuǎn)向④;否則xa,轉(zhuǎn)向④。④若b-a＜ε,則輸出方程滿足精度的根x,結(jié)束;否則轉(zhuǎn)向②。1.計(jì)算步驟2.計(jì)算框圖例1求方程

f(x)=x3-x-1=0

在區(qū)間(1,1.5)內(nèi)的根。要求用四位小數(shù)計(jì)算,精確到10-2。解這里

a=1,b=1.5

取區(qū)間(1,1.5)的中點(diǎn)2.計(jì)算框圖

圖5.3圖5.3

由于f(1)＜0,f(1.25)＜0,則令

a1=1.25,b1=1.5

得到新的有根區(qū)間(1.25,1.5)由于f(1)＜0,f(1.25)＜0,則令

表5―1表5―1§2迭代法

迭代法的基本思想是:首先將方程(5―1)改寫成某種等價(jià)形式,由等價(jià)形式構(gòu)造相應(yīng)的迭代公式,然后選取方程的某個(gè)初始近似根x0,代入迭代公式反復(fù)校正根的近似值,直到滿足精度要求為止。迭代法是一種數(shù)值計(jì)算中重要的逐次逼近方法。例如,求方程

x3-x-1=0§2迭代法迭代法的基本思想

在x=1.5附近的一個(gè)根(用六位有效數(shù)字計(jì)算)。首先將原方程改寫成等價(jià)形式用初始近似根

x0=1.5代入式(5―5)的右端可得在x=1.5附近的一個(gè)根(用六位有效數(shù)字計(jì)算)。x1與x0相差較大,如果改用x1作為近似根代入式(5―5)的右端得x1與x0相差較大,如果改用x1作

表5―2表5―2

對(duì)于一般形式的方程(5―1),首先我們?cè)O(shè)法將其化為下列等價(jià)形式

x=g(x)(5―7)

然后按(5―7)構(gòu)造迭代公式從給定的初始近似根x0出發(fā),按迭代公式(5―8)可以得到一個(gè)數(shù)列

x0,x1,x2,…,xk,…

若這個(gè)數(shù)列｛xk｝有極限,則迭代公式(5―8)是收斂的。此時(shí)數(shù)列的極限對(duì)于一般形式的方程(5―1),首先我

就是原方程(5―1)的根。雖然迭代法的基本思想很簡(jiǎn)單,但效果并不總是令人滿意的。對(duì)于上例,若按方程寫成另一種等價(jià)形式

x=x3-1(5―9)

建立迭代公式

xk+1=x3k-1,k=0,1,2,…

仍取初始值x0=1.5,則迭代結(jié)果為

x1=2.375x2=12.3976

就是原方程(5―1)的根。

定理設(shè)方程x=g(x)在(a,b)內(nèi)有根x,g(x)滿足李普希茨(Lipschitz)條件:即對(duì)(a,b)內(nèi)任意的x1和x2都有q為某個(gè)確定的正數(shù),若q＜1,則方程在(a,b)內(nèi)有唯一的根;且迭代公式

xk+1=g(xk)

對(duì)任意初始近似值x0均收斂于方程的根x;還有誤差估計(jì)式(5―11)定理設(shè)方程x=g(x)在(a,b)

因?yàn)椋瑢?duì)任意正整數(shù)p有

當(dāng)時(shí)，因?yàn)?，?duì)任意正整數(shù)p有當(dāng)

證由已知條件知,x為方程x=g(x)的根,即x=g(x)設(shè)也是方程的根,即于是,由李普希茨條件得因?yàn)閝＜1,所以上式矛盾,故必有證由已知條件知,x為方程x=g(x)的根,

亦即方程在(a,b)內(nèi)有唯一的根。再考慮迭代公式

xk+1=g(xk),k=0,1,2,…

由李普希茨條件(5―12)由(5―12)可得(5―13)亦即方程在(a,b)內(nèi)有唯一的根。(5―12)

因?yàn)閝＜1,當(dāng)k→∞時(shí),qk→0,即有所以也就是對(duì)任意初始值x0迭代公式收斂。利用李普希茨條件因?yàn)閝＜1,當(dāng)k→∞時(shí),qk→0,即有所以

迭代法的幾何意義:把方程(5―1)求根的問(wèn)題改寫成(5―7)變?yōu)榍髷?shù)列｛xn｝的極限,實(shí)際上是把求根問(wèn)題轉(zhuǎn)化為求迭代法的幾何意義:把方程(5―1)求

圖5.4圖5.4

迭代過(guò)程(5―8)就是在x軸取初始近似值x0,過(guò)x0作y軸的平行線交曲線y=g(x)于p0,p0的橫坐標(biāo)為x0,縱坐標(biāo)為g(x0)(g(x0)=x1),也即

p0(x0,x1)

再在x軸上取x1作為新的近似值,過(guò)x1作y軸的平行線交曲線y=g(x)于p1,p1的橫坐標(biāo)為x1,縱坐標(biāo)為

g(x1)(g(x1)=x2),也即

p1(x1,x2)

而這相當(dāng)于過(guò)p0引平行于x軸的直線交y=x于

Q1(x1,x2)迭代過(guò)程(5―8)就是在x軸取初始近

再過(guò)Q1引平行于y軸的直線交曲線y=g(x)于

p1(x1,x2)

仿此可得到點(diǎn)列

p0(x0,x1),p1(x1,x2),p2(x2,x3),…

若則迭代法收斂,見(jiàn)圖5.4(a);否則迭代法發(fā)散,見(jiàn)圖5.4(b)。再過(guò)Q1引平行于y軸的直線交曲線y=g(x)于則迭代法必須說(shuō)明兩點(diǎn):①要驗(yàn)證g(x)是否滿足李氏條件一般比較困難,若g(x)可微,可用充分條件來(lái)代替。這里q＜1是非常重要的條件,否則不能保證迭代收斂。②對(duì)于收斂的迭代過(guò)程,誤差估計(jì)式(5―11)說(shuō)明迭代值的偏差｜xk-xk-1｜相當(dāng)小,就能保證迭代誤差｜x-xk｜足夠小。因此在具體計(jì)算時(shí)常常用條件｜xk-xk-1｜＜ε(5―15)

來(lái)控制迭代過(guò)程結(jié)束。必須說(shuō)明兩點(diǎn):

迭代法的突出優(yōu)點(diǎn)是算法的邏輯結(jié)構(gòu)簡(jiǎn)單,且在計(jì)算時(shí),中間結(jié)果若有擾動(dòng),仍不會(huì)影響計(jì)算結(jié)果。其計(jì)算步驟為:(1)確定方程f(x)=0的等價(jià)形式x=g(x),為確保迭代過(guò)程的收斂,要求g(x)滿足李普希茨條件(或｜g′(x)｜≤q＜1);(2)選取初始值x0,按公式

xk+1=g(xk),k=0,1,2,…

進(jìn)行迭代;(3)若｜xk+1-xk｜＜ε,則停止計(jì)算,x≈xk+1。迭代法的突出優(yōu)點(diǎn)是算法的邏輯結(jié)構(gòu)簡(jiǎn)單

例2求方程

x=e-x

在x=0.5附近的一個(gè)根。按五位小數(shù)計(jì)算,計(jì)算結(jié)果的精度要求為ε=10-3。解過(guò)x=0.5以步長(zhǎng)h=0.1計(jì)算

f(x)=x-e-x

由于

f(0.5)＜0,f(0.6)＞0

故所求的根在區(qū)間(0.5,0.6)內(nèi),且在x=0.5附近例2求方程

圖5.5圖5.5

表5―3表5―3

因此用迭代公式

由表可見(jiàn)為方程因此用迭代公式為方程

最后,我們給出一個(gè)說(shuō)明,在將方程(5―1)化為等價(jià)形式(5―7)時(shí),g(x)的形式是多種多樣的,選取不當(dāng),迭代公式(5―8)就不會(huì)收斂。最一般的形式可以寫成

x=x+α(x)f(x)(5―16)

這里α(x)為任意一個(gè)正(或負(fù))的函數(shù)。于是

g(x)=x+α(x)f(x)(5―17)

這樣可根據(jù)式(5―17)選取α(x),使得迭代公式

(5―8)滿足收斂條件特別當(dāng)取(5―18)最后,我們給出一個(gè)說(shuō)明,在將方程(5

時(shí),由式(5―16)構(gòu)造的迭代公式為下面要介紹的切線迭代公式;當(dāng)取(5―19)時(shí),可得到弦截迭代公式。時(shí),由式(5―16)構(gòu)造的迭代公式為§3切線法(牛頓法)

切線法是求解方程(5―1)的一種重要迭代方法。如圖5.6,曲線y=f(x)與x軸的交點(diǎn)x就是方程(5―1)的根?！?切線法(牛頓法)切線法

圖5.6圖5.6

與x軸的交點(diǎn)為xk+1,其方程為

點(diǎn)xk+1滿足該切線方程,即可得到切線迭代公式(或牛頓迭代公式)(5―20)與x軸的交點(diǎn)為xk+1,其方程為點(diǎn)xk+

切線法是非線性方程線性化的方法。其計(jì)算步驟為:①給出初始近似根x0及精度ε。②計(jì)算③若｜x1-x0｜＜ε,則轉(zhuǎn)向④;否則x1x0,轉(zhuǎn)向②。④輸出滿足精度的根x1,結(jié)束。切線法的計(jì)算框圖見(jiàn)圖5.7。切線法是非線性方程線性化的方法。其計(jì)算步驟為:圖5.7圖5.7

例3用切線法求方程

xex-1=0

的根(取五位小數(shù)計(jì)算)。取x0=0.5,迭代結(jié)果如表5―4所示