计算方法教案

1、计算方法教案第一章绪论（1）误差）选用教材：高等教育出版社计算机数值方法（第三版）施吉林等编著主讲老师：张利萍基本内容提要1.误差的来源2.浮点数、误差、误差限和有效数字3.相对误差和相对误差限4.误差的传播5.在近似计算中需要注意的一些问题二教学目的和要求熟练掌握绝对误差、绝对误差限、相对误差、相对误差限和有效数字的概念及其相互关系；了解误差的来源以及误差传播的情况，掌握在基本算术运算中误差传播后对运算结果误差限的计算方法和函数求值中的误差估计；理解并掌握几种减少误差避免错误结果应采取的措施，了解选用数值稳定的算法的重要性。三教学重点1.绝对误差、绝对误差限、相对误差、相对误差限和有效数字的

2、概念及其相互关系，误差传播，减少误差避免错误结果应采取的措施。四教学难点1.误差传播；2.数值稳定算法的选用。五课程类型新知识理论课；六教学方法结合课堂提问，以讲授为主七教学过程如下：Introduction计算方法课程介绍计算方法是用数值的方法研究研究科学与工程中的计算问题；它的内容主要包括：近似值的计算和误差估计两个方面；主要工具：计算机；地位：这门课已成为工科各专业，特别是计算机科学与技术、土木工程、机械、数学等专业的必修基础课。2.发展状况几十年来，计算方法效率的提高是与计算机速度的提高几乎同步地、同比例地前进的。这里简述一下国家重点基础研究计划项目(简称973项目)“大规模科学计算研

3、究”(1999-2004)的主要内容，可以帮助同学们了解我国科学计算界所关心的问题。此项目由石钟慈院士等人为首组织，集中了我国计算数学、计算物理、计算力学、计算机、以及材料、环境能源等领域60多名专家，跨学科，跨部门通力合作研究以下几个方面的主要内容：2)1)复杂流体的高精度计算，含天气预报数值模拟研究；新材料的物理性质机理多尺度计算研究，含超导、超硬度合金等问题的计算研究；3）地质油藏模拟与波动问题及其反问题计算研究；（4）基础计算方法的理论创新与发展；（5）大规模计算软件系统的基础理论和实施计算规模是解决百万级节点问题（即求解百万至千万个未知数的方程组）。项目的目标是在几个重大科技难题的计

4、算研究中取得突破性进展，并在国际科学计算的学科前沿取得重要的一席之地。我国计算科学主要专家简介周毓麟冯康（1920-1993）院士，早年学习物理，后去苏联研究拓扑学和函数论，有深厚的数学和物理功底。1957年受命组建国家计算中心，为推动我国计算科学进入国际前列，培养一批批优秀人才，做出了不朽的贡献。冯院士一生中作出两项国际公认的重大创造，早在20世纪60年代，独立提出变分差分格式（即有限元），用于计算水坝很成功，1964年在国际上首次证明有限元的收敛性（中文发表），比M.Zlamal早四年，接着10年文化大革命，冯康的工作几乎被淹没，到70年代末才被国际公认为有限元理论的开拓者。1984年又开

5、创了Hamilton系统的辛几何算法。1923-）院士，著名的拓扑学、偏微分方程与计算科学家。1945年毕业于大同大学数学系，后在北京大学任教，1953年留学莫斯科大学研究偏微分方程，是我国最早用先验估计和拓扑方法研究偏微分方程的专家。1957年回国在北大任教，1960年调国防科工委从事核武器与数值模拟的研究，为“两弹一星”的成功做出了默默的贡献，这20年的工作鲜为人知，仍公开发表百余篇论文，他对差分法首次建立离散Sobolev空间的嵌入理论，并用于偏微分方程的研究，建立了全新体系。石钟慈（1933-）院士，早年在浙江大学和复旦大学学习基础数学，后留学苏联学习计算数学，在中国科学院成为冯康的得

