第六章非線性方程求根第1頁，共58頁，2023年，2月20日，星期三*2第六章非線性方程求根數(shù)值分析（NumericalAnalysis）第2頁，共58頁，2023年，2月20日，星期三

非線性科學是當今科學發(fā)展的一個重要研究方向，而非線性方程的求根也成了一個不可缺的內(nèi)容。但是，非線性方程的求根非常復雜。無窮組解無解一個解兩個解四個解一、引言*3第3頁，共58頁，2023年，2月20日，星期三求根問題包括下面三個問題：

根的存在性：即f(x)=0有沒有根？若有，有幾個根？

哪兒有根？確定有根區(qū)間

根的精確化：已知一個根的近似值后，能否將它精確到足夠精度？*4第4頁，共58頁，2023年，2月20日，星期三【定理1】設(shè)函數(shù)f(x)在區(qū)間[a,b]上連續(xù)，如果f(a)

f(b)<0，

則方程f(x)=0在[a,b]內(nèi)至少有一實根x*。

【定義1】如果存在使得，則稱為方程#的根或函數(shù)的零點。*5第5頁，共58頁，2023年，2月20日，星期三若其中，為正整數(shù)，則當m=1時，稱為方程#的單根或函數(shù)的單零點。稱為方程#的m重根或函數(shù)的m重零點。當時，【定義2】*6第6頁，共58頁，2023年，2月20日，星期三abx*f(x)1．畫出f(x)的略圖，從而看出曲線與x軸交點的位置。2．從左端點x0=a出發(fā)，按某個預先選定的步長h一步一步地向右跨，每跨一步都檢驗每步起點x0和終點x0+h的函數(shù)值，若那么所求的根x*必在x0與x0+h之間，這里可取x0或x0+h作為根的初始近似。二、根的搜索(1)逐步搜索法7*第7頁，共58頁，2023年，2月20日，星期三【例1】考察方程的根。x00.51.01.5f(x)的符號－－－＋步長太大，有根區(qū)間太長，精度得不到保障。步長太小，搜索步數(shù)增多，計算量增大。*8如何選取合適的步長？第8頁，共58頁，2023年，2月20日，星期三abx1x2abx*(2)二分法什么時候停止？每次二分后，設(shè)有根區(qū)間[ak,bk]的中點作為根的近似值，則二分過程中得到近似根的一個序列，該序列必以根為極限。誤差：*9f(x)第9頁，共58頁，2023年，2月20日，星期三算法步驟：1．計算f(x)在有解區(qū)間[a,b]端點處的值，f(a)，f(b)。2．計算f(x)在區(qū)間中點處的值f(x1)。3．判斷若f(x1)=0，則x1即是根，否則檢驗：（1）若f(x1)與f(a)異號，則知解位于區(qū)間[a,x1]，

b1=x1,a1=a;（2）若f(x1)與f(a)同號，則知解位于區(qū)間[x1,b]，

a1=x1,b1=b。反復執(zhí)行步驟2、3，便可得到一系列有根區(qū)間：

(a,b),(a1,b1),…,(ak,bk),…*10第10頁，共58頁，2023年，2月20日，星期三4、當時，則，即為根的近似①簡單;②對f(x)

要求不高(只要連續(xù)即可).①無法求復根及偶重根②收斂慢*11第11頁，共58頁，2023年，2月20日，星期三定義f(x)f(a)

f(b)>0f(a)

f(b)=0f(a)=0打印b,k打印a,k結(jié)束是是是否否否m=(a+b)/2|a-b|<f(a)f(m)>0打印m,ka=mb=m結(jié)束k=k+1是是否否輸入k=012*第12頁，共58頁，2023年，2月20日，星期三【例2】

求方程在區(qū)間(1.0,1.5)內(nèi)的一個實根，要求準確到小數(shù)點后的第二位。kakbkxkf(xk)的符號01.01.51.25-11.251.51.375+21.251.3751.3125-31.31251.3751.3438+41.31251.34381.3281+51.31251.32811.3203-61.32031.32811.3242-*13第13頁，共58頁，2023年，2月20日，星期三1．簡單迭代法f(x)=0x=g(x)等價變換三、迭代法f(x)的根g(x)的不動點從一個初值x0出發(fā)，計算x1=g(x0),x2=g(x1),…,xk+1=g(xk),…,若收斂，即存在x*，使得

