1計(jì)算方法1計(jì)算方法1.1計(jì)算方法研究的對(duì)象和特點(diǎn)

計(jì)算方法實(shí)際上就是計(jì)算機(jī)上使用的數(shù)值計(jì)算方法，所以這門課程又稱為數(shù)值計(jì)算方法或數(shù)值分析。它是專門研究求解各種數(shù)學(xué)問題的數(shù)值計(jì)算方法。現(xiàn)在，由于大多數(shù)科學(xué)計(jì)算都比較復(fù)雜，人工計(jì)算無(wú)法完成；而計(jì)算機(jī)科學(xué)的迅速發(fā)展和廣泛應(yīng)用提供了解決這些復(fù)雜問題的新途徑。用計(jì)算機(jī)解決科學(xué)計(jì)算問題的一般過程，可以概括為：

實(shí)際問題→數(shù)學(xué)模型→計(jì)算方法→程序設(shè)計(jì)→上機(jī)計(jì)算→結(jié)果分析精選課件1.1計(jì)算方法研究的對(duì)象和特點(diǎn)精選課件2

由實(shí)際問題應(yīng)用有關(guān)科學(xué)知識(shí)和數(shù)學(xué)理論建立數(shù)學(xué)模型這一過程，通常作為應(yīng)用數(shù)學(xué)的任務(wù)。而根據(jù)數(shù)學(xué)模型提出求解的計(jì)算方法直到編出程序上機(jī)算出結(jié)果，進(jìn)而對(duì)計(jì)算結(jié)果進(jìn)行分析，這一過程則是計(jì)算數(shù)學(xué)的任務(wù)，也是數(shù)值計(jì)算方法的研究對(duì)象。因此，數(shù)值計(jì)算方法就是研究用計(jì)算機(jī)解決數(shù)學(xué)問題的數(shù)值方法及其理論的科學(xué)。它的內(nèi)容包括：誤差理論、線性與非線性方程(組)的數(shù)值解、矩陣的特征值與特征向量計(jì)算、曲線擬合與函數(shù)逼近、插值方法、數(shù)值積分與數(shù)值微分、常微分方程與偏微分方程數(shù)值解等。2022/12/30精選課件3由實(shí)際問題應(yīng)用有關(guān)科學(xué)知識(shí)和數(shù)學(xué)理論建2022/12/30精選課件41.把實(shí)際問題歸結(jié)為數(shù)值問題⒉制定數(shù)值問題的算法⒊得不到準(zhǔn)確解時(shí)，設(shè)法得到近似解⒋解的特性（近似程度，斂散性）⒌各種方法的優(yōu)缺點(diǎn)（速度，存儲(chǔ)量）⒍各種方法的實(shí)用范圍（收斂范圍）⑴計(jì)算方法要解決的幾個(gè)問題：（或研究的對(duì)象）2022/12/29精選課件41.把實(shí)際問題歸結(jié)為數(shù)值問題⑴2022/12/30精選課件5⒈把實(shí)際問題歸結(jié)為數(shù)值問題

由于電子數(shù)字計(jì)算機(jī)的廣泛使用，使越來(lái)越多的實(shí)際問題能歸結(jié)為數(shù)值問題而得到解決（如：曲線擬合，數(shù)值逼近等）。

【什么是數(shù)值問題呢？所謂數(shù)值問題，指的是由一組已知數(shù)據(jù)（又稱輸入數(shù)據(jù)）求出一組結(jié)果數(shù)據(jù)（又稱輸出數(shù)據(jù)），使得這兩組數(shù)據(jù)之間滿足預(yù)先指定的某種關(guān)系（函數(shù)關(guān)系）的問題。（即由一組數(shù)求得另一組數(shù)）】⒉制定數(shù)值問題的算法

【什么叫算法？用完全確定的運(yùn)算規(guī)則（包括運(yùn)算的邏輯順序），對(duì)某一類數(shù)值問題的輸入數(shù)據(jù)進(jìn)行處理，判斷此數(shù)值問題是否有解，在解存在的情況下，給出輸出數(shù)據(jù)，此種過程稱為算法?！?022/12/29精選課件5⒈把實(shí)際問題歸結(jié)為數(shù)值問題⒊得不到準(zhǔn)確解時(shí)，設(shè)法得到近似解

例：求已知數(shù)。由數(shù)學(xué)中的極限理論可知，（極限存在）

于是又∵n只能有限，∴x是近似值。62022/12/30精選課件⒊得不到準(zhǔn)確解時(shí)，設(shè)法得到近似解62022/12/29精選課在計(jì)算方法中，我們還將討論：⒋解的特性（近似程度，斂散性）⒌各種方法的優(yōu)缺點(diǎn)（速度，存儲(chǔ)量）⒍各種方法的實(shí)用范圍（收斂范圍）2022/12/30精選課件7在計(jì)算方法中，我們還將討論：2022/12/29精選課件7⑵一個(gè)好的方法應(yīng)具有如下特點(diǎn)：

