《計(jì)算方法》課件2第1章

1.1算法1.2誤差

習(xí)題一

1.1.1研究算法的意義

計(jì)算機(jī)雖然運(yùn)算速度高，可以承擔(dān)大運(yùn)算量工作，但正確制定算法才是科學(xué)計(jì)算的關(guān)鍵。

比如，基于行列式的克萊姆法則原則上可用來(lái)求解線性方程組。如求解一個(gè)20階線性方程組，要算21個(gè)20階行列式的值，總共需要20!×19×21次乘法運(yùn)算，大約1021次乘法。1.1算法

如用每秒可完成1億次乘法運(yùn)算的計(jì)算機(jī)來(lái)計(jì)算，需要的時(shí)間為

(年)

即需要三十幾萬(wàn)年，這當(dāng)然沒(méi)有實(shí)際意義，所以要研究可行的算法。本書(shū)第7章就提出了解線性方程組的許多實(shí)用算法。這個(gè)簡(jiǎn)單的例子告訴我們，能否正確制定算法是科學(xué)計(jì)算成

敗的關(guān)鍵。1.1.2算法

針對(duì)一個(gè)具體數(shù)學(xué)問(wèn)題，可以給出多種解法。

例1.1

證明二次方程x2+2bx+c=0至多有兩個(gè)不同的實(shí)根。解

(1)反證法。

假定方程有三個(gè)互異的實(shí)根x1,x2,x3，則有

以上式子兩兩相減得

(x1-x2)(x1+x2+2b)=0

(x1-x3)(x1+x3+2b)=0

因?yàn)閤1≠x2≠x3，所以有

x1+x2+2b=0

x1+x3+2b=0

從而x2=x3，這與原假設(shè)矛盾，證畢。

(2)圖解法。

將方程x2+2bx+c=0配方為

(x+b)2+c-b2=0

在坐標(biāo)紙上描出拋物線y=(x+b)2+c-b2，它與x軸的交點(diǎn)的橫坐標(biāo)即為所求的實(shí)根，而交點(diǎn)至多為兩個(gè)。

(3)公式法。

根據(jù)(x+b)2+c-b2=0，可導(dǎo)出直接的求根公式，即

上述三種方法，反證法不是構(gòu)造性的，圖解法雖是構(gòu)造性的，但不是數(shù)值的。我們所說(shuō)的算法，必須是構(gòu)造性的數(shù)值方法，即不但要論證問(wèn)題的可解性，而且解的構(gòu)造是通過(guò)數(shù)值

演算過(guò)程來(lái)完成的。

我們所要研究的算法是為計(jì)算機(jī)提供的計(jì)算方案，因此每個(gè)細(xì)節(jié)都必須準(zhǔn)確地加以定義，并且整個(gè)解題過(guò)程必須完整地描述。因此，算法不僅僅是單純的數(shù)學(xué)公式，而是指解題

方案的準(zhǔn)確而完整的描述。

描述算法可以用多種方式，本書(shū)常用框圖直觀地顯示算法。設(shè)要求解x2+2bx+c=0，我們將依據(jù)判別式d=b2-c的符號(hào)區(qū)分為下列三種情況：

(1)若d<0，則此時(shí)方程無(wú)實(shí)根。

(2)若d=0，則此時(shí)有重根x1=x2=-b。

(3)若d>0，則x1,2=-b±。

本算法的框圖如圖1-1所示。圖1-1二次方程求根1.1.3多項(xiàng)式求值的秦九韶方法

計(jì)算公式通常是算法的核心部分，計(jì)算機(jī)上使用的算法，其計(jì)算公式常采用遞推化的形式。遞推化的基本思想是將一個(gè)復(fù)雜的計(jì)算過(guò)程歸結(jié)為簡(jiǎn)單過(guò)程的多次重復(fù)，這種重復(fù)在

算法上表現(xiàn)為循環(huán)，比較容易實(shí)現(xiàn)。

設(shè)要對(duì)給定的x求多項(xiàng)式P(x)=a0+a1x+…+anxn的值。

