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

第1章緒論1.1引言1.2計(jì)算機(jī)中數(shù)的表示1.3數(shù)值計(jì)算的誤差1.4函數(shù)求值的誤差1.5數(shù)值計(jì)算中要注意的若干原則數(shù)學(xué)是研究數(shù)量、結(jié)構(gòu)、變化以及空間模型等概念的一門學(xué)科。隨著社會(huì)的發(fā)展和科學(xué)的進(jìn)步，數(shù)學(xué)開(kāi)始被應(yīng)用于力學(xué)領(lǐng)域，后來(lái)被應(yīng)用于越來(lái)越廣的范圍，覆蓋了物理、工程、化學(xué)、天文、地理、生物、醫(yī)學(xué)，甚至經(jīng)濟(jì)、

語(yǔ)言等領(lǐng)域，這促進(jìn)了包括可應(yīng)用的數(shù)學(xué)及數(shù)學(xué)的應(yīng)用兩個(gè)部分的應(yīng)用數(shù)學(xué)的產(chǎn)生和迅速發(fā)展，使其成為數(shù)學(xué)的一個(gè)分支。應(yīng)用數(shù)學(xué)研究如何將數(shù)學(xué)知識(shí)應(yīng)用到其他的范疇，它包含許多分支，其中數(shù)值計(jì)算方法是其重要的分支之一。1.1引言數(shù)學(xué)是研究數(shù)量、結(jié)構(gòu)、變化以及空間模型等概念的一門學(xué)科。隨著社會(huì)的發(fā)展和科學(xué)的進(jìn)步，數(shù)學(xué)開(kāi)始被應(yīng)用于力學(xué)領(lǐng)域，后來(lái)被應(yīng)用于越來(lái)越廣的范圍，覆蓋了物理、工程、化學(xué)、天文、地理、生物、醫(yī)學(xué)，甚至經(jīng)濟(jì)、語(yǔ)言等領(lǐng)域，這促進(jìn)了包括可應(yīng)用的數(shù)學(xué)及數(shù)學(xué)的應(yīng)用兩個(gè)部分的應(yīng)用數(shù)學(xué)的產(chǎn)生和迅速發(fā)展，使其成為數(shù)學(xué)的一個(gè)分支。應(yīng)用數(shù)學(xué)研究如何將數(shù)學(xué)知識(shí)應(yīng)用到其他的范疇，它包含許多分支，其中數(shù)值計(jì)算方法是其重要的分支之一。計(jì)算機(jī)解決實(shí)際問(wèn)題的過(guò)程包括實(shí)際問(wèn)題、數(shù)學(xué)模型、計(jì)算方法、方法的程序設(shè)計(jì)、計(jì)算機(jī)求解等步驟。其中實(shí)際問(wèn)題包括各個(gè)領(lǐng)域的許多問(wèn)題，而這些實(shí)際問(wèn)題的計(jì)算機(jī)求解，目前雖有一些計(jì)算軟件可以直接使用，如Matlab、Mathematica等，但需要了解算法設(shè)計(jì)的原理，以便更好地應(yīng)用；同時(shí)，隨著實(shí)際問(wèn)題越來(lái)越復(fù)雜，規(guī)模越來(lái)越龐大，現(xiàn)成的數(shù)值方法軟件難以滿足實(shí)際需要，如天氣預(yù)報(bào)、計(jì)算化學(xué)、Web搜索、結(jié)構(gòu)設(shè)計(jì)等，這也要求學(xué)習(xí)計(jì)算方法，以便尋求新的解決問(wèn)題的方法。

本書(shū)從工程實(shí)際問(wèn)題出發(fā)，研究以下數(shù)學(xué)問(wèn)題:非線性方程的求解、線性方程組的求解、函數(shù)的插值與逼近、數(shù)值積分與微分、微分方程的數(shù)值求解、矩陣的特征值與特征向量的計(jì)算。 1.2計(jì)算機(jī)中數(shù)的表示

