第1章計算方法的一般概念

1、計算方法計算方法數(shù)值計算方法能做什么？n研究使用計算機求解各種科學與工程計研究使用計算機求解各種科學與工程計算問題的數(shù)值方法（近似方法），對求算問題的數(shù)值方法（近似方法），對求得的解的精度進行評估，以及如何在計得的解的精度進行評估，以及如何在計算機上實現(xiàn)求解等。算機上實現(xiàn)求解等。n數(shù)值計算課程中所講述的各種數(shù)值方法數(shù)值計算課程中所講述的各種數(shù)值方法在科學與工程計算、信息科學、管理科在科學與工程計算、信息科學、管理科學、生命科學等交叉學科中有著廣泛的學、生命科學等交叉學科中有著廣泛的應用應用應用問題舉例應用問題舉例323023342326xyzxyzxyz1 1、一個兩千年前的例子、一個兩千年前

2、的例子今有上禾三秉，中禾二秉，下禾一秉，實三十斗；今有上禾三秉，中禾二秉，下禾一秉，實三十斗； 上禾二秉，中禾三秉，下禾一秉，實三十四上禾二秉，中禾三秉，下禾一秉，實三十四斗；斗； 上禾一秉，中禾二秉，下禾三秉，實二十六上禾一秉，中禾二秉，下禾三秉，實二十六斗。斗。問上、中、下禾實一秉各幾何？問上、中、下禾實一秉各幾何？答曰：上禾一秉九斗四分斗之一。中禾一秉四斗答曰：上禾一秉九斗四分斗之一。中禾一秉四斗四分斗之一。下禾一秉二斗四分斗之三。四分斗之一。下禾一秉二斗四分斗之三。-九章算術(shù)九章算術(shù)nnnnnnaaaaaaaaa212222111211bxAnnbbbxxx2121本課程第二章的內(nèi)容：

3、本課程第二章的內(nèi)容： 線性方程組的數(shù)值方法！線性方程組的數(shù)值方法！2、已經(jīng)測得在某處海洋不同深度處的水溫如下：深度（M） 466 741 950 1422 1634水溫（oC）7.04 4.28 3.40 2.54 2.13根據(jù)這些數(shù)據(jù)，希望合理地估計出其它深度（如500米，600米，1000米）處的水溫本課程第三章的內(nèi)容：插值法用比較簡單的函數(shù)代替復雜的函數(shù)誤差為最小，即距離為最?。ㄔ诓煌亩攘恳饬x下）本課程第四章的內(nèi)容：函數(shù)最優(yōu)逼近法3、人口預測 下面給出的是中國1900年到2000年的人口數(shù)，我們的目標是預測未來的人口數(shù)（數(shù)據(jù)量較大時）19505519619606620719708299

4、219809870519901143332000126743432231ttty30/ )1979( ts432231sssy4、鋁制波紋瓦的長度問題、鋁制波紋瓦的長度問題 建筑上用的一種鋁制波紋瓦是用一種機建筑上用的一種鋁制波紋瓦是用一種機器將一塊平整的鋁板壓制而成的器將一塊平整的鋁板壓制而成的.假若要求波紋瓦長假若要求波紋瓦長4 4英尺英尺, ,每個波紋的高度每個波紋的高度( (從從中心線中心線) )為為1 1英寸英寸, ,且每個波紋以近似且每個波紋以近似22英寸英寸為一個周期為一個周期. . 求制做一塊波紋瓦所需鋁板的求制做一塊波紋瓦所需鋁板的長度長度L.L. 這個問題就是要求由函數(shù)這個

5、問題就是要求由函數(shù)dxxdxxfL48024802)(cos1)(1上述積分稱為第二類橢圓積分上述積分稱為第二類橢圓積分, ,它不能用普它不能用普通方法來計算通方法來計算.本課程第五章的內(nèi)容：數(shù)值微積分5、天體力學中的Kepler方程x是行星運動的軌道，它是時間t 的函數(shù)sin0,01xxt 本課程第六章的內(nèi)容： 非線性方程的數(shù)值解法全球定位系統(tǒng)：在地球的任何一個位置，至少可以同時收到4顆以上衛(wèi)星發(fā)射的信號 6、全球定位系統(tǒng)（Global Positioning System, GPS)02468051002468圖 7.8HeightS6S3S4S2S1RS5N-S positions 表示

