数值算法的稳定性.ppt

《数值算法的稳定性.ppt》由会员分享，可在线阅读，更多相关《数值算法的稳定性.ppt（41页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、1/32线性代数线性代数线性代数线性代数一一一一 设设x*是准确数是准确数,x是是x*的近似数，称的近似数，称e=x*-x 为近为近似值似值x的的绝对误差绝对误差，简称误差。，简称误差。上节课内容回顾上节课内容回顾反映是近似值与精确值的绝对差值反映是近似值与精确值的绝对差值称称为近似值为近似值x的的相对误差相对误差反映是近似值与精确值的近似程度反映是近似值与精确值的近似程度通常用百分数来表示，相对误差越小，近似程度越高通常用百分数来表示，相对误差越小，近似程度越高绝对误差限，相对误差限绝对误差限，相对误差限2/32线性代数线性代数线性代数线性代数一一一一则称则称 r 为近似值为近似值x的相对误

2、差限。的相对误差限。|e|=|x*-x|，称称 为近似值为近似值x的绝对误差限，简称的绝对误差限，简称误差限误差限或或精度精度 3/32线性代数线性代数线性代数线性代数一一一一如果如果|e|=|e|=|x*-x|1/2 1/2 10m-n 称近似数称近似数x准确到小数点后第准确到小数点后第n位位,从这小数点后第从这小数点后第n位位数字直到最左边非零数字之间的所有数字都称为有效数字直到最左边非零数字之间的所有数字都称为有效数字数字.有效数字 有效数字越多有效数字越多,误差越小误差越小,计算结果越精确计算结果越精确.近似数近似数x=0.a1a2an10m4/32线性代数线性代数线性代数线性代数一一

3、一一3.142=0.3142101，3.1416=0.31416101，3.141=0.3141101的近似值如下的近似值如下例：例：用四舍五入得到的数都是有效数字用四舍五入得到的数都是有效数字.4位有效数字位有效数字5位有效数字位有效数字3位有效数字位有效数字m=1,n=4m=1,n=5m=1,n=3|e|=|e|=|x*-x|1/2 1/2 10m-n5/32线性代数线性代数线性代数线性代数一一一一相对误差与有效数字的关系如下：相对误差与有效数字的关系如下：定理定理1.1 设近似数设近似数x=0.a1a2an10m有有n位有效数字位有效数字,则则其相对误差限为其相对误差限为定理定理1.2

4、设设近似数近似数x=0.a1a2an10m的相对误差限为的相对误差限为则它至少有则它至少有n位有效数字。位有效数字。6/32线性代数线性代数线性代数线性代数一一一一三、四则运算的误差计算三、四则运算的误差计算绝对误差：e=x*-x=xdx 相对误差：er=(x*-x)/x*dx/x=dlnx利用这个关系可以讨论四则运算的误差和函数的误差例如下列式子说明什么误差结果?d(x+y)=dx+dy dln(xy)=dlnx+dlny dln(xn)=ndlnx思考思考:若若则则7/32线性代数线性代数线性代数线性代数一一一一作业：作业：P1213 1、3、4、6四则运算误差限的公式四则运算误差限的公式

5、:8/32线性代数线性代数线性代数线性代数一一一一 近似计算中误差是不可避免的近似计算中误差是不可避免的，但不能无限，但不能无限扩大。如何控制误差的传播，是设计算法时必须考扩大。如何控制误差的传播，是设计算法时必须考虑的问题。本节将要介绍的内容就是如何控制误差虑的问题。本节将要介绍的内容就是如何控制误差的传播，给出一般的原则。的传播，给出一般的原则。解决一个计算问题往往有多种算法，用不同算法解决一个计算问题往往有多种算法，用不同算法计算的结果其精度往往大不相同。这是因为初始数据计算的结果其精度往往大不相同。这是因为初始数据的误差或计算中的舍入误差在计算过程中的传播造成的误差或计算中的舍入误差在

