數(shù)值分析課件 第1章 緒論

1、第一章 緒論上世紀中葉誕生的計算機給科學(xué)、工程技術(shù)和人類的社會生活帶來一場新的革命。它使科學(xué)計算平行于理論分析和實驗研究，成為人類探索未知科學(xué)領(lǐng)域和進行大型工程設(shè)計的第三種方法和手段。在獨創(chuàng)性工作的先行性研究中，科學(xué)計算更有突出的作用。在今天，熟練地運用電子計算機進行科學(xué)計算，已成為科學(xué)工作者的一項基本技能。然而，科學(xué)計算并不是計算機本身的自然產(chǎn)物，而是數(shù)學(xué)與計算機結(jié)合的結(jié)果，它的核心內(nèi)容是以現(xiàn)代化的計算機及數(shù)學(xué)軟件為工具，以數(shù)學(xué)模型為基礎(chǔ)進行模擬研究。近年來，它同時也成為數(shù)學(xué)科學(xué)本身發(fā)展的源泉和途徑之一。1 數(shù)值分析的研究對象與特點數(shù)值分析是計算數(shù)學(xué)的一個主要部分，計算數(shù)學(xué)是數(shù)學(xué)科學(xué)的一個分

2、支，它研究用計算機求解各種數(shù)學(xué)問題的數(shù)值計算方法及其理論與軟件實現(xiàn)。一般地說，用計算機解決科學(xué)計算問題，首先需要針對實際問題提煉出相應(yīng)的數(shù)學(xué)模型，然后為解決數(shù)學(xué)模型設(shè)計出數(shù)值計算方法，經(jīng)過程序設(shè)計之后上機計算，求出數(shù)值結(jié)果，再由實驗來檢驗。概括為實際問題數(shù)學(xué)模型計算方法程序設(shè)計計算結(jié)果由實際問題的提出到上機求得問題的解答的整個過程都可看作是應(yīng)用數(shù)學(xué)的任務(wù)。如果細分的話，由實際問題應(yīng)用有關(guān)科學(xué)知識和數(shù)學(xué)理論建立數(shù)學(xué)模型這一過程，通常作為應(yīng)用數(shù)學(xué)的任務(wù)，而根據(jù)數(shù)學(xué)模型提出求解的數(shù)值計算方法直到編出程序上機計算出結(jié)果，這一過程則是計算數(shù)學(xué)的任務(wù)，即數(shù)值分析研究的對象。因此，數(shù)值分析是尋求數(shù)學(xué)問題近似

3、解的方法、過程及其理論的一個數(shù)學(xué)分支。它以純數(shù)學(xué)作為基礎(chǔ)，但卻不完全像純數(shù)學(xué)那樣只研究數(shù)學(xué)本身的理論，而是著重研究數(shù)學(xué)問題求解的數(shù)值方法及與此有關(guān)的理論，包括方法的收斂性，穩(wěn)定性及誤差分析；還要根據(jù)計算機的特點研究計算時間最?。ɑ蛴嬎阗M用最?。┑挠嬎惴椒āＳ械姆椒ㄔ诶碚撋想m然還不夠完善與嚴密，但通過對比分析，實際計算和實踐檢驗等手段，被證明是行之有效的方法也可采用。因此數(shù)值分析既有純數(shù)學(xué)高度抽象性與嚴密科學(xué)性的特點，又有應(yīng)用的廣泛性與實際試驗的高度技術(shù)性的特點，是一門與使用計算機密切結(jié)合的實用性很強的數(shù)學(xué)課程。在電子計算機成為數(shù)值計算機的主要工具以后，則要求研究適合計算機使用的，滿足精確要求，

