數(shù)值計算方法講義第一章預(yù)篇

1、前言由于計算機(jī)的普及，科學(xué)計算已成為各學(xué)科領(lǐng)域的一項重要工作。學(xué)習(xí)和掌握數(shù)值計算方法的基本原理及應(yīng)用已成為現(xiàn)代科學(xué)工作者不可缺少的一個環(huán)節(jié)。用計算機(jī)解決科學(xué)計算問題需經(jīng)歷幾個過程：由實際問題建立數(shù)學(xué)模型，根據(jù)數(shù)學(xué)模型提出求解的數(shù)值計算方法，編出程序、上機(jī)求出結(jié)果。通過以上過程，可以看出，數(shù)值計算方法是計算機(jī)、數(shù)學(xué)和應(yīng)用科學(xué)之間的橋梁，是程序設(shè)計和對數(shù)值結(jié)果進(jìn)行分析的依據(jù)，是用計算機(jī)進(jìn)行科學(xué)計算全過程的一個重要環(huán)節(jié)。目前，數(shù)值計算方法已經(jīng)成為理工科院校（非數(shù)學(xué)專業(yè)）碩士學(xué)位研究生的學(xué)位課。在農(nóng)業(yè)科學(xué)研究中，數(shù)值計算方法已經(jīng)成為不可缺少的有力工具。學(xué)生通過本課程的學(xué)習(xí)，能掌握科學(xué)計算中常用的算法，

2、能獨(dú)立地用學(xué)過的算法編程，測試。并能解決工作中遇到的實際問題。本教材同時也適當(dāng)增加一些只供閱讀，而不在課堂教授的內(nèi)容，這樣在規(guī)定的課時內(nèi)可完成基本內(nèi)容的講授，又可以作為今后科研的參考書。各章節(jié)要點(diǎn)及授課時數(shù)本教材的特點(diǎn)：對現(xiàn)有的已知的數(shù)學(xué)模型建立起相應(yīng)的一系列數(shù)值求解方法，力求設(shè)計計算量小、存儲量少、精度高，特別是計算機(jī)所能接受且執(zhí)行計算方法，兼顧分析方法的收斂性、穩(wěn)定性及誤差估計。在不失科學(xué)性的前提下，盡量做到深入淺出地介紹計算機(jī)上常用的數(shù)值方法，使學(xué)生能用數(shù)值計算方法對建立的數(shù)學(xué)模型實際求解。本教材既堅持介紹數(shù)值計算方法基本原理，又兼顧應(yīng)用學(xué)科的特點(diǎn)，這是現(xiàn)有教材所不具備的。使用范圍：理工

3、科非數(shù)學(xué)學(xué)科公共專業(yè)課教材。本教材主要介紹計算機(jī)上常用的各種數(shù)值計算方法以及相關(guān)的基本概念及理論。內(nèi)容包括誤差分析初步，方程求根，線性方程組的直接解法與迭代法，插值法，最小二乘曲線擬合，數(shù)值積分計算，常微分方程數(shù)值解法和偏微分方程數(shù)值解法。本課程中對主要基本算法的推導(dǎo)、構(gòu)造原理、收斂性、誤差估計進(jìn)行了討論。本教材的另一個特色是側(cè)重于計算機(jī)應(yīng)用，各章均有例題及數(shù)值算例，并指出應(yīng)掌握的基本問題，對每一個算法都給出偽代碼，以便于學(xué)生編制程序的需要，且有適當(dāng)?shù)臅婢毩?xí)及一些上機(jī)計算題。本教材可作為理工科（非計算數(shù)學(xué)）各專業(yè)研究生及大學(xué)本科高年級的數(shù)值計算方法教材，也可供工程技術(shù)人員參考。作者從事碩士研

4、究生學(xué)位課數(shù)值計算方法教學(xué)已經(jīng)30余年，在多年的教學(xué)中發(fā)現(xiàn)給農(nóng)業(yè)院校的學(xué)生尋找一本合適的教材很難。一方面，和其它理工科院校的學(xué)生相比，農(nóng)業(yè)院校的學(xué)生數(shù)學(xué)基礎(chǔ)課學(xué)得不夠，因此需要淺顯易懂的教材；另一方面，農(nóng)業(yè)科學(xué)的發(fā)展，對數(shù)學(xué)和計算科學(xué)提出了很高的要求，因為農(nóng)業(yè)科學(xué)的復(fù)雜性和不確定性，需要有盡可能多的內(nèi)容和深度，這樣互相矛盾的需求給講課教師提出了很高的要求，教師要深入的理解數(shù)值計算的理念，要有深厚的計算數(shù)學(xué)理論知識和計算經(jīng)驗才能講好這門課。在學(xué)習(xí)了許多國內(nèi)外教材的基礎(chǔ)上，根據(jù)農(nóng)業(yè)院校學(xué)生的特殊要求，作者于1984年編寫了數(shù)值計算方法講稿，每年都有小的改動，在1993年、1999年、2005年和2

5、009年對講稿進(jìn)行了幾次較大的修改，以適應(yīng)科學(xué)發(fā)展需要和農(nóng)大學(xué)生的基礎(chǔ)。許多研究生通過學(xué)習(xí)，在畢業(yè)論文中引用了數(shù)值計算方法解決應(yīng)用問題，提高了論文水平，也有許多在職教師和科研人員學(xué)習(xí)這門課程后，將數(shù)值方法引用到科研課題中，取得了較好的成果。目錄第一章 預(yù)篇 1.1 數(shù)值計算方法的研究對象和特點(diǎn) 1.2 誤差分析 1.3 算法的概述第二章 非線性方程求根 2.1 二分法 2.2 迭代法的一般原則 2.3 牛頓法(切線法) 2.4 弦截法第三章 解線性方程組的直接法 3.1 Gauss 消去法 3.2 矩陣的三角分解及其在解方程組中的應(yīng)用 3.3 解對稱正定矩陣方程組的平方根解法 3.4 解三對角

