數(shù)值計(jì)算教案第一章預(yù)篇

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

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

3、相關(guān)的基本概念及理論。內(nèi)容包括誤差分析初步，方程求根，線性方程組的直接解法與迭代法，插值法，最小二乘曲線擬合，數(shù)值積分計(jì)算，常微分方程數(shù)值解法和偏微分方程數(shù)值解法。本課程中對(duì)主要基本算法的推導(dǎo)、構(gòu)造原理、收斂性、誤差估計(jì)進(jìn)行了。本的另一個(gè)特色是側(cè)重于計(jì)算機(jī)應(yīng)用，各章均有例題及數(shù)值算例，并應(yīng)掌握的基本問題，對(duì)每一個(gè)算法都給出偽代碼，以便于學(xué)生編制程序的需要，且有適當(dāng)?shù)木毩?xí)及一些上機(jī)計(jì)算題。本可作為理工科（非數(shù)學(xué)）各專業(yè)及大學(xué)本科高年級(jí)的數(shù)值計(jì)算方法，也可供工程技術(shù)參考。學(xué)位課數(shù)值計(jì)算方法教學(xué)已經(jīng) 30 余年，在多年作者從事的教學(xué)中發(fā)現(xiàn)給農(nóng)業(yè)院校的學(xué)生尋找一本合適的很難。一方面，和其它理工科院校的

4、學(xué)生相比，農(nóng)業(yè)院校的學(xué)生數(shù)學(xué)基礎(chǔ)課學(xué)得不夠，因此需要淺顯易懂的；另一方面，農(nóng)業(yè)科學(xué)的發(fā)展，對(duì)數(shù)學(xué)和計(jì)算科學(xué)提出了很高的要求，因?yàn)檗r(nóng)業(yè)科學(xué)的復(fù)雜性和不確定性，需要有盡可能多的內(nèi)容和深度，這樣互相的需求給講課教師提出了很高的要求，教師要深入的理解數(shù)值計(jì)算的理念，要有深厚的計(jì)算數(shù)學(xué)理論知識(shí)和計(jì)算經(jīng)驗(yàn)才能講好這門課。在學(xué)習(xí)了許多國(guó)內(nèi)外的基礎(chǔ)上，根據(jù)農(nóng)業(yè)院校學(xué)生的特殊要求，作者于 1984 年編寫了數(shù)值計(jì)算方法講稿，每年都有小的改動(dòng)，在 1993 年、1999 年、2005 年和 2009 年對(duì)講稿進(jìn)行了幾次較大的修改，以適應(yīng)科學(xué)發(fā)展需要和農(nóng)業(yè)院校學(xué)生的基礎(chǔ)。許多通過學(xué)中了數(shù)值計(jì)算方法解決應(yīng)用問題，提高

5、了水平，也有許多在職教師和科研學(xué)習(xí)這門課程后，將數(shù)值方法到科研課題中，取得了較好的成果。超星公司在 2009 年為作者做了數(shù)值計(jì)算方法的教學(xué)，幾年來在網(wǎng)上聽眾甚多，作者時(shí)常收到理工科選修數(shù)值分析學(xué)生的郵件，表達(dá)了大家對(duì)作者講課的認(rèn)可，本講義也可以作為理工科非數(shù)學(xué)專業(yè)學(xué)生學(xué)習(xí)數(shù)值計(jì)算方法的參考書。目錄第一章預(yù)篇1.1數(shù)值計(jì)算方法的研究對(duì)象和特點(diǎn)1.2誤差分析1.3算法概述第二章非線性方程求根2.1二分法2.2迭代法的一般原則2.3法(切)2.4弦截法第三章解線性方程組的直接法3.1Gauss 消去法3.2矩陣的三角分解及其在解方程組中的應(yīng)用3.3稱正定矩陣方程組的平方根解法3.4解三對(duì)角方程組的

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

