數(shù)值計算方法第一章

1、第一章 緒 論 本章以誤差為主線，介紹了計算方法課程的特點，并概略描述了與算法相關(guān)的基本概念，如收斂性、穩(wěn)定性，其次給出了誤差的度量方法以及誤差的傳播規(guī)律，最后，結(jié)合數(shù)值實驗指出了算法設(shè)計時應(yīng)注意的問題§1.1 引 言 計算方法以科學(xué)與工程等領(lǐng)域所建立的數(shù)學(xué)模型為求解對象，目的是在有限的時間段內(nèi)利用有限的計算工具計算出模型的有效解答。 由于科學(xué)與工程問題的多樣性和復(fù)雜性，所建立的數(shù)學(xué)模型也是各種各樣的、復(fù)雜的. 復(fù)雜性表現(xiàn)在如下幾個方面：求解系統(tǒng)的規(guī)模很大，多種因素之間的非線性耦合，海量的數(shù)據(jù)處理等等，這樣就使得在其它課程中學(xué)到的分析求解方法因計算量龐大而不能得到計算結(jié)果，且更多的復(fù)

2、雜數(shù)學(xué)模型沒有分析求解方法 這門課程則是針對從各種各樣的數(shù)學(xué)模型中抽象出或轉(zhuǎn)化出的典型問題，介紹有效的串行求解算法，它們包括(1) 非線性方程的近似求解方法；(2) 線性代數(shù)方程組的求解方法；(3) 函數(shù)的插值近似和數(shù)據(jù)的擬合近似；(4) 積分和微分的近似計算方法；(5) 常微分方程初值問題的數(shù)值解法；(6) 優(yōu)化問題的近似解法；等等從如上內(nèi)容可以看出，計算方法的顯著特點之一是“近似” 之所以要進行近似計算，這與我們使用的工具、追求的目標(biāo)、以及參與計算的數(shù)據(jù)來源等因素有關(guān) 計算機只能處理有限數(shù)據(jù)，只能區(qū)分、存儲有限信息，而實數(shù)包含有無窮多個數(shù)據(jù)，這樣，當(dāng)把原始數(shù)據(jù)、中間數(shù)據(jù)、以及最終計算結(jié)果用

3、機器數(shù)表示時就不可避免的引入了誤差，稱之為舍入誤差 我們需要在有限的時間段內(nèi)得到運算結(jié)果，就需要將無窮的計算過程截斷，從而產(chǎn)生截斷誤差 如的計算是無窮過程，當(dāng)用作為的近似時，則需要進行有限過程的計算，但產(chǎn)生了截斷誤差 當(dāng)用計算機計算時，因為舍入誤差的存在，我們也只能得到的近似值，也就是說最終用近似，該近似值既包含有舍入誤差，也包含有截斷誤差 當(dāng)參與計算的原始數(shù)據(jù)是從儀器中觀測得來時，也不可避免得有觀測誤差 由于這些誤差的大量存在，我們得到的只能是近似結(jié)果，進而對這些結(jié)果的“可靠性”進行分析就是必須的，它成為計算方法的第二個顯著特點 可靠性分析包括原問題的適定性和算法的收斂性、穩(wěn)定性 所謂適定性

4、問題是指解存在、惟一，且解對原始數(shù)據(jù)具有連續(xù)依賴性的問題 對于非適定問題的求解，通常需要作特殊的預(yù)處理，然后才能做數(shù)值計算 在這里，如無特殊說明，都是對適定的問題進行求解 對于給定的算法，若有限步內(nèi)得不到精確解，則需研究其收斂性 收斂性是研究當(dāng)允許計算時間越來越長時，是否能夠得到越來越可靠的結(jié)果，也就是研究截斷誤差是否能夠趨于零 對于給定的算法，穩(wěn)定性分析是指隨著計算過程的逐步向前推進，研究觀測誤差、舍入誤差對計算結(jié)果的影響是否很大 對于同一類模型問題的求解算法可能不止一種，常希望從中選出高效可靠的求解算法 如我國南宋時期著名的數(shù)學(xué)家秦九韶就提出求n次多項式值的如下快速算法； 它通過n次乘法和

