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

山東科技大學信息科學與工程學院數(shù)值分析

能夠做什么？

§1

Introduction應用問題舉例2、天體力學中的Kepler方程x是行星運動的軌道，它是時間t的函數(shù).全球定位系統(tǒng)：在地球的任何一個位置，至少可以同時收到4顆以上衛(wèi)星發(fā)射的信號

3、全球定位系統(tǒng)（GlobalPositioningSystem,GPS)記為其中，4、已經(jīng)測得在某處海洋不同深度處的水溫如下：深度（M）46674195014221634水溫（oC）7.044.283.402.542.13根據(jù)這些數(shù)據(jù)，希望合理地估計出其它深度（如500米，600米，1000米…）處的水溫5、用比較簡單的函數(shù)代替復雜的函數(shù)誤差為最小，即距離為最小（在不同的度量意義下）7、鋁制波紋瓦的長度問題建筑上用的一種鋁制波紋瓦是用一種機器將一塊平整的鋁板壓制而成的.假若要求波紋瓦長4英尺,每個波紋的高度(從中心線)為1英寸,且每個波紋以近似2π英寸為一個周期.求制做一塊波紋瓦所需鋁板的長度L.

這個問題就是要求由函數(shù)f(x)=sinx給定的曲線從x=0到x=48英寸間的弧長L.由微積分學我們知道,所求的弧長可表示為:上述積分稱為第二類橢圓積分,它不能用普通方法來計算.理論研究科學實驗科學計算計算數(shù)學諾貝爾獎得主,計算物理學家Wilson提出現(xiàn)代科學研究的三大支柱21世紀信息社會的兩個主要特征：“計算機無處不在”“數(shù)學無處不在”21世紀信息社會對科技人才的要求：--會用數(shù)學解決實際問題--會用計算機進行科學計算

科學方法論的巨大變革：如果說伽利略和牛頓在科學發(fā)展史上奠定了實驗和理論這兩大科學方法的支柱，那么由馮.諾依曼研制的現(xiàn)代電子計算機把計算推上了人類科學活動的前沿，使計算成為第三種方法。山東科技大學信息學院現(xiàn)代科學與工程計算——緒論數(shù)值計算方法是計算數(shù)學的一個主要組成部分，“什么是數(shù)值計算方法？”山東科技大學信息學院現(xiàn)代科學與工程計算——緒論它主要研究使用計算機求解各種科學與工程計算問題的數(shù)值方法（近似方法）;對求得的解的精度進行評估以及在計算機上實現(xiàn)求解等。

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

科學計算可視化是目前研究的熱門問題，下面的藝術(shù)圖形是基于科學計算的數(shù)據(jù)表示的例子山東科技大學信息學院現(xiàn)代科學與工程計算——緒論分形圖混沌圖山東科技大學信息學院現(xiàn)代科學與工程計算——緒論傳統(tǒng)的數(shù)值計算的主要研究內(nèi)容：1、數(shù)值逼近

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

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

ODE、PDE和有限元法4、最優(yōu)化方法無約束優(yōu)化與有約束優(yōu)化方法

現(xiàn)代計算方法：融進了機器學習計算、仿生計算、網(wǎng)絡計算、以數(shù)據(jù)為核心的計算和各種普適計算、非線性科學計算等內(nèi)容。山東科技大學信息學院現(xiàn)代科學與工程計算——緒論數(shù)值計算方法的主要特點借助計算機提供切實可行的數(shù)學算法.想的精確度;收斂且穩(wěn)定;誤差可以分析或估計.所提出的算法必須具有：可靠的理論分析;理時間復雜性好__指節(jié)省時間；空間復雜性好__指節(jié)省存儲量。計算復雜性好

通過數(shù)值實驗證明算法行之有效.山東科技大學信息學院現(xiàn)代科學與工程計算——緒論

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

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

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

把求解數(shù)學問題轉(zhuǎn)化為按一定次序只進行加，減，乘，除等基本運算.設計數(shù)值算法的出發(fā)點？山東科技大學信息學院現(xiàn)代科學與工程計算——緒論威爾金森（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成為第五位圖靈獎獲得者。教材

