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

1數(shù)值計算方法徐晶理學院數(shù)學系Mobile-mail:309807913@Office:理學院數(shù)學系2102教材

(TextBook)數(shù)值計算方法令鋒傅守忠等編著

（國防工業(yè)出版社）

參考書目

(Reference)

數(shù)值分析王金銘劉艷秋陳欣大連理工大學出版社

數(shù)值分析李慶揚王能超易大義華中科技大學出版社計算方法典型例題與解法高培旺等國防科技大學出版社

計算方法典型例題與分析孫守忠科學出版社教材及參考書微積分線性代數(shù)常微分方程C、C++語言預備知識教學進度課次教學內容1第1章數(shù)值計算方法概論2§2.1對分區(qū)間法§2.2簡單迭代法3§2.3加速收斂迭代法

§2.4牛頓迭代法§2.5正割法4§3.1Gauss列主元消去法5§3.2LU分解法

6§3.3三對角方程組的追趕法7§4.1向量范數(shù)與矩陣范數(shù)8§4.2Jacobi迭代法§4.3Gauss-Seidel迭代法9§4.4迭代法的收斂性§4.5逐次超松弛迭代法10§5.1代數(shù)插值法及其唯一性

§5.2Lagrange插值法11

§5.3Newton插值法§5.4Hermite插值法12

§5.5三次樣條插值法13§5.6最小二乘擬合法14§6.1插值型求積公式§6.2三個常用的求積公式及其誤差

15§6.3復化求積公式16§6.4Romberg求積公式§6.5Gauss求積公式

§6.6數(shù)值微分法

17§7.1Euler方法§7.2高階Taylor方法18§7.3Runge-Kutta法51.閉卷考試占60%2.出勤占10%3.測驗及平時作業(yè)占30%成績構成一、數(shù)值計算方法

能夠做什么？§1.1數(shù)值計算方法的基本內容與特點今有上禾三秉，中禾二秉，下禾一秉，實三十九斗；上禾二秉，中禾三秉，下禾一秉，實三十四斗；上禾一秉，中禾二秉，下禾三秉，實二十六斗。問上、中、下禾實一秉各幾何？答曰：上禾一秉九斗四分斗之一。中禾一秉四斗四分斗之一。下禾一秉二斗四分斗之三。-------《九章算術》1、一個兩千年前的例子線性方程組的求解！2、天體力學中的Kepler方程x是行星運動的軌道，它是時間t的函數(shù).非線性方程求根！全球定位系統(tǒng)：在地球的任何一個位置，至少可以同時收到4顆以上衛(wèi)星發(fā)射的信號

3、全球定位系統(tǒng)（GlobalPositioningSystem,GPS)

表示地球上一個接收點R的當前位置，衛(wèi)星Si的位置為，則得到下列非線性方程組記為其中，非線性方程組的求解！4、已經(jīng)測得在某處海洋不同深度處的水溫如下：深度（M）46674195014221634水溫（oC）7.044.283.402.542.13根據(jù)這些數(shù)據(jù)，希望合理地估計出其它深度（如500米，600米，1000米…）處的水溫.插值法！5、人口預測

下面給出的是中國1900年到2000年的人口數(shù)，我們的目標是預測未來的人口數(shù)（數(shù)據(jù)量較大時）19505519619606620719708299219809870519901143332000126743數(shù)據(jù)擬合！6、鋁制波紋瓦的長度問題建筑上用的一種鋁制波紋瓦是用一種機器將一塊平整的鋁板壓制而成的.假若要求波紋瓦長4英尺,每個波紋的高度(從中心線)為1英寸,且每個波紋以近似2π英寸為一個周期.求制做一塊波紋瓦所需鋁板的長度L.

這個問題就是要求由函數(shù)f(x)=sinx

給定的曲線從x=0到x=48英寸間的弧長L.

