某大學(xué)計(jì)算方法課件-第五章非線性方程數(shù)值解法

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

科學(xué)工程中常常涉及求解非線性方程

F(X)=0,(1)

T

這里X=(的,陶…，Xn),F(X)=(力(X),這X)，…,加X))T6

一般而言，其精確求解是非常困難的，例如對(duì)于高于4次的

代數(shù)方程，理論分析已證明其不存在精確求根公式。為此，我們

必須借助于數(shù)值算法來(lái)求解各種非線性方程。

§5.1幾何方法

在本節(jié)，我們介紹非線性標(biāo)量方程的二類幾何解法：二分

法和弦截法?？紤]非線性標(biāo)量方程

/?=0.(2)

為保證方程⑵在求解區(qū)間［a,b］內(nèi)存在實(shí)根，我們假設(shè)

/3GC(［QM,f⑷<u.⑶

此外，我們恒設(shè)方程⑵在［Q,b］內(nèi)有唯一實(shí)根I*,此時(shí)區(qū)間［Q,b］

稱為方程的根的一個(gè)隔離區(qū)間。

§5.1.1二分法

非線性標(biāo)量方程⑵的二分法，其基本計(jì)算思路如下：

Step1.把區(qū)間［Q詢二等分,記等分節(jié)點(diǎn)

__a+b

Q?！猀)/0—7>—b.

乙

計(jì)算g處的函數(shù)值/(g),若/(g)=0,則取7*=空；否則，轉(zhuǎn)

至Step2;

Step2.若

/⑷/(亨)<0,

乙

則記Ql=Q,仇=空；若