1)直接計(jì)算

要對(duì)給定的一個(gè)x值計(jì)算多項(xiàng)式的值P(x)=a0+a1x+…+anxn,需要作1+2+…+n=

n(n+1)次乘法。

2)逐項(xiàng)求和法

設(shè)tk=xk，uk=a0+a1x+…+akxk，則有遞推公式

利用初值，對(duì)k=1,2,…,n執(zhí)行算法，得到：

k=1時(shí)，

k=2時(shí)，

k=3時(shí)，

以此類推，可得k=n時(shí)，

遞推公式的每一步需做兩次乘法，因此總的計(jì)算量為2n次乘法運(yùn)算。

3)秦九韶方法

設(shè)用Vk表示第k層(從里面數(shù)起)的值，即

Vk=(…(anx+an-1)x+…+an-k+1)x+an-k

則有

Vk=x·Vk-1+an-k,V0=an(k=1,2,…,n)

k=1時(shí)，

V1=x·V0+an-1=anx+an-1

k=2時(shí)，

V2=x·V1+an-2=(anx+an-1)x+an-2

以此類推，可得k=n時(shí)，

Vn=x·Vn-1+a0=(…(anx+an-1)x+…+a1)x+a0

每一步需做1次乘法，其計(jì)算量減少了一半。例如：

P(x)=3x3+4x2+2x+1=((3x+4)x+2)x+1

秦九韶方法是由宋代數(shù)學(xué)家秦九韶提出的，國(guó)外稱此算法為霍納(Horner)算法，其實(shí)它比秦九韶方法晚500多年。1.1.4方程求根的二分法

許多實(shí)際算法表現(xiàn)為某種無(wú)窮遞推過(guò)程的截?cái)啵瑢?shí)現(xiàn)這類算法，不但需要建立計(jì)算公式，還需要解決精度控制問(wèn)題。

設(shè)函數(shù)f(x)在［a,b］上連續(xù)，且f(a)f(b)<0，根據(jù)連續(xù)函數(shù)的性質(zhì)，f(x)在［a,b］內(nèi)一定有零點(diǎn)，即方程f(x)=0在［a,b］內(nèi)一定有根。假設(shè)它在［a,b］內(nèi)有唯一的單根x*，如圖1-2所示。圖1-2二分法示意圖考察有根區(qū)間［a,b］，取中點(diǎn)x0=(a+b)/2，檢查f(x0)與f(a)是否同號(hào),如果確系同號(hào)，說(shuō)明所求的根x*在x0右側(cè)，這時(shí)令a1=x0，b1=b；否則x*在x0左側(cè)，這時(shí)令a1=a，b1=x0。不管出現(xiàn)哪一種情形，新的有根區(qū)間［a1,b1］的長(zhǎng)度僅為［a,b］的一半。

對(duì)壓縮了的有根區(qū)間［a1,b1］又可施行同樣的處理工程，即用中點(diǎn)x1=(a1+b1)/2將［a1,b1］再分為兩半，判定所求的根x*在x1的哪一側(cè)，從而確定一個(gè)新的有根區(qū)間［a2,b2］，其長(zhǎng)度是［a1,b1］的一半。如此反復(fù)二分下去，可得出有根區(qū)間序列

［a,b］［a1,b1］…

［ak,bk］…

其中,每個(gè)區(qū)間長(zhǎng)度都是前一個(gè)有根區(qū)間長(zhǎng)度的一半，因此二分k次后的有根區(qū)間［ak,bk］的長(zhǎng)度為

可見(jiàn)，如果二分過(guò)程無(wú)限地繼續(xù)下去，這些有根區(qū)間最終必收縮于一點(diǎn)x*，這點(diǎn)顯然就是所要求的根。

實(shí)際計(jì)算時(shí)，我們不可能無(wú)窮計(jì)算下去，用作x*的近似值，其與x*的誤差為

若ε為給定精度，只要k充分大，一定能滿足條件|x*-xk|≤ε。

