第一章數(shù)值的基本概念(刪減版)

數(shù)值分析

NumericalAnalysis于佳平東華大學(xué)Email：jpyu@教材《數(shù)值分析及其MATLAB實(shí)驗(yàn)》

姜健飛

吳笑千

胡良劍編

上課(2--17周)每周五8:15-9:45第二教學(xué)樓129室每個(gè)單周五10:05-11:35圖文3號(hào)機(jī)房(圖文信息中心)請(qǐng)按機(jī)號(hào)入座！成績(jī)的評(píng)定方法筆試考試：70%閉卷上機(jī)考試：20%平時(shí)成績(jī)：10%作業(yè)和答疑作業(yè)：雙周上課前交到講臺(tái)上

上機(jī)作業(yè)要在上機(jī)時(shí)檢查答疑：1）課前或課后2）2號(hào)學(xué)院樓449室677923313）jpyu@第一章

數(shù)值分析的基本概念

§1.1數(shù)值算法的研究對(duì)象

§1.2誤差分析的概念§1.3數(shù)值算法設(shè)計(jì)的一些要點(diǎn)

§1.1數(shù)值算法的研究對(duì)象研究對(duì)象數(shù)學(xué)分析、高等代數(shù)、概率論與數(shù)理統(tǒng)計(jì)都是精確數(shù)學(xué)，例如極限、導(dǎo)數(shù)、積分都是唯一的。數(shù)值分析不同，我們面對(duì)的問(wèn)題是理論上有解的，但我們沒(méi)有求解公式；另外一種情況，計(jì)算量過(guò)大，我們手工難以實(shí)現(xiàn)的。這樣的一類問(wèn)題，實(shí)際上都是無(wú)限的，但我們只能取有限項(xiàng)求解，因此得到的是近似解。近似解就有個(gè)近似程度，這個(gè)解就不是唯一的了，精確度不同，解就不同，距離真解誤差越小越好。研究過(guò)程

（理論上有解，而無(wú)求解公式或計(jì)算量過(guò)大難以用手工實(shí)現(xiàn)的數(shù)學(xué)問(wèn)題）實(shí)際問(wèn)題數(shù)學(xué)模型數(shù)值分析理論程序設(shè)計(jì)上機(jī)計(jì)算重點(diǎn)內(nèi)容研究并求解數(shù)學(xué)問(wèn)題的數(shù)值（近似）解的方法計(jì)算的目的不在于數(shù)據(jù)，而在于洞察事物。

－－理查德·哈明Thepurposeofcomputingisinsight，notnumbers.

－－Richard

Wesley

Hamming

理論分析

科學(xué)實(shí)驗(yàn)

科學(xué)計(jì)算地球外部大氣流動(dòng)模型應(yīng)用：大數(shù)據(jù)搜索、金融、核實(shí)驗(yàn)、飛行器、油田勘探、天氣預(yù)報(bào)......飛機(jī)外形優(yōu)化設(shè)計(jì)問(wèn)題數(shù)值分析課程的期望掌握各種解決數(shù)學(xué)問(wèn)題的數(shù)值方法對(duì)近似解進(jìn)行評(píng)估在計(jì)算機(jī)上實(shí)現(xiàn)求解仿真模擬1.例1.1(易計(jì)算問(wèn)題)(1)

求解線性方程組AX=b,其中A為3階可逆方陣，X=(x1,x2,x3)T;(2)求代數(shù)方程x2+x6=0在[0,4]上的根x*；(3)

已知y=P(x)為[x0,x1]上的直線，滿足P(x0)=y0,P(x1)=y1,x2(x0,x1),求P(x2)；(4)計(jì)算定積分(1<a<b)；(5)

解常微分方程初值問(wèn)題

解：

(1)Cramer法則,其中D=|A|,Dj為由b置換D的第j列所得。

(2)根據(jù)求根公式得x*=2;(3)P(x2)=;(4)根據(jù)積分公式得到;(5)根據(jù)常微分方程求解公式得例1.2(難計(jì)算問(wèn)題)(1)

求解線性方程組AX=B,其中A為30階可逆方陣，X=(x1,x2,,x30)T;(2)求超越方程xex=1在[0,1]上的根x*；(3)

已知y=f(x)為[x0,x1]上的函數(shù)，滿足f(x0)=y0,f(x1)=y1,x2(x0,x1),求f(x2)；(4)計(jì)算定積分(1<a<b)；(5)

解常微分方程初值問(wèn)題

解：例1.2同例1.1“差不多”

？(1)計(jì)算量非常大，31＊30?。?9次乘法；(2)無(wú)法求得x*的解析形式，只能求近似值；(3)f(x2)

試試；(4)無(wú)法找到原函數(shù)，考慮近似方法；(5)沒(méi)有解析解，數(shù)值解法求取近似解。利用計(jì)算機(jī)！但是：計(jì)算機(jī)的認(rèn)識(shí)能力是有限的

