计算方法课件第一章

1、计计 算算 方方 法法何凯何凯2/47教材教材n计算方法计算方法, , 易大义等易大义等, , 浙江大学出版社浙江大学出版社, , 2002 2002年第年第2 2版版3/47计算方法计算方法课程体系课程体系n第一章第一章 数值计算中的误差数值计算中的误差n第二章第二章 插值法插值法n第三章第三章 曲线拟合的最小二乘法曲线拟合的最小二乘法n第四章第四章 数值积分数值积分n第五章第五章 非线性方程的数值解法非线性方程的数值解法n第六章第六章 方程组的数值解法方程组的数值解法n第七章第七章 常微分方程数值解法常微分方程数值解法4/47计算方法计算方法课程体系课程体系本本课课程程的的内内容容数值逼近

2、数值逼近数值代数数值代数常微分方程的数值方法常微分方程的数值方法插值法插值法数据拟合的最小二乘法数据拟合的最小二乘法数值积分和数值微分数值积分和数值微分*线性方程组的求解线性方程组的求解非线性方程组的求解非线性方程组的求解矩阵特征值矩阵特征值*第一章第一章数值计算中的误差数值计算中的误差3 学时学时6/47本章内容本章内容n1.1 1.1 引言引言n1.2 1.2 误差的种类及其来源误差的种类及其来源n1.3 1.3 绝对误差和相对误差绝对误差和相对误差n1.4 1.4 有效数字及其与误差的关系有效数字及其与误差的关系n1.5 1.5 误差的传播与估计误差的传播与估计n1.6 1.6 选用算法

3、应遵循的原则选用算法应遵循的原则n小结小结n作业与实验作业与实验7/47本章要求本章要求n1. 熟悉计算方法在解决实际问题中所处的地位熟悉计算方法在解决实际问题中所处的地位,熟悉计算方法是以计算机为工具求近似解的数熟悉计算方法是以计算机为工具求近似解的数值方法；值方法；n2. 熟悉绝对误差（限），相对误差（限）及有熟悉绝对误差（限），相对误差（限）及有效数字概念；效数字概念；n3. 熟悉公式；熟悉公式；n4. 熟悉选用算法应遵循的原则。熟悉选用算法应遵循的原则。8/471.1 引言引言n解决科学技术和工程问题的步骤解决科学技术和工程问题的步骤:n什么是什么是数值计算方法数值计算方法: 将所预求

4、解的数学模将所预求解的数学模型简化成一系列算术运算和逻辑运算型简化成一系列算术运算和逻辑运算, 以便以便在计算机上求解在计算机上求解, 并对算法的稳定性、收敛并对算法的稳定性、收敛性和误差进行分析。性和误差进行分析。实际问题数学问题提供计算方法实际问题数学问题提供计算方法程序设计上机计算结果分析程序设计上机计算结果分析9/471.1 引言引言n简单地说，就是研究如何用计算机有效地简单地说，就是研究如何用计算机有效地解决一个数学问题。解决一个数学问题。n如何理解这两个含义？如何理解这两个含义？这句这句话有话有两个两个含义含义（1）有一个有效的数学方法）有一个有效的数学方法（2）一个能实现方法的有

5、效程序）一个能实现方法的有效程序 （算法）（算法）先看两个例子先看两个例子10/471.1 引言引言n算法影响计算的速度和效率算法影响计算的速度和效率 （见课本（见课本 P2 秦九韶算法）秦九韶算法）例例1 古代中国人的贡献古代中国人的贡献多项式的计值：多项式的计值： 设设 f (x) = a0 xn + a1 xn-1 + + an-1 x+an原始的算法需：原始的算法需： n + n-1 + + 1 = n ( n+1 ) / 2 次乘法。次乘法。秦九韶算法：秦九韶算法： f (x) = ( . ( a0 x + a1 ) x + + an-1 ) x + an 仅需仅需 n 次乘法。次乘

6、法。计算代价快速下降计算代价快速下降。11/471.1 引言引言n算法影响计算的精度算法影响计算的精度例例2 设多项式为设多项式为 ( x-2)9 , 我们来计算其在区间我们来计算其在区间1.92, 2.08上的值。上的值。令令 p(x) = (x-2)9 q(x) = x9 18 x8 + 144 x7 672 x6 + 2016 x5 - 4032 x4 + 5376 x3 4608 x2 + 2304 x - 512 则则 p(x) = q(x)，以下我们分别作画以下我们分别作画 p(x) 与与 q(x)的图。的图。12/47n上例说明，即使数学上的恒等公式，用计上例说明，即使数学上的恒