4、計算時間省的有效算法及其相關(guān)的理論。在實現(xiàn)這些算法時往往還要根據(jù)計算機的容量、字長、速度等指標(biāo)，研究具體的求解步驟和程序設(shè)計技巧。有的方法在理論上雖還不夠嚴格，但通過實際計算、對比分析等手段，證明是行之有效的方法，也應(yīng)采用。這些就是數(shù)值分析具有的特點，概括起來有四點：第一，面向計算機，要根據(jù)計算機特點提供切實可行的有效算法。即算法只能包括加、減、乘、除運算和邏輯運算，這些運算是計算機能直接處理的運算。.第二，有可靠的理論分析，能任意逼近并達到精確要求，對近似算法要保證收斂性和數(shù)值穩(wěn)定性，還要對誤差進行分析。這些都建立在相應(yīng)數(shù)學(xué)理論的基礎(chǔ)上。第三，要有好的計算復(fù)雜性，時間復(fù)雜性好是指節(jié)省時間，空

5、間復(fù)雜性好是指節(jié)省存儲量，這也是建立算法要研究的問題，他關(guān)系到算法能否在計算機上實現(xiàn)。第四，要有數(shù)值試驗，即任何一個算法除了從理論上要滿足上述三點外，還要通過數(shù)值試驗證明是行之有效的。根據(jù)“數(shù)值分析”課程的特點，學(xué)習(xí)是我們首先要注意掌握方法的基本原理和思想，要注意方法處理的技巧及其與計算機的結(jié)合，要重視誤差分析、收斂性及穩(wěn)定性的基本理論；其次，要通過例子，學(xué)習(xí)使用各種數(shù)值方法解決實際計算問題；最后，為了掌握本課的內(nèi)容，還應(yīng)作一定數(shù)量的理論分析與計算練習(xí)。由于本課內(nèi)容包括了微積分、代數(shù)、常微分方程的數(shù)值方法，讀者必須掌握這幾門課的基本內(nèi)容才能學(xué)好這門課。2 數(shù)值計算的誤差2.1 誤差來源與分類我

6、們算出數(shù)學(xué)模型的近似解和一個物理量的真的值往往不相等，它們之差稱為誤差。用電子計算機進行解決實際問題的數(shù)值計算，誤差是不可避免的。引起數(shù)值結(jié)果中的誤差的模型誤差觀測誤差誤差來源計算誤差固有誤差截斷誤差舍入誤差原因是多方面，通常來自固有誤差和計算誤差，如下面所示：模型誤差：用數(shù)學(xué)方法解決實際問題，首先必須建立該問題的數(shù)學(xué)模型。即把實際問題經(jīng)過抽象，忽略一些次要的因素，簡化成一個確定的數(shù)學(xué)問題。數(shù)學(xué)模型只是對實際問題的一種近似、一種粗糙的描述，因而它與實際問題或客觀現(xiàn)象之間必然存在誤差，這種誤差稱為“模型誤差”。這樣的誤差常常是可以忽略不計的。例如在經(jīng)典力學(xué)問題中，我們常常忽略相對論效應(yīng)。但是，如

7、果這種誤差不可忽略，說明數(shù)學(xué)模型選擇得不好。那么不論數(shù)值計算多么精確，其結(jié)果都將存在不可忽略的誤差。觀測誤差：數(shù)學(xué)問題中總包含一些參量（或物理量，如電壓、電流、溫度、長度等），它們的值（輸入數(shù)據(jù)）往往是由觀測得到的。而觀測的誤差是難以避免的，由此產(chǎn)生的誤差稱為“觀測誤差”。由于觀測誤差通常具有隨機的性質(zhì)，所以想用分析的方法來估計它們的影響常常是一件非常困難的事。由于固有誤差的產(chǎn)生往往涉及各專業(yè)知識及實驗手段，所以它不是數(shù)值分析所研究的內(nèi)容。截斷誤差：數(shù)值計算的本質(zhì)就是用有限的過程、離散的數(shù)據(jù)來近似（刻畫）無限的過程、連續(xù)的量。這樣對一些具有連續(xù)量、無限計算量的數(shù)學(xué)問題的求解的過程中，我們不得不

