第7章非線性方程迭代解法1．根的存在性。方程有沒(méi)有根？假如有根，有幾個(gè)根？2．這些根大致在哪里？如何把根隔離開(kāi)來(lái)？3．根的精確化本章介紹求解非線性方程f(x)=0的幾種常見(jiàn)和有效的數(shù)值方法.其中(x)是高次多項(xiàng)式函數(shù)或超越函數(shù).如

(x)=3x5-2x4+8x2-7x+1(x)=e2x+1-xln(sinx)-2等等.1科大探討生學(xué)位課程數(shù)值分析7.1根的搜尋與二分法求非線性方程確定方程的有根區(qū)間計(jì)算根的近似值f(x)=0的根的方法分為兩步：2科大探討生學(xué)位課程數(shù)值分析首先確定有限區(qū)間：依據(jù)零點(diǎn)定理。設(shè)，且，則方程在區(qū)間上至少有一個(gè)根。假如在上恒正或恒負(fù)，則此根唯一。3科大探討生學(xué)位課程數(shù)值分析等步長(zhǎng)掃描法求有根區(qū)間

用計(jì)算機(jī)求有根區(qū)間：等步長(zhǎng)掃描法。設(shè)h>0是給定的步長(zhǎng)，取x0=a,x1=a+h，若f(x0)*f(x1)<0則掃描成功；否則令x0=x1,x1=x0+h，接著上述方法，直到成功。假如x1>b則掃描失敗。再將h縮小，接著以上步驟。4科大探討生學(xué)位課程數(shù)值分析等步長(zhǎng)掃描算法

算法：（求方程f(x)=0的有根區(qū)間）(1)輸入a,b,h；(2)f0=f(a)；(3)x=a+h,f1=f(x),若x>b輸出失敗信息，停機(jī)。(4)若f1=0,輸出x，已算出方程的一個(gè)根，停機(jī)。(5)若f0f1<0.輸出a,x,[a,x]為有根區(qū)間，停機(jī)(6)a=x，轉(zhuǎn)3）注：假如對(duì)足夠小的步長(zhǎng)h掃描失敗。說(shuō)明：在[a,b]內(nèi)無(wú)根在[a,b]內(nèi)有偶重根具體看書(shū)上Matlab程序P148看例7.15科大探討生學(xué)位課程數(shù)值分析用二分法(將區(qū)間對(duì)平分)求解。令a1=a,b1=b,c1=(a1+b1)/2若f(a1)f(c1)<0，則[a1,c1]為有根區(qū)間，否則[c1,b1]為有根區(qū)間記新的有根區(qū)間為[a2,b2]，則[a1,b1]包含[a2,b2]，且b2-a2=(a1+b1)/2二分法對(duì)[a2,b2]重復(fù)上述做法得6科大探討生學(xué)位課程數(shù)值分析設(shè)所求的根為x*，則即取為x*的近似解

二分法7科大探討生學(xué)位課程數(shù)值分析求方程f(x)=0的根的二分法算法(2)置x:=(a+b)/2,(3)若f(x)=0，輸出x，停算；否則，轉(zhuǎn)步(4);(4)若f(a)f(b)<0，則置b:=x；否則，置a:=x;(5)置x:=(a+b)/2,若|b-a|<,輸出x，停算，否則，轉(zhuǎn)步(3).參看教材程序P1508科大探討生學(xué)位課程數(shù)值分析誤差分析：第1步產(chǎn)生的有誤差第k步產(chǎn)生的xk

