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

1、计算方法计算方法数值计算方法能做什么？n研究使用计算机求解各种科学与工程计研究使用计算机求解各种科学与工程计算问题的数值方法（近似方法），对求算问题的数值方法（近似方法），对求得的解的精度进行评估，以及如何在计得的解的精度进行评估，以及如何在计算机上实现求解等。算机上实现求解等。n数值计算课程中所讲述的各种数值方法数值计算课程中所讲述的各种数值方法在科学与工程计算、信息科学、管理科在科学与工程计算、信息科学、管理科学、生命科学等交叉学科中有着广泛的学、生命科学等交叉学科中有着广泛的应用应用应用问题举例应用问题举例323023342326xyzxyzxyz1 1、一个两千年前的例子、一个两千年前

2、的例子今有上禾三秉，中禾二秉，下禾一秉，实三十斗；今有上禾三秉，中禾二秉，下禾一秉，实三十斗； 上禾二秉，中禾三秉，下禾一秉，实三十四上禾二秉，中禾三秉，下禾一秉，实三十四斗；斗； 上禾一秉，中禾二秉，下禾三秉，实二十六上禾一秉，中禾二秉，下禾三秉，实二十六斗。斗。问上、中、下禾实一秉各几何？问上、中、下禾实一秉各几何？答曰：上禾一秉九斗四分斗之一。中禾一秉四斗答曰：上禾一秉九斗四分斗之一。中禾一秉四斗四分斗之一。下禾一秉二斗四分斗之三。四分斗之一。下禾一秉二斗四分斗之三。-九章算术九章算术nnnnnnaaaaaaaaa212222111211bxAnnbbbxxx2121本课程第二章的内容：

3、本课程第二章的内容： 线性方程组的数值方法！线性方程组的数值方法！2、已经测得在某处海洋不同深度处的水温如下：深度（M） 466 741 950 1422 1634水温（oC）7.04 4.28 3.40 2.54 2.13根据这些数据，希望合理地估计出其它深度（如500米，600米，1000米）处的水温本课程第三章的内容：插值法用比较简单的函数代替复杂的函数误差为最小，即距离为最小（在不同的度量意义下）本课程第四章的内容：函数最优逼近法3、人口预测 下面给出的是中国1900年到2000年的人口数，我们的目标是预测未来的人口数（数据量较大时）19505519619606620719708299

4、219809870519901143332000126743432231ttty30/ )1979( ts432231sssy4、铝制波纹瓦的长度问题、铝制波纹瓦的长度问题 建筑上用的一种铝制波纹瓦是用一种机建筑上用的一种铝制波纹瓦是用一种机器将一块平整的铝板压制而成的器将一块平整的铝板压制而成的.假若要求波纹瓦长假若要求波纹瓦长4 4英尺英尺, ,每个波纹的高度每个波纹的高度( (从从中心线中心线) )为为1 1英寸英寸, ,且每个波纹以近似且每个波纹以近似22英寸英寸为一个周期为一个周期. . 求制做一块波纹瓦所需铝板的求制做一块波纹瓦所需铝板的长度长度L.L. 这个问题就是要求由函数这个

5、问题就是要求由函数dxxdxxfL48024802)(cos1)(1上述积分称为第二类椭圆积分上述积分称为第二类椭圆积分, ,它不能用普它不能用普通方法来计算通方法来计算.本课程第五章的内容：数值微积分5、天体力学中的Kepler方程x是行星运动的轨道，它是时间t 的函数sin0,01xxt 本课程第六章的内容： 非线性方程的数值解法全球定位系统：在地球的任何一个位置，至少可以同时收到4颗以上卫星发射的信号 6、全球定位系统（Global Positioning System, GPS)02468051002468图 7.8HeightS6S3S4S2S1RS5N-S positions 表示

6、地球上一个接收点R的当前位置，卫星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本课程第六章的内容： 非线性方程组的数值方法非线性方程组的数值方法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本课程第七章的内容： 矩阵特征值问题的数值方法8、生物化学反应的例子 A，B，C是三种蛋白质，

9、其反应如下：123aaaABBBCBBCAC 我们通过建模可以得到如下方程组 111323ya ya y y 1(0)1y221132322ya ya y ya y2(0)0y3y 222a y3(0)0y A： B：C： 本课程第八章的内容： 常微分方程的数值解法用计算机解决实际问题的步骤用计算机解决实际问题的步骤 建立数学模型建立数学模型 选择数值方法选择数值方法 编写程序编写程序 上机计算结果上机计算结果数值计算方法的主要任务数值计算方法的主要任务： 数值求解各类数值问题，并提出最有效的算法。（包括误差分析，算法的稳定性及收敛性）第1章 计算方法的一般概念n算法n误差1.1 算法n由基本

10、运算（算术运算及一些逻辑运算）及运算顺序的规定构成的完整的解题步骤。 例如：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次减法次减法缩减幂级数法（第四章）：*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可得利用根的关系acxx219991021010021010991x若已算出121xacx110111099上式是解二次方程的数值公式几个简单的估计公式几个简单的估计公式1212121212211212112222,()()()xxxxxxxxx xxxxxxxxxxxx 的 近 似 值设1.2.4机器数与舍

13、入误差机器数与舍入误差 在计算机中，一般实数x均按舍入原则表示成: (b进制浮点数)其中b称为基数，m为阶码， 为尾数或数码 时fl(x)称为规格化的浮点数，t为计算机的位数.一定型号的计算机，t是固定的，L=m=U.12( )(0.)mtfl xxbx xx 1 20.tx xx10 x 避免大数吃掉小数(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)一般来说，若干数相加最好先加绝对值较小的数！简化计算步骤，尽量减少运算次数简化计算步骤，尽量减少运算次数12864321684222222222215次乘法运算而不是255次！2562例如：10001000111111()1(1)11001nnn nnn又如：例如，计算多项式例如，计算多项式 通常运算的乘法次数为通常运算的乘法次数为 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算法的稳定性算法的稳定性例如：计算积分表表 1-1Ek 0.367879 0.264242 0.207274 0.170904 0.145480 0.127120 0.110160 0.118720 -0.068480k用上面的递推公式，在字长为6，基底为10的计算机上，从 E1出发计算前几个积分值，其结果如上表表1-1。 被

16、积函数 在积分限（0,1）区间内都是正值，积分值 E9 取三位有效数字的精确结果为0.0916，但上表中E9 = - 0.068480却是负值，与0.0916相差很大。怎么会出现这种现象？可分析如下。 由于在计算时有舍入误差约为1xnex710412. 4且考虑以后的计算都不再另有舍入误差。此对后面各项计算的影响为! 221)(21112EEE! 2211E53! 2213113EE! 321311E ! 321314114EE! 42131411E! 981919E这样，算到 E9 时产生的误差为6101. 010412. 4! 9! 97这就是一个不小的数值了。 可以改进算法来提高此例的数

17、值稳定性，即将递推公式改写为nEEnn11从后向前递推计算时，En 的误差下降为原来的1/n，因此只要 n 取得足够大，误差逐次下降，其影响就会越来越小。由 可知： 当 时 。因此可取E20作为初始值进行递推计算。 由于 ，故E20 =0 的误差约为1/21。在计算 时误差下降到到计算E15时误差已下降到 ，结果如表表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