7、等公式，用计算机来算，结果也是不一样的。算机来算，结果也是不一样的。p(x)q(x)13/471.2 误差的种类及其来源误差的种类及其来源n一一. 误差来源误差来源例1，例2 的结果的根源实实际际问问题题数数学学模模型型建建立立算算法法上上机机计计算算结结果果(初值误差初值误差)观测误差观测误差模型误差模型误差(方法误差方法误差)截断误差截断误差舍入误差舍入误差14/471.2 误差的种类及其来源误差的种类及其来源n二二. 误差分类误差分类1. 模型误差（描述误差）模型误差（描述误差）/* Modeling Error */n简化，抽象问题后建立的数学模型与实际问简化，抽象问题后建立的数学模型

8、与实际问题之差。题之差。2. 观测误差观测误差 /* Measurement Error */n观测和实验得到的参量（物理量为电压、电观测和实验得到的参量（物理量为电压、电流、温度等）流、温度等）15/471.2 误差的种类及其来源误差的种类及其来源3. 截断误差（方法误差）截断误差（方法误差）/*Truncation Error*/n有限过程代替无限过程的误差（无穷级数有限过程代替无限过程的误差（无穷级数求和，只能取前面有限项求和来近似代求和，只能取前面有限项求和来近似代替）。这种计算方法本身出现的误差，所替）。这种计算方法本身出现的误差，所以也称为方法误差。如以也称为方法误差。如n右端是截