所以二分區(qū)間的次數(shù)為

(1.1)二分法的優(yōu)點(diǎn)是計(jì)算簡(jiǎn)便，對(duì)函數(shù)f(x)的要求不高，只要求連續(xù)即可，且誤差估計(jì)容易。二分法的缺點(diǎn)是收斂速度很慢，每計(jì)算一步，誤差減小—半。

例1.2

用二分法求方程x3-x-1=0在區(qū)間［1,1.5］內(nèi)的一個(gè)實(shí)根，要求誤差不超過(guò)0.005。

解首先估計(jì)二分法區(qū)間次數(shù):

所以用二分法6次運(yùn)算就達(dá)到精度，二分法的計(jì)算結(jié)果見(jiàn)表1-1。表1-1二分法的計(jì)算結(jié)果1.2.1誤差分析

在研究算法的同時(shí)，必須注重誤差分析，否則一個(gè)合理的算法也可能得出錯(cuò)誤的結(jié)果。

例1.3

用中心差商公式求在x=2點(diǎn)的導(dǎo)數(shù)值。

解中心差商公式為

1.2誤差從理論上說(shuō)，步長(zhǎng)h愈小，計(jì)算結(jié)果愈準(zhǔn)確，實(shí)際情況如何呢?

計(jì)算機(jī)上數(shù)據(jù)受機(jī)器字長(zhǎng)的限制，設(shè)取5位有效數(shù)字計(jì)算，則

f′(2)的精確解為0.353553…，取5位有效數(shù)字為0.35355。h=0.1時(shí)的結(jié)果還可以接受，h=0.0001的結(jié)果則毫無(wú)價(jià)值，因此要作變換

h=0.1,h=0.0001,

例1.4

求解方程x2-(105+1)x+105=0。

解取5位數(shù)字計(jì)算，化成x2+2bx+c=0形式，即

則x1=105，x2=0與原來(lái)精確解，結(jié)果嚴(yán)重失真，此現(xiàn)象稱為“大數(shù)吃小數(shù)”。

例1.5

考察方程組

，其精確解為如果把系數(shù)舍入成3位浮點(diǎn)數(shù)，即

求得x1=1.09，x2=0.488，x3=1.49。

盡管系數(shù)變化不大，但是所求出的解有很大出入，這類問(wèn)題稱作“病態(tài)問(wèn)題”或“壞條件

問(wèn)題”。計(jì)算這類問(wèn)題必須十分小心，一般采用高精度計(jì)算。1.2.2誤差的來(lái)源

一個(gè)物理量的真實(shí)值與我們算出的值往往存在差異，它們的差稱為誤差。提起誤差分析，往往給人不嚴(yán)格、不準(zhǔn)確、不夠完善的感覺(jué)，其實(shí)近似是正常的，誤差是不可避免的。

根據(jù)誤差的來(lái)源，可將誤差分為以下幾種：

1)模型誤差

用計(jì)算機(jī)解決科學(xué)計(jì)算問(wèn)題，首先要建立數(shù)學(xué)模型。數(shù)學(xué)模型是對(duì)被描述的實(shí)際問(wèn)題進(jìn)行抽象、簡(jiǎn)化而得到的。在建立數(shù)學(xué)模型過(guò)程中，不可能將所有因素均考慮在內(nèi)，必然要進(jìn)行必要的簡(jiǎn)化，忽略一些次要因素，簡(jiǎn)化許多條件，這就帶來(lái)了與實(shí)際問(wèn)題的誤差。數(shù)值計(jì)算方法不涉及模型誤差，通常都假設(shè)數(shù)學(xué)模型是合理的。

2)觀測(cè)誤差(測(cè)量誤差)

在數(shù)學(xué)模型中通常包含一些觀測(cè)數(shù)據(jù)，如溫度、長(zhǎng)度、電壓等，這些數(shù)據(jù)的值一般是由觀測(cè)或?qū)嶒?yàn)得到的，由于觀測(cè)手段的限制，得到的數(shù)據(jù)和實(shí)際大小必然有誤差，這種誤差稱為觀測(cè)誤差，又稱測(cè)量誤差。

