非線性方程的數(shù)值解法-課件

第二章非線性方程的數(shù)值解法 非線性方程:f(x)=0包括：代數(shù)方程（多項(xiàng)式）、超越方程（三角函數(shù)、指數(shù)函數(shù)或?qū)?shù)函數(shù)）。求解方法：直接求解法、間接求解法；直接求解法一般為解析法，能夠得到精確解，如二次方程求根公式等。簡(jiǎn)單但不一定總有效。間接求解法一般較復(fù)雜，可以利用計(jì)算機(jī)進(jìn)行計(jì)算，其結(jié)果為近似解，但誤差可以控制。1ppt課件非線性方程求解的基本問題：根的個(gè)數(shù)；根的位置。求解方程的根，一般有兩種情形：求出在給定范圍內(nèi)的某個(gè)根求出方程的全部根，而根的數(shù)目和位置事先不知道求解方程的根，需要解決的問題：根的存在性，根的個(gè)數(shù)根的隔離根的精細(xì)化2ppt課件求非線性方程根的一些常用方法：區(qū)間搜索法（逐步搜索法、二分法）迭代法牛頓法弦截法3ppt課件2.1區(qū)間搜索法預(yù)備知識(shí)：方程的根：?jiǎn)胃?、重根。根的存在性定理：定理：若f

在[a,b]上連續(xù)，且f(a)·f(b)<0，則f

在(a,b)上必有一根；若

f在[a,b]上連續(xù)且單調(diào)則f在(a,b)上有且僅有一根。定理函數(shù)f(x)對(duì)于x*

有f(x*)=0，但則稱為方程的單根。如果有但，則稱是方程的

m重根。4ppt課件abx*f(x)1．畫出f(x)

的略圖，從而看出曲線與x軸交點(diǎn)的位置。2．從左端點(diǎn)x=a出發(fā)，按某個(gè)預(yù)先選定的步長(zhǎng)h一步一步地向右跨，每跨一步都檢驗(yàn)每步起點(diǎn)x0和終點(diǎn)x0+h的函數(shù)值，若那么所求的根x*必在x0與x0+h之間，這里可取x0或x0+h作為根的初始近似。2.1.2逐步搜索法5ppt課件

開始讀入a,ha

x0f(x0)

y0x0+h

x0f(x0)

y0>0打印結(jié)束否是繼續(xù)掃描

6ppt課件例1：考察方程x0123456f(x)的符號(hào)--++--+計(jì)算速度慢，一般用于確定根的位置7ppt課件二分法的步驟：

二分法abx0x1a1x*b12.1.3區(qū)間二分法思路：二分法的基本思想就是逐步對(duì)分區(qū)間,經(jīng)過對(duì)根的搜索，將有根區(qū)間的長(zhǎng)度縮小到充分小，從而求出滿足精度的根的近似值。8ppt課件

執(zhí)行步驟1．計(jì)算f(x)在有解區(qū)間[a,b]端點(diǎn)處的值，f(a)，f(b)。2．計(jì)算f(x)在區(qū)間中點(diǎn)處的值f(x0)。3．判斷若f(x0)=0，則x0即是根，否則檢驗(yàn)：（1）若f(x0)與f(a)異號(hào)，則知解位于區(qū)間[a,x0]，

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

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

(a,b),(a1,b1),…,(ak,bk),…9ppt課件4、當(dāng)時(shí)5、則即為根的近似①簡(jiǎn)單;②對(duì)f(x)

要求不高(只要連續(xù)即可)；③事先可以估計(jì)出迭代次數(shù)。①無(wú)法求復(fù)根及偶重根②收斂慢③已知含根區(qū)間。10ppt課件

每次二等分后，設(shè)取有根區(qū)間的中點(diǎn)作為根的近似值，則在二分過程中可以獲得一個(gè)近似根的序列，該序列以根為極限。誤差

分析：

若取區(qū)間的中點(diǎn)作為的近似值，則誤差估計(jì)為：所以在實(shí)際計(jì)算時(shí)，只要二分足夠多次，便有。這里，為預(yù)定精度。

二分法11ppt課件注：用二分法求根，最好先給出f(x)

