数值计算方法第一章

1、 第一章绪论本章以误差为主线，介绍了计算方法课程的特点，并概略描述了与算法相关的基本概念，如收敛性、稳定性，其次给出了误差的度量方法以及误差的传播规律，最后，结合数值实验指出了算法设计时应注意的问题1.1引言计算方法以科学与工程等领域所建立的数学模型为求解对象，目的是在有限的时间段内利用有限的计算工具计算出模型的有效解答。由于科学与工程问题的多样性和复杂性，所建立的数学模型也是各种各样的、复杂的.复杂性表现在如下几个方面：求解系统的规模很大，多种因素之间的非线性耦合，海量的数据处理等等，这样就使得在其它课程中学到的分析求解方法因计算量庞大而不能得到计算结果，且更多的复杂数学模型没有分析求解方法

2、这门课程则是针对从各种各样的数学模型中抽象出或转化出的典型问题，介绍有效的串行求解算法，它们包括非线性方程的近似求解方法；线性代数方程组的求解方法；函数的插值近似和数据的拟合近似；积分和微分的近似计算方法；常微分方程初值问题的数值解法；优化问题的近似解法；等等从如上内容可以看出，计算方法的显著特点之一是“近似”之所以要进行近似计算，这与我们使用的工具、追求的目标、以及参与计算的数据来源等因素有关计算机只能处理有限数据，只能区分、存储有限信息，而实数包含有无穷多个数据，这样，当把原始数据、中间数据、以及最终计算结果用机器数表示时就不可避免的引入了误差，称之为舍入误差我们需要在有限的时间段内得到运

3、算结果，就需要将无穷的计算过程截断，从而产生截断误差.如e=1+丄+丄+的计算是无穷过程，当用1!2!e=1+-+丄+丄作为e的近似时，则需要进行有限过程的计算，但产生了n1!2!n!截断误差e-e.n当用计算机计算e时，因为舍入误差的存在，我们也只能得到e的近似值nne*，也就是说最终用e*近似e，该近似值既包含有舍入误差，也包含有截断误差当参与计算的原始数据是从仪器中观测得来时，也不可避免得有观测误差由于这些误差的大量存在，我们得到的只能是近似结果，进而对这些结果的“可靠性”进行分析就是必须的，它成为计算方法的第二个显著特点可靠性分析包括原问题的适定性和算法的收敛性、稳定性所谓适定性问题是

4、指解存在、惟一，且解对原始数据具有连续依赖性的问题对于非适定问题的求解，通常需要作特殊的预处理，然后才能做数值计算在这里，如无特殊说明，都是对适定的问题进行求解对于给定的算法，若有限步内得不到精确解，则需研究其收敛性收敛性是研究当允许计算时间越来越长时，是否能够得到越来越可靠的结果，也就是研究截断误差是否能够趋于零对于给定的算法，稳定性分析是指随着计算过程的逐步向前推进，研究观测误差、舍入误差对计算结果的影响是否很大对于同一类模型问题的求解算法可能不止一种，常希望从中选出高效可靠的求解算法.如我国南宋时期著名的数学家秦九韶就提出求n次多项式axn+axn-hFax+a值的如下快速算法nn-11

5、0s=a；nt=a；s=sx+1（k=1,2,n）n-k它通过n次乘法和n次加法就计算出了任意n次多项式的值.再如幂函数x64可以通过如下快速算法计算出其值s=x；s=s-s；循环6次如上算法仅用了6次乘法运算，就得到运算结果算法最终需要在计算机上运行相应程序，才能得到结果，这样就要关注算法的时间复杂度（计算机运行程序所需时间的度量）、空间复杂度（程序、数据对存储空间需求的度量）和逻辑复杂度（关联程序的开发周期、可维护性以及可扩展性）事实上，每一种算法都有自己的局限性和优点，仅仅理论分析是很不够的，大量的实际计算也非常重要，结合理论分析以及相当的数值算例结果才有可能选择出适合自己关心问题的有效