6、方程組的追趕法 3.5 向量和矩陣的范數(shù) 3.6 方程組的性態(tài)、條件數(shù)第四章 解線性方程組的迭代法 4.1 Jacobi 迭代法 4.2 Gauss-Seidel 4.3 SQR 方法 4.4 迭代法的收斂性 4.5 共軛梯度法 4.6 最小二乘法第五章 矩陣特征值問題的計算方法 5.1 矩陣特征值問題 5.2 乘冪法和反冪法 5.3 Household方法 5.4 QR方法第六章 函數(shù)插值 6.1 Lagrange 插值 6.2 Newton 插值 6.3 等距節(jié)點(diǎn)的插值 6.4 Hermite 插值6.5分段低次多項式插值 6.6 三次樣條插值第七章 最佳平方逼近 7.1 正交多項式 7.

7、2 切比雪夫多項式 7.3 曲線擬合的最小二乘法第八章 數(shù)值積分 8.1 Newton-Cotes 求積公式 8.2 Romberg 求積公式 8.3 Gauss 型求積公式第九章 常微分方程數(shù)值解 9.1 Euler 法和改進(jìn) Euler 法 9.2 Runge-Kutta 法 9.3 線性多步法 9.4 解二階常微分方程邊值問題的差分法第十章 偏微分方程數(shù)值解 10.1 橢圓型方程差分法 10.2 拋物型方程差分法 10.3 雙曲型方程差分法 10.4 有限元方法初步第一章 預(yù)篇數(shù)學(xué)是研究數(shù)與形的科學(xué)。其中研究怎樣利用手指、算盤、計算尺、計算器、計算機(jī)等工具，來求出數(shù)學(xué)問題數(shù)值解的學(xué)問，就

8、是數(shù)值計算方法。它是數(shù)學(xué)中最古老的部分，但只是在計算機(jī)出現(xiàn)以后，人們獲得了高速度、自動化的計算工具，才為眾多浩繁的數(shù)值問題的解決展現(xiàn)了光明的前景。從此，科學(xué)研究與工程設(shè)計的手段，發(fā)生了由模型試驗向數(shù)值計算的巨大轉(zhuǎn)變。近年來，由于計算機(jī)的發(fā)展，計算性的學(xué)科新分支，如計算力學(xué)、計算物理、計算化學(xué)、計算生物學(xué)、計算地質(zhì)學(xué)、計算經(jīng)濟(jì)學(xué)以及眾多工程科學(xué)的計算分支紛紛興起。因為任何具體學(xué)科中的計算過程，不論其目的、背景和含義如何，終歸是數(shù)學(xué)的計算過程，數(shù)值計算方法是各種計算性學(xué)科的聯(lián)系紐帶和共性基礎(chǔ)。學(xué)習(xí)數(shù)值計算方法可以知道如何用計算機(jī)解決數(shù)學(xué)問題，特別是我們在微積分和線性代數(shù)中沒有學(xué)過的一些解決問題的方

9、法，還介紹一些用不同的方法解決以前用傳統(tǒng)的數(shù)學(xué)方法解決的問題。我們選擇一些現(xiàn)實世界存在的例子，用解析的方法能夠解出來，以便將數(shù)值方法和解析方法做一個對比。1.1 數(shù)值計算方法的起源和意義計算方法是數(shù)學(xué)的一個古老的分支，雖然數(shù)學(xué)不僅僅是計算，但推動數(shù)學(xué)產(chǎn)生和發(fā)展的最直接原因還是計算問題。人類社會發(fā)展的初期，就常常遇到各種各樣的計算問題。一開始沒有任何計算工具，最得心應(yīng)手的就是人類的一雙手了。于是人們采取了扳手指頭和結(jié)繩計數(shù)的方法進(jìn)行計算。隨著社會的進(jìn)一步向前發(fā)展，問題越來越復(fù)雜，原始的工具不敷使用。人們越來越迫切地希望有更先進(jìn)的技術(shù)和理論來進(jìn)行計算，于是數(shù)學(xué)應(yīng)運(yùn)而生?？梢赃@么說，記數(shù)術(shù)是最原始的

10、數(shù)學(xué)，數(shù)學(xué)的源頭就是計算，計算自古以來就是數(shù)學(xué)的一個重要組成部分。中國古代數(shù)學(xué)曾經(jīng)有過輝煌的成就，它不像古希臘數(shù)學(xué)那樣注重邏輯和推理，而是具有顯著的計算性和實用性的特點(diǎn)，從九章算術(shù)等中國古典數(shù)學(xué)名著中就可以看出這一點(diǎn)。早在商代中國就形成了十進(jìn)制這一方便的計數(shù)和運(yùn)算機(jī)制。從最早發(fā)明的算籌到后來的算盤以及相應(yīng)發(fā)展起來的珠算方法，是古代中國對世界計算技術(shù)的最重要貢獻(xiàn)，至今還在中國和其他一些國家都發(fā)揮著作用。到了二十世紀(jì)四十年代，生產(chǎn)高性能計算工具的技術(shù)條件已經(jīng)成熟。當(dāng)時適逢第二次世界大戰(zhàn)，軍事上對高速計算機(jī)有迫切的需求。這就迎來了世界上第一臺電子計算機(jī)的誕生。計算機(jī)的問世，從根本上改變了計算工具落后

