數(shù)值分析 引論

1、 計(jì)算方法計(jì)算方法 鄭海標(biāo)鄭海標(biāo)數(shù)學(xué)學(xué)院數(shù)學(xué)學(xué)院Email：n計(jì)算的目的不在于數(shù)據(jù)，而在于洞察事物計(jì)算的目的不在于數(shù)據(jù)，而在于洞察事物。 理查德理查德哈明哈明nThe purpose of computing is insight，not numbers. Richard Wesley Hamming理論分析理論分析 科學(xué)實(shí)驗(yàn)科學(xué)實(shí)驗(yàn) 科學(xué)計(jì)算科學(xué)計(jì)算計(jì)算方法課程簡介計(jì)算方法課程簡介n教材教材 數(shù)值計(jì)算數(shù)值計(jì)算方法方法 李乃成李乃成 鄧建中編鄧建中編n參考書目參考書目 數(shù)值計(jì)算數(shù)值計(jì)算方法方法 馮康等編馮康等編 數(shù)值數(shù)值分析簡明教程分析簡明教程 王能超編王能超編 Numerical Analy

2、sis (Seventh Edition) 數(shù)值分析數(shù)值分析 （第七版（第七版 影印版）影印版） Richard L. Burden & J. Douglas Faires （高等教育出版社）（高等教育出版社）計(jì)算方法學(xué)什么？計(jì)算方法=數(shù)值分析=科學(xué)計(jì)算n計(jì)算方法n數(shù)值逼近n數(shù)值代數(shù)或者矩陣計(jì)算n微分方程數(shù)值解法n非線性數(shù)值解法 成績的評(píng)定方法n期末考試：70% 閉卷n平時(shí)成績：30%=10%平時(shí) +20%上機(jī)n上機(jī)： 周四 7：00-10:30 理科樓二樓西側(cè)機(jī)房 考試： 暫定十月底十一月初第一講第一講 引論引論引論n數(shù)值計(jì)算的研究內(nèi)容n誤差與有效數(shù)字n數(shù)值算法設(shè)計(jì)要點(diǎn)1 1、數(shù)值計(jì)

3、算的研究內(nèi)容、數(shù)值計(jì)算的研究內(nèi)容研究過程 （理論上有解，而無求解公式或計(jì)算（理論上有解，而無求解公式或計(jì)算量過大難以用手工實(shí)現(xiàn)的數(shù)學(xué)問題）量過大難以用手工實(shí)現(xiàn)的數(shù)學(xué)問題）實(shí)際問題數(shù)學(xué)模型數(shù)值分析理論程序設(shè)計(jì)上機(jī)計(jì)算重點(diǎn)內(nèi)容重點(diǎn)內(nèi)容研究并求解數(shù)學(xué)問題的研究并求解數(shù)學(xué)問題的數(shù)值（近似）解的方法數(shù)值（近似）解的方法地球外部大氣流動(dòng)模型地球外部大氣流動(dòng)模型飛機(jī)外形優(yōu)化設(shè)計(jì)問題飛機(jī)外形優(yōu)化設(shè)計(jì)問題研究內(nèi)容n線性方程組的直接法n插值方法n數(shù)值積分n常微分方程的差分方法n方程求根的迭代法n線性方程組的迭代法數(shù)值分析課程的期望n掌握各種解決數(shù)學(xué)問題的數(shù)值方法n對(duì)近似解進(jìn)行評(píng)估n在計(jì)算機(jī)上實(shí)現(xiàn)求解n仿真模擬2

4、2、誤差與有效數(shù)字、誤差與有效數(shù)字誤差無處不在防不勝防誤差無處不在防不勝防例例 (病態(tài)問題)（系數(shù)保留小數(shù)點(diǎn)后4位,再精確計(jì)算）x1=x2=x3=1 x1=1.1788, x2= 0.0006, x3= 1.9658. 病態(tài)問題病態(tài)問題:失之毫厘謬之千里12312312349321949 36440360336310614144107202137693739401036003600 xxxxxxxxx1231231231.36110.75000.52502.63610.75000.43600.30001.47360.52500.30000.21361.0386xxxxxxxxxa. 誤差來源與