由微積分學我們知道,所求的弧長可表示為:上述積分稱為第二類橢圓積分,它不能用普通方法來計算.數(shù)值積分！計算機輔助設計：波音777應用三維立體建模，數(shù)字化設計與有限元計算的第一架噴氣客機。天氣預報：計算能力的發(fā)展將把海洋、大氣和生態(tài)系統(tǒng)的綜合知識融合成一個氣象變化模型。醫(yī)學與生物工程：CT、核磁共振與Radon變換；至病基因與藥物設計；人造生物材料的彷真響應；傳染病動力學模型。現(xiàn)代科學計算在工程計算中的應用電子系統(tǒng)自動化設計：大規(guī)模集成電路的設計與邏輯檢測。材料設計：性能設計的大規(guī)模計算與模擬：設計用于生產(chǎn)新的高熱值、高壓材料中的化學蒸發(fā)沉淀反應器。車輛與道路工程設計與模擬：車輛與道路相互作用綜合系統(tǒng)設計。存儲與物流系統(tǒng)：工農業(yè)發(fā)展使得產(chǎn)品的存儲、交流和時效性極大提高；廢物和垃圾問題成為城市生活的重大問題。規(guī)劃計算和系統(tǒng)分析成為常用計算方法。燃燒與爆炸工程：燃燒對環(huán)境的影響；計算流體力學與爆炸工程。網(wǎng)絡設計與計算：搜索引擎的設計航空航天工程：神州飛船系列信息與通信工程：GPS衛(wèi)星導航二、數(shù)值計算方法的意義、內容與方法軟件的核心就是算法。20世紀最偉大的科學技術發(fā)明---計算機

計算機是對人腦的模擬，它強化了人的思維智能；計算機的發(fā)展和應用，已不僅僅是一種科學技術現(xiàn)象，而且成了一種政治、軍事、經(jīng)濟和社會現(xiàn)象；沒有軟件的支持，超級計算機只是一堆廢鐵而已；算法猶如樂譜，軟件猶如CD盤片，硬件如同CD唱機。理論研究科學實驗科學計算計算數(shù)學諾貝爾獎得主,計算物理學家Wilson提出現(xiàn)代科學研究的三大支柱

科學方法論的巨大變革：如果說伽利略和牛頓在科學發(fā)展史上奠定了實驗和理論這兩大科學方法的支柱，那么由馮.諾依曼研制的現(xiàn)代電子計算機把計算推上了人類科學活動的前沿，使計算成為第三種方法。21世紀信息社會的兩個主要特征：“計算機無處不在”“數(shù)學無處不在”21世紀信息社會對科技人才的要求：--會用數(shù)學解決實際問題--會用計算機進行科學計算建立數(shù)學模型選取計算方法編寫上機程序計算得出結果科學計算解題過程數(shù)值計算方法是計算數(shù)學的一個主要組成部分，“什么是數(shù)值計算方法？”它主要研究使用計算機求解各種科學與工程計算問題的數(shù)值方法（近似方法）;對求得的解的精度進行評估以及在計算機上實現(xiàn)求解等。

數(shù)值計算方法已經(jīng)成為計算機處理實際問題的一個重要手段，從宏觀天體運動學到微觀分子細胞學，從工程系統(tǒng)到社會經(jīng)濟系統(tǒng)，無一能離開數(shù)值計算方法。因此，數(shù)值計算與計算機模擬被稱為“第三種科學研究方法”。

科學計算可視化是目前研究的熱門問題，下面的藝術圖形是基于科學計算的數(shù)據(jù)表示的例子分形圖混沌圖1、數(shù)值逼近

插值與擬合、FFT、數(shù)值積分與微分2、數(shù)值代數(shù)

代數(shù)基礎、線性代數(shù)方程組的解法、非線性代數(shù)方程（組）的解法、特征值與特征向量3、微分方程數(shù)值解

ODE、PDE和有限元法4、最優(yōu)化方法*無約束優(yōu)化與約束優(yōu)化方法融進了機器學習計算、仿生計算、網(wǎng)絡計算、以數(shù)據(jù)為核心的計算和各種普適計算、非線性科學計算等內容。傳統(tǒng)的數(shù)值計算的主要研究內容

現(xiàn)代計算方法：數(shù)值計算方法的主要特點借助計算機提供切實可行的數(shù)學算法.想的精確度;收斂且穩(wěn)定;誤差可以分析或估計.所提出的算法必須具有：可靠的理論分析;理時間復雜性好__指節(jié)省時間；空間復雜性好__指節(jié)省存儲量。計算復雜性好

通過數(shù)值實驗證明算法行之有效.采用“近似替代”方法→逼近采用“構造性”方法采用“離散化”方法

