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

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

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

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

分析：

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

二分法優(yōu)點：簡單，對f(x)

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

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

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

(x)的不動點思路從一個初值x0

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

，只要φ

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

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

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

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

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

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

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

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

時，

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

對以上定理中的條件⑴，所有，，一般不容易驗證。實際使用迭代法時，通?？偸窃诟?/p>

的鄰域進行。

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

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

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

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

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

2.2.4迭代過程的收斂速度迭代過程的收斂速度，是指在收斂時迭代誤差的下降速度。

定義：設迭代過程

收斂于

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

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

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

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

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

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

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

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

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

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

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

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

定理

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

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

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

修正迭代格式（平方收斂）n證明過程見書p42改進二：

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

原理：若由xk

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

割線

切線斜率

割線斜率2.4弦截法：x2x1用割線斜率（差商）替換切線斜率，代入牛頓法迭代公式：上式中，固定弦的一個端點（x0,f(x0)），而另一端點變動，稱為單點弦法。2.4.1單點弦法：單點弦法幾何意義因為f(x*)=0，故求導數(shù)得

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