11、的局面。古老的計算數(shù)學(xué)借助計算機(jī)這一強(qiáng)有力的工具，一下子換發(fā)出了青春。隨著計算技術(shù)的發(fā)展，社會需求的急劇增加，計算數(shù)學(xué)的應(yīng)用領(lǐng)域越來越廣泛，這就使得越來越多的、以前不能設(shè)想的、難度和規(guī)模日益增大的計算問題得以解決。在這樣新的條件下，計算在整個科學(xué)技術(shù)以至經(jīng)濟(jì)生活中的重要性得到前所未有的提高；同時，以原來分散在數(shù)學(xué)各分支的計算方法為基礎(chǔ)的一門新的數(shù)學(xué)科學(xué)開始形成并迅速發(fā)展。計算數(shù)學(xué)和計算機(jī)一起已經(jīng)成為眾多領(lǐng)域研究工作中不可或缺的工具和手段。當(dāng)代計算能力的大幅度提高既來自計算機(jī)的進(jìn)步，也來自計算方法的進(jìn)步。計算機(jī)和計算方法的發(fā)展是相輔相成，相互制約和相互促進(jìn)的。計算方法的發(fā)展啟發(fā)了新的計算機(jī)體系結(jié)

12、構(gòu)，而計算機(jī)的更新?lián)Q代也對計算方法提出了新的標(biāo)準(zhǔn)和要求。自計算機(jī)誕生以來，經(jīng)典的計算方法業(yè)已經(jīng)歷了一個重新評價、篩選、改造和創(chuàng)新的過程；與此同時，涌現(xiàn)了許多新概念、新課題和許多能夠充分發(fā)揮計算機(jī)潛力、有更大解題能力的新方法；這就構(gòu)成了現(xiàn)代意義下的計算數(shù)學(xué)（數(shù)值計算方法）。1.2 數(shù)值計算方法的研究對象科學(xué)計算問題的出發(fā)點(diǎn)，往往是研究現(xiàn)實世界中的問題或現(xiàn)象。例如：物理、自然或者社會問題。在一定的假設(shè)下，可以將這些實際問題列成方程，也就是數(shù)學(xué)模型來描述或進(jìn)行分析。從簡單的代數(shù)方程到復(fù)雜的非線性偏微分方程應(yīng)有盡有。這些方程一旦建立起來，下一步就是要解方程，以預(yù)測這些現(xiàn)象將來朝什么方向發(fā)展。為了獲取數(shù)

13、據(jù)，我們也需要做一些實驗。如果模型預(yù)測的結(jié)果和實測數(shù)據(jù)一致或接近，就認(rèn)為所建立的模型是合適的，否則就要對所建立的模型加以調(diào)整和改進(jìn)。在求解階段，最理想的狀況是求出方程的解析解，遺憾的是，僅對最簡單的模型才能求出解析解。我們通過幾個例子來說明在微積分和線性代數(shù)中學(xué)過的數(shù)學(xué)模型而在這兩門課程中所沒有學(xué)到可行的解法。例1.1求解線性方程組AX=b，其中系數(shù)矩陣A是的方陣，設(shè)n = 20；解：本例的行列式。按照Gramer法則，此方程的解為：。如解n階方程組，要計算n + 1個n階行列式的值，每個行列式按Laplace 展開計算，總共需要做（n+1）n! 次乘法運(yùn)算。本題n=20, 需要進(jìn)行以上的乘法

14、運(yùn)算。設(shè)用每秒可做一億次乘法的計算機(jī)，一年可以做次乘法。所以在此計算機(jī)上用Gramer法則解20階的線性方程組，需要的時間在萬年以上。這當(dāng)然是沒有實際意義的。例1.2求超越方程 和的根例1.3 不用計算器，求的近似值。x149123例 1.4 計算定積分例1.5在7塊并排、形狀大小相同的試驗田上施化肥對水稻產(chǎn)量影響的試驗，得到如下表所示的一組數(shù)據(jù)（單位：kg） 施化肥量 x 15202530354045水稻產(chǎn)量 Y330345365405445450455求施肥和產(chǎn)量的關(guān)系。例1.6 研究對象是連續(xù)的，我們只能了解到其有限個數(shù)據(jù)溫度的變化，時間是連續(xù)的，溫度是時間的函數(shù)，如何畫出溫度的曲線圖？

15、大量的根據(jù)實際問題所建立的模型只能求出近似解，也就是用“逼近”技術(shù)求出問題的解。本書的目的就是設(shè)計一些算法，對可以用數(shù)學(xué)模型描述的現(xiàn)實世界的現(xiàn)象求出近似解（數(shù)值解）。用計算機(jī)解決科學(xué)計算問題需經(jīng)歷幾個過程：由實際問題建立數(shù)學(xué)模型，根據(jù)數(shù)學(xué)模型提出求解的數(shù)值計算方法，編出程序，上機(jī)求出結(jié)果。通過以上過程，可以看出：數(shù)值計算方法是計算機(jī)、數(shù)學(xué)和應(yīng)用科學(xué)之間的橋梁，是程序設(shè)計對數(shù)值結(jié)果進(jìn)行分析的依據(jù)，是用計算機(jī)進(jìn)行科學(xué)計算全過程的一個重要環(huán)節(jié)。計算機(jī)實質(zhì)上只會做加減乘除等基本運(yùn)算。研究怎樣通過計算機(jī)所執(zhí)行的基本運(yùn)算，求得各類問題的數(shù)值解或近似數(shù)值解，就是計算數(shù)學(xué)的根本課題。數(shù)值計算方法的研究對象：數(shù)