6、计算过程中的传播造成的，这种传播因算法不同而相异。的，这种传播因算法不同而相异。9/32线性代数线性代数线性代数线性代数一一一一1.4 算法的数值稳定性算法的数值稳定性(数值计算中值得注意的问题数值计算中值得注意的问题)一个算法如果输入数据有误差，而在计算过程一个算法如果输入数据有误差，而在计算过程中舍入误差不增长，则称此算法是中舍入误差不增长，则称此算法是数值稳定的，数值稳定的，否否则称此算法为则称此算法为不稳定的。不稳定的。换句话说：若误差传播是可控制的换句话说：若误差传播是可控制的,则称此算法是则称此算法是数值稳定的数值稳定的,否则称此算法为否则称此算法为不稳定的。不稳定的。10/32线

7、性代数线性代数线性代数线性代数一一一一见教材第见教材第2、1011页页例：计算例：计算(1)In0;(2)In单调递减单调递减In有以下性质有以下性质 在该例中在该例中,用上述公式计算积分的值用上述公式计算积分的值,I0=ln6-ln50.182322的舍入误差在计算过程迅速传播，每次扩大的舍入误差在计算过程迅速传播，每次扩大5倍，致使倍，致使I12=-0.3290211010-2 严重失真，所以这一严重失真，所以这一公式是不稳定的。公式是不稳定的。有递推公式有递推公式11/32线性代数线性代数线性代数线性代数一一一一nInnInnInnIn10.088392260.0243239110.01

8、7324716-10.156920.05803870.018810912-0.003290221750.843330.043138780.021237813-0.093374218-254016140.034306390.017056614-0.395442191270.8650.0284686100.0147169152.0438820-6354.23舍入误差在计算过程迅速传播，每次扩大舍入误差在计算过程迅速传播，每次扩大5倍倍.所以此算法是不稳定的。所以此算法是不稳定的。12/32线性代数线性代数线性代数线性代数一一一一然后取充分大的然后取充分大的m对应的对应的Im的一个估计值为计算初的一

9、个估计值为计算初值，再逐步用上式算出值，再逐步用上式算出Im-1，Im-2，.，I1。用上式计算用上式计算 Im 可使计算的误差减少可使计算的误差减少5倍，因而它对应倍，因而它对应的算法是数值稳定的算法。的算法是数值稳定的算法。而将公式变为而将公式变为由由:可取可取自自n=20计算到计算到n=1,13/32线性代数线性代数线性代数线性代数一一一一nInnInnInnIn200.00873016150.0105205100.015367650.0284684190.00825397140.011229290.016926540.0343063180.00887552130.012039980.0

10、93374230.0431387170.00933601120.012976670.021232620.0580389160.00989750110.014071360.023325010.0883922最后得最后得:I0=0.182322与我们开始计算的与我们开始计算的I00.182322是一样的是一样的该公式给该公式给出的算法出的算法就是稳定就是稳定的的下面通过例子给出算法数值稳定的几个原则：下面通过例子给出算法数值稳定的几个原则：14/32线性代数线性代数线性代数线性代数一一一一一、防止相近的两数相减一、防止相近的两数相减(会会耗耗失失许许多多有有效效数数字字,可可以以用用数数学学公公式

11、式化化简简后后再再做做)例例2:当当x较大时，计算较大时，计算0.041只有两位有效数字只有两位有效数字,有效数字的耗失有效数字的耗失,说明准确度减说明准确度减小小,因此因此,在计算时需要加工计算公式在计算时需要加工计算公式,以免这种情况发以免这种情况发生生.控制误差传播的几个原则控制误差传播的几个原则例例1:各有五位有效数字的两个数各有五位有效数字的两个数23.034与与22.993相减相减.23.034-22.993=0.041 15/32线性代数线性代数线性代数线性代数一一一一解解:例例3:用四位浮点数用四位浮点数计计算算 结结果只有一位有效数字果只有一位有效数字,有效数字大量有效数字大

