计算方法课件第一章.

计算方法何凯[e-mail]2/47教材《计算方法》,易大义等,浙江大学出版社,2002年第2版3/47《计算方法》课程体系第一章数值计算中的误差第二章插值法第三章曲线拟合的最小二乘法第四章数值积分第五章非线性方程的数值解法第六章方程组的数值解法第七章常微分方程数值解法4/47《计算方法》课程体系本课程的内容数值逼近数值代数常微分方程的数值方法插值法数据拟合的最小二乘法数值积分和数值微分*线性方程组的求解非线性方程组的求解矩阵特征值*第一章数值计算中的误差3学时6/47本章内容§1.1引言§1.2误差的种类及其来源§1.3绝对误差和相对误差§1.4有效数字及其与误差的关系§1.5误差的传播与估计§1.6选用算法应遵循的原则小结作业与实验7/47本章要求1.熟悉计算方法在解决实际问题中所处的地位,熟悉计算方法是以计算机为工具求近似解的数值方法；2.熟悉绝对误差（限），相对误差（限）及有效数字概念；3.熟悉公式；4.熟悉选用算法应遵循的原则。8/47§1.1引言解决科学技术和工程问题的步骤:什么是数值计算方法:将所预求解的数学模型简化成一系列算术运算和逻辑运算,以便在计算机上求解,并对算法的稳定性、收敛性和误差进行分析。实际问题数学问题提供计算方法程序设计上机计算结果分析9/47§1.1引言简单地说，就是研究如何用计算机有效地解决一个数学问题。如何理解这两个含义？这句话有两个含义（1）有一个有效的数学方法（2）一个能实现方法的有效程序（算法）——先看两个例子10/47§1.1引言算法影响计算的速度和效率（见课本P2秦九韶算法）例1古代中国人的贡献——多项式的计值：设f(x)=a0xn+a1xn-1+…+an-1x+an原始的算法需：n+n-1+…+1=n(n+1)/2次乘法。秦九韶算法：f(x)=(...(a0x+a1)x+…+an-1)x+an仅需n次乘法。计算代价快速下降。11/47§1.1引言算法影响计算的精度例2设多项式为(x-2)9,我们来计算其在区间[1.92,2.08]上的值。令p(x)=(x-2)9q(x)=x9–18x8+144x7–672x6+2016x5-4032x4+5376x3–4608x2+2304x-512则p(x)=q(x)，以下我们分别作画p(x)与q(x)的图。12/47上例说明，即使数学上的恒等公式，用计算机来算，结果也是不一样的。p(x)q(x)13/47§1.2误差的种类及其来源一.误差来源例1，例2的结果的根源实际问题数学模型建立算法上机计算结果(初值误差)观测误差模型误差(方法误差)截断误差舍入误差14/47§1.2误差的种类及其来源二.误差分类1.模型误差（描述误差）/*ModelingError*/简化，抽象问题后建立的数学模型与实际问题之差。2.观测误差/*MeasurementError*/观测和实验得到的参量（物理量为电压、电流、温度等）15/47§1.2误差的种类及其来源3.截断误差（方法误差）/*TruncationError*/有限过程代替无限过程的误差（无穷级数求和，只能取前面有限项求和来近似代替）。这种计算方法本身出现的误差，所以也称为方法误差。如右端是截断误差。,......!5!3sin53xxxx......!5)!3(sin53xxxx16/47§1.2误差的种类及其来源4.舍入误差/*RoundoffError*/计算机字长有限，一般实数不能精确存储，于是产生舍入误差。例如：在10位十进制数限制下：舍入误差很小，本课程将研究它在运算过程中是否能有效控制。））本应（、）本应、1222104040000000000.0000004.1040000040000.1000004.1000002.1(0000004.1)000002.1(233333333333.031(3333333333.031117/47§1.2误差的种类及其来源据说,美军1910年的一次部队的命令传递是这样的:营长对值班军官:明晚大约8点钟左右,哈雷彗星将可能在这个地区看到,这种彗星每隔76年才能看见一次。命令所有士兵着野战服在操场上集合,我将向他们解释这一罕见的现象。如果下雨的话,就在礼堂集合,我为他们放一部有关彗星的影片。值班军官对连长:根据营长的命令,明晚8点哈雷彗星将在操场上空出现。如果下雨的话,就让士兵穿着野战服列队前往礼堂,这一罕见的现象将在那里出现。18/47§1.2误差的种类及其来源连长对排长:根据营长的命令,明晚8点,非凡的哈雷彗星将身穿野战服在礼堂中出现。如果操场上下雨,营长将下达另一个命令,这种命令每隔76年才会出现一次。排长对班长:明晚8点,营长将带着哈雷彗星在礼堂中出现,这是每隔76年才有的事。如果下雨的话,营长将命令彗星穿上野战服到操场上去。班长对士兵:在明晚8点下雨的时候,著名的76岁哈雷将军将在营长的陪同下身着野战服,开着他那“彗星”牌汽车,经过操场前往礼堂。19/47§1.3绝对误差和相对误差一．绝对误差/*absoluteerror*/设——准确值，——近似值。称为的绝对误差(简称误差)为的绝对误差限。二．相对误差/*relativeerror*/称为的相对误差。实用中，常用表示的相对误差。称为的相对误差限。x*xxxxe*)(|)(|xe*x*xxxexer)()(*xxxe)()(xre*x*x20/47§1.4有效数字及其与误差的关系一．有效数字/*significantdigits*/为有效数。，则称＝若位有效数字，分别是具有则说若设*21*121,,,)2.4.1P10(1021*),0(10).0(xpnaaanxxxpaaaaaxnnmmpn一定要从规格化后的数来判断其位数有效位数与第一个非0项后的数字个数是不一致的。四舍五入所得到的数是一致的。21/47§1.4有效数字及其与误差的关系。，，分别是位有效数字有由有效数字定义可知故该不等式又可写为又：末位的的半个单位，即不超过则误差经“四舍五入”所得，是某数＝：设例072,3*,1021*)270.0(101021*0270.03311*4**)(*xxxxxxxexxx注:四舍五入规则修正为四舍五以上入,五时若前一位是偶数则5舍去,奇数则进一,以减少积累误差。22/47§1.4有效数字及其与误差的关系不是有效数。故不是有效数字，中的数字由于。，，位有效数字，分别是有故，＝，：例*9*8233*1021*102105.004.0*89.3293.324321*xxxxxxxxx23/47§1.4有效数字及其与误差的关系二．有效数位与误差的关系*)(xe位有效数字。至少有则反之，若）（位有效数字，则具有定理：若近似数）（由定义越小越多，则绝对误差有效数位nxaxeaxenxxennrnr)1(1)()1(1)()(10)1(214.4.1P111021.22.4.1.124/47§1.4有效数字及其与误差的关系证：证毕。位有效数字。至少具有因此，反之，由位有效数字时，有，故当因nxaaxaaxnxaxanmnmrnmnmrmm,105.010)1(2110)1(102110105.010)1(1011111111*1*125/47§1.4有效数字及其与误差的关系例5：为使*的相对误差小于0.001%,至少应取几位有效数字？解：假设*取到n位有效数字，则其相对误差上限为要保证其相对误差小于0.001%，只要保证其上限满足已知a1=3，则从以上不等式可解得n6log6，即n6，应取*=3.14159。111021*nraε%001.01021*11nraε26/47§1.5误差的传播与估计例：蝴蝶效应——纽约的一只蝴蝶翅膀一拍，风和日丽的北京就刮起台风来了？！以上是一个病态问题/*ill-posedproblem*/关于本身是病态的问题，还是留给数学家去头痛吧！NYBJ27/47§1.5误差的传播与估计一.一元函数情形误差传播）。数值的误差的近似式（差引起的函）给出了自由变量的误）和（（）（得两边除以）（展开公式，由，则设4.13.14.1*)()(3.1*)(*)(*)(*)*)((*)()(**)()()(*)(**)(*)('*)(*)(*)('**)(*)(*****xrxxfxfyrrxfxfxyyyreexeeexfyxexfyexxxfxfxfyyyeTaylorxfyxfy28/47§1.5误差的传播与估计二.多元函数情形）（）（展开公式类似可得由多元函数的则，设4.5.1*)(**),*,*,(*),*,*,(*)(3.5.1*)(*),*,*,(*)(*),*,*,(*),,,(212112112121irinninirinniinnxexxxxfxxxfyexexxxfyeTaylorxxxfyxxxfy29/47§1.5误差的传播与估计二.多元函数情形（续））（）（）（同号）（，可得分别取）式中，在（，，9.1)(8.17.1,max),(6.1*2)1()2()1()*2*1()2()1()21(21)(21)21(21212121**********xexexexexxexexexxexxxexxexxxxxxxxfrrrrrrrririr30/47§1.5误差的传播与估计例6：测得某桌面的长a的近似值a*=120cm,宽b的近似值b*=60cm。若已知|e(a*)|≤0.2cm,|e(b*)|≤0.1cm。试求近似面积s*=a*b*的绝对误差限与相对误差限。%33.06012024|**)(||*)(|241.01202.060|*)(||*||*)(||*||*)(*)(**)(**)(*)*,(*)(*)*,(*)(,),(,)5.1(,:221ssesecmbeaaebsebeaaebbebbasaeabasseabsxxfyabsr相对误差限为则换为将中在公式面积解31/47§1.6选用算法应遵循的原则一.尽量简化计算步骤，减少乘除运算的次数。100111)111()1(1)()0121(2)1(......21......)(10001100010110nnnkkknnnnnnnnnnuxp,,,,n-n-kaxuuaunnnxaxaaxp。又如则乘法次数仅为若采用递推算法，通常运算的乘法次数为例如，计算多项式32/47§1.6选用算法应遵循的原则二.防止大数“吃掉”小数当|a||b|时，尽量避免a+b。例如，假设计算机只能存放10位尾数的十进制数，则例：89981040000000000.0101.01004.010110010)110(291992x,xxx精确解为的根。用单精度计算33/47§1.6选用算法应遵循的原则算法1：利用求根公式在计算机内，109存为0.11010，1存为0.1101。做加法时，两加数的指数先向大指数对齐，再将浮点部分相加。即1的指数部分须变为1010，则：1=0.00000000011010，取单精度时就成为：109+1=0.100000001010+0.000000001010=0.100000001010aacbbx242024,102422921aacbbxaacbbx大数吃小数34/47§1.