（例如C語(yǔ)言不能識(shí)別“積分”）計(jì)算機(jī)的計(jì)算能力也是有限的（例如例2(1),超級(jí)計(jì)算機(jī)“天河二號(hào)”每秒做33.86千萬(wàn)億次乘法，也需要591億年）解決方案：可行且高效的算法+計(jì)算機(jī)2數(shù)值算法的特點(diǎn)：

計(jì)算機(jī)算法對(duì)于給定的問(wèn)題和設(shè)備（計(jì)算機(jī)），一個(gè)算法是用該設(shè)備可理解的語(yǔ)言表示的，對(duì)解決這個(gè)問(wèn)題的一種方法的精確刻畫。計(jì)算機(jī)算法主要包含數(shù)值算法、非數(shù)值算法和軟計(jì)算方法三類。

數(shù)值計(jì)算軟件FortranC++Matlab三類計(jì)算機(jī)算法

數(shù)值算法主要指與連續(xù)數(shù)學(xué)模型有關(guān)的算法，如數(shù)值線性代數(shù)、方程求解、數(shù)值逼近、數(shù)值微積分、微分方程數(shù)值解和最優(yōu)化計(jì)算方法等；(本課程內(nèi)容)

非數(shù)值算法主要指與離散數(shù)學(xué)模型有關(guān)的算法，如排序、搜索、分類、圖論算法等；軟計(jì)算方法是近來(lái)發(fā)展的不確定性算法的總稱，包括神經(jīng)網(wǎng)絡(luò)計(jì)算、模糊邏輯、遺傳算法、螞蟻算法等。

數(shù)值算法的特點(diǎn)有窮性

數(shù)值性

近似性

§1.2誤差分析的概念

誤差限和有效數(shù)字

截?cái)嗾`差與收斂性

舍入誤差和數(shù)值穩(wěn)定性

數(shù)據(jù)誤差和病態(tài)問(wèn)題

1.誤差限和有效數(shù)字誤差和相對(duì)誤差(定義1.1)

設(shè)x*是某量的準(zhǔn)確值，x是x*的近似值稱x=x*-x

為x的誤差或絕對(duì)誤差。|x*-x|,稱為x的(絕對(duì))誤差限或精度，rx=(x*-x)/x*稱為x的相對(duì)誤差|(x*-x)/x*|

r,稱

r為x的相對(duì)誤差限。當(dāng)

r

很小時(shí)，

r

/|x|。

誤差的四則運(yùn)算見(jiàn)后準(zhǔn)確位數(shù)和有效數(shù)字(定義1.2)設(shè)x=0.a1a2an10m(m為整數(shù))(1.1)其中a1~an為0~9中一個(gè)數(shù)字且a10。如果|x*-x|0.510k(1.2)即x的誤差不超過(guò)10-k位的半個(gè)單位則稱近似數(shù)x準(zhǔn)確到第k位小數(shù)，并說(shuō)x有m+k位有效數(shù)字。

等價(jià)定義：如果近似值x的絕對(duì)誤差限不超過(guò)它某一位的半個(gè)單位，則從這一位起，直到最左邊的第一位非零數(shù)字為止的所有數(shù)字都稱為有效數(shù)字。并說(shuō)x“準(zhǔn)確”到這一位。例1.3(誤差限和有效數(shù)字)圓周率=3.1415926。x1=3.14;x2=3.141;x3=3.142;x4=3.1414解(1)x1=0.314101,x1=0.15926102,|x1|0.5102,有3位有效數(shù)字；(2)x2=0.5926103,|x2|0.5102,有3位有效數(shù)字；(3)x3=0.4073103,|x3|0.5103,有4位有效數(shù)字；(4)x4=0.1926103,|x4|0.5103,有4位有效數(shù)字。

有效數(shù)字概念的通俗定義

設(shè)x*是某量的準(zhǔn)確值，x是x*的近似值，如果在從第一個(gè)非零數(shù)字開(kāi)始的第n位進(jìn)行四舍五入(即考慮第n+1位是舍還是入？)，x*和x的結(jié)果完全一致，則稱x有n位有效數(shù)字。

與定義1.2的區(qū)別x*

未知，從而在數(shù)值分析中無(wú)法應(yīng)用。按照通俗定義，

只有三位有效數(shù)字，但實(shí)際上

的誤差比

的誤差小，因此是的更好的近似值。通俗定義并不合理。2.截?cái)嗾`差與收斂性

截?cái)嗾`差：一個(gè)無(wú)限的數(shù)學(xué)極限過(guò)程用有限次運(yùn)算近似計(jì)算產(chǎn)生的誤差。

例（無(wú)限）近似計(jì)算（有限）截?cái)嗾`差（余項(xiàng)公式）在0與x之間

