第一章绪论上次课要点:§1数值分析的几个基本问题一、用数学方法解决科学与工程问题的步骤二、研究对象三、研究内容四、研究数值计算方法的意义五、算法设计的基本思想六、算法应具备的特性§2数值计算的误差一、误差的分类1.截断误差:近似公式引起的2.舍入误差:计算机字长有限引起的二、误差的概念1.绝对误差xxxE**)(2.相对误差xxExEr)()(**(其中0x)近似相对误差****()()rExExx(其中*0x)三、数值运算的误差当自变量有误差时,一般地,其函数值也有误差。误差——可能是截断误差——也可能是舍入误差1.一元函数的误差设*x是准确值x的近似值,则函数)(xf的近似值为)(*xf。由于))(()()(**xxfxfxf,介于x与*x之间,所以)()()()(**xxfxfxf从而)()())((**xfxf本次课继续。。。。2.多元函数的误差对于多元函数),,,(21nxxxf,设自变量的近似值分别为**2*1,,,nxxx,则),,,(),,,(),,,((21**2*1**2*1nnnxxxfxxxfxxxfE)(|)(|*),,,(*1),,,(1**2*1**2*1nxxxnxxxxexfxexfnn于是误差限),,,((**2*1nxxxfnkkxxxkxxfn1*),,()(|**2*1特别)()()(*2*1*2*1xxxx)()()(*1*2*2*1*2*1xxxxxx2*2*1*2*2*1*2*1)()()/(xxxxxxx四、病态问题与条件数一个工程或科学计算问题:——往往需要巨量的机器运算——每次运算都可能产生误差——这些误差有正有负,绝对值有大有小误差积累的结果很难定量分析。首先定性研究什么情况下误差会被放大,导致计算结果严重失真。1.从问题的角度——病态问题对于一个数值问题,如果输入数据有微小的扰动,就能引起输出数据相对误差很大,该问题就称为病态问题。例如计算函数)(xf的值,设输入数据x——有扰动x,即xxx*,其相对误差为xx;输出数据)(xf——相对误差为)()()(*xfxfxf两者的绝对值的比值*()()()()()pfxfxfxxfxcxfxxpc称为计算函数值的条件数。当条件数pc很大时,虽然xx较小,但函数值的相对误差可能很大。条件数pc很大的函数称为病态函数,否则称为良态函数。例如nxxf)(,有ncp。它表示相对误差可能大约放大n倍。这说明多项式函数对于计算函数值而言是病态的。线性方程组也有病态、良态问题,它可以用系数矩阵的条件数刻画。2.从算法的角度——算法的数值稳定性舍入误差对计算结果的精确性影响小的算法,称为数值稳定的;反之,算法称为数值不稳定性的。【例7】计算积分9,,2,1,0,d101nxexeIxnn由于1011010ddd)(xexnxexxexexnxnxn所以11nnnII(1)使用递推公式11nnInI。先计算0I,101eI若用泰勒展开式!)1(!2)1()1(121kek并取7k,用4位小数计算,则得3679.01e从而6321.03679.01*0I利用递推公式*1*1nnnII(9,,2,1n)可依次得到552.77280.02160.01120.01480.01704.02074.02642.03679.0*9*8*7*6*5*4*3*2*1IIIIIIIII用0E表示这样计算0I的绝对误差,则03679.0)1()3679.01(110*00eeIIE则011*1*!)1()1()1(EnnEnInIIIEnnnnnnn由此可见,尽管误差正负交错,但绝对值逐步增大,说明该迭代公式数值不稳定。(2)使用递推公式11nnIIn。先计算9I,由于1011091Ie我们初略取0684.0)10101(211*9eI则又递推公式nIInn**11可依次得到6321.03679.02643.02073.01708.01455.01268.01121.01035.0*0*1*2*3*4*5*6*7*8IIIIIIIII误差nEEnn1!)1(0nEEnn该迭代公式是数值稳定的。例题对于1x的情况,从舍入误差传播的角度,指出下述两个Matlab程序哪一个计算1()xefxx是数值稳定的,并说明理由.注意:0x是()fx的可去间断点,可定义001(0)lim()lim1xxxeffxx。%Algorithm1ifx==0f=1;elsef=(exp(x)-1)/x;end%Algorithm2Y=exp(x)ify==1f=1;elsef=(y-1)/log(y);end解答:当1x时,0x分两种情况:(1)1xe。此时,两种算法结果一样。(2)1xe。此时,正确的结果(Algorithm2)是()1fx。因为此时()1/()1xxfxexfxe。但按Algorithm1,()0fx。3.避免误差危害的几个原则(1)避免两个相近数相减(代数和接近0)。(2)避免除数绝对值太小。(3)避免两个绝对值相差很大的数相加减(大吃小,丧失有效数字的位数)。(4)尽可能减少运算步骤(减少误差积累)。(5)算法或公式要数值稳定。下面分别进行讨论。(1)避免两个相近数相减(代数和接近0)因两数之差x-y的相对误差为yxyExEyxEr)()()(,当x与y很接近时,两数之差x-y的相对误差会很大,有效数字位数将严重丢失。某些情况可以避免。办法:进行变换。【例】.1701300384048,如用四位有效数字计算:..17013130413004,结果只有一位有效数字;如改为:..111701300384013041317013,有四位有效数字。新算法避免了两个相近数的相减。【例】用四位浮点数计算76017591。解:522102.0101316.0101318.076017591只有一位有效数字,有效数字大量损失,造成相对误差扩大。56101734.0105768.01760759176017591结果仍然有四位有效数字。【例】当xy时,计算lnlnxy有效位数会损失。改用lnlnlnxxyy是否就能减少舍入误差?解:不能。当xy时,1xy。考虑()lnfzz在1z附近的性态。()1()lnpzfzCfzz,当1z时,pC,说明自变量的误差对函数值的误差影响很大。本问题可以1lnlndxyxytt,用数值积分计算。(2)避免除数绝对值太小2xyyxxyy,当xy时,舍入误差会扩大。某些情况可通过改变运算次序避免。(3)避免两个绝对值相差很大的数相加减(大吃小,丧失有效数字的位数)【例】一元二次方程010)110(992xx其精确解为1,10291xx。如用求根公式aacbbx2422,1和字长为8位的计算器求解,有91891821010104104acb,及9910110;则999110210)10(x,0210)10(992x。2x的值与精确解差别很大。若用acbbcaacbbx4224222110)10(102999。因此,算法的选用很重要。【例】采用单精度计算71017110kfe解:f=exp(-1.0)=0.3678795dok=1,10000000f=f+0.00000001enddo计算结果:f=0.3678795(小数被大数吃掉!)正确结果应为:f=1.3678795(先计算)(4)尽可能减少运算步骤(减少误差积累)【例】计算255x的值如果逐个相乘要用254次乘法。若128643216842255xxxxxxxxx只需14次乘法。【例】计算多项式的值:0111)(axaxaxaxPnnnnn如若按kkax有k次乘法运算,计算nPx共需1122nnn次乘法和n次加法运算。如写成(秦九韶,公元1202-1261)1210nnnnPxaxaxaxaxa,用递推算法:01,,1,2,,.nkknkuauuxakn,最终nnPxu,共需n次乘法和n次加法运算。(5)算法或公式要数值稳定。【例】已知a是积分210dxex的近似值,并且有四位有效数字,则a的绝对误差限()a——。解:根据积分中值定理,有2210d,01xexe因此,2100.1d1.0xex又a具有4位有效数字,因此12340.aaaaa,(10a)所以a与210dxex的绝对误差的绝对值不超过小数点后第4位的半个单位。因此a的绝对误差限41()102a。例2.设有一长方体水池,由测量知其长为(500.01)m,宽为(250.01)m,深为(200.01)m,试按所给数据求出该水池的容积,并分析所得近似值的绝对误差和相对误差,给出绝对误差限和相对误差限。【解】设长方体水池的长、宽、高、分别为,,abc由题设条件**50()0.01aea**25()0.01beb**20()0.01cec长方体水池体积abc****350252025000()abcm因为*************(,,)(,,)(,,)*********()|()|()|()()()()abcabcabcvvveveaebecabcbceaacebabec故**********()()()()ebceaacebabec*********()()()bceaacebacec25200.0150200.0150250.01327.50()m而***()()ree故**27.50()0.11%25000rev(绝对值很小)所以*()0.11%rev例3.已知201和200的6位有效数的近似值分别为14.1774和14.1421,试按201200A和1201200A两种算法求出A的近似值,并分别求出两种算法所得A的近似值的绝对误差限,问这两种结果各具有几位有效数字。【解】令12201,200,xx**1214.1774,14.1421,xx且*4*41211()10()1022exex第一种算法:20120014.177414.14210.0353A1100.353。第二种算法:1114.177414.1421201200A10.035311357928.31951100.353113579。由****1212()()()exxexex有****1212()()()exxexex**12()()exex44111010224311010212110(10)2故对于算式201200A来讲,算法至少有2位有效数字。而**12****21212()1()exxexxxx故**12****2121211()()()eexexxxxx**12**2121()()()exexxx2411028.319526610.124691010215110102故对于算法1201200A来讲,算法至少具有5位有效数字。例4.设126.1025