草圖以確定根的大概位置。或用搜索程序，將[a,b]分為若干小區(qū)間，對(duì)每一個(gè)滿足f(ak)·f(bk)<0的區(qū)間調(diào)用二分法程序，可找出區(qū)間[a,b]內(nèi)的多個(gè)根，二分法對(duì)于給定的精度

,可估計(jì)二分法所需的步數(shù)k：12ppt課件定義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=013ppt課件應(yīng)用： 例、設(shè) ，求x=?

解：所以，x=2.101562502-3+2.5+112-2.5+2.25+0.522-2.25+2.125+0.2532-2.125+2.0625-0.12542.0625-2.125+2.09375-0.062552.09375-2.125+2.109375+0.0312562.093752.1093752.10156250.01562514ppt課件2.2迭代法（不動(dòng)點(diǎn)迭代法）2.2.1迭代原理2.2.2迭代的收斂性2.2.3迭代的收斂速度2.2.4迭代的加速（不講）15ppt課件2.2迭代法（不動(dòng)點(diǎn)迭代）f(x)=0x=φ(x)等價(jià)變換f(x)的根φ

(x)的不動(dòng)點(diǎn)思路從一個(gè)初值x0

出發(fā),計(jì)算x1=φ(x0),x2=φ(x1),…,xk+1=φ(xk),…若收斂，即存在x*使得

，只要φ

連續(xù)，則，也就是x*=φ(x*)，即x*是φ

的根，也就是f

的根。若｛xk｝發(fā)散，則迭代法失敗。2.2.1迭代法原理：16ppt課件

迭代法：是一種逐次逼近的方法。它是用某個(gè)固定公式反復(fù)校正根的近似值，使之逐步精確，最后得到滿足精度要求的結(jié)果。xk+1=φ(xk)稱為迭代格式，φ(x)稱為迭代函數(shù)x0

稱為迭代初值,數(shù)列稱為迭代序列

迭代法思想：將隱式方程的求根問題歸結(jié)為計(jì)算一組顯式xk+1=φ(xk)

，也就是說，迭代過程是一個(gè)逐步顯式化的過程。x=φ(x)17ppt課件1、例題：求 在1附近的根。 解：[方法1]

由題意可得到下面求解迭代方式：

計(jì)算結(jié)果如下所示：01234511.31951.33991.34121.34131.3413終止條件取初值結(jié)論：求18ppt課件[方法2]01231-2-35-52521878失敗迭代方式計(jì)算結(jié)果：19ppt課件2.2.2迭代法的收斂性20ppt課件xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=φ(x)y=φ(x)y=φ(x)y=φ(x)x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p1簡(jiǎn)單迭代法0<k<1-1<k<0k>1k<-121ppt課件收斂定理考慮方程x=φ(x),φ(x)在[a,b]上連續(xù),若(I)對(duì)所有x[a,b]，有φ

(x)[a,b]；(II)存在

0<L<1，使所有

x[a,b]有|φ’(x)|L<1。則：1）方程x=φ(x)在[a,b]上的解x*存在且唯一。

2）任取x0[a,b]，由迭代過程xk+1=φ

(xk)收斂于x*簡(jiǎn)單迭代法推論驗(yàn)后誤差估計(jì)：誤差估計(jì)式：驗(yàn)前誤差估計(jì)：22ppt課件證明：①φ

(x)在[a,b]上有根？令有根②根唯一？反證：若不然，設(shè)還有，則在和之間。而③當(dāng)k

時(shí)，

xk收斂到x*？3簡(jiǎn)單迭代法有根L<123ppt課件④⑤可用來控制收斂精度L越收斂越快小注：定理?xiàng)l件非必要條件，對(duì)某些問題在區(qū)間[a,b]上不滿足|φ’(x)|L<1，迭代也收斂。實(shí)際應(yīng)用中還是用此定理判斷收斂性，當(dāng)不滿足收斂條件時(shí)，改變迭代公式使之滿足。3簡(jiǎn)單迭代法24ppt課件例題例：證明函數(shù)在區(qū)間[1，2]上滿足迭代收斂條件。證明：25ppt課件例題

26ppt課件例題若取迭代函數(shù)，不滿足收斂定理，故不能肯定收斂到方程的根。27ppt課件迭代法局部收斂性

對(duì)以上定理中的條件⑴，所有，，一般不容易驗(yàn)證。實(shí)際使用迭代法時(shí)，通?？偸窃诟?/p>

