第一章緒論

1、誤差估計

(1)設(shè)x為真值(精確值)，x*為x的一個近似值。稱e*=e(x*)=x*-x為近似值x*的

絕對誤差，簡稱誤差。如果卜*|=|x-x*卜￡,則稱￡為近似值x*的絕對誤差限，簡稱誤差

限。

?*

pX—X

(2)近似值X*的誤差e*與準(zhǔn)確值X的比值j=二_^,稱為近似值x*的相對誤差，記作

xx

**

pX—Y

e,*=e,(x*)(實際計算時，由于真值x常常是未知的，通常取a-；?=「一)；如果

xx

|<|<7>則稱〃為近似值x*的相對誤差限。

(3)若近似值X*與準(zhǔn)確值的誤差不超過某一位的半個單位，且該位到X*的第一位非零數(shù)字

共有〃位，則稱￡有〃位有效數(shù)字。用數(shù)學(xué)的語言描述，即若x的近似值寫作：

X*=±10mxffljxlO-1+。2xl。-?+?,,+%xlO-A+…+Q〃xl(T"+…)(1.1)

其中m是整數(shù)，。戶0,q,心，…，4是。到9中的一個數(shù)字，若k*T<；xlO"""，則

X*至少具有〃位有效數(shù)字，即4,陽，…，a“為有效數(shù)字，而凡+i，…等則不一定是有效數(shù)字。

注：由上述定義知，當(dāng)x*是x的區(qū)川按照四舍五入原則得到的近似數(shù)，則x*具有〃位

有效數(shù)字。若X*的每一位都是有效數(shù)字，那么稱X*為有效數(shù)。

m)按照四舍五入原則分別寫出下列各數(shù)具有5位有效數(shù)字的近似數(shù)：132.2316、

0.02565552、1.000035.3.237183,并指出它們的絕對誤差限和相對誤差限。

分析此例考察有效數(shù)字、絕對誤差限和相對誤差限的定義。

解：上述各數(shù)具有5位有效數(shù)字的近似數(shù)分別為：132.23、0.025656、1.0000、3.2372

絕對誤差限分別為：-xlO-2,-xlO-6,-xlO-4,-xlO-4；

2222

相對誤差限分別為：-xlO-4,-xlO-1,-xlOM,-xlO^o

2222

注：有效數(shù)字從第1位非零數(shù)字開始；第1位非零數(shù)字后面的零有意義。

EditedbyFoxitReader

Copyright(C)byFoxitSoftwareCompany,2005-2008

ForEvaluationOnly.

例2如果x的近似數(shù)x*=±%4…《“.可用…勺具有〃+1-s位有效數(shù)字，則其相對誤差

Y—V*1

限有估計式<—xlO-'^,若其中a,w0是x*的第位有效數(shù)字。

x2as

分析此例給出了有效數(shù)字和相對誤差兩者之間的關(guān)系，故需從有效數(shù)字和相對誤差定義來

考慮。

ra

證明：若s=0,此時《尸0,由(1.1)式知|x*|>aoxlO

因為￡具有〃+1(s=0)位有效數(shù)字，則，一#gxl(y"f

x-x

<---x-xl0w-(,=—X10-"

m

aoxlO22ao

若swO,此時m=0,則有卜*上4*10一‘

<-------x-xlO-"=—xl0'(,,-5)

axlO^2la.

s_____s

例31使而的近似值的相對誤差限小于0.1%,至少應(yīng)取兒位有效數(shù)字？

芬S此例是尋求相對誤差限和有效數(shù)字兩者之間的關(guān)系，可以利用例2結(jié)論。此題的另一

說法是：取幾位有效數(shù)字就能確保近似數(shù)的相對誤差不超過0.1%。

解因為a=4.4…，故在例1中，5=l,/n=0,4=4,<—xlO-0-0,

令±^K」一xl0iT<0.1%則〃N4,

X*|2x4

所以，只要而取4位有效數(shù)字即可滿足條件，而a4.472。

例4取曬的6位有效數(shù)9.94987計算10-屈，則以下兩種算法各有幾位有效數(shù)字?

算法1：10-V99?10-9.94987=0.0501^)

算法2：10-799=-----—=-----------

10+炳10+9.94987

分析利用有效數(shù)字的多少來比較不同算法的優(yōu)劣，說明了算法選取的重要性。

解記*=回,丁=9.94987,e(x*)=x*-x,則；xl()T,

由e(10-x*)a-e(x*)得|e(10-x*)|?|e(x*)|^-xl0-5

2

所以由有效數(shù)字的定義，算法1：10一回力0.05013至少具有4位有效數(shù)字。

又由e(10+J)ae(x*)，卜(10+x*)|?|e(x*)|<—xlO-5,得

2

e(x，)xl5

71

e(_L>.Il<I°'=0.1256xl0-7<-xl0-7

V1O+X*J(10+x*)2-(10+9.94987)22

所以，算法2：10-799=a0.050125639至少具有6位有效數(shù)字，即

10+V99

10-799=-=0.0501256?

10+V99

2、誤差的傳播分析

（1）向前誤差分析法

假設(shè)所討論的算法由若干公式表達，某個新的量x由已知量（前面已算出的量或原始數(shù)

據(jù)）q,…M”的某個公式定義，寫成X=gS],4，…,%），X從q,%,經(jīng)過基本

的算術(shù)運算得出。因為計算過程中產(chǎn)生舍入誤差，實際計算值記作X*,它與精確值X不同。

對于一些簡單情形，利用誤差限，隨著計算過程逐步向前進行分析，直至估計出最后結(jié)果的

舍入誤差,-|的界，這種方法稱為向前誤差分析法。

例如：設(shè)兩個近似數(shù)X：和X；,其誤差限分別為￡（x：）和￡（x；）,它們進行加、減、乘、除

運算得到的誤差限分別為

￡（X；士X；）?i￡（X；）±￡（X；）;￡（X；X；）*卜；[￡（*；）+卜；歸（工）；（1.2）

,X；、|x：|￡（x；）+|x；|e（K）,.八、

1

e（T）?———4------U2*0）

%同

特別，設(shè)計算函數(shù)值A(chǔ)=f（x1,x2,---,xn）,如果x”了2,…,x”的近似值為x：,x；,…,x：,

則A的近似值為A*=/（x：,工,…,X：）,函數(shù)值4"的誤差可由Taylor展開方法得到：

e(A*)=A*-A=f(x*,x*,---x*)-f(x],x1,---xll)^^"但丁，~~(工一乙)

制風(fēng))

所以誤差限為e(A*)a支紗區(qū)廣，…”")[工)

Mdxk

相對誤差限為6：=fr(A-)?￡-(*：金,…？/2

(2)誤差分析原則

由于誤差分析的復(fù)雜性，數(shù)值運算中應(yīng)注意以下幾點原則：

①盡量避免除數(shù)絕對值遠遠小于被除數(shù)絕對值的除法；

②盡量避免兩相近數(shù)相減，以免有效數(shù)字消失；

③注意運算次序，防止大數(shù)“吃掉”小數(shù)；

④注意簡化計算步驟，減少運算次數(shù)。

例5設(shè)x=10±5%,試求函數(shù)f(x)=6的相對誤差限。

分析這是一元函數(shù)的誤差傳播問題，只需利用傳播公式計算即可。

解：由x=10±5%知近似值為x*=10,絕對誤差限為￡(X*)=5%。

利用7(E)=-(x*)?-1=VF3得到：

nnx

一.八e(f?)/'(X?陽J)e(x-)0.005

皿)=5FLk丁

例6設(shè)計一種算法計算*256,要求所用乘法次數(shù)盡可能少。

分析要盡可能地減少運算量，最常用的思路就是盡可能利用已經(jīng)計算出的結(jié)果，避免重復(fù)

運算。

解：X256=X128XX128=X64XX64XX128

=X32XX32XX64XX128=X16Xx16xX32XX64XX128

=...=xXXXX2XX4XX8Xx16Xx32XX64XX128o

而2計算球體積時要使相對誤差限為1%,問測量半徑時允許的相對誤差限是多少?

分析本題主要考察誤差在計算過程中的傳播，仍然利用微分方法進行分析。

解：球體積y=求微分得dV=4萬所以有

3

“八e(V)dV4爪玲派e(R).

e(V)=------?——=-------------=3d—R?3-------=3e(R),

rVVVRRr

er(Z?)?-er(V)^-xl%=^-?

r3r3300

例8證明：底的相對誤差約等于x的相對誤差的g。

分析本題主要考察誤差傳播的分析方法一微分方法。

r

解I。（3口||/（x）e（x）||r（x）e（x）|1|e（x）|_er（x）

例9對解耍狒:=-3,105,x；=0.001,x；=0.100，估計下列算式是相對誤差限

XXX

H=x；+x；+x；；72=；；；；y3=^/.?

分析根據(jù)有效數(shù)的定義首先確定出自變量誤差限，然后利用誤差傳播關(guān)系式。

解：已知有效數(shù)的絕對誤差限為e（x：）=e（x；）=e（x；）=0.0005,從而相對誤差限為

er(X：)=0.00016,e,(x；)=0.5,er(x*)=0.005,

er(j*)?e(xf)+e(x*)+e(xj)=0.0015,

由絕對誤差限的傳播關(guān)系式得

e(7；)。kH|e(%；)+k：x；|e(x；)+|x；x；|e(x；),3小君）+

所求算式的相對誤差限為

40-001K004?0-0005

?（［；）=V(x；)+(x；)+(x；)力0.50516

*(x；)+e,(x；)=0.505

例10用4位三角函數(shù)值表，怎樣計算才能保證1-COS2。有較高的精度？

分析此題意在考察對“在算法設(shè)計中應(yīng)避免相近的數(shù)相減”原則的掌握程度，主要方法就

是采用恒等變形方法一Taylor公式、三角變形、分子或分母有理化等。

解：法1直接計算查三角函數(shù)值表知cos2°a0.9994,于是1-cos2°修0.0006,至多有

1位有效數(shù)字。

法2用三角半角公式有l(wèi)-cos2°=2sin21,郊2x0.01752=0.0006125,至多有4

位有效數(shù)字。

sin220003492

法3利用變形1一cos2。-------?—-------?0.0006092,至多有4位有效數(shù)

l+cos201+0.9994

字。

注：上述結(jié)果與其真值l-cos21=0.00060917298…比較，法3結(jié)果更精確一些。另外，

本題也可以利用Taylor公式得到更好的近似值。

例11求方程必-56*+1=0的兩個根，使其至少具有4位有效數(shù)字。(要求利用

V783?27.982)

分析此例考察在運算過程中應(yīng)該注意的??些基本原則。

解：由求根公式得再，=%土’56--4=28土⑦價一1=28土，

1,22

取加號得到一個根為X,=28+V783=28+27.982=55.982,

取減號時，為了避免相近的數(shù)相減，采用如下方法計算：

x,=28-7783=——]-^==------J-------=0.01786,

28+V78328+27.982

從而保證每個根至少具有4位有效數(shù)字。

例12設(shè)xa80.128,y,80.115均具有5位有效數(shù)字，試分別估計這由些數(shù)據(jù)計算如下兩

表達式的絕對誤差限，并指出相應(yīng)的有效位數(shù)：

(1)-(X2+J2)?-(80.1282+80.1152)；(2)-(x2-j2)?-(80.1282-80.1152)

2222

分析此例考察初始誤差在運算過程中的傳播問題，應(yīng)用向前誤差分析方法分析。

解：x?80.128,j?80.115,|e(x)|^-xl0-3,|e(j)|-xlO-3,

22

(1)-(x2+y2)?-(80.1282+80.1152)=6419.4548045

22

；(/+j2)J?1+j2)?|1[e(x2)+e(j2)]?xe(x)+ye(y),

22

—(x2+j2)?\xe(x)+ye(y)\<x|e(x)|+j|e(j)|<80.128x—xlO-3+80.115x—xW3

2J22

=160.243x-xl0-3=80.1215xl0-3=0.0801215^-xl0°i-X104-

22

所以表達式（1）至少具有4位有效數(shù)字。

(2)^(x2-j2)?1(80.1282-80.1152)=1.0415795

-(x2+j2)?-e(x2-j2)?-[e(x2)-e(j2)]?xe(x)-je(j)

22

1

-(x2-j2)I?|xe(x)-je(j)|<x|e(x)|+j|e(j)|<-xlO°

2

所以表達式（2）至少具有1位有效數(shù)字。

例13已測得某場地長x的值為x*=110米，寬y的值為V=80米，已知卜一工［40.2

米，米。試求面積s=xy的絕對誤差限和相對誤差限。

分析此例是分析兩個自變量乘積的誤差，故可以利用（L2）式來考慮。

解因為s=xy,—=y,—=x,￡(X*)=0.2,￡(y")=0.l,

dxdy

絕對誤差限￡(s*)=f(x*/)?|x*|￡(j*)+|j*|f(x*)=110x0.1+80x0.2=27；

27

相對誤差限￡,(一)=——a--------=0.31%。

rs'110x80

例14寫出下列各題的合理計算路徑，使計算結(jié)果更精確（不必計算結(jié)果）。

1-COSX八口II11-x

(z1)-------,工00且國?1；(2)-----------,|x|?1；

sinx1+2x1+x

產(chǎn)+idt

(3)一,X?1;(4)|——TX?1;

XL1+1

(5)ax5+bx4+CX3,+dx2+ex+f(其中。仍,為已知常數(shù));

1001

(6)

A=2K1

分析：本題主要考察誤差分析的基本原則。

解：

2sin2—

1-cosx

(1)--------2—=tan-(避免很小的數(shù)作除數(shù));

sinxc.XX2

2sin—cox一

22

1-x

(2)(避免相近的數(shù)相減);

l+2xl+x(l+2x)(l+x)

2

x2

(3)(理由同(2))；

fx+idt1

(4)----7=arctan(x+1)-arctan(x)=arctan-------(理山同(2))

卜1+r1+x+x7

/工ILLI八z、tanx—tany

(利用公式tan(x-y)=-------------即得y);

1+tanxtany

(5)利用秦九韶法減少計算量

axs+bx4+cx3^dx2+ex+f=((((ax+b)+c)x+d)x+e)+f；

(6)避免大數(shù)吃小數(shù)

i(M)i10011

y^—=yl(—1

)=-(1+-------)?0.74005?

￡1—1￡2k-lk+l22100101

例15設(shè)?=0,1,2,?■?,10000

(1)證明：/?=e-n/?_1,〃=1,2,3,…,10000；

(2)給出一個數(shù)值穩(wěn)定的遞推算法，并證明算法的穩(wěn)定性。

分析此例是關(guān)于算法的穩(wěn)定性問題，要保證算法穩(wěn)定，必須保證隨著計算過程的增加，誤

差要減小或不增長，故需從每一步的誤差角度來分析。

(1)證明：由分步積分得

xnxxx

In=Jx"edx=Jxde=x"e［')—Jnx"~'edx=e—nln_t,n=l,2,---

(2)穩(wěn)定的遞推算法：

顯然上述遞推公式每一步誤差會增加，故不穩(wěn)定。

由(1)式解得“T=e-/“，如果已知，v，可得遞推算法：

n=N,N-l,N-2,-,l

n------------------------

-----1見文檔中值定癟

下面確定IN5積分中值磅/"=*［〉”公=今，^e(O,l)

因此—</,<—且/(1+e)4，T.(TO,當(dāng)時)

〃+1n+12(〃+1)2(〃+1)

.In_,=-(e-In),n=N,N-l,…,2,1

0+]n

故可取I=-------,得遞推算法："

N2(/1+1)/e+1

"-2(N+1)

此時有|1,1-］：1=；|/"一/：|，〃=N,N-1,…,2,1,可見誤差均在減少，從而穩(wěn)定。

例16某生產(chǎn)部門生產(chǎn)的一件產(chǎn)品需用7個零件，而這7個零件的質(zhì)量取決于零件參數(shù)的

標(biāo)定值，它們的參數(shù)允許有一定的誤差(參見表1)：

零件類別參數(shù)取值容許范圍零件類別參數(shù)取值容許范圍

X1[0.075,0.125]x5[1.125,1.875]

只用來求取標(biāo)定值

x2[0.225,0.375]x6[12,20]

x3[0.075,0.125]x7[0,5625,0.9375]

x4L0.075,0.125J

表1

若每一零件的標(biāo)定值取相應(yīng)的區(qū)間中點，在生產(chǎn)過程中每一零件的參數(shù)都有可能產(chǎn)生誤差，

由此將零件分成不同的等級：A,B,C三等，等級由標(biāo)定值的相對誤差限表示，A等為1%,

B等為5%,C等為10%,試確定三個等級的零件分別滿足的區(qū)間。

分析：結(jié)合一簡單的實際問題，考察相對誤差限的概念，有想確定三個等級的零件分別滿足

的區(qū)間，只需確定每一零件的標(biāo)定值的絕對誤差限。

解：7個零件的標(biāo)定值分別為（按順序）：0」0.30.10.11.5160.75

確定三個等級的零件分別滿足的區(qū)間

xl：A等[0.009,0.101]B等[0.095,0.105]C等[0.09,0.11]求出相應(yīng)的絕

x2：A等[0.297,0.303]B等[0.285,0.315]C等[0.27,0.33]對誤差極限后，在

標(biāo)定值上加減絕對

x3：A等[0.009,0.101]B等[0.095,0.105]C等[0.09,0.11]誤差即為零件需滿

足的區(qū)間

x4：A等[0.009,0.101]B等[0.095,0.105]C等[0.09,0.11]

x5：A等[1.485,1.515]B等[1.425,1.575]C等[1.35,1.65]

x6：A等[15.84,16.16]B等[15.2,16.8]C等[14.4,17.6]

x7：A等[0.7425,0.7575]B等[0.7125,0.7875]C等[0.675,0.825]

第二章非線性方程

1、二分求根收斂階

例1舉出一方程，有偶次重根，但不能用對分法求出它的這一偶次重根。

分析用對分法時，每次保留有根區(qū)間［%，4］的依據(jù)是被求根的函數(shù)/(X)在此區(qū)間端點滿

足/4)/屹)<0。

解如/(x)=(x—l)2,a=1e［0.5,2］,f(a)=0,但

/(0.5)>0,/(2)>0,/(1.25)>0

所以不能用對分法求出/(x)=0的這一偶次重根a。

點撥對分法實際上是將連續(xù)函數(shù)/(x)的有根區(qū)間不斷分半，依據(jù)是連續(xù)函數(shù)/(x)的兩個

異號函數(shù)值之間必有/(x)的零點，其收斂速度與公比為g的等比數(shù)列相同。

例2試求方程d-2x-5=0的正根所在的區(qū)間，并說明在此區(qū)間上用對分法求此根

時，若其截斷誤差不超過,X10一3,則所需的迭代次數(shù)是多少？

2

分析根據(jù)所給的方程，利用連續(xù)函數(shù)的性質(zhì)確定所求根的區(qū)間［a,切，而二分法的誤差為

b-a

\mn-a\-2〃+i

解令/(x)=/—2x—5,則f(x)=3x2—2,當(dāng)國2，：時，/'(x)>0,即函數(shù)

/(x)單調(diào)增；當(dāng)一Jg<x<，時，/'(x)<0,即函數(shù)/(x)單調(diào)減。因此

當(dāng)。。靖時，小)"(。)=-5<。；

當(dāng)后x42時,/(%)</(2)=-1<0；

而/(3)=16>0,f(x)>f(3)>0,Vx>3時，方程存在唯一的一個正根ae［2,3卜

在此區(qū)間上，二分法迭代時的誤差為一［,因此要1

<-xl0-3,即

2?12

、31nl0?

n>-----=9.966

In2

所需迭代次數(shù)為10o

例3證明二分法得到的序列｛4｝線性收斂.

證明：二分法產(chǎn)生的序列｛4｝滿足

N-X*歸擊=0,1,2,...

LIk+T||-*+「「玉|i產(chǎn)…

同k*-x*|4一x*

若X*>X*,則xA.+1<xk;若X*<X*,則xM>xk,因此

叱？<0,又卜—

Xr""""X乙

/S-a）

lim..=lim=lim

k—>8]|k—>oo上一KC93一。）2

