第二章非線性方程的數值解法

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

（2）收縮含根區間第二類是迭代法。（1）選定根的初始近似值（2）按某種原則生成收斂于根的近似點列（1）確定初始含根區間數值計算方法主要分為兩大類。第一類是22.1二分法(對分法)

一、根的隔離將含根區間一個個隔開，找到根的范圍，使每個區間只有一個根。

定理：對f(x)=0,f(x)在[a,b]上連續,f(a)f(b)<0且f(x)嚴格單調上升（或嚴格單調下降），則f(x)在[a,b]內僅有一根。1。利用零點存在定理2.1二分法(對分法)一、根的隔離將含根區間一個3非線性方程的數值解法ppt課件42。搜索法：2。搜索法：53。作圖找出交點xy3。作圖找出交點xy6二、對分法設f(x)在（a,b)上連續且f(x)=0在（a,b)內只有一個根1。算法二、對分法設f(x)在（a,b)上連續且f(x)=0在（a,72。收斂性根據精度終止計算。2。收斂性根據精度終止計算。83。誤差控制3。誤差控制9非線性方程的數值解法ppt課件10例2.1：試用二分法求的非零實根，使其誤差小于10-2解：(1)根的隔離取h=0.5例2.1：試用二分法求11(2)預先算出計算步數(3)計算（用表格形式寫出來）0(+)1.5(-)21.75+1.7521.875+1.87521.9375–1.8751.93751.90265+1.902651.93751.921875+51.921881.93751.92688+(2)預先算出計算步數(3)計算（用表格形式寫出來）0122.1.3

二分法評述優點：簡單可靠，易于編程實現，它對函數要求低，適用于的奇數重根情形。缺點：不能直接用于求偶重根，不能用于求復根，也難以向方程組推廣使用，收斂速度慢。2.1.3

二分法評述優點：簡單可靠，易于編程實現，它對132.2一般迭代法迭代法的算法思想為：(A)把（1）等價變換為如下形式(B)建立迭代格式(C)適當選取初始值x

0，遞推計算出所需的解。一迭代法的算法思想

2.2一般迭代法迭代法的算法思想為：(A)把（1）等14或更一般地建立迭代格式或更一般地建立迭代格式15

例由此建立迭代格式也可建立迭代格式-----發散-----收斂例由此建立迭代格式也可建立迭代格式-----發散---16二迭代法的收斂性則稱在內李普希茲連續。

定義2.1

設在某個區間

內，函數

滿足下述李普希茲條件：命題得證。證則在內李普希茲連續。命題2.1

若在閉區間內連續且

二迭代法的收斂性則稱在內17（1）首先用數學歸納法證明：

由假設知

又設，則

綜上，由歸納法原理知，結論成立。

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

上局部收斂）。（1）首先用數學歸納法證明：由假設知又設18因此，，定理得證。

反設存在矛盾。所以結論成立。2)迭代函數在x*附近李普希茲連續從而收斂的迭代格式統稱為皮卡（Picard）迭代

(2)由（1）的結論和g(x)在

內李普希茲連續的假設，可遞推得到

注1)g(x)在

內李普希茲連續的條件保證了x*為f(x)=0在

內的唯一根。

證因此，，定理19推論設x*=g(x*)，若g(x)在x*附近連續可微且，則迭代格式xk+1=g(xk)在x*附近局部收斂。

注由于x*事先未知，故實際應用時，代之以近似判則。但需注意，這實際上是假設了x0充分接近x*，若x0離x*較遠，迭代格式可能不收斂。推論設x*=g(x*)，若g(x)在x20

定理2.2（非局部收斂定理）如果在上連續可微且以下條件滿足：命題2.2

若在區間內，則對任何，迭代格式不收斂。