第一，面向計(jì)算機(jī)，要根據(jù)計(jì)算機(jī)特點(diǎn)提供實(shí)際可行的有效算法，即算法只能包括加、減、乘、除運(yùn)算和邏輯運(yùn)算，是計(jì)算機(jī)能直接處理的。

第二，有可靠的理論分析，能任意逼近并達(dá)到精度要求，對(duì)近似算法要保證方法的收斂性和數(shù)值穩(wěn)定性，還要對(duì)誤差進(jìn)行分析，這些都建立在相應(yīng)數(shù)學(xué)理論基礎(chǔ)上。

第三，要有好的計(jì)算復(fù)雜性（即時(shí)間復(fù)雜性和空間復(fù)雜性）；時(shí)間復(fù)雜性好是指節(jié)省時(shí)間，空間復(fù)雜性好是指節(jié)省存儲(chǔ)量，這也是建立算法要研究的問題，它關(guān)系到算法能否在計(jì)算機(jī)上實(shí)現(xiàn)。

第四，要有數(shù)值實(shí)驗(yàn)，即任何一個(gè)算法除了從理論上要滿足上述三點(diǎn)外，還要通過數(shù)值試驗(yàn)證明是行之有效的。2022/12/30精選課件8⑵一個(gè)好的方法應(yīng)具有如下特點(diǎn)：2022/12/29

例：一個(gè)簡(jiǎn)單的算法問題，設(shè)要對(duì)給定的求多項(xiàng)式的值。92022/12/30精選課件

一種計(jì)算過程是直接計(jì)算的每一項(xiàng)后逐項(xiàng)求和，這樣要做次乘法和次加法。

例：一個(gè)簡(jiǎn)單的算法問題，設(shè)要對(duì)給定的求多102022/12/30精選課件

另一種算法就是先將變形為如下形式：再由內(nèi)層向外層計(jì)算，如設(shè)：

就可以得到一個(gè)遞推公式k=1,2,…,n(1.3)

這樣的計(jì)算過程只需要計(jì)算n次乘法和n次加法。這種算法和上一種算法相比，不僅邏輯結(jié)構(gòu)簡(jiǎn)單，而且計(jì)算也明顯地減少了。多項(xiàng)式求值的這種算法稱為秦九韶算法（計(jì)算框圖見圖1.2)。102022/12/29精選課件另一種算法就是1.2誤差的來(lái)源及其基本概念1.2.1誤差來(lái)源：用數(shù)值計(jì)算方法解決科學(xué)技術(shù)中的具體問題，一般說都有誤差，其來(lái)源有下列四種：（注：由于人為的粗心大意造成的計(jì)算錯(cuò)誤，不算誤差）

1.模型誤差數(shù)學(xué)描述和實(shí)際問題之間的誤差如：勻加速運(yùn)動(dòng)或自由落體運(yùn)動(dòng)公式略去了風(fēng)力，空氣阻力等。