故由二分法產(chǎn)生的序列｛xj線性收斂。

2、不動點迭代法及其收斂階

1、不動點迭代發(fā)的構(gòu)造

本章的各種求解非線性方程的根方法幾乎都可視為一種不動點迭代方法（區(qū)間二分法除

外）。構(gòu)造不動點迭代法的關(guān)鍵是由非線性方程/（x）=0出發(fā)，作同解變形化為x=e（x）的

形式，然后即可建立不動點迭代格式

4+1=。（七,）,"=0』,2,一-

不同的構(gòu)造方法，在收斂性，或收斂速率上是不一定相同的。因此在作同解變形時，必

須要注意到構(gòu)造出的迭代格式的收斂性及收斂速度.

2、不動點迭代法的收斂性和收斂速度分析

好的迭代算法必須是收斂的算法，更是收斂速度快的算法。因此不動點迭代算法的收斂

法證明，收斂速度的估計，是本章的重點和難點。收斂性證明可收斂速度的估計關(guān)鍵在于不

動點迭代公式的迭代函數(shù)°（x）的性質(zhì)，當(dāng)然也與初值天的選取有關(guān)。關(guān)于不動點迭代法的

全局收斂性定理和局部收斂性定理是我們必須掌握熟悉的內(nèi)容,它是分析各種不動點迭代算

