第六章 非線性方程求根

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

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

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

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

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

f(b)<0，

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

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

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

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

(a,b),(a1,b1),…,(ak,bk),…*10第10頁(yè)，共58頁(yè)，2023年，2月20日，星期三4、當(dāng)時(shí)，則，即為根的近似①簡(jiǎn)單;②對(duì)f(x)

要求不高(只要連續(xù)即可).①無(wú)法求復(fù)根及偶重根②收斂慢*11第11頁(yè)，共58頁(yè)，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頁(yè)，共58頁(yè)，2023年，2月20日，星期三【例2】

求方程在區(qū)間(1.0,1.5)內(nèi)的一個(gè)實(shí)根，要求準(zhǔn)確到小數(shù)點(diǎn)后的第二位。kakbkxkf(xk)的符號(hào)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頁(yè)，共58頁(yè)，2023年，2月20日，星期三1．簡(jiǎn)單迭代法f(x)=0x=g(x)等價(jià)變換三、迭代法f(x)的根g(x)的不動(dòng)點(diǎn)從一個(gè)初值x0出發(fā)，計(jì)算x1=g(x0),x2=g(x1),…,xk+1=g(xk),…,若收斂，即存在x*，使得

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

的根。思路*14第14頁(yè)，共58頁(yè)，2023年，2月20日，星期三x1=0.4771x2=0.3939 …x6=0.3758x7=0.3758迭代過(guò)程的收斂性?【例3】求方程的一個(gè)根。迭代格式*15第15頁(yè)，共58頁(yè)，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頁(yè)，共58頁(yè)，2023年，2月20日，星期三【定理2】如果

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

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

則迭代過(guò)程對(duì)任意初值x0[a,b]時(shí)，迭代序列xk+1=

(xk)

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

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

取初值得：

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

取初值得

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

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

由迭代格式（3）

取初值得

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

求導(dǎo)得

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

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

當(dāng)時(shí)由*23第23頁(yè)，共58頁(yè)，2023年，2月20日，星期三知當(dāng)時(shí)，

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

*25第25頁(yè)，共58頁(yè)，2023年，2月20日，星期三由時(shí)，

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

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

x*，將f(x)在x0

做一階Taylor展開:，在x0

和x

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

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

x0)2

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

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

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

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

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

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

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

當(dāng)時(shí)，，則該迭代過(guò)程的收斂速度只可能是線性的；

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

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

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

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

實(shí)驗(yàn)名稱：函數(shù)逼近與數(shù)據(jù)擬合實(shí)驗(yàn)?zāi)康模嚎疾鞂W(xué)生綜合運(yùn)用Matlab進(jìn)行編程的能力。根據(jù)最佳平方逼近及最小二乘算法要求，自行設(shè)計(jì)編程方案，實(shí)現(xiàn)算法。掌握Matlab中的polyfit、lsqcurvefit、nlinfit等函數(shù)，并用這些函數(shù)解決實(shí)際問題第40頁(yè)，共58頁(yè)，2023年，2月20日，星期三*41實(shí)驗(yàn)任務(wù)：寫出相應(yīng)的MATLAB程序給出實(shí)驗(yàn)結(jié)果對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析和討論寫出相應(yīng)的實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)步驟：用Matlab語(yǔ)言實(shí)現(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頁(yè)，共58頁(yè)，2023年，2月20日，星期三五、弦截法與拋物線法421.引入

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

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

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

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

xk

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

拋物線法

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

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

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