7、 求積公式8.2Romberg 求積公式8.3Gauss 型求積公式第九章常微分方程數(shù)值解9.1Euler 法和改進(jìn) Euler 法9.2Runge-Kutta 法9.3線性多步法9.4解二階常微分方程邊值問題的差分法第十章偏微分方程數(shù)值解10.1 橢圓型方程差分法10.2 拋物型方程差分法10.3 雙曲型方程差分法10.4 有限元方法初步第一章預(yù)篇數(shù)學(xué)是研究數(shù)與形的科學(xué)。其中研究怎樣利用手指、算盤、計(jì)算尺、計(jì)算器、計(jì)算機(jī)等工具，來求出數(shù)學(xué)問題數(shù)值解的學(xué)問，就是數(shù)值計(jì)算方法。它是數(shù)學(xué)中最古老的部分，但只是在計(jì)算機(jī)出現(xiàn)以后，人們獲得了高速度、自動(dòng)化的計(jì)算工具，才為眾多浩繁的數(shù)值計(jì)算問題的解決展現(xiàn)

8、了光明的前景。從此，科學(xué)研究與工程設(shè)計(jì)段，發(fā)生了由模型試驗(yàn)向數(shù)值計(jì)算的巨大轉(zhuǎn)變。近年來，由于計(jì)算機(jī)的發(fā)展，計(jì)算性的學(xué)科新分支，如計(jì)算力學(xué)、計(jì)算物理、計(jì)算化學(xué)、計(jì)算生物學(xué)、計(jì)算地質(zhì)學(xué)、計(jì)算經(jīng)濟(jì)學(xué)以及眾多工程科學(xué)的計(jì)算分支紛紛興起。因?yàn)槿魏尉唧w學(xué)科中的計(jì)算過程，不論其目的、背景和含義如何，終歸是數(shù)學(xué)的計(jì)算過程，數(shù)值計(jì)算方法是各種計(jì)算性學(xué)科的聯(lián)系紐帶和共性基礎(chǔ)。學(xué)習(xí)數(shù)值計(jì)算方法可以知道如何用計(jì)算機(jī)解決數(shù)學(xué)問題，特別是在微積分和線性代數(shù)中沒有學(xué)過的一些解決問題的方法，還介紹一些用不同的方法解決以前用傳統(tǒng)的數(shù)學(xué)方法解決。選擇一些現(xiàn)實(shí)世界存在的例子，用的方法能夠解出來，以便將數(shù)值方法和方法做一個(gè)對(duì)比。1.

9、1數(shù)值計(jì)算方法的和意義數(shù)值計(jì)算方法是數(shù)學(xué)的一個(gè)古老的分支，雖然數(shù)學(xué)不僅僅是計(jì)算，但推動(dòng)數(shù)學(xué)產(chǎn)生和發(fā)展的最直接原因還是計(jì)算問題。人類社會(huì)發(fā)展的初期，就常常遇到各種各樣的計(jì)算問題。一開始沒有任何計(jì)算工具，最得心應(yīng)手的就是人類的一雙手了。于是人們采取了扳手指頭和結(jié)繩計(jì)數(shù)的方法進(jìn)行計(jì)算。隨著社會(huì)的進(jìn)一步向前發(fā)展，問題越來越復(fù)雜，原始的工具不敷使用。人們?cè)絹碓狡惹械叵Ｍ懈冗M(jìn)的技術(shù)和理論來進(jìn)行計(jì)算，于是數(shù)學(xué)應(yīng)運(yùn)而生?？梢赃@么說，記數(shù)術(shù)是最原始的數(shù)學(xué)，數(shù)學(xué)的就是計(jì)算，計(jì)算自古以來就是數(shù)學(xué)的一個(gè)重要組成部分。中國(guó)古代數(shù)學(xué)曾經(jīng)有過輝煌的成就，它不像古希臘數(shù)學(xué)那樣注重邏輯和推理，而是具有顯著的計(jì)算性和實(shí)用性的