，且g連續(xù)，則由可知x*=g(x*)，即x*是g的不動點，也就是f

的根。思路*14第14頁，共58頁，2023年，2月20日，星期三x1=0.4771x2=0.3939 …x6=0.3758x7=0.3758迭代過程的收斂性?【例3】求方程的一個根。迭代格式*15第15頁，共58頁，2023年，2月20日，星期三xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p1*16第16頁，共58頁，2023年，2月20日，星期三【定理2】如果

(x)滿足下列條件 （1）當x[a,b]時，(x)[a,b]

（2）對任意x[a,b]，存在0<L<1，使

則迭代過程對任意初值x0[a,b]時，迭代序列xk+1=

(xk)

(k=0,1,…)收斂于x*,

[注]此處L可以看成是在區(qū)間[a,b]內(nèi)的上界。迭代法的結(jié)束條件*17且有誤差估計第17頁，共58頁，2023年，2月20日，星期三求方程在內(nèi)的根【例】。解：原方程可以等價變形為下列三種迭代格式*18第18頁，共58頁，2023年，2月20日，星期三由迭代格式（1）

取初值得：

結(jié)果是發(fā)散的？！*19第19頁，共58頁，2023年，2月20日，星期三由迭代格式（2）

取初值得

結(jié)果精確到4位有效數(shù)字，迭代到得到收斂結(jié)果。

10步才能得到收斂的結(jié)果！*20第20頁，共58頁，2023年，2月20日，星期三

由迭代格式（3）

取初值得

結(jié)果精確到4位有效數(shù)字，迭代到得到收斂結(jié)果。4步就能得到收斂的結(jié)果了！*21第21頁，共58頁，2023年，2月20日，星期三迭代格式（1）的迭代函數(shù)為

求導得

當時故迭代格式（1）是發(fā)散的。結(jié)果分析:*22第22頁，共58頁，2023年，2月20日，星期三

迭代格式（2）的迭代函數(shù)為

當時由*23第23頁，共58頁，2023年，2月20日，星期三知當時，

所以迭代格式（2）是收斂的。*24第24頁，共58頁，2023年，2月20日，星期三迭代格式（3）的迭代函數(shù)為當時

*25第25頁，共58頁，2023年，2月20日，星期三由時，

知當所以迭代格式（3）也是收斂的。*26第26頁，共58頁，2023年，2月20日，星期三【結(jié)論】

通過以上算例可以看出對迭代函數(shù)所得到的若小于1，則收斂；且上界越小收斂速度越快。求導，的上界若是大于1，則迭代格式發(fā)散；*27【定義】若存在的某個鄰域，使迭代過程對于任意初值均收斂，則稱迭代過程在鄰近具有局部收斂性?！径ɡ?】設(shè)為方程的根，在的鄰近連續(xù)且,則迭代過程在鄰近具有局部收斂性。第27頁，共58頁，2023年，2月20日，星期三*28P1611,3作業(yè)第28頁，共58頁，2023年，2月20日，星期三2．迭代公式的加工29對于收斂的迭代過程，只要迭代足夠多次，就可以使結(jié)果達到任意的精度。但有的迭代過程收斂緩慢，計算量很大，因此我們需要對迭代過程加速。加速思想設(shè)是根的某個預測值，用迭代公式得由微分中值定理可得：假定改變不大，近似取某個近似值，則由得：可以期望是比更好的近似值（改進值）。*第29頁，共58頁，2023年，2月20日，星期三30校正：改進：缺點：其中要用到的有關(guān)信息，實際使用不便！再次修改：由聯(lián)立得：因此：校正：改進：再校正：艾特肯方法！*第30頁，共58頁，2023年，2月20日，星期三1.牛頓法的迭代公式原理：將非線性方程線性化—Taylor展開取x0

x*，將f(x)在x0

