第一章数值计算方法与误差分析.ppt

《第一章数值计算方法与误差分析.ppt》由会员分享，可在线阅读，更多相关《第一章数值计算方法与误差分析.ppt（53页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第一章第一章 数值计算引论数值计算引论数值计算方法就是要解决如何让计算机计算数值(如解方程、解方程组、求积分等)不仅算得快（用的机时少）、而且也要算得准（与真实值的误差小)的问题。如果光算得快,算得不准(超过了误差范围),计算出来的结果不能用,计算也就没有什么意义。如何才能让计算机既算得快又算得准（误差达到最小）呢？这就需要掌握一些误差知识。本章介绍的内容）数值计算方法的含义及其特点；）误差的来源；）误差的有关概念（绝对误差、相对误差、有效数字）；）误差的传播过程；）算法的数值稳定性概念；）选用数值算法的若干原则。第一节第一节 数值计算方法数值计算方法数值计算方法是应用数学的一个分支,又称数值

2、分析或计算方法,它是研究用计算机求解各种数学问题的数值方法及其理论的一门学科,是程序设计和对数值结果进行分析的依据和基础。我们知道，用计算机解决科学计算问题需要经过以下几个过程：提出具具体体问问题题,建立数数学学模模型型，选用数数值值计计算算方方法法，程程序序设设计计、上上机机调试直至得出最终数值结结果果。可见,选用数值计算方法是应用计算机进行科学计算全过程的一个重要环节。数值计算方法特点（1）面向计算机面向计算机。根据计算机特点提供实际可行的有效算法。即算法只能包括加、减、乘、除和逻辑运算，是计算机所能直接处理的。（2）有可靠的理论分析有可靠的理论分析。能任意逼近并达到精度要求，对近似算法要

3、保证收敛性和数值稳定性，还要对误差进行分析。有相应的数学理论做基础。（3）有好的计算复杂性（包括空间复杂度和有好的计算复杂性（包括空间复杂度和时间复杂度）。时间复杂度）。算法需占用的存储空间要小，运算次数要少。这也是建立算法要研究的问题，它关系到算法能否在计算机上实现。第二节第二节 科学计算中误差的来源科学计算中误差的来源用计算机解决科学计算问题通常经历以下过程：据此误差的来源主要有以下四类。实际问题实际问题数学模型数学模型数值计算方法数值计算方法程序设计程序设计上机计算结果上机计算结果（一）模型误差（一）模型误差在将实际问题转化为数学模型的过程中，为了使数学模型尽量简单，以便于分析或计算，往

4、往要忽略一些次要的因素，进行合理的简化。这样，实际问题与数学模型之间就产生了误差，这种误差称为模型误差。由于这类误差难于作定量分析，所以在计算方法中，总是假定所研究的数学模型是合理的，对模型误差不作深入的讨论。（二）观测误差（二）观测误差在数学模型中，一般都含有从观测（或实验）得到的数据，如温度、时间、速度、距离、电流、电压等等。但由于仪器本身的精度有限或某些偶然的客观因素，会引入一定的误差，这类误差叫做观测误差。通常根据测量工具或仪器本身的精度，可以知道这类误差的上限值，所以无需在数值分析中作过多的研究。当数学模型得不到精确解时，要用数值计算方法求它的近似解，由此产生的误差称为截断误差或方法

5、误差。譬如在数值计算中，常用收敛的无穷级数的前几项来代替无穷级数进行计算，即抛弃了无穷级数的后段，这样就产生了截断误差。（三）截断误差（方法误差）（三）截断误差（方法误差）截断误差举例例如sinx=xx3/3!+x5/5!x7/7!+,x 0.005即可知近似值x*并不具有两位有效数字。实际上,x*只有一位有效数字。|r(x)|1/(2a1)10-(n-1)第四节第四节 数值运算中误差的传播数值运算中误差的传播要分析数值运算中误差的传播，首先就要估计数值运算中的误差。数值运算的误差估计情况较复杂,通常利用微分来估计误差。一、利用微分估计误差一、利用微分估计误差1.一元函数一元函数设y=f(x)

