《現(xiàn)代數(shù)值計算》課件7非方程的數(shù)值解法（上課用）

1、教學(xué)目的 1. 掌握解非線性方程（組）的二分法和插值法； 2. 掌握解非線性方程（組）的一般迭代法及有關(guān)收斂性的證明與牛頓法； 3. 掌握解非線性方程（組）的牛頓法 4. 了解加速收斂的方法。教學(xué)重點及難點 重點是解非線性方程（組）的牛頓法；難點是迭代法的收斂性的證明。 第七章 非線性方程的數(shù)值解法 代數(shù)方程求根問題是一個古老的數(shù)學(xué)問題.早在16世紀就找到了三次，四次方程的求根公式.但直到19世紀才證明了n5次的一般代數(shù)方程式不能用代數(shù)公式求解.因此需要研究用數(shù)值方法求得滿足一定精度的代數(shù)方程式的近似解. 而在工程和科學(xué)技術(shù)中許多問題常歸結(jié)為求解非線性方程式問題。例如在控制系統(tǒng)的設(shè)計領(lǐng)域中，在

2、研究人口增長率等問題中都最后可化為方程求根的問題。非線性方程的數(shù)值解法 求解非線性方程的根，就是求解高次方程或超越方程(含有指數(shù)和對數(shù)等)，因為這類方程沒有固定的求根公式。 用 f(x)表示方程左端的函數(shù)，則一般的非線性方程可表示為 f (x) = 0. 本節(jié)的任務(wù)就是上述方程的根或函數(shù)的零點。7.1 引言如果f(x)可以分解成 , 其中m為正整數(shù)且 ,則稱x*是f(x)的m重零點,或稱方程f(x)=0的m重根。當m=1時稱x*為單根。若f(x)存在m階導(dǎo)數(shù),則是方程f(x)的m重根(m1) 當且僅當 通常方程根的數(shù)值解法大致分為三個步驟進行判定根的存在性。即方程有沒有根？如果有根,有幾個根？

3、 確定根的分布范圍。即將每一個根用區(qū)間隔離開來，這個過程實際上是獲得方程各根的初始近似值。 根的精確化。將根的初始近似值按某種方法逐步精確化，直到滿足預(yù)先要求的精度為止. 本章介紹方程的迭代解法，它既可以用來求解代數(shù)方程，也可以用來解超越方程，并且僅限于求方程的實根。運用迭代法求解方程的根應(yīng)解決以下兩個問題：確定根的初值;將進一步精確化到所需要的精度。 由高等數(shù)學(xué)知識知, 設(shè)f (x)為區(qū)間a,b上的單值連續(xù), 如果f (a)f (b)0 , 則a,b中至少有一個實根。如果f (x)在a,b上還是單調(diào)地遞增或遞減，則僅有一個實根。由此可大體確定根所在子區(qū)間，方法有： (1) 畫圖法 (2) 逐

4、步搜索法y=f(x)abyx(1) 畫圖法 畫出y = f (x)的略圖，從而看出曲線與x軸交點的 大致位置。 也可將f (x) = 0分解為1(x)= 2(x)的形式，1(x) 與 2(x)兩曲線交點的橫坐標所在的子區(qū)間即為含根區(qū)間。例如 xlogx-1= 0可以改寫為logx=1/x畫出對數(shù)曲線y=logx,與雙曲線y= 1/x,它們交 點的橫坐標位于區(qū)間2,3內(nèi)畫圖法023yx對于某些看不清根的函數(shù)，可以擴大一下曲線y0 xy=f(x)y=kf(x)y0 xABa1b1a2b2(2) 逐步搜索法(2) 搜索法 對于給定的f (x), 設(shè)有根區(qū)間為A,B, 從x0=A出發(fā),以步長h=(B-

5、A)/n(n是正整數(shù)), 在A,B內(nèi)取定節(jié)點:xi=x0ih (i=0,1,2,n), 從左至右檢查f (xi)的符號, 如發(fā)現(xiàn)xi與端點x0的函數(shù)值異號,則得到一個縮小的有根子區(qū)間xi-1,xi。例1 方程f(x)=x3-x-1=0 確定其有根區(qū)間解：用試湊的方法，不難發(fā)現(xiàn) f(0)0 在區(qū)間（0,2）內(nèi)至少有一個實根 設(shè)從x=0出發(fā),取h=0.5為步長向右進行根的搜索,列表如下xf(x)0 0.5 1.0 1.5 2 + +可以看出，在1.0,1.5內(nèi)必有一根 用逐步搜索法進行實根隔離的關(guān)鍵是選取步長h要選擇適當h ，使之既能把根隔離開來，工作量又不太大。 為獲取指定精度要求的初值,可在以