2.觀察誤差如：讀表、讀尺、讀溫度計(jì)。2022/12/30精選課件111.2誤差的來(lái)源及其基本概念2022/12/29精選課件3.截?cái)嗾`差

如：對(duì)x>0，求。利用泰勒公式有取其部分和作為，就產(chǎn)生了截?cái)嗾`差。4.舍入誤差由于計(jì)算機(jī)的字長(zhǎng)有限，對(duì)超過位數(shù)的數(shù)字要進(jìn)行舍入，通常取與它們接近的數(shù)來(lái)表示，由此產(chǎn)生的誤差稱為舍入誤差。例如，我們通常使用2.71828和3.1416來(lái)表示的近似值，由此所產(chǎn)生的誤差就是舍入誤差。2022/12/30精選課件123.截?cái)嗾`差2022/12/29精選課件12

本課程僅討論后兩種誤差（截?cái)嗾`差和舍入誤差），討論它們?cè)谟?jì)算過程中的傳播和對(duì)計(jì)算結(jié)果的影響，研制能夠控制誤差的影響且保證最終結(jié)果有足夠精度的算法。2022/12/30精選課件13本課程僅討論后兩種誤差（截?cái)嗾`差和舍入誤差），1.2.2誤差的概念和有效數(shù)字1.絕對(duì)誤差定義1.1

設(shè)某數(shù)的精確值為，其近似值為，那么與之差稱為近似值的絕對(duì)誤差，簡(jiǎn)稱誤差。一般地，某數(shù)的精確值是不知道的，因而

不能求出，但往往可以估計(jì)出它的大小范圍，亦即可以確定一個(gè)正數(shù)，使得此時(shí)，稱為的絕對(duì)誤差限。有時(shí)也用表示近似值的精確值或精確值的所在范圍。2022/12/30精選課件141.2.2誤差的概念和有效數(shù)字1.絕對(duì)誤差2022/2.相對(duì)誤差

絕對(duì)誤差反映不了一個(gè)近似數(shù)的準(zhǔn)確程度。如：稱一頭大象誤差十公斤，稱一只螞蟻誤差一克，誰(shuí)的近似程度好，顯然大象的近似應(yīng)好些。于是引進(jìn)了相對(duì)誤差。記

稱為近似值x的相對(duì)誤差，由于精確值一般不知道，實(shí)際計(jì)算時(shí)通常取作為近似值x的相對(duì)誤差。若能求出一個(gè)正數(shù)，使得，則稱為近似值x的相對(duì)誤差限。它是無(wú)量綱的數(shù)，通常用百分比表示。2022/12/30精選課件152.相對(duì)誤差2022/12/29精選課件

例：甲用米尺測(cè)量10M長(zhǎng)的物體，所產(chǎn)生的絕對(duì)誤差為2cm，乙用同一米尺測(cè)量1M長(zhǎng)的物體，所產(chǎn)生的絕對(duì)誤差為1cm，他們誰(shuí)的測(cè)量精度好？解：根據(jù)上述定義可知，甲測(cè)量時(shí)的相對(duì)誤差

乙測(cè)量時(shí)的相對(duì)誤差可見甲測(cè)量結(jié)果比乙精確。162022/12/30精選課件例：甲用米尺測(cè)量10M長(zhǎng)的物體，所產(chǎn)生的絕對(duì)誤3.有效數(shù)字

當(dāng)準(zhǔn)確數(shù)的位數(shù)很多時(shí)，我們常按“四舍五入”原則減少位數(shù)，得其近似數(shù)。并用“有效數(shù)字”來(lái)描述它。定義1.2如果近似值的誤差限是某一位的半個(gè)單位，該位到的第一位非零數(shù)字共有位，則稱有位有效數(shù)字。如果的每一位都是有效數(shù)字，則稱為有效數(shù)。如：，有5位有效數(shù)字，有6位有效數(shù)字2022/12/30精選課件173.有效數(shù)字2022/12/29精選

任何一個(gè)實(shí)數(shù)，經(jīng)四舍五入后得到的近似值都可以表示為如下標(biāo)準(zhǔn)形式：（其中m可為正負(fù)數(shù)）2022/12/30精選課件18如果其絕對(duì)誤差限滿足則稱近似值具有n位有效數(shù)字。任何一個(gè)實(shí)數(shù)，經(jīng)四舍五入后得到的近似2022/12/30精選課件19例1

設(shè)=0.0270是某數(shù)經(jīng)“四舍五入”所得，則誤差不超過末位的半個(gè)單位，即：又,故該不等式又可寫為由有效數(shù)字定義可知,有3位有效數(shù)字，分別是2,7，0。2022/12/29精選課件19例12022/12/30精選課件20例2

又,故該不等式又可寫為故有3位有效數(shù)字，分別是3,2，8。由于中的數(shù)字9不是有效數(shù)字,故不是有效數(shù)。思考：有幾位有效數(shù)字？

2022/12/29精選課件20例2有效數(shù)位為3位有效數(shù)位為5位有效數(shù)位為4位精選課件有效數(shù)位為3位有效數(shù)位為5位有效數(shù)位為4位精選課件214.有效數(shù)字與絕對(duì)誤差、相對(duì)誤差有如下關(guān)系:

⑴若某數(shù)的近似值有n位有效數(shù)字，那么這個(gè)近似值的絕對(duì)誤差限為

（注：由（1.4）式可知：m為整數(shù)位，n為小數(shù)位）由此看出：當(dāng)m相同時(shí)，n越大，則m-n越小，從而有效位數(shù)越多，其絕對(duì)誤差限越小。數(shù)據(jù)也就越精確。

2022/12/30精選課件224.有效數(shù)字與絕對(duì)誤差、相對(duì)誤差有如下關(guān)系:2022/1⑵用式(1.4)表示的近似數(shù)，若具有n位有效數(shù)字，則其相對(duì)誤差限為

則至少具有n位有效數(shù)字。

2022/12/30精選課件23

反之，若的相對(duì)誤差限為⑵用式(1.4)表示的近似數(shù)，若具有n位證明由⑴知，若x具有n位有效數(shù)字，則從而（將上式代入）242022/12/30精選課件（參見1.4式）證明由⑴知，若x具有n位有效數(shù)字，則242022/12/

反之，若x的相對(duì)誤差限為

所以x至少有n位有效數(shù)字。

由(2)可以看出，有效位數(shù)越多，相對(duì)誤差限就越小，精確度也就越高。2022/12/30精選課件25反之，若x的相對(duì)誤差限為

1.2.3初值誤差的傳播近似數(shù)參加運(yùn)算后所得到的值也是近似值，含有誤差，將這一現(xiàn)象稱為誤差傳播。數(shù)值運(yùn)算中誤差的傳播情況比較復(fù)雜，主要表現(xiàn)在：算法本身可能有截?cái)嗾`差；初始數(shù)據(jù)在計(jì)算機(jī)內(nèi)的浮點(diǎn)表示一般有舍入誤差；每次運(yùn)算一般又會(huì)產(chǎn)生新的誤差，并且傳播以前已經(jīng)引入的誤差。因此，對(duì)誤差進(jìn)行準(zhǔn)確分析是困難的，但也是很重要的。它關(guān)系到一個(gè)方法是否穩(wěn)定,計(jì)算結(jié)果是否可靠。2022/12/30精選課件261.2.3初值誤差的傳播2022/12/29精選課件誤差的傳播與積累例3：蝴蝶效應(yīng)