12、量损损失失,造成相造成相对误对误差差扩扩大。大。这这是由两个比是由两个比较较接近的数相减造成的。接近的数相减造成的。结结果仍然有四位有效数字。果仍然有四位有效数字。这说这说明了算法明了算法设计设计的的重要性。重要性。注：数值计算中要避免有效数字减少。注：数值计算中要避免有效数字减少。16/32线性代数线性代数线性代数线性代数一一一一二、防止大数吃小数二、防止大数吃小数.当当两两个个绝绝对对值值相相差差很很大大的的数数进进行行加加法法或或减减法法运运算算时时,绝绝对对值值小小的的数数有有可可能能被被绝绝对对值值大大的的数数 吃吃掉掉 从从而而引引起起计计算算结果很不可靠结果很不可靠.例例4:求一

13、元二次方程求一元二次方程x2-(109+4)x+4109=0 的实数根的实数根.采采用用因因式式分分解解法法,很很容容易易得得到到两两个个根根为为x1=109,x2=4.如如采采用用字字长长为为8位位的的计计算算机机来来计计算算,求求得得根根为为x1=109 ，x2=0.(怎怎样计算可得较好的结果样计算可得较好的结果?)两两者者结结果果不不同同,因因为为计计算算机机计计算算时时做做加加减减法法要要“对对阶阶”,“对对阶阶”的的结结果果使使大大数数吃吃掉掉了了小小数数.产产生生了了误误差差.为为了了避避免免由由于于上上述述原原因因引引起起的的计计算算结结果果严严重重失失真真,可可以以根根据据一一

14、些些具具体体情情况况,有有时时需需要要把把某某些些算算式式改改写写成成另另一一种种等等价价的的形形式式.17/32线性代数线性代数线性代数线性代数一一一一四、要控制舍入误差的累积和传播四、要控制舍入误差的累积和传播见教材第见教材第2、1011页页分母接近分母接近0，如何改进？，如何改进？如：如：|x|0;(2)In单调递减单调递减In有以下性质有以下性质也可以用等价无穷替换也可以用等价无穷替换18/32线性代数线性代数线性代数线性代数一一一一 在该例中在该例中,用上述公式计算积分的值用上述公式计算积分的值,I0=ln6-ln50.182322的舍入误差在计算过程迅速传播，每次扩大的舍入误差在计

15、算过程迅速传播，每次扩大5倍，致使倍，致使I12=-0.3290211010-2 严重失真，所以这一严重失真，所以这一公式是不稳定的。公式是不稳定的。有递推公式有递推公式nInnInnInnIn10.088392260.0243239110.017324716-10.156920.05803870.018810912-0.003290221750.843330.043138780.021237813-0.093374218-254016140.034306390.017056614-0.395442191270.8650.0284686100.0147169152.0438820-6354.2

16、319/32线性代数线性代数线性代数线性代数一一一一然后取充分大的然后取充分大的m对应的对应的Im的一个估计值为计算初的一个估计值为计算初值，再逐步用上式算出值，再逐步用上式算出Im-1，Im-2，.，I1。用上式计算用上式计算 Im 可使计算的误差减少可使计算的误差减少5倍，因而它对应倍，因而它对应的算法是数值稳定的算法。的算法是数值稳定的算法。而将公式变为而将公式变为由由:可取可取自自n=20计算到计算到n=1,20/32线性代数线性代数线性代数线性代数一一一一nInnInnInnIn200.00873016150.0105205100.015367650.0284684190.00825

17、397140.011229290.016926540.0343063180.00887552130.012039980.093374230.0431387170.00933601120.012976670.021232620.0580389160.00989750110.014071360.023325010.0883922最后得最后得:I0=0.182322与我们开始计算的与我们开始计算的I00.182322是一样的是一样的该公式给该公式给出的算法出的算法就是稳定就是稳定的的21/32线性代数线性代数线性代数线性代数一一一一五、简化计算步骤五、简化计算步骤,减小运算次数减小运算次数,避免误差