9、断误差。右端是截断误差。, .!5!3sin53 xxxx.!5)!3(sin53 xxxx16/471.2 误差的种类及其来源误差的种类及其来源4. 舍入误差舍入误差 /* Roundoff Error */n计算机字长有限，一般实数不能精确存储，于计算机字长有限，一般实数不能精确存储，于是产生舍入误差。是产生舍入误差。n例如：在例如：在 10 位十进制数限制下：位十进制数限制下：n舍入误差很小，本课程将研究它在运算过程中舍入误差很小，本课程将研究它在运算过程中是否能有效控制。是否能有效控制。）本本应应（、）本本应应、1222104040000000000. 0000004. 1040000

10、040000. 1000004. 1000002. 1(0000004. 1)000002. 1(233333333333. 031(3333333333. 0311 17/471.2 误差的种类及其来源误差的种类及其来源n据说据说, 美军美军1910年的一次部队的命令传递是这样的年的一次部队的命令传递是这样的:营长营长对对值班军官值班军官: 明晚大约明晚大约 8点钟左右点钟左右, 哈雷彗星将哈雷彗星将可能在这个地区看到可能在这个地区看到, 这种彗星每隔这种彗星每隔 76年才能看见年才能看见一次。命令所有士兵着野战服在操场上集合一次。命令所有士兵着野战服在操场上集合, 我将我将向他们解释这一罕

11、见的现象。如果下雨的话向他们解释这一罕见的现象。如果下雨的话, 就在就在礼堂集合礼堂集合, 我为他们放一部有关彗星的影片。我为他们放一部有关彗星的影片。值班军官值班军官对对连长连长: 根据营长的命令根据营长的命令, 明晚明晚8点哈雷彗点哈雷彗星将在操场上空出现。如果下雨的话星将在操场上空出现。如果下雨的话, 就让士兵穿就让士兵穿着野战服列队前往礼堂着野战服列队前往礼堂, 这一罕见的现象将在那里这一罕见的现象将在那里出现。出现。18/471.2 误差的种类及其来源误差的种类及其来源连长连长对对排长排长: 根据营长的命令根据营长的命令, 明晚明晚 8 点点, 非凡的哈非凡的哈雷彗星将身穿野战服在礼

12、堂中出现。如果操场上雷彗星将身穿野战服在礼堂中出现。如果操场上下雨下雨, 营长将下达另一个命令营长将下达另一个命令, 这种命令每隔这种命令每隔 76 年年才会出现一次。才会出现一次。排长排长对对班长班长: 明晚明晚 8 点点, 营长将带着哈雷彗星在礼营长将带着哈雷彗星在礼堂中出现堂中出现, 这是每隔这是每隔 76 年才有的事。如果下雨的年才有的事。如果下雨的话话,营长将命令彗星穿上野战服到操场上去。营长将命令彗星穿上野战服到操场上去。班长班长对对士兵士兵: 在明晚在明晚 8 点下雨的时候点下雨的时候, 著名的著名的 76 岁岁哈雷将军将在营长的陪同下身着野战服哈雷将军将在营长的陪同下身着野战服

13、, 开着他那开着他那“彗星彗星”牌汽车牌汽车, 经过操场前往礼堂。经过操场前往礼堂。19/471.3 绝对误差和相对误差绝对误差和相对误差n一绝对误差一绝对误差 /* absolute error */设设 准确值，准确值， 近似值。近似值。称称 为为 的绝对误差的绝对误差(简称误差简称误差) 为为 的绝对误差限。的绝对误差限。n二相对误差二相对误差 /* relative error */称称 为为 的相对误差。的相对误差。 实用中，常用实用中，常用 表示表示 的相对误差。的相对误差。 称称 为为 的相对误差限。的相对误差限。x*xxxxe *)( | )(|xe*x*xxxexer)()(

14、 *x xxe)( )(xre*x*x20/471.4 有效数字及其与误差的关系有效数字及其与误差的关系n一有效数字一有效数字 /* significant digits */为为有有效效数数。，则则称称若若位位有有效效数数字字，分分别别是是具具有有则则说说若若设设*21*121,)2 . 4 . 1 P10(1021*), 0(10). 0(xpnaaanxxxpaaaaaxnnmmpn 一定要从规格化后的数来判断其位数一定要从规格化后的数来判断其位数有效位数与第一个非有效位数与第一个非 0 项后的数字个数是不项后的数字个数是不一致的。一致的。 四舍五入所得到的数是一致的。四舍五入所得到的数

15、是一致的。21/471.4 有效数字及其与误差的关系有效数字及其与误差的关系n 。，分分别别是是位位有有效效数数字字有有由由有有效效数数字字定定义义可可知知故故该该不不等等式式又又可可写写为为又又：末末位位的的的的半半个个单单位位，即即不不超超过过则则误误差差经经“四四舍舍五五入入”所所得得，是是某某数数：设设例例072,3*,1021*)270. 0(101021*0270. 03311*4*)(*xxxxxxxexxx 注注: 四舍五入规则修正为四舍五以上入四舍五入规则修正为四舍五以上入, 五时若前一五时若前一位是偶数则位是偶数则5舍去舍去, 奇数则进一奇数则进一, 以减少积累误差。以减少

16、积累误差。22/471.4 有效数字及其与误差的关系有效数字及其与误差的关系n 不不是是有有效效数数。故故不不是是有有效效数数字字，中中的的数数字字由由于于。，位位有有效效数数字字，分分别别是是有有故故，：例例*9*8233*1021*102105. 004. 0*89.3293.324321*xxxxxxxxx 23/471.4 有效数字及其与误差的关系有效数字及其与误差的关系n二有效数位与误差的关系二有效数位与误差的关系*)(xe位位有有效效数数字字。至至少少有有则则反反之之，若若）（位位有有效效数数字字，则则具具有有定定理理：若若近近似似数数）（由由定定义义越越小小越越多多，则则绝绝对对

17、误误差差有有效效数数位位nxaxeaxenxxennrnr )1(1)()1(1)()(10)1(214 . 4 . 1 P111021. 22 . 4 . 1. 124/471.4 有效数字及其与误差的关系有效数字及其与误差的关系n证：证：证证毕毕。位位有有效效数数字字。至至少少具具有有因因此此，反反之之，由由位位有有效效数数字字时时，有有，故故当当因因nxaaxaaxnxaxanmnmrnmnmrmm ,105 . 010)1(2110)1(102110105 . 010)1(1011111111*1*1 25/471.4 有效数字及其与误差的关系有效数字及其与误差的关系n例例5： 为使为

18、使 *的相对误差小于的相对误差小于0.001%,至少应取几位有效数字？至少应取几位有效数字？ 解：解：假设假设 * 取到取到 n 位有效数字，则其相对误差上限为位有效数字，则其相对误差上限为 要保证其相对误差小于要保证其相对误差小于0.001%，只要保证其上限满足，只要保证其上限满足 已知已知 a1 = 3，则从以上不等式可解得，则从以上不等式可解得 n 6 log6， 即即 n 6，应取，应取 * = 3.14159。111021* nra%001.01021*11 nra26/471.5 误差的传播与估计误差的传播与估计n例：例：蝴蝶效应蝴蝶效应 纽约的一只蝴蝶翅膀一拍，风纽约的一只蝴蝶翅

19、膀一拍，风和日丽的北京就刮起台风来了？！和日丽的北京就刮起台风来了？！以上是一个以上是一个病态问题病态问题 /* ill-posed problem*/关于本身是病态的问题，还是留给数学家去头痛吧！关于本身是病态的问题，还是留给数学家去头痛吧！NYBJ27/471.5 误差的传播与估计误差的传播与估计n一一. 一元函数情形一元函数情形误差传播）。误差传播）。数值的误差的近似式（数值的误差的近似式（差引起的函差引起的函）给出了自由变量的误）给出了自由变量的误）和（）和（）（得得两边除以两边除以）（展开公式展开公式，由，由，则，则设设4 . 13 . 14 . 1*)()(3 . 1*)(*)(*

20、)(*)*)(*)()(*)()()(*)(*)(*)( *)(*)(*)( *)(*)(*xrxxfxfyrrxfxfxyyyreexeeexfyxexfyexxxfxfxfyyyeTaylorxfyxfy 28/471.5 误差的传播与估计误差的传播与估计n二二. 多元函数情形多元函数情形）（）（展开公式类似可得展开公式类似可得由多元函数的由多元函数的则，则，设设4 . 5 . 1*)(*),*,*,(*),*,*,(*)(3 . 5 . 1*)(*),*,*,(*)(*),*,*,(*),(212112112121irinninirinniinnxexxxxfxxxfyexexxxfye

21、Taylorxxxfyxxxfy 29/471.5 误差的传播与估计误差的传播与估计n二二. 多元函数情形（续）多元函数情形（续）（）（）（同同号号）（，可可得得分分别别取取）式式中中，在在（，9 . 1)(8 . 17 . 1,max),(6 . 1*2)1()2()1()*2*1()2()1()21(21)(21)21(21212121*xexexexexxexexexxexxxexxexxxxxxxxfrrrrrrrririr 30/471.5 误差的传播与估计误差的传播与估计n例例6：测得某桌面的长测得某桌面的长a的近似值的近似值a*=120cm, 宽宽b的近似的近似值值b*= 60c

22、m。若已知。若已知|e(a*)|0.2cm, |e(b*)|0.1cm。试。试求近似面积求近似面积s*= a*b*的绝对误差限与相对误差限。的绝对误差限与相对误差限。%33. 06012024|*)(|*)(|241 . 01202 . 060|*)(|*|*)(|*|*)(*)(*)(*)(*)*,(*)(*)*,(*)(,),(,)5 . 1(,:221 ssesecmbeaaebsebeaaebbebbasaeabasseabsxxfyabsr相相对对误误差差限限为为则则换换为为将将中中在在公公式式面面积积解解31/471.6 选用算法应遵循的原则选用算法应遵循的原则n一一. 尽量简化计

23、算步骤，减少乘除运算的次数。尽量简化计算步骤，减少乘除运算的次数。100111)111()1(1)()0121( 2)1(.21.)(10001100010110 nnnkkknnnnnnnnnnuxp,n-n-kaxuuaunnnxaxaaxp。又又如如则则乘乘法法次次数数仅仅为为若若采采用用递递推推算算法法，通通常常运运算算的的乘乘法法次次数数为为例例如如，计计算算多多项项式式32/471.6 选用算法应遵循的原则选用算法应遵循的原则n二二. 防止大数防止大数“吃掉吃掉”小数小数当当|a|b|时，尽量避免时，尽量避免a+b 。例如，假设计算。例如，假设计算机只能存放机只能存放10位尾数的十

24、进制数，则位尾数的十进制数，则例：例：89981040000000000. 0101 . 01004. 010110010)110(291992x,xxx精精确确解解为为的的根根。用用单单精精度度计计算算33/471.6 选用算法应遵循的原则选用算法应遵循的原则 算法算法1：利用求根公式利用求根公式 在计算机内，在计算机内，109 存为存为 0.1 1010，1存为存为 0.1 101。做做加法时，两加数的指数先向大指数对齐，再将浮点部加法时，两加数的指数先向大指数对齐，再将浮点部分相加。即分相加。即 1 的指数部分须变为的指数部分须变为 1010， 则：则： 1 = 0.0000000001

25、 1010 ， 取单精度时就成为：取单精度时就成为： 109 + 1 = 0.10000000 1010 + 0.00000000 1010 = 0.10000000 1010aacbbx242 024,102422921 aacbbxaacbbx大数大数吃吃小数小数34/471.6 选用算法应遵循的原则选用算法应遵循的原则算法算法2： 例：例：按从小到大、以及从大到小的顺序分别计算按从小到大、以及从大到小的顺序分别计算 1 + 2 + 3 + + 40 + 109110101024)(991221921 xacxacxxaacbbsignbx再利用再利用先解出先解出求和时求和时从小到大从小到大相加相加, 可使和的误差减小。可使和的误差减小。35/471.6 选用算法应遵循的原则选用算法应遵循的原则n三三. 尽量避免相近数相减尽量避免相近数相减 例：例：a1 = 0.12345，a2 = 0.12346， 各有各有 5 位有效数字。位有效数字。 而而a2 - a1= 0.00001, 只剩下只剩下 1 位有效数字。位有效数字。2cos1sinsincos10)1(1111111xtgxxxxxxxxxxxxxx或或时时，应应接接近近于于当当很很大大时时，应应当当 36/471.6 选用算法应遵循的原则选用算法应遵循的原则n四四. 避免绝对值很小的数做分母，