10、特點(diǎn)，從九章算術(shù)等中國(guó)古典數(shù)學(xué)名著中就可以看出這一點(diǎn)。早在商代中國(guó)就形成了十進(jìn)制這一方便的計(jì)數(shù)和運(yùn)算機(jī)制。從最早發(fā)明的算籌到后來的算盤以及相應(yīng)發(fā)展起來的珠算方法，是古代中國(guó)對(duì)世界計(jì)算技術(shù)的最重要貢獻(xiàn)，至今還和其他一些國(guó)家都發(fā)揮著作用。到了二十世紀(jì)四十年產(chǎn)高性能計(jì)算工具的技術(shù)條件已經(jīng)成熟。當(dāng)時(shí)第二次世界大戰(zhàn)，軍事上對(duì)高速計(jì)算機(jī)有迫切的需求。這就迎來了世界上第一臺(tái)電子計(jì)算機(jī)的誕生。計(jì)算機(jī)的問世，從根本上改變了計(jì)算工具的局面。古老的計(jì)算數(shù)學(xué)借助計(jì)算機(jī)這一強(qiáng)有力的工具，一下子換發(fā)出了青春。隨著計(jì)算技術(shù)的發(fā)展，社會(huì)需求的急劇增加，計(jì)算數(shù)學(xué)的應(yīng)用領(lǐng)域越來越廣泛，這就使得越來越多的、以前不能設(shè)想的、難度和規(guī)

11、模日益增大的計(jì)算問題得以解決。在這樣新的條件下，計(jì)算在整個(gè)科學(xué)技術(shù)以至經(jīng)濟(jì)生活中的重要性得到前所未有的提高；同時(shí)，以原來分散在數(shù)學(xué)各分支的計(jì)算方法為基礎(chǔ)的一門新的數(shù)學(xué)科學(xué)開始形成并迅速發(fā)展。計(jì)算數(shù)學(xué)和計(jì)算機(jī)一起已經(jīng)成為眾多領(lǐng)域研究工作中不可或缺的工具和手段。當(dāng)代計(jì)算能力的大幅度提高既來自計(jì)算機(jī)的進(jìn)步，也來自計(jì)算方法的進(jìn)步。計(jì)算機(jī)和計(jì)算方法的發(fā)展是相輔相成、相互制約和相互促進(jìn)的。計(jì)算方法的發(fā)展啟發(fā)了新的計(jì)算機(jī)體系結(jié)構(gòu)，而計(jì)算機(jī)的更新?lián)Q代也對(duì)計(jì)算方法提出了新的標(biāo)準(zhǔn)和要求。自計(jì)算機(jī)誕生以來，經(jīng)典的計(jì)算方法業(yè)已經(jīng)歷了一個(gè)重新評(píng)價(jià)、篩選、改造和創(chuàng)新的過程；與此同時(shí)，涌現(xiàn)了許多新概念、新課題和許多能夠充分

12、發(fā)揮計(jì)算機(jī)潛力、有更大解題能力的新方法；這就了現(xiàn)代意義下的計(jì)算數(shù)學(xué)（數(shù)值計(jì)算方法）。1.2 數(shù)值計(jì)算方法的研究對(duì)象科學(xué)計(jì)算問題的出發(fā)點(diǎn)，往往是研究現(xiàn)實(shí)世界中或現(xiàn)象。例如：物理、自然或者社會(huì)問題。在一定的假設(shè)下，可以將這些實(shí)際問題列成方程，也就是數(shù)學(xué)模型來描述或進(jìn)行分析。從簡(jiǎn)單的代數(shù)方程到復(fù)雜的非線性偏微分方程應(yīng)有盡有。這些方程一旦建立起來，下一步就是要解方程，以這些現(xiàn)象將來朝什么方向發(fā)展。為了獲取數(shù)據(jù)，也需要做一些實(shí)驗(yàn)。如果模型的結(jié)果和實(shí)測(cè)數(shù)據(jù)一致或接近，就認(rèn)為所建立的模型是合適的，否則就要對(duì)所建立的模型加以調(diào)整和改進(jìn)。在求解階段，最理想的狀況是求出方程的解，遺憾的是，僅對(duì)最簡(jiǎn)單的模型才能求出

