數(shù)值計(jì)算：緒論

1、任課教師：任課教師：柴振華柴振華Email：數(shù)值分析數(shù)值分析(Numerical Analysis)數(shù)值分析數(shù)值分析(Numerical Analysis)考試方式：考試方式：閉卷閉卷考試成績(jī)：考試成績(jī)：數(shù)值實(shí)驗(yàn)報(bào)告占數(shù)值實(shí)驗(yàn)報(bào)告占 20%，考試占，考試占 80%有關(guān)數(shù)值實(shí)驗(yàn)報(bào)告的幾點(diǎn)說(shuō)明：有關(guān)數(shù)值實(shí)驗(yàn)報(bào)告的幾點(diǎn)說(shuō)明：1) 題目范圍：教材每章后面的數(shù)值實(shí)驗(yàn)題（題目范圍：教材每章后面的數(shù)值實(shí)驗(yàn)題（自選三題自選三題）2) 提交時(shí)間：第提交時(shí)間：第11周周 周一上午（周一上午（C12-S201）3) 要求：要求：u利用所學(xué)知識(shí)，并嚴(yán)格按照題目要求完成所選題目利用所學(xué)知識(shí)，并嚴(yán)格按照題目要求完成所選題

2、目u報(bào)告中必須包含詳細(xì)的算法代碼（報(bào)告中必須包含詳細(xì)的算法代碼（C/C+、Matlab等）、數(shù)值結(jié)果等）、數(shù)值結(jié)果（圖形、表格）以及必要的結(jié)果描述與分析（圖形、表格）以及必要的結(jié)果描述與分析uA4紙雙面打印、首頁(yè)（單面）須包含姓名、院系、學(xué)號(hào)等基本信息紙雙面打印、首頁(yè)（單面）須包含姓名、院系、學(xué)號(hào)等基本信息注：作業(yè)必須獨(dú)立完成，若出現(xiàn)雷同，將視情況酌情扣分注：作業(yè)必須獨(dú)立完成，若出現(xiàn)雷同，將視情況酌情扣分& 參考書(shū)目參考書(shū)目 (Reference) 數(shù)值分析數(shù)值分析 李慶揚(yáng)、王能超、易大義李慶揚(yáng)、王能超、易大義編著編著 （清華大學(xué)出版社）（清華大學(xué)出版社） Numerical Analysis

3、 (Seventh Edition) 數(shù)值分析數(shù)值分析 （第七版（第七版 影印版）影印版） Richard L. Burden & J. Douglas Faires （高等教育出版社）（高等教育出版社） Introduction to Numerical Analysis (Second Edition) 數(shù)值分析導(dǎo)論數(shù)值分析導(dǎo)論 （第二版（第二版 影印版）影印版） J. Stoer & R. Bulirsch （世界圖書(shū)出版公司）（世界圖書(shū)出版公司） 數(shù)值分析學(xué)習(xí)輔導(dǎo)數(shù)值分析學(xué)習(xí)輔導(dǎo) 李紅、徐長(zhǎng)發(fā)李紅、徐長(zhǎng)發(fā)編著編著 （華工出版社）（華工出版社）&教材教材 (Text Book) 數(shù)值分析

4、數(shù)值分析（第二版）（第二版）李李 紅紅 編著編著 （華中科技大學(xué)出版社）（華中科技大學(xué)出版社）緒緒 論論 數(shù)值分析數(shù)值分析概括為用計(jì)算機(jī)求解數(shù)學(xué)問(wèn)題的數(shù)值方數(shù)值方法和理論法和理論。 在工程計(jì)算和科學(xué)實(shí)驗(yàn)中會(huì)遇到諸如線性方程組的求解、微分、積分、微分方程的求解等常見(jiàn)的數(shù)學(xué)問(wèn)題。 求解數(shù)學(xué)問(wèn)題思維方式： （1）利用數(shù)學(xué)方法求出（或推導(dǎo)出）結(jié)果的解析表達(dá)式（又稱解析解） （2）若實(shí)際中結(jié)果的解析表達(dá)式難以給出，例如滿足某個(gè)微分方程的函數(shù)不易求得，采用數(shù)學(xué)理論與計(jì)算機(jī)相結(jié)合，尋求(設(shè)計(jì))合適的算法以期得到問(wèn)題的近似數(shù)值解數(shù)值分析數(shù)值分析研究的主要問(wèn)題。 下面是兩種思維過(guò)程的對(duì)比：實(shí)際問(wèn)題實(shí)際問(wèn)題數(shù)學(xué)模