/(中/⑹<0,

則記。1=喏，瓦=b。取近似根

X1="1:仇G［?1,61］；

Step3.重復(fù)上述步驟，得根/*的下列隔離區(qū)間序列

M%］DM瓦］D%,蚓D…M切一….

這里，二分k次后隔離區(qū)間山,加］的長(zhǎng)度為

bk_CLk=

近似根股=啥Gk，㈤，其有誤差估計(jì)

bk—dk_b—a

成-行|<

22卜+1.

因此，若要近似根3達(dá)到預(yù)定精度￡：|1*—Xk\＜瞑只需貂＜￡,

即當(dāng)

ln[l)—Q)/?2(2￡)

k＞

Zn2

時(shí)，可終止迭代，取跳=中作為欲求近似根。

______________________算法5.1二分法

functionx=half(a,b,tol)

c=(a+b)/2;k=1;

m=l+round((log(b—a)—log(2*tol))/log(2));

whilek<=?n

iff(c)==0

c=c;

return;

elseiff(a)*f(c)<0

b=(a+b)/2;

else

a=(a+b)/2;

end

c=(a+b)/2;k=k+1;

end

k

二分方法是方程求根問(wèn)題的一種直接搜索方法，其優(yōu)點(diǎn)是算法

簡(jiǎn)單直觀，數(shù)值解的精度易于判別。該算法的局限性是僅適用于

標(biāo)量方程，且事先要確定方程的根的一個(gè)隔離區(qū)間，當(dāng)隔離區(qū)間

較長(zhǎng)時(shí)其計(jì)算速度較慢。

例5.1用二分法求方程/=4sinx在區(qū)間自7T］內(nèi)的根，要求絕對(duì)

誤差小于10一8.

解記/(c)=①一4sinc,則/⑶e0(假,行］),且其滿足

7T7T

/(9)=?-4<°，/W=7T>0.

此外，曾6區(qū)對(duì)有

產(chǎn)⑶=1—4cos/>0,

即/⑶在區(qū)間隹句上單調(diào)遞增。因此,原方程在區(qū)間詼加內(nèi)有唯一根。

編制函數(shù)文件f.m:

functiony=f(x)

y=x—4：sinx

運(yùn)行Matlab命令九Q/(7F/2,TT,10-8)得滿足精度要求的數(shù)值解

%=2.47457678796451,

其需迭代28次?！?/p>

§5.1.2弦截法

設(shè)方程(2)中函數(shù)在區(qū)間[a,b]上除滿足(3)外還滿足如下

條件：存在精確解7*的一個(gè)鄰域SQ*,6]={x:\x-x^\<d}C

[Q,可使得f⑺在該鄰域內(nèi)二階連續(xù)可微，且

f'37^0,VxGS(/*,5),(4)

里叫」/〃(叫6

_*eSQ*,8)

W：=2minIfM|-(5)

-WS(談』)

今在鄰域SO**)="—N*<6}內(nèi)任取二點(diǎn)作以

(g,/(3))和QiJ(g))為端點(diǎn)的弦

人：

其與X軸相交于點(diǎn)

力1-3\

◎=為一一）一〃

進(jìn)一步，作以QiJQi））和（物/（3））為端點(diǎn)的弦

，2：y=/（62）+-力2）,

X2—Xy

其與X軸相交于點(diǎn)

力2-3一、

磔=妝./（旬―/3）/3）；

如此循環(huán)往復(fù)，可得一列逼近X*的點(diǎn)，/Q-?（見圖

5.1）,其一般表達(dá)式為

跳+i=八12….（6）

該公式所表征的求解方法稱為弦截法或割線法。

理論分析表明：當(dāng)條件(3)-(5)成立時(shí)，由弦截法⑹產(chǎn)生的序

列｛交｝收斂于精確解￡*,且有如下誤差估計(jì)

2min\f,M\

⑺

max"1

此S（2*@）

例5?2用弦截法求方程I=4sinx在區(qū)間質(zhì)河內(nèi)的根，要求

-8

\xk-xk-i\<10o

解記/(幻=1—4sini。例5.1的求解過(guò)程已表明方程/(為=0

在區(qū)間［f,7T］內(nèi)有唯一根。今取初始迭代點(diǎn)g=7T/2,%=7T,應(yīng)

用弦截法(6)到該方程得滿足精度要求的數(shù)值解

X=2.47457678736983,

其需迭代7次?！?/p>

例5.1與例5.2相比較，顯見弦截法的收斂速度要快于二分法

的收斂速度。此外，若弦截法產(chǎn)生的迭代序列跳充分接近于精

確解/*,則以—與/(跳)均充分接近于零。因此，我們可近

似地置xk-xk-ix/(跳)，從而弦截法可改造為Steffensen方法

3+1=以一而八3)

J\xk)~J\xk~J\^k))

一般而言，Steffensen方法的收斂速度要快于弦截法，例如：

我們?nèi)羧〕跏嫉c(diǎn)g=7r/2,應(yīng)用Steffensen方法(8)到例

5.2中的方程/=4sini,則經(jīng)6次迭代后，可得滿足精度要求

\xk-ml<10—8的數(shù)值解7=2.47457678736983.

§5.2Picard迭代法

本節(jié)將基于不動(dòng)點(diǎn)原理給出非線性方程的Picard迭代法。

§5.2.1標(biāo)量方程的Picard迭代法

將非線性標(biāo)量方程⑵情形等價(jià)地寫成

/=夕0),(9)

其中夕(])為連續(xù)函數(shù)。該方程的求根問(wèn)題在幾何上可視為求曲

線9=以7)與直線g=7的交點(diǎn)P*的橫坐標(biāo)7*。因此，我們可從

這一幾何觀點(diǎn)出發(fā)來(lái)構(gòu)造求解方程⑼的數(shù)值算法。

圖5.2.Picard迭代

重復(fù)上述迭代過(guò)程，可得點(diǎn)列外,￡,????（見圖5.2）,

其橫坐標(biāo)滿足公式

叫+1=3（4），A:=0,1,2,-??.（10）

上迭代過(guò)程表明，若迭代函數(shù)夕及初始逼近值g選擇恰當(dāng)，則

點(diǎn)歹久只｝/逐步逼近廣，即迭代序列以收斂于I*（見圖5.2中左

圖）；否則，迭代過(guò)程發(fā)散（見圖5.2中右圖）。由公式（10）確定

的方法稱為Picard迭代法。

例5.3利用Picard迭代法迭代法求方程

x3—2/+/—2=0

在x=1.8附近的近似根跳，并使其滿足血-跳_i|<10-8

解其方程可寫成下列等價(jià)形式

x—步2/2―/+2,

由此得Picard迭代公式

"一6k+2,k0,1,2,,*,,7。=：1.8.

根據(jù)該迭代公式，經(jīng)31次迭代后，可得其方程在x=1.8附近且滿

足精度要求的近似根31=1.99999998890913c

若取其方程的另一等價(jià)形式

x=—x3+2?+2,

則有迭代格式

力卜+1——+2,ZL=0,1,2,,,?,XQ—1.8.

根據(jù)該迭代公式，經(jīng)10次迭代后，計(jì)算機(jī)發(fā)生溢出，無(wú)法獲得

滿足題設(shè)精度要求的近似根。■

§5.2.2非線性方程組的Picard迭代法

Picard迭代法(10)也可推廣應(yīng)用于非線性方程組情形(1),其有

如下Picard送代格表

Xk+i=<D(Xk),k=0,1,2,…(11)

這里Xk=儂化曖)，…，需))T,方程組

X=①(X),XeCRn(12)

與方程組⑴等價(jià)。為簡(jiǎn)單見，以下我們簡(jiǎn)稱G-可微為可微。

綜合中值公式(1.27)與定理1.24可直接獲得迭代格式(11)的收

斂性判據(jù)。

定理5.1設(shè)中：。UIT一肽”于閉凸集。QU。上連續(xù)可微，且

滿足

’①(Oo)uOo,q=sup||d(X)||<1,(13)

XeR)

這里||?||是中給定向量范數(shù)，則方程組(12)有唯一不動(dòng)點(diǎn)

X*€Do,迭代格式(11)自任意迭代初值X。6R)出發(fā)收斂于該

不動(dòng)點(diǎn)，且有先驗(yàn)誤差估計(jì)

||X*-Xk||S4||X1—Xo||,k=l,2…(14)

i-q

及后驗(yàn)誤差估計(jì)

||x*—Xk||s4||Xk_Xk_J|,k=L2….(15)

"q

由此可導(dǎo)出標(biāo)量方程(9)的迭代格式(10)的收斂性準(zhǔn)則。

推論5.1若迭代格式(10)的迭代函數(shù)夕(/)在[&b]上連續(xù)可微，

且滿足

(1)a<<b,\/xE[a,5],

(2)q:=sup|/O)|<1,

則方程⑼有唯一不動(dòng)點(diǎn)1*G[Q,“，迭代格式(10)自任意迭代初

值gG[a.b]出發(fā)收斂于該不動(dòng)點(diǎn)，且有誤差估計(jì)式(14)及(15)

成立。

此外,對(duì)于Picard迭代法，我們還有如下局部收斂性準(zhǔn)則。

定理5.2設(shè)中：。u肽，，-在其不動(dòng)點(diǎn)X*RD處及其某鄰域

內(nèi)連續(xù)可微，且存在國(guó)，中的某向量范數(shù)II-||使得

||①，(X*)||<1,(16)

則存在X*的某鄰域S(X*,6)：={XeRn：||X—X*|W6},使

得迭代格式(11)自任意迭代初值X。GS(X*,b)出發(fā)收斂于不動(dòng)

點(diǎn)X*。

證既然小于其不動(dòng)點(diǎn)x*e。處及其某鄰域內(nèi)連續(xù)可微，且有

||*(X*)||<1,則存在0<q<1及b>0使得

快(X)||一<1,X-S(X*,b).

從而，對(duì)一切xeS(x*,b),由中值公式有

網(wǎng)X)—X*||=||①(X)—①(X*)||

<sup惟,(x*+e(x—x*))||||x—x*||

0<0<1

<q1|X—X*|j

即中(X)eS(X*,8).故應(yīng)用定理5.1即得本結(jié)論?！?/p>

上述結(jié)論不僅給出了Picard迭代法的收斂性準(zhǔn)則，而且給出

了計(jì)算程序的終止準(zhǔn)則，即若要求計(jì)算精度滿足|X*-X,||<￡

時(shí)，我們只需近似用條件\\Xk-X"i||<￡來(lái)控制迭代過(guò)程的終

止，然后以當(dāng)前迭代值Xk作為滿足精度要求的數(shù)值解。

例5.4利用Picard迭代法求解非線性方程組

x=0.5cosx—0.5sin（*）

{y=0.5sinx+0.5cosg,

并要求所得數(shù)值解Xk滿足精度要求：||Xk-Xk_i||2<10-8o

解記

X①(X)=Icosx—siny

X=

y乙sinx+cosy'

則其Jacobi矩陣

1—sin/—cosy

①'(X)

=2cosa;—siny?

顯然該矩陣的元素均在R2上的連續(xù)，因此中(X)在R2上連續(xù)可

微。若取。()={Xe肽2：lixgsi},由于VXe股2有

11______________

II①(X)，2=-\/(cosx—siny)2+(sinx+cos?/)2=+sin(\—y)<

2v2

cVXe2eR

則中(。())DQO又肽及人有

det[A/-仲<X))T(6(X))]

i4A—sin2x—cos2ysinxcosx—sinycosy

4sinxcosx—sinycosy4A—cos2x—sin2y

=4A2—2A+|cos2(x—y)

其多項(xiàng)式的根為無(wú),2=當(dāng)用也因此

—=夜@(用)丁仲"))]

=Jmax{J1-疝『[j《標(biāo)

從而有sup忡'(X)||2<1。故據(jù)定理5.1,Picard迭代格式

XsDo

Xk+1=中(Xk),k=0,1,2,…；Xo=(0,0)T

收斂于其方程組的解。利用該迭代格式計(jì)算方程組(17),經(jīng)27

次迭代后得滿足精度要求的數(shù)值解

T

X27=(0.22905926899460,0.54189671768053).■

§5.2.3加速收斂技術(shù)

下面，我們改進(jìn)Picard迭代方法，使其迭代收斂過(guò)程得以加速

運(yùn)行。設(shè)Jacobi陣中'(X)在X*的鄰域內(nèi)變化不大，其近似矩陣

為P,則由Taylor展并式有

X*—孰Xk)=①(X*)-縱XQ

=fo①'(Xk+WX*—Xk))(X*—Xk)gXP(X*—Xk),

即

X*x(1—P)T怦(Xk)—PXJ

由此得加速迭代公式

Xk+1=(1—P)T饞(Xk)-PXk],k=0,1,….(18)

例5.5取迭代初始向量X0=(0,0戶，利用加速迭代公式求解方

程組(17),并要求所得數(shù)值解Xk滿足精度要求：||Xa-X"i||2<

10一8。

解記

x1cosx-sinyP"(Xo)=[；二.

X=，①(X)

y2sinx+cosy乙

則得加速迭代格式

Xk+1=g；21卜(Xk)_10-1

10,k=0,1?,???

利用該迭代格式計(jì)算方程組(17),經(jīng)11次迭代后得滿足精度要

求的數(shù)值解

Xn=(0.22905926751849,0.54189671634967)^.■

例5.5表明，加速迭代格式大大加快了Picard迭代方法的收斂

速度，但該方法的缺陷是需要確定矩陣P,而這在實(shí)際問(wèn)題的計(jì)

算中是非常困難的。對(duì)于標(biāo)量非線性方程（9）,我們有一種克服

該困難的方法，即所謂的Aitken加速迭代法。記

私+1=以沖），金k+i=3（通+1）,

則由Taylor展開定理近似地有

/*-xk+ix,(/*-xk\/*-ifc+i~0(i*-

由上二式消去未知常數(shù)p得

(誦+1—誦：+1)2

*人

x

力?k+l~

金k+1—2/卜+1+6k

故得Aitken加速迭代公式

14+1=夕―,

以+1=夕(交k+1),(19)

Xk+i=誦+i—1

八十［八十］x-2xi+x^

!k+1k+k

例5.6利用Aitken加速迭代公式求方程

X3—2/+/—2=0

在x=1.8附近的近似根3,并使其滿足\xk-跳_i|<10丑

解取__________

xo—1.8,#(1)=</272—7+2,

應(yīng)用Aitken加速迭代公式(19)求解方程，經(jīng)3次迭代后，

可得其方程在x=L8附近且滿足精度要求的近似根g=

2.00000000000000o

若另取

夕⑶=—X3+2?+2,

應(yīng)用Aitken加速迭代公式(19)求解方程，經(jīng)6次迭代后，可得

其方程在x=1.8附近且滿足精度要求的近似根方=2?！?/p>

與例5.3比較，例5.6表明：Aitken迭代法大大加速了Picard迭

代公式的收斂速度，而且在某些情形下，Aitken迭代方法可將一

個(gè)發(fā)散的Picard迭代過(guò)程改造成一個(gè)收斂的迭代過(guò)程。

§5.3Newton迭代法

§5.3.1標(biāo)量方程的Newton迭代法

為求解標(biāo)量方程（2）,我們考慮如下迭代方法：在方程⑵的解

的隔離區(qū)間［a,b］上選取適當(dāng)?shù)踔礸,過(guò)曲線沙=f⑺的點(diǎn)

（如產(chǎn)（3））引切線

沙=/（g）+/'（必）（①一。o）

與X軸相交于點(diǎn)

_/（g）

X1=XQ———r；

/（3）

進(jìn)一步，過(guò)曲線g=于⑺的點(diǎn)（gJQi））引切線

?沙==（的）+/'麗（①一①i）

與X軸相交于點(diǎn)

_fM）

X2=Xi——-~r；

/⑶）

如此循環(huán)往復(fù)，可得一列逼近X*的點(diǎn)力0,力1,-?，跳,-?（見圖

5.3）,其一般表達(dá)式為

_____/（利-1）「1Q

工k—^k—1f/（.y,k,—1,2,???（20）

該公式即稱為Newton迭代公式，其相應(yīng)求解方法稱為Newton迭

代法或切線法。由圖5.3可見，當(dāng)?shù)踔?選擇恰當(dāng)時(shí)，點(diǎn)

列…，也,…，將逼近標(biāo)量方程⑵的精確解x*o

圖5.3.Newton迭代法幾何圖示.

例5.7用Newton迭代法求方程x=4sinx在區(qū)間［f,7r］內(nèi)的根,

-8

并使其滿足|跳—xk-i\<10o

解記于⑸=7一4sin/,,并取g=梟應(yīng)用Newton迭代法(20)

于方程x=4sinx,經(jīng)7次迭代后，用得滿足精度要求的數(shù)值解

叼=2.47457678736983?！?/p>

將例5.1與例5.7相比較，顯見Newton迭代法的收斂速度要遠(yuǎn)

遠(yuǎn)快于二分法的收斂速度。

§5.3.2非線性方程組的Newton迭代法

標(biāo)量方程的Newton迭代法也可推廣到非線性方程組⑴情

形。事實(shí)上，若記方程組(1)的精確解為X*,其第k次逼近值為

Xk,則由一階Taylor展開式有

9(X*)xF(XQ+尸'(X4X*-Xk).

由F(X*)=0及上式得

X**Xk—尸(Xk)「5(X。.

故得方程組情形的Newton迭代公式

Xa+1=Xk—F'(Xk)]Tp(x。，k=o,12…?(21)

為節(jié)省每步計(jì)算Jacobi陣F\Xk)的時(shí)間，我們有時(shí)也可采用如

下簡(jiǎn)化的Newton迭代公式

Xk+i=Xk—k(X0)]T尸(Xk),k=0,1,2,….(22)

例5.8取迭代初始向量X()=(0,0)T,利用Newton迭

代法求解方程組(17),并要求所得數(shù)值解Xk滿足精度要

解記

12x—cos/+siny

X=,9(X)=-

y，「22y—sinx—cosy'

應(yīng)用Newton迭代公式(21)計(jì)算方程組(17),經(jīng)5次迭代后得滿

足精度要求的數(shù)值解

=(0.22905926720286,0.54189671602062)7.■

由例5.8可見，Newton迭代法的收斂速度要快于Picard迭代

方法及其加速迭代格式的收斂速度。但Newton迭代法有一個(gè)不

足之處，即其要求選擇一個(gè)恰當(dāng)?shù)牡踔礨。，方可保證迭代

過(guò)程快速收斂。為盡量避免因初值X。選擇不當(dāng)而導(dǎo)致迭代過(guò)

程緩慢收斂或發(fā)散，我們?cè)贜ewton迭代公式中引入一個(gè)下山因

子》:0<A<1,從而產(chǎn)生下述Newton下山法

Xk+1=Xk-可尸(Xk)「i"Xk),k=0,1,2,….(23)

在實(shí)際計(jì)算中，入可依次取為1/，亮…，再…，并且采用雙

精度控制：

||Xk+i—X疝2<勺或||尸(Xk)，2<%

這里￡1,￡2為預(yù)定精度。Newton迭代法(21)的收斂性可由如下

Kantorovich定理給出。

定理5.3若尸：。u史一Rn在開凸集AU。上連續(xù)可微，

且存在常數(shù)必用)>0,IT上的范數(shù)|HI及X。GDQ使得

(Q)\\F\X)-Ff(Y)\\<a\\X-Y\\,VX、”D。、

(b)I尸(X)T||SG,VXePo,

?7：=IIF'(Xo)]T9(Xo)||,77:=Q/?7<I，

(d)S(X0,27):={X:||X-Xo||<27}CDo,

則方程組(1)在S(X(),27)內(nèi)有唯一解X*,且Newton迭代法(21)

收斂于X*,其迭代解Xk€S(X(),27)且滿足誤差估計(jì)

在該定理?xiàng)l件下，簡(jiǎn)化的Newton迭代法(22)也收斂于方程組

⑴在S(X(),2])內(nèi)的唯一解X*,其證明參見下節(jié)定理5.6。

§5.3.3迭代法的收斂速度

求解非線性方程(1)有多種迭代方法，以下我們需給出一個(gè)評(píng)

價(jià)其收斂速度的指標(biāo)。

定義5.1設(shè)有求解非線性方程(1)的迭代方法，其第k步數(shù)值

解的迭代誤差為ek.=|||X*-X,||,這里X*為方程(1)的精確

解，卜||為肽九中的某向量范數(shù)。若存在常數(shù)c,0>0,使得

p

||efc+i||<c\\ek\\,k=0,1,…，

則稱該迭代方法是。階收斂的。特別，當(dāng)p=l時(shí)，稱其為線性

收斂的；當(dāng)夕>1時(shí)，稱其為超線性收斂的；當(dāng)°=2時(shí)，稱其

為平方收斂的。

在適當(dāng)條件下，我們可證明：弦截法(6)是超線性收斂

的，Steffensen方法(8)是平方收斂的。對(duì)于一般Picard迭代法，

我們則有如下收斂階判據(jù)。

定理5.4設(shè)中(X)在其不動(dòng)點(diǎn)X*處及其某鄰域內(nèi)p階連續(xù)可

微，且

叫X*)=0(￡=1,2,…，0—1),①⑼(X*)#0,

則Picard迭代法(11)是夕階收斂的。

證明由于中在其不動(dòng)點(diǎn)X*e。處及其某鄰域內(nèi)連續(xù)可微，

且①但*)=0,則據(jù)定理5.2,存在X*的某鄰域S(X*,b),使

得迭代格式(11)自任意迭代初值XoGS(X*⑼出發(fā)收斂于不

動(dòng)點(diǎn)X*。又據(jù)Taylor展開定理及已知條件，存在X*的某鄰域

S(X*花)z)S(X*,b),使得所有XkwS(X*,使且有

①(Xk)中(X*)+￡吧戶(Xk-X*)。