5、n次加法就計算出了任意n次多項式的值 再如冪函數(shù)可以通過如下快速算法計算出其值；循環(huán)6次如上算法僅用了6次乘法運算，就得到運算結(jié)果 算法最終需要在計算機上運行相應(yīng)程序，才能得到結(jié)果，這樣就要關(guān)注算法的時間復(fù)雜度(計算機運行程序所需時間的度量)、空間復(fù)雜度(程序、數(shù)據(jù)對存儲空間需求的度量)和邏輯復(fù)雜度(關(guān)聯(lián)程序的開發(fā)周期、可維護性以及可擴展性) 事實上，每一種算法都有自己的局限性和優(yōu)點，僅僅理論分析是很不夠的，大量的實際計算也非常重要，結(jié)合理論分析以及相當(dāng)?shù)臄?shù)值算例結(jié)果才有可能選擇出適合自己關(guān)心問題的有效求解算法 也正因如此，只有理論分析結(jié)合實際計算才能真正把握準(zhǔn)算法 §1.2 誤差的

6、度量與傳播一、誤差的度量 誤差的度量方式有絕對誤差、相對誤差和有效數(shù)字 定義1.1 用作為量的近似，則稱為近似值的絕對誤差 由于量x的真值通常未知，所以絕對誤差不能依據(jù)定義求得，但根據(jù)測量工具或計算情況，可以估計出絕對誤差絕對值的一個較小上界，即有 (1.1)稱正數(shù)為近似值的絕對誤差限，簡稱誤差 這樣得到不等式工程中常用表示近似值的精度或真值x所在的范圍 誤差是有量綱的，所以僅誤差數(shù)值的大小不足以刻劃近似的準(zhǔn)確程度 如量 (1.2)為此，我們需要引入相對誤差定義1.2 用作為量的近似，稱為近似值的相對誤差 當(dāng)是x的較好近似時，也可以用如下公式計算相對誤差 (1.3) 顯然，相對誤差是一個無量綱

7、量，它不隨使用單位變化 如式(1.2)中的量s的近似，無論使用何種單位，它的相對誤差都是同一個值 同樣地，因為量x的真值未知，我們需要引入近似值的相對誤差限，它是相對誤差絕對值的較小上界 結(jié)合式(1.1)和(1.3)，相對誤差限可通過絕對誤差限除以近似值的絕對值得到，即 (1.4) 為給出近似數(shù)的一種表示法，使之既能表示其大小，又能體現(xiàn)其精確程度，需引入有效數(shù)字以及有效數(shù)的概念 定義1.3 設(shè)量的近似值有如下標(biāo)準(zhǔn)形式 (1.5)其中且，m為近似值的量級 如果使不等式 (1.6)成立的最大整數(shù)為n，則稱近似值具有n位有效數(shù)字，它們分別是、 和 特別地，如果有，即最后一位數(shù)字也是有效數(shù)字，則稱是有

8、效數(shù) 從定義可以看出，近似數(shù)是有效數(shù)的充分必要條件是末位數(shù)字所在位置的單位一半是絕對誤差限 利用該定義也可以證明，對真值進行“四舍五入”得到的是有效數(shù) 對于有效數(shù)，有效數(shù)字的位數(shù)等于從第一位非零數(shù)字開始算起，該近似數(shù)具有的位數(shù) 注意，不能給有效數(shù)的末位之后隨意添加零，否則就改變了它的精度 例1.1 設(shè)量，其近似值， 試回答這三個近似值分別有幾位有效數(shù)字，它們是有效數(shù)嗎？ 解 這三個近似值的量級，因為有 所以和都有3位有效數(shù)字，但不是有效數(shù) 具有4位有效數(shù)字，是有效數(shù)二、誤差的傳播 這里僅介紹初值誤差傳播，即假設(shè)自變量帶有誤差，函數(shù)值的計算不引入新的誤差 對于函數(shù)有近似值，利用在點處的泰勒公式(

9、Taylor Formula)，可以得到 (1.7)其中，是的近似值，是的絕對誤差 式(1.7)表明函數(shù)值的絕對誤差近似等于自變量絕對誤差的線性組合，組合系數(shù)為相應(yīng)的偏導(dǎo)數(shù)值 從式(1.7)也可以推得如下函數(shù)值的相對誤差傳播近似計算公式 (1.8) 對于一元函數(shù)，從式(1.7)和(1.8)可得到如下初值誤差傳播近似計算公式 (1.9) (1.10)式(1.9)表明，當(dāng)導(dǎo)數(shù)值的絕對值很大時，即使自變量的絕對誤差比較小，函數(shù)值的絕對誤差也可能很大 例1.2 試建立函數(shù)的絕對誤差(限)、相對誤差的近似傳播公式，以及時的相對誤差限傳播公式 解 由公式(1.7)和(1.8)可分別推得和的絕對誤差、相對誤

