1、华长生制作1iiijjijiilxlbx11nnnnnnaaaaaaaaaA212222111211bAx ni, 3 ,2第一章 引论 1.3 误差 1.1 数值计算的研究对象与特点 1.2 数值问题与数值方法华长生制作2本章要点:绝对误差(限)和相对误差(限)有效数字位数及其与误差的关系数值问题的性态与误差的关系数值算法设计原则华长生制作3 1.1 数值方法的研究对象与特点以计算机为工具,求解各种数学模型,都要经历三个过程:总体设计模型的细化详细设计主要为算法设计程序设计数值方法研究的是将数学模型化为数值问题，研究求解数值问题的数学方法进而设计数值算法华长生制作4数值问题：输入数据与输出数
2、据之间函数关系的一个确定而无歧义的描述即： 输入与输出的都是数值的数学问题如求解线性方程组bAx 求解二次方程02cbxaxcbabA,与系数常数项向量输入的数据是系数矩阵是数值问题一、数值问题 1.2 数值问题与数值算法华长生制作5求解微分方程0)0(32yxy不是数值问题xxy3,2函数但输出的不是数据而是输入的虽是数据将其变成数值问题，即将其“离散化”xxy32即将求函数nnxxxxyxyxy2121),(,),(),(改变成求函数值“离散化”是将非数值问题的数学模型化为数值问题的主要方法，这也是计算方法的任务之一21,xxx 和方程的解输出的数据是解向量华长生制作6二、数值方法数值方法
3、:是指解数值问题的在计算机上可执行的系列计算公式在计算机上可执行的公式 是指只含有加减乘除的公式现在的计算机中几乎都含有关于开方的标准函数sqrt()常见的在计算机上不能直接运行的计算有:开方、极限、超越函数、微分、积分等等要在计算机上实行上述运算需将其化为可执行的等价或近似等价运算华长生制作7xe超越函数应化为! 212nxxxenx的计算应化为的导数函数)()(xyxyhxyhxyxy)()()(如求根公式aacbbx2422,1应化为公式aacbsqrtbx2)4(22,1华长生制作8研究数值方法的主要任务:1.将计算机上不能执行的运算化为在计算机上可 执行的运算2.针对所求解的数值问题
4、研究在计算机上可执行 的且有效的计算公式3.因为可能采用了近似等价运算,故要进行误差分析, 即数值问题的性态及数值方法的稳定性本课程的重点就是对线性方程组、微积分、微分方程、矩阵特征值及回归拟合等问题寻找行之有效的数值方法华长生制作9三、数值算法数值算法是指有步骤地完成解数值问题的过程.数值算法有四个特点:1.目的明确算法必须有明确的目的,其条件和结论均应有清楚的规定2.定义精确对算法的每一步都必须有精确的定义3.可执行算法中的每一步操作都是可执行的4.步骤有限算法必须在有限步内能够完成解题过程华长生制作10例1. 给出等差数列1,2,3,10000的求和算法解:0, 0. 1SN取记数器置零
5、SNSNN,1. 2，否则转若2,10000. 3NSN,. 4 输出华长生制作11 1.3 误差一、误差的种类及来源模型误差在建立数学模型过程中,要将复杂的现象抽象归结为数学模型,往往要忽略一些次要因素的影响,而对问题作一些简化,因此和实际问题有一定的区别.观测误差在建模和具体运算过程中所用的数据往往是通过观察和测量得到的,由于精度的限制,这些数据一般是近似的,即有误差截断误差由于计算机只能完成有限次算术运算和逻辑运算,因此要将有些需用极限或无穷华长生制作12过程进行的运算有限化,对无穷过程进行截断,这就带来误差.! 3! 2132xxxex! 7! 5! 3sin753xxxxx! 4!
6、3! 2)1ln(432xxxxx如:若将前若干项的部分和作为函数值的近似公式,由于以后各项都舍弃了,自然产生了误差Taylor展开华长生制作13舍入误差在数值计算过程中还会遇到无穷小数,因计算机受到机器字长的限制,它所能表示的数据只能有一定的有限位数,如按四舍五入规则取有限位数,由此引起的误差14159265. 3414213562. 12 166666666. 061! 311415927. 34142136. 12 16666667. 0! 31过失误差由于模型错误或方法错误引起的误差.这类误差一般可以避免华长生制作14数值计算中除了过失误差可以避免外,其余误差都是难以避免的.数学模型一
7、旦建立,进入具体计算时所考虑和分析的就是截断误差和舍入误差经过大量的运算之后,积累的总误差有时会大得惊人,因此如何控制误差的传播也是数值方法的研究对象.二、误差和误差限定义1. 称的一个近似值为为准确值设,*xxxxxxE*)(.,*Ex可简记为简称误差的绝对误差为近似值华长生制作15知道的往往是未知甚至是无法因为准确值 x往往也无法求出因此xxxE*)(即绝对值的某个上界而只能知道,)(*xxxE)(|)(|*xxxxE的称为数值*)(xx绝对误差限或误差限,简记为显然*xxx的范围准确值 x或*xx0且华长生制作16215 x若对于51000 y15*x1000*y2)(*x5)(*y哪个
8、更精确呢?吗？15*x定义2. 称的一个近似值为为准确值设,*xxxxxxxxExEr*)()(.,*rEx可简记为的相对误差为近似值rrrxxxxxE)()(*的相对误差限为近似值*xrelativeerror华长生制作17| xr绝对误差限相对误差限往往未知*)()(xxxxxExEr|*xr代替相对误差代替相对误差限15*x1000*y2)(*x5)(*y因此%33.13152)(*xr%5 . 010005)(*yr华长生制作18例1.,28718. 2,82281718. 2*reee和相对误差限的绝对误差限求其近似值为已知解:eeE*绝对误差82001000. 082001000.
9、 0|E002000. 061026102|*er28718. 2102628718. 2102661071. 0是唯一的并不和*r华长生制作19例2.,7 ,5 ,3求绝对误差限位数的近似值经四舍五入取小数点后若解:65592141. 359141. 3*142. 3*7592141. 3*|*407000. 065002000. 004000000. 03105 . 05105 . 07105 . 0可见,经四舍五入取近似值,其绝对误差限将不超过其末位数字的半个单位华长生制作20三、误差的传播与估计(补充)为二元函数设),(21xxfy ,21*2*1的近似值分别为xxxx的近似值为相应的
10、 yy*),(*2*1*xxfy 即的绝对误差分别为*2*121,xxEE的绝对误差限分别为*2*121,xx的相对误差限分别为*2*1*2*1,xxrr的相对误差分别为*2*1*2*1,xxEErr华长生制作212*22*222*22*11*2122*11*212)()()(! 21xxxfxxxxxxfxxxf),(*2*1xxf2*21*1ExfExf),(21xxf),(*2*1xxf)()(*22*2*11*1xxxfxxxf的误差的关系的误差与考察*2*1*,xxy展开式为处的在点函数Taylorxxxxf),(),(*2*121华长生制作22)(*yE),(21xxf的绝对误差为
11、*y),(*2*1xxf2*21*1ExfExf为的绝对误差限*y)(*yE2*21*1ExfExf2*21*1ExfExf2*21*1xfxf华长生制作23)(*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华长生制作24)(*yE2*21*1xfxf2*21*1ExfExf*2*2*2*1*1*1rrExfyxExfyx)(*yEr*2*2*2*1*1*1rrxfyxxfyx)
12、(*yr绝对误差增长因子相对误差增长因子思考:试分析四则运算、乘方和开方的误差传播规律华长生制作25有4位有效数字有6位有效数字四、有效数字定义3. .,*位有效数字有简称有效数字位时具有近似则称用位一位非零数字共有的第而该位数字到单位超过某一位数字的半个其绝对误差的绝对值不的近似值作为若nxnxxnxxx65592141. 359141. 3*142. 3*7592141. 3*有8位有效数字1415. 3*只有4位有效数字华长生制作26形式：的下列形式称为规格化的近似值*xxknaaax10. 021*knaaax10.21*则四舍五入得到的近似值位数的第是对如果,110. 021*nxa
13、aaxkn位有效数字具有naaaxkn10. 021*且|*xxEnk105 . 0因此,可根据上述分析对有效数字有如下结果:01a或华长生制作27定理1. 的近似值满足作为若xx*|*xxEnk105 . 0kmaaax10. 021*位有效数字至少有nx*例3.求下列四舍五入近似值的有效数字个数.218.0*1x18002.0*2x180.2*3x0.218*4x2*51018.2x6*51000218.0 x3个3个4个4个3个5个位有效数字恰好有时而mxnm*,时则nm 华长生制作28例4.个近似值有设395. 3x0 . 4*1x9 . 3*2x4*3x|*1xx |95. 30 .
14、 4|05. 021105 . 0|*2xx |95. 39 . 3|05. 021105 . 0|*3xx |95. 34| 05. 021105 . 0都至少有两个有效数字知根据定理*2*1, 1xx都具有两个有效数字即*2*1,xx?*3字吗也至少具有两个有效数x实际上只1有个华长生制作29例5.:1000效数字位数的下面两个近似值的有判断 x9 .999*1x1 .1000*2x3109999. 041010001. 0|*11xxE1 . 033105 . 0|*22xxE1 . 044105 . 0位有效数字有所以3*1x位有效数字却有而4*2x从以上分析可见,四舍五入的近似值的数
15、字都是有效数字而不是四舍五入得到的近似值的数字不一定是有效数字华长生制作30定理2. 的近似值的表达式为作为若xx*kmaaax10. 021*满足则其相对误差位有效数字有若*,)1(rEnx位有效数字至少有则nx*1*105 . 0|nrE满足的相对误差若反之*,)2(rExnrE105 . 0|*证明:kmaaax10. 021*有位有效数字时有当,)1(*nx|*xxEnk105 . 0kkx10|101 . 0*华长生制作31 xx* xx*|xxxErnk105 . 0k101 . 01105 . 0n1*105 . 0|nrE即满足的相对误差若*)2(rExnrE105 . 0|*
16、|xxxErk10n105 . 0k10n105 . 0nk105 . 0则有则由定理1.可知位有效数字至少有则nx*华长生制作32|*11xxE例6:986. 11x设014. 12x98. 1*1x01. 1*2x.*2*1误差限的有效数字位数与相对与分别求xx31105 . 0解:*11*1*1|)1(xxxEr006. 098. 12105 . 0位有效数字至少有根据定理2,2*1x006. 0位有效数字不会有位有效数字有因此3,2*1x华长生制作33|2*22xxE31105 . 0*22*2*2|)2(xxxEr004. 001. 12105 . 0位有效数字至少有根据定理2,2*
17、2x004. 0位有效数字有因此3*2x位有效数字必然有经四舍五入得到事实上3,*2x华长生制作34定理3 的近似值的表达式为作为若xx*kmaaax10. 021*满足则其相对误差位有效数字有若*,)1(rEnx位有效数字至少有则nx*nraE11*1021|满足的相对误差若反之*,)2(rExnraE11*10) 1(21|该结论可以参照定理2的证明，请同学们自证补充华长生制作35例7.几位至少有效数字？，应取的相对误差不超过要使%1 . 020解:. 4201a的首位数是.*20位有效数字有的近似值设nxnraxxxE11*1021|*|*|则有定理3,相对误差满足001. 010421
18、1n%1 . 0097. 3n即应取4位有效数字,近似值的误差不超过0.1%.华长生制作36五、浮点数和浮点运算(略)六、数值方法的稳定性与算法设计原则例8.101dxexeIxnn计算定积分7 ,2 , 1 , 0i解:nI101xndexe101xnexe101dxexenxn11nnI,0I如果先计算721,III然后再计算华长生制作37,*00II 的近似值为假设计算出)(*0IE误差为)(*1*11IEII的误差为的近似值则2)(*2*22IEII的误差为的近似值! 3)(*3*33IEII的误差为的近似值! 7)(*7*77IEII的误差为的近似值5040误差放大 5千倍!nIIn
19、n11但如果利用递推公式,7I先计算!570千分之一误差的的误差只有II华长生制作38因此在计算公式选用及算法设计时,应注意以下原则1. 四则运算中的稳定性问题(1) 防止大数吃小数这一类问题主要由计算机的位数引起假如作一个有效数字为4位的连加运算11nnnII公式nIInn11公式误差会放大误差不会放大华长生制作394012. 04697. 04896. 04987. 01234. 01041234. 01044697. 0 ,4896. 0 ,4987. 01234. 0104吃了将小数大数而如果将小数放在前面计算1234. 0104012. 04697. 04896. 04987. 04
20、1236. 0104在作连加时,为防止大数吃小数,应从小到大进行相加,如此,精度将得到适当改善.当然也可采取别的方法.华长生制作40(2) 作减法时应避免相近数相减两个相近的数相减,会使有效数字的位数严重损失01. 0cos1510999958. 4xcos12sin22x201. 0sin22510999958333. 4由于在算法设计中,若可能出现两个相近数相减,则改变计算公式,如使用三角变换、有理化等等华长生制作41例9.解方程010)110(992xx解:由中学知识韦达定理可知,方程的精确解为9110 x12xaacbsqrtbx2)4(22,1而如果在字长为8,基底为10的计算机上利
21、用求根公式1109b10101 . 010100100000000. 0机器吃了因此在计算机上10101 . 0b101000000000. 010101 . 0910华长生制作42aacbsqrtbx2)4(21)4(2acbsqrt92101014)101 . 0(910 aacbsqrtbx2)4(22可得利用根的关系acxx219991021010021010991x若已算出121xacx110111099上式是解二次方程的数值公式华长生制作43(3) 避免小数作除数和大数作乘数由误差传播的估计式)(yE2112xx21xxy对于21xxy 对于)(yE2221121xxx|21xx或)(yE|2x)(yE在算法设计时,要避免这类算法在计算公式中出现华长生制作442. 提高算法效率问题(1) 尽量减少运算次数256212864321684222222222215次乘法运算而不是255次使用秦九韶算法0111)(axaxaxaxpnnnn0121)()(axaxaxaxaxpnnn对多项式可大大减少计算量华长生制作45(2) 尽量使用耗时少的运算都要节省运算时间比比比如425. 0,22xxxxxxxx(3) 充分利用存储空间
