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

計算方法方程求根的迭代法第一頁，共六十四頁，編輯于2023年，星期一§1二分法

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

x3-x-1=0

或超越方程

第二頁，共六十四頁，編輯于2023年，星期一

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

f(x)=0(5―1)第三頁，共六十四頁，編輯于2023年，星期一

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

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

(3)根的精確化,即根據(jù)根的初始近似值按某種方法逐步精確化,直至滿足預(yù)先要求的精度為止。第四頁，共六十四頁，編輯于2023年，星期一

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

x2-2x-1=0

由圖5.1所示,該方程的一個負(fù)實根在-1和0之間,另一個正實根在2和3之間。第五頁，共六十四頁，編輯于2023年，星期一

圖5.1第六頁，共六十四頁，編輯于2023年，星期一

這樣,我們總可以假設(shè)方程(5―1)(a,b)內(nèi)有且僅有一個單實根x*。由連續(xù)函數(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)某一個點的值作為根的初始近似值。第七頁，共六十四頁，編輯于2023年，星期一

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

f(a)·f(b)＜0

則方程(5―1)在區(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∈(x0,b),令

a1=x0,b1=b第八頁，共六十四頁，編輯于2023年，星期一圖5.2第九頁，共六十四頁，編輯于2023年，星期一

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

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

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

當(dāng)k→∞時,區(qū)間(ak,bk)最終必收斂于一點,該點就是所求方程(5―1)的根x。第十頁，共六十四頁，編輯于2023年，星期一

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

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

x0,x1,x2,…,xk,…該序列必以根x為極限,即(5―3)故對于預(yù)先給定的精度ε,若有第十一頁，共六十四頁，編輯于2023年，星期一

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

對于確定的精度ε,從式(5―4)易求得需要二等分的次數(shù)k。二分法具有簡單和易操作的優(yōu)點。其計算步驟如下,框圖如圖5.3所示。第十二頁，共六十四頁，編輯于2023年，星期一1.計算步驟①輸入有根區(qū)間的端點a,b及預(yù)先給定的精度ε;②(a+b)/2x;③若f(a)f(x)＜0,則xb,轉(zhuǎn)向④;否則xa,轉(zhuǎn)向④。④若b-a＜ε,則輸出方程滿足精度的根x,結(jié)束;否則轉(zhuǎn)向②。第十三頁，共六十四頁，編輯于2023年，星期一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)的中點第十四頁，共六十四頁，編輯于2023年，星期一

圖5.3第十五頁，共六十四頁，編輯于2023年，星期一

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

a1=1.25,b1=1.5

得到新的有根區(qū)間(1.25,1.5)第十六頁，共六十四頁，編輯于2023年，星期一

表5―1第十七頁，共六十四頁，編輯于2023年，星期一§2迭代法

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

x3-x-1=0第十八頁，共六十四頁，編輯于2023年，星期一

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

x0=1.5代入式(5―5)的右端可得第十九頁，共六十四頁，編輯于2023年，星期一x1與x0相差較大,如果改用x1作為近似根代入式(5―5)的右端得第二十頁，共六十四頁，編輯于2023年，星期一

表5―2第二十一頁，共六十四頁，編輯于2023年，星期一

對于一般形式的方程(5―1),首先我們設(shè)法將其化為下列等價形式

x=g(x)(5―7)

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

x0,x1,x2,…,xk,…

若這個數(shù)列｛xk｝有極限,則迭代公式(5―8)是收斂的。此時數(shù)列的極限第二十二頁，共六十四頁，編輯于2023年，星期一

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

x=x3-1(5―9)

建立迭代公式

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

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

x1=2.375x2=12.3976

第二十三頁，共六十四頁，編輯于2023年，星期一

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

xk+1=g(xk)

對任意初始近似值x0均收斂于方程的根x;還有誤差估計式(5―11)第二十四頁，共六十四頁，編輯于2023年，星期一

因為，對任意正整數(shù)p有

當(dāng)時，第二十五頁，共六十四頁，編輯于2023年，星期一

證由已知條件知,x為方程x=g(x)的根,即x=g(x)設(shè)也是方程的根,即于是,由李普希茨條件得因為q＜1,所以上式矛盾,故必有第二十六頁，共六十四頁，編輯于2023年，星期一

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

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

由李普希茨條件(5―12)由(5―12)可得(5―13)第二十七頁，共六十四頁，編輯于2023年，星期一

因為q＜1,當(dāng)k→∞時,qk→0,即有所以也就是對任意初始值x0迭代公式收斂。利用李普希茨條件第二十八頁，共六十四頁，編輯于2023年，星期一