6、为一元函数，则计算函数值的误差为(y)=yy*=f(x)f(x*)dy=f(x)dxf(x)(x)解的相对误差r(y)dy/y一元函数的误差估计举例例正方形的边长约为100cm,怎样测量才能使其面积误差不超过1cm2。解设正方形的边长为xcm,测量值为x*cm,面积y=f(x)=x2f(x)=2x(y*)=y-y*dy*=f(x*)dx*f(x*)(x*)f(x*)(x*)=2x*(x*)=200(x*)由于|(y*)|1即|200(x*)|1所以，(x*)0.005cm2.二元函数二元函数设数学问题的解y与变量x1,x2有关,y=f(x1,x2)。若x1,x2的近似值为x1*,x2*,相应解

7、为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)利用这两式可得到两数和、差、积、商的误差估计。二、和差误差估计二、和差误差估计设y=f(x1,x2)=x1+x2，利用式(y)=yy*=f(x1,x2)f(x1*,x2*)dy=f(x1,x2)/x1*(x1)+f(x1,x2)/x2*(x2)可得(x1+x2)(x1)+(x2)|(x1+x2)|=|(x1)+(x2)|(x1)|+|

8、(x2)|因此，任何两个数之和的绝对误差等于两个数的绝对误差之任何两个数之和的绝对误差等于两个数的绝对误差之和，任何两个数之和的绝对误差限为这两个数的绝对误差限之和，和，任何两个数之和的绝对误差限为这两个数的绝对误差限之和，且可推广到有限多个数相加的情形。且可推广到有限多个数相加的情形。所以作大量加减运算后的绝对误差是绝不可以忽视的。由于加法和减法是互为逆运算关系，所以减法可以化为加法情形讨论。两数之和的相对误差利用式r(y)dy/y=f(x1,x2)/xi*xi/f(x1,x2)*r(xi)(i=1,2）可得两个数之和的相对误差为r(x1+x2)=x1/(x1+x2)*r(x1)+x2/(x

9、1+x2)*r(x2)当x1和-x2相当接近时x1+x20，|x1/(x1+x2)|和|x2/(x1+x2)|都将很大，所以相近两数之差的相对误差将很大，即原始数据的误差会对计算结果产生很大的影响。和差误差估计举例例1用四位有效数字计算y=的值。解如果直接计算，则y=31.6431.62=0.02由于y的准确值是0.0158074374，可见直接计算所得的近似值仅有一位有效数字,其相对误差大于26%。若作适当变形后计算，可以避免相近两数相减的计算。如y=1/63.260.01581所得结果与准确值比较可知具有四位有效数字，其相对误差不超过0.02%。所以在数值计算中，必须避免相近两数相减。以免

10、损失有效数字的位数。三、积商误差估计三、积商误差估计利用微分可得两数积的绝对误差为(x1x2)d(x1x2)x2(x1)+x1(x2)相对误差为r(x1x2)=(x1x2)/(x1x2)r(x1)+r(x2)两数商的绝对误差为(x1/x2)d(x1/x2)x2(x1)-x1(x2)/x22(x20)相对误差为r(x1/x2)=(x1/x2).x2/x1r(x1)-r(x2)(x20)从而得出：两数乘积的相对误差，可看作是各乘数的相对误差之和；两数乘积的相对误差，可看作是各乘数的相对误差之和；两数商的相对误差，可看作是被除数与除数的相对误差之差。两数商的相对误差，可看作是被除数与除数的相对误差之

11、差。上述误差积累规律，对多个近似数的运算也是成立的。通常，任意多次连乘连除所得结果的相对误差限，可看作是各乘数和除数的相对误差限之和。第五节第五节 算法的数值稳定性算法的数值稳定性一、算法的数值稳定性概念一、算法的数值稳定性概念所谓算法算法，是指对一些数据按某种规定的顺序进行的运算序列。在实际计算中，对于同一问题我们选用不同的算法,所得结果的精度往往大不相同。这是因为初始数据的误差或计算中的舍入误差在计算过程中的传播，因算法不同而异，于是就产生了算法的数值稳定性问题。一个算法,如果计算结果受误差的影响小，就称这个算法具有较好的数值稳数值稳定性定性。否则，就称这个算法的数值稳定性不好。例如在第四

12、节的例1中，第一种算法就是不稳定的,而第二种算法是数值稳定的。算法的数值稳定性概念举例算法的数值稳定性概念举例例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时

13、造成相近两数相减，从而使有效数字严重损失。请看下面的求解方法。一元二次方程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是数值稳定的。从而可知，算法数值稳定性的讨论甚为重要。二、设计算法的若干原则二、设计算法的若干原则为防止误差使计算结果失真(失常）现象发生，要选用数值稳

14、定的计算公式，以保证算法的数值稳定性。下面我们给出设计算法的若干原则，并给出改善算法的例子，这些原则有助于鉴别算法的可靠性并防止误差危害的现象产生。（一）要避免相近两数相减（一）要避免相近两数相减在第四节例1和本节例1中,我们已看到这一原则实际应用的效果,下面再举几个例说明改善算法的方法。例x充分大时1/x1/(x+1)=1/x(x+1)(1+x)1/2x1/2=1/(1+x)1/2+x1/2例对于小的正数 sin(x+)sinx=2cos(x+/2)sin(/2)(注：sin(x)sin(y)=2cos(x+y)/2sin(x-y)/2)例对于绝对值小的x，可利用泰勒级数ex1=x+x2/2

15、+x3/6+取前n项来计算。（二）要防止大数要防止大数“吃掉吃掉“小数，注意保护重要数据小数，注意保护重要数据在数值运算中，参加运算的数有时数量级相差很大，而计算机位数有限，如不注意运算次序就可能出现大数“吃掉”小数的现象，影响计算结果的可靠性。例5在五位浮点十进制计算机上，计算y=54321+0.4+0.3+0.4如果按从左到右的顺序进行加法运算，后三个数都在对阶过程中被当作零，得出含有较大绝对误差的结果y=54321。要避免这种大数“吃掉”小数的现象，可以调整计算顺序，采用先小数后大数的计算次序，即先将0.4,0.3,0.4加起来，然后再加上54321，结果等于54322。一般情况下，若干

16、数相加，采用绝对值较小者先加的算法，结果的相对误差限较小。（三）注意简化计算步骤、减少运算次数、避免误差积累（三）注意简化计算步骤、减少运算次数、避免误差积累同一个计算问题，如果能减少运算次数，不但可以提高计算速度，而且能减少误差的积累。简化计算步骤、减少运算次数、避免误差积累的例子简化计算步骤、减少运算次数、避免误差积累的例子例6计算多项式P4(x)=0.0625x4+0.425x3+1.215x2+1.912x+2.1296的值。如果先计算各项然后相加，需做十次乘法和四次加法。如改用下式计算(0.0625x+0.425)x+1.215)x+1.912)x+2.1296则只需做四次乘法和四次

