數(shù)值分析-計算方法

1、數(shù) 值 分 析,上海大學機自學院,第一章 緒 論§1.1 課程主要內(nèi)容 1、非線性方程數(shù)值解法 2、線性方程組的數(shù)值解法 3、插值方法 4、數(shù)值積分 5、常微分方程初值問題的數(shù)值解法,§1.2 數(shù)值算法概論 數(shù)值算法是利用計算機求解數(shù)學問題近似解的方法，所獲近似解也稱為原問題的數(shù)值解或逼近解。,重點研究數(shù)值算法構(gòu)造及其相關(guān)理論，包括誤差分析，算法收斂性和穩(wěn)定等。,實際問題

2、,,數(shù)學模型,,構(gòu)造數(shù)值算法,,程序設計,獲取近似解,,數(shù)值算法，不僅僅是單純的數(shù)學公式，而是指解題方案準確而完整的描述。,算法優(yōu)劣主要取決于:1、計算開銷2、誤差控制,數(shù)值方法是一門與計算機應用密切結(jié)合的實用性很強的學科；思維方法是歸納法，核心問題是“誤差”或誤差分析。數(shù)值方法這門課程討論連續(xù)變量問題又要討論離散變量問題，關(guān)心的是數(shù)值結(jié)果。數(shù)值分析、計算數(shù)學、計算方法或數(shù)值方法這門課程已成為近代數(shù)學的一個重要分支。,例1.1

3、多項式求值的秦九韶算法 P(x)=a0+a1x+a2x2+…+anxn,算法①： 令 tk=xk uk=a0+a1x+…+akxk則得遞推公式 tk=xtk-1 uk=uk-1+aktk

4、 初值 t0=1 , u0=a0,(k=1,2,…,n),,顯然，由算法①計算n次多項式P(x)值所需的乘法次數(shù)為2n 。,算法②（秦九韶算法，我國宋代數(shù)學家） P(x)=a0+a1x+a2x2+…+anxn P(x)=a0+x (a1+a2x+…+anxn-1)

5、 P(x)=a0+x (a1+x (a2+…+anxn-2)) P(x)=a0+x (a1+…+x (an-1+anx) …)顯然，由里層往外一層一層的計算，僅需n次乘法運算，比算法①節(jié)省一半的計算量。,,,,,秦九韶算法 令 (p=0) v0=an (p=1) v1=anx+an-1=v0x+an-1

6、 (p=2) v2=(anx+an-1)x+an-2=v1x+an-2 …… (p=k) vk=vk-1x+an-k ...... (p=n) vn=vn-1x+a0,v0=an vk=vk-1x+an-k (k=1,2,…,n) P(x)=vn,例1.2 計

7、算積分解：通過直接計算可產(chǎn)生如下遞推公式 ， （1.1） 由經(jīng)典微積分知識可推得In具有如下性質(zhì)(1) (2) 單調(diào)遞減(3) (4)直接根據(jù)公式(1.1)，從n=1計算到n

8、=30 。結(jié)果為,表1-1從n=18開始，計算值出現(xiàn)異常。原因是從第n-1步計算到第n步時，第n-1步的誤差被放大了5倍。,算法改造：由性質(zhì)(4)，取遞推公式改寫為 （1.2）從n=30計算到n=1。由于該算法每向后推進一步，其誤差便減少5倍，

9、可期望獲得符合原積分性態(tài)的數(shù)值結(jié)果。計算結(jié)果見表1-2。,表1-2由此列可知，算法的設計十分重要，關(guān)系到計算結(jié)果是否真實可信。,§1.3 誤差 實際問題的求解過程中，一般會產(chǎn)生誤差。誤差的產(chǎn)生是正常的，不可避免的。,實際問題,數(shù)學模型,問題的解,,,模型誤差,觀測誤差,截斷誤差,舍入誤差,,,,,本課程中，僅考慮數(shù)值計算過程所帶來的誤差，即截斷誤差和舍入誤差。,截斷誤差 計算過

10、程中，往往將解題方案加工成算術(shù)運算與邏輯運算的有限序列，這種加工過程常表現(xiàn)為無窮過程的截斷，由此產(chǎn)生的誤差稱為截斷誤差。 … …,用計算機計算 𝑒 𝑥 時，只能取有限項 … 截斷誤差為,舍入誤差 計算過程中數(shù)