6、力助手、合作者和接班人。与冯康合作研究弹性组合结构的数学理论，获得国家自然科学奖。20世纪80年代初，是我国最早赴德国洪堡基金会研究的学者之一。在对四阶板问题的非协调元的研究中，首次提出了非协调元收敛的F-E-M检验准则，成为以后一系列研究的基石，也培养了一批批优秀的人才。今年来对瀑布式网格法研究中，证明了最佳收敛性，并引发了一系列工作。1993年冯康院士去世后，石钟慈院士成为我国计算数学的领头人，为继续推动我国科学计算进入世界强国做出了贡献。我国计算数学界的院士还有林群和催俊芝。河南省计算数学发展状况介绍河南大学计算数学发展状况介绍课堂纪律要求，作业收交安排和答疑办法。第一章误差1.1误差的

7、来源用数学作为工具解决实际问题过程：实际问题f数学模型f数值计算方法f程序设计f上机计算结果。从上述过程看，影响计算精度的误差可分为两类：一类是“过失误差”，人为造成的，可以避免；另一类是“非过失误差”，无法避免。按来源的不同，分为下面几种：模型误差：数学模型与实际问题之间出现的不可避免的误差。将实际问题转化为数学问题，即建立数学模型时，对被描述的实际问题进行了抽象和简化，忽略了一些次要因素，数学模型只是客观世界的一种近似描述，之间存在一定的差别。属于“非过失误差”。例如，用1s=gt22描述自由落体规律，就是一个数学模型，此模型建立时忽略了空气阻力等因素。如果用s(t)表示真正的运动规律，则

8、模型误差为/、1s(t)-gt2。观测误差：建立模型和数值计算过程中，通常用到一些观测数据，由于仪器设备精度的限制，观测值和实际值之间的误差称为观测误差，也叫数据误差。截断误差：在计算中常遇到只有通过无限过程才能得到的结果，但在实际计算中只能用有限过程来计算，于是产生了有限过程代替无限过程的误差，这种误差称为截断误差，也叫方法误差。本课程主要研究该误差。例如，指数函数在x=0点有Taylor展式ex=1+x+2+（Ix|1）2!n!实际计算时只能取前面的有限项（例如n项）刃xkk=0无截断误差=艺匕-艺巴。k=0k!k=0k!舍入误差：数值计算过程中遇到的数据可能位数很多，也可能是无穷小数，但

9、在计算时只能对有限位数进行运算，往往要进行四舍五入，这样产生的误差称为舍入误差。例如，V2,3,“等，在计算时只能取有限位数进行运算，要进行四舍五入。少量舍入误差微不足道，但在计算机上完成百千万次运算后，舍入误差的积累有时是很大的。前两种误差是客观存在的，后面两种是计算方法所引起的，本课程所研究的内容只涉及后两种误差。1.2浮点数、误差、误差限和有限数字一浮点数浮点数：（1）浮点数属于有理数集的某特定子集，为该特定子集中数的数字表示；（2）浮点数可以用来近似表示任意一个实数，这种表示方法类似于基数为10的科学计数法；（3）如何一个浮点数x均可表示为x=3x0j=0.aa心x0j,LWJWU12

10、t其中，卩叫做这个数X的基（10进制中0=10，二进制中0=2），J是阶，取整数，3是尾数，由t位小数构成，t又称精度，0WaW01（i=1,2,丫）。i所谓浮点数就是小数点在逻辑上是不固定的，而定点数只能表示小数点固定的数值，具用浮点数或定点数表示某哪一种数要看用户赋予了这个数的意义是什么。浮点计算是指浮点数参与的运算，这种运算通常伴随着无法精确表示而进行的近似或舍入。浮点数的规格化（normalize）浮点数在计算机中的表示是基于科学计数法（ScientificNotation）.例如，32676用科学计数法可写成：3.2676x104，3.2676称为尾数（Mantissam史ntise