6、上隔離根的基礎(chǔ)上采用對分法繼續(xù)縮小該含根子區(qū)間 下面的二分法可以看作是搜索法的一種改進。(3)方程求根的二分法(對分法或分半法) (bisection method)(3) 生成含根區(qū)間：滿足下式:生成含根區(qū)間例不能求出所有根,(即有可能漏根)。例如圖該點可求出,注1 :改進的方法，試位法（比例求根法）。但漏掉了四個點2.不能用于求偶重根、復(fù)根；不能推廣到多元方程組求解；缺點: 的等比級數(shù)的收斂速度相同。1.收斂速度不快,僅與公比為 即是線性收斂的。實根，要求準確到小數(shù)點后的第2位。解例1.32031.32811.3242-1.31251.32811.3203-1.31251.34381.32

7、81+1.31251.3751.3438+1.251.3751.3125-1.251.51.375+11.51.25-6543210表6-1 上述二分法的優(yōu)點是算法簡單,而且在有限區(qū)間內(nèi),收斂性總能得到保證.值得注意的是,為了求出足夠精確的近似解,往往需要計算很多次函數(shù)值,是一種收斂較慢的方法,通常用二分法給出根的大致范圍,再利用下面將介紹的更有效的方法求解方程.另一方面，二分法只使用于求一元方程的奇數(shù)重實根. 7.3 一元方程的不動點迭代法7.3.2 局部收斂性和加速收斂法7.3.1 不動點迭代法及其收斂性 迭代法是一種逐次逼近法。它是求解代數(shù)方程，超越方程及方程組的一種基本方法，但存在收斂

8、性及收斂快慢的問題。 為用迭代法求解f (x)=0的近似根，首先需將此方程化為等價的方程 x=(x) (7.3.1) 然而將 f (x)=0 化為等價方程（7.3.1）的方法是很多的。例1 簡單迭代法又稱為不動點迭代法，基本思想是首先構(gòu)造不動點方程 x= (x)，即由方程 f(x)=0變換為等價形式 x= (x), 式中(x)稱為迭代函數(shù)。然后建立迭代格式：xk+1 = (xk)稱為不動點迭代格式。知a= (a)，即xk收斂于方程的根 a。 a稱為函數(shù) (x)的不動點 當給定初值x0 后, 由迭代格式xk+1 = (xk)可求得數(shù)列xk。如果xk收斂于a，且(x)在a連續(xù)，則a就是不動點方程的

9、根。因為：例1對應(yīng)的迭代法分別為表 7-2012111.51.51.357208812.375000001.3308609612.39648441.324717961133-+kkxxk數(shù)值分析數(shù)值分析迭代法的幾何意義記y1=x , y2=(x) , 它們交點的橫坐標即為方程的根數(shù)值分析數(shù)值分析xyy = xxyy = xxyy = xxyy = xx*x*x*x*y=(x)y=(x)y=(x)y=(x)x0p0 x1p1x0p0 x1p1x0p0 x1p1x0p0 x1p1yxy=x0y=(x)aabb 若從任何可取的初值出發(fā)都能保證收斂，則稱它為大范圍收斂。如若為了保證收斂性必須選取初值充