11、據(jù)的位數(shù)可能很多，甚至為無窮小數(shù)，受計算機字長限制，用機器代碼表示的數(shù)據(jù)必須舍入成一定的位數(shù)，由此產(chǎn)生的誤差稱為舍入誤差。,定義1.1 設 𝑥 ? 是某量的精確值，𝑥是其近似值，則稱差𝑒= 𝑥 ? ?𝑥為𝑥的絕對誤差。 一般而言， 𝑥 ? 未知，直接確定e是困難的，常用|e|≤ε表征絕對誤差，

12、ε稱為絕對誤差限。,定義1.2 在定義1.1的假設條件下，稱比值𝑒𝑟=𝑒/ 𝑥 ? 為近似值得相對誤差。 通常用|er|≤εr表征相對誤差， εr稱為相對誤差限。因 𝑥 ? 未知，常用𝑒𝑟=𝑒/𝑥表示相對誤差。,通常近似值的精度用所謂有效數(shù)字位數(shù)來表征，即近似值 

13、9909; 的絕對誤差限是它某一位的半個單位，則稱該近似值“準確”到這一位，且這一位直到前面第一個非零數(shù)字為止的所有數(shù)字均為有效數(shù)字。,如圓周率π的近似值為𝑥=3.142，其絕對誤差限為 | π-𝑥|=0.000407…<0.0005=(0.5) ×101-4則近似值𝑥有4位有效數(shù)字，近似值𝑥準確到小數(shù)點后第3位。,小數(shù)點

14、后第3位半個單位,定義1.3 若 𝑥 ? 的近似值𝑥=±0.𝑥1𝑥2 ? 𝑥 𝑛 ×10m，其中𝑥1 ≠0，諸𝑥𝑖 ∈{0,1,2,…,9}，𝑚為整數(shù)，且 |𝑥- 𝑥 ? | ≤(0.5)

15、 × 10 𝑚?𝑝 ，1 ≤𝑝 ≤𝑛則稱近似值𝑥有𝑝位有效數(shù)字或稱𝑥準確到 10 𝑚?𝑝 位。,定理1.1 設近似值𝑥=±0.𝑥1𝑥2 ? 𝑥 𝑛 ×10m有𝑛位有

16、效數(shù)字，則其相對誤差限為 𝜀 𝑟 =(1/2𝑥1) × 10 ?𝑛+1,定理1.2 設近似值𝑥=±0.𝑥1𝑥2 ? 𝑥 𝑛 ×10m的相對誤差限為 𝜀 𝑟 =(1/2(ү

17、09;1+1)) × 10 ?𝑛+1 ，則近似值𝑥有𝑛位有效數(shù)字。,證明：定理1.1因為𝑥=±0.𝑥1𝑥2 ? 𝑥 𝑛 × 10 𝑚 ，故有 𝑥 1 × 10 𝑚?1 ≤ 𝑥

18、≤( 𝑥 1 +1)× 10 𝑚?1 當𝑥有𝑛位有效數(shù)字時 𝜀 𝑟 = 𝑥 ? ?𝑥 𝑥 ≤ 0.5× 10 𝑚?𝑛 𝑥 1 × 10 𝑚?1 = 1 2 w

19、909; 1 × 10 ?𝑛+1 定理1.2 𝑥 ? ?𝑥 ≤ 𝑥 𝜀 𝑟 ≤( 𝑥 1 +1)× 10 𝑚?1 × 1 2 𝑥 1 +1 × 10 ?𝑛+1 = 1 2 

20、5; 10 𝑚?𝑛 所以𝑥有𝑛位有效數(shù)字,例1.3 下列近似值有幾位有效數(shù)字，其相對誤差是多少？（1） 𝑥 ? =𝑒，𝑥=2.71828（2） 𝑥 ? =0.030021，𝑥=0.0300解：（1） 𝑥 ? =𝑒=2.7182818284…

21、 𝑥 ? ?𝑥 =0.0000018…< 1 2 × 10 1?6 近似值𝑥=2.71828有6位有效數(shù)字 （2） 𝑥 ? ?𝑥 =0.000021< 1 2 × 10 ?1?3 近似值𝑥=0.0300有3位有效數(shù)字,例1.4 為使𝜋的近似值的相對誤差小