做一階Taylor展開:，在x0

和x

之間。*31四、牛頓法（切線法）

考慮非線性方程將x=x*代入第31頁，共58頁，2023年，2月20日，星期三將(x*

x0)2

看成高階小量，則有：只要f

C1，且每步迭代都有f'(xk)0，而且則

x*就是f(x)的根。公式（1）稱為牛頓迭代公式。(1)構(gòu)造迭代公式*32P151Newton法的計算步驟！第32頁，共58頁，2023年，2月20日，星期三x*x0x1x2xyf(x)2、牛頓法的幾何意義*33第33頁，共58頁，2023年，2月20日，星期三

3．牛頓法的收斂性【定義】由某方法確定的序列{xk}收斂于方程的根x*，如果存在正實數(shù)p，使得

（C為非零常數(shù)）則稱序列{xk}收斂于x*的收斂速度是p階的，或稱該方法具有p

階收斂速度。當p=1時，稱該方法為線性（一次）收斂；當p>1時，稱方法為超線性收斂。當p=2時，稱方法為平方（二次）收斂；34*第34頁，共58頁，2023年，2月20日，星期三35【定理4】對于迭代過程，如果在所求根的附近連續(xù)，且：則該迭代過程在點附近是p階收斂的。

迭代過程收斂速度依賴于迭代函數(shù)的選取；

當時，，則該迭代過程的收斂速度只可能是線性的；

當x*是單根時，牛頓法在x*附近至少是平方收斂的？？？*第35頁，共58頁，2023年，2月20日，星期三注：Newton法的收斂性依賴于x0

的選取。x*x0x0x0*36第36頁，共58頁，2023年，2月20日，星期三4、牛頓法的應(yīng)用舉例對任給的正數(shù)a,應(yīng)用牛頓法解二次方程，可導出開平方的值。

*37選取迭代格式為這種迭代格式對任意的初值都是收斂的！【例】求，取x0=10第37頁，共58頁，2023年，2月20日，星期三5、牛頓法的變形--牛頓下山法計算：使得具有單調(diào)性：滿足這項要求的算法稱之為下山法。將牛頓法和下山法結(jié)合起來使用，即可在下山法保證函數(shù)值穩(wěn)定下降的前提下，用牛頓法加快收斂速度。

其中的稱為下山因子。下山因子的選擇是個逐步搜索的過程。從開始反復將其減半，如果能找到值使得單調(diào)性條件成立，則稱“下山成功”，否則“下山失敗”。保證全局收斂！*38第38頁，共58頁，2023年，2月20日，星期三*39P161-1625,7(1)(2),12,13作業(yè)第39頁，共58頁，2023年，2月20日，星期三*40實驗二

實驗名稱：函數(shù)逼近與數(shù)據(jù)擬合實驗目的：考察學生綜合運用Matlab進行編程的能力。根據(jù)最佳平方逼近及最小二乘算法要求，自行設(shè)計編程方案，實現(xiàn)算法。掌握Matlab中的polyfit、lsqcurvefit、nlinfit等函數(shù)，并用這些函數(shù)解決實際問題第40頁，共58頁，2023年，2月20日，星期三*41實驗任務(wù)：寫出相應(yīng)的MATLAB程序給出實驗結(jié)果對實驗結(jié)果進行分析和討論寫出相應(yīng)的實驗報告實驗步驟：用Matlab語言實現(xiàn)最佳平方逼近及最小二乘算法X=[0.1,0.2,0.15,0,-0.2,0.3],Y=[0.95,0.84,0.86,1.06,1.50,0.72]。用以上數(shù)據(jù)擬合非線性函數(shù)y=aebx第41頁，共58頁，2023年，2月20日，星期三五、弦截法與拋物線法421.引入

