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

數(shù)值分析上課(2--17周)每周三8:15-9:45第二教學(xué)樓121室每個(gè)單周三10:05-11:35圖文3號(hào)機(jī)房(圖文信息中心三樓319室)教師：吳笑千2號(hào)學(xué)院樓理學(xué)院四樓449室答疑時(shí)間：每周二下午3:00-5:00放假和上課通知

1.中秋節(jié)期間2010年9月22日至24日放假，共3天。9月19日(星期日)上星期四（雙周）的課程，9月25日(星期六)上星期五（雙周）的課程。2.國(guó)慶節(jié)期間2010年10月1日至7日放假，共7天。9月26日(星期日)上星期三（雙周）的課程，10月9日(星期六)上星期四（雙周）的課程。

數(shù)值分析數(shù)值分析（numericalanalysis），是數(shù)學(xué)的一個(gè)分支，以數(shù)字計(jì)算機(jī)求解數(shù)學(xué)問(wèn)題的理論和方法為研究對(duì)象。-----

第一章

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

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

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

現(xiàn)代復(fù)雜工程技術(shù)問(wèn)題的解決步驟工程問(wèn)題上機(jī)計(jì)算數(shù)學(xué)模型結(jié)果分析問(wèn)題解答設(shè)計(jì)算法例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ì)算量非常大；(2)無(wú)法求得x*的解析形式，只能求近似值；(3)f(x2)

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

計(jì)算機(jī)的計(jì)算能力也是有限的可行且高效的算法+計(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ì)算方法三類。

三類計(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ù)值性

近似性

數(shù)值計(jì)算軟件FortranC++Matlab§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,字長(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例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.1650,x2=0.0003,x3=2.0004.

病態(tài)問(wèn)題:很小的變化數(shù)據(jù)卻導(dǎo)致解產(chǎn)生了很大的變化。區(qū)別：收斂性和數(shù)值穩(wěn)定性主要源于算法，病態(tài)性主要是模型本身的原因。§1.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ù)字.若改用由求根公式相近數(shù)相減大數(shù)吃小數(shù)1234+(0.4+0.3)=1235取4位有效數(shù)字計(jì)算：(1234+0.4)+0.3=1234問(wèn)題：(x+y)+z