法的依據(jù)，許多考試，特別是要求稍高的研究生考試中，有大的幾率出現(xiàn)分析迭代算法的收

斂性及收斂速度的題目。

不動點迭代算法的收斂性分析，我們一般依據(jù)不動點迭代法的局部或全局收斂性定理；

收斂階的估計，我們?般依據(jù)不動點迭代法的局部收斂階定理。但是如果迭代算法本身不是

整階收斂速率的，這類算法的收斂階估計，我們更多的是從收斂階的定義出發(fā)，尋找盡可能

大的p〉0,使

EditedbyFoxitReader

Copyright(C)byFoxitSoftwareCompany,2005-2008

ForEvaluationOnly.

\Ak/

要完成這項工作，往往借助一元函數(shù)的Taylor展式來完成。

例4用迭代法的思想，給出求V2+的迭代格式，并證明

^2+^2+4---1--^2+5/2

lim2。

解記/=亞，玉=亞二/?,則

X”=j2+x,i，〃=1,2,…

故上述迭代格式的迭代函數(shù)9(x)=岳二。

解得x*=2或x*=—1(不合題意，舍去)

故limx=2

上一＞8n

即

limJ2+J2+72+---+72+V2=2

例5對于迭代函數(shù)°(X)=X+C(X2-2),試討論

