數(shù)值分析NumericalAnalysis

1、數(shù)值分析NumericalAnalysis&教材教材 (Text Book) 數(shù)值計算方法數(shù)值計算方法 李維國、黃炳家、同登科、王子亭李維國、黃炳家、同登科、王子亭 編著編著 2004& 參考書目參考書目 (Reference) 數(shù)值計算方法數(shù)值計算方法 () 林成森林成森 編著編著 （科學出版社（科學出版社 1998 Principle of Numerical Analysis 數(shù)值分析原理數(shù)值分析原理 封建湖、車剛明、聶玉峰封建湖、車剛明、聶玉峰 編著編著 （科學出版社，（科學出版社，2001 課程評分方法課程評分方法 (Grading Policies) 平時成績和上機

2、實驗平時成績和上機實驗 (25%左右左右) 期末考試成績期末考試成績 (75%左右左右) 提問：數(shù)值計算方法是做什么用的？提問：數(shù)值計算方法是做什么用的？研究對象研究對象：數(shù)值問題數(shù)值問題有限個輸入數(shù)據(jù)（問題的自有限個輸入數(shù)據(jù)（問題的自變量、原始數(shù)據(jù)）與有限個輸出數(shù)據(jù)（待求解數(shù)據(jù)）之變量、原始數(shù)據(jù)）與有限個輸出數(shù)據(jù)（待求解數(shù)據(jù)）之間函數(shù)關系的一個明確無歧義的描述。間函數(shù)關系的一個明確無歧義的描述。如一階微分方程初值問題如一階微分方程初值問題2(0)1dyxdxy求函數(shù)解析表達式求函數(shù)解析表達式( )yy x數(shù)學問題數(shù)學問題求函數(shù)求函數(shù) 在某些點在某些點( )yy x 1niix的近似函數(shù)值的近

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

4、雜度要小可可靠靠性性分分析析計算復雜性計算復雜性誤差估計：運算結果不能產生太大的偏差且誤差估計：運算結果不能產生太大的偏差且能夠控制誤差能夠控制誤差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ù)和計算過程會產生新的誤差、由于機器字長有限，原始數(shù)據(jù)和計算過程會產生新的誤差 舍入誤差舍入誤差 /* Roundoff Error */二、二、 誤差分析的基本概念誤差分析的基本概念 /* Basic Concepts */ 設設 為真值（精確值），為真值（精確值）， 為為 的一個近似值的一個近似值 稱稱 為近似值為近似值 的絕對誤差，簡稱誤差。的絕對誤差，簡稱誤差。 xxx x exx 注：注：誤差可正可負，常常是無限位

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

7、xxex 1 2 .Def（相對誤差（相對誤差/* relative error */ ）相對相對誤差也可正可負誤差也可正可負rexxxx 1 3 .Def（有效數(shù)字有效數(shù)字/*Significant Digits*/ ）相對相對誤差限誤差限相對相對誤差的絕對值的上界誤差的絕對值的上界r /* relative accuracy */如：如：31415926. 314. 3141592. 3位位21102e 6位位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 aa n3.1415926535897932;3.1415 例例1：問：問： 有幾位有效數(shù)字？請證明你的結論。有幾位有效數(shù)字？請證明你的結論。 *10501050*and103141504131 .| ,

9、.*證明：證明：有有 位有效數(shù)字，精確到小數(shù)點后第位有效數(shù)字，精確到小數(shù)點后第 位。位。43規(guī)格化形式規(guī)格化形式注：注：若若 的每一位都是有效數(shù)字，則的每一位都是有效數(shù)字，則 稱是稱是有效數(shù)有效數(shù)x x 特別，經特別，經“四舍五入四舍五入”得到的數(shù)均為有效數(shù)得到的數(shù)均為有效數(shù)1 1 .Th1 2010mknx.aaaa 將將 的近似值的近似值 表示為表示為 ，若若 是有效數(shù)字，則相對誤差不超過是有效數(shù)字，則相對誤差不超過 ；反之，若已知相對誤差反之，若已知相對誤差 ，且有，且有 ，11102()k xre 1102kre x kaka則則 必為有效數(shù)字。必為有效數(shù)字。證明：證明：一方面，一方面