11、、,或者叫Significand）.4称为指数（Exponent）,10为基数（Radix）.浮点数在计算机中的表示于此类似，只不过基数是2而不是10.例如:17=17.0 x100=0.17xl02,类似地17二（10001）x2o二（0.10001）x25，22可以看出，每个浮点数的表示都不唯一，这样给计算机处理数据增加了复杂性。为了解决这个问题，规定尾数部分的最高位必须是1，也就是说尾数必须以0.1开头，只对指数做相应的调整，这称为正规化，也叫规格化。注：二进制：除2取余！例如，100用二进制表示（%表示求余数，/表示整数除法，忽略余数）：100%2=0二进制最后一位，100/2=50;

12、50%2=0二进制倒数第二位,50/2=25;25%2=1二进制倒数第三位，25/2=12;（忽略余数）12%2=0二进制倒数第四位，12/2=6;6%2=0二进制倒数第五位，6/2=3;3%2=1二进制倒数第六位，3/2=1;1%2=1二进制倒数第七位，结束。100用二进制表示为1100100=1x22+1x25+1x26。二误差、误差限和有效数字1.误差：数X的一个近似值x*与准确值x的差称为误差。用e*来表示，即e*=x*-x,误差可证可负，近似值大于准确值，误差为正，叫“强近似”；近似值小于准确值，误差为负，叫“弱近似”。2误差限：误差绝对值的上限。用e*表示，即Ie*1=1x*-xl

13、8*nx*-8*xx*+8*因此，可以用误差限表示近似值x*的精确度x=x*+8*例用有毫米刻度的尺子测量桌子长度，x*=1235mm，是实际长度的一个近似值，由米尺的精度知，误差不会超过半个毫米，则有Ix*-xI=I1235-xI-2即1234.5x1235.5，写成x=(1235土0.5)mm.对于一个近似值，除了用误差表示精确程度外，还希望这个近似值本身就能表示出它的准确程度。于是引入有效数字的概念。引例，x=*3=1.732050808，下面通过四舍五入取近似值：取3位：x*=1.738*(x)0.005；取5位：x*二1.7321(x)0.00005,这种近似值取法的特点是它们的误差

14、都不超过末位数字的半个单位，即1.731*x10-2,1.732111x10-4.3有效数字：如果近似值x*的误差限是某位上的半个单位时，称近似值“准确”到这一位，且该位直到x*的第一位非零数字一共有n位，则称x*有n位有效数字。n位x*=*J误差限不超过该位的半个单位从左向又看第一个非零数注意：在同一问题中，参加运算的数都应该有相同位数的有效数字。例，x=兀=3.14159265.，按四舍五入的原贝U取1位：x*=3,e*-0.14；11取3位:x*=3.14,e*-0.0016/33取5位：x*=3.1416,e*q+0.000007；55有效数字和误差限之间的关系在有效数字的定义中给出了

15、有效数字和误差限之间的关系。一般地，设有一个数x，其近似值x*的表示成规格化浮点数为：x*=0.aaax10m，12n其中，a,a,a都是0，1，2，,9中的一个数字，且a丰0，n是12n1正整数，m为整数。那么x*的误差限为I8*(X)KX10m-n2称X*具有n位有效数字，或称它精确到10m_n。上式表达了有效数字和绝对误差限之间的关系，可以看出：有效数字的位数越多，其绝对误差限也就越小。例若x*=3587.64是x的具有6位有效数字的近似值；(2)若x*=0.0023156是x的具有5位有效数字的近似值;分别求其误差限。解：（1）x*=0.358764x104XIX104-6=22x10

16、-2（2）x*=0.23156x10-2，所以m二2，有Ix*-xIX10-2-5=2A1。-7当然，也可以由有效数字的定义直接读出两数的误差限分别为：0.005和0.00000005.1.3相对(relative)误差和相对误差限1.相对误差：误差与精确值的比值，即e*x*-x。e*=。rxx注：实际应用中，真值x无法知道，通常取e*=工=乂二。rx*x*2相对误差限：相对误差绝对值的上界，记为：8*=二(8*为x*rIx*I的误差限)。注：为了区别相对误差与前面所讲的误差，把前面讲的误差称为绝对误差。例光速c=(2.997925土0.000001)xlOlCtm/s,近似值c*=2.997