(1)當(dāng)c為何值時，V+1=雙%)(〃=0,12“)產(chǎn)生的序列｛怎｝收斂于夜；

(2)當(dāng)c取何值時收斂最快？

]___計算9(x)的不動點后，要求|x?-x?|<IO-

(3)分別取c+l

25272

解①夕(x)=x+c(x?-2),夕'(x)=l+2cx,由收斂定理知,‘(友)卜卜+2j^c、|<l

即—\＜。＜0時迭代收斂。

②由收斂階定理知，當(dāng)9(0)=1+2岳=0,即，=一一尸時迭代至少是二階收

2V2------一

斂的，收斂最快。

③分別取c=-4,——并取5=1,2,迭代計算結(jié)果

22j2

nX"(C=一])ng矗)

01.201.2

11.4811.397989899

61.41336958621.414120505

121.41420930331.414213559

131.41421532741.414213562

2

例6給定初值與±0,—以及迭代公式

a

xM=々(2-%),4=0,1,2???，常數(shù)一工0

證明①該迭代公式是二階收斂的；②該迭代產(chǎn)生的序列｛/｝收斂的充要條件是

|1一%|<1O

證明①迭代函數(shù)°(x)=x(2-ax),且9(,)=,，即,是**)的不動點，又

aaa

p(x)=2(l—ax),°"(x)=—2a,所以9(')=0,，(3=—2aH0,由收斂階定理知，迭