18、积累避免误差积累例例7：设设A、B、C、D分分别别是是10 20、20 50、50 1、1 100的矩阵，试按不同的算法求矩阵乘积的矩阵，试按不同的算法求矩阵乘积E=ABCD.解：由矩阵乘法的结合律，可有如下算法解：由矩阵乘法的结合律，可有如下算法1.E=(AB)C)D.计算量计算量N1=11500flop2.E=A(B(CD).计算量计算量N2=125000flop3.E=(A(BC)D.计算量计算量N3=2200flop 简化计算步骤是提高程序执行速度的关键，它不仅可以节省简化计算步骤是提高程序执行速度的关键，它不仅可以节省时间，还能减少舍入误差。时间，还能减少舍入误差。例例6：计算：计算

19、9255的值的值9255=(92)2)2)2)2)2)2)2/9只需只需8次乘法和次乘法和1次除法运算。次除法运算。9255=9 92 94 98 916 932 964 9128只需做只需做14次乘法运算即可。次乘法运算即可。9255=9999但若写成但若写成若逐个相乘要用若逐个相乘要用254次乘法次乘法,22/32线性代数线性代数线性代数线性代数一一一一矩阵乘积矩阵乘积AB的计算量分析的计算量分析a11 a12 a13 a1na21 a22 a23 a2n.am1 am2 amm-1 amnb11 b12 b13 b1sb21 b22 b23 b2s.bn1 bn2 bnn-1 bns=c

20、ijms因为因为 cij=aik bkj 计算每一个计算每一个cij的的计算量为计算量为n所以上面所以上面A m n B n s的的计算量为计算量为N=m n s计算量计算量：一个算法所需的乘除运算总次数，单位是：一个算法所需的乘除运算总次数，单位是flop.计算量也是衡量一个算法好坏的重要标准。计算量也是衡量一个算法好坏的重要标准。23/32线性代数线性代数线性代数线性代数一一一一作业：作业：P13 9、12实验题：实验实验题：实验1.1及及 P13 12作业：作业：P1213 1、3、4、6、824/32线性代数线性代数线性代数线性代数一一一一实验实验1.1（数值微分精度与步长的关系）（数

21、值微分精度与步长的关系）实验目的：实验目的：数值计算中误差是不可避免的，要求通过数值计算中误差是不可避免的，要求通过本实验初步认识数值分析中两个重要概念：截断误差本实验初步认识数值分析中两个重要概念：截断误差和舍入误差，并认真体会误差对计算结果的影响。和舍入误差，并认真体会误差对计算结果的影响。问题提出：设一元函数问题提出：设一元函数f:RR，则，则f在在x0的导数定义为的导数定义为:实验内容实验内容:根据不同的步长根据不同的步长h可设计两种算法可设计两种算法,计算计算f在在x0处的导数处的导数25/32线性代数线性代数线性代数线性代数一一一一计算一阶导数的算法计算一阶导数的算法:请给出两个计

22、算高阶导数的近似算法请给出两个计算高阶导数的近似算法,并完成如下工作并完成如下工作:(1)(2)1、对同样的、对同样的h，比较，比较(1)式和式和(2)式的计算结果；式的计算结果；2、针对计算高阶导数的算法，比较、针对计算高阶导数的算法，比较h取不同值时取不同值时(1)式和式和(2)式的计算结果；式的计算结果；实验要求实验要求：选择有代表性的函数：选择有代表性的函数f(x)（最好多选择几（最好多选择几个），利用个），利用Matlab提供的绘图工具画出该函数在某区提供的绘图工具画出该函数在某区间的导数曲线间的导数曲线f(s)(x)，再将数值计算的结果用，再将数值计算的结果用Matlab 画出来，