在數(shù)值計(jì)算中無(wú)處不涉及小數(shù)的運(yùn)算，了解小數(shù)在計(jì)算機(jī)中的表示和運(yùn)算是學(xué)習(xí)數(shù)值計(jì)算方法的基礎(chǔ)。計(jì)算機(jī)中的數(shù)都是以二進(jìn)制的形式來(lái)表示的。對(duì)于正整數(shù)，二進(jìn)制形式為而對(duì)于小于1的正數(shù)，其形式為其中，di表示二進(jìn)制數(shù)字，取值為0或1。1.2.1定點(diǎn)表示

定點(diǎn)表示就是小數(shù)點(diǎn)的位置在數(shù)中固定不變。計(jì)算機(jī)中有兩種定點(diǎn)數(shù)最常用:一種是定點(diǎn)純小數(shù)，另一種是定點(diǎn)純整數(shù)。

定點(diǎn)純小數(shù)是把小數(shù)點(diǎn)固定在數(shù)的符號(hào)位之后、最高數(shù)值位之前，小數(shù)點(diǎn)位置隱含，本身不占位，其格式如圖1.1所示。圖1.1定點(diǎn)純小數(shù)的格式

定點(diǎn)純整數(shù)是把小數(shù)點(diǎn)固定在數(shù)值的最低位之后，最高位為符號(hào)位，小數(shù)點(diǎn)位置隱含，本身不占位，其格式如圖1.2所示。圖1.2定點(diǎn)純整數(shù)的格式

例1－1

如圖1.3所示的兩個(gè)8位二進(jìn)制數(shù),求對(duì)應(yīng)的十進(jìn)制數(shù)。

解圖1.3(a)所示為定點(diǎn)純整數(shù)表示方法，故可得N1=+84，N2=-84。

圖1.3(b)所示為定點(diǎn)純小數(shù)表示方法,故可得N1=+0.65625，N2=-0.65625。圖1.3例1－1用圖1.2.2浮點(diǎn)表示

相比定點(diǎn)表示，浮點(diǎn)表示在位數(shù)有限的前提下可以擴(kuò)大數(shù)的表示范圍，同時(shí)又可保持?jǐn)?shù)的有效精度。

浮點(diǎn)數(shù)在機(jī)器中的一般表示形式如圖1.4所示。圖1.4浮點(diǎn)數(shù)的表示形式其中P表示階碼，而階符表示階碼的符號(hào)；S表示尾數(shù)，尾符表示尾數(shù)的符號(hào)。也就是說(shuō)，計(jì)算機(jī)中一個(gè)浮點(diǎn)數(shù)由階碼和尾數(shù)組成，而階碼和尾數(shù)都有自己的符號(hào)。

通常，用一位二進(jìn)制數(shù)Pf表示階碼的符號(hào)位。當(dāng)Pf=0時(shí)，表示階碼為正；當(dāng)Pf=1時(shí)，表示階碼為負(fù)。

同樣，用一位二進(jìn)制數(shù)Sf表示尾數(shù)的符號(hào)位。當(dāng)Sf=0時(shí)，表示尾數(shù)為正；當(dāng)Sf=1時(shí)，表示尾數(shù)為負(fù)。

例1－2用浮點(diǎn)數(shù)表示-18.75，并假定尾數(shù)用8位二進(jìn)制表示，階碼用4位二進(jìn)制表示，均含符號(hào)位。

解因?yàn)?-18.75)10=(-10010.11)2=(-0.1001011)×2+101

則-18.75的浮點(diǎn)數(shù)表示如圖1.5所示。圖1.5例1－2用圖 1.3數(shù)值計(jì)算的誤差

1.3.1誤差的來(lái)源

基于計(jì)算方法應(yīng)用計(jì)算機(jī)求解實(shí)際問(wèn)題的過(guò)程，不可避免會(huì)引入誤差，根據(jù)誤差的來(lái)源不同，誤差通常分為以下四種類型：

(1)模型誤差。 用數(shù)學(xué)方法解決一個(gè)具體的實(shí)際問(wèn)題，首先要建立數(shù)學(xué)模型，這就要對(duì)實(shí)際問(wèn)題進(jìn)行抽象、簡(jiǎn)化或假設(shè)，因此建立的數(shù)學(xué)模型與實(shí)際客觀問(wèn)題之間就存在著一定的差距，即誤差，這種誤差稱做模型誤差。

