Chap非線性方程(全)課件

第八章非線性方程的數(shù)值解§1二分法

§2迭代法2.1迭代格式2.2收斂性條件2.3迭代法的收斂階

§3牛頓迭代法

3.1迭代格式3.2迭代法的收斂階§4弦割法

xyoab*x*瞳礙鯨幸陳諄喳內(nèi)枷祥泳柒板寧未斷壕硬怔輛映徽拙春娜物陡勻啪摧慶誤Chap非線性方程(全)Chap非線性方程(全)1/3/20231第八章非線性方程的數(shù)值解§1二分法xyoab*x*瞳這種方程往往無法求得其精確解，只能通過數(shù)值方法求其近似解。這里我們將介紹兩種數(shù)值方法：非線性方程求根是我們經(jīng)常碰到的問題，例如：(1).二分法;(2).迭代法：一般迭代法、牛頓迭代法、弦截法.趕辟怖柿蔡俞雹外確昧量劍勞邵央桐療酵謊繁吻毋徑坑僑繃既留丁綱胎暮Chap非線性方程(全)Chap非線性方程(全)1/3/20232這種方程往往無法求得其精確解，只能通過數(shù)值方法求其近似解。這§1二分法對于

f(x)=0

（8.1）

設(shè)

f(x)∈C[a,b]

，且

f(a)f(b)<0

，則知（8.1）在(a,b)內(nèi)至少有一實根x*。如果在(a,b)內(nèi)有(8.1)的唯一實根x*：則可以用二分法進行求解，求解的步驟如下：xyoab*x*贈踢躊斌夯漸扎蘆刀雹吐閱酷菠澳慰潰碳務(wù)務(wù)喂鰓齋犀儡岡埠蘇繃黃汀殷Chap非線性方程(全)Chap非線性方程(全)1/3/20233§1二分法對于f(x)=0Step1計算f(a)、f(b)及

若令a1=a,若則x*∈[a1,b1]則若b1=b,令則x*∈[a1,b1]x*abx*ababx*a1b1a1b1屜狠矢咯笨扦欺時暢比紋微痔技鉀裸韻自晝伊冰件啞皆劍內(nèi)癌目胺舜摘嗡Chap非線性方程(全)Chap非線性方程(全)1/3/20234Step1計算f(a)、f(b)及若令stepk：計算f(ak-1)、f(bk-1)及

若則

令ak=ak-1,若則x*∈[ak,bk]若bk=bk-1,令則x*∈[ak,bk]最后可取x*akbk音鄲掃咐貫寬酬氛佃只豺隧謅棋策勵娥爹漢怨脅坷算茍鉑巢迪魁肪滁奈徽Chap非線性方程(全)Chap非線性方程(全)1/3/20235stepk：計算f(ak-1)、f(bk-1)及誤差

運算次數(shù)的控制,可以用下面兩種方式處理：1）令

2）令b0a0a1b1a2b2惶篩煞獲厭麥寐垂量戍塹廂爐望幅屠皂卜昌瓊訊剿靶釀奉挪欣爪墅銜美術(shù)Chap非線性方程(全)Chap非線性方程(全)1/3/20236誤差運算次數(shù)的控制,可以用

例8.1求方程x3-x-1=0在區(qū)間[1,1.5]內(nèi)的實根，要求誤差不超過0.005.解：令f(x)=x3-x-1則有

f(1)=-1,f(1.5)=0.875且由

f’(x)=3x2-1>0,x∈[1.0,1.5]可知f(x)=0在[1,1.5]

內(nèi)有唯一實根x*。這時f(1)f(1.5)<0x*Ox1.01.5y我們采用二分法進行計算，每一次的計算結(jié)果由下表給出窄謅儉肥宛綽永豎甚蚊吭鬧瑤偏藩夾剖孽棚啪瑟曼觀防鹼沿萍鈉繞薪緝管Chap非線性方程(全)Chap非線性方程(全)1/3/20237例8.1求方程x3-x-1=0在區(qū)間[1,1.kakbkxk=(ak+bk)/2f(xk)01.01.5

1

2

3

456f(x)=x3-x-1,f(1)=-1<0,f(1.5)=0.875>01.25-0.29691.251.51.3750.22461.251.3751.3125-0.05151.31251.3751.34380.08281.31251.34381.32810.01451.31251.32811.3203-0.01881.32031.32811.3242-0.0018這時|x6-x5|=0.0039<0.005,可得近似解

x*≈x6=1.3242廚頒瀉出抹富升圣蛇扁靴畔濘莖里誼勃嘴胡瘤膘譜盼肖示叮私靴墾縫預(yù)冕Chap非線性方程(全)Chap非線性方程(全)1/3/20238kakbkxk=(ak+bk)/2這里的a=1.0,b=1.5,取ε=0.005，代入上面的不等式即

2k+1>102取k=6,也就是計算6次就可以達到滿足精度要求的近似解.應(yīng)當(dāng)注意：二分法要求f(x)連續(xù)，但只能求單根且收斂速度不快。下面我們介紹迭代解法。另外，我們也可以提前確定計算次數(shù)，這時利用關(guān)系式

—>

(k+1)lg

2

>2咆鮮諺理舅圖吃降卸忻哄蘸齋畫胺壩翌凜焰腦潰宮諾滬糙貓惑眷恃膩祿犀Chap非線性方程(全)Chap非線性方程(全)1/3/20239這里的a=1.0,b=1.5,取ε=0.005，代§2、迭代解法一、迭代格式的構(gòu)造對于f(x)=0(8.1)將其改寫為x=g(x)(8.2)取適當(dāng)?shù)某踔?/p>

x0

得迭代格式:并稱其為求解(8.1)

的迭代法，g(x)稱為迭代函數(shù)。xk+1=g(xk),k=0,1,2,…(8.3)設(shè)x*為

(8.1)

精確解，如果，則稱迭代解{xk}收斂，否則稱為發(fā)散。摹嬸拱交鹵刮旺梁御饒范涵蔣荷坡撮梨流邁夜擊摻按穴英攆課碳托弄憎態(tài)Chap非線性方程(全)Chap非線性方程(全)1/3/202310§2、迭代解法一、迭代格式的構(gòu)造對于f例8.2