23、认真思考实验的结果。画出来，认真思考实验的结果。26/32线性代数线性代数线性代数线性代数一一一一function y=dsh1(fu,x,h)y=(feval(fu,x+h)-feval(fu,x)/h;y函数文件函数文件(扩展名为扩展名为.m),可以被其命令调用可以被其命令调用格式格式:function输出参数输出参数=函数名函数名(输入参数输入参数)可以是可以是多个多个函数名函数名一个一个注意注意:1、保存的文件名与函数名要一、保存的文件名与函数名要一致，这样才能保证调用成功；致，这样才能保证调用成功；2、调用时的输入输出参数要与、调用时的输入输出参数要与函数中的一样；函数中的一样；3、

24、养成良好的注释习惯，便于、养成良好的注释习惯，便于自己或用户调用定义的函数。自己或用户调用定义的函数。注释语句注释语句(前面有前面有%)程序语句程序语句function y=dsh2(fu,x,h)y=(feval(fu,x+h)-feval(fu,x-h)/(2*h);y 调用格式：调用格式：dsh2(sin,1,0.01)调用格式：调用格式：dsh1(sin,1,0.01)实验报告要上交，不能有相同的报告。实验报告要上交，不能有相同的报告。（否则，两个都作废，不予记分）（否则，两个都作废，不予记分）27/32线性代数线性代数线性代数线性代数一一一一 真解真解:cos(1)=0.5403an

25、s=0.5403 dsh1(sin,1,0.1)y=0.4974 dsh1(sin,1,0.01)y=0.5361 dsh1(sin,1,0.001)y=0.5399dsh1(sin,1,0.0001)y=0.5403f(x)=sin(x)-2,2的图形的图形要求：真解和要求：真解和近似解做在一近似解做在一张图上，近似张图上，近似解的散点图有解的散点图有红色的红色的*表示表示,便于比较便于比较.h=0.1有偏差有偏差28/32线性代数线性代数线性代数线性代数一一一一29/32线性代数线性代数线性代数线性代数一一一一 dsh2(sin,1,0.1)y=0.5394dsh2(sin,1,0.01)

26、y=0.5403 真解真解:cos(1)=05403ans=0.5403大家可以找其他大家可以找其他的函数来检验的函数来检验-2,2的图形的图形 plot(x,y,*r,x,y1,-)y=dsh2(sin,-2*pi:0.1:2*pi,0.01);y1=cos(x)x=-2*pi:0.1:2*pi;h=0.01几乎没有几乎没有偏差偏差30/32线性代数线性代数线性代数线性代数一一一一31/32线性代数线性代数线性代数线性代数一一一一dsh1(sin,1,0.00000001)y=0.5403dsh1(sin,1,0.0000000000001)y=0.5396步长为步长为10-12dsh1(s

27、in,1,0.00000000000001)y=0.5440 dsh1(sin,1,0.000000000000001)y=0.5551dsh1(sin,1,0.0000000000000001)y=0步长为步长为10-1532/32线性代数线性代数线性代数线性代数一一一一 截断误差用我们原有的数学思维方式就比较容易截断误差用我们原有的数学思维方式就比较容易理解的，而舍入误差则是本课程引入的一个新概念。理解的，而舍入误差则是本课程引入的一个新概念。要真正理解舍入误差，特别是它在计算中的传播及最要真正理解舍入误差，特别是它在计算中的传播及最终对计算结果的影响，是初步具备科学计算能力的重终对计算结

28、果的影响，是初步具备科学计算能力的重要标志。希望大家在完成实验后，认真仔细去体会截要标志。希望大家在完成实验后，认真仔细去体会截断误差和舍入误差的含义及对计算结果的影响。断误差和舍入误差的含义及对计算结果的影响。图图010-710-510-510-410-310-210-110-310-1误误差差步长步长h33/32线性代数线性代数线性代数线性代数一一一一实验分析实验分析：不论采用怎样的算法，计算结果通常都：不论采用怎样的算法，计算结果通常都会有误差。比如算法会有误差。比如算法(1)，由，由Taylor公式，知：公式，知：所以有所以有利用上式来计算利用上式来计算f(x0)，其截断误差为：，其截

29、断误差为：所以误差是存在的，并且当步长所以误差是存在的，并且当步长h越来越小时，越来越小时，(1)的的近似程度也越来越好。近似程度也越来越好。截断误差截断误差34/32线性代数线性代数线性代数线性代数一一一一类似地可以分析类似地可以分析(2)的截断误差为：的截断误差为：截断误差截断误差上述截断误差的分析表明上述截断误差的分析表明(2)是比是比(1)更好的算法，因为更好的算法，因为对步长对步长h(0,n=1,2,当当n=1时，得：时，得：当当n2时，由分部积分可得：时，由分部积分可得：n=2,3,另外，还有：另外，还有：37/32线性代数线性代数线性代数线性代数一一一一实验内容实验内容：由递推关

30、系：由递推关系In=1-nIn-1，可得计算积分，可得计算积分序列序列In的两种算法：的两种算法：算法一、直接使用递推公式得：算法一、直接使用递推公式得：In=1-nIn-1 n=2,3算法二、利用递推公式变形得：算法二、利用递推公式变形得：实验要求实验要求：用上述两种算法分别在计算中采用：用上述两种算法分别在计算中采用5位、位、6位和位和7位有效数字，请判断哪种算法给出的结果更精确位有效数字，请判断哪种算法给出的结果更精确.38/32线性代数线性代数线性代数线性代数一一一一实验分析：实验分析：两种算法的优劣可能与你的第一感觉完全不同。两种算法的优劣可能与你的第一感觉完全不同。设算法一中设算法

31、一中I1的误差为的误差为e1，由，由I1递推计算递推计算In的误差为的误差为en算法二中算法二中IN的误差为的误差为N，由，由IN向前递推计算向前递推计算In(nN)的的误差为误差为n如果假定上述两种算法在后面的计算中都不再引入其如果假定上述两种算法在后面的计算中都不再引入其他误差，则有：他误差，则有：39/32线性代数线性代数线性代数线性代数一一一一 由此可见，算法一中的由此可见，算法一中的e1可能很小，但在计算中可能很小，但在计算中它的影响急剧扩散，结果真实的数据很快被淹没了；它的影响急剧扩散，结果真实的数据很快被淹没了；而算法二中的而算法二中的N可能相对比较大，但在计算中误差可能相对比较

32、大，但在计算中误差影响不扩散，但某一步产生误差后，该误差对后面影响不扩散，但某一步产生误差后，该误差对后面的影响不断衰减。的影响不断衰减。误差扩散的算法是不稳定的，是我们所不期误差扩散的算法是不稳定的，是我们所不期望的；误差衰减的算法是稳定的，是我们努力寻望的；误差衰减的算法是稳定的，是我们努力寻求的，也是贯穿本课程始终的目标。求的，也是贯穿本课程始终的目标。40/32线性代数线性代数线性代数线性代数一一一一%绘制简单的2维图-图3.1%程序运行后，绘图窗口上出现纵横交叉的两条线，这是%运行 gtext 的结果。移动鼠标交叉点会随之移动。%注意程序中 hold 命令是如何使用的 x=-1:0.

33、05:1 t0=1.0+0*x;t1=x;t2=2*x.*t1-t0;t3=2*x.*t2-t1;plot(x,t0,r);gtext(T0);title(Chebeshev P);xlabel(x);ylabel(y);hold on plot(x,t1,r);gtext(T1);plot(x,t2,r);gtext(T2);plot(x,t3,r);gtext(T3);hold off 命令文件命令文件41/32线性代数线性代数线性代数线性代数一一一一假设机器字长为假设机器字长为32位位,阶码阶码8位位,尾数尾数24位位:阶符阶符C（阶码）（阶码）数符数符M（尾数）（尾数）1位位7位位1位位23位位浮点数在机器中的表示方法如下：浮点数在机器中的表示方法如下：