數值分析

NumericalAnalysis于佳平東華大學Email：jpyu@教材《數值分析及其MATLAB實驗》

姜健飛

吳笑千

胡良劍編

上課(2--17周)每周五8:15-9:45第二教學樓129室每個單周五10:05-11:35圖文3號機房(圖文信息中心)請按機號入座！成績的評定方法筆試考試：70%閉卷上機考試：20%平時成績：10%作業和答疑作業：雙周上課前交到講臺上

上機作業要在上機時檢查答疑：1）課前或課后2）2號學院樓449室677923313）jpyu@第一章

數值分析的基本概念

§1.1數值算法的研究對象

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

§1.1數值算法的研究對象研究對象數學分析、高等代數、概率論與數理統計都是精確數學，例如極限、導數、積分都是唯一的。數值分析不同，我們面對的問題是理論上有解的，但我們沒有求解公式；另外一種情況，計算量過大，我們手工難以實現的。這樣的一類問題，實際上都是無限的，但我們只能取有限項求解，因此得到的是近似解。近似解就有個近似程度，這個解就不是唯一的了，精確度不同，解就不同，距離真解誤差越小越好。研究過程

（理論上有解，而無求解公式或計算量過大難以用手工實現的數學問題）實際問題數學模型數值分析理論程序設計上機計算重點內容研究并求解數學問題的數值（近似）解的方法計算的目的不在于數據，而在于洞察事物。

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

－－Richard

Wesley

Hamming

理論分析

科學實驗

科學計算地球外部大氣流動模型應用：大數據搜索、金融、核實驗、飛行器、油田勘探、天氣預報......飛機外形優化設計問題數值分析課程的期望掌握各種解決數學問題的數值方法對近似解進行評估在計算機上實現求解仿真模擬1.例1.1(易計算問題)(1)

求解線性方程組AX=b,其中A為3階可逆方陣，X=(x1,x2,x3)T;(2)求代數方程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)根據求根公式得x*=2;(3)P(x2)=;(4)根據積分公式得到;(5)根據常微分方程求解公式得例1.2(難計算問題)(1)

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

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

解常微分方程初值問題

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

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

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

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

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

數值計算軟件FortranC++Matlab三類計算機算法

數值算法主要指與連續數學模型有關的算法，如數值線性代數、方程求解、數值逼近、數值微積分、微分方程數值解和最優化計算方法等；(本課程內容)

非數值算法主要指與離散數學模型有關的算法，如排序、搜索、分類、圖論算法等；軟計算方法是近來發展的不確定性算法的總稱，包括神經網絡計算、模糊邏輯、遺傳算法、螞蟻算法等。

數值算法的特點有窮性

數值性

近似性

§1.2誤差分析的概念

誤差限和有效數字

截斷誤差與收斂性

舍入誤差和數值穩定性

數據誤差和病態問題

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

設x*是某量的準確值，x是x*的近似值稱x=x*-x

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

r,稱

r為x的相對誤差限。當

r

很小時，

r

/|x|。

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

等價定義：如果近似值x的絕對誤差限不超過它某一位的半個單位，則從這一位起，直到最左邊的第一位非零數字為止的所有數字都稱為有效數字。并說x“準確”到這一位。例1.3(誤差限和有效數字)圓周率=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位有效數字；(2)x2=0.5926103,|x2|0.5102,有3位有效數字；(3)x3=0.4073103,|x3|0.5103,有4位有效數字；(4)x4=0.1926103,|x4|0.5103,有4位有效數字。

有效數字概念的通俗定義

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

與定義1.2的區別x*

未知，從而在數值分析中無法應用。按照通俗定義，

只有三位有效數字，但實際上

的誤差比

的誤差小，因此是的更好的近似值。通俗定義并不合理。2.截斷誤差與收斂性

截斷誤差：一個無限的數學極限過程用有限次運算近似計算產生的誤差。

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

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

余項0

3.舍入誤差和數值穩定性

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

m=12s

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

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

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

是變量xi的準確值，而

是變量xi的近似值。如果

,且f的計算過程中沒有新的誤差產生，那么計算結果

具有怎樣的精度？即算法的數值穩定:計算過程中舍入誤差不會被嚴重放大誤差的傳播線性情形用嚴格估計非線性情形用線性近似絕對誤差傳播主要取決于條件數

相對傳播主要取決于條件數

條件數很大

病態問題

誤差的四則運算

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

ba+abr(ab)

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

rarb計算誤差限:例如：例1.5(數值穩定性)

n=0,1,…,20估計

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

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

I0=1-1/eI1I2…I20

誤差很大(見書P8)

，n

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

，不穩定算法二：遞推公式

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

I19…I1I0

誤差很小n-1

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

病態問題:很小的變化數據卻導致解產生了很大的變化。區別：收斂性和數值穩定性主要源于算法，病態性主要是模型本身的原因

。§1.3數值算法設計的一些要點設計算法基本原則計算精度：收斂性、穩定性計算速度：計算量、收斂速度、多個CPU通信計算空間：存儲量注意事項病態問題速度細節(加法、乘法，函數)計算多項式的值存儲細節(降維)計算多項式的值穩定性細節(相近數相減(例)，大數吃小數(例)，分母接近0

(例))死循環

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

p0=an,pk=pk-1x

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

p

即是多項式

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

p=an,p=px

+an-k(k=1,…,n)存儲細節求

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

解

只有一位有效數字.則具有3位有效數字.