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

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

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

（2）收縮含根區(qū)間第二類是迭代法。（1）選定根的初始近似值（2）按某種原則生成收斂于根的近似點(diǎn)列2.1二分法(對(duì)分法)

一、根的隔離將含根區(qū)間一個(gè)個(gè)隔開(kāi)，找到根的范圍，使每個(gè)區(qū)間只有一個(gè)根。

定理：對(duì)f(x)=0,f(x)在[a,b]上連續(xù),f(a)f(b)<0且f(x)嚴(yán)格單調(diào)上升（或嚴(yán)格單調(diào)下降），則f(x)在[a,b]內(nèi)僅有一根。1。利用零點(diǎn)存在定理2。搜索法：3。作圖找出交點(diǎn)xy二、對(duì)分法設(shè)f(x)在（a,b)上連續(xù)且f(x)=0在（a,b)內(nèi)只有一個(gè)根1。算法2。收斂性根據(jù)精度終止計(jì)算。3。誤差控制例2.1：試用二分法求的非零實(shí)根，使其誤差小于10-2解：(1)根的隔離取h=0.5(2)預(yù)先算出計(jì)算步數(shù)(3)計(jì)算（用表格形式寫出來(lái)）0(+)1.5(-)21.75+1.7521.875+1.87521.9375–1.8751.93751.90265+1.902651.93751.921875+51.921881.93751.92688+2.1.3

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

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

或更一般地建立迭代格式

例由此建立迭代格式也可建立迭代格式-----發(fā)散-----收斂二迭代法的收斂性則稱在內(nèi)李普希茲連續(xù)。

定義2.1

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

若在閉區(qū)間內(nèi)連續(xù)且

（1）首先用數(shù)學(xué)歸納法證明：

由假設(shè)知

又設(shè)，則

綜上，由歸納法原理知，結(jié)論成立。

證定理2.1設(shè)x*=g(x*),g(x)在閉區(qū)間：內(nèi)李普希茲連續(xù)，則對(duì)任何初值由迭代格式xk+1=g(xk)計(jì)算得到的解序列收斂于x*(這時(shí)我們稱迭代格式xk+1=g(xk)在x*的鄰域上局部收斂）。因此，，定理得證。

反設(shè)存在矛盾。所以結(jié)論成立。2)迭代函數(shù)在x*附近李普希茲連續(xù)從而收斂的迭代格式統(tǒ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.2

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

發(fā)散收斂證明所以該迭代格式在內(nèi)不收斂，不可取。易知在x>0時(shí)g(x)單調(diào)增，故有2<g(2)<g(x)<g(3)<3故由定理2.2得：任取，該迭代格式收斂。

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

故對(duì)正整數(shù)p，有由此，對(duì)給定的精度可進(jìn)行（2）事后誤差估計(jì)

(1)事前誤差估計(jì)簡(jiǎn)單地代之以或

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

對(duì)給定的精度可進(jìn)行例2.2試建立收斂的迭代格式求解x–e–x=0在x=0.5附近的一個(gè)根（ε=10-3）。解建立迭代格式00.560.564860.6065370.568440.5452480.566410.5797090.567560.56006100.5669150.57117

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

則稱該迭代格式是p階收斂的。p=1時(shí)稱為線性收斂1<p<2時(shí)稱為超線性收斂p=2時(shí)稱為平方收斂。定義2.2設(shè)迭代格式的解序列收斂于的根，如果迭代誤差當(dāng)時(shí)滿足漸近關(guān)系式對(duì)分法：線性收斂一般迭代法：線性收斂

2.3牛頓迭代法

一、牛頓迭代公式的構(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給定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。解0212.10.12.094568121-0.0054318792.094551482-0.0000166392.0945514820牛頓迭代法評(píng)述

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

缺點(diǎn)：(1)局部收斂，對(duì)初始值的要求比較高。為解決這一問(wèn)題，可采用二分法來(lái)提供足夠“好”的近似值作為迭代初值，或通過(guò)增加“下山”限制來(lái)放寬對(duì)初值的要求，即把牛頓迭代法修改為其中的選取使得（這稱為“下山”限制）。該方法稱為牛頓下山法。（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)作為的新近似值yoy=f(x)PQx該定理說(shuō)明弦截法是超線性收斂的算法，也是局部收斂的方法，其迭代初始值亦可用二分法提供。定理2.4設(shè)f(x)在其零點(diǎn)x*的鄰域內(nèi)二階連續(xù)，且對(duì)，則對(duì)，相應(yīng)的弦截法是階收斂的。

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

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

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

因?yàn)閤-2-1012f(x)-++-+故f(x)在(0,1)內(nèi)有惟一零點(diǎn)，所以最小正根<1。若采用牛頓迭代法計(jì)算，則取計(jì)算，結(jié)果見(jiàn)表2—7。解在(0,1)內(nèi)，若采用弦截法計(jì)算，則取，解得的結(jié)果見(jiàn)表2-8。例1：用簡(jiǎn)單迭代法、牛頓迭代法求在（0，1）內(nèi)的根的近似值。解列表計(jì)算簡(jiǎn)單迭代法