把求連續(xù)變量的問題轉化為求離散變量的問題采用“遞推化”方法

復雜的計算歸結為簡單過程的多次重復，易于用循環(huán)結構來實現(xiàn)（迭代法）。采用各種搜索方法構造數(shù)值算法的主要手段

希望：求近似解，但方法簡單可行，行之有效（計算量小，誤差小,需存儲單元少等）,

以計算機為工具，易在計算機上實現(xiàn)。計算機運算:

只能進行加，減，乘，除等算術運算和一些邏輯運算。數(shù)值計算方法：

把求解數(shù)學問題轉化為按一定次序只進行加，減，乘，除等基本運算.設計數(shù)值算法的出發(fā)點？三、如何學好數(shù)值計算方法？hhhhhhhhhhhhhgggg幾點紀律要求上課至少提前2分鐘到教室，不早退上課期間手機靜音課前預習，課后復習，及時解決存在的問題課堂上認真聽講，適當記筆記，積極回答問題作業(yè)獨立完成，保質保量按時上交有事提前請假，否則，記無故曠課威爾金森（JamesHardy.Wilkinson，1919-1986）Wilkinson是數(shù)值分析和數(shù)值計算的開拓者和奠基人。1940年，開始研究彈道的數(shù)學模型與數(shù)值計算。1946年成為Turing的助手，協(xié)助設計PilotACE計算機。1969年他當選為英國皇家學會院士；1970年工業(yè)和應用數(shù)學會(s1am)授予他馮·諾伊曼獎；1987年他獲得美國數(shù)學會的chauvenet獎。著名的美國阿爾貢國家實驗室曾聘威爾金森為榮譽高級研究員并兩次向他授獎。

Wilkinson在數(shù)值分析研究領域作出了杰出貢獻，是數(shù)值計算的早期開拓者，其工作加速了數(shù)字計算機(在科學計算中)的使用。他研究的主要問題是線性代數(shù)方程組和矩陣特征值問題的數(shù)值解法，特別是他的向后誤差分析法(backwarderroranalysis)的創(chuàng)造性工作奠定了數(shù)值分析和數(shù)值計算早期的理論基礎。

1975年J.H.Wilkinson成為第五位圖靈獎獲得者。36用計算機進行實際問題的數(shù)值計算時，往往求得是問題的近似解，都存在誤差。誤差公理：任何測量（觀測）都存在誤差。誤差是不可避免的，即要允許誤差，又要控制誤差?！?.2誤差的基本理論一、誤差的來源與分類從實際問題中抽象出數(shù)學模型

——模型誤差ModelError

例:質量為m的物體，在重力作用下,自由下落，其下落距離s與時間t的關系是：

其中g

為重力加速度。通過測量得到模型中參數(shù)的值

——觀測誤差ObservationError

截斷誤差——方法誤差TruncationError例如，當函數(shù)用Taylor多項式

近似代替時，數(shù)值方法的截斷誤差是

與0之間。在舍入誤差——Round-offError

用計算機、計算器和筆算，都只能用有限位

=3.1415926…

小數(shù)來代替無窮小數(shù)或用位數(shù)較少的小數(shù)來代替位數(shù)較多的有限小數(shù)，如：四舍五入后……在數(shù)值計算方法中，主要研究截斷誤差和舍入誤差（包括初始數(shù)據(jù)的誤差）對計算結果的影響！二、誤差的概念1、絕對誤差AbsoluteError是近似值的絕對誤差,簡稱為誤差。

若近似值偏大，稱“強近似”或“盈近似”若近似值偏小，稱“弱近似”或“虧近似”注

越小，精度越高；定義1-1：設是準確值，為

的一個近似值，稱例1、用毫米刻度尺測量長度為的物體，測得其長度為，是物體實際長度的一個近似值，由于直尺以毫米為刻度，故誤差不超過半個毫米，則有：通常記為：絕對誤差限

例2、真空中光速c的近似值為例1、用毫米刻度尺測量長度為的物體，測得其長度為，是物體實際長度的一個近似值，由于直尺以毫米為刻度，故誤差不超過半個毫米，則有：在應用上，常常采用下列寫法來刻劃的精度。因準確值往往無法知道，只能估計：（上界）叫做的絕對誤差限。即落在內。44例如，有兩個量，則雖然比大4倍，但比

