數(shù)值計(jì)算課件-第二章非線(xiàn)性方程的數(shù)值解法

第二章非線(xiàn)性方程的數(shù)值解法非線(xiàn)性方程求解的基本問(wèn)題：根的個(gè)數(shù)；根的位置。 對(duì)于非線(xiàn)性方程，由于f(x)的多樣性，求其根尚無(wú)一般的解析方法可以使用。求解方程的根，一般有兩種情形：求出在給定范圍內(nèi)的某個(gè)根求出方程的全部根，而根的數(shù)目和位置事先不知道本章介紹幾種方程求根的方法。這些方法大部分是要已知根的范圍，而且在此范圍內(nèi)只有一個(gè)根。求非線(xiàn)性方程根的一些常用方法：區(qū)間分割法（逐步搜索法、二分法）迭代法牛頓法割線(xiàn)法2.1區(qū)間搜索法預(yù)備知識(shí)：方程的根：?jiǎn)胃?、重根。根的存在性定理：定理：若f在[a,b]上連續(xù)，且f(a)·f(b)<0，則f在(a,b)上必有一根；若f在[a,b]上連續(xù)且單調(diào)則f在(a,b)上有且僅有一根。定理函數(shù)f(x)對(duì)于x*有f(x*)=0，但則稱(chēng)為方程的單根。如果有但，則稱(chēng)是方程的m重根。2.1.1逐步搜索法思路：先把區(qū)間[a,b]均分為N等分，從初始值x0=a開(kāi)始，步長(zhǎng)h＝（b－a）/N來(lái)增值。每跨一步進(jìn)行一次根的搜索。計(jì)算速度慢，一般用于確定根的位置例：求連續(xù)函數(shù)f(x)在有根區(qū)間[a,b]上的根。2.1.2二分法思路：二分法的基本思想就是逐步對(duì)分區(qū)間,經(jīng)過(guò)對(duì)根的搜索，將有根區(qū)間的長(zhǎng)度縮小到充分小，從而求出滿(mǎn)足精度的根的近似值。二分法的步驟：

在有根區(qū)間取中點(diǎn)，計(jì)算函數(shù)值，若，就得到方程的實(shí)根，否則檢查與是否同號(hào)，如同號(hào)，說(shuō)明待求的根在的右側(cè)，這時(shí)令；如在的左側(cè)，這時(shí)令，這樣新的有根區(qū)間的長(zhǎng)度為之半。二分法abx0x1a1x*b1

對(duì)壓縮了的有根區(qū)間又可施以同樣的手續(xù)，即用中點(diǎn)將區(qū)間分為兩半，然后判定待求的根在的哪一側(cè)，從而又確定一個(gè)新的有根區(qū)間，其長(zhǎng)度為的一半。如此反復(fù)，即可得出一系列有根區(qū)間其中的長(zhǎng)度二分法每次二等分后，設(shè)取有根區(qū)間的中點(diǎn)作為根的近似值，則在二分過(guò)程中可以獲得一個(gè)近似根的序列，該序列以根為極限。誤差

分析：

若取區(qū)間的中點(diǎn)作為的近似值，則誤差估計(jì)為：所以在實(shí)際計(jì)算時(shí)，只要二分足夠多次，便有。這里，為預(yù)定精度。

二分法優(yōu)點(diǎn)：簡(jiǎn)單，對(duì)f(x)

要求不高(只要連續(xù)即可).注：用二分法求根，最好先給出f(x)

草圖以確定根的大概位置。或用搜索程序，將[a,b]分為若干小區(qū)間，對(duì)每一個(gè)滿(mǎn)足f(ak)·f(bk)<0的區(qū)間調(diào)用二分法程序，可找出區(qū)間[a,b]內(nèi)的多個(gè)根，二分法二分法特點(diǎn)：缺點(diǎn)：收斂慢（等比級(jí)數(shù)）無(wú)法求復(fù)根及偶重根

