数值计算方法第一章_2.docx

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

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

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

3、误差，称之为舍入误差我们需要在有限的时间段内得到运算结果，就需要将无穷的计算经过截断，进而产生截断误差如+=!21!111e的计算是无穷经过，当用!1!21!111nen+=作为e的近似时，则需要进行有限经过的计算，但产生了截断误差een-当用计算机计算ne时，由于舍入误差的存在，我们也只能得到ne的近似值*e，也就是讲最终用*e近似e，该近似值既包含有舍入误差，也包含有截断误差当介入计算的原始数据是从仪器中观测得来时，也不可避免得有观测误差由于这些误差的大量存在，我们得到的只能是近似结果，进而对这些结果的“可靠性进行分析就是必须的，它成为计算方法的第二个显著特点可靠性分析包括原问题的适定性和

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

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

6、择出合适本人关心问题的有效求解算法也正因如此，只要理论分析结合实际计算才能真正把握准算法1.2误差的度量与传播一、误差的度量误差的度量方式有绝对误差、相对误差和有效数字定义1.1用*x作为量x的近似，则称)(:*xexx=-为近似值*x的绝对误差由于量x的真值通常未知，所以绝对误差不能根据定义求得，但根据测量工具或计算情况，能够估计出绝对误差绝对值的一个较小上界，即有-=xxxe*)(1.1)称正数为近似值*x的绝对误差限，简称误差这样得到不等式+-*xxx工程中常用=*xx表示近似值*x的精度或真值x所在的范围误差是有量纲的，所以仅误差数值的大小缺乏以刻划近似的准确程度如量mmcms5000

7、1230000005.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)为给出近似数的

8、一种表示法，使之既能表示其大小，又能体现其准确程度，需引入有效数字以及有效数的概念定义1.3设量x的近似值*x有如下标准形式pnmaaaax21*.010?=()pmpnmnmmaaaa-?+?+?+?101010102211(1.5)其中9,1,01?=piia且01a，m为近似值的量级假如使不等式nmxx-?-1021*(1.6)成立的最大整数为n，则称近似值*x具有n位有效数字，它们分别是1a、2a、和na十分地，假如有pn=，即最后一位数字也是有效数字，则称*x是有效数从定义能够看出，近似数是有效数的充分必要条件是末位数字所在位置的单位一半是绝对误差限利用该定义可以以证实，对真值进行“

9、四舍五入得到的是有效数对于有效数，有效数字的位数等于从第一位非零数字开场算起，该近似数具有的位数注意，不能给有效数的末位之后随意添加零，否则就改变了它的精度例1.1设量=x，其近似值141.3*1=x，142.3*2=x，722*3=x试回答这三个近似值分别有几位有效数字，它们是有效数吗？解这三个近似值的量级1=m，由于有312*110211021005.000059.0-?=?=-xx413*2102110210005.00004.0-?=?=-xx571428571428.3*3=x312*310211021005.0001.0-?=?=-xx所以*1x和*3x都有3位有效数字，但不是有效

10、数*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)可以以推得

11、如下函数值的相对误差传播近似计算公式)(),()(*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)可分别推得和的绝对误差、相对误差传播公式如下=niiin

12、inixexexxxfye1*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，宽的近