——紐約的一只蝴蝶翅膀一拍，風(fēng)和日麗的北京就刮起臺(tái)風(fēng)來(lái)了？！NYBJ以上是一個(gè)病態(tài)問題精選課件誤差的傳播與積累例3：蝴蝶效應(yīng)——紐約的一只蝴蝶翅膀一拍27

1.3選用和設(shè)計(jì)算法應(yīng)注意的問題一般衡量算法的標(biāo)準(zhǔn)有：算法是否穩(wěn)定，算法的運(yùn)算次數(shù)和算法的存儲(chǔ)量是否盡量少，同時(shí)還要考慮誤差的傳播等。選用和設(shè)計(jì)算法應(yīng)注意如下幾個(gè)問題:

⒈

選用數(shù)值穩(wěn)定的計(jì)算公式

⒉防止兩個(gè)相近數(shù)相減

⒊防止大數(shù)“吃掉”小數(shù)

⒋簡(jiǎn)化計(jì)算步驟，減少運(yùn)算次數(shù)2022/12/30精選課件281.3選用和設(shè)計(jì)算法應(yīng)注意的問題2022/12/29精1.3.1選用數(shù)值穩(wěn)定的計(jì)算公式

如果數(shù)值算法的計(jì)算舍入誤差積累是可以控制的，則稱其為數(shù)值穩(wěn)定的；反之，稱為數(shù)值不穩(wěn)定的。例：計(jì)算定積分（序列）

利用分部積分法不難求得遞推關(guān)系式為

2022/12/30精選課件29公式推導(dǎo)1.3.1選用數(shù)值穩(wěn)定的計(jì)算公式2022/1由式（1.16）可依次算出如下結(jié)果：(p011.c)

2022/12/30精選課件30注意到（注：從積分中按x的最小和最大值提出ex)?(1.17)由上面的不等式可以看出由式（1.16）可依次算出如下結(jié)果：(p011.c)2

因此按遞推關(guān)系式（1.16）所算出的計(jì)算值是錯(cuò)誤的，嚴(yán)重偏離其準(zhǔn)確值。發(fā)生這種現(xiàn)象的原因是因?yàn)楸旧碛胁怀^的誤差。設(shè)是具有精確初始值，并按式（1.16)計(jì)算而得的，則有由此可見，初始值微小的誤差會(huì)隨著計(jì)算步數(shù)的增加而迅速擴(kuò)大，最終使計(jì)算結(jié)果失真。故算法式（1.16)不能控制誤差的傳播，是數(shù)值不穩(wěn)定的。2022/12/30精選課件31因此按遞推關(guān)系式（1.16如果將式（1.16）改寫為2022/12/30精選課件32（1.18)又注意到結(jié)合式（1.17）得由上面的估計(jì)式取開始按式（1.18）計(jì)算，有如下結(jié)果：（p012.c)如果將式（1.16）改寫為2022/12/29精選課件32（2022/12/30精選課件33由此可以看出按遞推關(guān)系式（1.18）算出的與結(jié)果相差無(wú)幾，已精確到小數(shù)點(diǎn)后第四位。分析誤差的傳播，則有這表明，隨著計(jì)算步驟的增加，初始誤差可以得到控制，于是可知算法（1.18）式是數(shù)值穩(wěn)定的。公式推導(dǎo)2022/12/29精選課件33由此可以看出按1.3.2防止兩個(gè)相近數(shù)相減在數(shù)值計(jì)算中若有兩個(gè)相近的數(shù)相減，則這兩個(gè)數(shù)的前幾位相同的有效數(shù)字會(huì)在它們之差中消失，從而使有效數(shù)字的位數(shù)減少。如果遇到兩個(gè)相近的數(shù)相減運(yùn)算，可考慮對(duì)公式進(jìn)行處理，避免減法。例如，當(dāng)很大時(shí)，下兩式應(yīng)作如下處理：342022/12/30精選課件1.3.2防止兩個(gè)相近數(shù)相減342022/12/29精選352022/12/30精選課件1.3.3絕對(duì)值太小的數(shù)不宜作除數(shù)算法語(yǔ)言中已講過，在機(jī)器上若用很小的數(shù)作除數(shù)會(huì)溢出停機(jī)，而且當(dāng)很小的數(shù)稍有一點(diǎn)誤差時(shí)，對(duì)計(jì)算結(jié)果影響很大。例如：352022/12/29精選課件1.3.3絕對(duì)值太小的數(shù)

1.3.4防止大數(shù)“吃掉”小數(shù)例：設(shè)a=63281312，b=0.1，c=0.9，求a,b,c之和。如果按（a+b)+c

次序來(lái)編制程序，此時(shí)按照加法浮點(diǎn)運(yùn)算的對(duì)階規(guī)則，應(yīng)有