8、對一些連續(xù)的量進行有限的離散化近似，不得截去無限的計算過程，只進行有限次的計算。如求一個收斂的無窮級數(shù)之和，必須截去該級數(shù)后面的無窮多項，而用前面有限項的部分來近似代替，于是產(chǎn)生了有限過程代替無限過程的誤差，稱為“截斷誤差”，這是計算方法本身所出現(xiàn)的誤差，所以也稱為“方法誤差”。例如，當(dāng)很小時，可以用作為近似值。由交錯級數(shù)判斂的萊布尼茲（Leibniz）準(zhǔn)則，它的截斷誤差的絕對值不超過。有限過程代替無限過程的誤差和計算量取決于其方法的收斂性及收斂速度。舍入誤差：計算中遇到的數(shù)據(jù)可能位數(shù)很多或是無窮小數(shù)，如受機器字長的限制，無窮小數(shù)和位數(shù)很多的數(shù)必須舍入成一定的位數(shù)（機器字長）。舍入方法：a)

9、舍入機。采用四舍五入的辦法，如將舍為；b) 截斷機。采用截尾的辦法。如在八位字長的截斷機里取成。這樣產(chǎn)生的誤差稱為“舍入誤差”。少量的舍入誤差是微不足道的，但在計算機是作了成千上萬次運算后，舍入誤差的累積有時可能是十分驚人的。它取決于方法的穩(wěn)定性。如果方法能夠累積大量的誤差，此算法是不穩(wěn)定的，反之為穩(wěn)定算法。如算法1：。顯然是不穩(wěn)定的；算法2：， 研究計算結(jié)果的誤差是否滿足精度要求就是誤差估計問題，本書主要討論算法的截斷誤差與舍入誤差，而截斷誤差將結(jié)合具體算法討論。為分析數(shù)值運算的舍入誤差，先要對誤差基本概念做簡單介紹。2.2 絕對誤差與相對誤差定義1 設(shè)為準(zhǔn)確值，為的一個近似值，稱為近似值的

10、絕對誤差，簡稱誤差。注意這樣定義的誤差可正可負，當(dāng)絕對誤差為正時近似值偏大，叫強（贏）近似值；當(dāng)絕對誤差為負時近似值偏小，叫弱（虧）近似值。通常我們不能算出準(zhǔn)確值，當(dāng)然也不能算出誤差的準(zhǔn)確值，只能根據(jù)測量工具或計算情況估計出誤差的絕對值不超過某正數(shù)，也就是誤差絕對值的一個上界。叫做近似值的誤差限，它總是正數(shù)。一般情形，即。這個不等式有時也表示為。我們把近似值的誤差與準(zhǔn)確值的比值稱為近似值的相對誤差，記作。在實際計算中，由于真值總是不知道的，通常取作為的相對誤差，條件是較小，此時是的平方項級，故可忽略不計。相對誤差也可正可負，它的絕對值上界叫做相對誤差限，記作，即。注1：1）絕對誤差是有量綱的量

11、，它與所研究問題的背景有關(guān)，因此我們不能單單從絕對誤差值的大小來判斷計算結(jié)果的精度，還必須考慮到實際問題的應(yīng)用背景；2）通過引入相對誤差，我們可比較不同算法，不同應(yīng)用問題的計算精度，這一點是無法通過比較絕對誤差做到的，因為不同值的東西，在量上是無法比較的。正如我們不能通過比較兩個商品的使用價值來判定商品的真貴，只能通過抽象的價值。2.3 有效數(shù)字有效數(shù)字是近似值的一種表示法，它既能表示近似值的大小，又能表示其精確程度。定義2 若近似值的誤差限是某一位的半個單位，該位到的第一位非零數(shù)字共有位，則稱近似值有位有效數(shù)字。在科學(xué)記數(shù)法中，將近似值寫成規(guī)格化形式為 (1-1)其中為整數(shù)，為0到9之間的整

12、數(shù)。按照定義2，近似值有位有效數(shù)字當(dāng)且僅當(dāng) (1-2)因此在相同的情形下，越大則誤差越小，亦即一個近似值的有效位數(shù)越多其誤差限越小。例1 按四舍五入原則寫出下列各數(shù)具有5位有效數(shù)字的近似數(shù):187.9325,0., 8., 2.。按定義，上述各數(shù)具有5位有效數(shù)字的近似數(shù)分別是187.93, 0., 8.0000, 2.7183注意的5位有效數(shù)字的近似數(shù)是8.0000而不是8，因為8只有1位有效數(shù)字。例2 重力常數(shù)，如果以為單位，；若以為單位，它們都具有3位有效數(shù)字，因為按第一種寫法，按第二種寫法，他們雖然寫法不同，但都具有3位有效數(shù)字。至于絕對誤差限，由于單位不同結(jié)果也不同，而相對誤差都是。例

