數(shù)值計(jì)算方法2

第二章非線性方程的數(shù)值解法2.1二分法2.2一般迭代法2.3牛頓迭代法2.4弦截法（1）確定初始含根區(qū)間數(shù)值計(jì)算方法主要分為兩大類(lèi)。第一類(lèi)是區(qū)間收縮法。

（2）收縮含根區(qū)間第二類(lèi)是迭代法。

（1）選定根的初始近似值（2）按某種原則生成收斂于根的近似點(diǎn)列2.1二分法

基本假設(shè):

2.1.1二分法的計(jì)算步驟

常用終止原則為:2.1.2二分法的收斂性與事前誤差估計(jì)

所以，二分法總是收斂的例2.1試用二分法求

的一個(gè)正根，使誤差小于10-3故可取初始區(qū)間解2.1.3

二分法評(píng)述優(yōu)點(diǎn)：簡(jiǎn)單可靠，易于編程實(shí)現(xiàn)，它對(duì)函數(shù)要求低，適用于的奇數(shù)重根情形。缺點(diǎn)：不能直接用于求偶重根，不能用于求復(fù)根，也難以向方程組推廣使用，收斂速度慢。2.2一般迭代法迭代法的算法思想為：(1)把（2-2）等價(jià)變換為如下形式(2)建立迭代格式或更一般地建立迭代格式(3)適當(dāng)選取初始值，遞推計(jì)算出所需的解。2.2.1迭代法的算法思想

2.2.2迭代法的收斂性則稱(chēng)在內(nèi)李普希茲連續(xù)。定義2.1

設(shè)在某個(gè)區(qū)間內(nèi)，函數(shù)滿足下述李普希茲條件：則在內(nèi)李普希茲連續(xù)。命題2.1

若在閉區(qū)間內(nèi)連續(xù)且命題得證。證定理2.1

設(shè)x*=g(x*),g(x)在閉區(qū)間：內(nèi)李普希茲連續(xù)，則對(duì)任何初值由迭代格式xk+1=g(xk)計(jì)算得到的解序列收斂于x*(這時(shí)我們稱(chēng)迭代格式xk+1=g(xk)在x*

的鄰域上局部收斂）。（1）首先用數(shù)學(xué)歸納法證明：由假設(shè)知又設(shè)，則綜上，由歸納法原理知，結(jié)論成立。

證因此，，定理得證。反設(shè)存在矛盾。所以結(jié)論成立。2)迭代函數(shù)在x*

附近李普希茲連續(xù)從而收斂的迭代格式統(tǒng)稱(chēng)為皮卡（Picard）迭代

(2)由（1）的結(jié)論和g(x)在內(nèi)李普希茲連續(xù)的假設(shè)，可遞推得到

注

1)g(x)在內(nèi)李普希茲連續(xù)的條件保證了x*

為f(x)=0在內(nèi)的唯一根。

證推論

設(shè)x*=g(x*)，若g(x)在x*

附近連續(xù)可微且，則迭代格式xk+1=g(xk)在x*

附近局部收斂。

注由于x*

事先未知，故實(shí)際應(yīng)用時(shí)，代之以近似判則。但需注意，這實(shí)際上是假設(shè)了x0充分接近x*，若x0

離x*

較遠(yuǎn)，迭代格式可能不收斂。

定理2.2

（非局部收斂定理）如果在上連續(xù)可微且以下條件滿足：注

雖然定理2.1的條件是充分條件，但其條件并不很強(qiáng)，實(shí)際上，我們易證如下命題。命題2.2

若在區(qū)間內(nèi)，則對(duì)任何，迭代格式不收斂。

2.2.3迭代法的誤差估計(jì)

故對(duì)正整數(shù)p，有

（2）事后誤差估計(jì)

由此，對(duì)給定的精度可進(jìn)行(1)事前誤差估計(jì)簡(jiǎn)單地代之以或

例2.2試建立收斂的迭代格式求解在區(qū)間(2,3)內(nèi)滿足精度要求的根。

首先可簡(jiǎn)單的把等價(jià)化為由此建立迭代格式所以該迭代格式在內(nèi)不收斂，不可取。為建立收斂的迭代格式，我們把等價(jià)化為從而建立迭代格式解易知在x>0時(shí)g(x)單調(diào)增，故有2<g(2)<g(x)<g(3)<3故由定理2.2得：任取x0

[2,3]，該迭代格式收斂。取x0=2計(jì)算，結(jié)果見(jiàn)表2-2（書(shū)17頁(yè)）。

2.2.4迭代法的收斂速度與加速收斂技巧

