數(shù)值計(jì)算方法與程序設(shè)計(jì)

1、 提問(wèn)：數(shù)值分析是做什么用的？提問(wèn)：數(shù)值分析是做什么用的？數(shù)值數(shù)值分析分析輸入復(fù)雜問(wèn)題或運(yùn)算輸入復(fù)雜問(wèn)題或運(yùn)算.),(,)(,ln,xfdxddxxfbxAxaxbax 計(jì)算機(jī)計(jì)算機(jī)近似解近似解第一章第一章 誤差誤差 /* Error */1 誤差的背景介紹誤差的背景介紹 /* Introduction */1. 來(lái)源與分類來(lái)源與分類 /* Source & Classification */ 從實(shí)際問(wèn)題中抽象出數(shù)學(xué)模型從實(shí)際問(wèn)題中抽象出數(shù)學(xué)模型 模型誤差模型誤差 /* Modeling Error */ 通過(guò)測(cè)量得到模型中參數(shù)的值通過(guò)測(cè)量得到模型中參數(shù)的值 觀測(cè)誤差觀測(cè)誤差 /* Measu

2、rement Error */ 求近似解求近似解 方法誤差方法誤差 (截?cái)嗾`差截?cái)嗾`差 /* Truncation Error */ ) 機(jī)器字長(zhǎng)有限機(jī)器字長(zhǎng)有限 舍入誤差舍入誤差 /* Roundoff Error */1 Introduction: Source & ClassificationThe following problem can be solved either the easy way or the hard way.Two trains 200 miles apart are moving toward each other; each one is going at

3、a speed of 50 miles per hour. A fly starting on the front of one of them flies back and forth between them at a rate of 75 miles per hour. It does this until the trains collide and crush the fly to death. What is the total distance the fly has flown?The fly actually hits each train an infinite numbe

4、r of times before it gets crushed, and one could solve the problem the hard way with pencil and paper by summing an infinite series of distances. The easy way is as follows: Since the trains are 200 miles apart and each train is going 50 miles an hour, it takes 2 hours for the trains to collide. The

5、refore the fly was flying for two hours. Since the fly was flying at a rate of 75 miles per hour, the fly must have flown 150 miles. Thats all there is to it.When this problem was posed to John von Neumann, he immediately replied, 150 miles.It is very strange, said the poser, but nearly everyone tri

6、es to sum the infinite series.What do you mean, strange? asked Von Neumann. Thats how I did it!1 Introduction: Source & Classification大家一起猜？大家一起猜？ dxe2x1011 / e解法之一解法之一：將將 作作Taylor展開(kāi)后再積分展開(kāi)后再積分2xe.91!4171!3151!21311).!4!3!21(10864210 dxxxxxdxe2xS4R4 /* Remainder */7430024010333014211013114.S 00102000

7、50. | 舍入誤差舍入誤差 /* Roundoff Error */ |006000100050102.dxe-x 的的總總體體誤誤差差計(jì)計(jì)算算= 0.747 由截去部分由截去部分/* excluded terms */引起引起,104 Sdxe2x取取則則.111!5191!414 R稱為稱為截?cái)嗾`差截?cái)嗾`差 /* Truncation Error */005091!414.R 這這里里由留下部分由留下部分/* included terms */引起引起dxex 102例：例：近似計(jì)算近似計(jì)算據(jù)說(shuō)，美軍據(jù)說(shuō)，美軍 1910 1910 年的一次部隊(duì)的命令傳遞是這樣的年的一次部隊(duì)的命令傳遞是這

8、樣的: : 營(yíng)長(zhǎng)對(duì)值班軍官營(yíng)長(zhǎng)對(duì)值班軍官: : 明晚大約明晚大約 8 8點(diǎn)鐘左右，哈雷彗星將可能在這個(gè)地區(qū)點(diǎn)鐘左右，哈雷彗星將可能在這個(gè)地區(qū)看到，這種彗星每隔看到，這種彗星每隔 7676年才能看見(jiàn)一次。命令所有士兵著野戰(zhàn)服在操年才能看見(jiàn)一次。命令所有士兵著野戰(zhàn)服在操場(chǎng)上集合，我將向他們解釋這一罕見(jiàn)的現(xiàn)象。如果下雨的話，就在禮場(chǎng)上集合，我將向他們解釋這一罕見(jiàn)的現(xiàn)象。如果下雨的話，就在禮堂集合，我為他們放一部有關(guān)彗星的影片。堂集合，我為他們放一部有關(guān)彗星的影片。值班軍官對(duì)連長(zhǎng)值班軍官對(duì)連長(zhǎng): : 根據(jù)營(yíng)長(zhǎng)的命令，明晚根據(jù)營(yíng)長(zhǎng)的命令，明晚8 8點(diǎn)哈雷彗星將在操場(chǎng)上空出點(diǎn)哈雷彗星將在操場(chǎng)上空出現(xiàn)。如果