13、解。通過幾個(gè)例子來說明在微積分和線性代數(shù)中學(xué)過的數(shù)學(xué)模型而在這兩門課程中所沒有學(xué)到可行的解法。例 1.1 求解線性方程組 AX=b，其中系數(shù)矩陣 A 是計(jì)算機(jī)實(shí)質(zhì)上只會(huì)做加減乘除等基本運(yùn)算。研究怎樣通過計(jì)算機(jī)所執(zhí)行的基本運(yùn)算，求得各類問題的數(shù)值解或近似數(shù)值解，就是計(jì)算數(shù)學(xué)的根本課題。數(shù)值計(jì)算方法的研究對(duì)象：數(shù)值計(jì)算方法主要研究適合于在計(jì)算機(jī)上使用的計(jì)算方法以及與此相關(guān)的理論，包括方法的收斂性、穩(wěn)定性及誤差分析。還要根據(jù)計(jì)算機(jī)的特點(diǎn)研究時(shí)間最短、需要計(jì)算機(jī)內(nèi)存最少的計(jì)算方法。1.3 算法算法的定決問題的一系列有序的步驟。描述算法可以有不同的方式。例如，可以用日常語言和數(shù)學(xué)語言加以敘述，也可以借助

14、形式語言（算法語言）給出精確的說明，也可以用框圖直觀地顯示算法的全貌。下面舉個(gè)簡(jiǎn)單的例子。例 1.7：求解二元一次聯(lián)立方程組YesNON圖 1.1 框圖這里使用了兩種形式的框，一種是矩形框，稱為敘述框，計(jì)算公式就填在這種框內(nèi)；另一種是棱形框，稱為判斷框，表示算法的判斷分。1.4 數(shù)值計(jì)算中的誤差用數(shù)值方法解決科學(xué)研究或工程技術(shù)中的實(shí)際問題，一般來說，產(chǎn)生誤差是不可避免的，根本不存在嚴(yán)格和精確。但是可以認(rèn)識(shí)誤差，從而控制誤差，使之局限于最?。ɑ虮M量?。┑姆秶鷥?nèi)。輸 入開 始1.4.1 誤差的來源運(yùn)用數(shù)學(xué)工具解決實(shí)際問題，可能產(chǎn)生的誤差主要有以下幾類。1描述誤差在將實(shí)際問題轉(zhuǎn)化為數(shù)學(xué)模型的過程中，

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

16、。如 = 3.1415926證明 若利用于是可建立遞推公式I4 0.034I2 0.058I0 0.182I3 0.043I1 0.088顯然，這樣算出的 I0 與 ln(1.2)的值比較符合。雖然初值 I9 很粗糙，但因?yàn)橛霉剑?.18）計(jì)算時(shí)，誤差是逐步衰減的，所以計(jì)算結(jié)果相當(dāng)可靠。比較以上兩個(gè)計(jì)算方案，顯然，前者是一個(gè)不穩(wěn)定的算法，后者是一個(gè)穩(wěn)定算法。對(duì)于一個(gè)穩(wěn)定的計(jì)算過程，由于舍入誤差不增大，因而不具體估計(jì)舍入誤差也是可用的。而對(duì)于一個(gè)不穩(wěn)定的計(jì)算過程，如計(jì)算步驟太多，就可能出現(xiàn)錯(cuò)誤結(jié)果。因此，在實(shí)際應(yīng)用中應(yīng)選用數(shù)值穩(wěn)定的算法，盡量避免使用數(shù)值不穩(wěn)定的算法。1.5.2 要避免兩個(gè)相似