則稱(chēng)該迭代格式是p階收斂的。特別地，p=1時(shí)稱(chēng)為線性收斂，1<p<2時(shí)稱(chēng)為超線性收斂，p=2

時(shí)稱(chēng)為平方收斂。

定義2.2

設(shè)迭代格式的解序列收斂于的根，如果迭代誤差當(dāng)時(shí)滿足漸近關(guān)系式對(duì)于線性收斂的計(jì)算格式，可采用以下介紹的埃特肯（Aitken）加速技巧來(lái)提高收斂速度。設(shè)序列線性收斂于，即有，則近似地有兩式相除得解得把埃特肯加速技巧應(yīng)用于單步迭代法便構(gòu)成了Steffensen算法。據(jù)此，我們可取修正值作為的新近似值以提高精度。這一技巧便稱(chēng)為埃特肯加速技巧。

例2.3試用Steffensen算法求解在區(qū)間（2，3）內(nèi)滿足精度要求的根。

對(duì)例2.2的迭代格式取用算法計(jì)算，結(jié)果見(jiàn)表2-3。解

2.3牛頓迭代法

2.3.1牛頓迭代公式的構(gòu)造

設(shè)f(x)在其零點(diǎn)附近連續(xù)可微，已知為的第k次近似值，則取的根作為的第k+1次近似值其迭代函數(shù)為牛頓迭代法幾何意義：過(guò)點(diǎn)作函數(shù)y=f(x)的切線l：以切線l與x軸的交點(diǎn)作為的新近似值

2.3.2牛頓迭代法的收斂性與收斂速度

定理2.3給定f(x)=0，如果在根附近f(x)二階連續(xù)，且為f(x)=0的單根，則牛頓迭代法在附近至少是平方收斂的。首先證明牛頓迭代法的收斂性：

而單根條件保證了因此由定理2.1知，牛頓迭代法局部收斂。證其次證明牛頓迭代法的收斂速度：整理得可見(jiàn)，當(dāng)時(shí)，牛頓迭代法為平方收斂；當(dāng)時(shí)，牛頓迭代法超平方收斂。例2.4試用牛頓迭代法求解在區(qū)間(2,3)內(nèi)滿足精度要求的根。相應(yīng)于該方程的牛頓迭代公式為取x0=2，計(jì)算結(jié)果見(jiàn)表2-4。解牛頓迭代法評(píng)述

優(yōu)點(diǎn)：是收斂速度比較快

缺點(diǎn)：(1)局部收斂，對(duì)初始值的要求比較高。為解決這一問(wèn)題，可采用二分法來(lái)提供足夠“好”的近似值作為迭代初值，或通過(guò)增加“下山”限制來(lái)放寬對(duì)初值的要求，即把牛頓迭代法修改為其中的選取使得（這稱(chēng)為“下山”限制）。該方法稱(chēng)為牛頓下山法。（2）當(dāng)為重根時(shí)，牛頓迭代法僅僅線性收斂。（3）由于涉及的計(jì)算，導(dǎo)致了對(duì)函數(shù)的要求高，并增加了每一迭代步的計(jì)算量，這在一定程度上減弱了該迭代法收斂快的優(yōu)越性，而且在向非線性方程組推廣時(shí)，使計(jì)算量和對(duì)函數(shù)的要求大大增加。因此，人們致力于研究建立牛頓迭代法的修改格式以回避對(duì)函數(shù)導(dǎo)數(shù)值的計(jì)算。本章僅對(duì)非線性方程介紹一種較為有效的修改算法——弦截法。

2.4弦截法

計(jì)算思想是：若已知x*

的兩個(gè)近似值xk

和xk-1，則以f(x)在xk

與xk-1

之間的平均變化率(差商)近似代替，據(jù)此把牛頓迭代法修改為幾何意義是以過(guò)和兩點(diǎn)做曲線的弦線l：以l與x軸的交點(diǎn)作為的新近似值（如圖2-3所示）弦截法

定理2.4設(shè)f(x)在其零點(diǎn)x*

的鄰域內(nèi)二階連續(xù)，且對(duì)，則對(duì)，相應(yīng)的弦截法是階收斂的。該定理說(shuō)明弦截法是超線性收斂的算法，也是局部收斂的方法，其迭代初始值亦可用二分法提供。

例2.5試用弦截法求解在區(qū)間內(nèi)滿足精度要求的根。

相應(yīng)于該方程的弦截法公式為取計(jì)算，結(jié)果見(jiàn)表2-5。解

例2.6試討論函數(shù)方程的根的分布情況，