9、下雨的話，就讓士兵穿著野戰(zhàn)服列隊(duì)前往禮堂，這一罕見(jiàn)的現(xiàn)。如果下雨的話，就讓士兵穿著野戰(zhàn)服列隊(duì)前往禮堂，這一罕見(jiàn)的現(xiàn)象將在那里出現(xiàn)?，F(xiàn)象將在那里出現(xiàn)。連長(zhǎng)對(duì)排長(zhǎng)連長(zhǎng)對(duì)排長(zhǎng): : 根據(jù)營(yíng)長(zhǎng)的命令，明晚根據(jù)營(yíng)長(zhǎng)的命令，明晚8 8點(diǎn)，非凡的哈雷彗星將身穿野戰(zhàn)點(diǎn)，非凡的哈雷彗星將身穿野戰(zhàn)服在禮堂中出現(xiàn)。如果操場(chǎng)上下雨，營(yíng)長(zhǎng)將下達(dá)另一個(gè)命令，這種命服在禮堂中出現(xiàn)。如果操場(chǎng)上下雨，營(yíng)長(zhǎng)將下達(dá)另一個(gè)命令，這種命令每隔令每隔7676年才會(huì)出現(xiàn)一次。年才會(huì)出現(xiàn)一次。排長(zhǎng)對(duì)班長(zhǎng)排長(zhǎng)對(duì)班長(zhǎng): : 明晚明晚8 8點(diǎn)，營(yíng)長(zhǎng)將帶著哈雷彗星在禮堂中出現(xiàn)，這是每隔點(diǎn)，營(yíng)長(zhǎng)將帶著哈雷彗星在禮堂中出現(xiàn)，這是每隔 7676年才有的事

10、。如果下雨的話，營(yíng)長(zhǎng)將命令彗星穿上野戰(zhàn)服到操場(chǎng)上年才有的事。如果下雨的話，營(yíng)長(zhǎng)將命令彗星穿上野戰(zhàn)服到操場(chǎng)上去。去。班長(zhǎng)對(duì)士兵班長(zhǎng)對(duì)士兵: : 在明晚在明晚8 8點(diǎn)下雨的時(shí)候，著名的點(diǎn)下雨的時(shí)候，著名的7676歲哈雷將軍將在營(yíng)長(zhǎng)的歲哈雷將軍將在營(yíng)長(zhǎng)的陪同下身著野戰(zhàn)服，開(kāi)著他那陪同下身著野戰(zhàn)服，開(kāi)著他那“彗星彗星”牌汽車，經(jīng)過(guò)操場(chǎng)前往禮堂。牌汽車，經(jīng)過(guò)操場(chǎng)前往禮堂。1 Introduction: Spread & Accumulation2. 傳播與積累傳播與積累 /* Spread & Accumulation */例：例：蝴蝶效應(yīng)蝴蝶效應(yīng) 紐約的一只蝴蝶翅膀一拍，風(fēng)和日麗的北京紐約的一只蝴蝶翅

