1、數(shù) 值 計 算 方 法陳研陳研 Tel:62732959 新學科綜合樓新學科綜合樓 4-201 中國農(nóng)業(yè)大學資源和環(huán)境學院中國農(nóng)業(yè)大學資源和環(huán)境學院 2005年年9月月現(xiàn)代科學研究的三大支柱理論研究科學實驗科學計算計算數(shù)學計算數(shù)學建立數(shù)學模型選取計算方法編寫上機程序計算得出結(jié)果一、一、計算數(shù)學的產(chǎn)生和早期發(fā)展計算數(shù)學的產(chǎn)生和早期發(fā)展計算數(shù)學是數(shù)學的一個古老的分支，雖然數(shù)學不僅僅計算數(shù)學是數(shù)學的一個古老的分支，雖然數(shù)學不僅僅是計算，但推動數(shù)學產(chǎn)生和發(fā)展的最直接原因還是是計算，但推動數(shù)學產(chǎn)生和發(fā)展的最直接原因還是。 二、二十世紀計算數(shù)學的發(fā)展二十世紀計算數(shù)學的發(fā)展數(shù)值代數(shù)數(shù)值代數(shù) 最優(yōu)化計算最優(yōu)化

2、計算 數(shù)值逼近數(shù)值逼近 計算幾何計算幾何 概率統(tǒng)計計算概率統(tǒng)計計算 蒙特卡羅方法蒙特卡羅方法 微分方程的數(shù)值解法微分方程的數(shù)值解法 微分方程的反演問題微分方程的反演問題 數(shù)值計算的主要內(nèi)容數(shù)值計算的主要內(nèi)容數(shù)值代數(shù)：方程求根、線性方程組求解、數(shù)值代數(shù)：方程求根、線性方程組求解、 特征值和特征向量的計算、特征值和特征向量的計算、 非線性方程組的求解；非線性方程組的求解；數(shù)值逼近：插值、數(shù)值微分和積分、數(shù)值逼近：插值、數(shù)值微分和積分、 最小二乘法；最小二乘法；微分方程數(shù)值解：微分方程數(shù)值解： 常微分方程數(shù)值解；常微分方程數(shù)值解； 偏微分方程數(shù)值解：偏微分方程數(shù)值解： 差分法差分法 有限元法有限元法

3、 有限體積法有限體積法&教材教材 數(shù)值計算方法數(shù)值計算方法 徐濤徐濤 編著編著 （吉林科學技術(shù)出版社）（吉林科學技術(shù)出版社）& 參考書目參考書目 應用應用數(shù)值方法數(shù)值方法 使用使用MATLAB和和C語言語言 Robert J.Schilling & Sandra L.Harris （機械工業(yè)出版社）（機械工業(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ù)學語言加以敘述，也可以借助形式語言（算法語言）和數(shù)學語言加以敘述，也可以借助形式語言（算法語言）給出精確的說明，也可以用框圖直觀地顯示算法的全貌。給出精確的說明，也可以用框圖直觀地顯示算法的全貌。 定義：由基本運算及運算順序的規(guī)定所構(gòu)成的完整的定義：由基本運算及運算順序的規(guī)定所構(gòu)成的完整的 解題步驟，稱為解題步驟，稱為。 例例1：一群小兔一群雞，兩群合到一群里，要數(shù)腿共：一群小兔一群雞

5、，兩群合到一群里，要數(shù)腿共48，要數(shù)腦袋整要數(shù)腦袋整17，多少小兔多少雞？，多少小兔多少雞？算術(shù)方法算術(shù)方法 ：若沒有小兔，則雞應是若沒有小兔，則雞應是17只只總腿數(shù)總腿數(shù) ：21734一只小兔增加一只小兔增加 2條腿，條腿，應該有應該有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)立方程組2222121121

6、2111bxaxabxaxa用行列式解法：首先判別用行列式解法：首先判別12212211aaaaD （1）如果如果 ，則令計算機計算，則令計算機計算 0D , 1222211DababxDababx2111122輸出計算的結(jié)果輸出計算的結(jié)果x1，x2。（2）如果如果D D= = 0 0，則或是無解，或有無窮多組解。，則或是無解，或有無窮多組解。是否為零，存在兩種可能：是否為零，存在兩種可能：12212211Daaaa令令通過求解過程，可以總結(jié)出算法步驟如下：通過求解過程，可以總結(jié)出算法步驟如下：S2 計算計算12212211DaaaaS3 如果如果0D 則輸出原方程無解或有無窮多組解的信息則輸

7、出原方程無解或有無窮多組解的信息;否則否則0D D1212112babax D2121221babaxS1 輸入輸入2122211211,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階方程組，要計算階方

