1、會計學1數值數值(shz)計算方法緒論計算方法緒論第一頁，共30頁。程序程序設計設計上機上機計算計算設計高效、可設計高效、可靠的數值方法靠的數值方法數值數值問題問題求解求解近似結果近似結果輸出輸出重點重點(zhngdin)討論討論數值問題數值問題(wnt)的的來源：來源：實際實際問題問題建立數學模型建立數學模型數值數值問題問題第2頁/共30頁第二頁，共30頁。數值方法的設計原數值方法的設計原則則收斂性：方法的可行性收斂性：方法的可行性穩定性：初始數據等產生的誤差對結果的影響穩定性：初始數據等產生的誤差對結果的影響便于編程實現：邏輯復雜度要小便于編程實現：邏輯復雜度要小計算量要小：時間復雜度要小

2、，運行時間要短計算量要小：時間復雜度要小，運行時間要短存貯量要盡量小：空間復雜度要存貯量要盡量小：空間復雜度要小小可可靠靠性性分分析析計算復雜性計算復雜性誤差估計：運算結果不能產生太大的偏差且誤差估計：運算結果不能產生太大的偏差且能夠控制誤差能夠控制誤差第3頁/共30頁第三頁，共30頁。物理學中：物理學中：Origin+fortran 七八十年代物理學家七八十年代物理學家(w l xu ji)Origin +C或或C+ 現代現代(xindi)物理學家物理學家數學數學(shxu)中：中：Matlab Mathematics Fortran C C+ 物理問題中：物理問題中：第4頁/共30頁第四頁

3、，共30頁。第5頁/共30頁第五頁，共30頁。1 誤誤 差差 /* Error */一、一、 誤差的來源誤差的來源(liyun)與分類與分類 /* Source & Classification */ 1、從實際問題中抽象、從實際問題中抽象(chuxing)出數學模型出數學模型 模型誤差模型誤差 /* Modeling Error */ 2、通過觀測得到模型中某些參數、通過觀測得到模型中某些參數(cnsh)（或物理量）（或物理量）的值的值 觀測誤差觀測誤差 /* Measurement Error */ 3、數學模型與數值算法之間的誤差數學模型與數值算法之間的誤差 方法誤差方法誤差 (

4、截斷誤差截斷誤差 /* Truncation Error */ ) 4、由于機器字長有限，原始數據和計算過程會產生新的誤差由于機器字長有限，原始數據和計算過程會產生新的誤差 舍入誤差舍入誤差 /* Roundoff Error */第6頁/共30頁第六頁，共30頁。二、二、 誤差誤差(wch)分析的基本概念分析的基本概念 /* Basic Concepts */ 設設 為真值（精確值），為真值（精確值）， 為為 的一個近似值的一個近似值 稱稱 為近似值為近似值 的的絕對誤差絕對誤差，簡稱誤差。，簡稱誤差。 xxx x exx 注：注：誤差可正可負，常常誤差可正可負，常常(chngchng)是無

5、限位是無限位的的絕對絕對誤差限誤差限/* accuracy */ 絕對值的上界絕對值的上界 如：如：53 141591103 14159262.(.) 絕對誤差還不能完全絕對誤差還不能完全(wnqun)表示近似值的好表示近似值的好壞壞（絕對誤差（絕對誤差/* absolute error */）1 1 .Def第7頁/共30頁第七頁，共30頁。近似值近似值 的誤差的誤差 與準確值與準確值 的比值：的比值：x e x稱為近似值稱為近似值 的相對誤差，記的相對誤差，記作作reex x 注：注：實際計算實際計算(j sun)時，相對誤差通常取時，相對誤差通常取因為因為(yn wi)1 2 .Def（