17、925x1Oiocm/s,计算c*的误差、误差限、相对误差和相对误差限。解:误差：e*=c*c=0.000001x1010,误差限：e*1=卜10117=卜104Ne*r相对误差：e*e*=rc*0.0000012.997925x1010相对误差限：s*0.00005*=rIc*l2.997925x10103.相对误差限与有效数字位数的关系(1)x*有n位有效数字H*=丄x10(n1)r2a1分析：设x*=0.aaax10m12n为10进制规格化浮点数，则有ax10m-1|x*1l(a+1)x10m-11ns*rx10(n1)2a11*=r2a1x10(n1)x10m-n匚ax10m-11即，

18、相对误差限可以取为：该式表达了有效数字位数n与相对误差限之间的关系。反过来，有下面的结论：(2)*1x10(n1)nX*至少有n位有效数字。r2(a+1)1证明：因为1x*-x曰x*l：(冒1)X10m-1X20X10-(n-1)1=X10m-n2由误差限与有效数字的关系知道结论成立例，用x*表示e具有3位有效数字的近似值，求相对误差限。解：12a1X10-(n-1)=1X10-(3-1)=X1022x24Summary绝对误差（e：）、绝对误差限（8：）、相对误差（e：）及相对误差限（8：）rr与有效数字之间的关系（1）近似值x：的规格化浮点数表示形式为:x*=0.aax10m，12na丰0

19、；1（2）x：有n位有效数字；le：l=lx：xl8:X10m-n；24)lx：-xl1le：l=8:X10-(n-1)；rlx：lr2a1(5)le：l=8:-X10-(n-1)(-x：至少有n位有效数字);rlx：lr2(0+1)1n则（1）卜（2）J。（4）（5）.non（5）V注：对具体问题而言，可能还可以写出更加具体更加精确的误差限和相对误差限，例如：兀=3.1415929.，右取近似值x*=0.314x10i,按上述统一的方法取误差限为：*1x10-2，其实我们可以看出来：2IX*x10.2x10-2，即8*0.2x10-2比0.5x10-2更精确。即是说，在不同情况下，误差限或相

20、对误差限可以取得不同的结果，但统一取法有时便于问题的讨论。1.4误差的传播1.误差的传播：参与运算的数据往往都带有误差，这些数据的误差在多次的运算中使计算结果产生一定的误差，这就是误差的传播问题。下面考虑用近似数代替准确数作基本算术运算，研究运算结果的误差限以及函数求值的误差估计问题。注：X*的绝对误差常用X的微分来近似地表示，即dx沁e*=x*一x仝Ax可看作x*是x获得了一个该变量得到的，即x+Ax=x*,由微分定义知dx沁(x)-Ax=Ax=e*。基本运算结果的误差限结论1设x*和y*分别是x和y的近似值，即dxx*-x,dy沁y*-y,则直接运用微分运算法则，有(1)d(x土y)=dx

21、土dy；(2)d(xy)=ydx+xdy；(3)d(x；y)=(-xdy+ydx)/y2,y丰0.例.设a=1.21x3.65+9.81，其中每个数据的绝对误差限为0.005，求a的绝对误差限。解：da=d(1.21x3.65)+d9.81=3.65xd1.21+1.21xd3.65+d9.81所以，有Idal1.21x0.005+3.65x0.005+0.005沁0.02930.03结论2若把dx和dy分别看做x*和y*的相对误差限，即rrdxdx=I1=1d(Inx)I,(x的相对误差近似地等于Inx的微分)rxdy=I1=1d(Iny)Iry不妨认为分母都是正的)，则有rrd(x+y)q

22、max(dx,dy)，x,y冋号；rd(x-y)q(IxIdx+IyIdy)/1x-yI，x,y冋号;rrr3）4）证明：d(xy)qdx+dy，y丰0-rrr(1)d(x+y)Qd(x+y)=dx+dy=亠竺+亠dyrx+yx+yx+yxx+yy=-dx+丄dyx+yrx+yr若x与x同号，则上式右端dx和dy的系数亠和亠都在0和1之12rrx+yx+y间，且它们的和等于1，所以有d(x+y)maxdx，dy+rx+yrrmaxdx，dyx+yrr综上知有二maxdx，dyrrd(x+y)qmax(dx,dy)rrr(2)d(xy)qd(xy)=竺二生=亠rxyxyxydxydyxxyy故（