17、加法。秦九韶算法通常，计算多项式Pn(x)=anxn+an-1xn-1+a1x+a0的值，若直接计算再逐项相加,一共需做n(n+1)/2次乘法和n次加法。若采用Pn(x)=(anx+an-1)x+an-2)x+a1)x+a0即“秦秦九九韶韶算算法法”，则只需n次乘法和n次加法就可以算出Pn(x)的值。“秦九韶算法秦九韶算法”的优点是不仅运算量小，而且数值稳定。秦九韶算法的计算机实现Pn(x)=(anx+an-1)x+an-2)x+a1)x+a0为计算多项式Pn(x)=anxn+an-1xn-1+a1x+a0的秦九韶算法秦九韶算法。计算机实现可按下面的步骤进行：y=an;for(i=n-1;i=

18、0;i-)y=y*x+ai;/*只需n次乘法和n次加法*/简化计算步骤、减少运算次数、避免误差积累的例子简化计算步骤、减少运算次数、避免误差积累的例子又如计算1/(1*2)+1/(2*3)+1/(1000*1001)的值。若一项一项进行计算，不仅计算次数多，而且误差积累也很大。若简化成11/1001进行计算，则整个计算只要一次求倒数和一次减法。（四）要避免绝对值小的数作除数（四）要避免绝对值小的数作除数由式 (x1/x2)d(d(x1/x2)x2(x1)x1(x2)/x22,(x20)可知，当除数x2接近于零时，商的绝对误差就可能很大。因此,在数值计算中要尽量避免绝对值小的数作除数,避免的方法

19、是把算式变形或改变计算顺序。例8当x接近于0时(1-cosx)/sinx的分子、分母都接近0，为避免绝对值小的数作除数，可将原式化为(1-cosx)/sinx=sinx/(1+cosx)例9当x很大时，可化x/(x+1)0.5x0.5=x(x+1)0.5+x0.5（五）设法控制误差的传播（五）设法控制误差的传播许多算法常常具有递推性，如计算多项式值的秦九韶算法，求方程根的牛顿迭代法等。利用递推关系进行计算时，运算过程比较规律，相当方便，但多次递推，必须注意误差的积累。如果递推过程中误差增大，多次递推会得到错误的结果，如果递推过程中误差减小，则得出的结果比较准确。控制误差传播的例子控制误差传播的

20、例子例10计算积分In=01xnex-1dx，n=0,1,2,9利用分部积分法，可得In=xnex-1|0101ex-1dxn=1n01xn-1ex-1dx=1nIn-1从而有递推公式I0=01ex-1dx=ex-1|01=1-1-e-10.6321In=1nIn-1（n=0,1,2,9）计算积分In=01xnex-1dx的过程如果直接应用递推公式I0=01ex-1dx=ex-1|01=1-1-e-10.6321In=1nIn-1（n=1,2,9）用四位小数计算依次得到：0.6321,0.3679,0.2642,0.2074,0.17040.1480,0.1120,0.2160,-0.7280

21、,7.5520由此看到I8为负值、I91，显然与一切0In1（由于e-1/(n+1)=min(ex-1)01xndxIn(0 x1)max(ex-1)01xndx=1/(n+1)矛盾。事实上，从I7开始已经连一位有效数字也没有了（I715|r(I9)|=|(I9)|/I91500%(0I91)这样求得的结果是完全不可靠的，因此这个算法是不稳定的。计算积分In=01xnex-1dx的改进方法根据In=1nIn-1可知In-1=(1In)/n再由e-1/10I91/10取I9(e-1/10+1/10)/2=0.0684按I9(e-1/10+1/10)/2=0.0684In-1=(1In)/n（n=

22、9,8,7,1)计算，保留四位小数依次得I9,I8,I7,I6,I5,I4,I3,I2,I1,I0为：0.0684,0.1035,0.1121,0.1268,0.1455,0.1709,0.2073,0.2642,0.3679,0.6321I0=0.6321全部为有效数字。为什么会有这么好的计算结果呢？下面我们分析一下这种方法的误差积累。计算积分In=01xnex-1dx改进方法的误差分析 根据根据 I9 (e-1/10+1/10)/2=0.0684 In-1=(1 In)/n （n=9,8,7,1)计算计算I9,I8,I7,I6,I5,I4,I3,I2,I1,I0，假定假定I I9 9与准确

23、值的误差为与准确值的误差为(I(I9 9)。那那么么，(I8)=(I9)/9 (I7)=(I8)/8=(I9)/9)/8=(I9)/(9.8)(I6)=(I7)/7=(I8)/8)/7=(I9)/9)/8)/7=(I9)/(9.8.7)(I0)=(I1)/1=(I2)/2)/1=(I9)/9!（如：如：I4=(1-I5)/5=(1-(1-I6)/6)/5=(1-(1-(1-I7)/7)/6)/5 =(1-(1-(1-(1-I8)/8)/7)/6)/5=(1-(1-(1-(1-(1-I9)/9)/8)/7)/6)/5 =1/5 I9/(9.8.7.6.5)这说明由初始值这说明由初始值I I9 9的舍入而产生的误差在计算过程中绝对值会逐渐缩小。若的舍入而产生的误差在计算过程中绝对值会逐渐缩小。若|(I9)|=510-5则则|(I0)|=510-5/9!故这个算法是稳定的。故这个算法是稳定的。