5、型數(shù)學(xué)模型解析表達(dá)式解析表達(dá)式結(jié)果結(jié)果實(shí)際問(wèn)題實(shí)際問(wèn)題數(shù)學(xué)模型數(shù)學(xué)模型算法設(shè)計(jì)算法設(shè)計(jì)編程計(jì)算結(jié)果編程計(jì)算結(jié)果 眾所周知，電子計(jì)算機(jī)實(shí)質(zhì)上只會(huì)做加眾所周知，電子計(jì)算機(jī)實(shí)質(zhì)上只會(huì)做加減乘除等基本運(yùn)算，研究怎樣通過(guò)計(jì)算機(jī)所減乘除等基本運(yùn)算，研究怎樣通過(guò)計(jì)算機(jī)所能執(zhí)行的基本運(yùn)算，求得各類數(shù)學(xué)問(wèn)題的數(shù)能執(zhí)行的基本運(yùn)算，求得各類數(shù)學(xué)問(wèn)題的數(shù)值解或近似解就是數(shù)值計(jì)算的值解或近似解就是數(shù)值計(jì)算的根本課題根本課題。由。由基本運(yùn)算及運(yùn)算順序的規(guī)定所構(gòu)成的完整的基本運(yùn)算及運(yùn)算順序的規(guī)定所構(gòu)成的完整的解題步驟，稱為解題步驟，稱為算法算法。數(shù)值。數(shù)值計(jì)算計(jì)算的的根本任務(wù)根本任務(wù)就是就是研究算法研究算法。通過(guò)編制程序我

6、們就可以計(jì)通過(guò)編制程序我們就可以計(jì)算算sinx的的近似值。事實(shí)上，近似值。事實(shí)上，計(jì)算機(jī)語(yǔ)言常用的數(shù)學(xué)運(yùn)算的標(biāo)準(zhǔn)函數(shù)也可用這種方法計(jì)算機(jī)語(yǔ)言常用的數(shù)學(xué)運(yùn)算的標(biāo)準(zhǔn)函數(shù)也可用這種方法寫(xiě)成。寫(xiě)成。)()!12()1(!7! 5! 3sin1212753xRnxxxxxxnnn )!12()1(!7! 5! 3sin12753 nxxxxxxnn 例：例：計(jì)算任意角的三角函數(shù)，如計(jì)算任意角的三角函數(shù)，如sinx。不調(diào)用庫(kù)函數(shù)，。不調(diào)用庫(kù)函數(shù)，計(jì)算機(jī)是不能直接計(jì)算計(jì)算機(jī)是不能直接計(jì)算sinx的。根據(jù)微分學(xué)的的。根據(jù)微分學(xué)的Taylor公式，公式，我們有：我們有：等式的右端就只是乘法與加法的循環(huán)運(yùn)算。取等

7、式的右端就只是乘法與加法的循環(huán)運(yùn)算。取 算法算法1 1：按原形計(jì)算：按原形計(jì)算： 需做需做 次乘法、次乘法、 次加法次加法1296. 2912. 1215. 1425. 00625. 0234 xxxx例：例：計(jì)算多項(xiàng)式計(jì)算多項(xiàng)式的值。的值。十十四四 算法算法2 2；上述多項(xiàng)式化為；上述多項(xiàng)式化為1296. 2)912. 1)215. 1)425. 00625. 0( xxxx則需做則需做 次乘法、次乘法、 次加法。次加法。四四四四 算法算法3 3；上述多項(xiàng)式化為；上述多項(xiàng)式化為xxx22(0.5 +0.6) +0.5 +0.7(0.5 +0.6) +0.8+0.9則需做則需做 次乘法、次乘法

8、、 次加法。次加法。三三五五秦九韶秦九韶（公元12021261）中國(guó)剩余定理中國(guó)剩余定理數(shù)書(shū)九章（1247）秦九韶算法（秦九韶算法（1247）Hernor算法（算法（1819）nnnnnnnnnnbxaxaxabxaxaxabxaxaxa .22112222212111212111例：例：解線性方程組解線性方程組按按Cramer法則求解，即法則求解，即nkDDxkk,.2,1, 其中其中, nnnnnnaaaaaaaaaD.212222111211 kD 是把是把D中第中第k列列 Tnkkkaaa.21 Tnbbb.21換為換為這要計(jì)算這要計(jì)算 個(gè)行列式，做個(gè)行列式，做 次除法。次除法。n+1

9、n而每個(gè)行列式包含而每個(gè)行列式包含 個(gè)乘積，每個(gè)乘積個(gè)乘積，每個(gè)乘積n!n-1需做需做次乘法次乘法. .這樣共需做這樣共需做nnnAn )1()!1(次乘除法。次乘除法。 當(dāng)當(dāng)n=20時(shí)，時(shí)，2020107 . 9 A這意味這意味著在每秒做一億次乘除法的計(jì)算機(jī)上，要做著在每秒做一億次乘除法的計(jì)算機(jī)上，要做多萬(wàn)年！多萬(wàn)年！30因此，在構(gòu)造算法時(shí)，還應(yīng)考慮如何因此，在構(gòu)造算法時(shí)，還應(yīng)考慮如何計(jì)算計(jì)算, , 才能才能既快又省。既快又省。 提問(wèn)：提問(wèn)：數(shù)值分析是做什么用的？數(shù)值分析是做什么用的？數(shù)值數(shù)值分析分析輸入復(fù)雜問(wèn)題或運(yùn)算輸入復(fù)雜問(wèn)題或運(yùn)算.),(,)(,ln,xfdxddxxfbxAxaxba

10、x 計(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è)誤差 /* Measurement Error */ 求近似解求近似解 方法誤差方法誤差 (截?cái)嗾`差截?cái)嗾`差 /* Truncation Error */ ) 機(jī)器字長(zhǎng)有限機(jī)器字長(zhǎng)有限 舍

