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

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

能夠做什么？

§1

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

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

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

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

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

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

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

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

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

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

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

希望：求近似解，但方法簡(jiǎn)單可行，行之有效（計(jì)算量小，誤差小,需存儲(chǔ)單元少等）,

以計(jì)算機(jī)為工具，易在計(jì)算機(jī)上實(shí)現(xiàn)。計(jì)算機(jī)運(yùn)算:

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

把求解數(shù)學(xué)問題轉(zhuǎn)化為按一定次序只進(jìn)行加，減，乘，除等基本運(yùn)算.設(shè)計(jì)數(shù)值算法的出發(fā)點(diǎn)？山東科技大學(xué)信息學(xué)院現(xiàn)代科學(xué)與工程計(jì)算——緒論威爾金森（JamesHardy.Wilkinson，1919-1986）Wilkinson是數(shù)值分析和數(shù)值計(jì)算的開拓者和奠基人。1940年，開始研究彈道的數(shù)學(xué)模型與數(shù)值計(jì)算。1946年成為Turing的助手，協(xié)助設(shè)計(jì)PilotACE計(jì)算機(jī)。1969年他當(dāng)選為英國(guó)皇家學(xué)會(huì)院士；1970年工業(yè)和應(yīng)用數(shù)學(xué)會(huì)(s1am)授予他馮·諾伊曼獎(jiǎng)；1987年他獲得美國(guó)數(shù)學(xué)會(huì)的chauvenet獎(jiǎng)。著名的美國(guó)阿爾貢國(guó)家實(shí)驗(yàn)室曾聘威爾金森為榮譽(yù)高級(jí)研究員并兩次向他授獎(jiǎng)。

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

1975年J.H.Wilkinson成為第五位圖靈獎(jiǎng)獲得者。教材

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

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

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

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

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

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

李慶揚(yáng)、易大義、王能超

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

§2

算法一、算法的概念

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

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

（1）如果，則令計(jì)算機(jī)計(jì)算

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

D=a11a22-a12a21D=0開始輸出

x1,x2

結(jié)束

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

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

次乘法運(yùn)算。

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

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

與時(shí)間t的關(guān)系是：

其中g(shù)

為重力加速度?！?誤差通過測(cè)量得到模型中參數(shù)的值

——觀測(cè)誤差求近似解——方法誤差(截?cái)嗾`差）例如，當(dāng)函數(shù)用Taylor多項(xiàng)式

近似代替時(shí)，數(shù)值方法的截?cái)嗾`差是

與0之間。在機(jī)器字長(zhǎng)有限——舍入誤差

用計(jì)算機(jī)、計(jì)算器和筆算，都只能用有限位

=3.1415926…

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

定義：設(shè)是準(zhǔn)確值，為

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

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

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

則

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

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

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

反之,若

則

不是有效數(shù)字，

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

§4

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

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

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

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

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

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

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

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

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

的誤差擴(kuò)大了5倍后傳給

，因而初值

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

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

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

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

因此，可以看出數(shù)值不穩(wěn)定的算法是不能使用的，實(shí)際計(jì)算中對(duì)任何輸入數(shù)據(jù)都是數(shù)值穩(wěn)定的算法，稱為無條件穩(wěn)定。而對(duì)某些數(shù)據(jù)數(shù)值穩(wěn)定，對(duì)其它數(shù)據(jù)數(shù)值不穩(wěn)定的算法，稱為條件穩(wěn)定。病態(tài)問題和條件數(shù)

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

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

求的值。當(dāng)x=1000，y的準(zhǔn)確值為0.01580

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

(2)若將原式改寫為則y=0.01581(1)直接相減有3位有效數(shù)字！只有1位有效數(shù)字2.盡量避免絕對(duì)值太小的數(shù)作分母例：如分母變?yōu)?.0011，也即分母只有0.0001的變化時(shí)結(jié)果相差這么大!3.避免大數(shù)吃小數(shù)精確解為算法1：利用求根公式例：用單精度計(jì)算的根。在計(jì)算機(jī)內(nèi)，109存為0.11010，1存為0.1101。做加法時(shí)，兩加數(shù)的指數(shù)先向大指數(shù)對(duì)齊，再將浮點(diǎn)部分相加。即1的指數(shù)部分須變?yōu)?010，則：1=0.00000000011010，取單精度時(shí)就成為：109+1=0.100000001010+0.000000001010=0.100000001010算法2：先解出再利用注：求和時(shí)從小到大相加，可使和的誤差減小。例：按從小到大、以及從大到小的順序分別計(jì)算1+2+3+…+40+1094.簡(jiǎn)化計(jì)算步驟，避免誤差積累。一般來說，計(jì)算機(jī)處理下列運(yùn)算的速度為例：多項(xiàng)式求值：給定的x求下列n次多項(xiàng)式的值。

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

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

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年接受了普林斯頓大學(xué)客座教授的職位，西渡美國(guó)