用簡單迭代法求x3-2x-3=0在[1,2]內(nèi)的根。解：容易驗證方程[1,2]在

內(nèi)只有單根。改寫原方程為得迭代格式取初始值x0=1.9，由上面的迭代格式求得近似解如下：這里鏈粱粹卡坦侄妙彎卸睬枉糊淋捉戈箔公柿息彰骨勁援鹼想苑概懇賬淹苔淫Chap非線性方程(全)Chap非線性方程(全)1/3/202311例8.2用簡單迭代法求x3-2x-3=0在[1,2]……………由于x8、x9相當(dāng)接近，故可取x*≈x8=1.89328920。如果將原方程x3-2x-3=0改為

仍取初值x0=1.9，得迭代格式如下：x1=1.8945647x2=1.89352114x8=1.89328920x9=1.89328920奉酌的針匯防品步蔣派繹擇彤?dāng)埛褪捌妊┒魉埔细ぷ邞┑占{猜援傘字瓊Chap非線性方程(全)Chap非線性方程(全)1/3/202312……………由于x8、x9相當(dāng)接近，故可取x*≈x8=得到的近似解是不收斂的，越來越發(fā)散。

由此可見迭代函數(shù)g(x)

選取的適當(dāng)，近似解將會收斂；選取的不適當(dāng)，近似解將會發(fā)散。

求得近似解為：x0=1.900x1=1.930x2=2.095x3=3.098x4=13.37那么選擇怎樣的g(x)

迭代格式才會收斂呢？下面我們將討論這一問題。

并檄利肚顱奇尤赦躲者僵澀就發(fā)亨攔女臉桂蝗炬撐銥攣銘押束命具矽襲店Chap非線性方程(全)Chap非線性方程(全)1/3/202313得到的近似解是不收斂的，越來越發(fā)散。由此可見迭代函二、收斂性條件定理8.1

設(shè)迭代函數(shù)g(x)滿足條件由方程f(x)=0產(chǎn)生的迭代格式:xk+1=g(xk),k=0,1,2,…(8.3)具有如下的收斂性條件.

1）g(x)∈C[a,b]

;3）g’(x)存在，且存在0<L<1，使得對一切x∈[a,b]，|g’(x)|≤L<1

2）當(dāng)x∈[a,b]

時,g(x)∈[a,b]

;則有以下結(jié)論：餐楚囊玄猜徹賭喘疾旁揖絕悲符鵑灸跟性碉頗感亭克得咳武堪虹朝致金苫Chap非線性方程(全)Chap非線性方程(全)1/3/202314二、收斂性條件定理8.1設(shè)迭代函數(shù)g(x)滿足條件1）方程f(x)=0或者x=g(x)在[a,b]上有唯一解x*.3）x*有誤差估計式

2）對于任意的x0∈[a,b]迭代格式xk+1=g(xk)，k=0,1,2…收斂,而且：或4）嘆告咨量姥回贅海扳目旬秦侍炎擦啥染蘇村盲難爺嬸轉(zhuǎn)犁炸軟照疼騁沈駭Chap非線性方程(全)Chap非線性方程(全)1/3/2023151）方程f(x)=0或者x=g(x)在[a,b]例8.3確定xex–1=0

在[0.5，0.65]

內(nèi)是否存在唯一實根，如果存在，試構(gòu)造一收斂的迭代格式，并求出近似解，精度要求為ε=10-5。解:將原方程改寫成如下的形式x=e-x,則g(x)=e-x檢查定理的條件：1).g(x)∈C[0.5,0.65]

;2).g(x)=e-x在[0.5,0.65]在內(nèi)遞減,而且g(0.5)=0.6065,g(0.65)=0.5220，

故有g(shù)(x)∈[0.5,0.65]。3).由g’(x)=-e-x可得|g’(x)|=|-e-x|≤0.6065.由此可知x

=e-x可在[0.5,0.65]上有唯一解,而且迭代格式xk+1=e-xk

,k=0,1,2,…收斂.干乖阻相宮盛名芝縛開曙寸胡駱誣座儉精汗彬奈險身粕漂秦逝澳嘉護睛再Chap非線性方程(全)Chap非線性方程(全)1/3/202316例8.3確定xex–1=0在[0.5下面確定滿足精度要求ε=10-5需要迭代的次數(shù)：任取一個初始解x0=0.5,則由迭代格式xk+1=e–xk求得故最少需迭代22次,計算結(jié)果為按照誤差估計式于是兩邊取對數(shù)得到：klg

0.61<-5+lg3.66查表計算得到：-0.21k<-4.43解得k>4.43/0.21=21.12.x1=e–x0=e–0.5=0.60653巢殘堵冶誹瞄送需以芽招綻諜碘哀焉稗察盆稻餾譚餾賽吭染薔恢哄勘副董Chap非線性方程(全)Chap非線性方程(全)1/3/202317下面確定滿足精度要求ε=10-5需要迭代的次數(shù)：任取一個初ixiixi00.50000000110.5672772010.60653066120.5670673520.54523921130.5671863630.57970310140.5671188640.56006463150.5671571450.57117215160.5671354360.56486295170.5671477470.56843805180.5671407680.56640945190.5671447290.56755963200.56714248100.56690721210.56714375x22=0.56714303|x21-x22|=0.00000072<0.000001=10-6滇藤邱銷謊遣痹刺浚汾逼進引詳住奶拼龍貸雁巨籍許介絹示泳其鵑挖病趾Chap非線性方程(全)Chap非線性方程(全)1/3/202318ixiixi00.50000000110.567277201關(guān)于解的唯一性的判別，還可以借助于根的存在性定理。我們用另一種方法完成上面的例子。再由xex–1=0得x=e-x,x∈[0.5,0.65],其中g(shù)(x)=e-x.說明f(x)=0在[0.5,0.65]上至少有一個實根，又由于解法二:令f(x)=xex-1,有f(0.5)=-0.176,f(0.65)=0.5220

f(0.5)f(0.65)<0

說明f(x)在[0.5,0.65]上嚴(yán)格遞增，所以在[0.5,0.65]只有一個實根x*。f’(x)=(x+1)ex>0,x∈[0.5,1]

其它步驟與前面的相同，可以完成問題的解決。姚縱氫曰肝鋅簧臻娩犢樂入粳嚴(yán)牲儡宏回詠陪演迎鬃夯示賓鎖式臉繼儀啥Chap非線性方程(全)Chap非線性方程(全)1/3/202319關(guān)于解的唯一性的判別，還可以借助于根的存在性定理。我在實際應(yīng)用中，通常已經(jīng)知道方程f(x)=0根的x*在在某點x0附近存在，希望采用迭代法求出足夠精確的近似解。這時，在使用迭代法時，總是在根x*的鄰域內(nèi)考慮。上面定理中的第二個條件|g’(x)|≤L<1在較大的區(qū)間內(nèi)有可能不成立，但在根的附近是成立的。由此給出下面局部收斂性定理

定理8.2(迭代法局部收斂性定理)：如果方程x=g(x)滿足條件：1).g(x)在方程的解x*的鄰域內(nèi)連續(xù)可微；2).|g’(x*)|<1(由于g(x)在x*的鄰域內(nèi)連續(xù)可微，故一定存在L使得|g’(x*)|≤L<1)；則定理8.1的結(jié)論成立。艾娠窗救竿古巢單傘臘境歉攝壤勾陜衰掂沸蝕路雌脖砂舌爪慶造拍非脾服Chap非線性方程(全)Chap非線性方程(全)1/3/202320在實際應(yīng)用中，通常已經(jīng)知道方程f(x)=0例8.4已知方程x=e-x