5、分類誤差來源與分類 從實(shí)際問題中抽象出數(shù)學(xué)模型從實(shí)際問題中抽象出數(shù)學(xué)模型 模型誤差模型誤差 通過測量得到模型中參數(shù)的值通過測量得到模型中參數(shù)的值 觀測誤差觀測誤差 求求(數(shù)學(xué)表達(dá)的數(shù)學(xué)表達(dá)的)近似解近似解 方法誤差方法誤差 (截?cái)嗾`差截?cái)嗾`差) 模型的準(zhǔn)確解模型的準(zhǔn)確解與用與用數(shù)值方法求得的準(zhǔn)確解數(shù)值方法求得的準(zhǔn)確解之差稱為之差稱為“截?cái)嗾`差截?cái)嗾`差”。 機(jī)器字長有限機(jī)器字長有限 舍入誤差舍入誤差（理論計(jì)算誤差）（理論計(jì)算誤差）模型誤差 ( Modeling Error )n處理實(shí)際問題時(shí)，要建立數(shù)學(xué)模型，通常模處理實(shí)際問題時(shí)，要建立數(shù)學(xué)模型，通常模型只是近似的。由此產(chǎn)生的型只是近似的。由此產(chǎn)

6、生的數(shù)學(xué)模型解數(shù)學(xué)模型解與與實(shí)實(shí)際問題的解際問題的解 之間的誤差叫之間的誤差叫模型誤差模型誤差。n例如例如 是是實(shí)際問題的解，而若數(shù)學(xué)模型的解是實(shí)際問題的解，而若數(shù)學(xué)模型的解是 由此由此產(chǎn)生的誤差叫作模型誤差。產(chǎn)生的誤差叫作模型誤差。8656sin,010yxxx656,010 ,yxx觀測誤差 ( Measurement Error )n數(shù)學(xué)模型中包含某些變量，如時(shí)間、長度、數(shù)學(xué)模型中包含某些變量，如時(shí)間、長度、電壓等，它們一般是通過觀測來獲得。由于電壓等，它們一般是通過觀測來獲得。由于觀測得到的數(shù)據(jù)與實(shí)際數(shù)據(jù)之間有誤差，這觀測得到的數(shù)據(jù)與實(shí)際數(shù)據(jù)之間有誤差，這種誤差叫種誤差叫觀測誤差觀測誤