的鄰域進(jìn)行。

定義如果存在的某個(gè)鄰域，是任意指定的正數(shù)，使迭代過程對(duì)于任意初值1均收斂，則迭代過程在根鄰域具有局部收斂性。

28ppt課件

證:

由于，存在的充分小鄰域，使成立，據(jù)微分中值定理，有:

注意到，又當(dāng)時(shí)，故有:

由收斂定理的條件⑴可以斷定對(duì)于任意收斂。局部收斂性定理：設(shè)函數(shù)在的根鄰近有連續(xù)的一階導(dǎo)數(shù)，且，則迭代過程具有局部收斂性。29ppt課件由于在實(shí)際應(yīng)用中根

x*

事先不知道，故條件

|φ′(x*)|<1無(wú)法驗(yàn)證。但已知根的初值x0在根

x*鄰域，又根據(jù)φ′(x)的連續(xù)性，則可采用

|φ′(x0)|<1來代替|φ′(x*)|<1，判斷迭代的收斂性。

30ppt課件2.2.3迭代過程的收斂速度迭代過程的收斂速度，是指在收斂時(shí)迭代誤差的下降速度。

定義：設(shè)迭代過程

收斂于

的根，令迭代誤差，若存在常數(shù)和，使

則稱序列是階收斂的，稱漸近誤差常數(shù)。

收斂速度是誤差的收縮率，階數(shù)越高，收斂得越快。特別地，時(shí)稱線性收斂，時(shí)稱平方收斂或二次收斂，時(shí)稱超線性收斂。迭代法的收斂速度常用收斂階表示31ppt課件

定理對(duì)迭代過程，若在所求根的鄰域連續(xù)，且則迭代過程在鄰域是階收斂的.證:p33Q:

如何實(shí)際確定收斂階？32ppt課件2.3牛頓迭代法2.3.1迭代公式的建立2.3.2牛頓迭代法的收斂情況2.3.3牛頓迭代法的修正法(了解)33ppt課件2.3牛頓法原理：將非線性方程線性化

——Taylor展開取x0

x*，將f(x)在x0

做一階Taylor展開:，在x0

和x*

之間。將(x*

x0)2

看成高階小量，則有：線性xyx*x0x1迭代公式：迭代函數(shù)：34ppt課件牛頓切線法2.3.2牛頓切線法的收斂情況

定理

（局部收斂性）設(shè)函數(shù)在包含的某鄰域內(nèi)有階連續(xù)導(dǎo)數(shù)，是方程的單根，則當(dāng)初值充分接近時(shí)，牛頓切線法收斂，且至少為二階收斂。并有這里單根意味著：35ppt課件牛頓切線法2.3.2牛頓迭代法的收斂情況

定理設(shè)函數(shù)滿足且在鄰域連續(xù)，則牛頓迭代法在收斂，且至少為二階收斂。并有36ppt課件牛頓切線法證明：牛頓法事實(shí)上是一種特殊的不動(dòng)點(diǎn)迭代其中，則收斂由Taylor展開：只要f’(x*)0在單根附近收斂快37ppt課件牛頓切線法注：牛頓法收斂性依賴于x0

的選取。x*x0x0x0具有局部恒收斂性，收斂性依賴于初值的選取。收斂性好（至少平方收斂）每次計(jì)算要計(jì)算導(dǎo)數(shù)，效率不高牛頓法特點(diǎn)：38ppt課件例題例1:用Newton法求的近似解。（取8位有效數(shù)字）。解：由根存在定理。39ppt課件例題40ppt課件Newton迭代法算法41ppt課件牛頓切線法改進(jìn)牛頓法的改進(jìn)與推廣改進(jìn)一：重根時(shí)的收斂速度及改進(jìn)：Q1:

若，牛頓法是否仍收斂？設(shè)x*是f

的m

重根，則：且。因?yàn)榕ｎD法事實(shí)上是一種特殊的不動(dòng)點(diǎn)迭代，其中，則A1:

有局部收斂性，收斂慢（線性收斂）。Q2:

如何加速重根的收斂？A2:

修正迭代格式（平方收斂）m證明過程見書p4342ppt課件改進(jìn)二：