13、似值8.704*=bmm(数据的最后一位均为估计值)试求桌子面积近似值的绝对误差限和相对误差限解长和宽的近似值的最后一位都是估计位，尺子的最小刻度是毫米，故有误差限5.0)(*=amm，5.0)(*=bmm面积abS=，由式(1.7)得到近似值*baS=的绝对误差近似为)()()(*beaaebSe+进而有绝对误差限55.10045.03.13045.08.704)()()(*=?+?=+baabSmm2相对误差限%11.00011.08.7043.130455.1004)()(*=?=SSSr1.3数值实验与算法性能比拟本节通过几个简单算例讲明解决同一个问题能够有不同的算法，但算法的性能并不

14、完全一样，他们各自有本人的适用范围，并进而指出算法设计时应该注意的事项算例1.1表达式)1(1111+=+-xxxx，在计算经过中保留7位有效数字，研究对不同的x，两种计算公式的计算精度的差异讲明1：Matlab软件采用IEEE规定的双精度浮点系统，即64位浮点系统，其中尾数占52位，阶码占10位，尾数以及阶码的符号各占1位机器数的相对误差限(机器精度)eps=2522.2204461016，能够表示的数的绝对值在区间(2.225073910308，1.79769310308)内，该区间内的数能够近似表达，但有舍入误差，能够保留至少15位有效数字其原理可参阅参考文献2,4分析算法1：111)(

15、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从图中能够看出两种方法的相对误

16、差基本上都为710-，因此二者的精度相当图1.1算例1.1中两种算法的相对误差图+x图1.2算例1.1中两种算法的精度比拟)1(-x算例1.2试用不同位数的浮点数系统求解如下线性方程组?=+=+2321200001.02121xxxx讲明2：浮点数系统中的加减法在运算时，首先按较大的阶对齐，其次对尾数施行相应的加减法运算，最后规范化存入计算机算法1首先用第一个方程乘以适当的系数加至第二个方程，使得第二个方程的1x的系数为零，这时可解出2x；其次将2x带入第一个方程，进而求得1x(在第三章中称该方法为高斯消元法)当用4位和7位尾数的浮点运算实现该算法，分别记之为算法1a和算法1b算法2首先交换两

17、个方程的位置，其次按算法1计算未知数(第三章中称其为选主元的高斯消元法)当用4位和7位尾数的浮点运算实现该算法，分别记之为算法2a和算法2b方程组的准确解为.25000187.01=x，.49999874.02=x，用不同的算法计算出的结果见表1.1对于算例1.2，表中的数据表明，当用4位尾数计算时，算法1给出错误的结果，算法2则给出解很好的近似这是由于在实现算法1时，需要给第一个方程乘以00001.0/2加至第二个方程，进而削去第二个方程中1x的系数，但在计算2x的系数时需做如下运算661610000003.0104.0103.0104.03200001.02?=+?(1.13)对上式用4位

18、尾数进行计算，其结果为6104.0?由于舍入误差，给相对较大的数加以相对较小的数时，出现大数“吃掉小数的现象计算右端项时，需做如下运算661610000002.0102.0102.0102.02100001.02?=+?(1.14)同样出现了大数吃小数现象，其结果为6102.0?这样，得到的变形方程组?-=?-?=?+?62612114102.0104.0101.0102.0101.0xxx中没有原方程组中第二个方程的信息，因此其解远偏离于原方程组的解该算法中之所以出现较大数的原因是由于运算00001.0/2，因此算法设计中尽可能避免用绝对值较大的数除以绝对值较小的数其实当分子的量级远远大于分

19、母的量级时，除法运算还会导致溢出，计算机终止运行虽从单纯的一步计算来看，大数吃掉小数，只是精度有所损失，但屡次的大数吃小数，累计起来可能带来宏大的误差，甚至导致错误例如在算法1a中出现了两次大数吃小数现象，带来严重的后果因此尽可能避免大数吃小数的出如今算法设计中也是非常必要的当用较多的尾数位数进行计算，舍入误差减小，算法1和2的结果都有所改善，算法1的改良幅度更大些算例1.3计算积分?+=1055dxxxIn有递推公式),2,1(511=-=-nInInn，已知56ln0=I采用IEEE双精度浮点数，分别用如下两种算法计算30I的近似值算法1取0I的近似值为6793950.18232155*0

20、=I，按递推公式*1*51-=nnInI计算*30I算法2由于)139(5156)139(611039103939+?=图1.3算例1.3用不同算法计算结果的误差绝对值的对数图从表1.2中的计算结果能够看出，算法1随着计算经过的推进，绝对误差几乎不断地以5的倍数增长，即有0*02*221*1*555IIIIIIIInnnnnnn-成立对于逐步向前推进的算法，若随着经过的进行，相对误差在不断增长，导致产生不可靠的结果，这种算法称之为数值不稳定的算法对于算法1绝对误差按5的幂次增长，但真值的绝对值却在不断变小且小于1，相对误差增长的速度快于5的幂次，导致产生错误的结果，因此算法1数值不稳定，不能使

21、用而算法2随着计算经过的推进，绝对误差几乎不断地缩小为上一步的1/5，即有mmnmnnnnnnnIIIIIIII5/5/5/*22*21*1*+-成立绝对误差不断变小，真值的绝对值随着经过向前推进却在变大，这样相对误差也越来越小，这样的方法称之为数值稳定的算法算法1和算法2的误差对数示意图见图1.3这个算例告诉我们应该选用数值稳定的算法知识构造图?算法设计要点数值方法的稳定性数值方法的收敛性算法多元函数一元函数传播有效数字相对误差限绝对误差限度量截断误差舍入误差误差的产生误差误差与算法习题一1已知有效数105.3*1-=x，4*210125.0?=x，010.0*3=x试给出各个近似值的绝对误

22、差限和相对误差限，并指出它们各有几位有效数字2证实当近似值*x是x的较好近似时，计算相对误差的计算公式xxx-*和*xxx-相差一个和2*?-xxx同阶的无穷小量3设x的近似值*x具有如式(1.5)的表示形式，试证实1)若*x具有n位有效数字，则相对误差nraxe-?11*1021)(；2)若相对误差nraxe-?+11*10)1(21)(，则*x至少具有n位有效数字4试建立二元算术运算的绝对误差限传播近似计算公式5试建立如下表达式的相对误差限近似传播公式，并针对第1题中数据，求下列各近似值的相对误差限1)*3*2*1*1xxxy+=；2)3*2*2xy=；3)*3*2*3/xxy=6若例题1.3中使用的尺子长度是80mm，最小刻度为1mm，量得某桌面长的近似值3.1304*=amm，宽的近似值8.704*=bmm试估计桌子长度、宽度的绝对误差限，并求用该近似数据计算出的桌子面积的绝对误差限和相对误差限7改变如下计算公式，使其计算结果更为准确1)0,cos1-xxx且1-+=?+NNNNNxdxNN