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

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

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

3、多項(xiàng)式求值的秦九韶算法 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),,顯然，由算法①計(jì)算n次多項(xiàng)式P(x)值所需的乘法次數(shù)為2n 。,算法②（秦九韶算法，我國(guó)宋代數(shù)學(xué)家） 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) …)顯然，由里層往外一層一層的計(jì)算，僅需n次乘法運(yùn)算，比算法①節(jié)省一半的計(jì)算量。,,,,,秦九韶算法 令 (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 計(jì)

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

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

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

10、程中，往往將解題方案加工成算術(shù)運(yùn)算與邏輯運(yùn)算的有限序列，這種加工過(guò)程常表現(xiàn)為無(wú)窮過(guò)程的截?cái)啵纱水a(chǎn)生的誤差稱為截?cái)嗾`差。 … …,用計(jì)算機(jī)計(jì)算 𝑒 𝑥 時(shí)，只能取有限項(xiàng) … 截?cái)嗾`差為,舍入誤差 計(jì)算過(guò)程中數(shù)

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

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

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

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

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

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

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

18、≤( 𝑥 1 +1)× 10 𝑚?1 當(dāng)𝑥有𝑛位有效數(shù)字時(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ù)字，其相對(duì)誤差是多少？（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 為使𝜋的近似值的相對(duì)誤差小

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

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

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

25、891; (2) 𝜃 𝑥 ? ?𝑥 2 當(dāng) 𝑥 ? ?𝑥 較小時(shí)，可以忽略其平方項(xiàng) 1 2 𝑓 (2) 𝜃 𝑥 ? ?𝑥 2 計(jì)為0,于是 𝑓 𝑥 ? ?&

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

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

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

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

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

31、#119909; 𝑖 ? ? 𝑥 𝑖 𝑓 𝑥 1 , 𝑥 2 ,?, 𝑥 𝑛,四則運(yùn)算的絕對(duì)誤差估計(jì)式 𝑒 𝑥 1 ± 𝑥 2 =𝑒 𝑥 1 +𝑒 &

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

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

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

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

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

37、#119894; 再與𝑎求和,§1.5 化粗為精的松弛方法 1、松弛法 設(shè)F0與F1為準(zhǔn)確值F*的兩個(gè)近似值 取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 祖沖之之前的劉徽從計(jì)算圓內(nèi)正6邊形面積S6開(kāi)始一直計(jì)算到圓內(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é)果相當(dāng)于圓內(nèi)正3072邊形的面積，換算成圓周率，得

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

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

42、定理1.3 若 與 為Rn上的任意兩種范數(shù)，則存在正常數(shù)C2≥C1使得 ， 。定義1.5 設(shè)有向量序列{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 設(shè)A為n階方陣， 為Rn中的某范數(shù)，則稱 為矩陣A的從屬于向量范數(shù)的范數(shù)，記作 。,矩陣范數(shù)的性質(zhì)：（1）對(duì)任意n階方陣A有 ，且 當(dāng)且僅當(dāng)A=0；（2）對(duì)任意實(shí)數(shù)k及任意n階方陣A，有

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

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