對(duì)于給定的精度,可估計(jì)二分法所需的步數(shù)k：求方程f(x)=0的根的二分法算法2.2簡(jiǎn)單迭代法2.2.1迭代原理2.2.2迭代的收斂性2.2.3迭代的收斂速度2.2.4迭代的加速2.2簡(jiǎn)單迭代法f(x)=0x=φ(x)等價(jià)變換f(x)的根φ

(x)的不動(dòng)點(diǎn)思路從一個(gè)初值x0

出發(fā),計(jì)算x1=φ(x0),x2=φ(x1),…,xk+1=φ(xk),…若收斂，即存在x*使得

，只要φ

連續(xù)，則，也就是x*=φ(x*)，即x*是φ

的根，也就是f的根。若｛xk｝發(fā)散，則迭代法失敗。2.2.1迭代法原理：

迭代法：是一種逐次逼近的方法。它是用某個(gè)固定公式反復(fù)校正根的近似值，使之逐步精確，最后得到滿(mǎn)足精度要求的結(jié)果。xk+1=φ(xk)稱(chēng)為迭代格式，φ(x)稱(chēng)為迭代函數(shù)x0稱(chēng)為迭代初值,數(shù)列稱(chēng)為迭代序列

迭代法思想：將隱式方程的求根問(wèn)題歸結(jié)為計(jì)算一組顯式xk+1=φ(xk)

，也就是說(shuō)，迭代過(guò)程是一個(gè)逐步顯式化的過(guò)程。x=φ(x)例題例2.2.1試用迭代法求方程在區(qū)間(1，2)內(nèi)的實(shí)根。解：由建立迭代關(guān)系

k=10,1,2,3…….計(jì)算結(jié)果如下:例題精確到小數(shù)點(diǎn)后五位例題但如果由建立迭代公式仍取，則有，顯然結(jié)果越來(lái)越大，是發(fā)散序列xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=φ(x)y=φ(x)y=φ(x)y=φ(x)x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p1簡(jiǎn)單迭代法收斂定理考慮方程x=φ(x),φ(x)在[a,b]上連續(xù),若(I)對(duì)所有x[a,b]，有φ

(x)[a,b]；(II)存在0L<1，使所有

x[a,b]有|φ’(x)|L<1。則：1）方程x=φ(x)在[a,b]上的解x*存在且唯一。2）任取x0[a,b]，由迭代過(guò)程xk+1=φ

(xk)收斂于x*簡(jiǎn)單迭代法推論驗(yàn)后誤差估計(jì)：誤差估計(jì)式：驗(yàn)前誤差估計(jì)：證明：①φ

(x)在[a,b]上有根？令有根②根唯一？反證：若不然，設(shè)還有，則在和之間。而③當(dāng)k

時(shí)，

xk收斂到x*？3簡(jiǎn)單迭代法有根L<1④⑤可用來(lái)控制收斂精度L越收斂越快小注：定理?xiàng)l件非必要條件，對(duì)某些問(wèn)題在區(qū)間[a,b]上不滿(mǎn)足|φ’(x)|L<1，迭代也收斂。實(shí)際應(yīng)用中還是用此定理判斷收斂性，當(dāng)不滿(mǎn)足收斂條件時(shí)，改變迭代公式使之滿(mǎn)足。3簡(jiǎn)單迭代法2.2.3迭代法局部收斂性

對(duì)以上定理中的條件⑴，所有，，一般不容易驗(yàn)證。實(shí)際使用迭代法時(shí)，通常總是在根

的鄰域進(jìn)行。

定義如果存在的某個(gè)鄰域，是任意指定的正數(shù)，使迭代過(guò)程對(duì)于任意初值1均收斂，則迭代過(guò)程在根鄰域具有局部收斂性。

證:由于，存在的充分小鄰域，使成立，據(jù)微分中值定理，有:

注意到，又當(dāng)時(shí)，故有:由收斂定理的條件⑴可以斷定對(duì)于任意收斂。局部收斂性定理：設(shè)函數(shù)在的根鄰近有連續(xù)的一階導(dǎo)數(shù)，且，則迭代過(guò)程具有局部收斂性。由于在實(shí)際應(yīng)用中根x*

事先不知道，故條件|φ′(x*)|<1無(wú)法驗(yàn)證。但已知根的初值x0在根x*鄰域，又根據(jù)φ′(x)的連續(xù)性，則可采用

|φ′(x0)|<1來(lái)代替|φ′(x*)|<1，判斷迭代的收斂性。

2.2.4迭代過(guò)程的收斂速度迭代過(guò)程的收斂速度，是指在收斂時(shí)迭代誤差的下降速度。

定義：設(shè)迭代過(guò)程

收斂于

的根，令迭代誤差，若存在常數(shù)和，使

，則稱(chēng)序列是階收斂的，稱(chēng)漸近誤差常數(shù)。

收斂速度是誤差的收縮率，階數(shù)越高，收斂得越快。特別地，時(shí)稱(chēng)線(xiàn)性收斂，時(shí)稱(chēng)平方收斂或二次收斂，時(shí)稱(chēng)超線(xiàn)性收斂。迭代法的收斂速度常用收斂階表示

定理對(duì)迭代過(guò)程，若在所求根的鄰域連續(xù)，且則迭代過(guò)程在鄰域是階收斂的.證:p28Q:

如何實(shí)際確定收斂階？例題例：證明函數(shù)在區(qū)間[1，2]上滿(mǎn)足迭代收斂條件。證明：例題

例題若取迭代函數(shù)，不滿(mǎn)足收斂定理，故不能肯定收斂到方程的根。2.2.5迭代過(guò)程的加速

對(duì)于收斂的迭代過(guò)程,只要迭代足夠多次,就可以使結(jié)果達(dá)到任意的精度。但有時(shí)迭代過(guò)程收斂緩慢,從而使計(jì)算量加大.因此迭代過(guò)程的加速是個(gè)重要的課題.常用迭代加速方法加權(quán)法埃特金加速法斯蒂芬生算法

Aitken加速：簡(jiǎn)單迭代法xyy=xy=

φ(x)x*x0P(x0,x1)x1x2P(x1,x2)一般地，有：比收斂得略快。

Steffensen加速：2.3牛頓迭代法2.3.1迭代公式的建立2.3.2牛頓迭代法的收斂情況2.3.3牛頓迭代法的修正法2.3牛頓法原理：將非線(xiàn)性方程線(xiàn)性化——Taylor展開(kāi)取x0

x*，將f(x)在x0做一階Taylor展開(kāi):，在x0和x*之間。將(x*

x0)2看成高階小量，則有：線(xiàn)性化xyx*x0x1迭代公式：迭代函數(shù)：牛頓切線(xiàn)法2.3.2牛頓切線(xiàn)法的收斂情況

定理

（局部收斂性）設(shè)函數(shù)在包含的某鄰域內(nèi)有階連續(xù)導(dǎo)數(shù)，是方程的單根，則當(dāng)初值充分接近時(shí)，牛頓切線(xiàn)法收斂，且至少為二階收斂。并有這里單根意味著：牛頓切線(xiàn)法2.3.2牛頓迭代法的收斂情況