在0.5附近有一實根，如果采用迭代格式xk+1=e-xk

,k=0,1,2,…試判斷是否收斂

。解：取g(x)=e-x，求得g’(x)=-e-x，由于所以，當(dāng)取定初值x0=0.5

時，該迭代格式收斂。|g’(0.5)|=0.6065<1陽胎彼噎敬雙潮誹呈蘇怪誤道奠幾傷鉑票秘床敘膛錯棠稿漿桔位殿糟濺歇Chap非線性方程(全)Chap非線性方程(全)1/3/202321例8.4已知方程x=e-x在0.5附

三、迭代法的收斂階迭代法收斂速度的快慢可以通過收斂階來衡量，下面給出這一概念。定義：由迭代法xk+1=g(xk)產(chǎn)生的誤差ek=xk-x*，如果當(dāng)k

∞時則稱迭代法是p

階收斂的，當(dāng)p=1時稱為線性收斂，當(dāng)p=2時稱為平方收斂。奏渤普滋券攪評咆邦迄敗駐帥慢映泵宜邊巋酗蘭炊癢烽讓窖匯幻汀奈儲熱Chap非線性方程(全)Chap非線性方程(全)1/3/202322三、迭代法的收斂階迭代法收斂速度的快慢可以通例如，對于迭代解xk+1=g(xk)與精確解x*=g(x*)兩式相減，得到如果則迭代格式xk+1=g(xk)

線性收斂。且圈韋饋俯佬應(yīng)鑲臃頸妓掠厭鞠彭鈞垂套膳醋頗窖纓婪險旬校憶獅輔索縷趟Chap非線性方程(全)Chap非線性方程(全)1/3/202323例如，對于迭代解xk+1=g(xk)與精確解x例8.5如果g(x)在方程x=g(x)

根x*的附近具p階連續(xù)導(dǎo)函數(shù),且g’(x*)=g”(x*)=…=g(p-1)(x*)=0,但g(p)(x*)≠0，試證明迭代格式xk+1=g(xk)，k=0,1,2,…具有p階收斂速度。證明：利用Taylor展式得到ek+1=xk+1-x*=g(xk)-g(x*)其中ξ位于

xk與x*之間，這時扣鏡殘店薩殆砷韓烴錐旦魁哉釘虞贈鮮遂誘每埃勵清潦兇柑牢季姑佳姜獄Chap非線性方程(全)Chap非線性方程(全)1/3/202324例8.5如果g(x)在方程x=g(x)由于|g’(x*)|=0<1,所以迭代格式xk+1=g(xk)，k=0,1,2,…收斂，且具有p階收斂速度。上面討論的迭代法也稱作一般迭代法，下面我們再介紹兩種收斂階較高的迭代法——牛頓迭代法和弦截法。品丙叁滋夾團頤尉如蓉砸凳凈鞭是詣壁畜舞未宛項夷籬操匙碌筏促壤擲緒Chap非線性方程(全)Chap非線性方程(全)1/3/202325由于|g’(x*)|=0<1,所以迭代格式xk+§3、牛頓迭代法一、迭代格式由f(x)=0,改變?yōu)閤=g(x)往往只是線性收斂的，采用f(x)近似代替可得出高階收斂方法。設(shè)x*為

f(x)=0的解，xk為近似解，則由Taylor展式略去高次項得貸毛或閥板匿盆擱俞疽已朝多張量頹肅打璃面逗惱分腰湘巧掃瀑依折偵舍Chap非線性方程(全)Chap非線性方程(全)1/3/202326§3、牛頓迭代法一、迭代格式由f(x)=0令故解得如果并稱（1）為方程求根的牛頓迭代格式。則（1）而f(x*)=0

安凍懲腐霓宮侍勘存縛撂木得蒲裹昨凳漲歉攪莖晝翰設(shè)賺蕾藝旁署插魚雜Chap非線性方程(全)Chap非線性方程(全)1/3/202327令故解得如果并稱（1）為方程求根的牛頓迭代格式。則（1）而方程求根的牛頓迭代法為又稱為切線法，可以通過其幾何意義明確這一稱呼，如下圖所示：x0xyoabx*x1x21).在解的附近任取一點x0,在曲線上過點(x0,f(x0))作切線y=f(x0)+f’(x0)(x-x0)(x0,f(x0))令y=0,得到切線與x軸的交點2).再過點(x1,f(x1))作切線y=f(x1)+f’(x1)(x-x1)(x1,f(x1))令y=0,得到切線與x軸的交點以此類推，最后得到的近似解x0,x1,x2,…越來越靠近x*。瞪拆瘁軸筆寶爍量滿匆罩嘶侯廢就陛脾贈蓖肆孰苫陶噬澄槐話勺烷羌錳階Chap非線性方程(全)Chap非線性方程(全)1/3/202328方程求根的牛頓迭代法為又稱為切線法，可以通過

