数值计算方法第一章

1第一章绪论本章以误差为主线，介绍了计算方法课程的特点，并概略描述了与算法相关的基本概念，如收敛性、稳定性，其次给出了误差的度量方法以及误差的传播规律，最后，结合数值实验指出了算法设计时应注意的问题．§1.1引言计算方法以科学与工程等领域所建立的数学模型为求解对象，目的是在有限的时间段内利用有限的计算工具计算出模型的有效解答。由于科学与工程问题的多样性和复杂性，所建立的数学模型也是各种各样的、复杂的.复杂性表现在如下几个方面：求解系统的规模很大，多种因素之间的非线性耦合，海量的数据处理等等，这样就使得在其它课程中学到的分析求解方法因计算量庞大而不能得到计算结果，且更多的复杂数学模型没有分析求解方法．这门课程则是针对从各种各样的数学模型中抽象出或转化出的典型问题，介绍有效的串行求解算法，它们包括(1)非线性方程的近似求解方法；(2)线性代数方程组的求解方法；(3)函数的插值近似和数据的拟合近似；(4)积分和微分的近似计算方法；(5)常微分方程初值问题的数值解法；(6)优化问题的近似解法；等等从如上内容可以看出，计算方法的显著特点之一是“近似”．之所以要进行近似计算，这与我们使用的工具、追求的目标、以及参与计算的数据来源等因素有关．计算机只能处理有限数据，只能区分、存储有限信息，而实数包含有无穷多个数据，这样，当把原始数据、中间数据、以及最终计算结果用机器数表示时就不可避免的引入了误差，称之为舍入误差．我们需要在有限的时间段内得到运算结果，就需要将无穷的计算过程截断，从而产生截断误差．如!21!111e的计算是无穷过程，当用!1!21!111nen作为e的近似时，则需要进行有限过程的计算，但产生了截断误差een．2当用计算机计算ne时，因为舍入误差的存在，我们也只能得到ne的近似值*e，也就是说最终用*e近似e，该近似值既包含有舍入误差，也包含有截断误差．当参与计算的原始数据是从仪器中观测得来时，也不可避免得有观测误差．由于这些误差的大量存在，我们得到的只能是近似结果，进而对这些结果的“可靠性”进行分析就是必须的，它成为计算方法的第二个显著特点．可靠性分析包括原问题的适定性和算法的收敛性、稳定性．所谓适定性问题是指解存在、惟一，且解对原始数据具有连续依赖性的问题．对于非适定问题的求解，通常需要作特殊的预处理，然后才能做数值计算．在这里，如无特殊说明，都是对适定的问题进行求解．对于给定的算法，若有限步内得不到精确解，则需研究其收敛性．收敛性是研究当允许计算时间越来越长时，是否能够得到越来越可靠的结果，也就是研究截断误差是否能够趋于零．对于给定的算法，稳定性分析是指随着计算过程的逐步向前推进，研究观测误差、舍入误差对计算结果的影响是否很大．对于同一类模型问题的求解算法可能不止一种，常希望从中选出高效可靠的求解算法．如我国南宋时期著名的数学家秦九韶就提出求n次多项式0111axaxaxannnn值的如下快速算法nas；knat；tsxs),,2,1(nk它通过n次乘法和n次加法就计算出了任意n次多项式的值．再如幂函数64x可以通过如下快速算法计算出其值xs；sss；循环6次如上算法仅用了6次乘法运算，就得到运算结果．算法最终需要在计算机上运行相应程序，才能得到结果，这样就要关注算法的时间复杂度(计算机运行程序所需时间的度量)、空间复杂度(程序、数据对存储空间需求的度量)和逻辑复杂度(关联程序的开发周期、可维护性以及可扩展性)．事实上，每一种算法都有自己的局限性和优点，仅仅理论分析是很不够的，大量的实际计算也非常重要，结合理论分析以及相当的数值算例结果才有可能选择出适合自己关心问题的有效求解算法．也正因如此，只有理论分析结合实际计算才能真正把握准算法．3§1.2误差的度量与传播一、误差的度量误差的度量方式有绝对误差、相对误差和有效数字．定义1.1用*x作为量x的近似，则称)(:**xexx为近似值*x的绝对误差．由于量x的真值通常未知，所以绝对误差不能依据定义求得，但根据测量工具或计算情况，可以估计出绝对误差绝对值的一个较小上界，即有xxxe**)((1.1)称正数为近似值*x的绝对误差限，简称误差．这样得到不等式**xxx工程中常用*xx表示近似值*x的精度或真值x所在的范围．误差是有量纲的，所以仅误差数值的大小不足以刻划近似的准确程度．如量mmcms50001230000005.023.15.0123(1.2)为此，我们需要引入相对误差定义1.2用0*x作为量x的近似，称)(:**xexxxr为近似值*x的相对误差．当*x是x的较好近似时，也可以用如下公式计算相对误差***)(xxxxer(1.3)显然，相对误差是一个无量纲量，它不随使用单位变化．如式(1.2)中的量s的近似，无论使用何种单位，它的相对误差都是同一个值．同样地，因为量x的真值未知，我们需要引入近似值*x的相对误差限)(*xr，它是相对误差绝对值的较小上界．结合式(1.1)和(1.3)，*x相对误差限可通过绝对误差限除以近似值的绝对值得到，即***)()(xxxr(1.4)为给出近似数的一种表示法，使之既能表示其大小，又能体现其精确程度，需引入有效数字以及有效数的概念．定义1.3设量x的近似值*x有如下标准形式pnmaaaax21*.010pmpnmnmmaaaa101010102211＝(1.5)其中}9,,1,0{}{1piia且01a，m为近似值的量级．如果使不等式4nmxx1021*(1.6)成立的最大整数为n，则称近似值*x具有n位有效数字，它们分别是1a、2a、…和na．特别地，如果有pn，即最后一位数字也是有效数字，则称*x是有效数．从定义可以看出，近似数是有效数的充分必要条件是末位数字所在位置的单位一半是绝对误差限．利用该定义也可以证明，对真值进行“四舍五入”得到的是有效数．对于有效数，有效数字的位数等于从第一位非零数字开始算起，该近似数具有的位数．注意，不能给有效数的末位之后随意添加零，否则就改变了它的精度．例1.1设量x，其近似值141.3*1x，142.3*2x，722*3x．试回答这三个近似值分别有几位有效数字，它们是有效数吗？解这三个近似值的量级1m，因为有312*110211021005.000059.0xx413*2102110210005.00004.0xx571428571428.3*3x312*310211021005.0001.0xx所以*1x和*3x都有3位有效数字，但不是有效数．*2x具有4位有效数字，是有效数．二、误差的传播这里仅介绍初值误差传播，即假设自变量带有误差，函数值的计算不引入新的误差．对于函数),,,(21nxxxfy有近似值),,,(**2*1*nxxxfy，利用在点),,,(**2*1nxxx处的泰勒公式(TaylorFormula)，可以得到)(),,,()(*1**2*1**iininixxxxxfyyye)(),,,(*1**2*1ininixexxxf(1.7)其中iixff:，*ix是ix的近似值，)(*ixe是*ix的绝对误差),,2,1(ni．式(1.7)表明函数值的绝对误差近似等于自变量绝对误差的线性组合，组合系数为相应的偏导数值．从式(1.7)也可以推得如下函数值的相对误差传播近似计算公式5)(),,,()(***1**2*1*irininirxeyxxxxfye(1.8)对于一元函数)(xfy，从式(1.7)和(1.8)可得到如下初值误差传播近似计算公式)()()(***xexfye(1.9))()()(*****xeyxxfyerr(1.10)式(1.9)表明，当导数值的绝对值很大时，即使自变量的绝对误差比较小，函数值的绝对误差也可能很大．例1.2试建立函数nnxxxxxxfy2121),,,(的绝对误差(限)、相对误差的近似传播公式，以及niix1*0时的相对误差限传播公式．解由公式(1.7)和(1.8)可分别推得和的绝对误差、相对误差传播公式如下niiininixexexxxfye1**1**2*1*)()(),,,()(＝(1.11)niiriirininirxeyxxeyxxxxfye1******1**2*1*)()(),,,()(＝(1.12)进而有niiniiniixxexeye1*1*1**)()()()(于是有和的绝对误差限近似传播公式niixy1**)()(当niix1*0时，由式(1.3)推得相对误差限的近似传播公式)(max)(max)(max)()()(*11***11***11****1**irniniiirniniiirniniiriniirxyxxyxxxyxyxy例1.3使用足够长且最小刻度为1mm的尺子，量得某桌面长的近似值3.1304*amm，宽的近似值8.704*bmm(数据的最后一位均为估计值)．试求桌子面积近似值的绝对误差限和相对误差限．解长和宽的近似值的最后一位都是估计位，尺子的最小刻度是毫米，故有误差限5.0)(*amm，5.0)(*bmm面积abS，由式(1.7)得到近似值***baS的绝对误差近似为6)()()(*****beaaebSe进而有绝对误差限55.10045.03.13045.08.704)()()(*****baabSmm2相对误差限%11.00011.08.7043.130455.1004)()(***SSSr§1.3数值实验与算法性能比较本节通过几个简单算例说明解决同一个问题可以有不同的算法，但算法的性能并不完全相同，他们各自有自己的适用范围，并进而指出算法设计时应该注意的事项．算例1.1表达式)1(1111xxxx，在计算过程中保留7位有效数字，研究对不同的x，两种计算公式的计算精度的差异．说明1：Matlab软件采用IEEE规定的双精度浮点系统，即64位浮点系统，其中尾数占52位，阶码占10位，尾数以及阶码的符号各占1位．机器数的相对误差限(机器精度)eps=2－52≈2.220446×10－16，能够表示的数的绝对值在区间(2.2250739×10－308，1.797693×10308)内，该区间内的数能够近似表达，但有舍入误差，能够保留至少15位有效数字．其原理可参阅参考文献[2,4]．分析算法1：111)(1xxxy和算法2：)1(1)(2xxxy的误差时，精确解用双精度的计算结果代替．我们选取点集301}{ii中的点作为x，比较两种方法误差的差异．从图1.1可以看出，当x不是很大时，两种算法的精度相当，但当x很大时算法2的精度明显高于算法1．这是因为，当x很大时，x1和11x是相近数，用算法1进行计算时出现相近数相减，相同的有效数字相减后变成零，于是有效数字位数急剧减少，自然相对误差增大．这一事实也可以从误差传播公式(1.12)分析出．鉴于此，算法设计时，应该避免相近数相减．在图1.2中我们给出了当x接近1时，两种算法的精度比较，其中变量x依次取为3011ii．从图中可以看出两种方法的相对误差基本上都为710，因而二者的精度相当．7图1.1算例1.1中两种算法的相对误差图（x）图1.2算例1.1中两种算法的精度比较)1(x算例1.2试用不同位数的浮点数系统求解如下线性方程组2321200001.02121xxxx说明2：浮点数系统中的加减法在运算时，首先按较大的阶对齐，其次对尾数实施相应的加减法运算，最后规范化存入计算机．算法