定理2.2（非局部收斂定理）如果21發散收斂證明所以該迭代格式在內不收斂，不可取。易知在x>0時g(x)單調增，故有2<g(2)<g(x)<g(3)<3故由定理2.2得：任取，該迭代格式收斂。發散收斂證明所以該迭代格式在內易知在x>0時g(x)22

三、迭代法的誤差估計

故對正整數p，有三、迭代法的誤差估計故對正整數p，有23由此，對給定的精度可進行由此，對給定的精度24（2）事后誤差估計

(1)事前誤差估計簡單地代之以或

三、迭代法的誤差估計

對給定的精度可進行（2）事后誤差估計(1)事前誤差估計簡單地代之以或25例2.2試建立收斂的迭代格式求解x–e–x=0在x=0.5附近的一個根（ε=10-3）。解建立迭代格式00.560.564860.6065370.568440.5452480.566410.5797090.567560.56006100.5669150.57117例2.2試建立收斂的迭代格式求解x–e–x26

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

則稱該迭代格式是p階收斂的。p=1時稱為線性收斂1<p<2時稱為超線性收斂p=2時稱為平方收斂。定義2.2設迭代格式的解序列收斂于的根，如果迭代誤差當時滿足漸近關系式四、迭代法的收斂速度與加速收斂技巧則稱該迭代格式27對分法：線性收斂一般迭代法：線性收斂對分法：線性收斂一般迭代法：線性收斂28

2.3牛頓迭代法

一、牛頓迭代公式的構造

設f(x)在其零點附近連續可微，已知為的第k次近似值，則取的根作為的第k+1次近似值其迭代函數為牛頓迭代法2.3牛頓迭代法一、牛頓迭代公式的構造29幾何意義：過點作函數y=f(x)的切線l：以切線l與x軸的交點作為的新近似值幾何意義：過點作30二、牛頓迭代法的收斂性與收斂速度

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

因此由定理2.1的推論知，牛頓迭代法局部收斂。二、牛頓迭代法的收斂性與收斂速度定理2.3給31其次證明牛頓迭代法的收斂速度：整理得

可見，當時，牛頓迭代法為平方收斂；當時，牛頓迭代法超平方收斂。其次證明牛頓迭代法的收斂速度：整理得可見，當32例2.4試用牛頓迭代法求解在區間(2,3)內滿足精度要求的根。相應于該方程的牛頓迭代公式為取x0=2，計算結果見表2-4。解0212.10.12.094568121-0.0054318792.094551482-0.0000166392.0945514820例2.4試用牛頓迭代法求解33牛頓迭代法評述

優點：是收斂速度比較快

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

2.4弦截法

弦截法計算思想是：若已知x*的兩個近似值xk和xk-1，則以f(x)在xk與xk-1之間的平均變化率(差商)近似代替，據此把牛頓迭代法修改為幾何意義是以過和兩點做曲線的弦線l：以l與x軸的交點作為的新近似值2.4弦截法弦截法計算思想是：若已知36yoy=f(x)PQxyoy=f(x)PQx37該定理說明弦截法是超線性收斂的算法，也是局部收斂的方法，其迭代初始值亦可用二分法提供。定理2.4設f(x)在其零點x*的鄰域內二階連續，且對，則對，相應的弦截法是階收斂的。該定理說明弦截法是超線性收斂的算法，也是局部38

例2.5試用弦截法求解在區間(2,3)內滿足精度要求的根。

相應于該方程的弦截法公式為解取計算，結果見表2-5。例2.5試用弦截法求解39

例2.6試討論函數方程的根的分布情況，分別用牛頓迭代法和弦截法求其最小正根，使誤差小于，并比較它們的工作量

因為x-2-1012f(x)-++-+故f(x)在(0,1)內有惟一零點，所以最小正根<1。若采用牛頓迭代法計算，則取計算，結果見表2—7。解在(0,1)內，例2.6試討論函數方程40若采用弦截法計算，則取，解得的結果見表2-8。若采用弦截法計算，則取41例1：用簡單迭