10、分接近于所要求的根，則稱它為局部收斂。 通常局部收斂方法比大范圍收斂方法收斂得快。因此，一個合理的算法是先用一種大范圍收斂方法求得接近于根的近似值（如對分法），再以其作為新的初值使用局部收斂法（如迭代法）。 這里討論迭代法的收斂性時，均指的是局部收斂性。7.3.2 局部收斂性定理3 （迭代法的局部收斂定理）設(shè)a是方程x=(x)的根，如果(1)迭代函數(shù)(x)在a的鄰域可導(dǎo)； (2)在a的某個鄰域S=x:|x- a | ,對于任 意的 xS 有則對于任意的初值 x0S ，迭代公式xn+1=(xn) 產(chǎn)生的數(shù)列xn，收斂于方程的根a 。YxY=x0-2-112YxY=x0-2-112k00.010.

11、6931471820.99071046 .141.1461931151.1461932 有時，對于一些不滿足定理7.1的條件問題，可以通過轉(zhuǎn)化，化為適合于迭代的形式。這要針對具體情況進行討論。7.3.3 迭代法的收斂速度 一種迭代法具有實用價值，首先要求它是收斂的，其次還要求它收斂得比較快。定義7.2 設(shè)迭代過程 收斂于 的根 ,記迭代誤差 ,若存在常數(shù)p（p1）和c（c0），使 則稱序列 是 p 階收斂的,c稱漸近誤差常數(shù)。特別地,p=1時稱為線性收斂,p=2時稱為平方收斂。p 1時稱為超線性收斂。 數(shù)p 的大小反映了迭代法收斂的速度的快慢，p愈大，則收斂的速度愈快，故迭代法的收斂階是對迭代

12、法收斂速度的一種度量。 定理 設(shè)迭代過程 , 若 在所求根 的鄰域連續(xù)且 則迭代過程在 鄰域是p階收斂的。根據(jù)已知條件得 由迭代公式 及有證: 由于 即在 鄰域 , 所以 有局部收斂性, 將 在 處泰勒展開 例5 已知迭代公式 收斂于 證明該迭代公式平方收斂.證: 迭代公式相應(yīng)的迭代函數(shù)為將 代入，根據(jù)定理可知，迭代公式平方收斂。為了使迭代過程收斂或提高收斂的速度, 可設(shè)法 提高初值的精度以減少迭代的次數(shù) 提高收斂的階數(shù) pSteffensen迭代格式 對于線性收斂的迭代法，收斂很慢，所以要在這些迭代法的基礎(chǔ)上考慮加速收斂的方法。設(shè)xk 線性收斂到x*，則迭代誤差en 滿足當n充分大時有 即展

13、開有：已知 ，則 ，改成 n=0，1，2，Steffensen迭代格式也可以改寫成其中迭代函數(shù)Steffensen迭代法收斂的充要條件定理7.4.1 Steffensen迭代法收斂的充要條件證明：必要性Steffensen迭代法收斂的充要條件充分性Steffensen算法的收斂速度定理7.4.2 在定理7.4.2假設(shè)下，若 產(chǎn)生的序列 至少平方收斂到 。 Steffensen算法的收斂速度Steffensen算法的收斂速度 Steffensen算法的收斂速度 Steffensen算法的收斂速度 由定理7.4.2知 至少以平方速度收斂到 。 也就是說：簡單迭代法是線性收斂；Steffensen迭

14、代至少平方以上收斂（加速收斂）。例題例7.9試用Steffensen算法求解方程解法一、取 ，由 n = 0，1，2，例題取初值 ，計算結(jié)果如下：NXnYnZn01.51.3572088081.33086095911.3248991811.3247523791.32472449621.3247179571.3247179571.324717957例題解法二、取 ，由對于該迭代函數(shù)在一般迭代法中是發(fā)散的，而Steffensen格式卻是收斂的。 n=0，1，2，例題取初值 ，計算結(jié)果如下：NXnYnZn01.52.3751.23964843711.4162929751.8409219155.238

15、87276921.3556504421.4913982792.31727069931.3289487771.3470628831.44435122441.3248044891.3251735441.32711728151.3247179441.3247181521.32471898061.324717957Steffensen迭代格式幾何解釋 Steffensen迭代算法 Steffensen迭代算法 1.理解收斂性、收斂階的概念及二分法思想方法。本課重點： 2.會求用二分法解非線性方程時的執(zhí)行次數(shù)k 。為給定的誤差界. 3.理解簡單迭代法的思想方法，幾何意義，壓縮不動點定理。 4. 掌握簡單