迭代法的幾何意義:把方程(5―1)求根的問題改寫成(5―7)變?yōu)榍髷?shù)列｛xn｝的極限,實際上是把求根問題轉(zhuǎn)化為求第二十九頁，共六十四頁，編輯于2023年，星期一

圖5.4第三十頁，共六十四頁，編輯于2023年，星期一

迭代過程(5―8)就是在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)第三十一頁，共六十四頁，編輯于2023年，星期一

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

p1(x1,x2)

仿此可得到點列

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

若則迭代法收斂,見圖5.4(a);否則迭代法發(fā)散,見圖5.4(b)。第三十二頁，共六十四頁，編輯于2023年，星期一必須說明兩點:①要驗證g(x)是否滿足李氏條件一般比較困難,若g(x)可微,可用充分條件來代替。這里q＜1是非常重要的條件,否則不能保證迭代收斂。②對于收斂的迭代過程,誤差估計式(5―11)說明迭代值的偏差｜xk-xk-1｜相當(dāng)小,就能保證迭代誤差｜x-xk｜足夠小。因此在具體計算時常常用條件｜xk-xk-1｜＜ε(5―15)

來控制迭代過程結(jié)束。第三十三頁，共六十四頁，編輯于2023年，星期一

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

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

進(jìn)行迭代;(3)若｜xk+1-xk｜＜ε,則停止計算,x≈xk+1。第三十四頁，共六十四頁，編輯于2023年，星期一

例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附近第三十五頁，共六十四頁，編輯于2023年，星期一

圖5.5第三十六頁，共六十四頁，編輯于2023年，星期一

表5―3第三十七頁，共六十四頁，編輯于2023年，星期一

因此用迭代公式

由表可見為方程第三十八頁，共六十四頁，編輯于2023年，星期一

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

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

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

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

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

(5―8)滿足收斂條件特別當(dāng)取(5―18)第三十九頁，共六十四頁，編輯于2023年，星期一

時,由式(5―16)構(gòu)造的迭代公式為下面要介紹的切線迭代公式;當(dāng)取(5―19)時,可得到弦截迭代公式。第四十頁，共六十四頁，編輯于2023年，星期一§3切線法(牛頓法)

切線法是求解方程(5―1)的一種重要迭代方法。如圖5.6,曲線y=f(x)與x軸的交點x就是方程(5―1)的根。第四十一頁，共六十四頁，編輯于2023年，星期一

圖5.6第四十二頁，共六十四頁，編輯于2023年，星期一

與x軸的交點為xk+1,其方程為

點xk+1滿足該切線方程,即可得到切線迭代公式(或牛頓迭代公式)(5―20)第四十三頁，共六十四頁，編輯于2023年，星期一

切線法是非線性方程線性化的方法。其計算步驟為:①給出初始近似根x0及精度ε。②計算③若｜x1-x0｜＜ε,則轉(zhuǎn)向④;否則x1x0,轉(zhuǎn)向②。④輸出滿足精度的根x1,結(jié)束。切線法的計算框圖見圖5.7。第四十四頁，共六十四頁，編輯于2023年，星期一圖5.7第四十五頁，共六十四頁，編輯于2023年，星期一

例3用切線法求方程

xex-1=0

的根(取五位小數(shù)計算)。取x0=0.5,迭代結(jié)果如表5―4所示。由于第四十六頁，共六十四頁，編輯于2023年，星期一

表5―4第四十七頁，共六十四頁，編輯于2023年，星期一

切線迭代公式(5―20)對應(yīng)著(5―1)的等價方程由于(5―21)若是方程(5―1)的一個單實根,即第四十八頁，共六十四頁，編輯于2023年，星期一

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

第四十九頁，共六十四頁，編輯于2023年，星期一§4弦截法

切線法迭代簡單,收斂速度也較快,但就是需要計算導(dǎo)數(shù)f′(x),有時使用會帶來麻煩。這一節(jié)介紹的弦截法就避免了切線法的不足。第五十頁，共六十四頁，編輯于2023年，星期一

點xk+1滿足該弦的方程,即有從而可求得弦截迭代公式(5―23)第五十一頁，共六十四頁，編輯于2023年，星期一

圖5.8第五十二頁，共六十四頁，編輯于2023年，星期一表5―5第五十三頁，共六十四頁，編輯于2023年，星期一

例4用弦截法解方程

xex-1=0

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

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

利用公式(5―23)得到弦截迭代公式為計算結(jié)果見表5―5。與切線法的計算結(jié)果比較,可以看出弦截法的收斂速度也是比較快的。第五十四頁，共六十四頁，編輯于2023年，星期一