算法的收斂性：該算法總可以通過(guò)提高計(jì)算量使得截?cái)嗾`差任意小。即

余項(xiàng)0

3.舍入誤差和數(shù)值穩(wěn)定性

舍入誤差:由于機(jī)器字長(zhǎng)的限制而產(chǎn)生的誤差機(jī)器數(shù)(二進(jìn)制0-1,離散)規(guī)格化浮點(diǎn)式:階碼m（用二進(jìn)制數(shù)表示）,字長(zhǎng)t,尾數(shù)(1=1)2m0.12t,

m=12s

單精度32位(4字節(jié)):t=23,s=7,符號(hào)2位,表示范圍2.910393.41038(2-128

2128)雙精度64位(8字節(jié)):t=52,s=10,符號(hào)2位,表示范圍5.56103091.7910308(2-1024

21024)上溢出和下溢出00數(shù)值穩(wěn)定性誤差傳播問(wèn)題:設(shè)函數(shù)y=f(x1,x2,,xn)是一個(gè)算法或模型，

是變量xi的準(zhǔn)確值，而

是變量xi的近似值。如果

,且f的計(jì)算過(guò)程中沒(méi)有新的誤差產(chǎn)生，那么計(jì)算結(jié)果

具有怎樣的精度？即算法的數(shù)值穩(wěn)定:計(jì)算過(guò)程中舍入誤差不會(huì)被嚴(yán)重放大誤差的傳播線性情形用嚴(yán)格估計(jì)非線性情形用線性近似絕對(duì)誤差傳播主要取決于條件數(shù)

相對(duì)傳播主要取決于條件數(shù)

條件數(shù)很大

病態(tài)問(wèn)題

誤差的四則運(yùn)算

(ab)=ab,r(ab)=[a/(ab)]ra[b/(ab)]rb(相近數(shù)相減不穩(wěn)定)(ab)

ba+abr(ab)

ra+rb(a/b)(1/b)a(a/b2)b(分母b0不穩(wěn)定)r(a/b)

rarb計(jì)算誤差限:例如：例1.5(數(shù)值穩(wěn)定性)

n=0,1,…,20估計(jì)

算法一:分部積分遞推公式

In=1nIn-1,n=1,,20

I0=1-1/eI1I2…I20

誤差很大(見(jiàn)書(shū)P8)

，n

=nn-1,20=(20!)0

，不穩(wěn)定算法二：遞推公式

In-1=(1In)/n,n=20,,1I20估計(jì)式中點(diǎn)

I19…I1I0

誤差很小n-1

=n/n,0=20/(20!)，穩(wěn)定4.數(shù)據(jù)誤差和病態(tài)問(wèn)題例1.6(病態(tài)問(wèn)題)（保留4位有效數(shù)字）x1=x2=x3=1x1=1.2203,x2=-0.3084,x3=2.2981.

病態(tài)問(wèn)題:很小的變化數(shù)據(jù)卻導(dǎo)致解產(chǎn)生了很大的變化。區(qū)別：收斂性和數(shù)值穩(wěn)定性主要源于算法，病態(tài)性主要是模型本身的原因

?！?.3數(shù)值算法設(shè)計(jì)的一些要點(diǎn)設(shè)計(jì)算法基本原則計(jì)算精度：收斂性、穩(wěn)定性計(jì)算速度：計(jì)算量、收斂速度、多個(gè)CPU通信計(jì)算空間：存儲(chǔ)量注意事項(xiàng)病態(tài)問(wèn)題速度細(xì)節(jié)(加法、乘法，函數(shù))計(jì)算多項(xiàng)式的值存儲(chǔ)細(xì)節(jié)(降維)計(jì)算多項(xiàng)式的值穩(wěn)定性細(xì)節(jié)(相近數(shù)相減(例)，大數(shù)吃小數(shù)(例)，分母接近0

(例))死循環(huán)

設(shè)置循環(huán)的上界。實(shí)數(shù)相等比較中間結(jié)果（要少顯示和輸出）速度細(xì)節(jié)使用秦九韶算法(Horner’srule)計(jì)算多項(xiàng)式的值可大大減少計(jì)算量直接計(jì)算，乘法的運(yùn)算次數(shù):n+(n-1)+…+1+0=n(n+1)/2乘的運(yùn)算次數(shù)：n次算法過(guò)程設(shè)計(jì)可使用遞推計(jì)算公式：

p0=an,pk=pk-1x

+an-k(k=1,…,n)最后得到的

p

即是多項(xiàng)式

p(x)的值，算法過(guò)程只需n次乘法和n次加法，此算法稱為秦九韶算法.

p=an,p=px

+an-k(k=1,…,n)存儲(chǔ)細(xì)節(jié)求

的小正根(取3位有效數(shù)字).

解

只有一位有效數(shù)字.則具有3位有效數(shù)字.