數(shù)值分析(計算方法)第一章

1、數(shù) 值 分析中國計量學(xué)院理學(xué)院中國計量學(xué)院理學(xué)院現(xiàn)代科學(xué)研究的三大支柱理論研究科學(xué)實驗科學(xué)計算計算數(shù)學(xué)計算數(shù)學(xué)建立數(shù)學(xué)模型選取計算方法編寫上機(jī)程序計算得出結(jié)果一、一、計算數(shù)學(xué)的產(chǎn)生和早期發(fā)展計算數(shù)學(xué)的產(chǎn)生和早期發(fā)展計算數(shù)學(xué)是數(shù)學(xué)的一個古老的分支，雖然數(shù)學(xué)不僅僅計算數(shù)學(xué)是數(shù)學(xué)的一個古老的分支，雖然數(shù)學(xué)不僅僅是計算，但推動數(shù)學(xué)產(chǎn)生和發(fā)展的最直接原因還是是計算，但推動數(shù)學(xué)產(chǎn)生和發(fā)展的最直接原因還是。 二、二十世紀(jì)計算數(shù)學(xué)的發(fā)展二十世紀(jì)計算數(shù)學(xué)的發(fā)展數(shù)值代數(shù)數(shù)值代數(shù) 最優(yōu)化計算最優(yōu)化計算 數(shù)值逼近數(shù)值逼近 計算幾何計算幾何 概率統(tǒng)計計算概率統(tǒng)計計算 蒙特卡羅方法蒙特卡羅方法 微分方程的數(shù)值解法微分方程

2、的數(shù)值解法 微分方程的反演問題微分方程的反演問題 數(shù)值計算的主要內(nèi)容數(shù)值計算的主要內(nèi)容數(shù)值代數(shù)：方程求根、線性方程組求解、數(shù)值代數(shù)：方程求根、線性方程組求解、 特征值和特征向量的計算、特征值和特征向量的計算、 非線性方程組的求解；非線性方程組的求解；數(shù)值逼近：插值、數(shù)值微分和積分、數(shù)值逼近：插值、數(shù)值微分和積分、 最小二乘法；最小二乘法；微分方程數(shù)值解：微分方程數(shù)值解： 常微分方程數(shù)值解；常微分方程數(shù)值解； 偏微分方程數(shù)值解：偏微分方程數(shù)值解： 差分法差分法 有限元法有限元法 有限體積法有限體積法&教材教材 數(shù)值計算方法數(shù)值計算方法 徐濤徐濤 編著編著 （吉林科學(xué)技術(shù)出版社）（吉林科學(xué)

3、技術(shù)出版社）& 參考書目參考書目 應(yīng)用應(yīng)用數(shù)值方法數(shù)值方法 使用使用MATLAB和和C語言語言 Robert J.Schilling & Sandra L.Harris （機(jī)械工業(yè)出版社）（機(jī)械工業(yè)出版社） Numerical Recipes in C+ The Art of Scientific Computing Second Edition William H.Press 等著等著 （電子工業(yè)出版社）（電子工業(yè)出版社） 現(xiàn)代數(shù)值分析現(xiàn)代數(shù)值分析 李慶揚、易大義、王能超李慶揚、易大義、王能超 編著編著 （高等教育出版社）（高等教育出版社） 一、算法的概念一、算法的概念 描述

4、算法可以有不同的方式。例如，可以用日常語言描述算法可以有不同的方式。例如，可以用日常語言和數(shù)學(xué)語言加以敘述，也可以借助形式語言（算法語言）和數(shù)學(xué)語言加以敘述，也可以借助形式語言（算法語言）給出精確的說明，也可以用框圖直觀地顯示算法的全貌。給出精確的說明，也可以用框圖直觀地顯示算法的全貌。 定義：由基本運算及運算順序的規(guī)定所構(gòu)成的完整的定義：由基本運算及運算順序的規(guī)定所構(gòu)成的完整的 解題步驟，稱為解題步驟，稱為。 例例1：一群小兔一群雞，兩群合到一群里，要數(shù)腿共：一群小兔一群雞，兩群合到一群里，要數(shù)腿共48，要數(shù)腦袋整要數(shù)腦袋整17，多少小兔多少雞？，多少小兔多少雞？算術(shù)方法算術(shù)方法 ：若沒有小