所以除考慮誤差的大小外，還應考慮準確值本身的大小.要小得多，這說明近似的程度比近似的程度好.45定義1-2：相對誤差

實際計算中，常用下式代替：2、相對誤差：RelativeError因實際誤差未知，常采用：相對誤差限

近似值的誤差與準確值x的比值

46定義1-3：若近似值的誤差限是某一位的半個單位，該位到的第一位非零數(shù)字共有位，就說有位有效數(shù)字。例意義：有效數(shù)字越多，誤差限越小，數(shù)值越準確。3、有效數(shù)字significantdigits

如果一個近似數(shù)的所有數(shù)字均為有效數(shù)字，則稱之為有效數(shù)。47則有位有效數(shù)字，精確到。類似科學計數(shù)法式中,(小數(shù)點后1位）；可以為零；為整數(shù)。如果48有效數(shù)字與相對誤差的關系

有效數(shù)字

相對誤差限已知x*有n位有效數(shù)字，則其相對誤差限為相對誤差限有效數(shù)字已知x*的相對誤差限可寫為則可見x*至少有n位有效數(shù)字。Th1.2：

設反之,若的相對誤差的絕對值大于，其中為整數(shù),為正整數(shù),。有位有效數(shù)字。則至多若至多有位有效數(shù)字,即是有效數(shù)字,而不是有效數(shù)字,則的相對誤差的絕對值必大于;證明：不是有效數(shù)字

反之,若

則

不是有效數(shù)字，

即至多有位有效數(shù)字.

51例為使的相對誤差小于0.001%,至少應取幾位有效數(shù)字？解假設*取到n

位有效數(shù)字，則其相對誤差上限為要保證其相對誤差小于0.001%，只要保證其上限滿足已知a1=3，則從以上不等式可解得n>6log6，即n6，應取*=3.14159。52注意：①準確值經(jīng)“四舍五入”后，都為有效數(shù)字；②有效數(shù)字位數(shù)相同，誤差可能不同；例如：但相同時，有效位數(shù)越多，誤差越小。③移動小數(shù)點時，不要改變有效數(shù)字；例如：④常數(shù)、系數(shù)、準確數(shù)有無數(shù)多個有效數(shù)字。例如：，，，

0.02030有4位有效數(shù)字，而0.0203只有3位有效。12300如果寫成0.123105，則表示只有3位有效數(shù)字。

數(shù)字末尾的0不可隨意省去！53按四舍五入原則寫出下列各數(shù)具有5位有效數(shù)字的近似數(shù)：解：按定義，187.93,的5位有效數(shù)字近似數(shù)是8.0000，而不是8，例187.9325,0.03785551,8.000033,2.7182818.上述各數(shù)具有5位有效數(shù)字的近似數(shù)分別是因為8只有1位有效數(shù)字.注意：0.037856,8.0000,2.7183.54加、減、乘、除運算的誤差為：

4、數(shù)值運算的誤差估計

（避免絕對值很大的數(shù)為乘數(shù)）（避免為很小的數(shù)為除數(shù)）

（避免兩相近數(shù)相減運算）5、函數(shù)的誤差估計當自變量有誤差時，計算函數(shù)值也會產(chǎn)生誤差，其誤差限可利用函數(shù)的Taylor展開式進行估計。

設是一元函數(shù)，的近似值為,以近似，其誤差限記作，可用Taylor展開

介于之間.取絕對值得假定與的比值不太大,,可忽略的高階項,于是可得計算函數(shù)的誤差限為

當為多元函數(shù)時計算,如果的近似值為,則的近似為于是函數(shù)值的誤差由Taylor展開,得：假定與的比值不太大,,可忽略的高階項,于是可得計算函數(shù)的誤差限為

于是誤差限為而的相對誤差限為(1.2.1)(1.2.2)例:已測得某場地長的值為,寬的值為,已知,.試求面積的絕對誤差限與相對誤差限.其中由式(1.2.1)得解:因

而于是絕對誤差限為相對誤差限為

數(shù)值計算在設計算法時首先關心的是由它產(chǎn)生的計算結果的穩(wěn)定性，而算法的穩(wěn)定性與舍入誤差是否增長密切相關。一個算法如果輸入數(shù)據(jù)有微小擾動（即誤差），而在計算過程中舍入誤差不增長，則稱此算法是數(shù)值穩(wěn)定的，否則稱其為數(shù)值不穩(wěn)定。

1.3數(shù)值算法設計的原則61（3）不在計算機數(shù)系中的數(shù)做四舍五入處理。例在四位浮點十進制數(shù)的計算機上計算1+104（1）加法先對階,后運算,再舍入；（2）乘法先運算,再舍入；=0.1000105=104=

0.10001105

=0.00001105+0.1000105

(對階，靠高階)解1+104=0.1000101+0.1000105

(浮點數(shù)形式)(運算)(舍入)計算機中數(shù)的計算特點例：求定積分的值.

解：直接積分可產(chǎn)生遞推公式若取初值可得遞推公式按公式就可以逐步算出注意此公式精確成立，且Whathappened?!不穩(wěn)定的算法！這就是誤差傳播所引起的危害!

NYBJ蝴蝶效應——紐約的一只蝴蝶翅膀一拍，風和日麗的北京就刮起臺風來了？！這是一個病態(tài)問題由題設中的遞推公式（1）可看出，

的誤差擴大了5倍后傳給

，因而初值

的誤差對以后各步這就造成的計算結果嚴重失真。計算結果的影響，隨著

的增大愈來愈嚴重。要怎么做才能解決這個問題呢?可求得I90.017，按改寫后的公式可逐次求得不妨設I9I10，于是由將公式變?yōu)?/p>