10、， 是有效數(shù)字，是有效數(shù)字， ka則則1102m kxx 且且111 101010mmx 111101210102()m kkmrxxex 另一方面，另一方面，11101022km kxxx 1102krxxex 10mx 必為有效數(shù)字，必為有效數(shù)字， ka即即 至少有至少有 位有效數(shù)字位有效數(shù)字x k注注: :定理定理1說明了說明了有效數(shù)字與相對誤差限的關系有效數(shù)字與相對誤差限的關系. 有效數(shù)字有效數(shù)字 相對誤差限相對誤差限1212110 51010010201102mnnrmnnne.ex.a aa.a aaa 已知已知 x* 有有 n 位有效數(shù)字，則其相對誤差限為位有效數(shù)字，則其相對誤差

11、限為 相對誤差限相對誤差限 有效數(shù)字有效數(shù)字112111111001021101100 51021|()()()nmrnmmnxxex.a aaa.a 1111021()nrea 已知已知 x* 的相對誤差限可寫為的相對誤差限可寫為則則可見可見 x* 至少有至少有 n 位有效數(shù)字。位有效數(shù)字。例例2 2：為使：為使 的相對誤差小于的相對誤差小于0.001%, ,至少應取幾位有至少應取幾位有效數(shù)字？效數(shù)字？*解：解：假設假設 * 取到取到 n 位有效數(shù)字，則其相對誤差上限為位有效數(shù)字，則其相對誤差上限為111102nrea 要保證其相對誤差小于要保證其相對誤差小于0.001%，只要保證其上限滿足