6、求解算法也正因如此，只有理论分析结合实际计算才能真正把握准算法1.2误差的度量与传播、误差的度量误差的度量方式有绝对误差、相对误差和有效数字定义11用x*作为量x的近似，则称x*-x二:e(x*)为近似值x*的绝对误差.由于量x的真值通常未知，所以绝对误差不能依据定义求得，但根据测量工具或计算情况，可以估计出绝对误差绝对值的一个较小上界即有e(x*)=x*一xs(1.1)称正数s为近似值x*的绝对误差限，简称误差.这样得到不等式x*-sxx*+s工程中常用x=x*s表示近似值x*的精度或真值x所在的范围.误差是有量纲的，所以仅误差数值的大小不足以刻划近似的准确程度.如量s二1230.5cm二1

7、.230.005m二12300005000rm(1.2)为此，我们需要引入相对误差定义1.2用xy0作为量x的近似，称乂二=:e(x*)为近似值x*的相对误xr差.当x*是x的较好近似时，也可以用如下公式计算相对误差e(x*)=x*一xrx*(1.3)显然，相对误差是一个无量纲量，它不随使用单位变化.如式(1.2)中的量s的近似，无论使用何种单位，它的相对误差都是同一个值.同样地，因为量x的真值未知，我们需要引入近似值x*的相对误差限s(x*)，它是相对误差绝对值的较小上界.结合式(1.1)和(1.3),x*相对误差限可r通过绝对误差限除以近似值的绝对值得到，即s(x*)=rs(x*)(1.4

8、)为给出近似数的一种表示法，使之既能表示其大小，又能体现其精确程度需引入有效数字以及有效数的概念.x*=10mx0.aaa12n定义1.3设量x的近似值x*有如下标准形式ap)=Ux10m-1+ax10m-2HFax10m-nHFax10m-p丿(1.5)12np其中apu0,1,-,9且a丰0，m为近似值的量级.如果使不等式ii=11(1.6)(1.6) #X10m-n2成立的最大整数为n,则称近似值x*具有n位有效数字，它们分别是a、a、12和a.特别地，如果有n=p，即最后一位数字也是有效数字，则称x*是有效n数从定义可以看出，近似数是有效数的充分必要条件是末位数字所在位置的单位一半是绝

9、对误差限利用该定义也可以证明，对真值进行“四舍五入”得到的是有效数对于有效数，有效数字的位数等于从第一位非零数字开始算起，x*322=22.试回答这7该近似数具有的位数注意，不能给有效数的末位之后随意添加零，否则就改变了它的精度例1.1设量x=兀，其近似值x*二3.141，x*二3.142，12三个近似值分别有几位有效数字，它们是有效数吗？解这三个近似值的量级m=1，因为有11=0.000590.005=x10-2=x101-32211=0.00040.0005=x10-3=x101-422x*二3.142857142857311=0.0010.005=X10-2=_X101-322所以x*和

10、x*都有3位有效数字，但不是有效数.x*具有4位有效数字，是有效132数二、误差的传播这里仅介绍初值误差传播，即假设自变量带有误差，函数值的计算不引入新的误差.对于函数y=f(x,x,x)有近似值y*=f(x*,x*,x*)，利用在点TOC o 1-5 h z12n12n(x*,x*,x*)处的泰勒公式(TaylorFormula)，可以得到 HYPERLINK l bookmark99 o Current Document 12ne(y*)=y*-yf(x*,x*,x*)(x*-x)i12niii=1 HYPERLINK l bookmark39 o Current Document =Yf

11、(x*,x*，,x*)e(x*)(1.7)i12nii=1其中f：=f，x*是x的近似值，e(x*)是x*的绝对误差(i=1,2,n).式(1.7)IQxi0乞时的相对误差限传播公式.ii=1解由公式(1.7)和(1.8)可分别推得和的绝对误差、相对误差传播公式如下e(y*)u工f(x*,x*,，x*)e(x*)=工e(x*)12(1.10)(1.11)进而有ii=1nx*e(y*)u乙f(x*,x*,x*)iri12ny*i=1iii=1nx*e(x*)=乙ie(x*)(1.12)riy*rii=1|e(y*)卜工工|e(x*)工(x*)ii=1e(x*)0时，由式(1.3)推得相对误差限的