13、2說明有效位數(shù)與小數(shù)點后有多少位數(shù)有關(guān)。然而，從(2-2)可以得到具有位有效數(shù)字的近似數(shù)，其絕對誤差限為，在相同的情況下，越大則越小，故有效位數(shù)越多，絕對誤差限越小。關(guān)于一個近似數(shù)的有效位數(shù)與其相對誤差的關(guān)系，有下面的定理定理1.1 設(shè)近似數(shù)具有規(guī)格化形式(1-1)，(1)若具有位有效數(shù)字，則其相對誤差限為 (1-3)(2) 如果 (1-4)則至少具有位有效數(shù)字。證明 由(1-1)可得到當(dāng)有位有效數(shù)字時即證(1)。反之，由即說明具有位有效數(shù)字，(2)得證。定理說明，有效位數(shù)越多，相對誤差限越少。例3 要使的近似值的相對誤差限小于0.1%，要取幾位有效數(shù)字？設(shè)取位有效數(shù)字，由定理1.1，。由于，

14、知，故只要取，就有即只要對的近似值取4位有效數(shù)字，其相對誤差就小于0.1%。此時由開方表得。3 數(shù)值計算中誤差的傳播3.1 基本運算中的誤差估計數(shù)值運算中誤差傳播情況比較復(fù)雜，估計起來比較困難。本節(jié)所討論的運算是四則運算與一些常用函數(shù)的計算。由微分學(xué)，當(dāng)自變量改變（誤差）很小時，函數(shù)的微分作為函數(shù)的改變量的主要線性部分可以近似函數(shù)的改變量，故可以利用微分運算公式可導(dǎo)出誤差運算公式。設(shè)數(shù)值計算中求得的解與參量（原始數(shù)據(jù)）有關(guān)，記為參量的誤差必然引起解的誤差。設(shè)的近似值分別為，相應(yīng)的解為假設(shè)在點可微，則當(dāng)數(shù)據(jù)誤差較小時，解的絕對誤差為(1-5)其相對誤差為(1-6)注2：函數(shù)值的絕對誤差等于函數(shù)的

15、全微分，自變量的微分即為自變量的誤差；函數(shù)值的相對誤差等于函數(shù)的對數(shù)的全微分。將式(1-5)及(1-6)中的和分別換成誤差限和，求和的各項變成絕對值。特別地，由式(1-5)及(1-6)可得和、差、積、商之誤差及相對誤差公式 (1-7) (1-8)由以上的式(1-7)及(1-8)可得出 (1-9)因此，和、差的誤差限不超過各數(shù)的誤差限之和，積、商的相對誤差限不超過各數(shù)的相對誤差限之和。例4 設(shè)，求的相對誤差與的相對誤差之間的關(guān)系。解 由式(1-9)得所以的相對誤差是的相對誤差的倍，特別地，的相對誤差是的相對誤差的一半。例5 設(shè)，的相對誤差為，求的絕對誤差。解 由于，即，所以例6 已測得某場地長為

16、的值為寬的值為已知，試求面積的絕對誤差與相對誤差。解 因由(1-5)知其中，而于是絕對誤差限相對誤差限3.2 誤差定性分析數(shù)值運算中的誤差分析是一個很重要而復(fù)雜的問題，上節(jié)討論了不精確數(shù)據(jù)運算結(jié)果的誤差限，他只適用于簡單情形，然而一個工程或科學(xué)計算問題往往要運算千萬次，由于每步運算都有誤差，如果每步都做誤差分析是不可能的，也不科學(xué)，因為誤差積累有正有負，絕對值有大有小，都按最壞情況估計誤差限得到的結(jié)果比實際誤差大得多，這種保守的誤差估計不反映實際誤差積累。考慮到誤差分布的隨機性，有人用概率統(tǒng)計方法，將數(shù)據(jù)和運算中的舍入誤差視為適合某種分布的隨機變量，然后確定計算結(jié)果的誤差分布，這樣得到的誤差估

