數(shù)值分析1(數(shù)值分析概論)

趙熙樂

photographyer@主頁:/shiziduiwu/teainfo.php?teacher=zhaoxileGoogleScholar:.hk/citations?user=88Zs8pAAAAAJ&hl=en百度網(wǎng)盤賬號：matrix2007603密碼：analysis2014*Humanbeingsareincrediblyslow,inaccurate,andbrilliant.Computersareincrediblyfast,accurate,andstupid.Togethertheyarepowerfulbeyondimagination.*數(shù)值分析(NumericalAnalysis)研究內(nèi)容:算法的構(gòu)造與分析近似的手段構(gòu)造適合計算機的算法

化大為小、化繁為簡、化難為易分析近似對計算結(jié)果的影響

圍繞病態(tài)性、收斂性、穩(wěn)定性和復(fù)雜度展開研究用計算機求解數(shù)學(xué)問題的數(shù)值方法(算法)及其相關(guān)理論。一、數(shù)值分析概論*數(shù)值分析的特點:近似替代:在誤差允許的范圍內(nèi),用近似解代替精確解或有限次計算代替無限次的計算遞推性:將復(fù)雜計算過程歸結(jié)為一系列適合計算機計算的簡單過程重復(fù)數(shù)值模擬:還要通過數(shù)值模擬驗證算法行之有效。數(shù)值模擬和數(shù)學(xué)理論一樣,都是數(shù)值分析的重要研究手段。*推動科學(xué)和社會發(fā)展Computationalsciencehasbecomethethirdpillarofscientificenterprise(科學(xué)研究的第三種方法),apeeralongsidetheoryandphysicalexperiment——摘自2005年美國總統(tǒng)顧問委員會報告大規(guī)模、高維數(shù)、多尺度、非線性、不適定、長時間、

復(fù)雜區(qū)域*趣例1:線性方程組求解*趣例2:特征值與特征向量計算*趣例3:數(shù)據(jù)插值*趣例4:Poisson方程*推薦書單[1]白峰杉,數(shù)值計算引論(高教)[2]李慶揚

關(guān)治

白峰杉,數(shù)值計算原理(清華)[3]李慶揚王能超易大義,數(shù)值分析(清華)[4]C.Moler,NumericalComputingwithMatlab[5]R.

Burden

J.Fairs,NumericalAnalysis[6]A.Quarteronietal,NumericalMathematics[7]王能超,算法演化論*數(shù)據(jù)觀測數(shù)學(xué)建模數(shù)值方法程序設(shè)計數(shù)據(jù)結(jié)果觀測誤差模型誤差截斷誤差舍入誤差二、誤差與有效數(shù)字將地球考慮成一個球體,設(shè)R為地球半徑,h為衛(wèi)星高度,計算覆蓋面積參考P.190*截斷誤差:由于問題不能精確求解,數(shù)值方法求得的近似解和精確解之間的誤差。微積分中sinx

可展開為例1但計算機計算時,常用前幾項來代替精確解,即拋棄了無窮級數(shù)的后段,這樣就產(chǎn)生了截斷誤差。

當(dāng)|x|很小時,常用x代替sinx,其截斷誤差大約為x3/6。

*尾數(shù)部階碼部

舍入誤差:一個非零的二進制一般的描述形式為計算機表示的數(shù)只有有限多個,且同時只有有限精度,這個有理數(shù)的子集稱為浮點數(shù)。絕大部分實數(shù)在計算機上總不能精確表示,總要經(jīng)“舍”或“入”而由一個與之相近的浮點數(shù)代替,由此引起的誤差稱為舍入誤差。*

假設(shè)某一數(shù)據(jù)的準確值為

x*,其近似值為x,則稱

而稱為

x

的相對誤差。誤差的有關(guān)概念

e(x)=x

-x*

為

x的絕對誤差。*如果存在一個適當(dāng)小的正數(shù)ε,使得

則稱ε為絕對誤差限。

稱εr為相對誤差限。

如果存在一個適當(dāng)小的正數(shù)εr,使得

*有效數(shù)字概念取的有限位數(shù)如下(≈3.1415926)取

x1=3.14,3位有效數(shù)字;取

x2=3.1416,5位有效數(shù)字。若近似值x的絕對誤差限是某一位上的半個單位,該位到x的第一位非零數(shù)字一共有n

位,則稱近似值x有n位有效數(shù)字。*用科學(xué)計數(shù)法,記

n

位有效數(shù)字的相對誤差限滿足：其中都是0~9中的任一整數(shù),且。有效數(shù)字和誤差的關(guān)系若絕對誤差限滿足：

則稱x

有n

位有效數(shù)字。*例2

已知

的十進制浮點數(shù)第一位是5,要使近似值的相對誤差限小于0.1%,問浮點數(shù)的有效數(shù)字的位數(shù)至少應(yīng)該為多少？解:利用不等式

所以浮點數(shù)的有效數(shù)字位數(shù)至少應(yīng)取3位。取n≥3,有

|er(x)|≤10-3*函數(shù)計算的誤差估計(準確值

y*=f(x*))

同理所以數(shù)值運算的誤差估計*算術(shù)運算的誤差估計*三、算法設(shè)計的基本原則

穩(wěn)定:算法控制誤差的傳播和積累以保證計算結(jié)果有足夠的精度

存儲:算法所需的存儲空間

效率:算法所需的運算次數(shù)*1.減少運算次數(shù)

不僅能提高計算效率,而且能減少誤差的積累。(b)利用秦九韶算法：(a)計算每一項再求和：例3*

Moore'sLaw集成電路上可容納的晶體管數(shù)目約每隔18個月便會增加一倍,性能也將提升一倍。*2.減少存儲量*3.構(gòu)造數(shù)值穩(wěn)定的計算方法計算機浮點數(shù)系統(tǒng)的特點:一個算法如果輸入數(shù)據(jù)有誤差,在計算過程中舍入誤差不增長,則此算法是數(shù)值穩(wěn)定;否則此算法數(shù)值不穩(wěn)定。浮點數(shù)是有限精度的,如IEEE的雙精度浮點數(shù),其精度eps=2^(-52),大約是2.2204e-16。有限的精度會導(dǎo)致舍入誤差。但舍入誤差并不可怕,關(guān)鍵是在算法設(shè)計中控制舍入誤差的傳播、放大和積累。*防止大數(shù)“吃掉”小數(shù)

例如a=1013和b=4,假設(shè)兩數(shù)在具有12位浮點數(shù)計算機系統(tǒng)中相加a+b=1013+4

=0.10000000000000

×1014

+0.00000000000004

×1014

(機器中相等)=0.100000000000×1014

*避免絕對值小的數(shù)作除數(shù)

*避免兩個相近數(shù)相減

如果y≈x,現(xiàn)分析兩個數(shù)的近似數(shù)作減法所得結(jié)果的誤差。設(shè)z=y–x,則利用誤差估計相對誤差估計

當(dāng)y≈x

時,有z≈0,計算結(jié)果的相對誤差限很大。*設(shè)法控制誤