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

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

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

3、浮點(diǎn)運(yùn)算，記為，記為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 運(yùn)算順序浮點(diǎn)運(yùn)算量第第1章章 緒論緒論例:解線性方程組 的Grammar 方法： 其中 是方程組系數(shù)矩陣 對(duì)應(yīng)的行列式，而 則是以右端向量 替代 的第 列所得矩陣對(duì)應(yīng)的行列式。由線性代數(shù)知識(shí)可知，若 ，則其中 是由 變換到 所需的置換次數(shù). 可見(jiàn)每計(jì)算一個(gè)行列式, 需要 個(gè)浮點(diǎn)運(yùn)算；因此，按Gram

4、mar方法解方程組約需 個(gè)浮點(diǎn)運(yùn)算。當(dāng) 時(shí) ，用一個(gè)運(yùn)算速度為 秒的計(jì)算機(jī)進(jìn)行求解，約需10年。而n=20的方程組是一個(gè)小型的方程組。因此Grammar方法是一個(gè)不能接受的算法，它缺乏可計(jì)算性。 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é)模型時(shí)，忽略次要因素而造

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

6、數(shù) 可以表示為以下具有 位有效數(shù)字的形式lLlU 其中: 稱為指數(shù)部分,12,.,td dd 稱為尾數(shù)( , , ,)Ft L U 將計(jì)算機(jī)中所能表示的全體數(shù)的集合稱為計(jì)浮點(diǎn)數(shù),系算機(jī)的記為 第第1章章 緒論緒論浮點(diǎn)數(shù)系浮點(diǎn)數(shù)系第第1章章 緒論緒論1.2 1.2 數(shù)值方法的分析數(shù)值方法的分析 在計(jì)算機(jī)的浮點(diǎn)數(shù)系中,四則運(yùn)算是非封閉的 為使經(jīng)過(guò)算術(shù)運(yùn)算產(chǎn)生的結(jié)果仍然以同一浮點(diǎn)數(shù)系中的數(shù)表示,必須用一個(gè)比較接近的浮點(diǎn)數(shù)代替.因此會(huì)產(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ù)運(yùn)算的相對(duì)舍入誤差滿足 ( )fl xx記為 的浮點(diǎn)近似 , 則其 相對(duì)誤差為 -( )( )xfl xxx ,1112 ()0,2,3,2xtddddltxdjttj 在任何一個(gè) 進(jìn)制中 實(shí)數(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é)果的運(yùn)算，尤其是避免小數(shù)作為除數(shù)避免產(chǎn)生大結(jié)果的運(yùn)算，尤其是避免

9、小數(shù)作為除數(shù) 參加運(yùn)算；參加運(yùn)算；(2)(2)避免避免“大大”“”“小小”數(shù)相加減；數(shù)相加減；(3)(3)避免相近數(shù)相減，防止大量有效數(shù)字損失；避免相近數(shù)相減，防止大量有效數(shù)字損失；(4)(4)盡可能簡(jiǎn)化運(yùn)算步驟，減少運(yùn)算次數(shù)。盡可能簡(jiǎn)化運(yùn)算步驟，減少運(yùn)算次數(shù)。浮點(diǎn)運(yùn)算原則浮點(diǎn)運(yùn)算原則二、算法的可靠性二、算法的可靠性問(wèn)題的性態(tài)：?jiǎn)栴}的性態(tài)： 例：方程組 的解是：若將方程組的系數(shù)改寫(xiě)成具有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條件則稱這個(gè)數(shù) 為該問(wèn)題的記為數(shù)( )f x設(shè)問(wèn)題的已知輸入數(shù)據(jù) 只有一個(gè)x,用 表示xx若有兩個(gè)輸入數(shù)據(jù) 和( ),( )f xf x,則可得到兩個(gè)不同的結(jié)果0 x 當(dāng)時(shí),( )0f x 設(shè)有,0m 若存在數(shù),滿足以下關(guān)系式( ) ( ) ( ) f xf xxxmf xx第第1章章 緒論緒論1.2 1.2 數(shù)值方法的分析數(shù)值方

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

12、步的誤差，隨著計(jì)算步數(shù)的增加被嚴(yán)重地放大，特別是竟變成負(fù)數(shù)（注意：被積函數(shù)是非負(fù)函數(shù)），而方法則相反；這是因?yàn)榉椒ㄖ?，若前步有誤差： ，則n步誤差:8 , 1,0,101 ndxexeIxnn11nnnII)1(11nnInI方法 準(zhǔn)確值.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說(shuō)明的

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

14、定了一串運(yùn)算，以產(chǎn)生一個(gè)問(wèn)題或者一類問(wèn)題的解類問(wèn)題的解 第第1章章 緒論緒論n具有的特征具有的特征 算法應(yīng)具有以下的特征：算法應(yīng)具有以下的特征： 正確性正確性 有窮性有窮性 適用范圍廣適用范圍廣 運(yùn)算工作量少運(yùn)算工作量少 使用資源少使用資源少 邏輯結(jié)構(gòu)簡(jiǎn)單邏輯結(jié)構(gòu)簡(jiǎn)單 便于實(shí)現(xiàn)便于實(shí)現(xiàn) 計(jì)算結(jié)果可靠計(jì)算結(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個(gè)數(shù)按順序相加個(gè)數(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算法實(shí)例算法實(shí)例niiaS1 計(jì)算計(jì)算第第1章章 緒論緒論1.3 1.3 數(shù)值方法的分析數(shù)值方法的分析l算法算法SUM2(A,n,S)SUM2(A,n,S) 將數(shù)組將數(shù)組A A中的中的n n個(gè)數(shù)中的正數(shù)與負(fù)分別相加個(gè)數(shù)中的正數(shù)與負(fù)分別相加, ,并將并將和存放于和存放于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中的有相同符號(hào)的中的有相同符號(hào)的n n個(gè)數(shù)的和個(gè)數(shù)的和, ,按絕對(duì)值按絕對(duì)值遞增的順序?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ù)按其符號(hào)分成兩組中的數(shù)按其符號(hào)分成兩組, ,分別按算法分別按算法SUM3SUM3求和求和, ,最后計(jì)算和最后計(jì)算和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