有誤差對(duì)于給定的精度,可估計(jì)二分法所需的步數(shù)k：①簡(jiǎn)潔;②對(duì)f(x)要求不高(只要連續(xù)即可).①無(wú)法求復(fù)根及偶重根②收斂慢注：用二分法求根，最好先給出f(x)草圖以確定根的或許位置。或用搜尋程序，將[a,b]分為若干小區(qū)間，對(duì)每一個(gè)滿足f(ak)·f(bk)<0的區(qū)間調(diào)用二分法程序，可找出區(qū)間[a,b]內(nèi)的多個(gè)根，且不必要求f(a)·f(b)<0。9科大探討生學(xué)位課程數(shù)值分析7.2簡(jiǎ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*是

的不動(dòng)點(diǎn)，也就是f的根。10科大探討生學(xué)位課程數(shù)值分析迭代法需解決的三個(gè)問(wèn)題迭代函數(shù)的構(gòu)造由迭代函數(shù)產(chǎn)生的解序列的收斂性序列的收斂速度和誤差估計(jì)11科大探討生學(xué)位課程數(shù)值分析迭代法的幾何意義交點(diǎn)的橫坐標(biāo)y=xy=(x)12科大探討生學(xué)位課程數(shù)值分析例1試用迭代法求方程在區(qū)間(1，2)內(nèi)的實(shí)根。解：由建立迭代關(guān)系

k=0,1,2,3…….計(jì)算結(jié)果如下:精確到小數(shù)點(diǎn)后五位13科大探討生學(xué)位課程數(shù)值分析但假如由建立迭代公式仍取，則有，明顯結(jié)果越來(lái)越大，是發(fā)散序列.14科大探討生學(xué)位課程數(shù)值分析xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=(x)y=(x)y=(x)y=(x)x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p115科大探討生學(xué)位課程數(shù)值分析定理考慮方程x=(x),(x)C1[a,b],若(I)當(dāng)x[a,b]時(shí)，(x)[a,b]；(II)0L<1使得|’(x)|L<1對(duì)x[a,b]成立。則任取x0[a,b]，由xk+1=(xk)得到的序列收斂于(x)在[a,b]上的唯一不動(dòng)點(diǎn)。并且有誤差估計(jì)式：(k=1,2,…)且存在極限k16科大探討生學(xué)位課程數(shù)值分析證明：①(x)在[a,b]上存在不動(dòng)點(diǎn)？令有根②不動(dòng)點(diǎn)唯一？反證：若不然，設(shè)還有，則在和之間。而③當(dāng)k

時(shí)，

xk收斂到x*？17科大探討生學(xué)位課程數(shù)值分析④⑤⑥可用來(lái)控制收斂精度L越收斂越快小注：定理?xiàng)l件非必要條件，可將[a,b]縮小，定義局部收斂性：若在x*的某領(lǐng)域B={x||xx*|}有(x)C1[a,b]且|’(x*)|<1，則由x0B起先的迭代收斂。即調(diào)整初值可得到收斂的結(jié)果。（局部收斂性）18科大探討生學(xué)位課程數(shù)值分析迭代過(guò)程的收斂速度設(shè)由某方法確定的序列{xk}收斂于方程的根x*，假如存在正實(shí)數(shù)p，使得 （C為非零常數(shù)）定義：則稱序列{xk}收斂于x*的收斂速度是p階的，或稱該方法具有p階斂速。稱C為漸進(jìn)常數(shù)。當(dāng)p=1時(shí)，稱該方法為線性（一次）收斂；當(dāng)p=2時(shí)，稱方法為平方（二次）收斂；當(dāng)1<p<2時(shí)，稱方法為超線性收斂。

19科大探討生學(xué)位課程數(shù)值分析Q:如何實(shí)際確定收斂階和漸進(jìn)誤差常數(shù)？定理設(shè)x*為x=(x)的不動(dòng)點(diǎn)，若，p2；，且，則xk+1=(xk)在內(nèi)p階收斂。證明：x*k

C20科大探討生學(xué)位課程數(shù)值分析改進(jìn)、加速收斂

待定參數(shù)法：若|’(x)|1，則將x=(x)等價(jià)地改造為求K，使得例：求在(1,2)的實(shí)根。如果用進(jìn)行迭代，則在(1,2)中有現(xiàn)令希望，即在(1,2)上可取任意，例如K=0.5，則對(duì)應(yīng)即產(chǎn)生收斂序列。21科大探討生學(xué)位課程數(shù)值分析

松弛加速：dwww+<=-+=+++-)()(

,

)

(

)1(

*21*1*1*kkkkkkkkkkkxfxfxxxxxxxxx條件下成立保證如下不等式在確定以此類推。引入松弛因子修正計(jì)算再對(duì)的修正，并計(jì)算作為把，令選取適當(dāng)?shù)乃沙谝蜃?2科大探討生學(xué)位課程數(shù)值分析

Aitken加速：xyy=xy=

(x)x*x0P(x0,x1)x1x2P(x1,x2)一般地，有：比收斂得略快。23科大探討生學(xué)位課程數(shù)值分析

Steffensen（斯蒂芬森）加速：其實(shí)是將原不動(dòng)點(diǎn)迭代計(jì)算兩次合并成一步得到，可改為另一種不動(dòng)點(diǎn)迭代法:將Aitken（埃特金）加速與不動(dòng)點(diǎn)迭代結(jié)合.可得到如下迭代法:24科大探討生學(xué)位課程數(shù)值分析定理

