数值计算方法解析课件.ppt

1、*)()(xxxxxExErbAx ni,3,2)(*yEr*2*2*2*1*1*1rrxfyxxfyx第一章 引论iiijjijiilxlbx11nnnnnnaaaaaaaaaA212222111211bAx ni,3,2第一章 绪论 1.3 误差 1.1 数值计算的研究对象与特点 1.2 数值问题与数值方法 1.1 计算机数值方法的研究对象与特点以计算机为工具,求解各种数学模型,都要经历三个过程:总体设计模型的细化详细设计主要为算法设计程序设计计算机数值方法研究的是将数学模型化为数值问题，并研究求解数值问题的数值方法进而设计数值算法数值问题：输入数据与输出数据之间关系即：输入与输出的都是数

2、值的数学问题如求解线性方程组bAx 求解二次方程02cbxaxcbabA,与系数常数项向量输入的数据是系数矩阵是数值问题一、数值问题 1.2 数值问题与数值算法求解微分方程0)0(32yxy不是数值问题xxy3,2函数但输出的不是数据而是输入的虽是数据将其变成数值问题，即将其“离散化”xxy32即将求函数nnxxxxyxyxy2121),(,),(),(改变成求函数值“离散化”是将非数值问题的数学模型化为数值问题的主要方法，这也是计算方法的任务之一21,xxx 和方程的解输出的数据是解向量二、数值方法数值方法:是指解数值问题的在计算机上可执行的系列计算公式在计算机上可执行的公式 是指只含有加减

3、乘除的公式现在的计算机中几乎都含有关于开方的标准函数sqrt()常见的在计算机上不能直接运行的计算有:开方、极限、超越函数、微分、积分等等要在计算机上实行上述运算需将其化为可执行的等价或近似等价运算xe超越函数应化为!212nxxxenx的计算应化为的导数函数)()(xyxyhxyhxyxy)()()(如求根公式aacbbx2422,1应化为公式aacbsqrtbx2)4(22,1研究数值方法的主要任务:1.将计算机上不能执行的运算化为在计算机上可 执行的运算2.针对所求解的数值问题研究在计算机上可执行 的且有效的计算公式3.因为可能采用了近似等价运算,故要进行误差分析,即数值问题的性态及数值

4、方法的稳定性本课程的重点就是对线性方程组、微积分、微分方程、矩阵特征值及回归拟合等问题寻找行之有效的数值方法三、数值算法数值算法是指有步骤地完成解数值问题的过程.数值算法有四个特点:1.目的明确算法必须有明确的目的,其条件和结论均应有清楚的规定2.定义精确对算法的每一步都必须有精确的定义3.可执行算法中的每一步操作都是可执行的4.步骤有限算法必须在有限步内能够完成解题过程例1.给出等差数列1,2,3,10000的求和算法解:0,0.1SN取记数器置零SNSNN,1.2，否则转若2,10000.3NSN,.4 输出 1.3 误差一、误差的种类及来源模型误差描述误差描述误差在建立数学模型过程中,要

5、将复杂的现象抽象归结为数学模型,往往要忽略一些次要因素的影响,而对问题作一些简化,因此和实际问题有一定的区别.观测误差参数误差参数误差在建模和具体运算过程中所用的数据往往是通过观察和测量得到的,由于精度的限制,这些数据一般是近似的,即有误差截断误差方法误差方法误差由于计算机只能完成有限次算术运算和逻辑运算,因此要将有些需用极限或无穷过程进行的运算有限化,对无穷过程进行截断,这就带来误差.截断误差是对参与计算的数学公式做简化可行处理后所产生的误差（用有限过程代替无限过程或用容易计算的方法代替不容易计算的方法），是计算方法关注的内容!3!2132xxxex!7!5!3sin753xxxxx!4!3

6、!2)1ln(432xxxxx如:若将前若干项的部分和作为函数值的近似公式,由于以后各项都舍弃了,自然产生了误差Taylor展开舍入误差计算误差计算误差在数值计算过程中还会遇到无穷小数,因计算机受到机器字长的限制,它所能表示的数据只能有一定的有限位数,如按四舍五入规则取有限位数,由此引起的误差14159265.3414213562.12 166666666.061!311415927.34142136.12 16666667.0!31过失误差由于模型错误或方法错误引起的误差.这类误差一般可以避免数值计算中除了过失误差可以避免外,其余误差都是难以避免的.数学模型一旦建立,进入具体计算时所考虑和分

7、析的就是截断误差和舍入误差经过大量的运算之后,积累的总误差有时会大得惊人,因此如何控制误差的传播也是数值方法的研究对象.二、误差和误差限定义1.称的一个近似值为为准确值设,*xxxxxxE*)(.,*Ex可简记为简称误差的绝对误差为近似值知道的往往是未知甚至是无法因为准确值 x往往也无法求出因此xxxE*)(即绝对值的某个上界而只能知道,)(*xxxE)(|)(|*xxxxE的称为数值*)(xx绝对误差限或误差限,简记为显然*xxx的范围准确值 x或*xx0且215 x若对于51000 y15*x1000*y2)(*x5)(*y哪个更精确呢?吗？15*x定义2.称的一个近似值为为准确值设,*x

8、xxxxxxxExEr*)()(.,*rEx可简记为的相对误差为近似值rrrxxxxxE)()(*的相对误差限为近似值*xrelativeerror|xr绝对误差限相对误差限往往未知*)()(xxxxxExEr|*xr代替相对误差代替相对误差限15*x1000*y2)(*x5)(*y因此%33.13152)(*xr%5.010005)(*yr例1.,28718.2,82281718.2*reee和相对误差限的绝对误差限求其近似值为已知解:eeE*绝对误差82001000.082001000.0|E002000.061026102|*er28718.2102628718.2102661071.0

9、例2.,7,5,3求绝对误差限位数的近似值经四舍五入取小数点后若解:65592141.359141.3*142.3*7592141.3*|*407000.065002000.004000000.03105.05105.07105.0可见,经四舍五入取近似值,其绝对误差限将不超过其末位数字的半个单位;四则运算误差限的公式四则运算误差限的公式:1212xxxx 121221x xxxxx 12211222xxxxxxx *12121212121212e x xx xx xx xx xx xx x *122211xxxxxx 故 *121222111221e x xxxxxxxxxxx三、误差的传播

10、与估计为二元函数设),(21xxfy,21*2*1的近似值分别为xxxx的近似值为相应的 yy*),(*2*1*xxfy 即的绝对误差分别为*2*121,xxEE的绝对误差限分别为*2*121,xx的相对误差限分别为*2*1*2*1,xxrr的相对误差分别为*2*1*2*1,xxEErr2*22*222*22*11*2122*11*212)()()(!21xxxfxxxxxxfxxxf),(*2*1xxf2*21*1ExfExf),(21xxf),(*2*1xxf)()(*22*2*11*1xxxfxxxf的误差的关系的误差与考察*2*1*,xxy展开式为处的在点函数Taylorxxxxf),