7、差。截?cái)嗾`差 ( Truncation Error)n求解數(shù)學(xué)模型所用的數(shù)值計(jì)算方法，如果是求解數(shù)學(xué)模型所用的數(shù)值計(jì)算方法，如果是一種近似的方法，只能得到模型的近似解，一種近似的方法，只能得到模型的近似解，由此產(chǎn)生的誤差稱為由此產(chǎn)生的誤差稱為 截?cái)嗾`差截?cái)嗾`差 或或 方法誤差方法誤差。71513114,9171513114舍入誤差 ( Roundoff Error )n由于計(jì)算機(jī)的字長有限，參加運(yùn)算的數(shù)據(jù)及其運(yùn)算結(jié)果在計(jì)算機(jī)中存放會(huì)產(chǎn)生誤差。這種誤差叫舍入誤差舍入誤差 或 計(jì)算誤差計(jì)算誤差。n例如，在 16 位微機(jī)上計(jì)算，單精度實(shí)數(shù)存放僅有 7 位有效數(shù)字。在其上運(yùn)算，會(huì)有1 3 0.333

8、333 3, (1.000 002)2 1.000 004 0;后者的準(zhǔn)確結(jié)果是 4 1012。dxex 102 近近似似計(jì)計(jì)算算: :例例解法之一解法之一：將將 作作Taylor展開后再積分展開后再積分2xe 91!4171!3151!21311)!4!3!21(10864210dxxxxxdxe2xS4R4dxex 102 近近似似計(jì)計(jì)算算: :例例,104 Sdxe2x取取則則 111!5191!414R稱為稱為截?cái)嗾`差截?cái)嗾`差 ( Truncation Error ).005091!414.R 這這里里7430024010333014211013114.S 0010200050. |

9、舍入誤差舍入誤差 ( Roundoff Error ) |006000100050102.dxe-x 的的總總體體誤誤差差計(jì)計(jì)算算= 0.747 由截掉部分引由截掉部分引起起( excluded terms )由留下部分引由留下部分引起起( included terms )b. 誤差誤差與誤差限與誤差限 絕對(duì)誤差絕對(duì)誤差xxe *其中x為精確值，x*為x的近似值。 10006074302.dxex，例如：，例如：*xx 上常記為上常記為|*e*，稱為，稱為絕對(duì)誤差限，絕對(duì)誤差限，一般地，一般地， 的上限記為的上限記為e*0 時(shí)，時(shí)，x*稱為強(qiáng)近似值，稱為強(qiáng)近似值，e*0 時(shí)，時(shí)，x*稱為弱近似

10、值稱為弱近似值 由于通常準(zhǔn)確值 x 是不知道的，所以誤差e* 的準(zhǔn)確值也不可能求出，但根據(jù)具體情況根據(jù)具體情況，可事先估計(jì)出誤差事先估計(jì)出誤差的范圍的范圍誤差絕對(duì)值不能超過某個(gè)正數(shù) ，我們把 叫做誤差絕對(duì)值的“上界”，或稱“誤差限”。 *xx*xxx *工程工程c. 相對(duì)誤差相對(duì)誤差與相對(duì)誤差限與相對(duì)誤差限xeer* |*xr x 的的相對(duì)誤差限相對(duì)誤差限 常定義為常定義為*r *re*xexe*xe*xeer 實(shí)際計(jì)算中，相對(duì)誤差通常取為：實(shí)際計(jì)算中，相對(duì)誤差通常取為：相對(duì)誤差相對(duì)誤差 d. 有效數(shù)字有效數(shù)字 若近似值 x*的誤差限是某一位的半個(gè)單位,該位到 x* 的第一位非零數(shù)字共有 n

11、位,就說 x*有 n 位有效數(shù)字.1415.3*;8979321415926535.3 例例:問：問： 有幾位有效數(shù)字？請(qǐng)證明你的結(jié)論。有幾位有效數(shù)字？請(qǐng)證明你的結(jié)論。* 43* 用科學(xué)計(jì)數(shù)法，記用科學(xué)計(jì)數(shù)法，記 （其中（其中 ）。若）。若 （即（即 的截取按四舍五入規(guī)則），則的截取按四舍五入規(guī)則），則 有有n 位有效數(shù)字，精確到位有效數(shù)字，精確到 。mnaa.ax10021* 01 anm.xx 1050|*na*xnm 10注：關(guān)于有效數(shù)字有以下幾點(diǎn)說明：注：關(guān)于有效數(shù)字有以下幾點(diǎn)說明：1、用四舍五入法取準(zhǔn)確值的前、用四舍五入法取準(zhǔn)確值的前n位作為近似值，則位作為近似值，則x*必必有有n位

12、有效數(shù)字；位有效數(shù)字；2、有效數(shù)字位數(shù)相同的兩個(gè)近似數(shù)，絕對(duì)誤差限不一、有效數(shù)字位數(shù)相同的兩個(gè)近似數(shù)，絕對(duì)誤差限不一定相同；定相同；3、將任何數(shù)乘以、將任何數(shù)乘以10m(m為整數(shù)為整數(shù))，等于移動(dòng)該數(shù)的小數(shù)，等于移動(dòng)該數(shù)的小數(shù)點(diǎn)，并不影響它的有效數(shù)字的位數(shù)；點(diǎn)，并不影響它的有效數(shù)字的位數(shù)；4、準(zhǔn)確值被認(rèn)為具有無窮位有效數(shù)字、準(zhǔn)確值被認(rèn)為具有無窮位有效數(shù)字.e. 有效數(shù)字有效數(shù)字與相對(duì)誤差的關(guān)系與相對(duì)誤差的關(guān)系 有效數(shù)字有效數(shù)字 相對(duì)誤差限相對(duì)誤差限11121102102101001050* nnmnnmra.aaa.a.x*已知已知 x* 有有 n 位位有效數(shù)字有效數(shù)字，則其，則其相對(duì)誤差限相

13、對(duì)誤差限為為 相對(duì)誤差限相對(duì)誤差限 有效數(shù)字有效數(shù)字nmmnmnr.aaa.aaxxx 105010)1()1(210100)1(210|*|*|*|111121111110)1(21* nra已知已知 x* 的的相對(duì)誤差限相對(duì)誤差限可寫為可寫為則則可見可見 x* 至少至少有有 n 位位有效數(shù)字有效數(shù)字。3.數(shù)值算法設(shè)計(jì)要點(diǎn)數(shù)值算法設(shè)計(jì)要點(diǎn)算法設(shè)計(jì)的幾算法設(shè)計(jì)的幾點(diǎn)注意事項(xiàng)點(diǎn)注意事項(xiàng)1. 避免相近二數(shù)相減避免相近二數(shù)相減例：例：a1 = 0.12345，a2 = 0.12346，各有，各有5位有效數(shù)字。位有效數(shù)字。 而而 a2 a1 = 0.00001，只剩下，只剩下1位有效數(shù)字。位有效數(shù)字。

14、 幾種經(jīng)驗(yàn)性避免方法：幾種經(jīng)驗(yàn)性避免方法：;xxxx ;1lnlnln xxx當(dāng)當(dāng) | x | 1 時(shí)：時(shí)：;2sin2cos12xx .6121112xxxex2. 避免小分母避免小分母 : 分母小會(huì)造成舍入誤差增大分母小會(huì)造成舍入誤差增大3. 避免大數(shù)避免大數(shù)吃吃小數(shù)小數(shù)例：用單精度計(jì)算例：用單精度計(jì)算 的根。的根。010)110(992 xx精確解為精確解為110291 x,x x 3.81574 y 0.0001= 38157.4 x 3.81574 y+ y 0.0001+0.00001= 34688.5 算法算法1 1：利用求根公式利用求根公式aacbbx242 在計(jì)算機(jī)內(nèi)，在計(jì)算

15、機(jī)內(nèi)，109存為存為0.1 1010，1存為存為0.1 101。做加法時(shí)，做加法時(shí)，兩加數(shù)的指數(shù)先向大指數(shù)對(duì)齊，再將浮點(diǎn)部分相加。即兩加數(shù)的指數(shù)先向大指數(shù)對(duì)齊，再將浮點(diǎn)部分相加。即1 的指數(shù)部分須變?yōu)榈闹笖?shù)部分須變?yōu)?010，則：，則：1 = 0.0000000001 1010，取，取單精度時(shí)就成為：單精度時(shí)就成為： 109+1=0.10000000 1010+0.00000000 1010=0.10000000 1010024,102422921 aacbbxaacbbx大數(shù)大數(shù)吃吃小數(shù)小數(shù)算法算法2：先解出先解出 再利用再利用2914102bbacxa 11010991221 xacxac

16、xx求和時(shí)求和時(shí)從小到大從小到大相加，可使和的誤差減小。相加，可使和的誤差減小。例：按從小到大、以及從大到小的順序分別計(jì)算例：按從小到大、以及從大到小的順序分別計(jì)算1 + 2 + 3 + + 40 + 1094. 先化簡再計(jì)算，減少步驟，避免誤差積累。先化簡再計(jì)算，減少步驟，避免誤差積累。一般來說，計(jì)算機(jī)處理下列運(yùn)算的速度為一般來說，計(jì)算機(jī)處理下列運(yùn)算的速度為 exp ,例：多項(xiàng)式求值：給定例：多項(xiàng)式求值：給定x x, , 求求n n次多項(xiàng)式的值次多項(xiàng)式的值方法方法1 1：直接求和法；：直接求和法；方法方法2 2：利用前一次求冪的結(jié)果進(jìn)行計(jì)算；：利用前一次求冪的結(jié)果進(jìn)行計(jì)算；方法方法3 3：秦

17、九韶方法；：秦九韶方法；2012( )nna xaPaaxxx5. 選用穩(wěn)定的算法。選用穩(wěn)定的算法。.210110,n,dxexeIxnn 例：計(jì)算例：計(jì)算11.nnIn I公式一：公式一：111111000011dd1d .nxnxnxnxnx exx en xexxexeee 此公式成立此公式成立, 因?yàn)橐驗(yàn)?10011d1063212056 xIex.ee記為記為*0,I80000 5 10 .EII.則初始誤差則初始誤差 1101001111dd ,(1)1nnnnxexIxexIeee nn39141423151959424941412276480713163289600012103

18、0592000111088128000101.367879440111415*13*14*12*13*11*12*10*11*9*10*0*1.II.II.II.II.II.II.II ? ! !考察第考察第 n 步的誤差步的誤差nE| )1()1( |*11* nnnnnnInIIIE1nn|E|(unstable algorithm), 我們有責(zé)任改變。我們有責(zé)任改變。 這種算法是這種算法是不穩(wěn)定的算法不穩(wěn)定的算法 迅速積累迅速積累, ,可見初始的小擾動(dòng)可見初始的小擾動(dòng)801050| .E誤差遞增誤差遞增. .0!|nE2(1)nn nE11,(1)1NIe NN*111,2(1)1NNI

19、Ie NN可取可取當(dāng) N 時(shí)，*|0.NNNEII1111(1)nnnnIn IIIn 公式公式方法：先估計(jì)一個(gè)方法：先估計(jì)一個(gè)IN , ,再反推要求的再反推要求的 In ( n N )。 避免誤差積累的方法避免誤差積累的方法101nxnIx e dxe11010011dd ,nnnxexIxexee632120560)1(11367879440)1(210838771150)1(1110773517320)1(1210717792140)1(1310668702200)1(1410638169180)1(151042746233016116121*1*0*2*1*11*10*12*11*13