6、相對誤差（相對誤差/* relative error */ ）第8頁/共30頁第八頁，共30頁。相對誤差也可正可負相對誤差也可正可負,常常常常(chngchng)是無限位的是無限位的1 3 .Def（有效數字有效數字/*Significant Digits*/ ）相對相對誤差限誤差限相對相對誤差的絕對值的上界誤差的絕對值的上界r /* relative accuracy */如：如：3位位21102e6位位51102e若近似值若近似值 與準確值的誤差與準確值的誤差絕對絕對值不超過某一位的值不超過某一位的半個單位，該位到半個單位，該位到 的第一位非零數字共有的第一位非零數字共有 位，則位，則x

7、x nx n稱稱 有有 位位有效數字有效數字第9頁/共30頁第九頁，共30頁。 有效數字有效數字(另外另外(ln wi)一種定義形式一種定義形式)用科學計數法，記用科學計數法，記 其中其中 ， 若若 （即（即 的截取按四舍五入規則），則稱的截取按四舍五入規則），則稱 為有為有 位有效位有效數字，精確到數字，精確到 。12010mnx.a aa 01 a| 0 5 10m nxx.nax nm 10 120 19, ,nmZ a aa n3.1415926535897932;3.1415 例例1：問：問： 有幾位有效數字？請證明你的結論。有幾位有效數字？請證明你的結論。 *10501050*an

8、d103141504131 .| ,.*證明：證明：有有 位有效數字，精確到小數點后第位有效數字，精確到小數點后第 位。位。43規格化形式規格化形式(xngsh)第10頁/共30頁第十頁，共30頁。注：注：若若 的每一位都是有效數字，則的每一位都是有效數字，則 稱是稱是有效數有效數x x 特別，經特別，經“四舍五入四舍五入”得到的數均為有效得到的數均為有效數數1 1 .Th12010mknx.a aaa 將將 的近似值的近似值 表示為表示為 ，若若 是有效數字，則相對誤差不超過是有效數字，則相對誤差不超過 ；反之，若已知相對誤差反之，若已知相對誤差 ，且有，且有 ，11102()k xre 1

9、102kre x kaka則則 必為有效數字。必為有效數字。第11頁/共30頁第十一頁，共30頁。例例2 2：為使為使 的相對誤差小于的相對誤差小于0.001%, ,至少應取幾位有至少應取幾位有效數字？效數字？*解：解：假設假設 * 取到取到 n 位有效數字位有效數字(yu xio sh z)，則其相，則其相對誤差上限為對誤差上限為要保證其相對誤差小于要保證其相對誤差小于0.001%，只要，只要(zhyo)保證其上限保證其上限滿足滿足解不等式可得解不等式可得 n 5.69，即，即 n = 6，應取，應取 * = 3.14159。第12頁/共30頁第十二頁，共30頁。例例3 3 計算下列多項式的

