计算方法与误差.ppt

,计算方法课程用途,.1 引言,我们每学习一门新课，首先总要大体了解一下为什么要开这门课，在这门课程中我们将要学习什么内容，怎样把这门课学好，学好这门课的标志是什么等等。,计算方法是怎样一门课？它的重要性表现在什么地方？用学习数学的方法就能学好计算方法吗？,用计算机解决实际问题的一般步骤是：,前三步为建模，集中于问题及其解法或算法，与任何特定的计算机或计算机语言无关。后两步为模型求解，集中于选择某一种程序设计语言，把算法表达给特定的计算机。,广义地说，为解决一个问题而采取的方法和步骤，就称为“算法”。,数学模型概述,从现实对象到数学模型我们常见的模型玩具、照片、飞机、火箭模型 能够实际潜水的小潜水艇 地图、电路图、分子结构图,实物模型,物理模型,符号模型,模型是为了一定目的，对客观事物的一部分进行简缩、抽象、提炼出来的原型的替代物,模型集中反映了原型中人们需要的那一部分特征,你碰到过的数学模型“航行问题”,用 x 表示船速，y 表示水速，列出方程：,答：船速每小时20千米/小时.,甲乙两地相距750千米，船从甲到乙顺水航行需30小时，从乙到甲逆水航行需50小时，问船的速度是多少?,x=20y=5,数学模型概述,航行问题建立数学模型的基本步骤,作出简化假设（船速、水速为常数）；,用符号表示有关量（x,y表示船速和水速）；,用物理定律（匀速运动的距离等于速度乘以 时间）列出数学式子（二元一次方程）；,求解得到数学解答（x=20,y=5）；,回答原问题（船速每小时20千米/小时）。,数学模型概述,数学模型(Mathematical Model)和 数学建模（Mathematical Modeling),对于一个现实对象，为了一个特定目的，根据其内在规律，作出必要的简化假设，运用适当的数学工具，得到的一个数学结构。,建立数学模型的全过程（包括表述、求解、解释、检验等）,数学模型,数学建模,数学模型的概念,应用领域,人口、交通、经济、生态、医学,数学方法,初等数学、微分方程、规划、统计,表现特性,描述、求解、预报、决策,建模目的,了解程度,白箱,灰箱,黑箱,确定和随机,静态和动态,线性和非线性,离散和连续,数学模型的分类,建立数学模型的方法与步骤,调查研究,模型假设,建立数学模型的方法与步骤,了解实际背景,明确建模目的,搜集有关信息,掌握对象特征,形成一个比较清晰的问题,针对问题特点,作出合理的、简化的假设,建立模型,用数学的语言、符号描述问题,模型求解,各种数学方法、软件和计算机技术,模型检验,模型应用,与实际现象、数据比较，检验模型的合理性、适用性,建立数学模型案例,例：有人借助英文词汇建立了一个用算法表述生活圆满程度的数学模型：1）将A、B、C、D、E、X、Y、Z这26个英文字母，分别对应百分数1%、2%、26%这26个数值2）对每一个英文词包含的字母进行对应百分数相加得到 该词的权重数，称其为生活圆满度。,用这个数学模型,可算出人们所追求的生活圆满度百分比数:,MONEY(金钱)：M+O+N+E+Y=13+15+14+5+25=72%,LEADERSHIP(权利)：L+E+A+D+E+R+S+H+I+P=97%,LOVE(爱情)：L+O+V+E=12+15+22+5=54%,ATTITUDE(态度)：A+T+T+I+T+U+D+E=1+20+20+9+20+21+4+5=100%,1.对于要解决的问题建立数学模型2.研究用于求解该数学问题近似解的算法和过程3.按照2进行计算，得到计算结果,换句话说,程序设计方法首先强调的是设计，其次才是实现（写出程序代码）。其核心是将程序设计过程分为两部分。第一部分集中于问题及其解法或算法，与任何特定的计算机或计算机语言无关。第二部分集中于选择某一种程序设计语言，把算法表达给特定的计算机。,程序设计方法,算法的概念,广义地说，为解决一个问题而采取的方法和步骤，就称为“算法”。你想查看计算机CPU，首先必须将计算机断电，拆除连线，打开机箱，然后按下夹子解除夹口，最后取出CPU进行查看。复制文件，首先要寻找所要复制的文件，然后选中，再进行复制，最后移动到需要的地方进行粘贴。,算法的分类：本书所讲述的算法只限于计算机算法，即计算机能执行的算法。计算机算法可分为两大类别：数值运算算法和非数值运算算法。数值运算的目的是求数值解，例如求方程的根，求一个函数的定积分等，都属于数值运算范围。非数值运算包括的面十分广泛，最常见的是用于事务管理领域，例如图书检索、人事管理等。目前，计算机在非数值运算方面的应用远远超过了在数值运算方面的应用。,开计算方法这门课的重要意义,.1 引言,计算方法是用数学方法借助计算机解决实际问题，侧重点是求模型的数值解。通过对一些典型的数学问题的研究形成常用的求解方法体系，是为解决实际问题奠定基础。,实际上，计算方法是数学方法的伸延，数学教科书中的遗留问题。在我们这里就可得到解决,计算方法是求解数学问题的计算机方法,计算方法研究对象,.1 引言,由数学模型找到求解方法的过程，是计算方法要研究的核心问题。,计算方法所面对的正是“模型求解”，或者说求模型的数值解。因此我们不能把“计算方法”理解为“计算”的“方法”，而应理解为借助计算机求解复杂数学问题的基本方法。,计算方法研究对象,研究对象：数值问题有限个输入数据（问题的自变量、原始数据）与有限个输出数据（待求解数据）之间函数关系的一个明确无歧义的描述。,如一阶微分方程初值问题,1.求方程 2x2+8x 3=0 在 0,1 上的根 x*2.求解线性方程组Ax=b，其中A为3阶可逆方阵 x=(x1,x2,x3)T 3.已知y=P(x)为x0,x1上的直线,满足 P(x0)=y0,P(x0)=y0 求x*x0,x1）求P(x*)4.计算定积分 5.解常微分方程初值问题,计算问题,目的明确:算法必须有明确的目的,其条件和 结论均应有清楚的规定,算法有四个特点,2.定义精确：对算法的每一步都必须有精确的定义,3.算法可执行：算法中的每一步操作都是可执行的,4.步骤有限：算法必须在有限步内能够完成 解题过程,1.2 误差的来源及分类,1.2.1 误差具有必然性与重要性,（1）某些问题不存在严谨的求解方法,（2）某些严谨的求解方法实际上不可行,（3）由观测得到的原始数据，必然有误差,（4）蝴蝶效应如果误差太大，求得的 解就没有意义了。,1.2.2 误差的来源,（1）模型误差,（2）观测误差,（3）截断误差（方法误差）,（4）舍入误差（计算误差）,科学计算中所处理的数据和计算的结果通常都是在一定范围内的近似值，它们与实际的真实值之间存在着误差。也就是说，一个物理量的真实值和我们算出的值往往不相等，其差值称为误差。误差的来源有下面几种,客观量的准确值与数学模型的准确解的差 模型误差,由观测数据而产生的误差 观测误差,(方法误差)数学模型的准确解与利用近似计算方法得到的解之差 截断误差,由于将数据进行舍入而产生的误差 舍入误差,由于问题不能精确求解，近似计算的方法所引起误差称为截断误差，这是计算方法本身出现的误差，故又称为方法误差例1.3 函数f(x)用泰勒(Taylor)多项式,（介于0与x之间）,近似代替，则数值方法的截断误差是,截断误差的大小直接影响计算结果的精度和计算 工作量，是数值计算中必须考虑的一类误差,1.2.3 截断误差,当e*0时，x*称为弱近似值，当e*0时，x*称为强近似值|e*|越小，x*的精度越高,1.3 误差的度量,1.3.1 绝对误差和绝对误差限,定义1.1(绝对误差)设 为真值（准确值），为 的一个近 似值，称 为近似值 的绝对 误差，简称误差。,由于精确值一般是未知的,因而e*不能求出来,但可以根据测量误差或计算情况设法估计出它的取值范围，即误差绝对值的一个上界或称误差限。,实际应用中经常使用这个量来衡量误差限,这就是说,如果近似数 的误差限为,则，表明准确值 x 必落在 上,常采用下面的写法,来表示近似值的精度或准确值x所在的范围。,例1.6 而近似值x*=3.1415，它的绝对误差是 0.0000926，误差限 x-x*=0.0000926 0.0001=0.110-3,可见，绝对误差限*不是唯一的，但*越小越好,1.3.2 相对误差和相对误差限,只用绝对误差还不能说明数的近似程度,例如甲打字每100个错一个,乙打字每1000个错一个,他们的误差都是错一个,但显然乙要准确些,这就启发我们除了要看绝对误差外,还必须顾及量的本身。,相对误差越小,精度就越高,实际计算时,x 通常是不知道的,通常用下列公式计算相对误差,解：根椐定义:甲打字时的相对误差,例1.7 甲打字每100个错一个，乙打字每1000个 错一个，求其相对误差,乙打字时的相对误差,则称 为x的具有n位有效数字的近似值，准确到第n位，是 的有效数字。,1.3.3 有效数字,解：3.141592=0.3141592 3.142=0.3142 m=1|-3.142|=|0.3141592-0.3142|0.000041 0.0005=m n=1n=-3,例1.8 3.142作为的近似值时有几位有效数字,所以 n=4，具有4位有效数字,-3.141=0.3141592101-0.3141101 0.0000592 101 0.0005 101 0.005=1/2 10-2 m-n=1-n=-2 所以n=3具有3位有效数字,例1.9 当取3.141作为的近似值时,-3.1416=0.3141592101-0.31416101 0.00000074 101 0.00000740.00005 0.5 10-4 m-n=1-n=-4 所以 n=5x*=3.1416有5位有效数字,例1.10 当取3.1416作为的近似值时,定义1.5若近似值x*的绝对误差限是某一位上的半个单位，则说 x*精确到该位，若从该位到 x*的左面第一位非零数字一共有n位，则称近似值x*有n位有效数字。准确数有无穷多位有效数字.,如例1.10 用3.1416作为的近似值,有几位有效数字?,=3.14159265,x*=3.1416,|-3.1416|=0.0000073 0.00005=0.510-4因此近似值精确到10-4,有5位有效数字.,定理1.1 若近似数x*=0.x1x2xn10m具有 n 位 有效数字，则其相对误差,1.3.4 有效数字与相对误差,证:x*=0.x1x2xn10m x*x110 m-1 又 x*具有n位有效数字,则,一般应用中可以取r*=1/2x1 10-(n-1),n越大,r*越小,有效数字越多，相对误差就越小例1.12 取3.14作为的四舍五入的近似值时，求其相对误差解：3.14=0.314 101 x1=3 m=1 四舍五入的近似值,其各位都是有效数字 n=3,例1.14 已知近似数x*有两位有效数字，试求其相 对误差限解：已知 n=2 代入公式 得 x*的第一位有效数字x1没有给出，可进行如下讨论：当 x1=1=5%x1=9=0.56%取 x1=1 时相对误差为最大，即 5%,定理1.2 若近似数x*=0.x1x2xn10m相对误差 则该近似数具有n位有效数字,由有效数字定义可知,x*具有n位有效数字。证毕,证:x*=0.x1 x2 xn 10m x*(x1+1)10m-1,例1.14 已知近似数x*的相对误差限为0.3%，问x*有几位有效数字？,当x1=1时,310-3=1/410-(n-1)1210-3=10-(n-1)上式两边取以10为底的对数得 lg22+lg3+(-3)=-n+1 lg2=0.3010 lg3=0.4771 20.3010+0.4771-4=-n n=2.9209 当x1=9时,310-3=1/2010-(n-1)610-3=10-n 上式两边取以10为底的对数得 lg2+lg3+(-3)=-n n=2.2219 x*至少有3位有效数字,例1.16 为使 的近似数的相对误差小于0.1%，问查开方表时，要取几位有效数字？,解：8 9 x1=8,-(n-1)2.7448 取 n=3 即查平方表时 8.37 取三位有效数字,注意:已知有效数字,求相对误差用公式,已知相对误差,求具有几位有效数字公式,介于x,x*之间,1.4 数值运算的误差估计,1.4.1 函数运算误差,设一元函数f(x)具有二阶连续导数，自变量x的一个近似值为x*，f(x*)作为f(x)近似,我们用Taylor展开的方法来估计其误差。即有,其中*为近似数x*的绝对误差限，设与 相差不大,可忽略*的高次项,于是可得出函数运算的误差和相对误差,多元函数亦类似，用泰勒展开即可推导出来,即,如果 是n元函数，自变量 的近似值分别为则,其中,所以可以估计到函数值的误差界，,两个变量,(d*)=0.1m,(L*)=0.2m绝对误差限(s*)(800.2+110 0.1)m2=27m2,例1.16 已测得某场地长L的值L*=110m,宽d的值 d*=80m,已知 L-L*0.2m,d-d*0.1m 求场地面积S=Ld的绝对误差限和相对误差限,其中,相对误差限,解：,例1.17 正方形的边长约为100cm,怎样测量才能使其 面积误差不超过1cm2?,解：设正方形边长为x cm,测量值为x*cm,面积 由于,记自变量和函数的绝对误差分别是e*、e(y*),则 e*=x-x*,现要求 e(y*)200e*1,于是 e*（1/200）cm=0.005cm 要使正方形面积误差不超过1cm2，测量边长时绝对误差应不超过0.005cm。,（1）要避免相近两数相减,当x1,可化,例,(2)要防止大数“吃掉”小数,注意保护重要数据,例,1.5 减少运算误差原则,(3)要避免绝对值小的数作除数,当x接近于0时,可化,当x1 时，可化,（4）简化计算步骤，减少运算次数 原先要做254次乘法现只需14次即可,例1.19 计算积分 并估计误差,1.6 控制递推公式中误差的传播,对于一个数学问题的求解往往有多种数值方法在选择数值方法时，要注意所用的数值方法不应将计算过程中难以避免的误差放大的较快，造成计算结果完全失真。,解 容易得到递推公式,即 为,则准确的理论递推式 实际运算的递推式 两式相减有,这就是说,若 与 的误差为=-,即，则误差的递推规律为,于是,计算 时的误差被扩大了 倍,显然算法是数值不稳定的。如果将递推公式 变换一种形式,准确的理论递推式实际运算的递推式,即,于是有,则这个算法的误差传递规律为,即每计算一步的误差的绝对值是上一步的十分之一，误差的传播逐步缩小，得到很好的控制，这个算法是数值稳定的,从而有,例1.19 蝴蝶效应 纽约的一只蝴蝶翅膀一拍，风和日丽的北京就刮起台风来了？！,纽约,北京,这是一个病态问题,关于蝴蝶效应,返回,本章小结,误差在数值计算中是不可避免的，误差的传播和积累直接影响到计算结果的精度。在研究算法的同时，必须注重误差分析，使建立起来的算法科学有效。按照误差产生的来源可分为模型误差、观测误差，截断误差、和舍入误差等。误差的表示法有绝对误差和相对误差两种。在表示一个近似数时,要用到有效数字的概念,这在数值计算中非常有用,有效数字是由绝对误差决定的 通常用函数的泰勒展开对误差进行估计,