11、入誤差舍入誤差 /* Roundoff Error */誤差：誤差：一個(gè)物理量的真實(shí)值與計(jì)算值之間的差異一個(gè)物理量的真實(shí)值與計(jì)算值之間的差異 1 Introduction: Source & Classificationdxex 102 近近似似計(jì)計(jì)算算: :例例大家一起猜？大家一起猜？ dxe2x1011 / e解法之一解法之一：將將 作作Taylor展開(kāi)后再積分展開(kāi)后再積分2xe 91!4171!3151!21311)!4!3!21(10864210dxxxxxdxe2xS4R4 /* Remainder */,104 Sdxe2x取取則則 111!5191!414R稱為稱為截?cái)嗾`差截?cái)嗾`

12、差 /* Truncation Error */005091!414.R 這這里里7430024010333014211013114.S 0010200050. | 舍入誤差舍入誤差 /* Roundoff Error */ |006000100050102.dxe-x 的的總總體體誤誤差差計(jì)計(jì)算算= 0.747 由截去部分由截去部分/* excluded terms */引起引起由留下部分由留下部分/* included terms */引起引起1 Introduction: Spread & Accumulation2. 傳播與積累傳播與積累 /* Spread & Accumulatio

13、n */例例：蝴蝶效應(yīng)蝴蝶效應(yīng) 紐約的一只蝴蝶翅膀一拍，風(fēng)和日麗的北京紐約的一只蝴蝶翅膀一拍，風(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 記為記為*0I80

14、001050 .IIE則初始誤差則初始誤差111111110010 nI)e(ndxexeIdxexennnn391414231519594249414122764807131632896000121030592000111088128000101.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| !0

15、1En|Enn 我們有責(zé)任改變。我們有責(zé)任改變。 造成這種情況的是造成這種情況的是不穩(wěn)定的算法不穩(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: Sp

16、read & Accumulation632120560)1(11367879440)1(210838771150)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 (

17、1|*1NNNNENININE 以此類推，對(duì)以此類推，對(duì) n 6 log6，即，即 n 6，應(yīng)取，應(yīng)取 * = 3.14159。3 函數(shù)的誤差估計(jì)函數(shù)的誤差估計(jì) /*Error Estimation for Functions*/問(wèn)題問(wèn)題：對(duì)于：對(duì)于 A = f (x)，若用，若用 x* 取代取代 x，將對(duì)，將對(duì)A 產(chǎn)生什么影響？產(chǎn)生什么影響？分析分析：e*(A) = 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*(A)| |

18、f (x*)|e*(x)|即：即：x*產(chǎn)生的誤差經(jīng)過(guò)產(chǎn)生的誤差經(jīng)過(guò) f 作用后被放大作用后被放大/縮小了縮小了| f (x*)|倍。故稱倍。故稱| f (x*)|為為放大因子放大因子 /* amplification factor */ 或或 絕對(duì)條件數(shù)絕對(duì)條件數(shù) /* absolute condition number */.3 Error Estimation for Functions* ()|() |(*)reAe *Afx *)(*| )(|xxex*er )(*)(*)(*)(*)(*)(xexfxfxxxxxfxxxxfxfr 相對(duì)誤差條件數(shù)相對(duì)誤差條件數(shù) /* relative

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

20、*|*)(*)(*| )(|xxexexyxyxy*errr 解解：設(shè)截?。涸O(shè)截取 n 位有效數(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 位有效數(shù)字，即位有效數(shù)字，即 , 則相對(duì)誤差則相對(duì)誤差8ln 209 )8920ln(. %.1010029820ln9820ln8920ln5 4 幾點(diǎn)注意事項(xiàng)幾點(diǎn)注意事項(xiàng) /* Remarks */1. 避免相近二數(shù)相減避免相近二數(shù)相減例例：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 .6121112xxxex4 Remarks2. 避免小分母避免小分母 : 分母小會(huì)造成浮點(diǎn)溢出分母小會(huì)造