12、，只要保證其上限滿足111100 0012.%nrea 已知已知 a1 = 3，則從以上不等式可解得，則從以上不等式可解得 n 6 log6，即即 n 6，應取，應取 * 。例例3 3 計算下列多項式的值計算下列多項式的值nnnaxaxaxp10)(為已知數(shù)據(jù)為已知數(shù)據(jù)01,na aax分析：分析：輸入數(shù)據(jù)為輸入數(shù)據(jù)為 ，輸出數(shù)據(jù)為，輸出數(shù)據(jù)為 ，若直接由，若直接由 算出算出 ，再乘相應的系數(shù)，再乘相應的系數(shù) 并并相加，則要做次相加，則要做次 乘法和乘法和 次加法，占用個次加法，占用個 存儲單元。存儲單元。 0,naaxx)(xpnxx,2021,aaann12()nn n12 n秦九韶方法，

13、也稱為秦九韶方法，也稱為HornerHorner算法算法 用遞推公式表示為用遞推公式表示為nnaxaxaxaxp)()(11000ab xbabiii1ni, 2 , 1)(xpbnn只用只用 次乘法和次乘法和 次加法，并占用次加法，并占用 個存儲單元個存儲單元 n2nn三、數(shù)值算法及穩(wěn)定性三、數(shù)值算法及穩(wěn)定性 /* Numerical Algorithm and Stability */大家一起猜？大家一起猜？ dxe2x1011 / e解法之一解法之一：將將 作作Taylor展開后再積分展開后再積分2xe 91!4171!3151!21311)!4!3!21(10864210dxxxxxd

14、xe2xS4R4 /* Remainder */,104 Sdxe2x取取則則 111!5191!414R稱為截斷誤差稱為截斷誤差 /* Truncation Error */005091!414.R 這這里里7430024010333014211013114.S 0010200050. | 舍入誤差舍入誤差 /* Roundoff Error */ |006000100050102.dxe-x 的的總總體體誤誤差差計計算算= 0.747 由截去部分由截去部分/* excluded terms */引起引起由留下部分由留下部分/* included terms */引起引起例例4 4 近似計算

15、近似計算210 xedx 10 333333. 10 0238042. 一個算法如果輸入數(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 */） 對數(shù)學問題本身如果輸入數(shù)據(jù)有微小擾動，引起對數(shù)學問題本身如果輸入數(shù)據(jù)有微小擾動，引起輸出數(shù)據(jù)（即問題真解）的很大擾動，這就是病態(tài)問輸出數(shù)據(jù)（即問題真解）的很大擾動，這就是病態(tài)問題。題。1 5 .

16、Def（病態(tài)問題（病態(tài)問題/ /* ill-posed problem */） 它是數(shù)學問題本身性質所決定的，與算法無關，它是數(shù)學問題本身性質所決定的，與算法無關，也就是說對病態(tài)問題，用任何算法（或方法）直接計也就是說對病態(tài)問題，用任何算法（或方法）直接計算都將產生不穩(wěn)定性。算都將產生不穩(wěn)定性。 此公式精確成立此公式精確成立80001050 .IIE記為記為*0I632120560111100.edxeeIx 則初始誤差則初始誤差111111110010 nI)e(ndxexeIdxexennnn10109111012111312141315141 10 36787944.1 100 0881

17、28001 110 030592001 120 632896001 137 22764801 1494 9594241 151423 3914II.II.II.II.II.II.II. ? ! !What happened?!例例5 5 計算計算1010 1 2, , ,.nxnIx e dxne 11101011nxnxnnIx enxe dxn Ie 公式一：公式一：考察第考察第n步的誤差步的誤差nE11|(1)(1)|nnnnnEIInInI | !01En|Enn 我們有責任改變。我們有責任改變。造成這種情況的是不穩(wěn)定的算法造成這種情況的是不穩(wěn)定的算法 /* unstable algo

18、rithm */迅速積累，誤差呈遞增趨勢。迅速積累，誤差呈遞增趨勢。初始的小擾動初始的小擾動801050| .E)1(1111nnnnInIInI 公式二：公式二：注意此公式與公式一注意此公式與公式一在理論上等價。在理論上等價。方法：先估計一個方法：先估計一個IN , ,再反推要求的再反推要求的In ( n N )。11)1(1 NINeN1112(1)1NNIIe NN 可取可取0* NNNIIEN, ,時時當當()()()()()()1514151314121311121011121110 04274623321616110 06381691815110 06687022014110 07

19、177921413110 07735173212110 08387711511110 367879442I.eII.II.II.II.II.II. ()01110 632120561II.取取考察反推一步的誤差：考察反推一步的誤差：()()1111|11|NNNNEIIENNN 以此類推，對以此類推，對 n N 有：有：|) 1(.) 1(1|NnEnNNE 誤差逐步遞減誤差逐步遞減, 這樣的算法稱為穩(wěn)定的算法這樣的算法稱為穩(wěn)定的算法 /* stable algorithm */ 在我們今后的討論中，誤差將不可回避，在我們今后的討論中，誤差將不可回避， 算法的穩(wěn)定性將會是一個非常重要的話題。算

20、法的穩(wěn)定性將會是一個非常重要的話題。例例6：蝴蝶效應：蝴蝶效應 紐約的一只蝴蝶翅膀一拍，風和日紐約的一只蝴蝶翅膀一拍，風和日 麗的北京就刮起臺風來了？！麗的北京就刮起臺風來了？！紐約紐約北京北京這是一個病態(tài)問題這是一個病態(tài)問題2 誤差分析的方法和原則誤差分析的方法和原則 /* Error Analysis */一、誤差分析的方法一、誤差分析的方法1、向前誤差分析法：利用誤差限，、向前誤差分析法：利用誤差限，隨著計算過程隨著計算過程 逐步向前進行分析，直至估計出最后的結果。（例逐步向前進行分析，直至估計出最后的結果。（例4 4） 1212()()()xxxx 121221()()()xxxxxx

21、 12211222()()()xxxxxxx 注：注：兩個近似數(shù)兩個近似數(shù) ，四則運算得到的誤差限分別為，四則運算得到的誤差限分別為12,xx（1 1）（2 2）對于函數(shù)對于函數(shù) y = f (x)，若用，若用 x* 取代取代 x，將對，將對y 產生什產生什 么影響么影響？分析：分析：e*(y) = f (x*) f (x) e*(x) = x* xMean Value Theorem( )()fxx x* 與與 x 非常接近時，可認為非常接近時，可認為 ，則有：，則有：( )()ffx ( )()( )e yf xe x 即：即： 產生的誤差經過產生的誤差經過 作用后被放大作用后被放大/ /

22、縮小了縮小了 倍。倍。故稱故稱 為放大為放大/縮小縮小因子因子 /* amplification factor */ 或或 絕對絕對條件數(shù)條件數(shù) /* absolute condition number */.x f()f x ()f x ( )|( )|()reyeyf x ( )|( )|rexexx ()( )( )()()( )()rrf xf xxxxeyxxf xxxfxexf x 相對誤差條件數(shù)相對誤差條件數(shù) /* relative condition number*/ f 的條件數(shù)在某一點是小的條件數(shù)在某一點是小 大，則稱大，則稱 f 在該點是好條在該點是好條件的件的 /* w

23、ell-conditioned */ 壞條件的壞條件的 /* ill-conditioned */。注：關于多元函數(shù)注：關于多元函數(shù) 可類似討論，可類似討論，理論工具：理論工具：Taylor公式公式 (教材第教材第6頁頁).,(21nx,x,xfy ()( )()fxexf x 例例7 7105%x 設設 ,試求函數(shù)試求函數(shù) 的相對誤差限的相對誤差限. ( )nf xx 解：解：由題設知由題設知:近似值為近似值為 ,絕對誤差限為絕對誤差限為 10 x ()5%x 1111()()nnfxxxnnx re ffx e xe xeff xf xnxn()() ()()0.005()()() 2、向

24、后誤差分析法：把舍入誤差的累積與導出、向后誤差分析法：把舍入誤差的累積與導出 的已的已知知 量量 的某種攝動（微小誤差）等價起來，的某種攝動（微小誤差）等價起來， A 12,nx xx即令即令1122(,)nnAf xxx 利用攝動理論，由利用攝動理論，由 的界估計出最后的舍入誤差界。的界估計出最后的舍入誤差界。i 3、區(qū)間分析法：把參加運算的數(shù)都看成區(qū)間量，、區(qū)間分析法：把參加運算的數(shù)都看成區(qū)間量，根根據(jù)區(qū)間運算規(guī)則求得最后結果的近似值和誤差限。據(jù)區(qū)間運算規(guī)則求得最后結果的近似值和誤差限。4、概率分析法：利用概率統(tǒng)計方法，將、概率分析法：利用概率統(tǒng)計方法，將數(shù)據(jù)和運算中數(shù)據(jù)和運算中 的舍入誤

25、差視為適合某種分布的隨機變量，然后確定計的舍入誤差視為適合某種分布的隨機變量，然后確定計算結果的誤差分布。算結果的誤差分布。 二、幾點注意事項二、幾點注意事項 /* Remarks */1、 避免相近二數(shù)相減避免相近二數(shù)相減例：例：a1，a2，各有，各有5位有效數(shù)字。位有效數(shù)字。 而而 a2 a1，只剩下，只剩下1位有效數(shù)字位有效數(shù)字。 幾種經驗性避免方法：幾種經驗性避免方法：;xxxx ;1lnlnln xxx當當 | x | 1 時：時：;2sin2cos12xx .6121112xxxex2、 避免小分母避免小分母 : 分母小會造成浮點溢出分母小會造成浮點溢出 /* over flow

26、*/3、避免大數(shù)吃小數(shù)、避免大數(shù)吃小數(shù)例：用單精度計算例：用單精度計算 的根。的根。010)110(992 xx精確解為精確解為110291 x,x 算法算法1 1：利用求根公式：利用求根公式aacbbx242 在計算機內，在計算機內，109存為存為 1010，1存為存為 101。做加法時，兩加做加法時，兩加數(shù)的指數(shù)先向大指數(shù)對齊，再將浮點部分相加。即數(shù)的指數(shù)先向大指數(shù)對齊，再將浮點部分相加。即1 的指的指數(shù)部分須變?yōu)閿?shù)部分須變?yōu)?010，則：，則：1 = 0.01 1010，取單精度時就成為：，取單精度時就成為： 109 1010+0.00000000 1010=0.10000000 1010大數(shù)吃小數(shù)大數(shù)吃小數(shù)024,102422921 aacbbxaacbbx算法算法2：先解出：先解出 再利用再利用9211024)( aacbbsignbx11010991221 xacxacxx求和時從小到大相加，可使和的誤差