22、于0.001%，至少應取幾位有效數(shù)字。解：假定𝜋的近似值有𝑛位有效數(shù)字，則其相對誤差上限為 𝜀 𝑟 ≤ 1 2 𝑥 1 × 10 ?𝑛+1 這里 𝑥 1 =3，依題意，應有 𝜀 𝑟 ≤ 1 2 𝑥 1 × 10 ?&

23、#119899;+1 6?lg6即𝑛≥6，應取近似值3.14159,函數(shù)值和算術(shù)運算的誤差估計 設一元函數(shù)𝑓(𝑥)具有二階連續(xù)導數(shù)，自變量的準確值為 𝑥 ? ，近似值為𝑥 ，將函數(shù)𝑓(𝑥)在𝑥處做級數(shù)展開 𝑓 𝑥 ? =𝑓 𝑥 + &

24、#119891; 𝑥 𝑥 ? ?𝑥 + 1 2 𝑓 2 (𝜃) 𝑥 ? ?𝑥 2 于是 𝑓 𝑥 ? ?𝑓 𝑥 ≤ 𝑓 𝑥 𝑥 ? ?𝑥 + 1 2 w

25、891; (2) 𝜃 𝑥 ? ?𝑥 2 當 𝑥 ? ?𝑥 較小時，可以忽略其平方項 1 2 𝑓 (2) 𝜃 𝑥 ? ?𝑥 2 計為0,于是 𝑓 𝑥 ? ?&

26、#119891; 𝑥 ≈ 𝑓 𝑥 𝑥 ? ?𝑥 𝑓 𝑥 ? ?𝑓 𝑥 𝑓 𝑥 ≈ 𝑓 𝑥 𝑓 𝑥 𝑥 ? ?w

27、909; 例1.5 設𝑥>0， 𝑥的相對誤差為𝛿，求ln𝑥的絕對誤差。 例1.6 設𝑥的相對誤差為2%，求 𝑥 𝑛 的相對誤差。,對多元函數(shù)𝑓 𝑥 1 , 𝑥 2 ,?, 𝑥 

28、9899; ，若自變量的準確值 𝑥 1 ? , 𝑥 2 ? , ?, 𝑥 𝑛 ? 近似值為 𝑥 1 , 𝑥 2 ,?, 𝑥 𝑛 取多元函數(shù)𝑓 𝑥 1 , &

29、#119909; 2 ,?, 𝑥 𝑛 的Taylor展式的一階項，得多元函數(shù)絕對誤差及相對誤差的估計式 𝑒= 𝑖=1 𝑛 𝜕𝑓 𝑥 1 , 𝑥 2 ,?, 𝑥 𝑛 𝜕 𝑥 𝑖

30、 𝑥 𝑖 ? ? 𝑥 𝑖 𝑒 𝑟 = 𝑖=1 𝑛 𝜕𝑓 𝑥 1 , 𝑥 2 ,?, 𝑥 𝑛 𝜕 𝑥 𝑖 &

31、#119909; 𝑖 ? ? 𝑥 𝑖 𝑓 𝑥 1 , 𝑥 2 ,?, 𝑥 𝑛,四則運算的絕對誤差估計式 𝑒 𝑥 1 ± 𝑥 2 =𝑒 𝑥 1 +𝑒 &

32、#119909; 2 𝑒 𝑥 1 𝑥 2 = 𝑥 2 𝑒 𝑥 1 + 𝑥 1 𝑒 𝑥 2 𝑒 𝑥 1 𝑥 2 = 𝑥 2

33、 𝑒 𝑥 1 + 𝑥 1 𝑒 𝑥 2 𝑥 2 2 , 𝑥 2 ≠0,誤差對計算結(jié)果的影響：例1.7 用中心差商公式求f(x)= 在x=2的導數(shù)：理論上，步長h愈小，計算結(jié)果愈準確。假定受計算機字長限制，只能取5位有效數(shù)字，于是 h=0.1