2022/12/30精選課件36在八位的計(jì)算機(jī)上計(jì)算時(shí)，上式后面的兩個(gè)數(shù)在計(jì)算機(jī)上變?yōu)榱恕皺C(jī)器零”，被“吃掉”。其結(jié)果為63281312。如果改變計(jì)算次序?yàn)椋╞+c)+a，則有（0.1＋0.9）＋63281312＝1＋63281312＝63281313

。這樣就避免了小數(shù)被大數(shù)“吃掉”的現(xiàn)象。1.3.4防止大數(shù)“吃掉”小數(shù)2022/12/29精1.3.5簡(jiǎn)化計(jì)算步驟，減少運(yùn)算次數(shù)

對(duì)于同一個(gè)問題的計(jì)算，可以有不同的計(jì)算方法，如計(jì)算的值，如果逐個(gè)相乘，則要計(jì)算254次乘法；但如果寫成

只要做14次乘法運(yùn)算就可以完成。由此可見，如果方法選擇得當(dāng)，則不僅能減少計(jì)算次數(shù)，提高計(jì)算速度，也可以簡(jiǎn)化邏輯結(jié)構(gòu)，減少誤差積累，從而達(dá)到提高計(jì)算精度的目的。

2022/12/30精選課件371.3.5簡(jiǎn)化計(jì)算步驟，減少運(yùn)算次數(shù)2022/12/29誤差問題是計(jì)算方法中既重要而又困難的課題，本章介紹了誤差來(lái)源及相關(guān)基本概念，同時(shí)還給出設(shè)計(jì)算法時(shí)應(yīng)注意的問題，這對(duì)今后學(xué)習(xí)是必須的。2022/12/30精選課件38誤差問題是計(jì)算方法中既重要而又困難的課題習(xí)題4.要使的相對(duì)誤差不超過至少需要保留多少位有效數(shù)字？所有至少要保留5位有效數(shù)字。精選課件習(xí)題4.要使的相對(duì)誤差不超過至39數(shù)學(xué)人類理性的杰作

先進(jìn)文化的精品各門科學(xué)的基礎(chǔ)和工具谷超豪

2003年5月2022/12/30精選課件40數(shù)學(xué)2022/12/29精選課件4041計(jì)算方法1計(jì)算方法1.1計(jì)算方法研究的對(duì)象和特點(diǎn)

計(jì)算方法實(shí)際上就是計(jì)算機(jī)上使用的數(shù)值計(jì)算方法，所以這門課程又稱為數(shù)值計(jì)算方法或數(shù)值分析。它是專門研究求解各種數(shù)學(xué)問題的數(shù)值計(jì)算方法?，F(xiàn)在，由于大多數(shù)科學(xué)計(jì)算都比較復(fù)雜，人工計(jì)算無(wú)法完成；而計(jì)算機(jī)科學(xué)的迅速發(fā)展和廣泛應(yīng)用提供了解決這些復(fù)雜問題的新途徑。用計(jì)算機(jī)解決科學(xué)計(jì)算問題的一般過程，可以概括為：

實(shí)際問題→數(shù)學(xué)模型→計(jì)算方法→程序設(shè)計(jì)→上機(jī)計(jì)算→結(jié)果分析精選課件1.1計(jì)算方法研究的對(duì)象和特點(diǎn)精選課件42

由實(shí)際問題應(yīng)用有關(guān)科學(xué)知識(shí)和數(shù)學(xué)理論建立數(shù)學(xué)模型這一過程，通常作為應(yīng)用數(shù)學(xué)的任務(wù)。而根據(jù)數(shù)學(xué)模型提出求解的計(jì)算方法直到編出程序上機(jī)算出結(jié)果，進(jìn)而對(duì)計(jì)算結(jié)果進(jìn)行分析，這一過程則是計(jì)算數(shù)學(xué)的任務(wù)，也是數(shù)值計(jì)算方法的研究對(duì)象。因此，數(shù)值計(jì)算方法就是研究用計(jì)算機(jī)解決數(shù)學(xué)問題的數(shù)值方法及其理論的科學(xué)。它的內(nèi)容包括：誤差理論、線性與非線性方程(組)的數(shù)值解、矩陣的特征值與特征向量計(jì)算、曲線擬合與函數(shù)逼近、插值方法、數(shù)值積分與數(shù)值微分、常微分方程與偏微分方程數(shù)值解等。2022/12/30精選課件43由實(shí)際問題應(yīng)用有關(guān)科學(xué)知識(shí)和數(shù)學(xué)理論建2022/12/30精選課件441.把實(shí)際問題歸結(jié)為數(shù)值問題⒉制定數(shù)值問題的算法⒊得不到準(zhǔn)確解時(shí)，設(shè)法得到近似解⒋解的特性（近似程度，斂散性）⒌各種方法的優(yōu)缺點(diǎn)（速度，存儲(chǔ)量）⒍各種方法的實(shí)用范圍（收斂范圍）⑴計(jì)算方法要解決的幾個(gè)問題：（或研究的對(duì)象）2022/12/29精選課件41.把實(shí)際問題歸結(jié)為數(shù)值問題⑴2022/12/30精選課件45⒈把實(shí)際問題歸結(jié)為數(shù)值問題

