第七章非線性方程的數(shù)值解法

第七章非線性方程的數(shù)值解法第一頁，共五十一頁，2022年，8月28日1本章要討論的問題：（非線性）方程f(x)=0的數(shù)值解法首先引入定義：1.f(x)=0的解x*稱為方程f(x)=0的根或函數(shù)f(x)

的零點.若f(x)=(x-x*)mg(x),g(x*)≠0

，其中m為正整數(shù)，則稱x*為方程f(x)=0的m重根，或稱x*為函數(shù)

f(x)的m重零點.上一頁下一頁

返回

第二頁，共五十一頁，2022年，8月28日2§1方程求根的二分法

方程求根步驟：①根的隔離確定根所在的區(qū)間[a,b],使在[a,b]內(nèi)至少有方程的一個根.有根區(qū)間②近似根的精確化

已知根的一個近似值后,構(gòu)造某種算法,將此近似值精確化,使其滿足給定的精度要求.越小越好上一頁下一頁

返回

第三頁，共五十一頁，2022年，8月28日3下面介紹方程求根的二分法在確立了有根區(qū)間[a,b]后,需要逐步縮小有根區(qū)間.

取[a,b]的中點x0=(a+b)/2,將區(qū)間一分為二.若f(x0)=0,則x0就是方程的根,否則判別根x*

在x0的左側(cè)還是右側(cè).

不論出現(xiàn)哪種情況,(a1,b1)均為新的有根區(qū)間,它的長度只有原有根區(qū)間長度的一半,達(dá)到了壓縮有根區(qū)間的目的.上一頁下一頁

返回

第四頁，共五十一頁，2022年，8月28日4

重復(fù)以上過程,繼續(xù)進行二分,可得一系列有根區(qū)間

由于每個小區(qū)間都是有根區(qū)間,所以這個點就是所求方程的根.

同時,在每次二分時,所求出的中點形成一個無窮數(shù)列這個數(shù)列必定收斂于x*.上一頁下一頁

返回

第五頁，共五十一頁，2022年，8月28日5abx0x1a1b2Whentostop?x*b1上一頁下一頁

返回

a2第六頁，共五十一頁，2022年，8月28日6誤差分析：第1步產(chǎn)生的有誤差第k步產(chǎn)生的xk－1

有誤差對于給定的精度

,可估計二分法所需的步數(shù)k：①算法簡單;

②對f(x)

要求不高(只要連續(xù)即可)，收斂性總能得到保證①無法求復(fù)數(shù)根及偶數(shù)重根（函數(shù)值的正負(fù)號相同）；②要計算很多次函數(shù)值，收斂慢二分法的誤差估計式上一頁下一頁

返回

第七頁，共五十一頁，2022年，8月28日7例1

用二分法求f(x)=x3-x-1=0在區(qū)間[1,1.5]內(nèi)的一個實根,要求誤差不超過0.005.解：由題可知x*(1,1.5)

,要想解之得取n＝6.按二分法計算的過程見下表,x6為所求之近似根.上一頁下一頁

返回

第八頁，共五十一頁，2022年，8月28日8nanbnxnf(xn)備注01.01.51.25-①f(a0)<0,f(b0)>0②根據(jù)精度要求xn取到小數(shù)點四位即可.11.251.51.375+21.251.3751.3125-31.31251.3751.3438+41.31251.34381.3281+51.31251.32811.3203-61.32031.32811.3242-上一頁下一頁

返回

第九頁，共五十一頁，2022年，8月28日9逐步搜索法

從區(qū)間[a，b]的左端點

a出發(fā),按選定的步長h>0一步步向右搜索,若：則區(qū)間[a+jh,a+(j+1)h]內(nèi)必有根.上一頁下一頁

返回

于是可確定一個縮小了的有根區(qū)間[a+jh,a+(j+1)h].

再對新的有根區(qū)間，取新的更小的預(yù)定步長，繼續(xù)搜索，直到有根區(qū)間的長度足夠小。搜索過程也可從b開始,這時應(yīng)取步長

h<0.第十頁，共五十一頁，2022年，8月28日10§2一元方程的不動點迭代法迭代格式一、不動點迭代法及其收斂性1.迭代法的基本思想

將方程f(x)=0化為等價方程然后在有根區(qū)間內(nèi)取一點x0,按下式計算計算結(jié)果生成數(shù)列{xk}上一頁下一頁

返回

第十一頁，共五十一頁，2022年，8月28日11如果這個數(shù)列有極限,x*就是方程的根.

迭代式（1）稱為基本迭代法.

稱為迭代函數(shù),x

0稱為迭代初值,數(shù)列(2)稱為迭代序列.上一頁下一頁

返回

如果迭代序列收斂,則稱迭代格式收斂,否則稱為發(fā)散.x*

稱為的不動點。迭代過程中，xk+1僅由xk決定，因此，這是一種單步法。第十二頁，共五十一頁，2022年，8月28日12例2

用迭代法求方程x4+2x2-