8、程組，要計算n + 1個個n n階行列式的值，階行列式的值， 總共需要做總共需要做n! (n - 1) (n + 1) 次乘法運算。次乘法運算。 n=20 需要運需要運算多少次？算多少次？n=100?一、一、 誤差的背景介紹誤差的背景介紹1. 來源與分類來源與分類 從實際問題中抽象出數(shù)學模型從實際問題中抽象出數(shù)學模型 模型誤差模型誤差例例1:1:質(zhì)量為質(zhì)量為m的物體，在重力作用下，自由下落，的物體，在重力作用下，自由下落， 其下落距離其下落距離s 與時間與時間t 的關(guān)系是：的關(guān)系是： mgdtsdm22（1.1）其中其中 g 為重力加速度。為重力加速度。 通過測量得到模型中參數(shù)的值通過測量得到

9、模型中參數(shù)的值 觀測誤差觀測誤差 求近似解求近似解 方法誤差方法誤差 (截斷誤差）截斷誤差）機器字長有限機器字長有限 舍入誤差舍入誤差 用計算機、計算器和筆算，都只能用有限位小數(shù)用計算機、計算器和筆算，都只能用有限位小數(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ù)值計算方法中，主要研究和和（包

10、括初始數(shù)據(jù)的誤差）對計算結(jié)果的影響?。òǔ跏紨?shù)據(jù)的誤差）對計算結(jié)果的影響！二、絕對誤差、相對誤差和有效數(shù)字二、絕對誤差、相對誤差和有效數(shù)字1 1絕對誤差與絕對誤差限絕對誤差與絕對誤差限例例 2: :若用以厘米為最小刻度的尺去量桌子的長，若用以厘米為最小刻度的尺去量桌子的長， 大約為大約為1.45米，求米，求1.45米的絕對誤差。米的絕對誤差。1.45米的米的絕對誤差絕對誤差= =？不知道！不知道！定義定義1：設(shè)：設(shè)x是準確值是準確值，x*為為x的一個近似值的一個近似值，稱，稱 *)(xxxe是近似值是近似值x的的, ,簡稱為簡稱為。 （1.5）但實際問題往往可以估計出但實際問題往往可以估計出

11、 不超過某個正數(shù)不超過某個正數(shù) ，即，即， ，則稱，則稱 為絕對誤差限，有了絕對誤差限為絕對誤差限，有了絕對誤差限就可以知道就可以知道x范圍為范圍為)(xe*xx*xxx*xx,*xx即即x落在落在 內(nèi)。在應用上，常常采用下列內(nèi)。在應用上，常常采用下列寫法來刻劃寫法來刻劃x*的精度。的精度。2相對誤差和相對誤差限相對誤差和相對誤差限xxxxe*（1.6）定義定義2：設(shè)設(shè)x是準確值，是準確值，x*是近似值，稱是近似值，稱rxxx*滿足滿足為近似值為近似值x的的，相應地，若正數(shù)，相應地，若正數(shù) ，r 則稱則稱 為為x的的。r3有效數(shù)字有效數(shù)字410211416. 35102114159. 3則說則

12、說x*近似表示近似表示x準確到小數(shù)后第準確到小數(shù)后第n位，并從這第位，并從這第n位起位起直到最左邊的非零數(shù)字之間的一切數(shù)字都稱為直到最左邊的非零數(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：蝴蝶效應蝴蝶效應 紐約的一只蝴蝶翅膀一拍，風和日麗的北紐約的一只蝴蝶翅膀一拍，風和日麗的北京就刮起臺風

13、來了？！京就刮起臺風來了？！NYBJ以上是一個病態(tài)問題以上是一個病態(tài)問題 1要使用數(shù)值穩(wěn)定的算法要使用數(shù)值穩(wěn)定的算法例例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. 054134IIW

14、hat happened?!025. 155145II952. 456156II不穩(wěn)定的算法不穩(wěn)定的算法 ！由遞推公式由遞推公式（1.8）可看出，可看出，In-1的誤差擴大了的誤差擴大了5倍后傳給倍后傳給In，因而初值因而初值I0的誤差對以后各步計算結(jié)果的影響，隨著的誤差對以后各步計算結(jié)果的影響，隨著n的增大的增大愈來愈嚴重。這就造成愈來愈嚴重。這就造成I4的計算結(jié)果嚴重失真。的計算結(jié)果嚴重失真。改變公式：改變公式：nIInn151將公式將公式變?yōu)樽優(yōu)椴环猎O(shè)不妨設(shè)I9 I10，于是由于是由10951501II可求得可求得I9 0.017，按公式按公式（1.9）可逐次求得可逐次求得) 1 , 1

15、,( 51511nnKIKIKk（1.9）I8 0.019 I7 0.021I6 0.024 I8 0.028I4 0.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）的值。的值。當當x = 1000，y 的準確值為的準確值為0.0158

16、0 1、直接相減直接相減02. 062.3164.3110001001y2、將將（1.10）改寫為改寫為xxxxy111則則 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精確解為精確解為11

17、0291 x,x 算法算法1 1：利用求根公式：利用求根公式aacbbx242在計算機內(nèi)，在計算機內(nèi)，109存為存為0.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：先解出：先解出9

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