10、差傳播公式如下 (1.11) (1.12)進而有 于是有和的絕對誤差限近似傳播公式 當(dāng)時，由式(1.3)推得相對誤差限的近似傳播公式 例1.3 使用足夠長且最小刻度為1mm的尺子，量得某桌面長的近似值 mm，寬的近似值mm (數(shù)據(jù)的最后一位均為估計值) 試求桌子面積近似值的絕對誤差限和相對誤差限 解 長和寬的近似值的最后一位都是估計位，尺子的最小刻度是毫米，故有誤差限mm，mm面積，由式(1.7)得到近似值的絕對誤差近似為進而有絕對誤差限 mm2相對誤差限 §1.3 數(shù)值實驗與算法性能比較 本節(jié)通過幾個簡單算例說明解決同一個問題可以有不同的算法，但算法的性能并不完全相同，他們各自有自

11、己的適用范圍，并進而指出算法設(shè)計時應(yīng)該注意的事項 算例1.1 表達式，在計算過程中保留7位有效數(shù)字，研究對不同的x，兩種計算公式的計算精度的差異 說明1：Matlab軟件采用IEEE規(guī)定的雙精度浮點系統(tǒng)，即64位浮點系統(tǒng)，其中尾數(shù)占52位，階碼占10位，尾數(shù)以及階碼的符號各占1位 機器數(shù)的相對誤差限(機器精度)eps=2522.220446×1016，能夠表示的數(shù)的絕對值在區(qū)間(2.2250739×10308，1.797693×10308)內(nèi)，該區(qū)間內(nèi)的數(shù)能夠近似表達，但有舍入誤差，能夠保留至少15位有效數(shù)字 其原理可參閱參考文獻2, 4 分析算法1： 和算法2：

12、 的誤差時，精確解用雙精度的計算結(jié)果代替 我們選取點集中的點作為x，比較兩種方法誤差的差異 從圖1.1可以看出，當(dāng)x不是很大時，兩種算法的精度相當(dāng)，但當(dāng)x很大時算法2的精度明顯高于算法1 這是因為，當(dāng)x很大時，和是相近數(shù)，用算法1進行計算時出現(xiàn)相近數(shù)相減，相同的有效數(shù)字相減后變成零，于是有效數(shù)字位數(shù)急劇減少，自然相對誤差增大 這一事實也可以從誤差傳播公式(1.12)分析出 鑒于此，算法設(shè)計時，應(yīng)該避免相近數(shù)相減 在圖1.2中我們給出了當(dāng)x接近時，兩種算法的精度比較，其中變量x依次取為 從圖中可以看出兩種方法的相對誤差基本上都為，因而二者的精度相當(dāng) 圖1.1 算例1.1中兩種算法的相對誤差圖（）

13、 圖1.2 算例1.1中兩種算法的精度比較 算例1.2 試用不同位數(shù)的浮點數(shù)系統(tǒng)求解如下線性方程組 說明2：浮點數(shù)系統(tǒng)中的加減法在運算時，首先按較大的階對齊，其次對尾數(shù)實施相應(yīng)的加減法運算，最后規(guī)范化存入計算機 算法1 首先用第一個方程乘以適當(dāng)?shù)南禂?shù)加至第二個方程，使得第二個方程的的系數(shù)為零，這時可解出；其次將帶入第一個方程，進而求得(在第三章中稱該方法為高斯消元法) 當(dāng)用4位和7位尾數(shù)的浮點運算實現(xiàn)該算法，分別記之為算法1a和算法1b 算法 2 首先交換兩個方程的位置，其次按算法1計算未知數(shù) (第三章中稱其為選主元的高斯消元法) 當(dāng)用4位和7位尾數(shù)的浮點運算實現(xiàn)該算法，分別記之為算法2a和算