x-3=0在區(qū)間[1,1.2]內(nèi)的實根.解：對方程進行如下三種變形分別按以上三種形式建立迭代格式,并取x0=1進行迭代計算,結(jié)果如下：準(zhǔn)確根x*=1.124123029,可見迭代格式不同,收斂情況也不同,收斂速度也不同.上一頁下一頁

返回

第十三頁，共五十一頁，2022年，8月28日13上一頁下一頁

返回

例3

解：把f(x)=0轉(zhuǎn)換成等價形式對應(yīng)的迭代法為取初值x0=±1,迭代結(jié)果分別收斂到x*=,計算結(jié)果見下表k012345xk

11.51.416666671.414215691.414213561.41421356xk

-1-1.5-1.41666667-1.41421569-1.41421356-1.41421356

從而可見，基本迭代法的收斂性取決于迭代函數(shù)和初值x0的選取。第十四頁，共五十一頁，2022年，8月28日14問題2.迭代格式應(yīng)該滿足什么條件才能保證收斂？3.如何判斷迭代收斂的速度,建立收斂快的迭代格式？上一頁下一頁

返回

1.迭代函數(shù)

如何構(gòu)造？第十五頁，共五十一頁，2022年，8月28日15定理12.收斂條件與誤差估計上一頁下一頁

返回

迭代格式的收斂性與迭代函數(shù)

密切相關(guān).方程x=，C[a,b],滿足條件(1)當(dāng)x[a,b]時，[a,b]；(2)0L<1使得

|

|L<1對x[a,b]成立.則(1)函數(shù)在[a,b]上有唯一不動點x*;(2)對任意迭代初值x0

[a,b],迭代序列{xk+1}收斂于x*.（3）有下列誤差估計式：第十六頁，共五十一頁，2022年，8月28日16(k=1,2,…)反之,若在區(qū)間R內(nèi),則迭代必發(fā)散.上一頁下一頁

返回

L越小收斂越快尚未計算時便估計出第k次迭代近似值的誤差,稱為事先誤差估計.第十七頁，共五十一頁，2022年，8月28日17由定理1的誤差估計式可看出,只要相鄰兩次迭代近似值xk與xk-1的偏差|xk–xk-1

|充分小,就可以保證迭代值xk足夠精確.這種用前后兩次迭代結(jié)果估計誤差的辦法稱為事后誤差估計上一頁下一頁

返回

因此對于給定的允許誤差ε,當(dāng)L較小時,常用前后兩次迭代是否滿足

|xk–xk-1

|<ε

來終止迭代.第十八頁，共五十一頁，2022年，8月28日18不但可以估計迭代k次時的誤差,也可以用來確定達(dá)到誤差精度要求的迭代次數(shù)k.當(dāng)要求誤差精度為ε,即要求,只要即可,從中解出k為實際應(yīng)用中,控制迭代結(jié)束的條件也常取為E<ε其中上一頁下一頁

返回

第十九頁，共五十一頁，2022年，8月28日19xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=φ(x)y=φ(x)y=φ(x)y=φ(x)x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p1上一頁下一頁

返回

迭代過程的幾何解釋如下圖第二十頁，共五十一頁，2022年，8月28日20上一頁下一頁

返回

例4

對于例2中的三種迭代法，討論它們的收斂性。解：對于下面三種迭代函數(shù)其導(dǎo)函數(shù)在[1,1.2]內(nèi)分別有根據(jù)定理1，例2中的第三種迭代法發(fā)散，第一、二種迭代格式收斂，而且第二種迭代法比第一種迭代法收斂快得多。這與實際計算結(jié)果完全吻合。第二十一頁，共五十一頁，2022年，8月28日21迭代法的流程圖如下：上一頁下一頁

返回

第二十二頁，共五十一頁，2022年，8月28日22上一頁下一頁

返回

例5解：即可得等價的方程有時，對于不滿足定理條件的問題，可以通過轉(zhuǎn)化，化為適合于迭代的形式。令則有故第二十三頁，共五十一頁，2022年，8月28日23上一頁下一頁

返回

二、局部收斂性和加速收斂法定理1中，迭代法在區(qū)間[a,b]上的收斂性，稱之為全局收斂性.定義:若在

x*的某鄰域

R

={x||xx*|},使迭代過程xk+1=(xk

),k=0,1,2…,對于任意x0R

均收斂,則稱該迭代過程在x*處具有局部收斂性.

定理2第二十四頁，共五十一頁，2022年，8月28日24迭代過程的收斂速度定義

p的大小反映了迭代過程收斂的快慢,p越大收斂速度越快.上一頁下一頁

返回

第二十五頁，共五十一頁，2022年，8月28日25定理3上一頁下一頁

返回

設(shè)x*為函數(shù)的不動點,在x*的鄰域內(nèi)

有連續(xù)的p階導(dǎo)數(shù)(p≥1),那么(1)0<||<1,則迭代過程在x*的鄰近為線性收斂；第二十六頁，共五十一頁，2022年，8月28日26例6