3)截?cái)嗾`差(方法誤差)

許多數(shù)學(xué)運(yùn)算(諸如微分、積分及無(wú)窮級(jí)數(shù)求和等)是通過(guò)極限來(lái)定義的，然而計(jì)算機(jī)只能完成有限次的算術(shù)運(yùn)算和邏輯運(yùn)算。通常把無(wú)限的計(jì)算過(guò)程用有限的計(jì)算過(guò)程代替，由此產(chǎn)生的誤差稱作截?cái)嗾`差。因截?cái)嗾`差是方法固有的，故又稱為方法誤差。比如，ex可展開(kāi)為冪級(jí)數(shù)形式

用計(jì)算機(jī)求值時(shí)，只能截取有限項(xiàng)

Sn(x)與ex的值必然有誤差，根據(jù)泰勒余項(xiàng)定理，其截?cái)嗾`差為

(1.2)

4)舍入誤差

計(jì)算過(guò)程中所用的數(shù)據(jù)可能位數(shù)很多，甚至是無(wú)窮小數(shù)，如π，，1/3等，由于計(jì)算是按有限位進(jìn)行的，超過(guò)位數(shù)的數(shù)字要進(jìn)行舍入。這種由于在計(jì)算過(guò)程中對(duì)數(shù)進(jìn)行舍入而引