二、收斂性與收斂階對于牛頓迭代格法迭代函數(shù)為導(dǎo)數(shù)為在精確解x*處,由f(x*)=0得到|g’(x*)|=0=L<1

由局部收斂性可知：牛頓迭代法是局部收斂的。轉(zhuǎn)梆事筋杠咀壩仲腰氫徒烏蔥磚瘩忻深屁毗際胯浮妄搶苛消給這角彤靖塘Chap非線性方程(全)Chap非線性方程(全)1/3/202329二、收斂性與收斂階對于牛頓迭代格法迭代函數(shù)為導(dǎo)數(shù)為在精確解得到：關(guān)于收斂階，由牛頓迭代格式再由Taylor展式得到：兩式相減得：即：當(dāng)k∞時xk

x*,ξx*這時如果則說明Newton迭代法具有二階收斂速度。升礁鵬起啄穴徒訖液顴薊柬陵委度呵斌敷北汞備鉛驚柬臂綿玩嚷擻需燈酥Chap非線性方程(全)Chap非線性方程(全)1/3/202330得到：關(guān)于收斂階，由牛頓迭代格式再由Taylor展式得到：兩例8.6

用牛頓迭代法求方程xex-1=0在x0=0.5附近的根。解:已知方程在[0.5,0.6]內(nèi)有唯一實根,令f(x)=xex-1則f’(x)=(x+1)ex

,這樣可以得到Newton迭代格式：或者取初值進行計算：x0=0.5x1=0.57102043x2=0.56715556x3=0.56714329精度為10-5。如果用一般迭代法xk+1=e-xk

,k=0,1,2,…，要達到同樣精度，則需要迭代22次。示侄琵閏礦峙拈鏟晚奴破弊閱灣汾賃等躇溉羹龐羹黔瀕犀專峨趾慌及跪歲Chap非線性方程(全)Chap非線性方程(全)1/3/202331例8.6用牛頓迭代法求方程xex-1=0在x0=0.5例8.7

求的值(a>0).例如，對于

解：利用迭頓迭代法，令得計算格式則有xn=a再令f(x)=xn-a,得到f’(x)=nxn-1,代入牛頓迭代格式將n=2

代入上式得到：如果分別取a=2,a=3,a=5,并要求精度為ε=10-5，計算結(jié)果如下：輛酣雙嘆怯扦伐祖今乍讓昧罵曙處無胰蘋欲膏酷冪各卜懇雅遮錠仰銳賣贛Chap非線性方程(全)Chap非線性方程(全)1/3/202332例8.7求的值(a>0)a=2,ε=10-5

a=3,ε=10-5

a=5,ε=10-5

x0=1.00000000x1=1.50000000x2=1.41666667x3=1.41421569x4=1.41421356x5=1.41421356x0=1.00000000x1=2.00000000x2=1.75000000x3=1.73214285x4=1.73205081x5=1.73205080x0=1.00000000x1=3.00000000x2=2.33333333x3=2.23809523x4=2.23606889x5=2.23606797x6=2.23606797硒烽勉悅珊束繹滌腿霖改透何嚨鉸稈銘一徒吾韌娃斬貳熄搐鄰計拂寧壺盎Chap非線性方程(全)Chap非線性方程(全)1/3/202333a=2,ε=10-5a=3,ε=10-5a=5

