數(shù)值計算方法2

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

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

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

基本假設:

2.1.1二分法的計算步驟

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

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

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

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

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

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

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

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

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

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

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

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

注

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

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

證推論

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

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

附近局部收斂。

注由于x*

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

離x*

較遠，迭代格式可能不收斂。

定理2.2

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

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

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

2.2.3迭代法的誤差估計

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

（2）事后誤差估計

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

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

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

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

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

則稱該迭代格式是p階收斂的。特別地，p=1時稱為線性收斂，1<p<2時稱為超線性收斂，p=2

時稱為平方收斂。

定義2.2

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

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

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

2.3牛頓迭代法

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

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

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

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

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

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

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

2.4弦截法

計算思想是：若已知x*

的兩個近似值xk

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

與xk-1

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

定理2.4設f(x)在其零點x*

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

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

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

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