aa

代是二階收斂的，且lim%='/([)=—a

18q2a

(②因,=x*—=—(dxk—1)?令〃=ax*—1,則

，二、「L.2

~~鼠一1=“_](1一1=(4_]+1)(1一*)一1=一〃一]

由此可知lime*=0等價于lim4=0,而lim〃=0又等價于|〃|<1,BP|l-ax|<lo

々TOO&T80

例7設(shè)*(x)是一個連續(xù)可微函數(shù)，若迭代格式公""=夕"@)是局部線性收斂，對

于awR,構(gòu)造新的迭代格式

x(k+\)”+土火少)

2+1

問如何選取4使得新的迭代格式有更高的收斂階。

解：記新的迭代格式函數(shù)為0(x),它的表達式

/、41,、

<y(x)=-~-x+-~-o(x)

A+1丸+1

將不動點工=/代入上式，并注意到夕(x*)=x*,得

&(x*)=X

21

。(止丁廣丁了⑴

4+1A+1

要想使新迭代格式比線性高的收斂階，需使0(X*)=0,即

%+---(p(x*)=0

2+12+1

4=9(X*)]

1.'

co(%)=-~~(p(%)

2+1

一般情況下(y"(x*)=」一"(/)/0。因此選擇/1=0(x*),根據(jù)高階收斂定理知,

2+1

新迭代格式2階收斂。

例8設(shè)〃N2為正整數(shù),c為正數(shù).記X*=冊.(1)說明不能用下面的迭代格式

4+i=cx：T,k=0,l,2,…

求x*的近似值.

(2)構(gòu)造一個可以求x*的迭代格式，證明所構(gòu)造的迭代格式的收斂性，并指出收斂階數(shù).

解(1)記夕(x)=crj,則“(X)=c(l-n)x-/,,(p\x)=(l-n).

a)當(dāng)〃N3時,|"(x*)|=?-1>2，迭代格式發(fā)散.

b)當(dāng)”=2時,x*+]=￡,女=0,1,2,…