牛頓下山法——擴(kuò)大初值范圍的修正牛頓法：

原理：若由xk

得到的xk+1不能使|f|減小，則在xk和xk+1之間找一個(gè)更好的點(diǎn)，使得。xkxk+1通過適當(dāng)選取的保證函數(shù)值能單調(diào)下降牛頓切線法改進(jìn)下山法：迭代過程中保證函數(shù)值單調(diào)下降，即牛頓下山法：將牛頓法與下山法結(jié)合使用的算法下山因子43ppt課件牛頓下山法幾點(diǎn)討論實(shí)用中從=1開始反復(fù)將減半計(jì)算。一旦單調(diào)下降則稱“下山成功”。反之則稱“下山失敗”，需另選初值x0計(jì)算。牛頓切線法改進(jìn)當(dāng)≠

1時(shí)。牛頓下山法只有線性收斂速度，但對(duì)初值的選取卻可放的很寬。常用牛頓下山法選取初值。實(shí)用中常用牛頓下山法選取初值。為加快收斂速度，轉(zhuǎn)入牛頓法來求解根的精確值。44ppt課件牛頓法每一步要計(jì)算f

和f’，相當(dāng)于2個(gè)函數(shù)值，且有些導(dǎo)數(shù)難求。為了避開導(dǎo)數(shù)的計(jì)算，用差商代替導(dǎo)數(shù)。x0切線

割線

切線斜率

割線斜率2.4弦截法x2x145ppt課件用割線斜率（差商）替換切線斜率，代入牛頓法迭代公式：上式中，固定弦的一個(gè)端點(diǎn)（x0,f(x0)），而另一端點(diǎn)變動(dòng)，稱為單點(diǎn)弦法。2.4.1單點(diǎn)弦法：46ppt課件單點(diǎn)弦法幾何意義：x0x1x2x3x4xf(x)47ppt課件因?yàn)閒(x*)=0，故求導(dǎo)數(shù)得

所以0<’(x*)<1，所以單點(diǎn)弦法僅為線性收斂。單點(diǎn)弦法收斂速度：迭代函數(shù)：當(dāng)初值x0充分接近時(shí)很接近f’(x*)48ppt課件2.4.2雙點(diǎn)弦法：為了加快收斂速度，弦的兩個(gè)端點(diǎn)都在變動(dòng)，稱為雙點(diǎn)弦法或稱快速弦截法。迭代時(shí)需要2個(gè)初值xk

和xk－1。雙點(diǎn)弦法迭代公式：49ppt課件快速弦截法的幾何意義：x0x1x2x3x4xf(x)50ppt課件雙點(diǎn)弦法收斂速度：

雙點(diǎn)弦截法的收斂性與牛頓迭代法一樣，即在根的某個(gè)鄰域內(nèi)，f(x)有直至二階的連續(xù)導(dǎo)數(shù)，且f’(x*)0，具有局部收斂性，同時(shí)在鄰域任取初值x0、x1，迭代均收斂。

可以證明，雙點(diǎn)弦截法具有超線性斂速度，收斂的階為：51ppt課件

例

用Newton法和弦截法解下面方程的根，并比較

解:由Newton法由弦截法52ppt課件x0=0.5;x1=0.4;x2=0.3430962343x3=0.3473897274x4=0.3472965093x5=0.3472963553x6=0.3472963553Newton法由弦截法要達(dá)到精度10-8弦截法迭代5次Newton迭代法迭代4次x0=0.5;x1=0.3333333333x2=0.3472222222x3=0.3472963532x4=0.347296355353ppt課件

解非線性方程組通常有兩類方法：一類屬于線性化方法，即將非線性方程組用一組線性方程來近似，由此構(gòu)造一種迭代格式，用逐次逼近真實(shí)解，這類方法有牛頓法及各種改進(jìn)方法；另一類屬于求函數(shù)極小值的方法，即由這些非線性函數(shù)構(gòu)造一個(gè)模函數(shù)，例如構(gòu)造非線性方程組的一般形式為：于是解非線性方程組歸結(jié)為求φ的極小值點(diǎn)，此極小值點(diǎn)即非線性方程組的一組解，這類方法有梯度法（最速下降法）。其中，牛頓法是解非線性代數(shù)方程組最常見的方法。2.5解非