數(shù)學(xué)與統(tǒng)計學(xué)院李義寶

1、數(shù)學(xué)與統(tǒng)計學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院 李義寶李義寶理科樓理科樓 312計算方法教程計算方法教程凌永祥凌永祥 陳明逵陳明逵 西安交通大學(xué)出版社西安交通大學(xué)出版社計算方法計算方法鄧建中鄧建中, ,西安交通大學(xué)出版社西安交通大學(xué)出版社數(shù)值分析數(shù)值分析李乃成李乃成, ,梅立泉梅立泉 科學(xué)出版社科學(xué)出版社參考書參考書課程基礎(chǔ)課程基礎(chǔ)數(shù)學(xué)基礎(chǔ)數(shù)學(xué)基礎(chǔ) 計算機基礎(chǔ)計算機基礎(chǔ) 高等數(shù)學(xué)高等數(shù)學(xué) 線性代數(shù)線性代數(shù) 計算機語言計算機語言 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 課程成績課程成績 考試成績考試成績 70%70%上機成績上機成績 30%30%應(yīng)用計算機解決問題應(yīng)用計算機解決問題 1.1.建立數(shù)學(xué)模型建立數(shù)學(xué)模型2.2.計算問題的解

2、計算問題的解3.3.實驗驗證實驗驗證第第1章章 緒論緒論什么是計算方法什么是計算方法1.1 1.1 數(shù)值計算數(shù)值計算第第1章章 緒論緒論計算方法的任務(wù)計算方法的任務(wù)1.1 1.1 數(shù)值計算數(shù)值計算第第1章章 緒論緒論問題的類型問題的類型bAx計算方法的選擇計算方法的選擇 1.1.可行性可行性2.2.計算效率計算效率3.3.算法穩(wěn)定性算法穩(wěn)定性1.2 1.2 數(shù)值方法的分析數(shù)值方法的分析n定義定義 通常以計算機完成操作通常以計算機完成操作 a+ba+b* *c ,c ,即一次浮點加法即一次浮點加法和一次浮點乘法所需的時間作為一個時間單位，稱為和一次浮點乘法所需的時間作為一個時間單位，稱為浮點運算

3、浮點運算，記為，記為flopflop. .12341.3 ,1020,2050,50 1,1 100 A A A A例設(shè)分別為 的矩陣,則按結(jié)合律,有 11500 flop 125000 flop 2200 flop1234()PA A A A1234()PA A A A1234()PA A AA 運算順序浮點運算量第第1章章 緒論緒論例:解線性方程組 的Grammar 方法： 其中 是方程組系數(shù)矩陣 對應(yīng)的行列式，而 則是以右端向量 替代 的第 列所得矩陣對應(yīng)的行列式。由線性代數(shù)知識可知，若 ，則其中 是由 變換到 所需的置換次數(shù). 可見每計算一個行列式, 需要 個浮點運算；因此，按Gram