起的誤差，稱為舍入誤差。每一步的舍入誤差是微不足道的，但經(jīng)過(guò)計(jì)算過(guò)程的傳播積累，舍入誤差甚至可能會(huì)“淹沒(méi)”真解。數(shù)值分析中的測(cè)量誤差可看做初始的舍入誤差，因此數(shù)值分析主要研究的是截?cái)嗾`差與舍入誤差對(duì)計(jì)算結(jié)果的影響。

1.2.3誤差限和有效數(shù)字

設(shè)精確值x*的近似值為x，稱誤差x*-x為近似值x的絕對(duì)誤差，簡(jiǎn)稱誤差。

誤差x*-x的具體數(shù)據(jù)通常無(wú)法確定，人們只能根據(jù)測(cè)量工具或計(jì)算過(guò)程設(shè)法估算出它的取值范圍，即誤差絕對(duì)值的一個(gè)上界：

|x*-x|≤ε這種上界ε稱做近似值x的絕對(duì)誤差限，簡(jiǎn)稱誤差限或精度。

要將一個(gè)位數(shù)很多的數(shù)表示成一定的位數(shù)，通常采用四舍五入的方法，如

π=3.14159265…，可表示為π=3.14或π=3.1416等。

如果用3.14表示π，其誤差為0.0015926，誤差限為0.005=

×10-2，也就是說(shuō)誤差限為其最末一位的半個(gè)單位。如果近似值x的誤差是它某一位的半個(gè)單位，我們就說(shuō)x準(zhǔn)確到這一位，并且從這一位起直到前面第一個(gè)非0數(shù)字為止的所有數(shù)字稱為x的有效數(shù)字。

具體地說(shuō)，精確值x*的近似值(規(guī)格化形式)為

x=±10m(a1×10-1+a2×10-2+…+an×10-n)其中a1,a2,…,an是0～9之間的自然數(shù)，且a1≠0。如果誤差滿足：

(1≤l≤n)

則稱近似值x有l(wèi)位有效數(shù)字。

如3.14=0.314×101，m=1

故3.14有3位有效數(shù)字。

如3.1416=0.31416×101，m=1

故3.1416有5位有效數(shù)字。

又如=10.723805…，近似值10.721875=0.10721875×102,m=2

故10.721875有4位有效數(shù)字。

由此可以得出規(guī)律：若末位數(shù)字是四舍五入得到的，則從這位數(shù)起到前面第一個(gè)不為零數(shù)字為止的數(shù)字均為有效數(shù)字。1.2.4相對(duì)誤差限與有效數(shù)字的聯(lián)系

絕對(duì)誤差|x*-x|還不足以刻畫(huà)x的精度。例如測(cè)量1000m和1m兩個(gè)長(zhǎng)度，若它們的絕對(duì)誤差都是1cm，顯然前者的測(cè)量比較準(zhǔn)確?？梢?jiàn)刻畫(huà)近似值精度除了考慮絕對(duì)誤差的大小外，還需要考慮該量本身的大小，為此引入相對(duì)誤差的概念。設(shè)精確值x*的近似值為x，以表示相對(duì)誤差，一般用來(lái)近似計(jì)算相對(duì)誤差。

若，則稱εr為近似值x的相對(duì)誤差限。

下面闡明相對(duì)誤差與有效數(shù)字的聯(lián)系。

定理1.1

設(shè)近似值x=±10m(a1×10-1+a2×10-2+…+an×10-n),有n位有效數(shù)字，則其相對(duì)誤差限為。

證因?yàn)榻浦祒有n位有效數(shù)字，則有

而|x|≥a1×10m-1，故

定理1.2

設(shè)近似值x=±10m(a1×10-1+a2×10-2+…+an×10-n)的相對(duì)誤差限為，則它至少有n位有效數(shù)字。

證因?yàn)閨x|≤(a1+1)×10m-1，所以

因此，近似值x有n位有效數(shù)字。1.2.5數(shù)值計(jì)算中應(yīng)注意的幾個(gè)原則

1.避免兩個(gè)相近數(shù)的相減

設(shè)x*與y*相接近，x和y是x*和y*的近似值，x-y的相對(duì)誤差為

當(dāng)x和y很接近時(shí)，和都很大，此時(shí)x-y的相對(duì)誤差可能比x和y的相對(duì)誤差大得多。

實(shí)際處理時(shí)要盡量避免兩個(gè)相近數(shù)相減，可作適當(dāng)變換。如：

(x很大時(shí))(x和y很接近時(shí))

如：，如用4位有效數(shù)字計(jì)算,

，結(jié)果只有1位有效數(shù)字；如改為

，則有4位有效數(shù)字，新

算法避免了兩個(gè)相近數(shù)的相減。

2.避免絕對(duì)值小的數(shù)作除數(shù)

比如

分母變?yōu)?.0011時(shí)，有

商產(chǎn)生了巨大變化。

3.防止大數(shù)吃掉小數(shù)

比如

(要先對(duì)階)這就是大數(shù)吃掉了小數(shù)。最好先計(jì)算小的數(shù)，然后再加上大的數(shù)。

4.簡(jiǎn)化計(jì)算步驟

如果能減少運(yùn)算次數(shù)，不但可以節(jié)省計(jì)算時(shí)間，而且還能減少舍入誤差。比如計(jì)算多項(xiàng)式的值，用秦九韶方法。

例如計(jì)算x22的值，若將x的值逐個(gè)相乘，那么需作21次乘法，但若令

u=x·x，v=u·u，w=v·v，h=w·w

那么x22=u·v·h，只要作6次乘法就可以了。

5.用數(shù)值穩(wěn)定的算法

一個(gè)程序往往要進(jìn)行大量的四則運(yùn)算才能得出結(jié)果，每一步的運(yùn)算均會(huì)產(chǎn)生舍入誤差。

在運(yùn)算過(guò)程中，舍入誤差能控制在某個(gè)范圍內(nèi)的算法(舍入誤差不增長(zhǎng))稱之為數(shù)值穩(wěn)定的算法，否則就稱之為不穩(wěn)定的算法。只有穩(wěn)定的數(shù)值方法才可能給出可靠的計(jì)算結(jié)果，不穩(wěn)定的數(shù)值方法毫無(wú)實(shí)用價(jià)值。

例1.6

求

(n=1,2,…,8)的值。

解由于

初值

于是可建立遞推公式

(1.3)(n=1,2,…8)若取I0=ln1.2≈0.182,按式(1.3)就可以逐步算得

因?yàn)樵冢?,1］上的被積函數(shù)(當(dāng)且僅當(dāng)x=0時(shí)為零)，且當(dāng)m>n時(shí)，

(當(dāng)且僅當(dāng)x=0時(shí)，等號(hào)成立)

所以In(n=1,2,…,8)是恒正的，并有I0>I1>I2>…>I8>0。

在上述計(jì)算結(jié)果中，I4的近似值是負(fù)的，這個(gè)結(jié)果顯然是錯(cuò)的。為什么會(huì)這樣呢？這就是誤差傳播所引起的危害。由遞推公式(1.3)可看出，In-1的誤差擴(kuò)大了5倍后傳給In，因而初值I0的誤差對(duì)以后各步計(jì)算結(jié)果的影響會(huì)隨著n的增大愈來(lái)愈嚴(yán)重,這就造成I4的計(jì)算結(jié)果嚴(yán)重失真。如果改變計(jì)算公式，先取一個(gè)In的近似值，用公式(1.4)倒過(guò)來(lái)計(jì)算In-1，In-2

…即

(1.4)

情況就不同了。我們發(fā)現(xiàn)Ik的誤差減小到1/5后傳給Ik-1，因而初值的誤差對(duì)以后各步的計(jì)算結(jié)果的影響是隨著n的增大而愈來(lái)愈小。由于誤差是逐步衰減的，初值In可以這樣確定，不妨設(shè)I9≈I10，于是由

可求得I9≈0.017，按公式(1.4)可逐次求得

I8≈0.019

I7=0.021

I6=0.024

I5≈0.028

I4≈0.034

I3≈0.043

I2≈0.058

I1≈0.088

I0≈0.182顯然，這樣算出的I0與ln1.2的值比較符合。雖然初值I9很粗糙，但因?yàn)橛霉?1.4)計(jì)算時(shí)，誤差是逐步衰減的，所以計(jì)算結(jié)果相當(dāng)可靠。

比較以上兩個(gè)計(jì)算方案，顯然，前者是一個(gè)不穩(wěn)定的算法，后者是一個(gè)穩(wěn)定算法。對(duì)于一個(gè)穩(wěn)定的計(jì)算過(guò)程，由于舍入誤差不增大，因而不具體估計(jì)舍入誤差也是可用的。而對(duì)于

一個(gè)不穩(wěn)定的計(jì)算過(guò)程，如果計(jì)算步驟太多，就可能出現(xiàn)錯(cuò)誤結(jié)果。因此，在實(shí)際應(yīng)用中應(yīng)選用數(shù)值穩(wěn)定的算法，盡量避免使用數(shù)值不穩(wěn)定的算法。1.2.6算法的評(píng)價(jià)標(biāo)準(zhǔn)

我們知道，計(jì)算機(jī)的特點(diǎn)是運(yùn)算速度快，存儲(chǔ)的信息量大，并能自動(dòng)完成極其復(fù)雜的計(jì)算過(guò)程。計(jì)算機(jī)功能雖然很強(qiáng)，但是否可降低對(duì)算法的要求呢？許多事實(shí)證明，如果算法選擇不當(dāng)，計(jì)算機(jī)的利用率就得不到充分發(fā)揮，有時(shí)甚至不能得到滿意的解答。一個(gè)好的算法，

要求有以下幾個(gè)優(yōu)點(diǎn)：

(1)計(jì)算量小或計(jì)算時(shí)間少。

(2)算出的數(shù)值解精度高。

(3)占用計(jì)算存儲(chǔ)單元和工作單元少。

(4)算法的邏輯結(jié)構(gòu)簡(jiǎn)單。一、填空題

(1)數(shù)值計(jì)算中，誤差主要來(lái)源于

誤差、

誤差、誤差和

誤差。

(2)為減少舍入誤差，應(yīng)將改寫(xiě)為

。

(3)若誤差限為0.000005，那么近似數(shù)0.003400有

位有效數(shù)字。

(4)分別用2.718281，2.718282作數(shù)e的近似值，