用牛頓法求方程f(x)=0的根時，每步除計算f(xk)外還要算f(xk)，當函數(shù)f(x)比較復雜時，計算f(x)往往比較困難。那么我們能否利用已知的信息，例如：xk,xk-1，xk-2,…,及其函數(shù)值f(xk),f(xk-1),f(xk-2),…,來回避導數(shù)值f(xk)的計算呢？本節(jié)的兩種方法是建立在插值原理基礎(chǔ)上的?；貞浺幌虏逯捣?！設(shè)是的一組近似根，我們利用函數(shù)值構(gòu)造插值多項式Pr(x)，并適當選取用Pr(x)=0的根作為方程f(x)=0的新的近似根xk+1。當r=1時，就是弦截法，當r=2時，就是拋物線法。

*第42頁，共58頁，2023年，2月20日，星期三設(shè)是的近似根，我們利用構(gòu)造一次插值多項式P1(x)，并用P1(x)=0的根作為方程f(x)=0的新的近似根xk+1，由于因此有:2、弦截法（割線法）差商？與導數(shù)的關(guān)系？*43第43頁，共58頁，2023年，2月20日，星期三這樣導出的迭代公式(2)可以看做牛頓公式中的導數(shù)用差商取代的結(jié)果.(2)式有幾何意義嗎？*44第44頁，共58頁，2023年，2月20日，星期三Ox*xk+1xkPkxk-1yPk-1按(2)式求得xk+1實際上是兩點弦線與x軸交點的橫坐標。這種算法因此而形象地稱為弦截(雙點割線)法.f(x)每步只用一個新點xk的值，此方法稱為單點割線法。如果把(2)式中的xk-1改為x0，即迭代公式為，即：*45第45頁，共58頁，2023年，2月20日，星期三線性化

切線法只用到前一步的函數(shù)值，而弦截法需要用到前兩步的函數(shù)值。其收斂速度一般比牛頓法慢，但比線性收斂的方法快。在與牛頓法具有同等的前提下，弦截法具有局部收斂性，并且收斂階由于弦截法是兩步法，它不屬于不動點迭代，因此不能用不動點迭代理論證明它的收斂性。*46【P154例】用弦截法解方程

弦截法和切線法的聯(lián)系和區(qū)別：第46頁，共58頁，2023年，2月20日，星期三計算結(jié)果表k

xk

xk-xk-100.510.60.120.56532-0.0346830.567090.0017740.567140.00005從表中可以看出弦截法的收斂速度也是相當快的，迭代到第4步就得到精度的結(jié)果。解1：*47第47頁，共58頁，2023年，2月20日，星期三取初值x0=0.5，牛頓法迭代結(jié)果見下表k0123xk0.50.571020.567160.56714*48解2：第48頁，共58頁，2023年，2月20日，星期三【定理6.4】假設(shè)f(x)在根x*的鄰域內(nèi)具有二階連續(xù)導數(shù)，且對于任意，有，又初值，那么當鄰域充分小時，弦截法將按階收斂到根x*。*49弦截法是超線性收斂的！第49頁，共58頁，2023年，2月20日，星期三3、

拋物線法

設(shè)已知方程f(x)=0的三個近似根xk,xk-1,xk-2，我們以這三點為插值節(jié)點構(gòu)造二次插值多項式P2(x)，并適當選取P2(x)的一個零點xk+1作為新的近似根，這樣確定的迭代過程稱為拋物線法，亦稱為密勒(Müller)法.在幾何圖形上,這種方法的基本思想是用拋物線y=P2(x)與x軸的交點xk+1作為所求根x*的近似位置。*50第50頁，共58頁，2023年，2月20日，星期三yxk-2xk-1xkxk+1xy=f(x)y=P2(x)x*O拋物線法的幾何意義*第51頁，共58頁，2023年，2月20日，星期三下面推導拋物線法的計算公式。插值多項式有兩個零點式中P2(x)與x

軸有兩個交點，取哪個點？在xk,xk-1,xk-2三個近似值中，自然假定xk更接近所求的根x*，這時，為了保證精度，我們選(3)式中接近xk的一個值作為新的近似根xk+1。為此，只要取根式前的符號與ω的符號相同.*52第52頁，共58頁，2023年，2月20日，星期三【例】用拋物線法求解方程f(x)=xex-1=0。

解：取x0=0.5,x1=0.6,x2=0.56532開始，計算得f(x0