16、值計算方法主要研究適合于在計算機(jī)上使用的計算方法以及與此相關(guān)的理論，包括方法的收斂性、穩(wěn)定性及誤差分析。還要根據(jù)計算機(jī)的特點(diǎn)研究時間最短、需要計算機(jī)內(nèi)存最少的計算方法。1.3 算法 算法的定義：解決問題的一系列有序的步驟。描述算法可以有不同的方式。例如，可以用日常語言和數(shù)學(xué)語言加以敘述，也可以借助形式語言（算法語言）給出精確的說明，也可以用框圖直觀地顯示算法的全貌。下面舉個簡單的例子。例1.7：求解二元一次聯(lián)立方程組這個方程組的行列式解法可表述如下：首先判別是否為零，存在兩種可能：（1）如果，則令計算機(jī)計算，輸出計算的結(jié)果x1，x2。（2）如果D=0，則或是無解，或有無窮多組解，這是奇異的情形

17、。下面用框圖（也稱流程圖）來形象地描述上面的算法。開 始輸 入D=a11a22-a12a21D=0 Y N輸出無解信息輸出 x1, x2結(jié) 束圖 1.1 框圖這里我們使用了兩種形式的框，一種是矩形框 ，稱為敘述框，計算公式就填在這種框內(nèi)；另一種是棱形框 ，稱為判斷框，表示算法的判斷檢查部分。1.4數(shù)值計算中的誤差用數(shù)值方法解決科學(xué)研究或工程技術(shù)中的實際問題，一般來說，產(chǎn)生誤差是不可避免的，根本不存在絕對的嚴(yán)格和精確。但是我們可以認(rèn)識誤差，從而控制誤差，使之局限于最小（或盡量?。┑姆秶鷥?nèi)。1.4.1 誤差的來源運(yùn)用數(shù)學(xué)工具解決實際問題，可能產(chǎn)生的誤差主要有以下幾類。1描述誤差在將實際問題轉(zhuǎn)化為數(shù)

18、學(xué)模型的過程中，為了使數(shù)學(xué)模型盡量簡單，以便于分析或計算，往往要忽略一些次要的因素，進(jìn)行合理的簡化。這樣，實際問題與數(shù)學(xué)模型之間就產(chǎn)生了誤差，這種誤差稱為描述誤差。由于這類誤差難于作定量分析，所以在計算方法中，總是假定所研究的數(shù)學(xué)模型是合理的，對描述誤差不作深入的討論。2觀測誤差在數(shù)學(xué)模型中，一般都含有從觀測（或?qū)嶒灒┑玫降臄?shù)據(jù)，如溫度、時間、速度、距離、電流、電壓等等。但由于儀器本身的精度有限或某些偶然的客觀因素會引入一定的誤差，這類誤差叫做觀測誤差。通常根據(jù)測量工具或儀器本身的精度，可以知道這類誤差的上限值，所以無須在計算方法課程中作過多的研究。3截斷誤差在數(shù)值計算中，常用收斂的無窮級數(shù)的

19、前幾項來代替無窮級數(shù)進(jìn)行計算。如（1.5）當(dāng)很小時，可以?。?.5）的前兩項來近似代替的計算，即 （很小時）（1.6）由泰勒定理可知，這時與的誤差是（1.7）在計算中被拋棄了，這類誤差叫做截斷誤差。截斷誤差的大小，直接影響數(shù)值計算的精度，所以它是數(shù)值計算中必須十分重視的一類誤差。4舍入誤差無論用計算機(jī)、計算器計算還是筆算，都只能用有限位小數(shù)來代替無窮小數(shù)或用位數(shù)較少的小數(shù)來代替位數(shù)較多的有限小數(shù)，如：p = 3.1415926x = 8.123456經(jīng)四舍五入后取含小數(shù)點(diǎn)后四位數(shù)字的數(shù)來表示它們時，便有誤差這類誤差叫做舍入誤差。當(dāng)然，計算過程中，這類誤差往往是有舍有入的，而且單從一次的舍入誤差

20、來看也許不算大，但數(shù)值計算中，往往要進(jìn)行成千上萬次四則運(yùn)算，因而就會有成千上萬個舍入誤差產(chǎn)生，這些誤差一經(jīng)迭加或傳遞，對精度可能有較大的影響。所以，作數(shù)值計算時，對舍入誤差應(yīng)予以足夠的重視。顯然，上述四類誤差都會影響計算結(jié)果的準(zhǔn)確性，但描述誤差和觀測誤差往往是計算工作者不能獨(dú)立解決的，是需要與各有關(guān)學(xué)科的科學(xué)工作者共同研究的問題，因此，在計算方法課程中，主要研究截斷誤差和舍入誤差（包括初始數(shù)據(jù)的誤差）對計算結(jié)果的影響。1.4.2 絕對誤差、相對誤差和有效數(shù)字在不同的場合下，表示近似數(shù)精確度的方法各有不同，下面將介紹數(shù)值運(yùn)算誤差的基本概念。1絕對誤差與絕對誤差限定義1：設(shè)x是準(zhǔn)確值，x*是x的一

21、個近似值，稱 （1.8）是近似值x*的絕對誤差，簡稱為誤差。由于準(zhǔn)確值x往往是未知的，因此也無法求出絕對誤差e(x)是多少，但實際問題往往可以估計出絕對誤差的一個上界。定義2：若已知 ，使 （1.9）則稱 近似值x*的絕對誤差限，簡稱為誤差限。對一般情況，即有時也表示為絕對誤差的大小，在許多情況下還不能完全刻劃一個近似值的準(zhǔn)確程度，例如測量1000米和1米兩個長度，若它們的絕對誤差都是1厘米，顯然前者的測量比較準(zhǔn)確。由此可見，決定一個量的近似值的精確度，除了考慮絕對誤差的大小外，還需考慮該量本身的大小，為此引入相對誤差的概念。2相對誤差和相對誤差限定義3：稱近似值x*的誤差e(x)與準(zhǔn)確值x的