11、膀一拍，風(fēng)和日麗的北京就刮起臺(tái)風(fēng)來(lái)了？！就刮起臺(tái)風(fēng)來(lái)了？！NYBJ以上是一個(gè)以上是一個(gè)病態(tài)問(wèn)題病態(tài)問(wèn)題 /* ill-posed problem*/關(guān)于本身是病態(tài)的問(wèn)題，我們還是留給數(shù)學(xué)家去頭痛吧！關(guān)于本身是病態(tài)的問(wèn)題，我們還是留給數(shù)學(xué)家去頭痛吧！1 Introduction: Spread & Accumulation.210110,n,dxexeIxnn 例：例：計(jì)算計(jì)算11 nnInI 公式一：公式一：注意此公式注意此公式精確精確成成立立632120560111100.edxeeIx 記為記為*0I80001050 .IIE則初始誤差則初始誤差111111110010 nI)e(ndxe

12、xeIdxexennnn391414231519594249414122764807131632896000121030592000111088128000101.367879440111415*13*14*12*13*11*12*10*11*9*10*0*1.II.II.II.II.II.II.II ? ! !What happened?!1 Introduction: Spread & Accumulation考察第考察第n步的誤差步的誤差nE| )1()1( |*11* nnnnnnInIIIE| !.01En|Enn 我們有責(zé)任改變。我們有責(zé)任改變。造成這種情況的是造成這種情況的是不穩(wěn)

13、定的算法不穩(wěn)定的算法 /* unstable algorithm */迅速積累，誤差呈遞增走勢(shì)。迅速積累，誤差呈遞增走勢(shì)?？梢?jiàn)初始的小擾動(dòng)可見(jiàn)初始的小擾動(dòng)801050| .E)1(1111nnnnInIInI 公式二：公式二：注意此公式與公式一注意此公式與公式一在理論上在理論上等價(jià)等價(jià)。方法：先估計(jì)一個(gè)方法：先估計(jì)一個(gè)IN , ,再反推要求的再反推要求的In ( n N )。11)1(1 NINeNNNINNeI 11)1(121*可取可取0* NNNIIEN, ,時(shí)時(shí)當(dāng)當(dāng)1 Introduction: Spread & Accumulation632120560)1(11367879440)

14、1(21.0838771150)1(1110773517320)1(1210717792140)1(1310668702200)1(1410638169180)1(151042746233016116121*1*0*2*1*11*10*12*11*13*12*14*13*15*14*15.II.II.II.II.II.II.II.eI 取取 We just got lucky?1 Introduction: Spread & Accumulation考察反推一步的誤差：考察反推一步的誤差：|1)1 (1)1 (1|*1NNNNENININE 以此類推，對(duì)以此類推，對(duì) n 6 log6，即，即

15、n 6，應(yīng)取，應(yīng)取 * = 3.14159。3 函數(shù)的誤差估計(jì)函數(shù)的誤差估計(jì) /*Error Estimation for Functions*/問(wèn)題問(wèn)題：對(duì)于：對(duì)于 y = f (x)，若用，若用 x* 取代取代 x，將對(duì)，將對(duì)y 產(chǎn)生什么影響？產(chǎn)生什么影響？分析分析：e*(y) = f (x*) f (x) e*(x) = x* xMean Value Theorem= f ( )(x* x)x* 與與 x 非常接近時(shí)，可認(rèn)為非常接近時(shí)，可認(rèn)為 f ( ) f (x*) ，則有：，則有：|e*(y)| | f (x*)|e*(x)|即：即：x*產(chǎn)生的誤差經(jīng)過(guò)產(chǎn)生的誤差經(jīng)過(guò) f 作用后被放大

16、作用后被放大/縮小了縮小了| f (x*)|倍。故稱倍。故稱| f (x*)|為為放大因子放大因子 /* amplification factor */ 或或 絕對(duì)條件數(shù)絕對(duì)條件數(shù) /* absolute condition number */.3 Error Estimation for Functions*)()(*| )(|xfyey*er *)(*| )(|xxex*er )(*)(*)(*)(*)(*)(xexfxfxxxxxfxxxxfxfr 相對(duì)誤差條件數(shù)相對(duì)誤差條件數(shù) /* relative condition number*/ f 的條件數(shù)在某一點(diǎn)是的條件數(shù)在某一點(diǎn)是小小大大

17、，則稱，則稱 f 在該點(diǎn)是在該點(diǎn)是好條件的好條件的 /* well-conditioned */ 壞條件的壞條件的 /* ill-conditioned */。注：關(guān)于多元函數(shù)注：關(guān)于多元函數(shù) 的討論，請(qǐng)參閱教的討論，請(qǐng)參閱教材第材第5、6頁(yè)。頁(yè)。).,(21nx,x,xfy 3 Error Estimation for Functions例例:計(jì)算計(jì)算 y = ln x。若。若 x 20，則取，則取 x 的幾位有效數(shù)字可保證的幾位有效數(shù)字可保證 y 的相對(duì)誤差的相對(duì)誤差 0.1% ?*ln| )(*| )(*|*)(*)(*| )(|xxexexyxyxy*errr 解：解：設(shè)截取設(shè)截取 n

18、 位有效數(shù)字后得位有效數(shù)字后得 x* x，則，則估計(jì)估計(jì) x 和和 y 的相對(duì)誤差上限滿足近似關(guān)系的相對(duì)誤差上限滿足近似關(guān)系)(*ln)(*yxxrr %1 . 0*ln102111 xan不知道怎么辦??？不知道怎么辦??？x 可能是可能是20.#，也可能，也可能是是19.#，取最壞情況，取最壞情況，即即a1 = 1。 n 4例：例：計(jì)算計(jì)算 ，取，取 4 位有效，即位有效，即 , 則相對(duì)誤差則相對(duì)誤差 9820ln)8920ln(. %.1010029820ln9820ln8920ln5 4 幾點(diǎn)注意事項(xiàng)幾點(diǎn)注意事項(xiàng) /* Remarks */1. 避免相近二數(shù)相減避免相近二數(shù)相減 (詳細(xì)分析

19、請(qǐng)參閱教材詳細(xì)分析請(qǐng)參閱教材p.6 - p.7)例：例：a1 = 0.12345，a2 = 0.12346，各有，各有5位有效數(shù)字。位有效數(shù)字。 而而 a2 a1 = 0.00001，只剩下，只剩下1位有效數(shù)字。位有效數(shù)字。 幾種經(jīng)驗(yàn)性避免方法：幾種經(jīng)驗(yàn)性避免方法：;xxxx ;1lnlnln xxx當(dāng)當(dāng) | x | 1 時(shí)：時(shí)：;2sin2cos12xx .6121112xxxex更多技巧請(qǐng)見(jiàn)教材第更多技巧請(qǐng)見(jiàn)教材第8頁(yè)習(xí)題頁(yè)習(xí)題6。4 Remarks2. 避免小分母避免小分母 : 分母小會(huì)造成浮點(diǎn)溢出分母小會(huì)造成浮點(diǎn)溢出 /* over flow */3. 避免大數(shù)避免大數(shù)吃吃小數(shù)小數(shù)例：