12、近似传播公式ii=1丫(x*)(y*)u=1=工ri=1=max(x*)X(x*)maxr1in(x*)ii=1x*i*1in=max(x*)y*1inri例1.3使用足够长且最小刻度为1mm的尺子，量得某桌面长的近似值a*=1304.3mm，宽的近似值b*=704.8mm(数据的最后一位均为估计值).试求桌子面积近似值的绝对误差限和相对误差限解长和宽的近似值的最后一位都是估计位，尺子的最小刻度是毫米，故有误差限1inri1i=1(a*)=0.5mm，(b*)=0.5mm面积S=ab，由式(1.7)得到近似值S*=a*b*的绝对误差近似为2020 e(S*)ub*e(a*)+a*e(b*)进而

13、有绝对误差限e(S*)-b*e(a*)+a*e(b*)=704.8x0.5+1304.3x0.5=1004.55mm2相对误差限e(S*)S*1004.551304.3x704.8U0.0011=0.11%1.3数值实验与算法性能比较本节通过几个简单算例说明解决同一个问题可以有不同的算法，但算法的性能并不完全相同，他们各自有自己的适用范围，并进而指出算法设计时应该注意的事项算例1.1表达式1-丄=1，在计算过程中保留7位有效数字，研究xx+1x(x+1)对不同的x,两种计算公式的计算精度的差异.说明1：Matlab软件采用IEEE规定的双精度浮点系统，即64位浮点系统，其中尾数占52位，阶码占

14、10位，尾数以及阶码的符号各占1位机器数的相对误差限(机器精度)eps=2-522.220446X10-】6,能够表示的数的绝对值在区间(2.2250739X10-308，1.797693X10308)内，该区间内的数能够近似表达，但有舍入误差，能够保留至少15位有效数字其原理可参阅参考文献2,4111分析算法1：儿(x)=-和算法2：y(x)=的误差时，精确解用1xx+12x(x+1)双精度的计算结果代替.我们选取点集腕i30中的点作为x,比较两种方法误差i=1的差异从图1.1可以看出，当x不是很大时，两种算法的精度相当，但当x很大时算11法2的精度明显咼于算法1.这是因为，当x很大时，一和