22、比值 （1.10）為近似值x*的相對誤差，記作，（在實際計算時，（1.10）式中的x通常用近似值x*代替）。類似定義2，有定義4 相對誤差的上界，稱為相對誤差限，即 （1.11）3有效數(shù)字眾所周知，當(dāng)準(zhǔn)確數(shù)x有很多位數(shù)時，常常按“四舍五入”的原則去得到x的近似數(shù)。例如p = 3.1415926按舍入原則，若取4位小數(shù)得p = 3.1416，取5位則有p = 3.14159。用有效數(shù)字這個概念來表示一個近似數(shù)的準(zhǔn)確程度，其定義為定義5：如果 （1.12）則說x*近似表示x 準(zhǔn)確到小數(shù)后第n位，并從這第n位起直到最左邊的非零數(shù)字之間的一切數(shù)字都稱為有效數(shù)字，并把有效數(shù)字的位數(shù)稱為有效位數(shù)。由上述定

23、義有效數(shù)位為3位有效數(shù)位為5位 有效數(shù)位為4位近似值的有效數(shù)字位數(shù)越多，近似程度就越好。絕對誤差、相對誤差及有效數(shù)字都是反映誤差或近似程度的量，它們相互之間存在某些關(guān)系。定義4 描述了絕對誤差限與相對誤差限的關(guān)系，下面的定義6 表明有效數(shù)字與絕對誤差限的關(guān)系。定義6：若將準(zhǔn)確值x 的近似值x*表示成標(biāo)準(zhǔn)形式 （1.13）而其誤差限 （1.14）則說近似值x*具有n 位有效數(shù)字。這里n 為正整數(shù)，m 為整數(shù)，每個均為0,1，9中的一個數(shù)字，。 例1.8 若x*=3587.64是x 的具有6位有效數(shù)字的近似值，求誤差限。解 將x*按（1.13）式寫成標(biāo)準(zhǔn)形式于是，在定義6 中 m=4，n=6 下面

24、討論有效數(shù)字和相對誤差限的關(guān)系。定理1.1：若x*具有n位有效數(shù)字，則其相對誤差滿足 （1.15）反之，若x*的相對誤差滿足 （1.16）則近似值x* 至少具有n位有效數(shù)字。證明若具有n位有效數(shù)字，由定義6,相對誤差由于所以反之，若（1.16）成立，利用得根據(jù)定義6，x* 至少具有n位有效數(shù)字。例1.9：x*=2.71828， ，求相對誤差限。解：因為：x*=2.71828=0.271828×101，由，n=6，由定理1前一部分，有例1.10要使的近似值的相對誤差小于0.1%，應(yīng)取幾位有效數(shù)字？解：由于，可確定，若相對誤差限利用則有效數(shù)字位數(shù)n應(yīng)滿足不等式解出n=4，即應(yīng)有4位有效數(shù)

25、字。1.5數(shù)值計算中應(yīng)該注意的一些原則由上述討論可知,誤差分析在數(shù)值計算中是一個很重要又很復(fù)雜的問題。因為在數(shù)值計算中每一步運(yùn)算都可能產(chǎn)生誤差，而一個科學(xué)計算問題的解決，往往要經(jīng)過成千上萬次運(yùn)算，如果每一步運(yùn)算都分析誤差，顯然是不可能的，其實也是不必要的。人們經(jīng)常通過對誤差的某傳播規(guī)律的分析，指出在數(shù)值計算中應(yīng)該注意的一些原則，有助于鑒別計算結(jié)果的可靠性并防止誤差危害現(xiàn)象的產(chǎn)生，下面我們給出在數(shù)值計算中應(yīng)該注意的一些原則。1.5.1要使用數(shù)值穩(wěn)定的算法 所謂算法，就是給定一些數(shù)據(jù)，按著某種規(guī)定的次序進(jìn)行計算的一個運(yùn)算序列。它是一個近似的計算過程，我們選擇一個算法，主要要求它的計算結(jié)果能達(dá)到給定

26、的精度。一般而言，在計算過程中初始數(shù)據(jù)的誤差和計算中產(chǎn)生的舍入誤差總是存在的，而數(shù)值解是逐步求出的，前一步數(shù)值解的誤差必然要影響到后一步數(shù)值解的精度。我們把運(yùn)算過程中舍入誤差增長可以控制的計算公式稱為數(shù)值穩(wěn)定的，否則是數(shù)值不穩(wěn)定的。只有穩(wěn)定的數(shù)值方法才可能給出可靠的計算結(jié)果，不穩(wěn)定的數(shù)值方法毫無實用價值。下面用一個例子來簡單介紹一下穩(wěn)定性的概念。例1.11：求 （n = 0, 1, 2, , 8）的值。解：由于初值于是可建立遞推公式（1.17）若取按 (1.17) 式就可以逐步算得因為在0, 1上被積函數(shù)（僅當(dāng)x = 0時為零），且當(dāng)m>n時，（僅當(dāng)x = 0時，等號成立），所以In (

27、n = 0, 1, 2, , 8)是恒正的，并有。在上述計算結(jié)果中，I4的近似值 是負(fù)的，這個結(jié)果顯然是錯的。為什么會這樣呢？這就是誤差傳播所引起的危害。由遞推公式（1.13）可看出，In-1的誤差擴(kuò)大了5倍后傳給In，因而初值I0的誤差對以后各步計算結(jié)果的影響，隨著n的增大愈來愈嚴(yán)重。這就造成I4的計算結(jié)果嚴(yán)重失真。如果改變計算公式，先取一個In的近似值，用下面的公式倒過來計算In-1，In-2，即：（1.18）情況就不同了。我們發(fā)現(xiàn)的誤差減小到后傳給，因而初值的誤差對以后各步的計算結(jié)果的影響是隨著n的增大而愈來愈小。由于誤差是逐步衰減的，初值In可以這樣確定，不妨設(shè)I9 »I10