17、計更能接近實際，這種方法稱為概率分析法。20世紀60年代以后對舍入誤差分析提出了一些新的方法，較重要的有以下兩種：1.向后誤差分析法是把新算出的量由某個公式表達，它僅含基本的算術(shù)運算，如假定是前面已算出的量或原始數(shù)據(jù)，新算出量若的攝動為，使得由浮點運算得出結(jié)果為則可根據(jù)的界由攝動理論估計最后舍入誤差的界，威克遜（Wilkinson）將這種方法應(yīng)用于數(shù)值代數(shù)（矩陣運算）的誤差分析，取得較好的效果。2.區(qū)間分析法是把參加運算的數(shù)都看成區(qū)間量根據(jù)區(qū)間運算規(guī)則求得最后結(jié)果的近似值及誤差限。例如，的近似數(shù)為，由于則若計算（*為運算符號），由 ,則為所求近似值，而則為誤差限。上面簡略介紹了誤差分析的幾種方

18、法，但都不是十分有效的，目前尚無有效的方法對誤差作出定量估計。為了確保數(shù)值計算結(jié)果的正確性，首先需對數(shù)值計算問題作出定性分析，為此本節(jié)討論以下三個問題。3.3 病態(tài)問題與條件數(shù)對一個數(shù)值問題本身如果輸入數(shù)據(jù)又微小擾動（即誤差），導(dǎo)致輸出數(shù)據(jù)（即問題解）相對誤差很大，這就是病態(tài)問題，例如計算函數(shù)值時，若有擾動，其相對誤差為，函數(shù)值的相對誤差為。相對誤差比值 (1-10)稱為計算函數(shù)值問題的條件數(shù)。自變量相對誤差一般不會太大，如果條件數(shù)很大，將引起函數(shù)值相對誤差很大，出現(xiàn)這種情況的問題就是病態(tài)問題。例如，則有，他表示相對誤差可能放大倍。如，有，若取自變量相對誤差為2%，函數(shù)值相對誤差為24%，這是

19、問題可以認為是病態(tài)的。一般情況條件數(shù)就認為是病態(tài)的，越大病態(tài)越嚴重。其他計算問題也要分析是否病態(tài)。例如解線性方程組，如果輸入數(shù)據(jù)有微小誤差引起解的巨大誤差，就認為是病態(tài)方程組，我們將在第5章用矩陣的條件數(shù)來分析這種現(xiàn)象。3.4 算法的數(shù)值穩(wěn)定性數(shù)值運算的誤差分析是個很重要而復(fù)雜的問題，對于一個工程或科學(xué)計算問題往往要運算千萬次，由于幾乎每一步運算都會產(chǎn)生誤差，如果每步都做誤差分析是不可能的，也不科學(xué)，因為誤差累積有正有負，絕對值有大有小，很可能有一部分相互抵消。如果每一步都按最壞情況估計誤差不反映實際情況。近年來，雖然發(fā)展起來一些新的誤差估計辦法，如概論統(tǒng)計法，事后誤差估計法及區(qū)間分析法等等。

20、但這些方法目前也僅僅在特定的一些問題上取得了較為滿意的結(jié)果，還正在發(fā)展中。對于計算步驟較多的算法，一般不宜采用上述的一些定量估計 的辦法。而是采用定性分析的辦法，即討論算法的數(shù)值穩(wěn)定性。定義3 一個算法如果輸入數(shù)據(jù)有誤差，而在計算過程中舍入誤差得到控制，則稱此算法是數(shù)值穩(wěn)定的，否則稱此算法是不穩(wěn)定的。在一種算法中，如果某一步有了絕對值為的誤差，而以后各步計算都準(zhǔn)確地進行，僅由所引起的誤差的絕對值，始終不超過，就說算法是穩(wěn)定的。對于數(shù)值穩(wěn)定性的算法，不用做具體的誤差估計，就認為其結(jié)果是可靠的。而數(shù)值不穩(wěn)定的算法盡量不要使用。例7 計算并估計誤差。由分部積分可得計算的遞推公式 (1-11)若計算出