14、法2b 方程組的精確解為， ，用不同的算法計算出的結(jié)果見表1.1 表1.1 對算例1.2用不同算法的計算結(jié)果比較算例1.2算法1a0.00000.10×1010.50000.25×107算法2a0.25000.75×1070.50000.25×107算法1b0.26000000.40×1010.49999870.10×106算法2b0.25000200.50×1080.50000000.25×107 對于算例1.2，表中的數(shù)據(jù)表明，當(dāng)用4位尾數(shù)計算時，算法1給出錯誤的結(jié)果，算法2則給出解很好的近似 這是因為在實現(xiàn)算

15、法1時，需要給第一個方程乘以加至第二個方程，從而削去第二個方程中的系數(shù)，但在計算的系數(shù)時需做如下運算(1.13)對上式用4位尾數(shù)進行計算，其結(jié)果為 因為舍入誤差，給相對較大的數(shù)加以相對較小的數(shù)時，出現(xiàn)大數(shù)“吃掉”小數(shù)的現(xiàn)象 計算右端項時，需做如下運算 (1.14)同樣出現(xiàn)了大數(shù)吃小數(shù)現(xiàn)象，其結(jié)果為 這樣，得到的變形方程組中沒有原方程組中第二個方程的信息，因而其解遠偏離于原方程組的解 該算法中之所以出現(xiàn)較大數(shù)的原因是因為運算，因而算法設(shè)計中盡可能避免用絕對值較大的數(shù)除以絕對值較小的數(shù) 其實當(dāng)分子的量級遠遠大于分母的量級時，除法運算還會導(dǎo)致溢出，計算機終止運行 雖從單純的一步計算來看，大數(shù)吃掉小數(shù)

16、，只是精度有所損失，但多次的大數(shù)吃小數(shù)，累計起來可能帶來巨大的誤差，甚至導(dǎo)致錯誤 例如在算法1a中出現(xiàn)了兩次大數(shù)吃小數(shù)現(xiàn)象，帶來嚴重的后果 因而盡可能避免大數(shù)吃小數(shù)的出現(xiàn)在算法設(shè)計中也是非常必要的 當(dāng)用較多的尾數(shù)位數(shù)進行計算，舍入誤差減小，算法1和2的結(jié)果都有所改善，算法1的改進幅度更大些 算例1.3 計算積分有遞推公式，已知 采用IEEE雙精度浮點數(shù)，分別用如下兩種算法計算的近似值 算法1 取的近似值為，按遞推公式計算 算法2 因為，取的近似值為，按遞推公式計算 算法1和算法2 的計算結(jié)果見表1.2 誤差絕對值的對數(shù)圖見圖1.3表1.2 算例1.3的計算結(jié)果n算法1n算法218.8392e-

17、0021.9429e-016394.5833e-0033.9959e-00425.8039e-0029.8532e-016384.2115e-0037.9919e-00534.3139e-0024.9197e-015374.4209e-0031.5984e-00543.4306e-0022.4605e-014364.5212e-0033.1967e-00652.8468e-0021.2304e-013354.6513e-0036.3935e-00762.4325e-0026.1520e-013344.7840e-0031.2787e-007334.9255e-0032.5574e-008251

18、.1740e+0011.1734e+001325.0755e-0035.1148e-00926-5.8664e+0015.8670e+001315.2349e-0031.0230e-009272.9336e+0022.9335e+002 305.4046e-0032.0459e-01028-1.4667e+0031.4668e+003 297.3338e+0037.3338e+003 30-3.6669e+0043.6669e+004圖1.3 算例1.3用不同算法計算結(jié)果的誤差絕對值的對數(shù)圖 從表1.2中的計算結(jié)果可以看出，算法1隨著計算過程的推進，絕對誤差幾乎不斷地以5的倍數(shù)增長，即有成立 對于逐步向前推進的算法，若隨著過程的進行，相對誤差在不斷增長，導(dǎo)致產(chǎn)生不可靠的結(jié)果，這種算法稱之為數(shù)值不穩(wěn)定的算法 對于算法1絕對誤差按5的冪次增長，但真值的絕對值卻在不斷變小且小于1，相對誤差增長的速度快于5的冪次，導(dǎo)致產(chǎn)生錯誤的結(jié)果，因而算法1數(shù)值不穩(wěn)定，不能使用 而算法2隨著計算過程的推進，絕對誤差幾乎不斷地縮小為上一步的1/5，即有成立 絕對誤差不斷變小，真值的絕對值隨著過程向前推