28、，于是由可求得I9 » 0.017，按公式（1.14）可逐次求得I8» 0.019I7» 0.021I6» 0.024I8» 0.028I4» 0.034I3» 0.043I2» 0.058I1» 0.088I0» 0.182顯然，這樣算出的I0與ln(1.2)的值比較符合。雖然初值I9很粗糙，但因為用公式（1.18）計算時，誤差是逐步衰減的，所以計算結(jié)果相當(dāng)可靠。比較以上兩個計算方案，顯然，前者是一個不穩(wěn)定的算法，后者是一個穩(wěn)定算法。對于一個穩(wěn)定的計算過程，由于舍入誤差不增大，因而不具體估計舍

29、入誤差也是可用的。而對于一個不穩(wěn)定的計算過程，如計算步驟太多，就可能出現(xiàn)錯誤結(jié)果。因此，在實際應(yīng)用中應(yīng)選用數(shù)值穩(wěn)定的算法，盡量避免使用數(shù)值不穩(wěn)定的算法。1.5.2 要避免兩個相似數(shù)相減在數(shù)值計算中，兩個相近的數(shù)作減法時有效數(shù)字會損失。例如，求：（1.19）之值，當(dāng)x = 1000，y的準(zhǔn)確值為0.01580。若兩者直接相減這個結(jié)果只有一位有效數(shù)字，損失了三位有效數(shù)字，從而絕對誤差和相對誤差都變得很大，嚴(yán)重影響計算結(jié)果的精度。若將公式（1.19）處理成，按此公式可求得y = 0.01581，則y有3位有效數(shù)字，可見改變計算公式，可以避免兩相近數(shù)相減引起有效數(shù)字損失，而得到較精確的結(jié)果。類似地，當(dāng)

30、e很小時，當(dāng)x和y很接近時，采用等號右邊的算法，有效數(shù)字就不損失。一般地，當(dāng)時，可用Taylor展開取右端的有限項近似左端。若無法改變算法，直接計算時就要多保留幾位有效數(shù)字。1.5.3絕對值太小的數(shù)不宜作除數(shù)算法語言中已講述，在機(jī)器上若用很小的數(shù)作除數(shù)會溢出，而且當(dāng)很小的數(shù)稍有一點(diǎn)誤差時，對計算結(jié)果影響很大。例1.12：如分母變?yōu)?.0011，也即分母只有0.0001的變化時商卻引起了巨大變化，因此，在計算過程中既要避免兩個相近數(shù)相減，更要避免再用這個差作除數(shù)。1.5.4采用遞推的算法計算機(jī)上使用的算法常采用遞推化的形式，遞推化的基本思想是把一個復(fù)雜的計算過程歸結(jié)為簡單過程的多次重復(fù)。這種重復(fù)

31、在程序上表現(xiàn)為循環(huán)。遞推化的優(yōu)點(diǎn)是簡化結(jié)構(gòu)和節(jié)省計算量。下面用多項式求值問題說明遞推化方法。例1.13：設(shè)對于給定的x求下列n次多項多的值。（1.16）解：1. 用一般算法，即直接求和法，可知乘法的次數(shù)為：；加法次數(shù)為：n2. 逐項求和法令，則所以 記： 可以看出前K + 1項部分和等于前K項部分和再加上第K+ 1項，因此有 = 1, 2, , n（1.17）初值應(yīng)取為（1.18）容易看出逐步求和法所用乘法的次數(shù)為2n，加法次數(shù)為n。當(dāng)n4后，。3. 秦九韶方法首先將多項式改寫為令 則遞推公式為： = 1, 2, , n（1.19）此方法稱為秦九韶方法,也是多項式求值中常用的方法。此方法的計算

32、量為：乘法n次，加法n次。同1、2相比，秦九韶方法的計算量小，且邏輯結(jié)構(gòu)簡單。例1.14：用秦和韶方法求多項式在x = -0.2的值。解：Ka5-KvK00.008330.00833v0 = a510.041670.04v1 = v0x+a420.166670.15867v2 = v1x+a330.50.46827v3 = v2x+a2410.90635v4 = v3x+a1510.81873v5 = v4x+a0（- 0.2）= 0.818731.6 算法的優(yōu)劣我們知道，計算機(jī)的特點(diǎn)是運(yùn)算速度快，存貯的信息量大，并能自動完成極其復(fù)雜的計算過程。計算機(jī)功能雖然很強(qiáng)，但是否可降低對算法的要求呢？

33、許多事實說明，如果算法選擇不當(dāng)，計算機(jī)的利用率就得不到充分發(fā)揮，有時甚至不能得到滿意的解答。一個好的算法，要求有以下幾個優(yōu)點(diǎn)：1計算量小因此，計算量大小是衡量算法優(yōu)劣的一項重要標(biāo)準(zhǔn)。 而后面將要介紹的高斯消去法求解同樣的方程組，乘除法的運(yùn)算次數(shù)不超過3074次，與Gramer法則比較計算量有天壤之別。方程組的階數(shù)增大，計算量的差別還會更大。應(yīng)當(dāng)指出，數(shù)值方法的計算時間，由計算機(jī)速度和數(shù)值方法的效率而定。從某種意義上來說，對于減少計算時間，提高數(shù)值方法的效率甚至比提高計算機(jī)速度更為重要，因為算法研究所需要的代價要小得多。在估計計算量時，我們將區(qū)分主次抓住計算過程中費(fèi)時較多的環(huán)節(jié)。比如，由于加減操