現(xiàn)代科學與工程計算孟大志劉偉（高等教育出版社）

參考書目數(shù)值分析孫志忠袁慰平等（東南大學出版社,第二版）

應用數(shù)值方法使用MATLAB和C語言

RobertJ.Schilling&SandraL.Harris（機械工業(yè)出版社）

數(shù)值分析基礎教程李慶揚編（高等教育出版社）

現(xiàn)代數(shù)值分析

李慶揚、易大義、王能超

編著（高等教育出版社）數(shù)值分析與科學計算JefferyJ.Leader著，張威，劉志軍，李艷紅等譯，（清華大學出版社)

§2

算法一、算法的概念

描述算法可以有不同的方式。例如，可以用日常語言和數(shù)學語言加以敘述，也可以借助形式語言（算法語言）給出精確的說明，也可以用框圖直觀地顯示算法的全貌。

定義：由基本運算及運算順序的規(guī)定所構(gòu)成的完整的解題步驟，稱為算法。例：求解二元一次聯(lián)立方程組用行列式解法：首先判別

（1）如果，則令計算機計算

輸出計算的結(jié)果x1，x2。（2）如果D=0，則或是無解，或有無窮多組解。是否為零，存在兩種可能：令通過求解過程，可以總結(jié)出算法步驟如下：S2計算S3如果則輸出原方程無解或有無窮多組解的信息;否則S1輸入S4輸出計算的結(jié)果輸入

D=a11a22-a12a21D=0開始輸出

x1,x2

結(jié)束

No輸出無解信息Yes二、算法優(yōu)劣的判別

計算量的大小存貯量邏輯結(jié)構(gòu)例：用行列式解法求解線性方程組:n階方程組，要計算n+1個n階行列式的值，總共需要做n!(n-1)(n+1)

次乘法運算。

n=20需要運算多少次？n=100?一、誤差的來源與分類從實際問題中抽象出數(shù)學模型

——模型誤差例:質(zhì)量為m的物體，在重力作用下,自由下落，其下落距離s

與時間t的關系是：

其中g(shù)

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

——觀測誤差求近似解——方法誤差(截斷誤差）例如，當函數(shù)用Taylor多項式

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

與0之間。在機器字長有限——舍入誤差

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

=3.1415926…

小數(shù)來代替無窮小數(shù)或用位數(shù)較少的小數(shù)來代替位數(shù)較多的有限小數(shù)，如：四舍五入后……在數(shù)值計算方法中，主要研究截斷誤差和舍入誤差（包括初始數(shù)據(jù)的誤差）對計算結(jié)果的影響！二、誤差的概念1、絕對誤差與絕對誤差限例:若用以厘米為最小刻度的尺去量桌子的長，大約為1.45米，求1.45米的絕對誤差。1.45米的絕對誤差=？不知道！是近似值的絕對誤差,簡稱為誤差。

定義：設是準確值，為

的一個近似值，稱但實際問題往往可以估計出不超過某個正數(shù)，即，則稱為絕對誤差限，有了絕對誤差限就可以知道的范圍為即落在內(nèi)。在應用上，常常采用下列寫法來刻劃的精度。2、相對誤差與相對誤差限定義：設是準確值，是近似值，是近似值的誤差，通常取為近似值的相對誤差，記作，稱一般情況下是不知道的，怎么辦？事實上，當較小時是的二次方項級,故可忽略不計.相應地，若正數(shù)滿足

則稱為的相對誤差限。3、有效數(shù)字定義：如果則說近似表示準確到小數(shù)后第位，并從這由上述定義第位起直到最左邊的非零數(shù)字之間的一切數(shù)字都稱為有效數(shù)字，并把有效數(shù)字的位數(shù)稱為有效位數(shù)。定義:若近似值的誤差限是某一位的半個單位,也即，若有位有效數(shù)字。則稱其中，是1到9中的一個數(shù)字；是0到9中一個數(shù)字；為整數(shù)，且該位到的左邊第一位非零數(shù)字共有位,就說有位有效數(shù)字。取作的近似值，就有三位有效數(shù)字；取作的近似值，就有五位有效數(shù)字。例如：注：

若一近似數(shù)是由原真值經(jīng)四舍五入得到，則必為有效數(shù).4、誤差限與有效數(shù)字的關系

則

至少具有位有效數(shù)字。Th1.1：

對于用式表示的近似數(shù)，若具有位有效數(shù)字，則其相對誤差限為反之，若的相對誤差限為Th1.2：

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

反之,若

則

不是有效數(shù)字，

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

§4

數(shù)值運算的誤差估計一、四則運算的誤差估計兩個近似數(shù)與,其誤差限分別為及,它們進行加減乘除運算得到的誤差限分別為二、函數(shù)誤差估計當自變量有誤差時，計算函數(shù)值也會產(chǎn)生誤差，其誤差限可利用函數(shù)的Taylor展開式進行估計。

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

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

當為多元函數(shù)時計算,如果的近似值為,則的近似為于是函數(shù)值的誤差由Taylor展開,得：于是誤差限為而的相對誤差限為(1.3.1)(1.3.2)例:已測得某場地長的值為,寬的值為,已知,.試求面積的絕對誤差限與相對誤差限.解:因

其中由式(1.3.1)得而于是絕對誤差限為相對誤差限為§5

算法的數(shù)值穩(wěn)定性

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

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

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

的誤差擴大了5倍后傳給

，因而初值

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

的增大愈來愈嚴重。要怎么做才能解決這個問題呢?可求得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)的舍入誤差在一定范圍內(nèi)以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)定。病態(tài)問題和條件數(shù)