23、2）成立。(3)d(xy)dln(xy)dlnx+dlny|dlnx1+1dlny|=dx+dyrrr故(3)成立.(4)d(x：y)dIn(兰)|=|dlnxdlny|=|dxdy|dx+dyryrrrr故（4）成立。例上例中a的相对误差限da沁max(d(1.21x3.65),d9.81)沁max(d1.21+d3.65,d9.81)rrrrrr二max(dl.21,1.21+d3.65/3.65,d9.81/9.81)=max(0.005/1.21+0.005/3.65,0.005/9.81)沁max(0.0055,0.005)=0.0055.函数求值的误差估计由于x不精确，计算f(x)

24、时会产生误差。有下面的结论结论：假定f在包含x和X*的区间上足够光滑，用f(x*)去近似f(x)，则f(x)的相对误差限有下面的关系df(x)=(r分析：由Taylor公式可得纣(x)=f(x*)-f(x)=f(x)(x*-x)+2(x*-x)2其中g在x和x*之间。若f(x)与f(x)相比不太大，则忽略高阶项得Af(x)qdf(x)=f(x)dx二业2=(4x止f(x)f(x)xdf(x)=(r注:上式中系数f(x)x表示x的相对误差经过传播后增大或者缩f(x)小的因子。多元函数值的误差科硏多元函数的Taylor公式得到。这里我们以二元函数为例，给出误差估计的一般公式。对于二元函数y=f(x

25、,x)，设x*,x*,y*分别是x,x,y的近似值，且121212y*=f(x*,x*)，将函数在(x,x)处作Taylor展开，得1212f(x*,x*)二f(x,x)+学(x*-x)+-(x*-x)1212Qx11dx22121Q2fQ2fQ2f+-F(x*-x)2+2(x*-x)(x*-x)+L(x*-x)22!Qx211QxQx1122Qx221122+所以，忽略高阶项后有e*(f)訥=f(x：，x2)f(x1,x2)Qxe*(x)+1(x2)12这里，两个系数f和f分别是x*和兀*的绝对误差增长的因子，表示绝对误差经传播后增大或缩小的倍数。e*(f)Qfe*(x*)Qfe*(x*)e

26、*(f)=i+2-ry*Qxy*Qxy*12x*Qfx*Qf=ffe*(x*)+-2fe*(x*)y*Qxr1y*Qxr212两个系数叮堂和借f分别是x*和x*对y*的相对误差增长的因子，y*Qxy*Qx1212表示相对误差经传播后增大或缩小的倍数。上述讨论结果可以推广到一般的n元函数y=f(x,x，x)TOC o 1-5 h z12n将f(x,x,x)在点(x,x,x)处作Tay|or展开，并略去高阶项，即12n12n可得函数的近似值y*=f(x*,x*,x*)的绝对误差和相对误差的估计12n式：Qfe*(y)-e*(x*)，TOC o 1-5 h zQxii=1ie*(y)=if-e*(x

27、*)ry*Qxrii=1i系数分别表示自变量的误差经传播变化的倍数。1.5在近似计算中要注意的一些现象一避免两个相近的数相减1例:x二0.3721478693,y=0.3720230572,x*=0.37215,y*二0.37202；则有：x-y=0.0001248121,x*-y*二0.00013那么相对误差为i(x*-y*)-(x一y)曰000013一o.。0012481211.4%.0.0001248121这个相对误差是很大的。2原因分析：如果x和y很接近，它们的差u二x-y就很小，因而u的相对误差就很大。另一方面，从相对误差的公式来看：18*x10-(n-1)r2a1x*和y*的前面几

28、位有效数字相同，相减后有效数字位数会大大减少，致使相对误差增大。解决办法：(1)取近似值时，多保留几位有效数字(上例适用)；(2)有时可以通过变换计算公式，以防止这种现象出现；看下面例子：1例:当X接近于零时，要计算1cosx，应先变换为sinx;sinx1+cosx当x充分大时，要计算农rr-祸，应先变换为1.1+X+X二两个相差很大的数进行运算时，要防止小的那个数被“吃掉”大数“吃掉”小数有些情况是允许的，但有些情况下会造成谬误。为说明这一点，下面举个例子例：计算方程X2(109+1)x+109二0的根.分析：用因式分解法，得(x109)(X1)二0，两根为:X二109,X二1.12如果只

29、能用将数表达到小数点后8位的计算机，按二次方程求根的公式编制程序进行计算，则有b-b2一4acx二1,22a其中，-b=109+1=0.1x1010+0.0000000001x1010，由于只能表达到小数点后8位，故0.0000000001x1010将不起作用(即被吃掉)。因b2一4ac沁b2,b24acMbI解得X=1091X=0.2为避免上面的现象出现，算法上做些处理，取bsign(b)b24ac2a在计算X时利用根与系数的关系式XXc，得这样可以算出aXX=1091X=1.2三要注意计算步骤的简化，减少运算次数计算公式决定计算步骤，计算步骤直接影响计算的速度和误差的积累。下面以计算多项式

30、的值为例来说明简化计算公式的重要性。例:计算多项式p(x)二axn+axn-1+a的值。nn-10分析：若直接计算，计算ax这一项需进行k次乘法运算，共需kk1n(n+1)次乘法运算和n次加法运算，若将公式改写成嵌套形式：P(x)=(ax+a)x+a)x+a)x+ann-1n-210则只要计算n次乘法运算和n次加法运算。四要避免做被除数的绝对值远远大于除数绝对值的除法1.直观认识：用绝对值很小的数去除绝对值很大的数，得到的结果更大，可能上溢，也会增大原有误差，或者使之后的运算有更大的舍入误差，将产生错误结果。2算式分析：|忡5中|令+留2212可以看出，如果Ix|很小，则Id()1将很大TOC

31、 o 1-5 h z2rx23.例子说明：求解二元一次方程组丿O0001x+x=1(1)12x+x=2(2)12分析:-(1)x-，得0.00019998-9999x=-9998nx=229999带入方程组可解得x=竺0.19999而在尾数是3位十进制浮点数字系统中运算，结果将是：-10000 x=-10000,2进一步解得：x=1,x=0(不满足(2)式)。21出现错误的原因：用0.0001作除数增大了参与运算的数，也就增大了舍入误差的量级，从而淹没了真解。令-(2)X0.0001,仍在上述浮点系统中运算，得x=1(这时舍入2误差10_4大小)/进而求得x=1，这很理想。1五选用数值稳定的计

32、算公式1.例子说明：计算I=e-1f1xnexdx,n=1,2，n0分析：由分部积分可以得到I的递推公式：nI=f1xnex-1dx=f1xndex-1=xnex-111-f1ex-1dxn=1-nf1xn-1ex-1dxn00000=1一nI,n=1,2,.n-1I=e一订1exdx=1-e-10.6321=I*1000（注：这里取k=7,用4位小数计算，由Taylor公式:e-1沁1+(-1)+(-1)2/2!+(-1)k/(k!)沁0.3679)用递推公式可以逐个算出近似值I*,但当计算到i*时有：i*=-0.728,n88但从I=e-1f1xnexdx知I都应该为正，I*20288上面的计算中，误差是积累增加的，计算过程中舍入误差不断增长的计算公式称为数值不稳定的。改进方法：选用舍入误差不增长的计算公式，也就是数值稳定的计算公式，直接从积分可以退出e-11，I，n+1nn+1(证：I1+nIn(n+1)I1nIe-111xndx=)n0n+1取n二9，有110e-i10粗略估计可取I沁丄(丄+兰)=0.0684.TOC o 1-5 h z921010又知I=1(1-1),n=9,8