16、迭代法的收斂(局部)定理（定理證明，會判斷簡單迭代法是否收斂）。7.4.2 割線法與拋物線法7.4.1 Newton迭代法 7.4 一元方程的常用迭代法 用迭代法可逐步精確方程 根的近似值，但必須要找到 的等價方程 ,如果 選得不合適,不僅影響收斂速度,而且有可能造成迭代格式發(fā)散。能否找到一種迭代方法,既結(jié)構(gòu)簡單,收斂速度快,又不存在發(fā)散的問題。這就是本節(jié)要介紹的牛頓迭代法.1 牛頓迭代法的基本思想 牛頓迭代法一種重要和常用的迭代法, 它的基本思想是將非線性函數(shù)f(x)逐步線性化, 從而將非線性方程f(x)=0近似地轉(zhuǎn)化為線性方程求解。7.4.1 Newton迭代法 對于方程 ,設(shè)其近似根為

17、, 函數(shù)f (x)可在 附近作泰勒展開 忽略高次項,用其線性部分作為函數(shù) f (x)的近似， 設(shè) 的根 ,則有 ,即 將右端取為 ,即 是比 更接近于 的近似值 這就是著名的牛頓迭代公式（7.4.2）（7.4.1）3 牛頓迭代法的幾何解釋任取初始值 ，上過點 的切線方程為：與 軸交于點過點 的切線方程為與 軸交于點如此下去得牛頓迭代公式: 用切線代替曲線，用線性函數(shù)的零點作為 f(x)的零點的近似值。牛頓迭代法也稱切線法因此牛頓法產(chǎn)生的序列xk如下圖所示。 x0 x2x1過P0的切線過P1的切線將(7.4.2)寫成一般的不動點迭代(7.3.3)的形式,有所以有 ， Newton迭代法是超線性收

18、斂的。更準確地，從(7.4.1)和(7.4.2)可得下面的定理. （收斂的充分條件）設(shè) f C2a, b，若(1) f (a) f (b) 0； 則Newtons Method產(chǎn)生的序列 xk 收斂到f (x) 在 a, b 的唯一根。產(chǎn)生的序列單調(diào)有界，保證收斂。定理13 牛頓迭代法的收斂性證明： 根的存在性根的唯一性收斂性yx0bax0yx0bax0yx0bax0yx0Ba x0例1 用迭代法求 在隔根區(qū)間1.4,1.5內(nèi)的根，要求準確到小數(shù)點后第4位。（1）牛頓迭代公式為（2）當 時有，因 ,故取 ,牛頓迭代法收斂。推論 在定理1條件下， Newton迭代法具有平方收斂速度。 （局部收斂

19、性）設(shè) f C2a, b，若 x* 為 f (x) 在a, b上的根，且 f (x*) 0，則存在 x* 的鄰域 使得任取初值 ，若Newtons Method產(chǎn)生的序列 xk 收斂到x*，則至少二階收斂，且定理2function y=newton(fname,dfname,x0,e,N)y=x0;x0=y+2*e;k=0;while abs(x0-y)e&k0,都有 ,并且 非增.因此 是有下界的非增序列 ，從而有極限x*。對（7.4.3）的兩邊取極限,得到 -a=0,因為 0，故有x*= 。由此可知證 對f(x)= -a, f(x)=2x, Newton迭代法為例2 設(shè)a0,對方程 -a=

20、0. 試證:取任何初值 0，Newton迭代法都收斂到算術(shù)根 。（7.4.3）練習(xí)練習(xí)1 用Newton法求 的近似解。解：由零點定理。練習(xí)練習(xí)練習(xí)2 用Newton法計算 。解：設(shè)x*是f(x)=0的m重根,，即在前個定理中,要求f(x*)=0 , 即 是方程的單根時, Newton法至少具有二階局部收斂性。下面討論重根的情形.由Newton迭代函數(shù) 的導(dǎo)數(shù)表達式,從而， 。因此只要 ，這時的Newton迭代法線性收斂。容易求出*為了改善重根時Newton法的收斂性，有如下兩種方法。(1) 若改為取容易驗證 。 迭代至少二階收斂.(2)若令 ,由x*是f(x)的m重零點，有這種方法也是至少二