由于電子數(shù)字計(jì)算機(jī)的廣泛使用，使越來(lái)越多的實(shí)際問題能歸結(jié)為數(shù)值問題而得到解決（如：曲線擬合，數(shù)值逼近等）。

【什么是數(shù)值問題呢？所謂數(shù)值問題，指的是由一組已知數(shù)據(jù)（又稱輸入數(shù)據(jù)）求出一組結(jié)果數(shù)據(jù)（又稱輸出數(shù)據(jù)），使得這兩組數(shù)據(jù)之間滿足預(yù)先指定的某種關(guān)系（函數(shù)關(guān)系）的問題。（即由一組數(shù)求得另一組數(shù)）】⒉制定數(shù)值問題的算法

【什么叫算法？用完全確定的運(yùn)算規(guī)則（包括運(yùn)算的邏輯順序），對(duì)某一類數(shù)值問題的輸入數(shù)據(jù)進(jìn)行處理，判斷此數(shù)值問題是否有解，在解存在的情況下，給出輸出數(shù)據(jù)，此種過程稱為算法?！?022/12/29精選課件5⒈把實(shí)際問題歸結(jié)為數(shù)值問題⒊得不到準(zhǔn)確解時(shí)，設(shè)法得到近似解

例：求已知數(shù)。由數(shù)學(xué)中的極限理論可知，（極限存在）

于是又∵n只能有限，∴x是近似值。462022/12/30精選課件⒊得不到準(zhǔn)確解時(shí)，設(shè)法得到近似解62022/12/29精選課在計(jì)算方法中，我們還將討論：⒋解的特性（近似程度，斂散性）⒌各種方法的優(yōu)缺點(diǎn)（速度，存儲(chǔ)量）⒍各種方法的實(shí)用范圍（收斂范圍）2022/12/30精選課件47在計(jì)算方法中，我們還將討論：2022/12/29精選課件7⑵一個(gè)好的方法應(yīng)具有如下特點(diǎn)：

第一，面向計(jì)算機(jī)，要根據(jù)計(jì)算機(jī)特點(diǎn)提供實(shí)際可行的有效算法，即算法只能包括加、減、乘、除運(yùn)算和邏輯運(yùn)算，是計(jì)算機(jī)能直接處理的。

第二，有可靠的理論分析，能任意逼近并達(dá)到精度要求，對(duì)近似算法要保證方法的收斂性和數(shù)值穩(wěn)定性，還要對(duì)誤差進(jìn)行分析，這些都建立在相應(yīng)數(shù)學(xué)理論基礎(chǔ)上。

第三，要有好的計(jì)算復(fù)雜性（即時(shí)間復(fù)雜性和空間復(fù)雜性）；時(shí)間復(fù)雜性好是指節(jié)省時(shí)間，空間復(fù)雜性好是指節(jié)省存儲(chǔ)量，這也是建立算法要研究的問題，它關(guān)系到算法能否在計(jì)算機(jī)上實(shí)現(xiàn)。

第四，要有數(shù)值實(shí)驗(yàn)，即任何一個(gè)算法除了從理論上要滿足上述三點(diǎn)外，還要通過數(shù)值試驗(yàn)證明是行之有效的。2022/12/30精選課件48⑵一個(gè)好的方法應(yīng)具有如下特點(diǎn)：2022/12/29

例：一個(gè)簡(jiǎn)單的算法問題，設(shè)要對(duì)給定的求多項(xiàng)式的值。492022/12/30精選課件

一種計(jì)算過程是直接計(jì)算的每一項(xiàng)后逐項(xiàng)求和，這樣要做次乘法和次加法。

例：一個(gè)簡(jiǎn)單的算法問題，設(shè)要對(duì)給定的求多502022/12/30精選課件

另一種算法就是先將變形為如下形式：再由內(nèi)層向外層計(jì)算，如設(shè)：

就可以得到一個(gè)遞推公式k=1,2,…,n(1.3)

這樣的計(jì)算過程只需要計(jì)算n次乘法和n次加法。這種算法和上一種算法相比，不僅邏輯結(jié)構(gòu)簡(jiǎn)單，而且計(jì)算也明顯地減少了。多項(xiàng)式求值的這種算法稱為秦九韶算法（計(jì)算框圖見圖1.2)。102022/12/29精選課件另一種算法就是1.2誤差的來(lái)源及其基本概念1.2.1誤差來(lái)源：用數(shù)值計(jì)算方法解決科學(xué)技術(shù)中的具體問題，一般說都有誤差，其來(lái)源有下列四種：（注：由于人為的粗心大意造成的計(jì)算錯(cuò)誤，不算誤差）

1.模型誤差數(shù)學(xué)描述和實(shí)際問題之間的誤差如：勻加速運(yùn)動(dòng)或自由落體運(yùn)動(dòng)公式略去了風(fēng)力，空氣阻力等。

