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

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

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

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

第一章

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

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

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

現(xiàn)代復(fù)雜工程技術(shù)問題的解決步驟工程問題上機計算數(shù)學(xué)模型結(jié)果分析問題解答設(shè)計算法例1.1(易計算問題)(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)計算定積分(1<a<b)；(5)解常微分方程初值問題解：

(1)Cramer法則,其中D=|A|,Dj為由b置換D的第j列所得。(2)根據(jù)求根公式得x*=2;(3)P(x2)=;(4)根據(jù)積分公式得到;(5)根據(jù)常微分方程求解公式得例1.2(難計算問題)(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)計算定積分(1<a<b)；(5)解常微分方程初值問題解：例1.2同例1.1“差不多”？(1)計算量非常大；(2)無法求得x*的解析形式，只能求近似值；(3)f(x2)

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

計算機的計算能力也是有限的可行且高效的算法+計算機?。?！2數(shù)值算法的特點：

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

三類計算機算法

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

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

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

數(shù)值性

近似性

數(shù)值計算軟件FortranC++Matlab§1.2誤差分析的概念

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

截斷誤差與收斂性

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

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

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

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

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

r,稱

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

r

很小時，

r

/|x|。

誤差的四則運算見后準(zhǔn)確位數(shù)和有效數(shù)字(定義1.2)設(shè)x=0.a1a2an10m(m為整數(shù))(1.1)其中a1~an為0~9中一個數(shù)字且a10。如果

|x*-x|0.510k(1.2)即x的誤差不超過10-k位的半個單位則稱近似數(shù)x準(zhǔn)確到第k位小數(shù)，并說x有m+k位有效數(shù)字。

等價定義：如果近似值x的絕對誤差限不超過它某一位的半個單位，則從這一位起，直到最左邊的第一位非零數(shù)字為止的所有數(shù)字都稱為有效數(shù)字。并說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*的近似值，如果在從第一個非零數(shù)字開始的第n位進行四舍五入(即考慮第n+1位是舍還是入？)，x*和x的結(jié)果完全一致，則稱x有n位有效數(shù)字。

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

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

只有三位有效數(shù)字，但實際上的誤差比的誤差小，因此是的更好的近似值。通俗定義并不合理。2.截斷誤差與收斂性

截斷誤差：一個無限的數(shù)學(xué)極限過程用有限次運算近似計算產(chǎn)生的誤差。

例（無限）近似計算（有限）截斷誤差（余項公式）在0與x之間

算法的收斂性：該算法總可以通過提高計算量使得截斷誤差任意小。即余項0

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

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

m=12s

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

2.910393.41038(2-128

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

5.56103091.7910308(2-1024

21024)上溢出和下溢出00數(shù)值穩(wěn)定性誤差傳播問題:設(shè)函數(shù)y=f(x1,x2,,xn)是一個算法或模型，是變量xi的準(zhǔn)確值，而是變量xi的近似值。如果,且f的計算過程中沒有新的誤差產(chǎn)生，那么計算結(jié)果具有怎樣的精度？即算法的數(shù)值穩(wěn)定:計算過程中舍入誤差不會被嚴(yán)重放大誤差的傳播線性情形用嚴(yán)格估計非線性情形用線性近似絕對誤差傳播主要取決于條件數(shù)

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

條件數(shù)很大病態(tài)問題誤差的四則運算(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估計算法一:分部積分遞推公式In=1nIn-1,n=1,,20

I0=1-1/eI1I2…I20

誤差很大(見書P8)

，n

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

，不穩(wěn)定算法二：遞推公式In-1=(1In)/n,n=20,,1I20估計式中點I19…I1I0

誤差很小n-1

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

病態(tài)問題:很小的變化數(shù)據(jù)卻導(dǎo)致解產(chǎn)生了很大的變化。區(qū)別：收斂性和數(shù)值穩(wěn)定性主要源于算法，病態(tài)性主要是模型本身的原因。§1.3數(shù)值算法設(shè)計的一些要點設(shè)計算法基本原則計算精度：收斂性、穩(wěn)定性計算速度：計算量、收斂速度、多個CPU通信計算空間：存儲量注意事項病態(tài)問題速度細節(jié)(加法、乘法，函數(shù))計算多項式的值存儲細節(jié)(降維)計算多項式的值穩(wěn)定性細節(jié)(相近數(shù)相減，大數(shù)吃小數(shù)，分母接近0)死循環(huán)設(shè)置循環(huán)的上界。實數(shù)相等比較中間結(jié)果（要少顯示和輸出）速度細節(jié)使用秦九韶算法(Horner’srule)計算多項式的值可大大減少計算量直接計算，乘法的運算次數(shù):n+(n-1)+…+1+0=n(n+1)/2乘的運算次數(shù)：n次算法過程設(shè)計可使用遞推計算公式：

p0=an,

pk=pk-1x

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

即是多項式p(x)的值，算法過程只需n次乘法和n次加法，此算法稱為秦九韶算法.

p=an,p=px

+an-k(k=1,…,n)存儲細節(jié)求的小正根(取3位有效數(shù)字).

解只有一位有效數(shù)字.則具有3位有效數(shù)字.若改用由求根公式相近數(shù)相減大數(shù)吃小數(shù)1234+(0.4+0.3)=1235取4位有效數(shù)字計算：(1234+0.4)+0.3=1234問題：(x+y)+z