第一章 数值计算引论,数值计算方法就是要解决如何让计算机计算 数值( 如解方程、解方程组、求积分等 )不仅算得 快（用的机时少）、而且也要算得准（ 与真实值 的误差小) 的问题。如果光算得快 , 算得不准 ( 超 过了误差范围),计算出来的结果不能用, 计算也就 没有什么意义。如何才能让计算机既算得快又算 得准（误差达到最小）呢？这就需要掌握一些误 差知识。,本章介绍的内容,）数值计算方法的含义及其特点； ）误差的来源； ）误差的有关概念（绝对误差、相对误差、有 效数字）； ）误差的传播过程； ）算法的数值稳定性概念； ）选用数值算法的若干原则。,第一节 数值计算方法研究的对象、内容及特点,数值计算方法是应用数学的一个分支,又称数值分析或计算方法,它是研究用计算机求解各种数学问题的数值方法及其理论的一门学科,是程序设计和对数值结果进行分析的依据和基础。 我们知道，用计算机解决科学计算问题需要经过以下几个过程：提出具体问题,建立数学模型，选用数值计算方法，程序设计、上机调试直至得出最终数值结果。可见,选用数值计算方法是应用计算机进行科学计算全过程的一个重要环节。,数值计算方法特点,（1）面向计算机。根据计算机特点提供实际可行的有效算法。即算法只能包括加、减、乘、除和逻辑运算，是计算机所能直接处理的。 （2）有可靠的理论分析。能任意逼近并达到精度要求，对近似算法要保证收敛性和数值稳定性，还要对误差进行分析。有相应的数学理论做基础。 （3）有好的计算复杂性（包括空间复杂度和时间复杂度）。算法需占用的存储空间要小，运算次数要少。这也是建立算法要研究的问题，它关系到算法能否在计算机上实现。,第二节 误差,用计算机解决科学计算问题通常经历以下过 程： 据此误差的来源主要有以下四类。,实际问题,数学模型,数值计算方法,程序设计,上机计算结果,（一）建模误差,在将实际问题转化为数学模型的过程中，为 了使数学模型尽量简单，以便于分析或计算，往 往要忽略一些次要的因素，进行合理的简化。这 样，实际问题与数学模型之间就产生了误差，这 种误差称为模型误差。由于这类误差难于作定量 分析，所以在计算方法中，总是假定所研究的数 学模型是合理的，对模型误差不作深入的讨论。,（二）观测误差,在数学模型中，一般都含有从观测（或 实验）得到的数据，如温度、时间、速度、 距离、电流、电压等等。但由于仪器本身的 精度有限或某些偶然的客观因素，会引入一 定的误差，这类误差叫做观测误差。通常根 据测量工具或仪器本身的精度，可以知道这 类误差的上限值，所以无需在数值分析中作 过多的研究。,当数学模型得不到精确解时，要用数 值计算方法求它的近似解，由此产生的误 差称为截断误差或方法误差。譬如在数值 计算中，常用收敛的无穷级数的前几项来 代替无穷级数进行计算，即抛弃了无穷级 数的后段，这样就产生了截断误差。,（三）截断误差（方法误差）,（四）舍入误差,由于计算机字长有限，原始数据的输入及浮点运 算过程中都可能产生误差。而事实上，无论用电子计 算器计算还是笔算，都只能用有限位小数来代替无穷 小数或用位数较少的小数来代替位数较多的有限小数 ，这样产生的误差叫做舍入误差。在数值计算中，往 往要进行成千上万次四则运算，因而就会有成千上万 个舍入误差产生，这些误差一经叠加或传递，对精度 可能有较大的影响。所以，作数值计算时，对舍入误 差应予以足够的重视。,小 结,上述四类误差都会影响计算结果的准确性， 但模型误差和观测误差往往需要会同各有关学科 的科学工作者共同研究, 因此在计算方法课程中, 主要研究截断误差和舍入误差（包括初始数据的 误差）对计算结果的影响。,一、绝对误差和绝对误差限,定义1 假设某一量的准确值为x ，近似值为x*, 则 x与x*之差叫做近似值x*的绝对误差（简称误差），记 为(x)，即 (x)= xx* |(x)的大小标志着x*的精确度。一般地，在同一 量的不同近似值中,(x)越小，x*的精确度越高。 当(x)较小时，由微分和增量的关系知x*的绝对 误差(x)dx ，故我们可以利用微分估计误差。,绝对误差限的概念,由于准确值x一般不能得到，于是误差的准确值也无法求得， 但在实际测量计算时，可根据具体情况估计出它的大小范围。也 就是指定一个适当小的正数，使 |(x)|= |xx* | 我们称为近似值x*的绝对误差限。 有时也用 x = x* 表示近似值的精度或准确值的所在范围。 在实际问题中，绝对误差一般是有量纲的。例如，测得某一 物体的长度为5m，其误差限为0.01m，通常将准确长度记为 =5 0.01 即准确值在5m左右，其误差限为0.01m的误差限。,相对误差的概念,定义2 我们把绝对误差与准确值之比 r(x)= (x)/x=(xx*)/x， x0 称为x*的相对误差。 由于准确值x往往是不知道的，因此在 实际问题中，当|r(x)|较小时，常取 r(x)= (x) /x* 一般地，在同一量或不同量的几个近似值中， |r(x)|小者精确度高。,相对误差限的概念,在实际计算中, 由于(x)与x都不能准 确地求得,因此相对误差 r(x)也不可能准确 地得到, 我们只能估计它的大小范围。即指 定一个适当小的正数，使 |r(x)|= |(x)|/| x* | 称为近似值x*的相对误差限。 当|r(x)|较小时，可以用下式来计算： =/|x*|,三、有效数字,为了既能表示近似数的大小，又能表示近似数的精确程度，我们下面介绍有效数字的概念（注意：有效数字既能表示近似数的大小，又能表示近似数的精确程度）。,半个单位的概念,为了理解有效数字的概念,首先要弄清什么是半个单位。 我们知道，当x有很多位数字时，常常按照“四舍五入”原则取前几位数字作为x的近似值x*。 例1 设 x = = 3.1415926 取x1*=3作为的近似值,则|1(x)|=0.1415 0.5100； 取x2*=3.14，则|2(x)|=0.00159 0.510-2； 取x3*=3.1416, 则|3(x)|=0.0000074 0.510-4 。 它们的误差都不超过末位数字的半个单位。,有效数字的概念,定义3 若近似值x*的绝对误差限是某一位上的半个单位，该位到x*的第一位非零数字一共有n位，则称近似值x*有n位有效数字，或说x*精确到该位。 准确数本身有无穷多位有效数字，即从第一位非零数字以后的所有数字都是有效数字。,有效数字举例,如例1中的x*1，x*2 ,x*3,分别有1,3,5位有效数字。 实际上，用四舍五入法取准确值x 的前n位（不包括第一位非零数字前面的零）作为它的近似值x*时，x*有n位有效数字。 例2 设 x = 4.26972，则按四舍五入法，取2位，x1*=4.3有效数字为2位,取3位，x2*=4.27,有效数字为3位，取4位，x3*=4.270，有效数字为4位。,特别注意,近似值后面的零不能随便省去， 如例2中4.27和4.270，前者精确到4.27,有效数字为3位，取4位，x3*=4.270,有效数字为4位。可见,它们的近似程度完全不同, 与准确值的最大误差也完全不同。,有效数字和绝对误差的关系,定义3换一种说法就是：设x的近似值 x*= 0.a1a2 an 10p 若其绝对误差 |(x)|=|xx*| 0.5 10p-n 则称近似数x*具有n 位有效数字。这里p为整数，a1 , a2 , , an 是0 到9中的一个数字且a10 。 例如，若x*=0.2315610-2是x 的具有五位有效数字的近似 值，则绝对误差是 |xx*| 0.5 10-2-5 = 0.5 10-7 定义3或式 |(x)|=|xx*| 0.5 10p-n 建立了绝对误差(限)和有效数字之间的关系。由于n 越大，10p-n 的值越小，所以有效数字位越多，则绝对误差(限)越小。,有效数字与相对误差的关系,定理1 若近似数x*具有n位有效数字，则 其相对误差为 |r(x)| 1/(2a1) 10-(n-1) 其中a10是x*的第一位有效数字。 定理1说明有效数字位越多,相对误差(限)越小。 定理2 形式如x*= 0.a1a2 an 10p的近似数 x*，若其相对误差满足 |r(x)| 1/2(a1+1) 10-(n-1) 则x* 至少有n位有效数字。 由此可知，有效数字位数可刻画近似数的精 确度，相对误差(限)与有效数字的位数有关。,有效数字与相对误差关系举例,注意从 并不能保证x*一定具有n位有效数字。 如 x=sin29020=0.4900 设其近似值 x*=0.484 , 其相对误差为 我们不能由此推出x*有两位有效数字，这是因为 x-x*=0.4900-0.484=0.00600.005 即可知近似值x*并不具有两位有效数字。 实际上, x*只有一位有效数字。,|r(x)| 1/(2a1) 10-(n-1),数值运算中误差的影响,要分析数值运算中误差的传播，首先就要估 计数值运算中的误差。数值运算的误差估计情况 较复杂, 通常利用微分来估计误差。,二元函数 设数学问题的解y与变量x1 , x2有关, y=f(x1,x2)。若 x1,x2的近似值为x1*, x2*,相应解为y*,则当数据误差较 小时解的绝对误差 (y)=yy*=f(x1,x2 )f(x1*,x2* ) dy=f (x1,x2 )/x1*(x1)+f (x1,x2 )/x2*(x2) 解的相对误差 r(y) dy/y =f (x1,x2 )/xi*xi/ f (x1,x2 )*r(xi) (i=1,2) 利用这两式可得到两数和、差、积、商的误差估 计。,一、算法的数值稳定性概念,所谓算法，是指对一些数据按某种规定的顺序 进行的运算序列。在实际计算中，对于同一问题我 们选用不同的算法, 所得结果的精度往往大不相同。 这是因为初始数据的误差或计算中的舍入误差在计 算过程中的传播，因算法不同而异，于是就产生了 算法的数值稳定性问题。一个算法, 如果计算结果 受误差的影响小，就称这个算法具有较好的数值稳 定性。否则，就称这个算法的数值稳定性不好。,算法的数值稳定性概念举例,例1 一元二次方程 X2+2pX +q=0 的两个根分别是： x1= p+(p2q)0.5，x2= p(p2q)0.5 当p= 0.5105,q=1时，方程的两个根取11位有效数字为： x1=99999.999990 , x2=0.000010000000001 在高精度的计算机(进制=10,字长t=8,浮点阶码下限L= 50, 浮点阶码上限U=50)上直接用上述公式计算的结果为： x1=100000.00, x2=0 可见，结果x1很好，而x2很不理想，这说明直接用上述公式 计算第二个根是不稳定的，其原因在于在计算x2时造成相近两数 相减，从而使有效数字严重损失。请看下面的求解方法。,一元二次方程 X2+2pX +q=0的求解方法,根据根与系数的关系可知 x1x2=q=1 所以 x2=1/x1 因此，如果仍用上述方法算出x1，然后用 x2=1/x1 计算x2，可得 x1=100000.00，x2=0.00001000 该结果是非常好的。这就说明这种算法有较好的数值稳 定性。 一般说来，当|p|q|时，用公式x1= psign(p)(p2q)0.5 , x2=q/x1来求解方程 X2+2pX+q=0 是数值稳定的。 从而可知，算法数值稳定性的讨论甚为重要。,二、设计算法的若干原则,为防止误差使计算结果失真(失常）现 象发生，要选用数值稳定的计算公式，以 保证算法的数值稳定性。下面我们给出设 计算法的若干原则，并给出改善算法的例 子