21、，代入(1-11)，可逐次求出的值。要算出就要先計算，若用泰勒多項式展開部分和，并取，用4位小數(shù)計算，則得，截斷誤差。計算過程中小數(shù)點后第5位的數(shù)字按四舍五入原則舍入，由此產(chǎn)生的舍入誤差這里先不討論。當(dāng)初始值取為時，用(1-11)遞推的計算公式為（A） 。計算結(jié)果見表1-1的列。用近似產(chǎn)生的誤差就是初始誤差，它對后面計算結(jié)果是有影響的。表1-1(用(A)算)(用(B)算)(用(A)算)(用(B)算)012340.63210.36790.26420.20740.17040.63210.36790.26430.20730.1708567890.1480 0.1120 0.2160 -0.7280

22、7.552 0.14550.12680.11210.10350.0684從表中可以看到出現(xiàn)負值，這與一切相矛盾。實際上，有積分估值得 (1-12)因此，當(dāng)較大時，用近似顯然是不正確的。這里的計算公式與每步計算都是正確的，那么是什么原因使計算結(jié)果錯誤呢？主要就是初值有誤差，由此引起以后各步計算的誤差滿足關(guān)系 容易推得，由此看出：誤差導(dǎo)致第步的誤差擴大倍，當(dāng)較大時，誤差將淹沒真值，因此用近似顯然是不正確的，這種遞推公式不宜采用。例如，若，則這就說明完全不能近似了。它表明公式(A)是數(shù)值不穩(wěn)定的?，F(xiàn)在換一種計算方法。由(1-12)取，有我們粗略取，然后將公式(1-11)倒過來算，即由算出公式為（B）

23、 計算結(jié)果見表1-1的列。我們發(fā)現(xiàn)與的誤差不超過。記，則，比縮小了倍，因此，盡管較大，但由于誤差逐步縮小，故可用近似。反之，當(dāng)用方案(A)計算時，盡管初值相當(dāng)準(zhǔn)確，由于誤差傳播是逐步擴大的，因而計算結(jié)果不可靠。此例說明，數(shù)值不穩(wěn)定的算法是不能使用的。在例7中，算法(B)使數(shù)值穩(wěn)定的，而算法(A)是不穩(wěn)定的。數(shù)值不穩(wěn)定現(xiàn)象屬于誤差危害現(xiàn)象，如何防止誤差危害下面將進一步討論。4 數(shù)值計算中應(yīng)注意的幾個問題數(shù)值計算中首先要分清問題是否病態(tài)和算法是否數(shù)值穩(wěn)定，計算時還應(yīng)盡量避免誤差危害，防止有效數(shù)字的損失，下面給出若干原則：1 要避免除數(shù)絕對值遠遠小于被除數(shù)絕對值的除法。因為故當(dāng)時，舍入誤差可能增大很多。例8 線性方程組的準(zhǔn)確解為現(xiàn)在四位浮點十進制數(shù)（仿機器實際計算）下用消去法求解，上述方程寫成若用除第一方程減第二方程，則出現(xiàn)用小的數(shù)除大的數(shù)，得到由此解出87顯然嚴重失真。若反過來用第二個方程消去第一個方程中含的項，則避免了大數(shù)被小數(shù)除，得到由此求的相當(dāng)好的近似解。2 要避免兩相近數(shù)相減兩數(shù)之差的相對誤差為當(dāng)與很接近時，的相對誤差會很大，有效數(shù)字位數(shù)將嚴重丟失。例如，都具有五位有效數(shù)字，但只有兩位有效數(shù)字。這說明必須盡量避免出現(xiàn)這類運算。最好是改變計算方法，防止這種現(xiàn)象產(chǎn)生。先舉例說明。例9 求的根。解 ，只有一位有效數(shù)字。若改用具有3位有效數(shù)字。例10 計算（用四位數(shù)學(xué)用表）