34、 h=0.0001,4位有效數(shù)字,例1.8 考察如下病態(tài)方程組 準確解為： x1=x2=x3=1若將系數(shù)舍入成3位有效數(shù)字，則有其解為x1=1.09，x2=0.488，x3=1.49系數(shù)改變不大，但近似解與精確解出入太大。,§1.4 避免誤差擴大的幾個常用原則 1、簡化計算步驟，減少運算次數(shù) 2、避免兩個相近數(shù)相減，導致

35、有效數(shù)字損失 a1=0.12345,a2=0.12346 a2-a1=0.00001 僅剩一位有效數(shù)字 解決方法 （1） （2） ， （3） ，,3、避免小數(shù)做除數(shù)，放大誤差4、注意運算次序，防止大數(shù)“吃掉”小數(shù) a=1234578，0<bi<1 ，i=1,2,…

36、,100 在具有8位浮點數(shù)的計算機上，計算 a+b1+b2+ … +b100 如果從左依次做加法運算，則有 a+b1=a， (a+b1)+b2=a+b2=a, …… a+b1+b2+ … +b100=a 這里bi<1被當作數(shù)值0 正確方法 先計算 𝑖=1 100 𝑏&

37、#119894; 再與𝑎求和,§1.5 化粗為精的松弛方法 1、松弛法 設F0與F1為準確值F*的兩個近似值 取F0與F1的加權(quán)平均作為新的近似值 𝐹 =(1-𝜔)F0+𝜔F1 權(quán)系數(shù)0<𝜔<1稱為松弛因子 2、超松弛法

38、 如果F0與F1有優(yōu)劣之分，譬如F0為劣F1為優(yōu) 𝐹 =(1+𝜔)F1-𝜔F0=F1+𝜔(F1-F0),割圓術(shù)阿基米德 𝜋≈3.14祖沖之 3.1415926 <𝜋<3.1415927 祖沖之之前的劉徽從計算圓內(nèi)正6邊形面積S6開始一直計算到圓內(nèi)

39、正192邊形面積S192，圓半徑r=10，其中 S96=313 584 625 ， S192=314 64 625 換算成圓周率后分別約為𝜋≈3.14利用超松弛法，取𝜔= 36 105,𝑆 =S192+ 36 105 (S192-S96)=314 4 25 該結(jié)果相當于圓內(nèi)正3072邊形的面積，換算成圓周率，得

40、 𝜋≈3.1416比阿基米德的圓周率精度提高了兩個數(shù)量級 如果取𝜔= 1 3 ，則可得圓周率 𝜋≈3.14159265相當于計算到圓內(nèi)正24576邊形面積,§1.6 向量范數(shù)與矩陣范數(shù)定義1.4 稱n維實空間 上的一個非負函數(shù) 為范數(shù)，若其滿足（1）

41、 當且僅當（2） ， 及（3） ， 。 對于一維實空間R而言， 即為絕對值 。對于n維向量，將主要涉及l(fā)p(p =1,2,…)范數(shù)： ，,特別，l∞范數(shù)為 。

42、定理1.3 若 與 為Rn上的任意兩種范數(shù)，則存在正常數(shù)C2≥C1使得 ， 。定義1.5 設有向量序列{X(k)∈Rn|X(k)=( , ,…, }T ,若 ，i=1,2,…,n則稱序列{X(k)}收斂域向量X =(x1,x2,…,x

43、n)T 。,定理1.4 在空間Rn中，序列{X(k)}收斂于向量X的充要條件是存在范數(shù) ，使得定義1.6 設A為n階方陣， 為Rn中的某范數(shù)，則稱 為矩陣A的從屬于向量范數(shù)的范數(shù)，記作 。,矩陣范數(shù)的性質(zhì)：（1）對任意n階方陣A有 ，且 當且僅當A=0；（2）對任意實數(shù)k及任意n階方陣A，有

44、 ；（3）對任意兩個n階方陣A，有 ， ；（4）對 及任意n階方陣A，有 性質(zhì)（4）稱為矩陣A及向量X的相容性。,定理1.5 設有n階方陣A=(aij)，則與l1，l2

45、，l∞范數(shù)相容的矩陣范數(shù)分別為 其中 為矩陣的譜半徑，其滿足 為方陣B的特征值。定理1.6 A為n階方陣，則,定理1.7 ?𝐴∈ 𝐹 𝑛×𝑛 ， l