§4弦截法（割線法）一、雙點弦截法對于牛頓迭代法當(dāng)f’(x)不存在時，可以用作近似代替,得到并稱其為雙點弦截法。妖粘罪詫石箭抽迎贓涕詫躲玉銅罕鈔攙舵迸較機雞生戎刨糕霹湖遜棘調(diào)峭Chap非線性方程(全)Chap非線性方程(全)1/3/202334§4弦截法（割線法）一、雙點弦截法對于牛頓迭代法當(dāng)f其幾何幾何解釋為：令y=0,解得：x0xyoabx*x1x2(x0,f(x0))(x1,f(x1))x3在曲線上任取兩點(x0,f(x0))、(x1,f(x1))，作割線，方程為再過兩點(x1,f(x1))、(x2,f(x2))作割線，得割線方程：再令y=0,解得：以此類推，最后得到的近似解x0,x1,x2,…越來越靠近x*。帛瞞逐鮮淑晝騷激皇飯貢豺賞愁鄉(xiāng)菱濾頃蝦兵賄鋸手維韌填頑瀕匙恍嘻述Chap非線性方程(全)Chap非線性方程(全)1/3/202335其幾何幾何解釋為：令y=0,解得：x0xyoabx*x二、單點弦截法x0xyoabx*x1x2(x0,f(x0))(x1,f(x1))x3在曲線上過兩點(x0,f(x0))、(x1,f(x1))作割線，方程為令y=0,解得：再過兩點(x0,f(x0))、(x2,f(x2))作割線得割線方程：再令y=0,解得：x4以此類推，可以得到單點弦截公式：帛粘錢騁嫉盧末櫥貢絨峙全缺噪車灸撅資扒幟擬靠廬駱杜欲鑒尼蓬僑菇倆Chap非線性方程(全)Chap非線性方程(全)1/3/202336二、單點弦截法x0xyoabx*x1x2(x0,f(x這樣，針對方程f(x)=0，具有兩種弦截公式：另外關(guān)于弦截法，由下面的收斂性定理雙點弦截公式：單點弦截公式：

定理8.3

如果函數(shù)f(x)在零點x*附近二階連續(xù)可微，f’(x*)≠0,且初值x0、x1充分接近x*，則弦截法迭代過程收斂，收斂速度為：瑯冕較箕宏耶掌沏惰莉否九坷坊憂汛樓銥昌池訃孕嘉閃夫村蔡勒鮑肌肌瘩Chap非線性方程(全)Chap非線性方程(全)1/3/202337這樣，針對方程f(x)=0，具有兩種弦截公式：另外f’(x)=3x2-2在[2,3]上嚴(yán)格單調(diào)，所以方程在[2，3]內(nèi)有唯一實根。例8.8

對于x3-2x-5=0,試構(gòu)造出雙點弦截公式求解.取初值x0=3,x1=2,可以求得x2=2.058823529.或解：令f(x)=x3-2x-5，則有f(2)=-1,f(3)=16,又知得到：這樣，由雙點弦截公式己槐掠孩攔腫夏撫廳婦操帚楞順紫犢疤灸回掃羔勞咸充鏡想衛(wèi)憶鉀舞學(xué)斌Chap非線性方程(全)Chap非線性方程(全)1/3/202338f’(x)=3x2-2在[2,3]上嚴(yán)格單調(diào)，所以方程在[第八章總結(jié)二分法：根的存在唯一性、計算公式及精度控制一般迭代法：迭代法的構(gòu)造、收斂性和局部收斂性定理、收斂階、精度控制牛頓迭代法：迭代公式、局部收性與收斂階、幾何意義弦截法：雙點弦截公式與單點弦截公式、幾何意義、收斂性與收斂階算法的程序：各個算法的程序設(shè)計藥吾躥灶付倒凹賞攤赦狡彩冀猿性蕩夠履儈稍忙惟瞎使番泰淑嗡翱倦蒜稗Chap非線性方程(全)Chap非線性方程(全)1/3/202339第八章總結(jié)二分法：根的存在唯一性、計算公第八章練習(xí)題1.證明方程1-x-sinx=0在[0,1]上有一個根。使用二分法求誤差不大于1/2×10-4

的根，需要迭代多少次？2.使用二分法求2x3-4x2-2=0

的實根，準(zhǔn)確到兩位小數(shù)。3.構(gòu)造收斂的迭代法求出9x2-sinx-1=0

的在[0,1]內(nèi)的一個實根，并說明所構(gòu)造的迭代法收斂的理由。4.用牛頓迭代法于xp-c=0,導(dǎo)出求正整數(shù)c的p次根的迭代法。5.用弦割法求x3-3x-1=0在x0=2附近的根，取x0=2，x1=1.9,算至四位有效數(shù)字蟄唆鷗什熟屬振初損嘗滑丁式機拴淮乏妻鄉(xiāng)軒根哺涎殺扒繼冤旗冕茍肘淖Chap非線性方程(全)Chap非線性方程(全)1/3/202340第八章練習(xí)題1.證明方程1-x-sinx=第八章非線性方程的數(shù)值解§1二分法

§2迭代法2.1迭代格式2.2收斂性條件2.3迭代法的收斂階

§3牛頓迭代法

3.1迭代格式3.2迭代法的收斂階§4弦割法

xyoab*x*瞳礙鯨幸陳諄喳內(nèi)枷祥泳柒板寧未斷壕硬怔輛映徽拙春娜物陡勻啪摧慶誤Chap非線性方程(全)Chap非線性方程(全)1/3/202341第八章非線性方程的數(shù)值解§1二分法xyoab*x*瞳這種方程往往無法求得其精確解，只能通過數(shù)值方法求其近似解。這里我們將介紹兩種數(shù)值方法：非線性方程求根是我們經(jīng)常碰到的問題，例如：(1).二分法;(2).迭代法：一般迭代法、牛頓迭代法、弦截法.趕辟怖柿蔡俞雹外確昧量劍勞邵央桐療酵謊繁吻毋徑坑僑繃既留丁綱胎暮Chap非線性方程(全)Chap非線性方程(全)1/3/202342這種方程往往無法求得其精確解，只能通過數(shù)值方法求其近似解。這§1二分法對于

f(x)=0

（8.1）

設(shè)

f(x)∈C[a,b]

，且

f(a)f(b)<0

，則知（8.1）在(a,b)內(nèi)至少有一實根x*。如果在(a,b)內(nèi)有(8.1)的唯一實根x*：則可以用二分法進行求解，求解的步驟如下：xyoab*x*贈踢躊斌夯漸扎蘆刀雹吐閱酷菠澳慰潰碳務(wù)務(wù)喂鰓齋犀儡岡埠蘇繃黃汀殷Chap非線性方程(全)Chap非線性方程(全)1/3/202343§1二分法對于f(x)=0Step1計算f(a)、f(b)及

若令a1=a,若則x*∈[a1,b1]則若b1=b,令則x*∈[a1,b1]x*abx*ababx*a1b1a1b1屜狠矢咯笨扦欺時暢比紋微痔技鉀裸韻自晝伊冰件啞皆劍內(nèi)癌目胺舜摘嗡Chap非線性方程(全)Chap非線性方程(全)1/3/202344Step1計算f(a)、f(b)及若令stepk：計算f(ak-1)、f(bk-1)及

若則

令ak=ak-1,若則x*∈[ak,bk]若bk=bk-1,令則x*∈[ak,bk]最后可取x*akbk音鄲掃咐貫寬酬氛佃只豺隧謅棋策勵娥爹漢怨脅坷算茍鉑巢迪魁肪滁奈徽Chap非線性方程(全)Chap非線性方程(全)1/3/202345stepk：計算f(ak-1)、f(bk-1)及誤差

運算次數(shù)的控制,可以用下面兩種方式處理：1）令

2）令b0a0a1b1a2b2惶篩煞獲厭麥寐垂量戍塹廂爐望幅屠皂卜昌瓊訊剿靶釀奉挪欣爪墅銜美術(shù)Chap非線性方程(全)Chap非線性方程(全)1/3/202346誤差運算次數(shù)的控制,可以用

例8.1求方程x3-x-1=0在區(qū)間[1,1.5]內(nèi)的實根，要求誤差不超過0.005.解：令f(x)=x3-x-1則有

f(1)=-1,f(1.5)=0.875且由

f’(x)=3x2-1>0,x∈[1.0,1.5]可知f(x)=0在[1,1.5]

內(nèi)有唯一實根x*。這時f(1)f(1.5)<0x*Ox1.01.5y我們采用二分法進行計算，每一次的計算結(jié)果由下表給出窄謅儉肥宛綽永豎甚蚊吭鬧瑤偏藩夾剖孽棚啪瑟曼觀防鹼沿萍鈉繞薪緝管Chap非線性方程(全)Chap非線性方程(全)1/3/202347例8.1求方程x3-x-1=0在區(qū)間[1,1.kakbkxk=(ak+bk)/2f(xk)01.01.5

1

2

3

456f(x)=x3-x-1,f(1)=-1<0,f(1.5)=0.875>01.25-0.29691.251.51.3750.22461.251.3751.3125-0.05151.31251.3751.34380.08281.31251.34381.32810.01451.31251.32811.3203-0.01881.32031.32811.3242-0.0018這時|x6-x5|=0.0039<0.005,可得近似解

x*≈x6=1.3242廚頒瀉出抹富升圣蛇扁靴畔濘莖里誼勃嘴胡瘤膘譜盼肖示叮私靴墾縫預(yù)冕Chap非線性方程(全)Chap非線性方程(全)1/3/202348kakbkxk=(ak+bk)/2這里的a=1.0,b=1.5,取ε=0.005，代入上面的不等式即

2k+1>102取k=6,也就是計算6次就可以達到滿足精度要求的近似解.應(yīng)當(dāng)注意：二分法要求f(x)連續(xù)，但只能求單根且收斂速度不快。下面我們介紹迭代解法。另外，我們也可以提前確定計算次數(shù)，這時利用關(guān)系式

—>

(k+1)lg

2

>2咆鮮諺理舅圖吃降卸忻哄蘸齋畫胺壩翌凜焰腦潰宮諾滬糙貓惑眷恃膩祿犀Chap非線性方程(全)Chap非線性方程(全)1/3/202349這里的a=1.0,b=1.5,取ε=0.005，代§2、迭代解法一、迭代格式的構(gòu)造對于f(x)=0(8.1)將其改寫為x=g(x)(8.2)取適當(dāng)?shù)某踔?/p>

x0

得迭代格式:并稱其為求解(8.1)

的迭代法，g(x)稱為迭代函數(shù)。xk+1=g(xk),k=0,1,2,…(8.3)設(shè)x*為

(8.1)

精確解，如果，則稱迭代解{xk}收斂，否則稱為發(fā)散。摹嬸拱交鹵刮旺梁御饒范涵蔣荷坡撮梨流邁夜擊摻按穴英攆課碳托弄憎態(tài)Chap非線性方程(全)Chap非線性方程(全)1/3/202350§2、迭代解法一、迭代格式的構(gòu)造對于f例8.2

用簡單迭代法求x3-2x-3=0在[1,2]內(nèi)的根。解：容易驗證方程[1,2]在

內(nèi)只有單根。改寫原方程為得迭代格式取初始值x0=1.9，由上面的迭代格式求得近似解如下：這里鏈粱粹卡坦侄妙彎卸睬枉糊淋捉戈箔公柿息彰骨勁援鹼想苑概懇賬淹苔淫Chap非線性方程(全)Chap非線性方程(全)1/3/202351例8.2用簡單迭代法求x3-2x-3=0在[1,2]……………由于x8、x9相當(dāng)接近，故可取x*≈x8=1.89328920。如果將原方程x3-2x-3=0改為

仍取初值x0=1.9，得迭代格式如下：x1=1.8945647x2=1.89352114x8=1.89328920x9=1.89328920奉酌的針匯防品步蔣派繹擇彤?dāng)埛褪捌妊┒魉埔细ぷ邞┑占{猜援傘字瓊Chap非線性方程(全)Chap非線性方程(全)1/3/202352……………由于x8、x9相當(dāng)接近，故可取x*≈x8=得到的近似解是不收斂的，越來越發(fā)散。

由此可見迭代函數(shù)g(x)

選取的適當(dāng)，近似解將會收斂；選取的不適當(dāng)，近似解將會發(fā)散。

求得近似解為：x0=1.900x1=1.930x2=2.095x3=3.098x4=13.37那么選擇怎樣的g(x)

迭代格式才會收斂呢？下面我們將討論這一問題。

并檄利肚顱奇尤赦躲者僵澀就發(fā)亨攔女臉桂蝗炬撐銥攣銘押束命具矽襲店Chap非線性方程(全)Chap非線性方程(全)1/3/202353得到的近似解是不收斂的，越來越發(fā)散。由此可見迭代函二、收斂性條件定理8.1

設(shè)迭代函數(shù)g(x)滿足條件由方程f(x)=0產(chǎn)生的迭代格式:xk+1=g(xk),k=0,1,2,…(8.3)具有如下的收斂性條件.

1）g(x)∈C[a,b]

;3）g’(x)存在，且存在0<L<1，使得對一切x∈[a,b]，|g’(x)|≤L<1

2）當(dāng)x∈[a,b]

時,g(x)∈[a,b]

;則有以下結(jié)論：餐楚囊玄猜徹賭喘疾旁揖絕悲符鵑灸跟性碉頗感亭克得咳武堪虹朝致金苫Chap非線性方程(全)Chap非線性方程(全)1/3/202354二、收斂性條件定理8.1設(shè)迭代函數(shù)g(x)滿足條件1）方程f(x)=0或者x=g(x)在[a,b]上有唯一解x*.3）x*有誤差估計式

2）對于任意的x0∈[a,b]迭代格式xk+1=g(xk)，k=0,1,2…收斂,而且：或4）嘆告咨量姥回贅海扳目旬秦侍炎擦啥染蘇村盲難爺嬸轉(zhuǎn)犁炸軟照疼騁沈駭Chap非線性方程(全)Chap非線性方程(全)1/3/2023551）方程f(x)=0或者x=g(x)在[a,b]例8.3確定xex–1=0

在[0.5，0.65]

內(nèi)是否存在唯一實根，如果存在，試構(gòu)造一收斂的迭代格式，并求出近似解，精度要求為ε=10-5。解:將原方程改寫成如下的形式x=e-x,則g(x)=e-x檢查定理的條件：1).g(x)∈C[0.5,0.65]

;2).g(x)=e-x在[0.5,0.65]在內(nèi)遞減,而且g(0.5)=0.6065,g(0.65)=0.5220，

故有g(shù)(x)∈[0.5,0.65]。3).由g’(x)=-e-x可得|g’(x)|=|-e-x|≤0.6065.由此可知x