21、階收斂的.所以，x*是 的單零點.可將Newton法的迭代函數(shù)修改為*例7.9 方程 的根 是二重根.用三種方法求解.解 (1)用Newton法有(2)由(7.4.4),m=2迭代公式為*(3) 由(7.4.5)確定的修改方法，迭代公式化簡為 三種方法均取 =1.5,計算結(jié)果列于表6-7.方法（2）和方法(3)都是二階方法， 都達到了誤差限為 的精確度,而普通的Newton法是一階的,要近30次迭代才有相同精度的結(jié)果. Xk X0 X1 X2 X3方法(1) 1.5 1.458333333 1.436607143 1.425497619方法(2) 1.5 1.416666667 1.41421

22、5686 1.414213562方法(3) 1.5 1.411764706 1.414211438 1.414213562表7-7*Newton法的每步計算都要求提供函數(shù)的導(dǎo)數(shù)值，當函數(shù)f(x) 比較復(fù)雜時，提供它的導(dǎo)數(shù)值往往是有困難的。此時，在Newton迭代法（7.4.2）中，可用 或常數(shù)D取代 迭代式變?yōu)榛蜻@稱為簡化Newton法。其迭代函數(shù)為簡化Newton法一般為線性收斂。* 牛頓下山法* 通常,牛頓迭代法的收斂性依賴于初始值 的選取,如果 偏離所求的根 比較遠,則牛頓法可能發(fā)散。為了防止迭代發(fā)散,我們對牛頓迭代法的迭代過程再附加一項要求,即具有單調(diào)性 將牛頓迭代法與下山法結(jié)合起來使

23、用,即在下山法保證函數(shù)值下降的前提下,用牛頓迭代法加快收斂速度。把這一算法稱為牛頓下山法。即滿足這項要求的算法稱下山法。其中(01)為下山因子 . 下山因子的選擇是個逐步探索的過程，設(shè)從=1開始反復(fù)將減半進行試算, 即逐次取為從中挑選下山因子，直至找到其中某個使單調(diào)性條件成立，則稱“下山成功”，否則“下山失敗”，這時需另選初值重算。7.4.2 割線法與拋物線法1. 割線法/弦截法這就是割線法的計算公式。我們也可用點 上的差商代替 ，得到迭代公式(7.4.6)弦截法也稱割線法,其幾何意義是用過曲線上兩點 、 的割線來代替曲線,用割線與x軸交點的橫座標作為方程的近似根 再過P1點和點 作割線求出

24、,再過P2點和點 作割線求出 ,余此類推，當收斂時可求出滿足精度要求的弦截法幾何意義即：弦截法具有超線性收斂，收斂的階約為1.618， 弦截法具有超線性收斂，收斂的階約為1.618，它與前面介紹的一般迭代法一樣都是線性化方法，但也有區(qū)別。即一般迭代法在計算 時只用到前一步的值 ，故稱之為單點迭代法；而弦截法在求 時要用到前兩步的結(jié)果 和 ，使用這種方法必須給出兩個初始近似根 ，這種方法稱為多點迭代法。 類似于簡化的Newton法，有如下的單點割線法 其迭代函數(shù)為于是 其中 在 和 之間。由此可見，單點割線法一般為線性收斂。但當 變化不大時， ，收斂仍可能很快。*解 由于 故，在（1，2）內(nèi)僅有一個根。對于單點割線法和割線法，取 計算結(jié)果如表7-8。 例10 分別用單點割線法，割線法和Newton法求解Leonardo方程對于Newton法，由于在(0,2)內(nèi) ，故取 ，計算結(jié)果如表7-8 單點割線法割線法Newton法1.3684210531.3684210531.3833887041.3688512631.3688504691.3688694191.3688032981.3688081041.3688081091.3688086441.3688081081.368808108 表 7-8