I80.019I70.021 I60.024I80.028 I40.034I30.043 I20.058I10.088 I00.182穩(wěn)定的算法！

在我們今后的討論中，誤差將不可回避，算法的穩(wěn)定性會是一個非常重要的話題。注：遞推公式(1)的舍入誤差以5的冪次增長進行傳播，因此是數(shù)值不穩(wěn)定的，而遞推公式(2)的舍入誤差在一定范圍內以0.2的冪次進行傳播，隨著n的增大，誤差逐步減少，因此該算法是數(shù)值穩(wěn)定的。

因此，可以看出數(shù)值不穩(wěn)定的算法是不能使用的，實際計算中對任何輸入數(shù)據(jù)都是數(shù)值穩(wěn)定的算法，稱為無條件穩(wěn)定。而對某些數(shù)據(jù)數(shù)值穩(wěn)定，對其它數(shù)據(jù)數(shù)值不穩(wěn)定的算法，稱為條件穩(wěn)定。1.簡化計算步驟，避免誤差積累。一般來說，計算機處理下列運算的速度為例：多項式求值：給定的x

求下列n次多項式的值。

解：1.用一般算法，即直接求和法；

2.逐項求和法；3.秦九韶方法(即Hornor算法）；先計算x2,x3,…,

xn,再作線性組合，需做2n-1次乘法和n次加法。解法一：直接求和法解法二：逐項求和法按順序依次計算每一項的值再求和，需做n(n+1)/2次乘法和n次加法。解法三：秦九韶算法（即Horner算法）只需做n次乘法和n次加法。且可以遞推實現(xiàn)。好處：①節(jié)省計算時間；②減少舍入誤差。2.要避免兩個相近的數(shù)相減在數(shù)值計算中，兩個相近的數(shù)作減法時有效數(shù)字會損失。例:

求的值。當x=1000，y

的準確值為0.01580

放大相對誤差限，導致計算結果有較大誤差！類似地

(2)若將原式改寫為則y=0.01581(1)直接相減有3位有效數(shù)字！只有1位有效數(shù)字當|x|<<1時：3.盡量避免絕對值太小的數(shù)作分母例：如分母變?yōu)?.0011，也即分母只有0.0001的變化時結果相差這么大!4.避免大數(shù)吃小數(shù)精確解為算法1：利用求根公式例：用單精度計算的根。在計算機內，109存為0.11010，1存為0.1101。做加法時，兩加數(shù)的指數(shù)先向大指數(shù)對齊，再將浮點部分相加。即1的指數(shù)部分須變?yōu)?010，則：1=0.00000000011010，取單精度時就成為：109+1=0.100000001010+0.000000001010=0.100000001010算法2：先解出再利用注：求和時從小到大相加，可使和的誤差減小。例：按從小到大、以及從