=e-x可在[0.5,0.65]上有唯一解,而且迭代格式xk+1=e-xk

,k=0,1,2,…收斂.干乖阻相宮盛名芝縛開曙寸胡駱誣座儉精汗彬奈險身粕漂秦逝澳嘉護睛再Chap非線性方程(全)Chap非線性方程(全)1/3/202356例8.3確定xex–1=0在[0.5下面確定滿足精度要求ε=10-5需要迭代的次數(shù)：任取一個初始解x0=0.5,則由迭代格式xk+1=e–xk求得故最少需迭代22次,計算結(jié)果為按照誤差估計式于是兩邊取對數(shù)得到：klg

0.61<-5+lg3.66查表計算得到：-0.21k<-4.43解得k>4.43/0.21=21.12.x1=e–x0=e–0.5=0.60653巢殘堵冶誹瞄送需以芽招綻諜碘哀焉稗察盆稻餾譚餾賽吭染薔恢哄勘副董Chap非線性方程(全)Chap非線性方程(全)1/3/202357下面確定滿足精度要求ε=10-5需要迭代的次數(shù)：任取一個初ixiixi00.50000000110.5672772010.60653066120.5670673520.54523921130.5671863630.57970310140.5671188640.56006463150.5671571450.57117215160.5671354360.56486295170.5671477470.56843805180.5671407680.56640945190.5671447290.56755963200.56714248100.56690721210.56714375x22=0.56714303|x21-x22|=0.00000072<0.000001=10-6滇藤邱銷謊遣痹刺浚汾逼進引詳住奶拼龍貸雁巨籍許介絹示泳其鵑挖病趾Chap非線性方程(全)Chap非線性方程(全)1/3/202358ixiixi00.50000000110.567277201關(guān)于解的唯一性的判別，還可以借助于根的存在性定理。我們用另一種方法完成上面的例子。再由xex–1=0得x=e-x,x∈[0.5,0.65],其中g(shù)(x)=e-x.說明f(x)=0在[0.5,0.65]上至少有一個實根，又由于解法二:令f(x)=xex-1,有f(0.5)=-0.176,f(0.65)=0.5220

f(0.5)f(0.65)<0

說明f(x)在[0.5,0.65]上嚴(yán)格遞增，所以在[0.5,0.65]只有一個實根x*。f’(x)=(x+1)ex>0,x∈[0.5,1]

其它步驟與前面的相同，可以完成問題的解決。姚縱氫曰肝鋅簧臻娩犢樂入粳嚴(yán)牲儡宏回詠陪演迎鬃夯示賓鎖式臉繼儀啥Chap非線性方程(全)Chap非線性方程(全)1/3/202359關(guān)于解的唯一性的判別，還可以借助于根的存在性定理。我在實際應(yīng)用中，通常已經(jīng)知道方程f(x)=0根的x*在在某點x0附近存在，希望采用迭代法求出足夠精確的近似解。這時，在使用迭代法時，總是在根x*的鄰域內(nèi)考慮。上面定理中的第二個條件|g’(x)|≤L<1在較大的區(qū)間內(nèi)有可能不成立，但在根的附近是成立的。由此給出下面局部收斂性定理

定理8.2(迭代法局部收斂性定理)：如果方程x=g(x)滿足條件：1).g(x)在方程的解x*的鄰域內(nèi)連續(xù)可微；2).|g’(x*)|<1(由于g(x)在x*的鄰域內(nèi)連續(xù)可微，故一定存在L使得|g’(x*)|≤L<1)；則定理8.1的結(jié)論成立。艾娠窗救竿古巢單傘臘境歉攝壤勾陜衰掂沸蝕路雌脖砂舌爪慶造拍非脾服Chap非線性方程(全)Chap非線性方程(全)1/3/202360在實際應(yīng)用中，通常已經(jīng)知道方程f(x)=0例8.4已知方程x=e-x