17、數(shù)相減在數(shù)值計(jì)算中，兩個(gè)相近的數(shù)作減法時(shí)有效數(shù)字會(huì)損失。例如，求：410.90635v4 = v3x+a1510.81873v5 = v4x+a0（- 0.2）= 0.818731.6算法的優(yōu)劣知道，計(jì)算機(jī)的特點(diǎn)是運(yùn)算速度快，存貯的信息量大，并能自動(dòng)完成極其復(fù)雜的計(jì)算過程。計(jì)算機(jī)功能雖然很強(qiáng)，但是否可降低對(duì)算法的要求呢？許多事實(shí)說明，如果算法選擇不當(dāng)，計(jì)算機(jī)的利用率就得不到充分發(fā)揮，有時(shí)甚至不能得到滿意的解答。一個(gè)好的算法，要求有以下幾個(gè)優(yōu)點(diǎn)：1計(jì)算量小因此，計(jì)算量大小是衡量算法優(yōu)劣的一項(xiàng)重要標(biāo)準(zhǔn)。而后面將要介紹的消去法求解同樣的方程組，乘除法的運(yùn)算次數(shù)不超過 3074 次，與Gramer 法

18、則比較計(jì)算量有天壤之別。方程組的階數(shù)增大，計(jì)算量的差別還會(huì)更大。應(yīng)當(dāng)，數(shù)值方法的計(jì)算時(shí)間，由計(jì)算機(jī)速度和數(shù)值方法的效率而定。從某種意義上來說，對(duì)于減少計(jì)算時(shí)間，提高數(shù)值方法的效率甚至比提高計(jì)算機(jī)速度更為重要，因?yàn)樗惴ㄐ枰拇鷥r(jià)要小得多。在估計(jì)計(jì)算量時(shí)，區(qū)分主次抓住計(jì)算過程中費(fèi)時(shí)較多的環(huán)節(jié)。比如，由于加減操作的機(jī)器時(shí)間比乘除少得多，對(duì)和式能使編制程度、維修程序和使用程序比較方便。由此可見，雖然計(jì)算機(jī)是一種強(qiáng)有力的計(jì)算工具，但不能因此忽略對(duì)算法的研究。應(yīng)該以計(jì)算量大小、存貯量多少、邏輯結(jié)構(gòu)是否簡(jiǎn)單作為評(píng)定算法優(yōu)劣的標(biāo)準(zhǔn)。4. 數(shù)值穩(wěn)定綜上所述，總結(jié)出一個(gè)高質(zhì)量的算法的特點(diǎn)：數(shù)值穩(wěn)定，計(jì)算量小，量小

19、，邏輯結(jié)構(gòu)簡(jiǎn)單。1.7 復(fù)習(xí)幾個(gè)常用公式微分中值定理和公式是學(xué)習(xí)數(shù)值計(jì)算方法的重要工具，許多數(shù)值解法可以直接從泰勒公式中得到，在使用這些方法時(shí)，所包含的誤差估計(jì)也可以直接得到。在微積分中已熟悉這些內(nèi)容，但仍將作一個(gè)簡(jiǎn)略的介紹。1.7.1 微分中值定理微分中值定理是反映函數(shù)與導(dǎo)數(shù)之間聯(lián)系的重要定理。導(dǎo)數(shù)是由極限定義的，而計(jì)算機(jī)只能進(jìn)行有限次運(yùn)算，在計(jì)算機(jī)上不得不用函數(shù)值來進(jìn)行微分或積分運(yùn)算，它們是通向微分學(xué)的許多重要應(yīng)用的橋梁。為了使大家能了解中值定理在幾何上的直觀背景，下述幾何事實(shí)：曲線換句話說，曲線段從幾何上看，y = p(x)與 y = f (x)代表兩條曲線，要想多項(xiàng)式 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 (于點(diǎn)（0, f(0)）（圖 1.4）也就是要求多項(xiàng)式 p (x)滿足條件綜上所述，所要找的多