Xk

設(shè)/#x*,則有芭=￡wx*且七x*+|Hx*,4=0,1,2,…,

于是X2m=Xo,x2m+i=X],m=0,1,2,…

迭代格式不收斂.

(2)考慮方程/(x)=/-c=0,則X*為其單根，用Newton迭代格式

xk+\~xk一*=(1)x*k=0,1,2,…\jy

求解，由于Newton迭代格式對單根是2階局部收斂的，所以迭代格式當(dāng)/比較靠近X*時是收

斂的,且收斂階數(shù)為2

3.Newton切線法

例9設(shè)f"(x)在3句上連續(xù),且①/(。)/3)<0,②f(x)H0,對

”ur3自/⑷八I/⑸”

\/xG\ct,b\>③1—；—<b—a,—；—<b-a

一/(?)|/3)|

則對Wxoe[a,b],由Netwon迭代公式產(chǎn)生的序列{x,,}收斂于方程/(x)=0的唯一解

a。

分析

Newton切線法收斂定理，條件(3)主要給出了初值在[a,切中的位置，當(dāng)初值不滿足條

件(4)時，由切線法的幾何意義知，迭代一次得王卻滿足條件(3)。

證明：不妨設(shè)r(x)40,/1(x)>0,則/(x)是嚴(yán)格單調(diào)增函數(shù)，f(x)是單調(diào)減函

數(shù)，且/(a)<0,/(b)>0,a存在唯一。

此時條件(3)為—/(a)4(b—a)f(a),f(b)<(b-a)f\b)