34、作的機(jī)器時間比乘除少得多，對和式可以忽略加法而只統(tǒng)計乘法的次數(shù)。又如算式中需要多次計算函數(shù)值，每求一次時，通常需要進(jìn)行多次加減乘除運(yùn)算，因此對算式只要統(tǒng)計調(diào)用f的次數(shù)就可以了。2存貯量小計算程序所占用的工作單元的數(shù)量稱為算法的內(nèi)存量。盡管計算機(jī)能貯存大量信息，但計算大型算題時有些微機(jī)仍不能使用。因此，盡量節(jié)約存貯量有經(jīng)濟(jì)價值，是衡量算法質(zhì)量的又一標(biāo)準(zhǔn)。3邏輯結(jié)構(gòu)簡單設(shè)計算法時應(yīng)考慮的另一個因素是邏輯結(jié)構(gòu)問題。雖然計算機(jī)能夠執(zhí)行極其復(fù)雜的計算方案，但是計算方案的每個細(xì)節(jié)都需要編程人員制定。因此算法的邏輯結(jié)構(gòu)應(yīng)盡量簡單，才能使編制程度、維修程序和使用程序比較方便。由此可見，雖然計算機(jī)是一種強(qiáng)有力的

35、計算工具，但不能因此忽略對算法的研究。應(yīng)該以計算量大小、存貯量多少、邏輯結(jié)構(gòu)是否簡單作為評定算法優(yōu)劣的標(biāo)準(zhǔn)。 4. 數(shù)值穩(wěn)定 綜上所述，我們總結(jié)出：1.7 復(fù)習(xí)幾個常用公式微分中值定理和泰勒公式是學(xué)習(xí)數(shù)值計算方法的重要工具，許多數(shù)值解法可以直接從泰勒公式中得到，在使用這些方法時，所包含的誤差估計也可以直接得到。同學(xué)們在微積分中已熟悉這些內(nèi)容，但我們?nèi)詫⒆饕粋€簡略的介紹。1.7.1微分中值定理微分中值定理是反映函數(shù)與導(dǎo)數(shù)之間聯(lián)系的重要定理。導(dǎo)數(shù)是由極限定義的，而計算機(jī)只能進(jìn)行有限次運(yùn)算，在計算機(jī)上不得不用函數(shù)值來進(jìn)行微分或積分運(yùn)算，它們是通向微分學(xué)的許多重要應(yīng)用的橋梁。為了使大家能了解中值定理在

36、幾何上的直觀背景，我們考察下述幾何事實：曲線中間，有一點(diǎn)P，在那里，曲線的切線平行于割線。圖1.2 圖1.3現(xiàn)在就來揭示這一幾何事實所包含的數(shù)量關(guān)系。設(shè)曲線的方程為：換句話說，曲線段是函數(shù)f（x）的圖像，則曲線在點(diǎn)P(x, f(x)處的切線斜率就是f(x)，而割線的斜率等于點(diǎn)P處的切線平行于割線，也就是二者斜率相等，于是得到一個公式可歸納出以下定理。定理1 （Roll中值定理）設(shè)函數(shù)f(x)在a, b上連續(xù)，在（a, b）內(nèi)可微，且f(a) = f (b)，則存在，使得f(x) = 0。定理2（Lagrange中值定理）設(shè)函數(shù)f(x)在a, b上連續(xù)，在（a, b）內(nèi)可微，則存在，使得 (1.

37、20)注1.1 若 f(a) = f (b)，則Lagrange中值定理化為Roll中值定理。注1.2 公式（1.20）稱為Lagrange中值公式，它還有其他表示形式，若令則 ，這時，公式（1.20）可以寫成 （1.21）1.7.2泰勒（Taylor）公式無論是手算或用其它計算工具去計算函數(shù)值，都?xì)w結(jié)為做有限次的四則運(yùn)算，由此可見，研究如何用多項式近似地表達(dá)一個給定函數(shù)的問題是很必要的。一個給定的函數(shù)，如果能用多項式近似表達(dá)，那么，通過計算多項式的值，就可以得到給定函數(shù)的近似值。用多項式近似地表達(dá)一個函數(shù)，方式很多，我們這里要談的只是其中一種，我們的問題是：給了一個函數(shù)f (x)，要找一個在