如果問題的輸入數(shù)據(jù)有微小擾動，就會引起輸出結(jié)果數(shù)據(jù)（即解）的很大擾動，稱這樣的問題為病態(tài)問題。相反的情形稱為良態(tài)問題。對于病態(tài)的數(shù)學問題，用通常的算法求數(shù)值解都是不穩(wěn)定的。病態(tài)和良態(tài)是相對的，沒有嚴格的界限，通常用條件數(shù)大小來衡量問題的病態(tài)程度，條件數(shù)越大病態(tài)可能越嚴重。

條件數(shù)c(x)越大，f(x)的相對誤差越大，通常認為時，問題是病態(tài)的。1.要避免兩個相近的數(shù)相減在數(shù)值計算中，兩個相近的數(shù)作減法時有效數(shù)字會損失。例:

求的值。當x=1000，y的準確值為0.01580

§6數(shù)值計算中應該注意的一些原則類似地

(2)若將原式改寫為則y=0.01581(1)直接相減有3位有效數(shù)字！只有1位有效數(shù)字2.盡量避免絕對值太小的數(shù)作分母例：如分母變?yōu)?.0011，也即分母只有0.0001的變化時結(jié)果相差這么大!3.避免大數(shù)吃小數(shù)精確解為算法1：利用求根公式例：用單精度計算的根。在計算機內(nèi)，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：先解出再利用注：求和時從小到大相加，可使和的誤差減小。例：按從小到大、以及從大到小的順序分別計算1+2+3+…+40+1094.簡化計算步驟，避免誤差積累。一般來說，計算機處理下列運算的速度為例：多項式求值：給定的x求下列n次多項式的值。

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

2.逐項求和法；3.秦九韶方法(即Hornor算法）；算法的遞推性計算機上使用的算法常采用遞推化的形式，遞推化的基本思想是把一個復雜的計算過程歸結(jié)為簡單過程的多次重復。這種重復在程序上表現(xiàn)為循環(huán)。遞推化的優(yōu)點是簡化結(jié)構(gòu)和節(jié)省計算量。例：用秦九韶方法求多項式解：

Ka5-KvK00.008330.00833v0=a510.041670.04v1=v0x+a420.166670.15867v2=v1x+a330.50.46827v3=v2x+a2410.90635v4=v3x+a1510.81873v5=v4x+a0約翰·馮·諾依曼（JohnvonNeumann,1903-1957）美藉匈牙利人，1930年接受了普林斯頓大學客座教授的職位，西渡美國