若x*為上式定義的函數(shù)g(x)的不動(dòng)點(diǎn)，則x*為(x)的不動(dòng)點(diǎn).反之，若x*是(x)的不動(dòng)點(diǎn)，設(shè)’’(x)存在,’(x*

)≠0，則x*是(x)的不動(dòng)點(diǎn)且斯蒂芬森迭代法是二階收斂的.(證明略）25科大探討生學(xué)位課程數(shù)值分析例2試用Steffensen算法求解方程解法一、取，由

n=0，1，2，…取初值x0=1.5，計(jì)算結(jié)果如下：nxnynzn01.51.3572088081.33086095911.3248991811.3247523791.32472449621.3247179571.3247179571.32471795726科大探討生學(xué)位課程數(shù)值分析解法二、取，對(duì)于該迭代函數(shù)在一般迭代法中是發(fā)散的，而Steffensen格式卻是收斂的。

n=0，1，2，…取初值x0=1.5，計(jì)算結(jié)果如下：nxnynzn01.52.3751.23964843711.4162929751.8409219155.23887276921.3556504421.4913982792.31727069931.3289487771.3470628831.44435122441.3248044891.3251735441.32711728151.3247179441.3247181521.32471898061.32471795727科大探討生學(xué)位課程數(shù)值分析Steffensen迭代格式幾何說(shuō)明

28科大探討生學(xué)位課程數(shù)值分析Steffensen迭代算法

程序見(jiàn)p159。29科大探討生學(xué)位課程數(shù)值分析7.3常用迭代法－牛頓法原理：將非線性方程線性化——Taylor綻開(kāi)取x0x*，將f(x)在x0做一階Taylor綻開(kāi):，在x0和x之間。將(x*

x0)2看成高階小量，則有：線性

/*linear*/xyx*x0只要f

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

x*就是f的根。30科大探討生學(xué)位課程數(shù)值分析定理（收斂的充分條件）設(shè)f

C2[a,b]，若(1)f(a)f(b)<0；(2)在整個(gè)[a,b]上f”不變號(hào)且f’(x)0；(3)選取x0

[a,b]使得f(x0)f”(x0)>0；則Newton’sMethod產(chǎn)生的序列{xk}收斂到f(x)在[a,b]的唯一根。有根根唯一產(chǎn)生的序列單調(diào)有界，保證收斂。定理（局部收斂性）設(shè)f

C2[a,b]，若x*

為f(x)在[a,b]上的根，且f’(x*)0，則存在x*的鄰域使得任取初值，Newton’sMethod產(chǎn)生的序列{xk}收斂到x*，且滿足31科大探討生學(xué)位課程數(shù)值分析證明：Newton’sMethod事實(shí)上是一種特殊的不動(dòng)點(diǎn)迭代其中，則收斂由Taylor展開(kāi)：只要f’(x*)0，則令可得結(jié)論。在單根/*simpleroot*/旁邊收斂快32科大探討生學(xué)位課程數(shù)值分析Newton’sMethod有，只要就有p

2。至少是二階收斂。算法7.5（牛頓法）取初始點(diǎn)x0，最大迭代次數(shù)N和精度要求eps，置k:=0；(2)計(jì)算xk+1=xk-f(xk)/f’(xk)(3)若|xk+1-xk|<eps,則停算；(4)若k=N,則停算；否則，置k:=k+1,轉(zhuǎn)步2.程序見(jiàn)P161。33科大探討生學(xué)位課程數(shù)值分析例用Newton法計(jì)算。解：34科大探討生學(xué)位課程數(shù)值分析注：Newton’sMethod收斂性依靠于x0的選取。x*x0x0x035科大探討生學(xué)位課程數(shù)值分析牛頓法迭代公式

牛頓法的優(yōu)點(diǎn)

牛頓法是目前求解非線性方程(組)的主要方法至少二階局部收斂，收斂速度較快，特殊是當(dāng)?shù)c(diǎn)充分靠近精確解時(shí)。

牛頓的缺點(diǎn)

對(duì)重根收斂速度較慢（線性收斂）

對(duì)初值的選取很敏感，要求初值相當(dāng)接近真解在實(shí)際計(jì)算中，可以先用其它方法獲得真解的一個(gè)粗糙近似，然后再用牛頓法求解。36科大探討生學(xué)位課程數(shù)值分析改進(jìn)與推廣重根加速收斂法：Q1:若，Newton’sMethod是否仍收斂？設(shè)x*是f的n重根，則：且。因?yàn)镹ewton’sMethod事實(shí)上是一種特殊的不動(dòng)點(diǎn)迭代，其中，則A1:

有局部收斂性，但重?cái)?shù)n越高，收斂越慢。Q2:如何加速重根的收斂？A2:

將求

f

的重根轉(zhuǎn)化為求另一函數(shù)的單根。令，則f的重根=

的單根。37科大探討生學(xué)位課程數(shù)值分析改進(jìn)與推廣Q3:如何加速重根的收斂？A3:

修改迭代函數(shù)，令

有，則改進(jìn)后的迭代法至少具有二階收斂性。38科大探討生學(xué)位課程數(shù)值分析下山法（阻尼牛頓法）——Newton’sMethod

局部微調(diào)：原理：若由xk

得到的xk+1不能使|f|減小，則在xk和xk+1之間找一個(gè)更