6、地球上一個接收點R的當前位置，衛(wèi)星Si的位置為 ，則得到下列非線性方程組( , , , )x y z t(, )iiiix y z t222111122222222223333222444422255552226666()()()(t -t)0()()()(t -t)0()()()(t -t)0()()()(t -t)0()()()(t -t)0()()()(t -t)xxyyzzcxxyyzzcxxyyzzcxxyyzzcxxyyzzcxxyyzz0c本課程第六章的內(nèi)容： 非線性方程組的數(shù)值方法非線性方程組的數(shù)值方法11221212( ,)0( ,)0( ,)0nnnnf x xxfx xx

7、fx xx( )0F x 記為記為其中其中:,nnF DRR12( ,)Tnxx xxxxGT1exTG: Google Matrix, “the worlds largest matrix computation”. 4,300,000,000 x: PageRank vector “The $25,000,000,000 Eigenvector”7 7、GoogleGoogle搜索引擎搜索引擎London, England: Millennium (Wobbly) Bridge (1998-2002, Norman Foster and Partners and Arup Associat

8、es) the natural modes and frequencies of a structure are the solution of an eigenvalue problem that is quadratic when damping effects are included in the model. (F. Tisseur, K. Meerbergen, The quadratic Eigenvalue Problem, SiREV 43, 2000, pp.235-286)Axx本課程第七章的內(nèi)容： 矩陣特征值問題的數(shù)值方法8、生物化學反應的例子 A，B，C是三種蛋白質(zhì)，

9、其反應如下：123aaaABBBCBBCAC 我們通過建?？梢缘玫饺缦路匠探M 111323ya ya y y 1(0)1y221132322ya ya y ya y2(0)0y3y 222a y3(0)0y A： B：C： 本課程第八章的內(nèi)容： 常微分方程的數(shù)值解法用計算機解決實際問題的步驟用計算機解決實際問題的步驟 建立數(shù)學模型建立數(shù)學模型 選擇數(shù)值方法選擇數(shù)值方法 編寫程序編寫程序 上機計算結(jié)果上機計算結(jié)果數(shù)值計算方法的主要任務數(shù)值計算方法的主要任務： 數(shù)值求解各類數(shù)值問題，并提出最有效的算法。（包括誤差分析，算法的穩(wěn)定性及收斂性）第1章 計算方法的一般概念n算法n誤差1.1 算法n由基本