定理設(shè)函數(shù)滿(mǎn)足且在鄰域連續(xù)，則牛頓迭代法在收斂，且至少為二階收斂。并有牛頓切線(xiàn)法證明：牛頓法事實(shí)上是一種特殊的不動(dòng)點(diǎn)迭代其中，則收斂由Taylor展開(kāi)：只要f’(x*)0在單根附近收斂快牛頓切線(xiàn)法注：牛頓法收斂性依賴(lài)于x0的選取。x*x0x0x0具有局部恒收斂性，收斂性依賴(lài)于初值的選取。收斂性好（至少平方收斂）每次計(jì)算要計(jì)算導(dǎo)數(shù)，效率不高牛頓法特點(diǎn)：例題例1:用Newton法求的近似解。（取8位有效數(shù)字）。解：由零點(diǎn)定理。例題例題例2:用Newton法計(jì)算。解：牛頓迭代法算法框圖Newton迭代法算法牛頓切線(xiàn)法改進(jìn)牛頓法的改進(jìn)與推廣改進(jìn)一：重根時(shí)的收斂速度及改進(jìn)：Q1:若，牛頓法是否仍收斂？設(shè)x*是f的n重根，則：且。因?yàn)榕ｎD法事實(shí)上是一種特殊的不動(dòng)點(diǎn)迭代，其中，則A1:

有局部收斂性，收斂慢（線(xiàn)性收斂）。Q2:如何加速重根的收斂？A2:

修正迭代格式（平方收斂）n證明過(guò)程見(jiàn)書(shū)p42改進(jìn)二：

牛頓下山法——擴(kuò)大初值范圍的修正牛頓法：

原理：若由xk

得到的xk+1不能使|f|減小，則在xk和xk+1之間找一個(gè)更好的點(diǎn)，使得。xkxk+1通過(guò)適當(dāng)選取的保證函數(shù)值能單調(diào)下降牛頓切線(xiàn)法改進(jìn)下山法：迭代過(guò)程中保證函數(shù)值單調(diào)下降，即牛頓下山法：將牛頓法與下山法結(jié)合使用的算法下山因子牛頓下山法幾點(diǎn)討論實(shí)用中從=1開(kāi)始反復(fù)將減半計(jì)算。一旦單調(diào)下降則稱(chēng)“下山成功”。反之則稱(chēng)“下山失敗”，需另選初值x0計(jì)算。牛頓切線(xiàn)法改進(jìn)當(dāng)≠1時(shí)。牛頓下山法只有線(xiàn)性收斂速度，但對(duì)初值的選取卻可放的很寬。常用牛頓下山法選取初值。實(shí)用中常用牛頓下山法選取初值。為加快收斂速度，轉(zhuǎn)入牛頓法來(lái)求解根的精確值。牛頓法每一步要計(jì)算f和f’，相當(dāng)于2個(gè)函數(shù)值，且有些導(dǎo)數(shù)難求。為了避開(kāi)導(dǎo)數(shù)的計(jì)算，用差商代替導(dǎo)數(shù)。x0切線(xiàn)

割線(xiàn)

切線(xiàn)斜率

割線(xiàn)斜率2.4弦截法：x2x1用割線(xiàn)斜率（差商）替換切線(xiàn)斜率，代入牛頓法迭代公式：上式中，固定弦的一個(gè)端點(diǎn)（x0,f(x0)），而另一端點(diǎn)變動(dòng)，稱(chēng)為單點(diǎn)弦法。2.4.1單點(diǎn)弦法：?jiǎn)吸c(diǎn)弦法幾何意義因?yàn)閒(x*)=0，故求導(dǎo)數(shù)得

所以0<’(x*)<1，所以單點(diǎn)弦法僅為線(xiàn)性收斂。單點(diǎn)弦法收斂速度：迭代函數(shù)：當(dāng)初值x0充分接近時(shí)很接近f’(x*)2.4.2雙點(diǎn)弦法：為了加快收斂速度，弦的兩個(gè)端點(diǎn)都在變動(dòng)，稱(chēng)為雙點(diǎn)弦法或稱(chēng)快速弦截法。迭代時(shí)需要2個(gè)初值xk和xk－1。雙點(diǎn)弦法迭代公式：。雙點(diǎn)弦法幾何意義P1P2雙點(diǎn)弦法收斂速度：雙點(diǎn)弦截法的收斂性與牛頓迭代法一樣，即在根的某個(gè)鄰域內(nèi)，f(x)有直至二階的連續(xù)導(dǎo)數(shù)，且f’(x*)0，具有局部收斂性，同時(shí)在鄰域