第一章數(shù)值計算方法緒論

1、*)()(xxxxxExErbAx ni, 3 ,2 中國石油大學（華東）理學院制作:劉新海)(*yEr*2*2*2*1*1*1rrxfyxxfyx&教材教材 (Text Book) 數(shù)值計算方法數(shù)值計算方法（第二版）（第二版） 李維國、同登科李維國、同登科主編主編 （中國石油大學出版社，（中國石油大學出版社，2009年）年）& 參考書目參考書目 (Reference) 數(shù)值計算方法數(shù)值計算方法 (上、下冊上、下冊) 林成森林成森 編著編著 （科學出版社（科學出版社 1998年）年） Principle of Numerical Analysis 數(shù)值分析原理數(shù)值分析原理 封建

2、湖、車剛明、聶玉峰封建湖、車剛明、聶玉峰 編著編著 （科學出版社，（科學出版社，2001年）年） 提問：提問：數(shù)值計算方法是做什么用的？數(shù)值計算方法是做什么用的？研究對象研究對象：數(shù)值問題數(shù)值問題有限個輸入數(shù)據(jù)（問題的自有限個輸入數(shù)據(jù)（問題的自變量、原始數(shù)據(jù)）與有限個輸出數(shù)據(jù)（待求解數(shù)據(jù)）之變量、原始數(shù)據(jù)）與有限個輸出數(shù)據(jù)（待求解數(shù)據(jù)）之間函數(shù)關(guān)系的一個明確無歧義的描述。間函數(shù)關(guān)系的一個明確無歧義的描述。如一階微分方程初值問題如一階微分方程初值問題2(0)1dyxdxy求函數(shù)解析表達式求函數(shù)解析表達式( )yy x數(shù)學問題數(shù)學問題求函數(shù)求函數(shù) 在某些點在某些點( )yy x 1niix的近似函

3、數(shù)值的近似函數(shù)值數(shù)值問題數(shù)值問題程序程序設(shè)計設(shè)計上機上機計算計算設(shè)計高效、可設(shè)計高效、可靠的數(shù)值方法靠的數(shù)值方法數(shù)值數(shù)值問題問題求解求解近似結(jié)果近似結(jié)果輸出輸出重點討論重點討論數(shù)值問題的來源：數(shù)值問題的來源：實際實際問題問題建立數(shù)學模型建立數(shù)學模型數(shù)值數(shù)值問題問題數(shù)值方法的設(shè)計原數(shù)值方法的設(shè)計原則則收斂性：方法的可行性收斂性：方法的可行性穩(wěn)定性：初始數(shù)據(jù)等產(chǎn)生的誤差對結(jié)果的影響穩(wěn)定性：初始數(shù)據(jù)等產(chǎn)生的誤差對結(jié)果的影響便于編程實現(xiàn)：邏輯復(fù)雜度要小便于編程實現(xiàn)：邏輯復(fù)雜度要小計算量要?。簳r間復(fù)雜度要小，運行時間要短計算量要小：時間復(fù)雜度要小，運行時間要短存貯量要盡量小：空間復(fù)雜度要小存貯量要盡量小

4、：空間復(fù)雜度要小可可靠靠性性分分析析計算復(fù)雜性計算復(fù)雜性誤差估計：運算結(jié)果不能產(chǎn)生太大的偏差且誤差估計：運算結(jié)果不能產(chǎn)生太大的偏差且能夠控制誤差能夠控制誤差1 誤誤 差差 /* Error */一、一、 誤差的來源與分類誤差的來源與分類 /* Source & Classification */ 1、從實際問題中抽象出數(shù)學模型從實際問題中抽象出數(shù)學模型 模型誤差模型誤差 /* Modeling Error */ 2、通過觀測得到模型中某些參數(shù)（或物理量）的值通過觀測得到模型中某些參數(shù)（或物理量）的值 觀測誤差觀測誤差 /* Measurement Error */ 3、數(shù)學模型與數(shù)值算

5、法之間的誤差求近似解數(shù)學模型與數(shù)值算法之間的誤差求近似解 方法誤差方法誤差 (截斷誤差截斷誤差 /* Truncation Error */ ) 4、由于機器字長有限，原始數(shù)據(jù)和計算過程會產(chǎn)生新的誤差由于機器字長有限，原始數(shù)據(jù)和計算過程會產(chǎn)生新的誤差 舍入誤差舍入誤差 /* Roundoff Error */二、二、 誤差分析的基本概念誤差分析的基本概念 /* Basic Concepts */ 設(shè)設(shè) 為真值（精確值），為真值（精確值）， 為為 的一個近似值的一個近似值 稱稱 為近似值為近似值 的絕對誤差，簡稱誤差。的絕對誤差，簡稱誤差。 xxx x exx注：注：誤差可正可負，常常是無限位的

6、誤差可正可負，常常是無限位的絕對絕對誤差限誤差限/* accuracy */ 絕對值的上界絕對值的上界 exx 如：如：53 141591103 14159262.(.) 絕對絕對誤差還不能完全表示近似值的好壞誤差還不能完全表示近似值的好壞（絕對誤差（絕對誤差/* absolute error */）1 1 .Def近似值近似值 的誤差的誤差 與準確值與準確值 的比值：的比值：x e xexxxx 稱為近似值稱為近似值 的相對誤差，記作的相對誤差，記作reex x 注：注：實際計算時，相對誤差通常取實際計算時，相對誤差通常取rexxexx 因為因為221()()()()eeeexxexexxx

7、xxxex 1 2 .Def（相對誤差（相對誤差/* relative error */ ）相對相對誤差也可正可負誤差也可正可負rexxxx 1 3 .Def（有效數(shù)字有效數(shù)字/*Significant Digits*/ ）相對相對誤差限誤差限相對相對誤差的絕對值的上界誤差的絕對值的上界r /* relative accuracy */如：如：3 1415926. 3 14. 3 141592. 3位位21102e6位位51102e若近似值若近似值 與準確值的誤差與準確值的誤差絕對絕對值不超過某一位的值不超過某一位的半個單位，該位到半個單位，該位到 的第一位非零數(shù)字共有的第一位非零數(shù)字共有 位

8、，則位，則x x nx n稱稱 有有 位位有效數(shù)字有效數(shù)字 有效數(shù)字有效數(shù)字(另外一種定義形式另外一種定義形式)用科學計數(shù)法，記用科學計數(shù)法，記 其中其中 ， 若若 （即（即 的截取按四舍五入規(guī)則），則稱的截取按四舍五入規(guī)則），則稱 為有為有 位有效位有效數(shù)字，精確到數(shù)字，精確到 。12010mnx.a aa 01 a| 0 5 10m nxx.nax nm 10 120 19, ,nmZ a aan3.1415926535897932;3.1415 例例1：問：問： 有幾位有效數(shù)字？請證明你的結(jié)論。有幾位有效數(shù)字？請證明你的結(jié)論。 *10501050*and103141504131 .| ,

9、.*證明：證明：有有 位有效數(shù)字，精確到小數(shù)點后第位有效數(shù)字，精確到小數(shù)點后第 位。位。43規(guī)格化形式規(guī)格化形式若若 的每一位都是有效數(shù)字，則的每一位都是有效數(shù)字，則 稱是稱是有效數(shù)有效數(shù)x x 特別，經(jīng)特別，經(jīng)“四舍五入四舍五入”得到的數(shù)均為有效數(shù)得到的數(shù)均為有效數(shù) 一個算法如果輸入數(shù)據(jù)有擾動（即誤差），而計算一個算法如果輸入數(shù)據(jù)有擾動（即誤差），而計算過程中舍入誤差不增長過程中舍入誤差不增長, ,則稱此算法是數(shù)值穩(wěn)定的，否則則稱此算法是數(shù)值穩(wěn)定的，否則此算法就稱為不穩(wěn)定的。此算法就稱為不穩(wěn)定的。 1 4 .Def（數(shù)值穩(wěn)定性（數(shù)值穩(wěn)定性/ /* Numerical Stability */

10、） 對數(shù)學問題本身如果輸入數(shù)據(jù)有微小擾動，引起對數(shù)學問題本身如果輸入數(shù)據(jù)有微小擾動，引起輸出數(shù)據(jù)（即問題真解）的很大擾動，這就是病態(tài)問輸出數(shù)據(jù)（即問題真解）的很大擾動，這就是病態(tài)問題。題。1 5 .Def（病態(tài)問題（病態(tài)問題/ /* ill-posed problem */） 它是數(shù)學問題本身性質(zhì)所決定的，與算法無關(guān)，它是數(shù)學問題本身性質(zhì)所決定的，與算法無關(guān)，也就是說對病態(tài)問題，用任何算法（或方法）直接計也就是說對病態(tài)問題，用任何算法（或方法）直接計算都將產(chǎn)生不穩(wěn)定性。算都將產(chǎn)生不穩(wěn)定性。 三、數(shù)值算法及穩(wěn)定性三、數(shù)值算法及穩(wěn)定性 /* Numerical Algorithm and Stab

11、ility */此公式此公式精確精確成立成立80001050 .IIE記為記為*0I632120560111100.edxeeIx 則初始誤差則初始誤差111111110010 nI)e(ndxexeIdxexennnn10109111012111312141315141 10 36787944.1 100 088128001 110 030592001 120 632896001 137 22764801 1494 9594241 151423 3914II.II.II.II.II.II.II. What happened?!例例2 2 計算計算1010 1 2, , ,.nxnIx e d

12、xne 11101011nxnxnnIx enxe dxn Ie 公式一：公式一：考察第考察第n步的誤差步的誤差nE11|(1)(1)|nnnnnEIInInI| !01En|Enn 我們有責任改變。我們有責任改變。造成這種情況的是造成這種情況的是不穩(wěn)定的算法不穩(wěn)定的算法 /* unstable algorithm */迅速積累，誤差快速遞增。迅速積累，誤差快速遞增。初始的小擾動初始的小擾動801050| .E)1(1111nnnnInIInI 公式二：公式二：注意此公式與公式一注意此公式與公式一在理論上等價。在理論上等價。方法：先估計一個方法：先估計一個IN , ,再反推要求的再反推要求的I

13、n ( n N )。11)1(1 NINeN1112(1)1NNIIe NN 可取可取0* NNNIIEN, ,時時當當()()()()()()1514151314121311121011121110 04274623321616110 06381691815110 06687022014110 07177921413110 07735173212110 08387711511110 367879442I.eII.II.II.II.II.II. ()01110 632120561II.取取考察反推一步的誤差：考察反推一步的誤差：()()1111|11|NNNNEIIENNN 以此類推，對以此類

14、推，對 n N 有：有：|)1(.)1(1|NnEnNNE 誤差逐步遞減誤差逐步遞減, 這樣的算法稱為這樣的算法稱為穩(wěn)定的算法穩(wěn)定的算法 /* stable algorithm */ 在我們今后的討論中，在我們今后的討論中，誤差誤差將不可回避，將不可回避， 算法的算法的穩(wěn)定性穩(wěn)定性將會是一個非常重要的話題。將會是一個非常重要的話題。例例3：蝴蝶效應(yīng)：蝴蝶效應(yīng) 紐約的一只蝴蝶翅膀一拍，風和日紐約的一只蝴蝶翅膀一拍，風和日 麗的北京就刮起臺風來了？！麗的北京就刮起臺風來了？！紐約紐約北京北京這是一個這是一個病態(tài)問題病態(tài)問題蝴蝶效應(yīng)蝴蝶效應(yīng)2 誤差分析的方法和原則誤差分析的方法和原則 /* Erro

15、r Analysis */一、誤差分析的方法一、誤差分析的方法1、向前誤差分析法向前誤差分析法：利用誤差限，：利用誤差限，隨著計算過程隨著計算過程 逐步向前進行分析，直至估計出最后的結(jié)果。逐步向前進行分析，直至估計出最后的結(jié)果。1212()()()xxxx121221()()()xxxxxx12211222()()()xxxxxxx 注：注：兩個近似數(shù)兩個近似數(shù) ，四則運算得到的誤差限分別為，四則運算得到的誤差限分別為12,xx（1 1）（2 2）對于函數(shù)對于函數(shù) y = f (x)，若用，若用 x* 取代取代 x，將對，將對y 產(chǎn)生什產(chǎn)生什 么影響么影響？分析：分析：e*(y) = f (x

16、*) f (x) e*(x) = x* xMean Value Theorem( )()fxx x* 與與 x 非常接近時，可認為非常接近時，可認為 ，則有：，則有：( )()ffx ( )()( )eyfxex 即：即： 產(chǎn)生的誤差經(jīng)過產(chǎn)生的誤差經(jīng)過 作用后被作用后被放大放大/ /縮小縮小了了 倍。倍。故稱故稱 為為放大放大/縮小縮小因子因子 /* amplification factor */ 或或 絕對絕對條件數(shù)條件數(shù) /* absolute condition number */.x f()f x ()f x ( )|( )|()reyeyf x ( )|( )|rexexx ()(

17、)( )()()( )()rrf xf xxxxeyxxf xxxfxexf x 相對誤差條件數(shù)相對誤差條件數(shù) /* relative condition number*/ f 的條件數(shù)在某一點是的條件數(shù)在某一點是小小 大大，則稱則稱 f 在該點是在該點是好條好條件的件的 /* well-conditioned */ 壞條件的壞條件的 /* ill-conditioned */。注：注：關(guān)于多元函數(shù)關(guān)于多元函數(shù) 可類似討論可類似討論，理論工具：理論工具：Taylor公式公式 (教材第教材第7頁頁).,(21nx,x,xfy ()( )()fxexf x 例例4 4105%x 設(shè)設(shè) ,試求函數(shù)試

18、求函數(shù) 的相對誤差限的相對誤差限. ( )nf xx 解：解：由題設(shè)知由題設(shè)知:近似值為近似值為 ,絕對誤差限為絕對誤差限為 10 x ()5%x 1111()()nnfxxxnnx ()() ()()0.005()()()re ffx e xe xeff xf xnxn 2、向后誤差分析法向后誤差分析法：把舍入誤差的累積與導(dǎo)出：把舍入誤差的累積與導(dǎo)出 的已的已知知 量量 的某種攝動（微小誤差）等價起來，的某種攝動（微小誤差）等價起來， A 12,nx xx即令即令1122(,)nnAf xxx 利用攝動理論，由利用攝動理論，由 的界估計出最后的舍入誤差界。的界估計出最后的舍入誤差界。i 3、

19、區(qū)間分析法區(qū)間分析法：把參加運算的數(shù)都看成區(qū)間量，：把參加運算的數(shù)都看成區(qū)間量，根根據(jù)區(qū)間運算規(guī)則求得最后結(jié)果的近似值和誤差限。據(jù)區(qū)間運算規(guī)則求得最后結(jié)果的近似值和誤差限。4、概率分析法概率分析法：利用概率統(tǒng)計方法，將：利用概率統(tǒng)計方法，將數(shù)據(jù)和運算中數(shù)據(jù)和運算中 的舍入誤差視為適合某種分布的隨機變量，然后確定計的舍入誤差視為適合某種分布的隨機變量，然后確定計算結(jié)果的誤差分布。算結(jié)果的誤差分布。 二、幾點注意事項二、幾點注意事項 /* Remarks */1、 避免相近二數(shù)相減避免相近二數(shù)相減例：例：a1 = 0.12345，a2 = 0.12346，各有，各有5位有效數(shù)字。位有效數(shù)字。 而而

20、 a2 a1 = 0.00001，只剩下，只剩下1位有效數(shù)字位有效數(shù)字。 幾種經(jīng)驗性避免方法：幾種經(jīng)驗性避免方法：;xxxx ;1lnlnln xxx當當 | x | 1 時：時：;2sin2cos12xx .6121112xxxex2、 避免小分母避免小分母 : 分母小會造成浮點溢出分母小會造成浮點溢出 /* over flow */3、避免大數(shù)避免大數(shù)吃吃小數(shù)小數(shù)例：例：用單精度計算用單精度計算 的根。的根。010)110(992 xx精確解為精確解為110291 x,x 算法算法1 1：利用求根公式利用求根公式aacbbx242 在計算機內(nèi)，在計算機內(nèi)，109存為存為0.1 1010，1存為存為0.1 101。做加法時，做加法時，兩加數(shù)的指數(shù)先向大指數(shù)對齊，再將浮點部分相加。即兩加數(shù)的指數(shù)先向大指數(shù)對齊，再將浮點部分相加。即1 的指數(shù)部分須變?yōu)榈闹笖?shù)部分須變?yōu)?010，則：，則：1 = 0.0000000001 1010，取取單精度時就成為：單精度時就成為： 109+1=0.10000000 1010+0.00000000 1010=