10、值計算下列多項式的值nnnaxaxaxp10)(為已知數據為已知數據01,na aax分析分析(fnx)：輸入數據為輸入數據為 ，輸出數據為，輸出數據為 ，若直接由，若直接由 算出算出 ，再乘相應的系數，再乘相應的系數 并并相加，則要做次相加，則要做次 乘法和乘法和 次加法，占用個次加法，占用個 存儲單元。存儲單元。 0,naaxx)(xpnxx,2021,aaann12()n n n12 n秦九韶方法，也稱為秦九韶方法，也稱為HornerHorner算法算法 用遞推公式用遞推公式(gngsh)(gngsh)表示表示為為00ab xbabiii1ni, 2 , 1)(xpbnn只用只用 次乘法

11、和次乘法和 次加法，并占用次加法，并占用 個存儲單元個存儲單元 n2nn三、數值三、數值(shz)(shz)算法及穩定性算法及穩定性 / /* * Numerical Numerical Algorithm and Stability Algorithm and Stability * */ /第13頁/共30頁第十三頁，共30頁。102xedx11 / e解法解法：將將 作作Taylor展開后再積分展開后再積分2xeS4R4 /* Remainder */,104 Sdxe2x取取則則 111!5191!414R稱為稱為截斷誤差截斷誤差 /* Truncation Error */00509

12、1!414.R 這這里里0010200050. | 舍入誤差舍入誤差 /* Roundoff Error */ |= 0.746824 由截去部分由截去部分(b fen)/* excluded terms */引起引起由留下由留下(li xi)部分部分/* included terms */引起引起例例4 4 近似計算近似計算210 xedx 第14頁/共30頁第十四頁，共30頁。 一個算法如果輸入數據有擾動（即誤差），而計算一個算法如果輸入數據有擾動（即誤差），而計算過程中舍入誤差不增長過程中舍入誤差不增長, ,則稱此算法是數值穩定的，否則則稱此算法是數值穩定的，否則此算法就稱為不穩定的。此

13、算法就稱為不穩定的。 1 4 .Def（數值穩定性（數值穩定性/ /* Numerical Stability */） 對數學問題本身如果輸入數據有微小擾動，引起對數學問題本身如果輸入數據有微小擾動，引起輸出數據（即問題真解）的很大擾動，這就是病態問輸出數據（即問題真解）的很大擾動，這就是病態問題。題。1 5 .Def（病態問題（病態問題/ /* ill-posed problem */） 它是數學問題本身性質所決定的，與算法無關，它是數學問題本身性質所決定的，與算法無關，也就是說對病態問題，用任何算法（或方法）直接計也就是說對病態問題，用任何算法（或方法）直接計算都將產生不穩定性。算都將產生

14、不穩定性。 第15頁/共30頁第十五頁，共30頁。此公式此公式(gngsh)精確成立精確成立80001050 .IIE記記為為*0I632120560111100.edxeeIx 則初始誤差則初始誤差What happened?!例例5 5 計算計算1010 1 2, , ,.nxnIx e dxne 公式公式(gngsh)一：一：第16頁/共30頁第十六頁，共30頁。考察第考察第n步的誤差步的誤差nE我們有責任改變。我們有責任改變。造成這種情況的是造成這種情況的是不穩定的算法不穩定的算法 /* unstable algorithm */迅速積累，誤差呈遞增趨勢。迅速積累，誤差呈遞增趨勢。初始

15、的小擾動初始的小擾動801050| .E 公式公式(gngsh)二：二：注意此公式與公式一注意此公式與公式一在理論在理論(lln)上等價。上等價。方法：先估計一個方法：先估計一個IN , ,再反推要求的再反推要求的In ( n N )。1112(1)1NNIIe NN 可取可取第17頁/共30頁第十七頁，共30頁。()()()()()()1514151314121311121011121110 04274623321616110 06381691815110 06687022014110 07177921413110 07735173212110 08387711511110 36787944

16、2I.eII.II.II.II.II.II. ()01110 632120561II.取取第18頁/共30頁第十八頁，共30頁。考察考察(koch)反推一步的誤差：反推一步的誤差：以此類推以此類推(y c li tu)，對，對 n N 有：有：誤差逐步誤差逐步(zhb)遞減遞減, 這樣的算法稱為穩定的算法這樣的算法稱為穩定的算法 /* stable algorithm */ 在我們今后的討論中，在我們今后的討論中，誤差誤差將不可回避，將不可回避， 算法的算法的穩定性穩定性將會是一個非常重要的話題。將會是一個非常重要的話題。第19頁/共30頁第十九頁，共30頁。例例6：蝴蝶效應：蝴蝶效應 紐約紐

17、約(ni yu)的一只蝴蝶翅膀一拍的一只蝴蝶翅膀一拍，風和日，風和日 麗的北京就刮起臺風來了？！麗的北京就刮起臺風來了？！紐約紐約(ni yu)北京北京(bi jn)這就是一個這就是一個病態問題病態問題第20頁/共30頁第二十頁，共30頁。2 誤差分析誤差分析(fnx)的方法和原則的方法和原則 /* Error Analysis */一、誤差一、誤差(wch)分分析的方法析的方法1、向前誤差分析法：利用誤差限，隨著計算過程、向前誤差分析法：利用誤差限，隨著計算過程 逐步逐步向前進行分析，直至估計出最后向前進行分析，直至估計出最后(zuhu)的結果。（例的結果。（例4） 1212()()()xx

18、xx 121221()()()xxxxxx12211222()()()xxxxxxx 注：注：兩個近似數兩個近似數 ，四則運算得到的誤差限分別為，四則運算得到的誤差限分別為12,xx （1 1）第21頁/共30頁第二十一頁，共30頁。（2 2）對于函數）對于函數(hnsh) y = f (x)(hnsh) y = f (x)，若用，若用 x x* * 取代取代 x x，將對，將對y y 產生什產生什 么影響？么影響？分析分析(fnx)：e*(y) = f (x*) f (x) e*(x) = x* xMean Value Theoremx* 與與 x 非常接近時，可認為非常接近時，可認為 ，則

19、有：，則有：( )()ffx ( )()( )eyfxex 即：即： 產生的誤差經過產生的誤差經過 作用后被作用后被放大放大/ /縮小縮小了了 倍倍。故稱。故稱 為為放大放大/縮小縮小因子因子 /* amplification factor */ 或或 絕對絕對條件數條件數 /* absolute condition number */.x f()f x ()f x 第22頁/共30頁第二十二頁，共30頁。例例7 7105%x 設設 ,試求函數試求函數 的相對誤差限的相對誤差限. ( )nf xx 解：解：由題設知由題設知:近似值為近似值為 ,絕對誤差限為絕對誤差限為 10 x ()5%x 第

20、23頁/共30頁第二十三頁，共30頁。二、幾點注意事項二、幾點注意事項 /* Remarks */1、 避免避免(bmin)相近相近二數相減二數相減例：例：a1 = 0.12345，a2 = 0.12346，各有，各有5位有效數字位有效數字(yu xio sh z)。 而而 a2 a1 = 0.00001，只剩下，只剩下1位有效數字位有效數字(yu xio sh z)。 幾種幾種(j zhn)經驗性避經驗性避免方法：免方法：當當 | x | 1 時：時：第24頁/共30頁第二十四頁，共30頁。2、 避免小分母避免小分母 : 分母小會造成分母小會造成(zo chn)浮點溢出浮點溢出 /* ove

21、r flow */3、避免大數、避免大數(d sh)吃小數吃小數例：例：用單精度計算用單精度計算 的根的根。010)110(992 xx精確精確(jngqu)解為解為 算法算法1 1：利用求根公式利用求根公式aacbbx242 在計算機內，在計算機內，109存為存為0.1 1010，1存為存為0.1 101。做加法時，兩加做加法時，兩加數的指數先向大指數對齊，再將浮點部分相加。即數的指數先向大指數對齊，再將浮點部分相加。即1 的指數的指數部分須變為部分須變為1010，則：，則：1 = 0.0000000001 1010，取單精度時就取單精度時就成為：成為： 109+1=0.10000000 1

22、010+0.00000000 1010=0.10000000 1010大數大數吃吃小數小數第25頁/共30頁第二十五頁，共30頁。算法算法2：先解出先解出 再利用再利用9211024)( aacbbsignbx11010991221 xacxacxx例：按從小到大、以及從大到小的順序分別例：按從小到大、以及從大到小的順序分別(fnbi)計算計算1 + 2 + 3 + + 40 + 1094、 先化簡再計算先化簡再計算(j sun)，減少步驟，避免誤差積累。，減少步驟，避免誤差積累。一般來說，計算機處理下列運算的速度為一般來說，計算機處理下列運算的速度為 exp ,5、選用穩定的算法。選用穩定的算法。第26頁/共30頁第二十六頁，共30頁。稱為稱為(chn