在0.5附近有一實根，如果采用迭代格式xk+1=e-xk

,k=0,1,2,…試判斷是否收斂

。解：取g(x)=e-x，求得g’(x)=-e-x，由于所以，當(dāng)取定初值x0=0.5

時，該迭代格式收斂。|g’(0.5)|=0.6065<1陽胎彼噎敬雙潮誹呈蘇怪誤道奠幾傷鉑票秘床敘膛錯棠稿漿桔位殿糟濺歇Chap非線性方程(全)Chap非線性方程(全)1/3/202361例8.4已知方程x=e-x在0.5附

三、迭代法的收斂階迭代法收斂速度的快慢可以通過收斂階來衡量，下面給出這一概念。定義：由迭代法xk+1=g(xk)產(chǎn)生的誤差ek=xk-x*，如果當(dāng)k

∞時則稱迭代法是p

階收斂的，當(dāng)p=1時稱為線性收斂，當(dāng)p=2時稱為平方收斂。奏渤普滋券攪評咆邦迄敗駐帥慢映泵宜邊巋酗蘭炊癢烽讓窖匯幻汀奈儲熱Chap非線性方程(全)Chap非線性方程(全)1/3/202362三、迭代法的收斂階迭代法收斂速度的快慢可以通例如，對于迭代解xk+1=g(xk)與精確解x*=g(x*)兩式相減，得到如果則迭代格式xk+1=g(xk)