4、mar方法解方程組約需 個浮點運算。當(dāng) 時 ，用一個運算速度為 秒的計算機進行求解，約需10年。而n=20的方程組是一個小型的方程組。因此Grammar方法是一個不能接受的算法，它缺乏可計算性。 bAx nixii, 2 , 1AAAAiAbAi)(ijAnnniiiiiiJ212121),()1(A),(21niiiJn, 2,1niii,21!) 1(nn!) 1(2nnN20n20107 . 9N/1038408 1.2 1.2 數(shù)值方法的分析數(shù)值方法的分析n定義定義 誤差誤差是指近似值與真正值之差是指近似值與真正值之差 誤差分類誤差分類模型誤差模型誤差在建立數(shù)學(xué)模型時，忽略次要因素而造

5、成的在建立數(shù)學(xué)模型時，忽略次要因素而造成的數(shù)據(jù)誤差數(shù)據(jù)誤差由于問題中的值通過觀察得到的，從而產(chǎn)生誤差由于問題中的值通過觀察得到的，從而產(chǎn)生誤差截斷誤差截斷誤差通過近似替代，簡化為較易求解的問題通過近似替代，簡化為較易求解的問題舍入誤差舍入誤差由于計算機中的性能限制而造成的由于計算機中的性能限制而造成的第第1章章 緒論緒論后兩種誤差主要是由于計算機的字長有限，采用浮點數(shù)系所致。所后兩種誤差主要是由于計算機的字長有限，采用浮點數(shù)系所致。所以首先介紹浮點數(shù)系以首先介紹浮點數(shù)系1.2 1.2 數(shù)值方法的分析數(shù)值方法的分析,1112 ()0,2,3,2xtddddltxdjttj 在任何一個 進制中 實

6、數(shù) 可以表示為以下具有 位有效數(shù)字的形式lLlU 其中: 稱為指數(shù)部分,12,.,td dd 稱為尾數(shù)( , , ,)Ft L U 將計算機中所能表示的全體數(shù)的集合稱為計浮點數(shù),系算機的記為 第第1章章 緒論緒論浮點數(shù)系浮點數(shù)系第第1章章 緒論緒論1.2 1.2 數(shù)值方法的分析數(shù)值方法的分析 在計算機的浮點數(shù)系中,四則運算是非封閉的 為使經(jīng)過算術(shù)運算產(chǎn)生的結(jié)果仍然以同一浮點數(shù)系中的數(shù)表示,必須用一個比較接近的浮點數(shù)代替.因此會產(chǎn)生誤差 ,稱此誤差為舍入誤差第第1章章 緒論緒論1.2 1.2 數(shù)值方法的分析數(shù)值方法的分析223(2,3,-1,2)(0.100 2 ) (0.110 2 )0.11

7、0 2F上溢 在中 012(2,3,-1,2)(0.100 2 ) (0.110 2 )0.110 2F下溢 在中 第第1章章 緒論緒論1.2 1.2 數(shù)值方法的分析數(shù)值方法的分析001(2,3,-1,2)(0.100 2 )(0.111 2 )0.1101 2F 在中 第第1章章 緒論緒論1.2 1.2 數(shù)值方法的分析數(shù)值方法的分析11( )2tx 可以證明,在數(shù)系F( ,t,L,U)中,算術(shù)運算的相對舍入誤差滿足 ( )fl xx記為 的浮點近似 , 則其 相對誤差為 -( )( )xfl xxx ,1112 ()0,2,3,2xtddddltxdjttj 在任何一個 進制中 實數(shù) 可以表

8、示為以下具有 位有效數(shù)字的形式第第1章章 緒論緒論-( )( )xfl xxx 第第1章章 緒論緒論1.2 1.2 數(shù)值方法的分析數(shù)值方法的分析( ),( )(1) ,xfl xx設(shè)則有因此可得123()(1-)()()(1-)()( )(1-)( )fl xyxyfl xyxyxxflyy123-()()-()()-( )( )xyfl xyxyxyfl xyxyxxxflyyy第第1章章 緒論緒論1.2 1.2 數(shù)值方法的分析數(shù)值方法的分析第第1章章 緒論緒論1.2 1.2 數(shù)值方法的分析數(shù)值方法的分析(1)(1)避免產(chǎn)生大結(jié)果的運算，尤其是避免小數(shù)作為除數(shù)避免產(chǎn)生大結(jié)果的運算，尤其是避免

9、小數(shù)作為除數(shù) 參加運算；參加運算；(2)(2)避免避免“大大”“”“小小”數(shù)相加減；數(shù)相加減；(3)(3)避免相近數(shù)相減，防止大量有效數(shù)字損失；避免相近數(shù)相減，防止大量有效數(shù)字損失；(4)(4)盡可能簡化運算步驟，減少運算次數(shù)。盡可能簡化運算步驟，減少運算次數(shù)。浮點運算原則浮點運算原則二、算法的可靠性二、算法的可靠性問題的性態(tài)：問題的性態(tài)： 例：方程組 的解是：若將方程組的系數(shù)改寫成具有2位有效數(shù)字的小數(shù)： 的解： ；604751413112134131216113121321321321xxxxxxxxx111X78. 020. 025. 033. 01 . 125. 033. 050. 0

10、8 . 133. 050. 000. 132132121xxxxxxxxx65.3325.3822. 6X第第1章章 緒論緒論1.2 1.2 數(shù)值方法的分析數(shù)值方法的分析n定義定義 第第1章章 緒論緒論1.2 1.2 數(shù)值方法的分析數(shù)值方法的分析,( )mCond f條件則稱這個數(shù) 為該問題的記為數(shù)( )f x設(shè)問題的已知輸入數(shù)據(jù) 只有一個x,用 表示xx若有兩個輸入數(shù)據(jù) 和( ),( )f xf x,則可得到兩個不同的結(jié)果0 x 當(dāng)時,( )0f x 設(shè)有,0m 若存在數(shù),滿足以下關(guān)系式( ) ( ) ( ) f xf xxxmf xx第第1章章 緒論緒論1.2 1.2 數(shù)值方法的分析數(shù)值方

11、法的分析n定義定義 在執(zhí)行某一數(shù)值方法時，如果由初始誤差導(dǎo)致最終解在執(zhí)行某一數(shù)值方法時，如果由初始誤差導(dǎo)致最終解的誤差能被有效地控制，這樣的方法是的誤差能被有效地控制，這樣的方法是數(shù)值穩(wěn)定數(shù)值穩(wěn)定的的 方法的數(shù)值穩(wěn)定性是指運算中由初始誤差通過計算方法的數(shù)值穩(wěn)定性是指運算中由初始誤差通過計算導(dǎo)致的最終解的誤差的可控性導(dǎo)致的最終解的誤差的可控性反之，如果各個計算過程中的誤差不斷增長，且不能反之，如果各個計算過程中的誤差不斷增長，且不能被有效地控制，則該方法稱為被有效地控制，則該方法稱為數(shù)值不穩(wěn)定數(shù)值不穩(wěn)定的的算法的穩(wěn)定性算法的穩(wěn)定性 例:計算積分解：由微積分，有計算公式， 由上表可見，方法中，原始

12、步的誤差，隨著計算步數(shù)的增加被嚴重地放大，特別是竟變成負數(shù)（注意：被積函數(shù)是非負函數(shù)），而方法則相反；這是因為方法中，若前步有誤差： ，則n步誤差:8 , 1,0,101 ndxexeIxnn11nnnII)1(11nnInI方法 準確值.6321.36792462.2073.1709.1455.1268.1124.1010 .6321.3679.2462.2074.1704.1480.1120.2160-.7280 .6320.3680.2643.2073.1709.1455.1268.1124.10100I1I2I3I4I5I6I7I8I11:nnIInInnIInInnnn1111說明的

13、誤差，經(jīng)一步計算后被擴大了n倍，隨著n增大，誤差將被大大地擴大；而通過同樣的分析可知：方法中的誤差則被縮小倍 算法的數(shù)值穩(wěn)定性算法的數(shù)值穩(wěn)定性：算法對初始誤差導(dǎo)致的最算法對初始誤差導(dǎo)致的最終誤差的可控性終誤差的可控性，如果最終誤差被有效地控制，則稱算法是穩(wěn)定的，否則就是不穩(wěn)定的。 因此,方法是不穩(wěn)定的,而則是穩(wěn)定的.nIInInInnnn1)1 (1)1 (111第第1章章 緒論緒論1.3 1.3 數(shù)值方法的分析數(shù)值方法的分析n定義定義 算法算法是由有限個無二義性的法則組成的一個計算過程，是由有限個無二義性的法則組成的一個計算過程，這些法則明確規(guī)定了一串運算，以產(chǎn)生一個問題或者一這些法則明確規(guī)

14、定了一串運算，以產(chǎn)生一個問題或者一類問題的解類問題的解 第第1章章 緒論緒論n具有的特征具有的特征 算法應(yīng)具有以下的特征：算法應(yīng)具有以下的特征： 正確性正確性 有窮性有窮性 適用范圍廣適用范圍廣 運算工作量少運算工作量少 使用資源少使用資源少 邏輯結(jié)構(gòu)簡單邏輯結(jié)構(gòu)簡單 便于實現(xiàn)便于實現(xiàn) 計算結(jié)果可靠計算結(jié)果可靠1.3 1.3 數(shù)值方法的分析數(shù)值方法的分析第第1章章 緒論緒論1.3 1.3 數(shù)值方法的分析數(shù)值方法的分析l算法算法SUM1(A,n,S)SUM1(A,n,S) 將數(shù)組將數(shù)組A A中的中的n n個數(shù)按順序相加個數(shù)按順序相加, ,并將和存放于并將和存放于S S中中1. 0-s1. 0-s

15、2. For i=1,2,2. For i=1,2,n,n 2.1 S+ai-S 2.1 S+ai-S3. 3. 輸出輸出S S算法實例算法實例niiaS1 計算計算第第1章章 緒論緒論1.3 1.3 數(shù)值方法的分析數(shù)值方法的分析l算法算法SUM2(A,n,S)SUM2(A,n,S) 將數(shù)組將數(shù)組A A中的中的n n個數(shù)中的正數(shù)與負分別相加個數(shù)中的正數(shù)與負分別相加, ,并將并將和存放于和存放于S S中中1. 0-s1;0-S2;1. 0-s1;0-S2;2. For i=1,2,2. For i=1,2,n,n 2.1 if ai S1 2.1 if ai S1 else S2+ai-S2 e

16、lse S2+ai-S23. S1+S2-S3. S1+S2-S第第1章章 緒論緒論1.3 1.3 數(shù)值方法的分析數(shù)值方法的分析l算法算法SUM3(A,n,S)SUM3(A,n,S) 將數(shù)組將數(shù)組A A中的有相同符號的中的有相同符號的n n個數(shù)的和個數(shù)的和, ,按絕對值按絕對值遞增的順序?qū)⑺鼈兦蠛瓦f增的順序?qū)⑺鼈兦蠛?. 0-s;1. 0-s;2. For i=1,2,2. For i=1,2,n,n 2.1 max-m 2.1 max-m 2.2 for k=1,2, 2.2 for k=1,2,n,n 2.2.1 If ak0 and abs(ak)m then 2.2.1 If ak0

17、and abs(ak)m;k-j; abs(ak)-m;k-j; 2.3 S+ai-s 2.3 S+ai-s 2.4 0-ai 2.4 0-ai第第1章章 緒論緒論1.3 1.3 數(shù)值方法的分析數(shù)值方法的分析l算法算法SUM4(A,n,S)SUM4(A,n,S) 將數(shù)組將數(shù)組A A中的數(shù)按其符號分成兩組中的數(shù)按其符號分成兩組, ,分別按算法分別按算法SUM3SUM3求和求和, ,最后計算和最后計算和S S1. 0-n1;0-n2;1. 0-n1;0-n2;2. For i=1,2,2. For i=1,2,n,n 2.1 if ai=0 then n1+1-n1; ai-bn1; 2.1 if ai=0 then n1+1-n1; ai-bn1; else n2+1-n2; ai-cn2; else n2