计算方法PPT课件第一章绪论

1,计算方法,1.1计算方法研究的对象和特点计算方法实际上就是计算机上使用的数值计算方法，所以这门课程又称为数值计算方法或数值分析。它是专门研究求解各种数学问题的数值计算方法。现在，由于大多数科学计算都比较复杂，人工计算无法完成；而计算机科学的迅速发展和广泛应用提供了解决这些复杂问题的新途径。用计算机解决科学计算问题的一般过程，可以概括为：实际问题数学模型计算方法程序设计上机计算结果分析,由实际问题应用有关科学知识和数学理论建立数学模型这一过程，通常作为应用数学的任务。而根据数学模型提出求解的计算方法直到编出程序上机算出结果，进而对计算结果进行分析，这一过程则是计算数学的任务，也是数值计算方法的研究对象。因此，数值计算方法就是研究用计算机解决数学问题的数值方法及其理论的科学。它的内容包括：误差理论、线性与非线性方程(组)的数值解、矩阵的特征值与特征向量计算、曲线拟合与函数逼近、插值方法、数值积分与数值微分、常微分方程与偏微分方程数值解等。,2020/5/3,主讲韩光朋,3,2020/5/3,主讲韩光朋,4,计算方法要解决的几个问题：（或研究的对象）,2020/5/3,主讲韩光朋,5,把实际问题归结为数值问题由于电子数字计算机的广泛使用，使越来越多的实际问题能归结为数值问题而得到解决（如：曲线拟合，数值逼近等）。【什么是数值问题呢？所谓数值问题，指的是由一组已知数据（又称输入数据）求出一组结果数据（又称输出数据），使得这两组数据之间满足预先指定的某种关系（函数关系）的问题。（即由一组数求得另一组数）】制定数值问题的算法【什么叫算法？用完全确定的运算规则（包括运算的逻辑顺序），对某一类数值问题的输入数据进行处理，判断此数值问题是否有解，在解存在的情况下，给出输出数据，此种过程称为算法。】,得不到准确解时，设法得到近似解例：求已知数。由数学中的极限理论可知，（极限存在）于是又n只能有限，x是近似值。,6,2020/5/3,主讲韩光朋,在计算方法中，我们还将讨论：解的特性（近似程度，敛散性）各种方法的优缺点（速度，存储量）各种方法的实用范围（收敛范围）,2020/5/3,主讲韩光朋,7,一个好的方法应具有如下特点：第一，面向计算机，要根据计算机特点提供实际可行的有效算法，即算法只能包括加、减、乘、除运算和逻辑运算，是计算机能直接处理的。第二，有可靠的理论分析，能任意逼近并达到精度要求，对近似算法要保证方法的收敛性和数值稳定性，还要对误差进行分析，这些都建立在相应数学理论基础上。第三，要有好的计算复杂性（即时间复杂性和空间复杂性）；时间复杂性好是指节省时间，空间复杂性好是指节省存储量，这也是建立算法要研究的问题，它关系到算法能否在计算机上实现。第四，要有数值实验，即任何一个算法除了从理论上要满足上述三点外，还要通过数值试验证明是行之有效的。,2020/5/3,主讲韩光朋,8,例：一个简单的算法问题，设要对给定的求多项式的值。,9,2020/5/3,主讲韩光朋,一种计算过程是直接计算的每一项后逐项求和，这样要做次乘法和次加法。,10,2020/5/3,主讲韩光朋,另一种算法就是先将变形为如下形式：,再由内层向外层计算，如设：,就可以得到一个递推公式,k=1,2,n(1.3),这样的计算过程只需要计算n次乘法和n次加法。这种算法和上一种算法相比，不仅逻辑结构简单，而且计算也明显地减少了。多项式求值的这种算法称为秦九韶算法（计算框图见图1.2)。,1.2误差的来源及其基本概念1.2.1误差来源：用数值计算方法解决科学技术中的具体问题，一般说都有误差，其来源有下列四种：（注：由于人为的粗心大意造成的计算错误，不算误差）1.模型误差数学描述和实际问题之间的误差如：匀加速运动或自由落体运动公式略去了风力，空气阻力等。2.观察误差如：读表、读尺、读温度计。,2020/5/3,主讲韩光朋,11,3.截断误差如：对x0，求。利用泰勒公式有取其部分和作为，就产生了截断误差。4.舍入误差由于计算机的字长有限，对超过位数的数字要进行舍入，通常取与它们接近的数来表示，由此产生的误差称为舍入误差。例如，我们通常使用2.71828和3.1416来表示的近似值，由此所产生的误差就是舍入误差。,2020/5/3,主讲韩光朋,12,本课程仅讨论后两种误差（截断误差和舍入误差），讨论它们在计算过程中的传播和对计算结果的影响，研制能够控制误差的影响且保证最终结果有足够精度的算法。,2020/5/3,主讲韩光朋,13,1.2.2误差的概念和有效数字,1.绝对误差定义1.1设某数的精确值为，其近似值为，那么与之差称为近似值的绝对误差，简称误差。一般地，某数的精确值是不知道的，因而不能求出，但往往可以估计出它的大小范围，亦即可以确定一个正数，使得此时，称为的绝对误差限。有时也用表示近似值的精确值或精确值的所在范围。,2020/5/3,主讲韩光朋,14,2.相对误差绝对误差反映不了一个近似数的准确程度。如：称一头大象误差十公斤，称一只蚂蚁误差一克，谁的近似程度好，显然大象的近似应好些。于是引进了相对误差。记称为近似值x的相对误差，由于精确值一般不知道，实际计算时通常取作为近似值x的相对误差。若能求出一个正数，使得，则称为近似值x的相对误差限。它是无量纲的数，通常用百分比表示。,2020/5/3,主讲韩光朋,15,例：甲用米尺测量10M长的物体，所产生的绝对误差为2cm，乙用同一米尺测量1M长的物体，所产生的绝对误差为1cm，他们谁的测量精度好？解：根据上述定义可知，甲测量时的相对误差乙测量时的相对误差可见甲测量结果比乙精确。,16,2020/5/3,主讲韩光朋,3.有效数字当准确数的位数很多时，我们常按“四舍五入”原则减少位数，得其近似数。并用“有效数字”来描述它。定义1.2如果近似值的误差限是某一位的半个单位，该位到的第一位非零数字共有位，则称有位有效数字。如果的每一位都是有效数字，则称为有效数。如：，有5位有效数字，有6位有效数字,2020/5/3,主讲韩光朋,17,任何一个实数，经四舍五入后得到的近似值都可以表示为如下标准形式：（其中m可为正负数）,2020/5/3,主讲韩光朋,18,如果其绝对误差限满足,则称近似值具有n位有效数字。,2020/5/3,主讲韩光朋,19,例1设=0.0270是某数经“四舍五入”所得，则误差不超过末位的半个单位，即：又,故该不等式又可写为由有效数字定义可知,有3位有效数字，分别是2,7，0。,2020/5/3,主讲韩光朋,20,例2又,故该不等式又可写为故有3位有效数字，分别是3,2，8。由于中的数字9不是有效数字,故不是有效数。思考：有几位有效数字？,有效数位为3位,有效数位为5位,有效数位为4位,4.有效数字与绝对误差、相对误差有如下关系:若某数的近似值有n位有效数字，那么这个近似值的绝对误差限为（注：由（1.4）式可知：m为整数位，n为小数位）由此看出：当m相同时，n越大，则m-n越小，从而有效位数越多，其绝对误差限越小。数据也就越精确。,2020/5/3,主讲韩光朋,22,用式(1.4)表示的近似数，若具有n位有效数字，则其相对误差限为则至少具有n位有效数字。,2020/5/3,主讲韩光朋,23,反之，若的相对误差限为,证明由知，若x具有n位有效数字，则从而（将上式代入）,24,2020/5/3,主讲韩光朋,（参见1.4式）,反之，若x的相对误差限为所以x至少有n位有效数字。由(2)可以看出，有效位数越多，相对误差限就越小，精确度也就越高。,2020/5/3,主讲韩光朋,25,1.2.3初值误差的传播近似数参加运算后所得到的值也是近似值，含有误差，将这一现象称为误差传播。数值运算中误差的传播情况比较复杂，主要表现在：算法本身可能有截断误差；初始数据在计算机内的浮点表示一般有舍入误差；每次运算一般又会产生新的误差，并且传播以前已经引入的误差。因此，对误差进行准确分析是困难的，但也是很重要的。它关系到一个方法是否稳定,计算结果是否可靠。,2020/5/3,主讲韩光朋,26,误差的传播与积累,例3：蝴蝶效应纽约的一只蝴蝶翅膀一拍，风和日丽的北京就刮起台风来了？！,NY,BJ,以上是一个病态问题,1.3选用和设计算法应注意的问题一般衡量算法的标准有：算法是否稳定，算法的运算次数和算法的存储量是否尽量少，同时还要考虑误差的传播等。选用和设计算法应注意如下几个问题:选用数值稳定的计算公式防止两个相近数相减防止大数“吃掉”小数简化计算步骤，减少运算次数,2020/5/3,主讲韩光朋,28,1.3.1选用数值稳定的计算公式如果数值算法的计算舍入误差积累是可以控制的，则称其为数值稳定的；反之，称为数值不稳定的。例：计算定积分（序列）利用分部积分法不难求得递推关系式为,2020/5/3,主讲韩光朋,29,公式推导,由式（1.16）可依次算出如下结果：(p011.c),2020/5/3,主讲韩光朋,30,注意到（注：从积分中按x的最小和最大值提出ex)?,(1.17),由上面的不等式可以看出,因此按递推关系式（1.16）所算出的计算值是错误的，严重偏离其准确值。发生这种现象的原因是因为本身有不超过的误差。设是具有精确初始值，并按式（1.16)计算而得的，则有由此可见，初始值微小的误差会随着计算步数的增加而迅速扩大，最终使计算结果失真。故算法式（1.16)不能控制误差的传播，是数值不稳定的。,2020/5/3,主讲韩光朋,31,如果将式（1.16）改写为,2020/5/3,主讲韩光朋,32,（1.18),又注意到,结合式（1.17）得,由上面的估计式取,开始按式（1.18）计算，有如下结果：（p012.c),2020/5/3,主讲韩光朋,33,由此可以看出按递推关系式（1.18）算出的与结果相差无几，已精确到小数点后第四位。分析误差的传播，则有,这表明，随着计算步骤的增加，初始误差可以得到控制，于是可知算法（1.18）式是数值稳定的。,公式推导,1.3.2防止两个相近数相减在数值计算中若有两个相近的数相减，则这两个数的前几位相同的有效数字会在它们之差中消失，从而使有效数字的位数减少。如果遇到两个相近的数相减运算，可考虑对公式进行处理，避免减法。例如，当很大时，下两式应作如下处理：,34,2020/5/3,主讲韩光朋,35,2020/5/3,主讲韩光朋,1.3.3绝对值太小的数不宜作除数算法语言中已讲过，在机器上若用很小的数作除数会溢出停机，而且当很小的数稍有一点误差时，对计算结果影响很大。例如：,1.3.4防止大数“吃掉”小数例：设a=63281312，b=0.1，c=0.9，求a,b,c之和。如果按（a+b)+c次序来编制程序，此时按照加法浮点运算的对阶规则，应有,2020/5/3,主讲韩光朋,36,在八位的计算机上计算时，上式后面的两个数在计算机上变为了“机器零”，被“吃掉”。其结果为63281312。如果改变计算次序为（b+c)+a，则有（0.10.9）6328131216328131263281313。这样就避免了小数被大数“吃掉”的现象。,1.3.5简化计算步骤，减少运算次数对于同一个问题的计算，可以有不同的计算方法，如计算的值，如果逐个相乘，则要计算254次乘法；但如果写成只要做14次乘法运算就可以完成。由此可见，如果方法选择得当，则不仅能减