第二章非線性方程的數(shù)值解法

第二章非線性方程的數(shù)值解法第一頁，共五十七頁，編輯于2023年，星期四求非線性方程根的一些常用方法：區(qū)間分割法（逐步搜索法、二分法）迭代法牛頓法割線法第二頁，共五十七頁，編輯于2023年，星期四2.1區(qū)間分割法預(yù)備知識(shí)：方程的根：單根、重根。根的存在性定理：定理：若f在[a,b]上連續(xù)，且f(a)·f(b)<0，則f在(a,b)上必有一根；若f在[a,b]上連續(xù)且單調(diào)則f在(a,b)上有且僅有一根。定理函數(shù)f(x)對于x*有f(x*)=0，但則稱為方程的單根。如果有但，則稱是方程的m重根。第三頁，共五十七頁，編輯于2023年，星期四2.1.1逐步搜索法思路：先把區(qū)間[a,b]均分為N等分，從初始值x0=a開始，步長h＝（b－a）/N來增值。每跨一步進(jìn)行一次根的搜索。計(jì)算速度慢，一般用于確定根的位置例：求連續(xù)函數(shù)f(x)在有限區(qū)間[a,b]上的根。2.1.2二分法思路：二分法的基本思想就是逐步對分區(qū)間,經(jīng)過對根的搜索，將有根區(qū)間的長度縮小到充分小，從而求出滿足精度的根的近似值。第四頁，共五十七頁，編輯于2023年，星期四二分法的步驟：

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

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

分析：

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

二分法第七頁，共五十七頁，編輯于2023年，星期四優(yōu)點(diǎn)：簡單，對f(x)

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

草圖以確定根的大概位置?；蛴盟阉鞒绦颍瑢a,b]分為若干小區(qū)間，對每一個(gè)滿足f(ak)·f(bk)<0的區(qū)間調(diào)用二分法程序，可找出區(qū)間[a,b]內(nèi)的多個(gè)根，二分法二分法特點(diǎn)：缺點(diǎn)：收斂慢（等比級數(shù)）無法求復(fù)根及偶重根

對于給定的精度,可估計(jì)二分法所需的步數(shù)k：第八頁，共五十七頁，編輯于2023年，星期四求方程f(x)=0的根的二分法算法第九頁，共五十七頁，編輯于2023年，星期四2.2簡單迭代法2.2.1迭代原理2.2.2迭代的收斂性2.2.3迭代的收斂速度2.2.4迭代的加速第十頁，共五十七頁，編輯于2023年，星期四2.2簡單迭代法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迭代法原理：第十一頁，共五十七頁，編輯于2023年，星期四

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

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

，也就是說，迭代過程是一個(gè)逐步顯式化的過程。x=φ(x)第十二頁，共五十七頁，編輯于2023年，星期四例題例2.2.1試用迭代法求方程在區(qū)間(1，2)內(nèi)的實(shí)根。解：由建立迭代關(guān)系

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

(x)[a,b]；(II)存在0<

L<1，使所有

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

(xk)收斂于x*簡單迭代法推論驗(yàn)后誤差估計(jì)：誤差估計(jì)式：驗(yàn)前誤差估計(jì)：第十八頁，共五十七頁，編輯于2023年，星期四證明：①φ

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

時(shí)，

xk收斂到x*？3簡單迭代法有根L<1第十九頁，共五十七頁，編輯于2023年，星期四④⑤可用來控制收斂精度L越收斂越快小注：定理?xiàng)l件非必要條件，對某些問題在區(qū)間[a,b]上不滿足|φ’(x)|L<1，迭代也收斂。實(shí)際應(yīng)用中還是用此定理判斷收斂性，當(dāng)不滿足收斂條件時(shí)，改變迭代公式使之滿足。3簡單迭代法第二十頁，共五十七頁，編輯于2023年，星期四2.2.3迭代法局部收斂性

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

的鄰域進(jìn)行。

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

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

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

注意到，又當(dāng)時(shí)，故有:由收斂定理的條件⑴可以斷定對于任意收斂。局部收斂性定理：設(shè)函數(shù)在的根鄰近有連續(xù)的一階導(dǎo)數(shù)，且，則迭代過程具有局部收斂性。第二十二頁，共五十七頁，編輯于2023年，星期四由于在實(shí)際應(yīng)用中根x*

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

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

第二十三頁，共五十七頁，編輯于2023年，星期四2.2.4迭代過程的收斂速度迭代過程的收斂速度，是指在收斂時(shí)迭代誤差的下降速度。

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

收斂于

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

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

收斂速度是誤差的收縮率，階數(shù)越高，收斂得越快。特別地，時(shí)稱線性收斂，時(shí)稱平方收斂或二次收斂，時(shí)稱超線性收斂。迭代法的收斂速度常用收斂階表示第二十四頁，共五十七頁，編輯于2023年，星期四

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

如何實(shí)際確定收斂階？第二十五頁，共五十七頁，編輯于2023年，星期四例題例：證明函數(shù)在區(qū)間[1，2]上滿足迭代收斂條件。證明：第二十六頁，共五十七頁，編輯于2023年，星期四例題

第二十七頁，共五十七頁，編輯于2023年，星期四例題若取迭代函數(shù)，不滿足收斂定理，故不能肯定收斂到方程的根。第二十八頁，共五十七頁，編輯于2023年，星期四2.2.5迭代過程的加速

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

Aitken加速：簡單迭代法xyy=xy=

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

Steffensen加速：第三十頁，共五十七頁，編輯于2023年，星期四2.3牛頓迭代法2.3.1迭代公式的建立2.3.2牛頓迭代法的收斂情況2.3.3牛頓迭代法的修正法第三十一頁，共五十七頁，編輯于2023年，星期四2.3牛頓法原理：將非線性方程線性化——Taylor展開取x0

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

x0)2看成高階小量，則有：線性xyx*x0x1迭代公式：迭代函數(shù)：第三十二頁，共五十七頁，編輯于2023年，星期四牛頓切線法2.3.2牛頓切線法的收斂情況

定理

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

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

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

修正迭代格式（平方收斂）n證明過程見書p42第四十二頁，共五十七頁，編輯于2023年，星期四改進(jìn)二：

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

原理：若由xk

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

割線

切線斜率

割線斜率2.4弦截法：x2x1第四十五頁，共五十七頁，編輯于2023年，星期四用割線斜率（差商）替換切線斜率，代入牛頓法迭代公式：上式中，固定弦的一個(gè)端點(diǎn)（x0,f(x0)），而另一端點(diǎn)變動(dòng)，稱為單點(diǎn)弦法。2.4.1單點(diǎn)弦法：第四十六頁，共五十七頁，編輯于2023年，星期四單點(diǎn)弦法幾何意義第四十七頁，共五十七頁，編輯于2023年，星期四因?yàn)閒(x*)=0，故求導(dǎo)數(shù)得

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

可以證明，雙點(diǎn)弦截法具有超線性斂速度，收斂的階為：第五十一頁