11、(),(*2*121)(*yE),(21xxf的绝对误差为*y),(*2*1xxf2*21*1ExfExf为的绝对误差限*y)(*yE2*21*1ExfExf2*21*1ExfExf2*21*1xfxf)(*yEyr的相对误差*)()(yyEyEr*2*2*1*1yExfyExf*22*2*2*11*1*1xExfyxxExfyx*2*2*2*1*1*1rrExfyxExfyx)(*yyr的相对误差限)(*yEr*2*2*2*1*1*1rrxfyxxfyx)(*yr)(*yE2*21*1xfxf2*21*1ExfExf*2*2*2*1*1*1rrExfyxExfyx)(*yEr*2*2*2*1

12、*1*1rrxfyxxfyx)(*yr绝对误差增长因子相对误差增长因子求近似数求近似数285.35,196.87,58.43,4.96的和的和,其中每个数的绝对其中每个数的绝对误差限为误差限为0.5*10-2 285.35196.8758.43+)4.96 545.61和和545.61545.61的绝对误差限为的绝对误差限为:4*(0.5*10-2)=0.020.5*10-1因此和因此和545.61应舍入为应舍入为545.6 加减运算加减运算例2 求3.150950,15.426463,568.3758,7684.388的和加减运算加减运算 0.50.5*1010-3-3 C=8271.341