2.觀察誤差如：讀表、讀尺、讀溫度計(jì)。2022/12/30精選課件511.2誤差的來(lái)源及其基本概念2022/12/29精選課件3.截?cái)嗾`差

如：對(duì)x>0，求。利用泰勒公式有取其部分和作為，就產(chǎn)生了截?cái)嗾`差。4.舍入誤差由于計(jì)算機(jī)的字長(zhǎng)有限，對(duì)超過位數(shù)的數(shù)字要進(jìn)行舍入，通常取與它們接近的數(shù)來(lái)表示，由此產(chǎn)生的誤差稱為舍入誤差。例如，我們通常使用2.71828和3.1416來(lái)表示的近似值，由此所產(chǎn)生的誤差就是舍入誤差。2022/12/30精選課件523.截?cái)嗾`差2022/12/29精選課件12

本課程僅討論后兩種誤差（截?cái)嗾`差和舍入誤差），討論它們?cè)谟?jì)算過程中的傳播和對(duì)計(jì)算結(jié)果的影響，研制能夠控制誤差的影響且保證最終結(jié)果有足夠精度的算法。2022/12/30精選課件53本課程僅討論后兩種誤差（截?cái)嗾`差和舍入誤差），1.2.2誤差的概念和有效數(shù)字1.絕對(duì)誤差定義1.1

設(shè)某數(shù)的精確值為，其近似值為，那么與之差稱為近似值的絕對(duì)誤差，簡(jiǎn)稱誤差。一般地，某數(shù)的精確值是不知道的，因而

不能求出，但往往可以估計(jì)出它的大小范圍，亦即可以確定一個(gè)正數(shù)，使得此時(shí)，稱為的絕對(duì)誤差限。有時(shí)也用表示近似值的精確值或精確值的所在范圍。2022/12/30精選課件541.2.2誤差的概念和有效數(shù)字1.絕對(duì)誤差2022/2.相對(duì)誤差

絕對(duì)誤差反映不了一個(gè)近似數(shù)的準(zhǔn)確程度。如：稱一頭大象誤差十公斤，稱一只螞蟻誤差一克，誰(shuí)的近似程度好，顯然大象的近似應(yīng)好些。于是引進(jìn)了相對(duì)誤差。記

稱為近似值x的相對(duì)誤差，由于精確值一般不知道，實(shí)際計(jì)算時(shí)通常取作為近似值x的相對(duì)誤差。若能求出一個(gè)正數(shù)，使得，則稱為近似值x的相對(duì)誤差限。它是無(wú)量綱的數(shù)，通常用百分比表示。2022/12/30精選課件552.相對(duì)誤差2022/12/29精選課件

例：甲用米尺測(cè)量10M長(zhǎng)的物體，所產(chǎn)生的絕對(duì)誤差為2cm，乙用同一米尺測(cè)量1M長(zhǎng)的物體，所產(chǎn)生的絕對(duì)誤差為1cm，他們誰(shuí)的測(cè)量精度好？解：根據(jù)上述定義可知，甲測(cè)量時(shí)的相對(duì)誤差

乙測(cè)量時(shí)的相對(duì)誤差可見甲測(cè)量結(jié)果比乙精確。562022/12/30精選課件例：甲用米尺測(cè)量10M長(zhǎng)的物體，所產(chǎn)生的絕對(duì)誤3.有效數(shù)字

當(dāng)準(zhǔn)確數(shù)的位數(shù)很多時(shí)，我們常按“四舍五入”原則減少位數(shù)，得其近似數(shù)。并用“有效數(shù)字”來(lái)描述它。定義1.2如果近似值的誤差限是某一位的半個(gè)單位，該位到的第一位非零數(shù)字共有位，則稱有位有效數(shù)字。如果的每一位都是有效數(shù)字，則稱為有效數(shù)。如：，有5位有效數(shù)字，有6位有效數(shù)字2022/12/30精選課件573.有效數(shù)字2022/12/29精選

任何一個(gè)實(shí)數(shù)，經(jīng)四舍五入后得到的近似值都可以表示為如下標(biāo)準(zhǔn)形式：（其中m可為正負(fù)數(shù)）2022/12/30精選課件58如果其絕對(duì)誤差限滿足則稱近似值具有n位有效數(shù)字。任何一個(gè)實(shí)數(shù)，經(jīng)四舍五入后得到的近似2022/12/30精選課件59例1

設(shè)=0.0270是某數(shù)經(jīng)“四舍五入”所得，則誤差不超過末位的半個(gè)單位，即：又,故該不等式又可寫為由有效數(shù)字定義可知,有3位有效數(shù)字，分別是2,7，0。2022/12/29精選課件19例12022/12/30精選課件60例2

又,故該不等式又可寫為故有3位有效數(shù)字，分別是3,2，8。由于中的數(shù)字9不是有效數(shù)字,故不是有效數(shù)。思考：有幾位有效數(shù)字？

2022/12/29精選課件20例2有效數(shù)位為3位有效數(shù)位為5位有效數(shù)位為4位精選課件有效數(shù)位為3位有效數(shù)位為5位有效數(shù)位為4位精選課件614.有效數(shù)字與絕對(duì)誤差、相對(duì)誤差有如下關(guān)系:

⑴若某數(shù)的近似值有n位有效數(shù)字，那么這個(gè)近似值的絕對(duì)誤差限為

（注：由（1.4）式可知：m為整數(shù)位，n為小數(shù)位）由此看出：當(dāng)m相同時(shí)，n越大，則m-n越小，從而有效位數(shù)越多，其絕對(duì)誤差限越小。數(shù)據(jù)也就越精確。

2022/12/30精選課件624.有效數(shù)字與絕對(duì)誤差、相對(duì)誤差有如下關(guān)系:2022/1⑵用式(1.4)表示的近似數(shù)，若具有n位有效數(shù)字，則其相對(duì)誤差限為

則至少具有n位有效數(shù)字。

2022/12/30精選課件63

反之，若的相對(duì)誤差限為⑵用式(1.4)表示的近似數(shù)，若具有n位證明由⑴知，若x具有n位有效數(shù)字，則從而（將上式代入）642022/12/30精選課件（參見1.4式）證明由⑴知，若x具有n位有效數(shù)字，則242022/12/

反之，若x的相對(duì)誤差限為

所以x至少有n位有效數(shù)字。

由(2)可以看出，有效位數(shù)越多，相對(duì)誤差限就越小，精確度也就越高。2022/12/30精選課件65反之，若x的相對(duì)誤差限為

1.2.3初值誤差的傳播近似數(shù)參加運(yùn)算后所得到的值也是近似值，含有誤差，將這一現(xiàn)象稱為誤差傳播。數(shù)值運(yùn)算中誤差的傳播情況比較復(fù)雜，主要表現(xiàn)在：算法本身可能有截?cái)嗾`差；初始數(shù)據(jù)在計(jì)算機(jī)內(nèi)的浮點(diǎn)表示一般有舍入誤差；每次運(yùn)算一般又會(huì)產(chǎn)生新的誤差，并且傳播以前已經(jīng)引入的誤差。因此，對(duì)誤差進(jìn)行準(zhǔn)確分析是困難的，但也是很重要的。它關(guān)系到一個(gè)方法是否穩(wěn)定,計(jì)算結(jié)果是否可靠。2022/12/30精選課件661.2.3初值誤差的傳播2022/12/29精選課件誤差的傳播與積累例3：蝴蝶效應(yīng)