即/(a)+3-a)f(a)2。，f(b)-{b-a)f\b}<0

①若飛€[。,0，此時/(%)</9)=0，/1(x0)/(x0)>0,由切線法收斂定理知:

結(jié)論成立。

②若Xoe[a力],(須將在何處？它是否會在[a,a]上？若是則由①知，結(jié)論成立.因

此即證：X,&[a,a},即要討論內(nèi)與的關(guān)系，首先看看占與a的關(guān)系。)令

g(x)=/(x)+(a-x)/'(x),Vxe[a,&],則

g'(x)=/'(x)+(a-x)/"(x)-/'(x)=(a-x)f"(x)>0,Vxe[a,b]

因而

g(x(1)=/(x0)+(a-x0)/1(x0)<§(/?)=f(b)+(a-b)fXb)<0

a<x-'(=x.

則Q

/Uo)

因/⑷=。，va=x0-a-器=Q-黑網(wǎng)-如"(g)

而/'G)Z/'(Xo),得X1<a?

所以修€[a,a|,則由①知，結(jié)論成立。

綜上所述，在此條件卜,，對任意初始近似/w切，由切線法迭代公式而得的序列卜“}

收斂于方程/(%)=0的唯一解a。

例10試就下列函數(shù)討論Newton法的收斂性和收斂速度