13、C=8271.341没有意义没有意义按最坏情况按最坏情况 估算误差估算误差 3.150950 15.426463 568.3758+7684.388 8271.341213 0.0000005 0.0000005 0.00005 +0.0005 0.0005510 3.150950 15.426463 568.3758 +7684.388 3.1510 15.4265 568.3758 +7684.388 8271.3413 作舍入作舍入 处理处理 和的绝对误差限为3*(0.5*10-4)+0.5*10-3=0.000650.5*10-2,可将结果舍入为8271.34 加减法运算时需要注意的地

14、方 (1)大量运算时,有时会很大 例 计算多项式的值 011.)(axaxaxPnnnn 如果将公式改写如果将公式改写 0121).)(.()(aaaaxaxxxxPnnn (2)防止大数吃小数的情况a+b+c a+c+b例如计算 采用3位浮点数以截断方式进行运算101.31211 y从左到右的次序计算得y=2.91从右到左的次序计算得y=2.92 误差误差0.0170.017误差误差0.0070.007 例:方程x2-(109+1)x+109=0其精确解为x1=109,x2=1 字长为字长为8 8位的计算器求解位的计算器求解 aacbbx242 929210*4)110(4 acb910 b

15、999110210)110(x0210)110(992 xacbbcacbbx4224222 110)10(10*2999 当被减数和减数相差很大时，大数的相对误差起主要作用|)()(|*yxyxyx|*yxyyyyyxxxxx ，很很小小，而而时时，当当1|yxxyxyyx|)()(|*xxxyxyxyx 很小很小 约为约为1 1 两个相近数相减,易失有效位两正数之差两正数之差 C=x-y y的相对误差是的相对误差是因为x和y的前几位有效数字必然相同，相减之后有效数字位会大大减少，使有效数字严重损失。例如：cos20=0.9994,1-cos20=0.0006yxdydx 避免这种情况,可以

16、使用转换公式;或者增加字长,维持一定有效位,保证精度 )(,)1(11)1()(,lnlnln)(,2sin)2cos(2sin)sin()(,111212121充充分分大大时时当当接接近近时时当当很很小小时时当当很很大大时时当当xxxarctgarctgxxarctgxxxxxxxxxxxxxx 乘积运算乘积运算 乘积运算的相对误差为各乘数的相对误差之和，其相对误差限等于各乘数相对误差限之和 xyyxydxxdydc|)|(|,yxdcyx 则则上上式式成成为为若若|ydyxdxydyxdxxyydxxdycdcc 相相对对误误差差限限为为求c=12.2*73.56的相对误差限和绝对误差限商

17、运算商运算商运算的相对误差限等于除数与被除数的相对误差限之和yxc|2yxdyydxdc ydyxdxyxyxdyydxcdcc 2|ydyxdxcdcc 例 求c=25.7/3.6的相对误差限和绝对误差限 注意(1)当分母很小时，|dc|可能很大xydcdcyxyxyxxyxc *1,商商的的真真值值)(000001.01000001.0481.0433.0 真真值值c 1000000商商的的真真值值舍入误差舍入误差 放大了放大了10106 6倍倍 (2)当分母为两个相近数相减时,会因有效数字丧失而出现(1)的情况)(100001.0)(1455.01456.0)(4分分子子分分子子分分子子

18、 这里分子的误差被这里分子的误差被扩大扩大10104 4倍倍指数运算指数运算 x的p次幂的相对误差是x本身的相对误差的p倍xpppxdxpxdc 11|)1(pxcp|1xdxpxdxpxcdccpp 若令p=1/q，则可得x的q次根的相对误差是x本身相对误差的1/q倍例 求c=(12.2)2的绝对误差限和相对误差限 例 设正方形面积s=12.34,其绝对误差限|s|0.01,问边长a具有多大的相对误差限和多少位有效数字？有4位有效数字有6位有效数字四、有效数字定义3.,*位有效数字有简称有效数字位时具有近似则称用位一位非零数字共有的第而该位数字到单位超过某一位数字的半个其绝对误差的绝对值不的

19、近似值作为若nxnxxnxxx65592141.359141.3*142.3*7592141.3*有8位有效数字1415.3*只有5位有效数字形式：的下列形式称为规格化的近似值*xxknaaax10.021*knaaax10.21*则四舍五入得到的近似值位数的第是对如果,110.021*nxaaaxkn位有效数字具有naaaxkn10.021*且|*xxEnk105.0因此,可根据上述分析对有效数字有如下结果:01a或五、数值方法的稳定性与算法设计原则例8.101dxexeIxnn计算定积分7,2,1,0i解:nI101xndexe101xnexe101dxexenxn11nnI,0I如果先计

20、算721,III然后再计算 数值稳定算法数值稳定算法 在计算过程中产生的舍入误差能被控制在一定的范围内，且对最后的结果影响不大的算法称为稳定算法稳定算法。不是数值稳定的算法称为数值不稳定算法不稳定算法。数值不稳定算法会导致计算结果失真，对数值不稳定的算法常采用转化成相应的数值稳定的算法来处理。,*00II 的近似值为假设计算出)(*0IE误差为)(*1*11IEII的误差为的近似值则2)(*2*22IEII的误差为的近似值!3)(*3*33IEII的误差为的近似值!7)(*7*77IEII的误差为的近似值5040误差放大 5千倍!nIInn11但如果利用递推公式,7I先计算!570千分之一误差

21、的的误差只有II因此在计算公式选用及算法设计时,应注意以下原则1.四则运算中的稳定性问题(1)防止大数吃小数这一类问题主要由计算机的位数引起假如作一个有效数字为4位的连加运算11nnnII公式nIInn11公式误差会放大误差不会放大4012.04697.04896.04987.01234.01041234.01044697.0,4896.0,4987.01234.0104吃了将小数大数而如果将小数放在前面计算1234.0104012.04697.04896.04987.041236.0104在作连加时,为防止大数吃小数,应从小到大进行相加,如此,精度将得到适当改善.当然也可采取别的方法.(2)

22、作减法时应避免相近数相减两个相近的数相减,会使有效数字的位数严重损失01.0cos1510999958.4xcos12sin22x201.0sin22510999958333.4由于在算法设计中,若可能出现两个相近数相减,则改变计算公式,如使用三角变换、有理化等等例9.解方程010)110(992xx解:由中学知识韦达定理可知,方程的精确解为9110 x12xaacbsqrtbx2)4(22,1而如果在字长为8,基底为10的计算机上利用求根公式1109b10101.010100100000000.0机器吃了因此在计算机上10101.0b101000000000.010101.0910aacbs

23、qrtbx2)4(21)4(2acbsqrt92101014)101.0(910 aacbsqrtbx2)4(22可得利用根的关系acxx219991021010021010991x若已算出121xacx110111099上式是解二次方程的数值公式(3)避免小数作除数和大数作乘数由误差传播的估计式)(yE2112xx21xxy对于21xxy 对于)(yE2221121xxx|21xx或)(yE|2x)(yE在算法设计时,要避免这类算法在计算公式中出现2.提高算法效率问题(1)尽量减少运算次数256212864321684222222222215次乘法运算而不是255次使用秦九韶算法0111)(axaxaxaxpnnnn0121)()(axaxaxaxaxpnnn对多项式可大大减少计算量(2)尽量使用耗时少的运算都要节省运算时间比比比如425.0,22xxxxxxxx