證明迭代公式是求的三階方法.假設(shè)xo充分靠近x*,求解：此迭代格式的迭代函數(shù)為方程兩邊對x

求導(dǎo),得上一頁下一頁

返回

第二十七頁，共五十一頁，2022年，8月28日27再將上式兩邊對x

求導(dǎo),得上式再對x

求導(dǎo),得上一頁下一頁

返回

所以，迭代格式是3階收斂的.第二十八頁，共五十一頁，2022年，8月28日28加速收斂的Steffensen迭代法對于線性收斂的迭代法，收斂很慢。上一頁下一頁

返回

設(shè)xk

是方程根

x*的一個近似值，由xk

開始相繼迭代兩次,將其結(jié)果記作第二十九頁，共五十一頁，2022年，8月28日29于是得到如下迭代格式稱之為Steffensen迭代法(其他教材也稱之為埃特金(Aitken)外推加速法).上一頁下一頁

返回

它的不動點迭代格式是其中迭代函數(shù)為第三十頁，共五十一頁，2022年，8月28日30若對此格式用Steffensen法,則上一頁下一頁

返回

例7第三十一頁，共五十一頁，2022年，8月28日31上一頁下一頁

返回

第三十二頁，共五十一頁，2022年，8月28日32上一頁下一頁

返回

例8現(xiàn)在用函數(shù)構(gòu)造Steffensen迭代法,k

01…56xk

1.51.4162930…1.32471801.3247180可見，Steffensen迭代法對這種不收斂的情形同樣有效。第三十三頁，共五十一頁，2022年，8月28日33§3一元方程的常用迭代法一、Newton迭代法設(shè)x*是方程f(x)=0的實根。取x0

x*，將f(x)在x0

做一階Taylor展開:，在x0

和x

之間。將(x*

x0)2

看成高階小量，則有：xyx*x0上一頁下一頁

返回

由圖示，可見xk+1為函數(shù)f(x)在點xk處的切線與橫坐標(biāo)軸的交點，所以，Newton迭代法也稱切線法。Newton迭代格式

第三十四頁，共五十一頁，2022年，8月28日34上一頁下一頁

返回

與上一節(jié)例7相比，牛頓法的收斂速度快很多。

例9

第三十五頁，共五十一頁，2022年，8月28日35上一頁下一頁

返回

牛頓迭代法的流程圖第三十六頁，共五十一頁，2022年，8月28日36注：牛頓迭代法的收斂性依賴于x0

的選取。x*x0x0x0上一頁下一頁

返回

第三十七頁，共五十一頁，2022年，8月28日37定理上一頁下一頁

返回

（收斂的充分條件）設(shè)f

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

[a,b]使得f(x0)f”(x0)>0；則牛頓迭代法產(chǎn)生的序列{xk}收斂到f(x)在[a,b]的唯一根。定理有根根唯一產(chǎn)生的序列單調(diào)有界，保證收斂。保證f(x)上凸或下凸第三十八頁，共五十一頁，2022年，8月28日38上一頁下一頁

返回

10

第三十九頁，共五十一頁，2022年，8月28日39Q1:

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

的m

重零點,則：且A1:

有局部收斂性，但僅為線性收斂.下面介紹計算重根的牛頓迭代法上一頁下一頁

返回

第四十頁，共五十一頁，2022年，8月28日40因此,求f(x)=0之m重根x*等價于求(x)=0

的單根x*

。而對(x)=0用牛頓迭代法求根則是平方收斂的,其迭代格式為

令，則f

的重零點就是

的單零點。A2:

方法1：將求

f

的重零點轉(zhuǎn)化為求另一函數(shù)的單零點。Q2:

如何加速求重根的收斂速度？上一頁下一頁

返回

第四十一頁，共五十一頁，2022年，8月28日41方法2：采用如下迭代格式可以證明它是求m重根x*的具有平方收斂的迭代格式.如何確定根的重數(shù)m?則：上一頁下一頁

返回

第四十二頁，共五十一頁，2022年，8月28日42例11

用牛頓迭代法求方程解：kxkλk1/(1-λk)00.9510.974427920.987058330.99348780.50902.036940.99673280.50472.019050.99835760.50072.002860.99919010.51252.0511上一頁下一頁

返回

第四十三頁，共五十一頁，2022年，8月28日43上一頁下一頁

返回

第四十四頁，共五十一頁，2022年，8月28日44例12

用3種方法求解方程解：上一頁下一頁

返回

都取x0=1.5，計算結(jié)果見下表：第四十五頁，共五十一頁，2022年，8月28日45方法（2）和方法（3）都是二階方法，x3都精確到了小數(shù)點后第9位，方法（1）即普通牛頓迭代法，解重根是一階方法，要近30次迭代才能有相同的精度。xk方法（1）方法（2）方法（3）x01.51.51.5x11.4583333331.4166666671.411764706x21.4366071431.4142156861.414211438x31.4254976191.4142135621.414213562上一頁下一頁

返回

第四十六頁，共五十一頁，2022年，8月28日46牛頓法的優(yōu)點

收斂速度快