10、運算（算術(shù)運算及一些邏輯運算）及運算順序的規(guī)定構(gòu)成的完整的解題步驟。 例如：357212121sin( 1) 1,13!5!7!(21)!( )( )nnnnxxxxxxxnPxRx 232123( )sin()(23)!2nnxnRxn225sin( )(1(0.16666670.0083333)xP xxxx3572121sin( )( 1)3!5!7!(21)!nnnxxxxxPxxn 355sin()6120 xxxPxx運算量：運算量：8次乘除，次乘除，2次加減次加減.5|( ) |0.001957Rx運算量：運算量：4次乘法，次乘法，2次減法次減法縮減冪級數(shù)法（第四章）：*225s

11、in( )()xPxx axbcx0.9999789,0.1664972,0.0079923abc其中，運算量：運算量：4次乘法，次乘法，2次減法次減法.誤差|R|121,212140 ,4,2sg n ()4,2-a ca xb xcba cxabba ccxxaa x 222又 如 b，解不 宜 采 用 公 式bb最 好 采 用 ，2211lnln;arctan(1)arctan11ln,arctan11(1)yxxzxxxxxyzxx x最好采用公式例：解方程010)110(992xx解:9110 x12xaacbsqrtbx2)4(22,1而如果在字長為8,基底為10的計算機上利用求根

12、公式1109b10101 . 010100100000000. 0機器吃了因此在計算機上10101 . 0b101000000000. 010101 . 0910aacbsqrtbx2)4(21)4(2acbsqrt92101014)101 . 0(910 aacbsqrtbx2)4(22可得利用根的關(guān)系acxx219991021010021010991x若已算出121xacx110111099上式是解二次方程的數(shù)值公式幾個簡單的估計公式幾個簡單的估計公式1212121212211212112222,()()()xxxxxxxxx xxxxxxxxxxxx 的 近 似 值設1.2.4機器數(shù)與舍

13、入誤差機器數(shù)與舍入誤差 在計算機中，一般實數(shù)x均按舍入原則表示成: (b進制浮點數(shù))其中b稱為基數(shù)，m為階碼， 為尾數(shù)或數(shù)碼 時fl(x)稱為規(guī)格化的浮點數(shù)，t為計算機的位數(shù).一定型號的計算機，t是固定的，L=m=U.12( )(0.)mtfl xxbx xx 1 20.tx xx10 x 避免大數(shù)吃掉小數(shù)(0.1999)(0.8190)(0.1999)(0.000008190)(0.19990819)(0.1999)4-14444101010101010例如：在4位的10進制的計算機上31.97+2.456+0.1352（=34.5612） (2)(31.97+2.456)+0.1352=3

14、4.43+0.1352=34.57 (3)31.97+(2.456+0.1352)=31.97+2.591=34.56 (4)一般來說，若干數(shù)相加最好先加絕對值較小的數(shù)！簡化計算步驟，盡量減少運算次數(shù)簡化計算步驟，盡量減少運算次數(shù)12864321684222222222215次乘法運算而不是255次！2562例如：10001000111111()1(1)11001nnn nnn又如：例如，計算多項式例如，計算多項式 通常運算的乘法次數(shù)為通常運算的乘法次數(shù)為 1011( )nnnnnpxa xa xaxa2)1(.21 nnn0011,2,( ) ()kkknbabbxaknp xb0121(

15、)()nnp xa xa xa xaxa采用秦九韶算法：采用秦九韶算法：n次乘法，次乘法，n加法！加法！), 2 , 1(101ndxexExnn解解 由分部積分可得1011101dxexnexExnxnn因此有遞推公式), 3 , 2(11nnEEnneE111.2.5算法的穩(wěn)定性算法的穩(wěn)定性例如：計算積分表表 1-1Ek 0.367879 0.264242 0.207274 0.170904 0.145480 0.127120 0.110160 0.118720 -0.068480k用上面的遞推公式，在字長為6，基底為10的計算機上，從 E1出發(fā)計算前幾個積分值，其結(jié)果如上表表1-1。 被

16、積函數(shù) 在積分限（0,1）區(qū)間內(nèi)都是正值，積分值 E9 取三位有效數(shù)字的精確結(jié)果為0.0916，但上表中E9 = - 0.068480卻是負值，與0.0916相差很大。怎么會出現(xiàn)這種現(xiàn)象？可分析如下。 由于在計算時有舍入誤差約為1xnex710412. 4且考慮以后的計算都不再另有舍入誤差。此對后面各項計算的影響為! 221)(21112EEE! 2211E53! 2213113EE! 321311E ! 321314114EE! 42131411E! 981919E這樣，算到 E9 時產(chǎn)生的誤差為6101. 010412. 4! 9! 97這就是一個不小的數(shù)值了。 可以改進算法來提高此例的數(shù)

17、值穩(wěn)定性，即將遞推公式改寫為nEEnn11從后向前遞推計算時，En 的誤差下降為原來的1/n，因此只要 n 取得足夠大，誤差逐次下降，其影響就會越來越小。由 可知： 當 時 。因此可取E20作為初始值進行遞推計算。 由于 ，故E20 =0 的誤差約為1/21。在計算 時誤差下降到到計算E15時誤差已下降到 ，結(jié)果如表表1-2。1010111ndxxdxexEnxnnn0nE21120E0024. 02012118104200.0000000190.0500000180.0500000170.0527778160.0557190150.0669477140.0627322130.06694771

18、20.0717733110.0773523100.083877190.0916123kkE表表 1-4,.2 , 11|555,.)1 , 0(5例1.3.310101101110nnnxdxxdxxxxIIndxxxInnnnnnnn解：由于計算定積分計算如下：得遞推公式18232155. 056ln,.2 , 15101InInInnn InnIn0 0.1823215590.0170566241 0.088392216100.0147168762 0.058039818110.0173247103 0.04313874212-0.0032902194 0.03430628713-0.0933741725 0.02846856014-0.3954422906 0.024323864152.0438781007 0.02123782016-10.156890008 0.0188108971750.84327600錯。的絕對值越大，顯然出越大，且時從表中看到，當。且即，所以由于nnnnnnInInIIdxxxxxx0120lim, 10150) 1 , 0(1501041)5(.)(5,.2