(2)觀測(cè)誤差。 在數(shù)學(xué)模型中通常包含一些需要通過(guò)觀測(cè)得到的物理量，如溫度、長(zhǎng)度、電壓等，這些量的觀測(cè)值與其實(shí)際值之間的誤差，稱做觀測(cè)誤差。

(3)截?cái)嗾`差。當(dāng)數(shù)學(xué)模型不能得到精確解時(shí)，通常用數(shù)值方法求它的近似解，則所求得的近似解與準(zhǔn)確解之間的誤差稱為截?cái)嗾`差，也稱為方法誤差。例如，計(jì)算sinx的值時(shí)，應(yīng)用其泰勒展開(kāi)式有如果取該式的前兩項(xiàng)計(jì)算sinx的值，即則為計(jì)算sinx的截?cái)嗾`差。

(4)舍入誤差。由于計(jì)算機(jī)的字長(zhǎng)有限，參加運(yùn)算的數(shù)據(jù)在計(jì)算機(jī)中只能表示為數(shù)據(jù)真實(shí)值的近似值，由此產(chǎn)生了誤差，而且用計(jì)算機(jī)進(jìn)行實(shí)際計(jì)算時(shí)每一步都可能產(chǎn)生該類誤差，這種誤差稱為舍入誤差。

例如，設(shè)計(jì)算機(jī)的字長(zhǎng)為最多能夠處理10位十進(jìn)制數(shù)，則1÷3=0.3333333333，而其真實(shí)值應(yīng)為1÷3=0.33333333333…，由此產(chǎn)生的誤差就是舍入誤差。1.3.2絕對(duì)誤差

定義1.1設(shè)x為準(zhǔn)確值，x*為x的一個(gè)近似值，稱x－x*為近似值x*的絕對(duì)誤差，簡(jiǎn)稱誤差，記做e*，即

(1.1)通常無(wú)法知道準(zhǔn)確值x，也就不能算出誤差的準(zhǔn)確值e*，只能根據(jù)測(cè)量或計(jì)算估計(jì)出誤差的絕對(duì)值不超過(guò)某個(gè)正數(shù)ε，即(1.2)ε稱為絕對(duì)誤差限或精度。顯然，誤差限不是唯一的，但是誤差限越小，表示近似值的精度越高。近似值的誤差可正可負(fù)，實(shí)際應(yīng)用中常用誤差限來(lái)表示誤差。有了誤差限就可知道x的范圍，因此工程上通常用(1.3)

來(lái)表示近似值的精度或準(zhǔn)確值的范圍。例如，用毫米測(cè)度尺測(cè)量一長(zhǎng)度x，若誤差限為0.5mm,讀出的長(zhǎng)度為23mm，則有|23－x|≤0.5mm；又如，測(cè)得某物體長(zhǎng)度為5m，若誤差限為0.01m，則可記準(zhǔn)確長(zhǎng)度x=(5±0.01)m，即該物體的準(zhǔn)確長(zhǎng)度在4.99m~5.01m范圍內(nèi)。絕對(duì)誤差是有量綱的，這從上述的兩個(gè)例子也可以看出。另外，僅有絕對(duì)誤差通常不能完全刻畫(huà)近似值的精確程度。例如，x=(15±2)cm，y=(1000±5)cm，則e(x*)=2cm，e(y*)=5cm，從表面上看y*的絕對(duì)誤差大于x*的絕對(duì)誤差，得出x*更精確的結(jié)論；實(shí)際上，x*為15cm產(chǎn)生了2cm的誤差，即每1cm產(chǎn)生的誤差約為0.1333cm，而y*為1000cm產(chǎn)生了5cm的誤差，即每1cm產(chǎn)生的誤差為0.005cm，所以y*比x*更精確，其實(shí)這就是相對(duì)誤差。1.3.3相對(duì)誤差

定義1.2設(shè)x為準(zhǔn)確值，x*為x的一個(gè)近似值，稱(x－x*)/x為近似值x*的相對(duì)誤差，記做e*r，即(1.4)根據(jù)絕對(duì)誤差的定義，即式(1.1)，將其代入式(1.4)有即相對(duì)誤差可由絕對(duì)誤差與準(zhǔn)確值計(jì)算得到，但實(shí)際中準(zhǔn)確值難以得到，因此通常根據(jù)下式來(lái)計(jì)算相對(duì)誤差：(1.5)同絕對(duì)誤差一樣，相對(duì)誤差也可正可負(fù)，因此實(shí)際中也取某個(gè)正數(shù)εr作為誤差限來(lái)表示相對(duì)誤差，即|er*|≤εr，則根據(jù)式(1.2)可得(1.6)

例1－3已知某商品的質(zhì)量為(35±0.2)kg，計(jì)算該商品的相對(duì)誤差限εr。

解根據(jù)已知可得該商品質(zhì)量的絕對(duì)誤差限ε=0.2，則根據(jù)式(1.6)有

例1－4已知e=2.71828182…，取其近似值e*=2.71828，求e*的絕對(duì)誤差限ε和相對(duì)誤差限εr。

解

e*的絕對(duì)誤差為所以絕對(duì)誤差限為則相對(duì)誤差為1.3.4有效數(shù)字與誤差

定義1.3若x*作為x的近似值，其絕對(duì)誤差的絕對(duì)值不超過(guò)某一位的半個(gè)單位，而從該位開(kāi)始到x*的第一位非零數(shù)字共有n位，則稱用x*近似x時(shí)，具有n位有效數(shù)字，簡(jiǎn)稱x*有n位有效數(shù)字。

一般來(lái)說(shuō)，如果x的近似值x*可以表示成如下形式：(1.7)其中ai∈{0，1，2，…，9}，且a1≠0。若(1.8)則稱近似數(shù)x*具有n位有效數(shù)字，或稱x*精確到第n位；反之，若x*具有n位有效數(shù)字，則其絕對(duì)誤差必定滿足：這也稱為有效數(shù)字的等價(jià)定義。

例1－5已知π=3.14159265…，設(shè)π的3個(gè)近似值分別為π1=3.14，π2=3.1415，π3=3.1415927，求π1、π2、π3有效數(shù)字的個(gè)數(shù)。

解方法一：根據(jù)有效數(shù)字的定義，需計(jì)算π1、π2、和π3的絕對(duì)誤差限，即

所以π1有3位有效數(shù)字，π2有4位有效數(shù)字，π3有8位有效數(shù)字。

方法二：利用有效數(shù)字的等價(jià)定義計(jì)算，則有

1=3.14=0.314×101，而，即k-n=-2，而k=1，所以n=3，即

1有3位有效數(shù)字。同理可得

2=3.1415有4位有效數(shù)字，

3有8位有效數(shù)字。例1－6已知x=4.854±0.03，則其近似值4.854具有幾位有效數(shù)字?

解因?yàn)?.854的誤差限ε=0.03,則ε<0.05=0.5×10－1，根據(jù)有效數(shù)字的等價(jià)定義，k-n=-1，而k=1,所以n=2，即4.854具有2位有效數(shù)字。

定理1.1如果x的近似值x*可以表示成如下形式：

(2)若x*的相對(duì)誤差滿足所以x*有n位有效數(shù)字。

例1－7要使得的相對(duì)誤差不超過(guò)0.1%，應(yīng)至少取幾位有效數(shù)字？

解設(shè)的近似值x*有n位有效數(shù)字，則由定理1.1得x*的相對(duì)誤差滿足而x*的首位數(shù)字a1為4,所以有由此可以得到n≥3.097，即應(yīng)至少取4位有效數(shù)字。

1.4函數(shù)求值的誤差

1.一元函數(shù)的情況

計(jì)算函數(shù)y=f(x)的值，若得到的是x的近似值x*，由此計(jì)算得到的函數(shù)值也是近似值y*=f(x*)，現(xiàn)在研究y*的絕對(duì)誤差與相對(duì)誤差。

將f(x)在x*處作泰勒展開(kāi)，并取一階泰勒多項(xiàng)式，則有所以y*的絕對(duì)誤差e(y*)=y－y*=f(x)－f(x*)≈f′(x*)(x－x*)，即根據(jù)相對(duì)誤差的定義可以得到y(tǒng)*的相對(duì)誤差為：

（1.9）（1.10）y*的絕對(duì)誤差為根據(jù)相對(duì)誤差的概念可以得到y(tǒng)*的相對(duì)誤差為：(1.12)(1.11)

3.和、差、積、商誤差的計(jì)算

利用函數(shù)求值的誤差計(jì)算公式可以得到兩個(gè)數(shù)的和、差、積、商的誤差估計(jì)，設(shè)兩個(gè)近似數(shù)x*1、x*2，其誤差分別為e(x*1)和e(x*2)，對(duì)它們進(jìn)行加、減、乘、除運(yùn)算得到的誤差分別為(1.13)(1.14)（1.15）（1.16）

例1－8測(cè)得某桌面的長(zhǎng)a的近似值a*=120cm，寬b的近似值b*=60cm。若已知|e(a*)|≤0.2cm，|e(b*)|≤0.1cm，試求面積近似值s*=a*b*的絕對(duì)誤差與相對(duì)誤差。

解根據(jù)乘法運(yùn)算的誤差計(jì)算公式得則相對(duì)誤差為1.5數(shù)值計(jì)算中要注意的若干原則

解決一個(gè)問(wèn)題的計(jì)算方法往往有多種，不同的計(jì)算方法計(jì)算結(jié)果的精確度往往不同，計(jì)算量小而精度高的算法最好，因此對(duì)數(shù)值計(jì)算中計(jì)算結(jié)果的精度，即誤差,進(jìn)行分析十分重要。然而現(xiàn)實(shí)中的工程或科學(xué)問(wèn)題經(jīng)常是非常復(fù)雜的，針對(duì)其計(jì)算的每一步都進(jìn)行誤差分析難以做到,也不必要，因此通過(guò)對(duì)誤差傳播的分析并結(jié)合計(jì)算過(guò)程中的實(shí)踐經(jīng)驗(yàn)，得出了數(shù)值計(jì)算中應(yīng)注意的若干原則。

(1)盡量避免兩個(gè)相近的數(shù)相減。數(shù)值計(jì)算中，兩個(gè)相近的數(shù)相減會(huì)嚴(yán)重?fù)p失有效數(shù)字，也會(huì)造成計(jì)算結(jié)果相對(duì)誤差變得很大。如x=532.65和y=532.32都具有5位有效數(shù)字，但x-y=0.33只有兩位有效數(shù)字。要避免這種現(xiàn)象的發(fā)生所采取的措施就是改變計(jì)算方法。例1－9當(dāng)x很大時(shí),和1/x－1/(x+1)的運(yùn)算就是兩個(gè)相近的數(shù)相減，避免該現(xiàn)象的方法是改變其計(jì)算方法，具體如下(即用右端代替左端進(jìn)行計(jì)算)：

例1-10當(dāng)x1與x2很接近時(shí)，的運(yùn)算成為兩個(gè)相近的數(shù)相減，避免該現(xiàn)象的方法仍是改變其計(jì)算的方法：

例1－11當(dāng)x接近于0時(shí)，1/sinx－cosx/sinx變成兩個(gè)相近的數(shù)相減，避免該現(xiàn)象的方法同樣是改變其計(jì)算方法,即

一般情況下，當(dāng)x*位于x附近時(shí)，可以用泰勒展開(kāi)公式代替兩個(gè)相近函數(shù)值的相減計(jì)算：

（1.17）

(2)避免大數(shù)“吃”小數(shù)現(xiàn)象。若參加運(yùn)算的數(shù)量級(jí)相差很大而計(jì)算機(jī)的位數(shù)有限，如不注意運(yùn)算次序，可能出現(xiàn)大數(shù)“吃”小數(shù)現(xiàn)象，影響計(jì)算的結(jié)果。如當(dāng)|a|>>|b|時(shí)，應(yīng)盡量避免進(jìn)行a+b的運(yùn)算。例如假設(shè)計(jì)算機(jī)只能存放10位尾數(shù)的十進(jìn)制數(shù)，則就出現(xiàn)了大數(shù)“吃”小數(shù)現(xiàn)象。要避免該現(xiàn)象發(fā)生的方法是改變計(jì)算方法，盡量使數(shù)量級(jí)相近的數(shù)進(jìn)行相加或相減運(yùn)算。

例1－12在8位十進(jìn)制計(jì)算機(jī)上，求二次方程x2－(109+1)x+109=0的根。

解利用因式分解容易求出該方程的兩個(gè)根為x1=109，x2=1。若在計(jì)算機(jī)上用求根公式求解，則有在8位十進(jìn)制計(jì)算機(jī)上，有進(jìn)而有由此得到方程的根x1=109，x2=0。顯然x2的結(jié)果是錯(cuò)誤的，這是大數(shù)“吃”小數(shù)現(xiàn)象造成的。為了避免該現(xiàn)象發(fā)生，改變x2的計(jì)算公式,即將則可以得到此結(jié)果正確。

例1－13在5位十進(jìn)制計(jì)算機(jī)上，計(jì)算，其中σi=0.9。

解因?yàn)楹苊黠@,其計(jì)算結(jié)果是錯(cuò)誤的，這也是大數(shù)“吃”掉了小數(shù)。避免該現(xiàn)象發(fā)生的方法是先計(jì)算小的數(shù)，然后再加上大的數(shù)，即

(3)避免使用絕對(duì)值較小的數(shù)做除數(shù)。根據(jù)除法運(yùn)算的誤差估計(jì)公式，較小的數(shù)做除數(shù)時(shí)會(huì)使計(jì)算結(jié)果的誤差變得很大，因此應(yīng)避免這種現(xiàn)象的發(fā)生。

例1－14計(jì)算的值。

解計(jì)算y時(shí),出現(xiàn)了絕對(duì)值較小的數(shù)做除數(shù)現(xiàn)象，應(yīng)改變其計(jì)算方法,即

(4)注意簡(jiǎn)化計(jì)算步驟，減少運(yùn)算次數(shù)。如果能夠減少運(yùn)算次數(shù)，既能節(jié)省計(jì)算機(jī)的運(yùn)行時(shí)間，又能減少舍入誤差，這也是數(shù)值計(jì)算應(yīng)注意的原則。

例1－15計(jì)算x31的值。

解若將x逐個(gè)相乘，那么要做30次乘法。注意到x31=xx2x4x8x16

則令x2＝xx，x4＝x2x2，x8=x4x4，x16=x8x8

則有x31=xx2x4x8x1630次乘法運(yùn)算減少到8次乘法運(yùn)算。

例1－16計(jì)算多項(xiàng)式f(x)=anxn+an－1xn－1+…+a1x+a0

的值。

解如果根據(jù)通常的計(jì)算方法，即逐項(xiàng)先進(jìn)行乘法然后相加，共需要進(jìn)行n+(n－1)+…+2+1=n(n+1)/2次乘法和n次加法。

如果采用秦九韶算法,則僅需要n次乘法和n次加法。關(guān)于秦九韶算法有興趣的讀者可參閱相關(guān)資料。

(5)選擇數(shù)值穩(wěn)定性好的算法。數(shù)值計(jì)算的過(guò)程中舍入誤差對(duì)計(jì)算結(jié)果影響不大的算法稱為數(shù)值穩(wěn)定的算法，影響嚴(yán)重的算法稱為數(shù)值不穩(wěn)定的算法。如果第n+1步的誤差en+1與第n步的誤差en滿足，則稱該算法是絕對(duì)穩(wěn)定的，否則稱不是絕對(duì)穩(wěn)定的。顯然，數(shù)值計(jì)算中應(yīng)該選擇數(shù)值穩(wěn)