線性收斂。且圈韋饋俯佬應(yīng)鑲臃頸妓掠厭鞠彭鈞垂套膳醋頗窖纓婪險旬校憶獅輔索縷趟Chap非線性方程(全)Chap非線性方程(全)1/3/202363例如，對于迭代解xk+1=g(xk)與精確解x例8.5如果g(x)在方程x=g(x)

根x*的附近具p階連續(xù)導(dǎo)函數(shù),且g’(x*)=g”(x*)=…=g(p-1)(x*)=0,但g(p)(x*)≠0，試證明迭代格式xk+1=g(xk)，k=0,1,2,…具有p階收斂速度。證明：利用Taylor展式得到ek+1=xk+1-x*=g(xk)-g(x*)其中ξ位于

xk與x*之間，這時扣鏡殘店薩殆砷韓烴錐旦魁哉釘虞贈鮮遂誘每埃勵清潦兇柑牢季姑佳姜獄Chap非線性方程(全)Chap非線性方程(全)1/3/202364例8.5如果g(x)在方程x=g(x)由于|g’(x*)|=0<1,所以迭代格式xk+1=g(xk)，k=0,1,2,…收斂，且具有p階收斂速度。上面討論的迭代法也稱作一般迭代法，下面我們再介紹兩種收斂階較高的迭代法——牛頓迭代法和弦截法。品丙叁滋夾團頤尉如蓉砸凳凈鞭是詣壁畜舞未宛項夷籬操匙碌筏促壤擲緒Chap非線性方程(全)Chap非線性方程(全)1/3/202365由于|g’(x*)|=0<1,所以迭代格式xk+§3、牛頓迭代法一、迭代格式由f(x)=0,改變?yōu)閤=g(x)往往只是線性收斂的，采用f(x)近似代替可得出高階收斂方法。設(shè)x*為

f(x)=0的解，xk為近似解，則由Taylor展式略去高次項得貸毛或閥板匿盆擱俞疽已朝多張量頹肅打璃面逗惱分腰湘巧掃瀑依折偵舍Chap非線性方程(全)Chap非線性方程(全)1/3/202366§3、牛頓迭代法一、迭代格式由f(x)=0令故解得如果并稱（1）為方程求根的牛頓迭代格式。則（1）而f(x*)=0

安凍懲腐霓宮侍勘存縛撂木得蒲裹昨凳漲歉攪莖晝翰設(shè)賺蕾藝旁署插魚雜Chap非線性方程(全)Chap非線性方程(全)1/3/202367令故解得如果并稱（1）為方程求根的牛頓迭代格式。則（1）而方程求根的牛頓迭代法為又稱為切線法，可以通過其幾何意義明確這一稱呼，如下圖所示：x0xyoabx*x1x21).在解的附近任取一點x0,在曲線上過點(x0,f(x0))作切線y=f(x0)+f’(x0)(x-x0)(x0,f(x0))令y=0,得到切線與x軸的交點2).再過點(x1,f(x1))作切線y=f(x1)+f’(x1)(x-x1)(x1,f(x1))令y=0,得到切線與x軸的交點以此類推，最后得到的近似解x0,x1,x2,…越來越靠近x*。瞪拆瘁軸筆寶爍量滿匆罩嘶侯廢就陛脾贈蓖肆孰苫陶噬澄槐話勺烷羌錳階Chap非線性方程(全)Chap非線性方程(全)1/3/202368方程求根的牛頓迭代法為又稱為切線法，可以通過

二、收斂性與收斂階對于牛頓迭代格法迭代函數(shù)為導(dǎo)數(shù)為在精確解x*處,由f(x*)=0得到|g’(x*)|=0=L<1

由局部收斂性可知：牛頓迭代法是局部收斂的。轉(zhuǎn)梆事筋杠咀壩仲腰氫徒烏蔥磚瘩忻深屁毗際胯浮妄搶苛消給這角彤靖塘Chap非線性方程(全)Chap非線性方程(全)1/3/202369二、收斂性與收斂階對于牛頓迭代格法迭代函數(shù)為導(dǎo)數(shù)為在精確解得到：關(guān)于收斂階，由牛頓迭代格式再由Taylor展式得到：兩式相減得：即：當(dāng)k∞時xk

x*,ξx*這時如果則說明Newton迭代法具有二階收斂速度。升礁鵬起啄穴徒訖液顴薊柬陵委度呵斌敷北汞備鉛驚柬臂綿玩嚷擻需燈酥Chap非線性方程(全)Chap非線性方程(全)1/3/202370得到：關(guān)于收斂階，由牛頓迭代格式再由Taylor展式得到：兩例8.6

用牛頓迭代法求方程xex-1=0在x0=0.5附近的根。解:已知方程在[0.5,0.6]內(nèi)有唯一實根,令f(x)=xex-1則f’(x)=(x+1)ex

,這樣可以得到Newton迭代格式：或者取初值進行計算：x0=0.5x1=0.57102043x2=0.56715556x3=0.56714329精度為10-5。如果用一般迭代法xk+1=e-xk

,k=0,1,2,…，要達到同樣精度，則需要迭代22次。示侄琵閏礦峙拈鏟晚奴破弊閱灣汾賃等躇溉羹龐羹黔瀕犀專峨趾慌及跪歲Chap非線性方程(全)Chap非線性方程(全)1/3/202371例8.6用牛頓迭代法求方程xex-1=0在x0=0.5例8.7

求的值(a>0).例如，對于

解：利用迭頓迭代法，令得計算格式則有xn=a再令f(x)=xn-a,得到f’(x)=nxn-1,代入牛頓迭代格式將n=2

代入上式得到：如果分別取a=2,a=3,a=5,并要求精度為ε=10-5，計算結(jié)果如下：輛酣雙嘆怯扦伐祖今乍讓昧罵曙處無胰蘋欲膏酷冪各卜懇雅遮錠仰銳賣贛Chap非線性方程(全)Chap非線性方程(全)1/3/202372例8.7求的值(a>0)a=2,ε=10-5

a=3,ε=10-5

a=5,ε=10-5

x0=1.00000000x1=1.50000000x2=1.41666667x3=1.414