——紐約的一只蝴蝶翅膀一拍，風(fēng)和日麗的北京就刮起臺(tái)風(fēng)來(lái)了？！NYBJ以上是一個(gè)病態(tài)問題精選課件誤差的傳播與積累例3：蝴蝶效應(yīng)——紐約的一只蝴蝶翅膀一拍67

1.3選用和設(shè)計(jì)算法應(yīng)注意的問題一般衡量算法的標(biāo)準(zhǔn)有：算法是否穩(wěn)定，算法的運(yùn)算次數(shù)和算法的存儲(chǔ)量是否盡量少，同時(shí)還要考慮誤差的傳播等。選用和設(shè)計(jì)算法應(yīng)注意如下幾個(gè)問題:

⒈

選用數(shù)值穩(wěn)定的計(jì)算公式

⒉防止兩個(gè)相近數(shù)相減

⒊防止大數(shù)“吃掉”小數(shù)

⒋簡(jiǎn)化計(jì)算步驟，減少運(yùn)算次數(shù)2022/12/30精選課件681.3選用和設(shè)計(jì)算法應(yīng)注意的問題2022/12/29精1.3.1選用數(shù)值穩(wěn)定的計(jì)算公式

如果數(shù)值算法的計(jì)算舍入誤差積累是可以控制的，則稱其為數(shù)值穩(wěn)定的；反之，稱為數(shù)值不穩(wěn)定的。例：計(jì)算定積分（序列）

利用分部積分法不難求得遞推關(guān)系式為

2022/12/30精選課件69公式推導(dǎo)1.3.1選用數(shù)值穩(wěn)定的計(jì)算公式2022/1由式（1.16）可依次算出如下結(jié)果：(p011.c)

2022/12/30精選課件70注意到（注：從積分中按x的最小和最大值提出ex)?(1.17)由上面的不等式可以看出由式（1.16）可依次算出如下結(jié)果：(p011.c)2

因此按遞推關(guān)系式（1.16）所算出的計(jì)算值是錯(cuò)誤的，嚴(yán)重偏離其準(zhǔn)確值。發(fā)生這種現(xiàn)象的原因是因?yàn)楸旧碛胁怀^的誤差。設(shè)是具有精確初始值，并按式（1.16)計(jì)算而得的，則有由此可見，初始值微小的誤差會(huì)隨著計(jì)算步數(shù)的增加而迅速擴(kuò)大，最終使計(jì)算結(jié)果失真。故算法式（1.16)不能控制誤差的傳播，是數(shù)值不穩(wěn)定的。2022/12/30精選課件71因此按遞推關(guān)系式（1.16如果將式（1.16）改寫為2022/12/30精選課件72（1.18)又注意到結(jié)合式（1.17）得由上面的估計(jì)式取開始按式（1.18）計(jì)算，有如下結(jié)果：（p012.c