20、例：用單精度計(jì)算用單精度計(jì)算 的根。的根。010)110(992 xx精確解為精確解為110291 x,x 算法算法1 1：利用求根公式利用求根公式aacbbx242 在計(jì)算機(jī)內(nèi)，在計(jì)算機(jī)內(nèi)，109存為存為0.1 1010，1存為存為0.1 101。做加法時(shí)，做加法時(shí)，兩加數(shù)的指數(shù)先向大指數(shù)對(duì)齊，再將浮點(diǎn)部分相加。即兩加數(shù)的指數(shù)先向大指數(shù)對(duì)齊，再將浮點(diǎn)部分相加。即1 的指數(shù)部分須變?yōu)榈闹笖?shù)部分須變?yōu)?010，則：，則：1 = 0.0000000001 1010，取，取單精度時(shí)就成為：?jiǎn)尉葧r(shí)就成為： 109+1=0.10000000 1010+0.00000000 1010=0.1000000

21、0 1010大數(shù)大數(shù)吃吃小數(shù)小數(shù)024,102422921 aacbbxaacbbx4 Remarks算法算法2：先解出先解出 再利用再利用9211024)( aacbbsignbx11010991221 xacxacxx求和時(shí)求和時(shí)從小到大從小到大相加，可使和的誤差減小。相加，可使和的誤差減小。例：例：按從小到大、以及從大到小的順序分別計(jì)算按從小到大、以及從大到小的順序分別計(jì)算1 + 2 + 3 + + 40 + 1094. 先化簡(jiǎn)再計(jì)算，減少步驟，避免誤差積累。先化簡(jiǎn)再計(jì)算，減少步驟，避免誤差積累。一般來(lái)說(shuō)，計(jì)算機(jī)處理下列運(yùn)算的速度為一般來(lái)說(shuō)，計(jì)算機(jī)處理下列運(yùn)算的速度為 exp ,5. 選

22、用穩(wěn)定的算法。選用穩(wěn)定的算法。HW: p.8-9 #1, #7Self-study Ch.2-1 Excuses for not doing homeworkI accidentally divided by zeroand my paper burst into flames. Lab 01. Numerical Summation of a Series Produce a table of the values of the series (1)for the 3001 values of x, x = 0.0, 0.1, 0.2, , 300.00. All entries of th

23、e table must have an absolute error less than 1.0e-10. This problem is based on a problem from Hamming (1962), when mainframes were very slow by todays microcomputer standards. InputThere is no input.Output The output is to be formatted as two columns with the values of x and (x) printed as in the C fprintf: fprintf(outfile,%6.2f%16.12fn,x,psix); /* hererepresents a space */ 1)(1)(kxkkx As an example, the sample output below shows 4 acceptable lines out of 3001, which might appear in the output file. The values of