38、指定點(diǎn)x = x0（為簡單計，以下先設(shè)x0 = 0）附近與f (x)很近似的多項式 (1.22)那么，要找的多項式應(yīng)滿足什么樣的條件呢？從幾何上看，y = p(x)與y = f (x)代表兩條曲線，要想多項式p (x)在點(diǎn)x = 0附近與函數(shù)f(x)很近似，就是要曲線y = p (x)與曲線y = f (x)在點(diǎn)(0, f(0)附近很靠近。很明顯，首先應(yīng)該要求曲線y = p (x)與曲線y =f (x)交于點(diǎn)（0, f(0)）（圖1.4）也就是要求多項式p (x)滿足條件 (1.23)要想曲線y = p(x)與曲線y = f (x)在（0, f(0)）附近靠得更近，應(yīng)該進(jìn)而要求它們在點(diǎn)（0,

39、f(0)）處有公共切線（圖1.4），也就是要求多項式p (x)同時滿足下列兩個條件： (1.24)滿足這兩個條件的多項式p (x)可以有很多。試看圖(1.4)曲線y = pi (x)都與曲線y = f (x)在點(diǎn)（0, f(0)）處有公共切線，但與曲線y = f的靠近程度卻可以不一樣。圖1.4要想從中找出與曲線y = f (x)靠得更近的，就要進(jìn)一步來考察它們的彎曲情況。我們要找的顯然是與曲線y = f (x)向同一方向彎曲，這條曲線y = p (x)應(yīng)該滿足條件p²(0) = f ²(0)，即p (x)應(yīng)同時滿足下列三個條件： (1.25)由此可以推想，假如在點(diǎn)x = 0

40、處，p (x)與f (x)的三階導(dǎo)數(shù)，以至更高階導(dǎo)數(shù)都相等，那么在點(diǎn)（0, f (0)）附近，曲線y = p (x)與曲線y = f (x)的靠近程度就會更高。綜上所述，所要找的多項式p (x)應(yīng)滿足下列條件： (1.26)現(xiàn)在，根據(jù)條件（1.26），我們就可以確定所要找的近似多項式的具體形狀了。首先，由（1.22）得到于是，條件（1.26）就變成即代入(1.22)式，就得到： (1.27)這就是我們要找的多項式，這個多項式稱為f (x)在x0 = 0這點(diǎn)的泰勒多項式，記為pn (x)。為了進(jìn)一步研究這個多項式和f (x)究竟差多少，我們必須分析誤差項為推導(dǎo)rn (x)的表達(dá)式，我們假定f (

41、x)在點(diǎn)x0 = 0附近有直到n + 1階的連續(xù)導(dǎo)數(shù)，注意從rn(x)的定義可見于是由微積分學(xué)基本定理及分部積分法，得繼續(xù)實行分部積分，最后利用。便得： (1.28)(1.28)式稱為f (x)在點(diǎn)x0 = 0的積分型Taylor余項公式。由(1.23)式，我們還可以導(dǎo)出另一種形式的余項公式：設(shè)在0£t £x上的最大值為M，最小值為m，不妨設(shè)x > 0，此時。因此而所以上式即由連續(xù)函數(shù)的介值定理，應(yīng)有x, 0£x£x，使即 (1.29)此式為f (x)在x0 = 0點(diǎn)的拉格朗日型余項公式，也是最常用的一種Taylor余項公式。rn(x)通常稱為n階

42、余項，利用rn(x)，我們可以寫成： (1.30)(1.30)式稱為f (x)在x0 = 0點(diǎn)的Taylor公式。對任意點(diǎn)x0，f (x)在x0點(diǎn)的Taylor公式是： 例1.15 Taylor展開1.8函數(shù)計算的誤差估計設(shè)一元函數(shù)f (x)具有二階導(dǎo)數(shù)，自變量x的一個近似值x*，f (x)的近似值為f (x*)，用f (x)在x*點(diǎn)的Teylor展開估計誤差，可得其中x在x與x*這間，如果與有相同數(shù)量級，而很小，則可得 （1.31）分別為f (x*)的一個近似誤差限與相對誤差限。如果f為多元函數(shù)，自變量為x1, xn，其近似值為，則類似于一元函數(shù)可用多元函數(shù)f (x1, x2, , xn)的

43、Taylor展開，取一階近似的誤差限 （1.32）及相對誤差限 （1.33）若把（1.33）用到兩個或多個數(shù)的算術(shù)運(yùn)算中，則可得到近似數(shù)及的四則運(yùn)算誤差估計： （1.34） （1.35） （1.36）例1.16 已測得某場地長l的值為l* = 110m，寬d的值為d* = 80m，已知，試求面積S = ld的絕對誤差限與相對誤差限。解 因S = ld，由（）知其中，從而有相對誤差限為病態(tài)問題與條件數(shù)對一個數(shù)值問題，往往由于問題本身而使計算結(jié)果相對誤差很大，這種問題就是病態(tài)問題。例如計算函數(shù)值f (x)，若x的近似值為x*，其相對誤差為，函數(shù)值f (x*)的相對誤差為，它們相對誤差之比的絕對值為

44、 (1.37）Cp稱為計算函數(shù)值f (x)的條件數(shù)，如果Cp很大，將引起函數(shù)值f (x*)的相對誤差很大，出現(xiàn)這種情況時，就認(rèn)為問題是病態(tài)的。例如，則Cp = n，它表示相對誤差可能放大n倍，如n = 10，有f (1) = 1，f (1.02) » 1.24，若x = 1，x* = 1.02，則自變量相對誤差為2%，而函數(shù)值f (1.02)的相對誤差為24%，這時就認(rèn)為問題是病態(tài)的。一般情況下若條件數(shù)Cp³ 10，則認(rèn)為是問題病態(tài)，Cp越大病態(tài)越嚴(yán)重。第一章 習(xí)題1什么是數(shù)值計算方法？它與數(shù)學(xué)科學(xué)和計算機(jī)的關(guān)系如何？2. 數(shù)值計算方法的主要研究對象是什么？3什么是算法？如何判斷數(shù)值算法的優(yōu)劣？4. 誤差為什么是不可避免的？用什么標(biāo)準(zhǔn)來衡量近似值是準(zhǔn)確的？5列出科學(xué)計算中的誤差來源，并說出截斷誤差與舍入誤差的區(qū)別。6什么是絕對誤差與相對誤差？什么是近似數(shù)的有效數(shù)字？它與絕對誤差和相對誤差有何關(guān)系？7. 什么是數(shù)值穩(wěn)定的算法？如何判斷算法穩(wěn)定？為什么不穩(wěn)定算法不能使用？8下列各數(shù)都是經(jīng)過四舍五入得到的近似數(shù)，試分別指出其絕對誤差限、相對誤差限和有效數(shù)字位數(shù)9求方程的兩個根，使它們具有4位有效數(shù)字。10計算下列式子，要求具有4位有效數(shù)字。（1） （2