5、兔，則雞應(yīng)是若沒有小兔，則雞應(yīng)是17只只總腿數(shù)總腿數(shù) ：21734一只小兔增加一只小兔增加 2條腿，條腿，應(yīng)該有應(yīng)該有7221748只小兔只小兔1010只小雞只小雞代數(shù)方法代數(shù)方法 ：設(shè)有設(shè)有x只小雞，只小雞，y只小兔只小兔 ，(ii) 4842(i) 17 ) I (yxyx(-2)*(i) +(ii) , 得得217-48)24( 17 )II(yyx72421748y只小兔只小兔高斯消高斯消去法去法例：求解二元一次聯(lián)立方程組例：求解二元一次聯(lián)立方程組22221211212111bxaxabxaxa用行列式解法：首先判別用行列式解法：首先判別12212211aaaaD （1）如果如果 ，則

6、令計算機(jī)計算，則令計算機(jī)計算 0D , 1222211DababxDababx2111122輸出計算的結(jié)果輸出計算的結(jié)果x1，x2。（2）如果如果D D= = 0 0，則或是無解，或有無窮多組解。，則或是無解，或有無窮多組解。是否為零，存在兩種可能：是否為零，存在兩種可能：12212211Daaaa令令通過求解過程，可以總結(jié)出算法步驟如下：通過求解過程，可以總結(jié)出算法步驟如下：S2 計算計算12212211DaaaaS3 如果如果0D 則輸出原方程無解或有無窮多組解的信息則輸出原方程無解或有無窮多組解的信息;否則否則0D D1212112babax D2121221babaxS1 輸入輸入21

7、22211211,bbaaaaS4 輸出計算的結(jié)果輸出計算的結(jié)果21,xx輸入輸入2122211211,bbaaaa D=a11a22-a12a21D=0開始開始DababxDababx/ )(/ )(21111221222211輸出輸出 x1, x2 結(jié)結(jié) 束束 No輸出無解信息輸出無解信息Yes二、算法的優(yōu)劣二、算法的優(yōu)劣 計算量小計算量小 存貯量少存貯量少 邏輯結(jié)構(gòu)簡單邏輯結(jié)構(gòu)簡單例：用行列式解法求解線性方程組例：用行列式解法求解線性方程組: : n階方程組，要計算階方程組，要計算n + 1個個n n階行列式的值，階行列式的值， 總共需要做總共需要做n! (n - 1) (n + 1)

8、次乘法運算。次乘法運算。 n=20 需要運需要運算多少次？算多少次？n=100?一、一、 誤差的背景介紹誤差的背景介紹1. 來源與分類來源與分類 從實際問題中抽象出數(shù)學(xué)模型從實際問題中抽象出數(shù)學(xué)模型 模型誤差模型誤差例例1:1:質(zhì)量為質(zhì)量為m的物體，在重力作用下，自由下落，的物體，在重力作用下，自由下落， 其下落距離其下落距離s 與時間與時間t 的關(guān)系是：的關(guān)系是： mgdtsdm22（1.1）其中其中 g 為重力加速度。為重力加速度。 通過測量得到模型中參數(shù)的值通過測量得到模型中參數(shù)的值 觀測誤差觀測誤差 求近似解求近似解 方法誤差方法誤差 (截斷誤差）截斷誤差）機(jī)器字長有限機(jī)器字長有限 舍

9、入誤差舍入誤差 用計算機(jī)、計算器和筆算，都只能用有限位小數(shù)用計算機(jī)、計算器和筆算，都只能用有限位小數(shù)來代替無窮小數(shù)或用位數(shù)較少的小數(shù)來代替位數(shù)較多來代替無窮小數(shù)或用位數(shù)較少的小數(shù)來代替位數(shù)較多的有限小數(shù)，如：的有限小數(shù)，如： = 3.1415926 3333. 031x = 8.12345四舍五入后四舍五入后0000074. 01416. 31000033. 0333. 0312000044. 01235. 83 x在數(shù)值計算方法中，主要研究在數(shù)值計算方法中，主要研究和和（包括初始數(shù)據(jù)的誤差）對計算結(jié)果的影響?。òǔ跏紨?shù)據(jù)的誤差）對計算結(jié)果的影響！二、絕對誤差、相對誤差和有效數(shù)字二、絕對誤差

10、、相對誤差和有效數(shù)字1 1絕對誤差與絕對誤差限絕對誤差與絕對誤差限例例 2: :若用以厘米為最小刻度的尺去量桌子的長，若用以厘米為最小刻度的尺去量桌子的長， 大約為大約為1.45米，求米，求1.45米的絕對誤差。米的絕對誤差。1.45米的米的絕對誤差絕對誤差= =？不知道！不知道！定義定義1：設(shè)：設(shè)x是準(zhǔn)確值是準(zhǔn)確值，x*為為x的一個近似值的一個近似值，稱，稱 *)(xxxe是近似值是近似值x的的, ,簡稱為簡稱為。 （1.5）但實際問題往往可以估計出但實際問題往往可以估計出 不超過某個正數(shù)不超過某個正數(shù) ，即，即， ，則稱，則稱 為絕對誤差限，有了絕對誤差限為絕對誤差限，有了絕對誤差限就可以

11、知道就可以知道x范圍為范圍為)(xe*xx*xxx*xx,*xx即即x落在落在 內(nèi)。在應(yīng)用上，常常采用下列內(nèi)。在應(yīng)用上，常常采用下列寫法來刻劃寫法來刻劃x*的精度。的精度。2相對誤差和相對誤差限相對誤差和相對誤差限xxxxe*（1.6）定義定義2：設(shè)設(shè)x是準(zhǔn)確值，是準(zhǔn)確值，x*是近似值，稱是近似值，稱rxxx*滿足滿足為近似值為近似值x的的，相應(yīng)地，若正數(shù)，相應(yīng)地，若正數(shù) ，r 則稱則稱 為為x的的。r3有效數(shù)字有效數(shù)字410211416. 35102114159. 3則說則說x*近似表示近似表示x準(zhǔn)確到小數(shù)后第準(zhǔn)確到小數(shù)后第n位，并從這第位，并從這第n位起位起直到最左邊的非零數(shù)字之間的一切數(shù)

12、字都稱為直到最左邊的非零數(shù)字之間的一切數(shù)字都稱為，并把有效數(shù)字的位數(shù)稱為并把有效數(shù)字的位數(shù)稱為。定義定義3：如果如果nxx1021*（1.7）由上述定義由上述定義0015926. 014. 3有效數(shù)位為有效數(shù)位為3位位0000074. 01416. 3有效數(shù)位為有效數(shù)位為5位位0000926. 01415. 3有效數(shù)位為有效數(shù)位為4位位誤差的傳播與積累誤差的傳播與積累例例3：蝴蝶效應(yīng)蝴蝶效應(yīng) 紐約的一只蝴蝶翅膀一拍，風(fēng)和日麗的北紐約的一只蝴蝶翅膀一拍，風(fēng)和日麗的北京就刮起臺風(fēng)來了？！京就刮起臺風(fēng)來了？！NYBJ以上是一個病態(tài)問題以上是一個病態(tài)問題 1要使用數(shù)值穩(wěn)定的算法要使用數(shù)值穩(wěn)定的算法例例

13、4：求：求 （n = 0, 1, 2, , 8）的值。的值。10dx5xxInn解：由于解：由于nxxxxIInnnnn1dxdn5551011011初值初值)2 . 1ln(5ln6lndx51100 xI遞推公式遞推公式)8, 2, 1(,51)2 . 1ln(10nInIInn（1.8）注意此公式注意此公式精確精確成成立立按按 (1.8) 式就可以逐步算出式就可以逐步算出09. 05101II05. 052112II083. 053123II165. 054134IIWhat happened?!025. 155145II952. 456156II不穩(wěn)定的算法不穩(wěn)定的算法 ！由遞推公式由

14、遞推公式（1.8）可看出，可看出，In-1的誤差擴(kuò)大了的誤差擴(kuò)大了5倍后傳給倍后傳給In，因而初值因而初值I0的誤差對以后各步計算結(jié)果的影響，隨著的誤差對以后各步計算結(jié)果的影響，隨著n的增大的增大愈來愈嚴(yán)重。這就造成愈來愈嚴(yán)重。這就造成I4的計算結(jié)果嚴(yán)重失真。的計算結(jié)果嚴(yán)重失真。改變公式：改變公式：nIInn151將公式將公式變?yōu)樽優(yōu)椴环猎O(shè)不妨設(shè)I9 I10，于是由于是由10951501II可求得可求得I9 0.017，按公式按公式（1.9）可逐次求得可逐次求得) 1 , 1,( 51511nnKIKIKk（1.9）I8 0.019 I7 0.021I6 0.024 I8 0.028I4 0.

15、034 I3 0.043I2 0.058 I1 0.088I0 0.182 穩(wěn)定的算法穩(wěn)定的算法 ！ 在我們今后的討論中，在我們今后的討論中，誤差誤差將不可回避，將不可回避， 算法的算法的穩(wěn)定性穩(wěn)定性會是一個非常重要的話題。會是一個非常重要的話題。2要避免兩個相似數(shù)相減要避免兩個相似數(shù)相減在數(shù)值計算中，兩個相近的數(shù)作減法時有效數(shù)字會損失。在數(shù)值計算中，兩個相近的數(shù)作減法時有效數(shù)字會損失。xxy1（1.10）的值。的值。當(dāng)當(dāng)x = 1000，y 的準(zhǔn)確值為的準(zhǔn)確值為0.01580 1、直接相減直接相減02. 062.3164.3110001001y2、將將（1.10）改寫為改寫為xxxxy111

16、則則 y = 0.01581 例例5: 求求類似地類似地 yxyxlnlnln2sin2cos2sin)sin(xxx2. 絕對值太小的數(shù)不宜作除數(shù)絕對值太小的數(shù)不宜作除數(shù)2 .2718001. 07182. 21 .24710011. 07182. 2例例6：如分母變?yōu)槿绶帜缸優(yōu)?.0011，也即分母只有，也即分母只有0.0001的變化時的變化時3. 避免大數(shù)避免大數(shù)吃吃小數(shù)小數(shù)例例7：用單精度計算：用單精度計算 的根。的根。010)110(992 xx精確解為精確解為110291 x,x 算法算法1 1：利用求根公式：利用求根公式aacbbx242在計算機(jī)內(nèi)，在計算機(jī)內(nèi)，109存為存為0.

17、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=0.10000000 1010024,102422921aacbbxaacbbx算法算法2：先解出：先解出9211024)( aacbbsignbx11010991221 xacxacxx求和時從小到大相加，可使和的誤差減小。求

18、和時從小到大相加，可使和的誤差減小。例例8：按從小到大、以及從大到小的順序分別計算：按從小到大、以及從大到小的順序分別計算4. 先化簡再計算，減少步驟，避免誤差積累。先化簡再計算，減少步驟，避免誤差積累。一般來說，計算機(jī)處理下列運算的速度為一般來說，計算機(jī)處理下列運算的速度為 exp ,1 + 2 + 3 + + 40 + 109再利用再利用5.算法的算法的遞推性遞推性 計算機(jī)上使用的算法常采用遞推化的形式，遞推計算機(jī)上使用的算法常采用遞推化的形式，遞推化的基本思想是把一個復(fù)雜的計算過程歸結(jié)為簡單過程化的基本思想是把一個復(fù)雜的計算過程歸結(jié)為簡單過程的多次重復(fù)。這種重復(fù)在程序上表現(xiàn)為循環(huán)。遞推化的的多次重復(fù)。這種重復(fù)在程序上表現(xiàn)為循環(huán)。遞推化的優(yōu)點是簡化結(jié)構(gòu)和節(jié)省計算量優(yōu)點是簡化結(jié)構(gòu)和節(jié)省計算量。多項式求值：多項式求值：給定的給定的x 求下列求下列n 次多項多的值次多項多的值。 nnxaxaxaaxP2210)(解：解：1. . 用