y[xx>0x>0

①/(x)=<②/(x)=<

-y/-Xx<0x<0

解①當(dāng)xZO時，于(x)=?,f(幻=」尸，其Newton迭代函數(shù)為

2y/x

/、

(p{x)=x---V-x--=-x

2y[x

當(dāng)x<0時，/(x)=-J耳，/(x)=—,其Newton迭代函數(shù)為

2y/-x

—yf-x

(p{x)=x-------=-x

2\[-x

則Newton迭代格式為xk+J=(p｛xk),k=0,1,…

②當(dāng)xNOff寸，于(x)=井,f(x)=gx《，其Newton迭代函數(shù)為

2-i/32

-X

3

當(dāng)x<0時/。)=一療，y'(x)=-|x3,其Newton迭代函數(shù)為

2-1/32

---X

3

而l°(x)l=l-但夕(x*)=gwO,故Newton迭代公式為

=-=,左=0,1,2,…

2

是收斂的，但只具線性收斂速度。

例11設(shè)/(X)=O有根，且0<〃2</'(X)("，試證明對于任意的初始與€(—8,8)

及0<幾<三2內(nèi)任意的2,迭代X.=乙—4/0,)產(chǎn)生的｛x.｝均收斂于方程/(x)=0的

M

根，并確定使迭代收斂得最快的值2。

證明：由題意在(-8,8)上/(X)嚴(yán)格單調(diào)增，則/(x)=0有唯一根a。

設(shè)g(x)=x-/l/(x),則g(x)在(一8,8)上存在一階導(dǎo)數(shù)且

2

-1<1——M<1-ZM<^'(x)<l-/l/'(x)=l-Z/n<l

M

2

所以對于任意的XG(—8,8)及0</l<—,l^'(x)l<L=max｛ll-/lM1,1l-Z/n1｝<1,

M

Vx0e(-00,00),-a=g(x0)-^(a)=^'(^0)(x0-a)<Llx0-al

同理I乙一aKLIX]-a14Z?IX。一aI；若Ix“一L"I玉)一aI,則

,,+l

Ixn+l-a1=1g'(^)(x?-a)l<LI(x?-a)l<Llx0-al,(在怎與a之間

2

因此，對VxoG(—8,8)及0</l<——，迭代七川=x“-/L/(x.)產(chǎn)生的序列｛X,,｝滿足

\xn-a\<V\xQ-a\?

當(dāng)〃foo時，一alWL"1/-。1->0,即limx〃=a

n—>00

由迭代收斂的誤差估計式：IX,-a二丁玉-小I知，L越小，收斂越快，使得L取

2M—m

最小值的4為4=-----，此時L=------，迭代收斂速度最快。

MM+m

例12當(dāng)R取適當(dāng)值時，曲線丁=/與y2+(x_8)2=R2相切，試用迭代法求切點橫

坐標(biāo)的近似值，要求不少于四位有效數(shù)字，且不必求R。

解y=f的導(dǎo)數(shù)y=2x,由V+a—8)2=R2確定的函數(shù)y的導(dǎo)數(shù)滿足

2yy+2(x-8)=0,由兩曲線相切的條件，可得

2xx?x2x+2(x-8)-0

即

2x3+x-8=0

令/(x)=2d+x—8,則/⑴<0,/(2)〉0,/(%)=0在(1,2)內(nèi)有實根。又

/'(X)=6X2+1>0,故/(x)=0僅有一個根。構(gòu)造迭代公式

8—x』