15、是相近数，用xx+1算法1进行计算时出现相近数相减，相同的有效数字相减后变成零，于是有效数字位数急剧减少，自然相对误差增大这一事实也可以从误差传播公式(1.12)分析出鉴于此，算法设计时，应该避免相近数相减在图1.2中我们给出了当x接近-1时，两种算法的精度比较，其中变量x依次取为I-i-10从图中可以看出两种方法的相对误差基本上都为10-7，因而二i=1者的精度相当051015202530i,x=pi图11算例1.1中两种算法的相对误差图（XT+8）1|IflIIlHUH(F算法:：iisiczcri,i=pH-1图1.2算例1.1中两种算法的精度比较（XT-1）算例12试用不同位数的浮点数

16、系统求解如下线性方程组J0.00001X+2x二1|2x+3x二212说明2：浮点数系统中的加减法在运算时，首先按较大的阶对齐，其次对尾数实施相应的加减法运算，最后规范化存入计算机算法1首先用第一个方程乘以适当的系数加至第二个方程，使得第二个方程的X的系数为零，这时可解出X；其次将X带入第一个方程，进而求得X（在第1221三章中称该方法为高斯消元法）当用4位和7位尾数的浮点运算实现该算法，分别记之为算法1a和算法1b. 算法2首先交换两个方程的位置，其次按算法1计算未知数(第三章中称其为选主元的高斯消元法)当用4位和7位尾数的浮点运算实现该算法，分别记之为算法2a和算法2b.方程组的精确解为x

17、=0.25000187,x=0.49999874.，用不同的算法计算12出的结果见表1.1.表1.1对算例1.2用不同算法的计算结果比较算例x*8(x*)x*8(x*)1.21r12r2算法1a0.00000.10X1010.50000.25X107算法2a0.25000.75X1070.50000.25X107算法1b0.26000000.40X1010.49999870.10X106算法0.25000200.50X1080.50000000.25X1072b对于算例1.2，表中的数据表明，当用4位尾数计算时，算法1给出错误的结果，算法2则给出解很好的近似.这是因为在实现算法1时，需要给第一

18、个方程乘以一2/0.00001加至第二个方程，从而削去第二个方程中x的系数，但在计算1x的系数时需做如下运算22x2+3二0.4x106+0.3x101=0.4x106+0.000003x106(1.13)0.00001对上式用4位尾数进行计算，其结果为一0.4x106.因为舍入误差，给相对较大的数加以相对较小的数时，出现大数“吃掉”小数的现象计算右端项时，需做如下运算2x1+2二0.2x106+0.2x101=0.2x106+0.000002x106(1.14)0.00001同样出现了大数吃小数现象，其结果为一0.2x106.这样，得到的变形方程组0.1x104x+0.2x101x二0.1x

19、101|-0.4x106x=-0.2x1062中没有原方程组中第二个方程的信息，因而其解远偏离于原方程组的解该算法中之所以出现较大数的原因是因为运算2/0.00001，因而算法设计中尽可能避免用绝对值较大的数除以绝对值较小的数其实当分子的量级远远大于分母的量级时，除法运算还会导致溢出，计算机终止运行虽从单纯的一步计算来看，大数吃掉小数，只是精度有所损失，但多次的大数吃小数，累计起来可能带来巨大的误差，甚至导致错误.例如在算法1a中出现了两次大数吃小数现象，带来严重的后果因而尽可能避免大数吃小数的出现在算法设计中也是非常必要的当用较多的尾数位数进行计算，舍入误差减小，算法1和2的结果都有所改善，

20、算法1的改进幅度更大些算例1.3计算积分I=11X5dx有递推公式I二一-51n0 x+5nn采用IEEE双精度浮点数，分别用如下两种算法计算I的近似值.30n一1(n=1,2,)，已知1o二ln5-算法1取I的近似值为I*二00.18232155679395，01按递推公式I*=-51*计nn-1算I*30算法2因为6x(39+1)=牛dX139件dX=5x(39+1)取I的近似39值为1(12L240200丿算法1和算法2的计算结果见表1.2误差绝对值的对数图见图1.3*=39沁0.00458333333333，按递推公式I*=n-11(1A-一-1*计算I*30nI*I*-1nI*I*-

21、1nnnnnn算法2表1.2算例1.3的计算结果算法11234568.8392e-0025.8039e-0024.3139e-0023.4306e-0022.8468e-0022.4325e-0021.9429e-0169.8532e-0164.9197e-0152.4605e-0141.2304e-0136.1520e-013252627281.1740e+001-5.8664e+0012.9336e+002-1.4667e+0031.1734e+0015.8670e+0012.9335e+0021.4668e+003393837363534333231304.5833e-0034.2115

22、e-0034.4209e-0034.5212e-0034.6513e-0034.7840e-0034.9255e-0035.0755e-0035.2349e-0035.4046e-0033.9959e-0047.9919e-0051.5984e-0053.1967e-0066.3935e-0071.2787e-0072.5574e-0085.1148e-0091.0230e-0092.0459e-01029307.3338e+003-3.6669e+0047.3338e+0033.6669e+004ood5-oHIeclm)3qEjicno-o*5-oJ1-201011111110510152025303540n图1.3算例1.3用不同算法计算结果的误差绝对值的对数图从表1.2中的计算结果可以看出，算法1随着计算过程的推进，绝对误差几乎不断地以5的倍数增长，即有I*-1U5I*-1U52I*-1U.U5nI*-Innn-1n-1n-2n-200成立对于逐步向前推进的算法，若随着过程的进行，相对误差在不断增长，导致产生不可靠的结果，这种算法称之为数值不稳定的算法对于算法1绝对误差按5的幂次增长，但真值的绝对值却在不断变小且小于1，相对误差增长的速度快于5的幂次，导致产生错误的结果，因而算法1数值不稳定，不能使用而算法2随着计算过程的推进，绝对误差几乎不断地缩小为上一步的