数值算法的稳定性ppt课件.ppt

《数值算法的稳定性ppt课件.ppt》由会员分享，可在线阅读，更多相关《数值算法的稳定性ppt课件.ppt（56页珍藏版）》请在三一办公上搜索。

1、设x*是准确数, x是x*的近似数，称e = x* - x 为近似值x的绝对误差，简称误差。,上节课内容回顾,反映是近似值与精确值的绝对差值,称,为近似值x的相对误差,反映是近似值与精确值的近似程度,通常用百分数来表示，相对误差越小，近似程度越高,绝对误差限，相对误差限,则称r 为近似值x的相对误差限。,|e| = |x* - x| ，称 为近似值x的绝对误差限，简称误差限或精度,如果|e| = |x* - x| 1/2 10m-n 称近似数x准确到小数点后第n位,从这小数点后第n位数字直到最左边非零数字之间的所有数字都称为有效数字.,有效数字,有效数字越多,误差越小,计算结果越精确.,近似数

2、x=0.a1a2an10m,相对误差与有效数字的关系如下：,定理1.1 设近似数x=0.a1a2an10m有n位有效数字,则其相对误差限为,定理1.2 设近似数x=0.a1a2an10m的相对误差限为,则它至少有n位有效数字。,1.4 算法的数值稳定性(数值计算中值得注意的问题),一个算法如果输入数据有误差，而在计算过程中舍入误差不增长，则称此算法是数值稳定的，否则称此算法为不稳定的。,换句话说：若误差传播是可控制的,则称此算法是数值稳定的,否则称此算法为不稳定的。,见教材第2、1011页,例：计算,(1)In0; (2)In单调递减,In有以下性质,在该例中,用上述公式计算积分的值,I0=l

3、n6-ln50.182322的舍入误差在计算过程迅速传播，每次扩大5倍，致使I12= -0.3290211010-2 严重失真，所以这一公式是不稳定的。,有递推公式,舍入误差在计算过程迅速传播，每次扩大5倍.,所以此算法是不稳定的。,然后取充分大的m对应的Im的一个估计值为计算初值，再逐步用上式算出Im-1 ，Im-2 ，.，I1。,用上式计算 Im 可使计算的误差减少5倍，因而它对应的算法是数值稳定的算法。,而将公式变为,由:,可取,自n=20计算到n=1,最后得: I0=0.182322,与我们开始计算的I00.182322是一样的,该公式给出的算法就是稳定的,下面通过例子给出算法数值稳定

4、的几个原则：,一、防止相近的两数相减(会耗失许多有效数字,可以用数学公式化简后再做),例2:当x较大时，计算,0.041只有两位有效数字,有效数字的耗失,说明准确度减小,因此,在计算时需要加工计算公式,以免这种情况发生.,控制误差传播的几个原则,例1: 各有五位有效数字的两个数23.034与22.993相减. 23.034-22.993=0.041,解:,例3:用四位浮点数计算,结果只有一位有效数字,有效数字大量损失,造成相对误差扩大。这是由两个比较接近的数相减造成的。,结果仍然有四位有效数字。这说明了算法设计的重要性。,注：数值计算中要避免有效数字减少。,二、防止大数吃小数 当两个绝对值相差

5、很大的数进行加法或减法运算时,绝对值小的数有可能被绝对值大的数吃掉从而引起计算结果很不可靠. 例4:求一元二次方程x2-(109 +4)x+4109=0 的实数根.采用因式分解法,很容易得到两个根为x1=109,x2=4.如采用字长为8位的计算机来计算,求得根为x1=109 ，x2=0.(怎样计算可得较好的结果?) 两者结果不同,因为计算机计算时做加减法要 “对阶”,“对阶”的结果使大数吃掉了小数.产生了误差.为了避免由于上述原因引起的计算结果严重失真,可以根据一些具体情况,有时需要把某些算式改写成另一种等价的形式.,四、要控制舍入误差的累积和传播,见教材第2、1011页,分母接近0，如何改进

6、？,如：|x|1时,三、防止接近零的数做除数分母接近零的数会产生溢出错误,因而产生较大的误差,此时可以用数学公式化简后再做.,例5 计算,In有以下性质,也可以用等价无穷小替换,在该例中,用上述公式计算积分的值,I0=ln6-ln50.182322的舍入误差在计算过程迅速传播，每次扩大5倍，致使I12= -0.3290211010-2 严重失真，所以这一公式是不稳定的。,有递推公式,然后取充分大的m对应的Im的一个估计值为计算初值，再逐步用上式算出Im-1 ，Im-2 ，.，I1。,用上式计算 Im 可使计算的误差减少5倍，因而它对应的算法是数值稳定的算法。,而将公式变为,在该例中,用上述公式

7、计算积分的值,I0=ln6-ln50.182322的舍入误差在计算过程迅速传播，每次扩大5倍，致使I12= -0.3290211010-2 严重失真，所以这一公式是不稳定的。,有递推公式,然后取充分大的m对应的Im的一个估计值为计算初值，再逐步用上式算出Im-1 ，Im-2 ，.，I1。,用上式计算 Im 可使计算的误差减少5倍，因而它对应的算法是数值稳定的算法。,而将公式变为,由:,可取,自n=20计算到n=1,最后得: I0=0.182322,与我们开始计算的I00.182322是一样的,该公式给出的算法就是稳定的,五、简化计算步骤,减小运算次数,避免误差积累,例7：设A、B、C、D分别是

8、1020、 2050、 501、 1100的矩阵，试按不同的算法求矩阵乘积E=ABCD.解：由矩阵乘法的结合律，可有如下算法1. E=(AB)C)D. 计算量N1=11500flop2. E=A(B(CD). 计算量N2=125000flop3. E=(A(BC)D. 计算量N3=2200flop,简化计算步骤是提高程序执行速度的关键，它不仅可以节省时间，还能减少舍入误差。,例6：计算9255的值,9255 = ( 92 )2 )2 )2 ) 2 )2 )2 )2 /9只需8次乘法和1次除法运算。,9255 = 9 92 94 98 916 932 964 9128只需做14次乘法运算即可。,

9、9255 = 9999,但若写成,若逐个相乘要用254次乘法,矩阵乘积AB的计算量分析,a11 a12 a13 a1na21 a22 a23 a2n. . . am1 am2 amm-1 amn,b11 b12 b13 b1sb21 b22 b23 b2s. . . bn1 bn2 bnn-1 bns,=cijms,因为 cij=aik bkj 计算每一个cij的计算量为n所以上面A mn B ns的计算量为N= m n s,计算量：一个算法所需的乘除运算总次数，单位是flop. 计算量也是衡量一个算法好坏的重要标准。,作业：P13 9、12,实验内容 实验1.1、实验 1.2（P1312）,

10、作业：P1213 1、3、 4、6、8,实验1.1（数值微分精度与步长的关系）,实验目的：数值计算中误差是不可避免的，要求通过本实验初步认识数值分析中两个重要概念：截断误差和舍入误差，并认真体会误差对计算结果的影响。,问题提出：设一元函数f :RR，则f在x0的导数定义为:,实验内容:根据不同的步长h可设计两种算法,计算f在x0处的导数,计算一阶导数的算法:,请给出两个计算高阶导数的近似算法,并完成如下工作:,(1),(2),1、对同样的h，比较(1)式和(2)式的计算结果；,2、针对计算高阶导数的算法，比较h取不同值时(1)式和(2)式的计算结果；,实验要求：选择有代表性的函数f (x)（最

11、好多选择几个），利用Matlab提供的绘图工具画出该函数在某区间的导数曲线f (s)(x)，再将数值计算的结果用Matlab 画出来，认真思考实验的结果。,function y=dsh1(fu,x,h)y=(feval(fu,x+h)-feval(fu,x)/h;y,函数文件(扩展名为.m),可以被其命令调用,格式:,function输出参数=函数名(输入参数),可以是多个,函数名,一个,注意:1、保存的文件名与函数名要一致，这样才能保证调用成功；2、调用时的输入输出参数要与函数中的一样；3、养成良好的注释习惯，便于自己或用户调用定义的函数。,注释语句(前面有%)程序语句,function y

12、=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),实验报告要上交，不能有相同的报告。（否则，两个都作废，不予记分）,真解:cos(1)=0.5403ans = 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.5399,dsh1(sin,1,0.0001)y = 0.5403,f(x)=sin(x),-2,2的图形,要求：真解和近似解做在一

13、张图上，近似解的散点图有红色的*表示,便于比较.,h=0.1有偏差,公式1,h=0.1有偏差,dsh2(sin,1,0.1)y = 0.5394,dsh2(sin,1,0.01)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几乎没有偏差,公式2,h=0.01几乎看不出误差,dsh1(sin,1,0.00000001)y = 0.5403,dsh1(

14、sin,1,0.0000000000001)y = 0.5396步长为10-12,dsh1(sin,1,0.00000000000001)y = 0.5440,dsh1(sin,1,0.000000000000001)y = 0.5551,dsh1(sin,1,0.0000000000000001)y = 0步长为10-15,截断误差用我们原有的数学思维方式就比较容易理解的，而舍入误差则是本课程引入的一个新概念。要真正理解舍入误差，特别是它在计算中的传播及最终对计算结果的影响，是初步具备科学计算能力的重要标志。希望大家在完成实验后，认真仔细去体会截断误差和舍入误差的含义及对计算结果的影响。,图

15、,误差,步长h,实验分析：不论采用怎样的算法，计算结果通常都会有误差。比如算法(1)，由Taylor公式，知：,所以有,利用上式来计算f (x0)，其截断误差为：,所以误差是存在的，并且当步长h越来越小时，(1)的近似程度也越来越好。,截断误差,类似地可以分析(2)的截断误差为：,截断误差,上述截断误差的分析表明(2)是比(1)更好的算法，因为对步长h(1)，(2)比(1)更接近于f (x0)。,计算方法的截断误差是数值计算中误差的重要来源，但不是唯一的！如果在实验中确已将h取到足够小的话，特别在高阶导数的计算中，就会发现当h小到一定程度后，计算结果的误差不但不再减少，反而会变大！(参见图),

16、事实上当步长h过小时，计算结果的误差变大就是由于舍入误差的缘故。,截断误差用我们原有的数学思维方式就比较容易理解的，而舍入误差则是本课程引入的一个新概念。要真正理解舍入误差，特别是它在计算中的传播及最终对计算结果的影响，是初步具备科学计算能力的重要标志。希望大家在完成实验后，认真仔细去体会截断误差和舍入误差的含义及对计算结果的影响。,图,误差,步长h,实验1.2（误差传播与算法稳定性）（P13 12题）,实验目的：体会算法的稳定性在选择算法中的地位,问题提出：考虑一个简单的积分序列,n=1,2,显然In0,n=1,2,当n=1时，得：,当n2时，由分部积分可得：,n=2,3,另外，还有：,实验

17、内容：由递推关系In=1-nIn-1，可得计算积分序列In的两种算法：,算法一、直接使用递推公式得：,In=1-nIn-1 n=2,3,算法二、利用递推公式变形得：,实验要求：用上述两种算法分别在计算中采用5位、6位和7位有效数字，请判断哪种算法给出的结果更精确.,实验分析：,两种算法的优劣可能与你的第一感觉完全不同。,设算法一中I1的误差为e1，由I1递推计算In的误差为en,算法二中IN的误差为N，由IN向前递推计算In (nN)的误差为n,如果假定上述两种算法在后面的计算中都不再引入其他误差，则有：,由此可见，算法一中的e1可能很小，但在计算中它的影响急剧扩散，结果真实的数据很快被淹没了

18、；而算法二中的N可能相对比较大，但在计算中误差影响不扩散，即某一步产生误差后，该误差对后面的影响不断衰减。,误差扩散的算法是不稳定的，是我们所不期望的；误差衰减的算法是稳定的，是我们努力寻求的，也是贯穿本课程始终的目标。,熟悉几个必备的matlab命令： 1、help (帮助查找已知命令) 例如：help plot3 (显示命令plot3的功能) 2、lookfor(帮助查找未知命令) 例如：lookfor contour (显示含有contour的所有函数)3、exist(检验函数) exist(A) %A是变量 返回0，代表变量不存在 返回其它数值，变量存在,第一次实验内容,熟悉几个必备的

19、matlab命令： 1、help (帮助查找已知命令) 例如：help plot3 (显示命令plot3的功能) 2、lookfor(帮助查找未知命令) 例如：lookfor contour (显示含有contour的所有函数)3、exist(检验函数) exist(A) %A是变量 返回0，代表变量不存在 返回其它数值，变量存在,作业：P13 9、12,实验内容 实验1.1、实验 1.2（P1312）,作业：P1213 1、3、 4、6、8,老教材,实验1.1（数值微分精度与步长的关系）,实验目的：数值计算中误差是不可避免的，要求通过本实验初步认识数值分析中两个重要概念：截断误差和舍入误差，

20、并认真体会误差对计算结果的影响。,问题提出：设一元函数f :RR，则f在x0的导数定义为:,实验内容:根据不同的步长h可设计两种算法,计算f在x0处的导数,计算一阶导数的算法:,请给出两个计算高阶导数的近似算法,并完成如下工作:,(1),(2),1、对同样的h，比较(1)式和(2)式的计算结果；,2、针对计算高阶导数的算法，比较h取不同值时(1)式和(2)式的计算结果；,实验要求：选择有代表性的函数f (x)（最好多选择几个），利用Matlab提供的绘图工具画出该函数在某区间的导数曲线f (s)(x)，再将数值计算的结果用Matlab 画出来，认真思考实验的结果。,function y=dsh

21、1(fu,x,h)y=(feval(fu,x+h)-feval(fu,x)/h;y,函数文件(扩展名为.m),可以被其命令调用,格式:,function输出参数=函数名(输入参数),可以是多个,函数名,一个,注意:1、保存的文件名与函数名要一致，这样才能保证调用成功；2、调用时的输入输出参数要与函数中的一样；3、养成良好的注释习惯，便于自己或用户调用定义的函数。,注释语句(前面有%)程序语句,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.

22、01),实验报告要上交，不能有相同的报告。（否则，两个都作废，不予记分）,真解:cos(1)=0.5403ans = 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.5399,dsh1(sin,1,0.0001)y = 0.5403,f(x)=sin(x),-2,2的图形,要求：真解和近似解做在一张图上，近似解的散点图有红色的*表示,便于比较.,h=0.1有偏差,dsh2(sin,1,0.1)y = 0.5394,dsh2(sin,1,0.01)y = 0.5403,真解:co

23、s(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几乎没有偏差,dsh1(sin,1,0.00000001)y = 0.5403,dsh1(sin,1,0.0000000000001)y = 0.5396步长为10-12,dsh1(sin,1,0.00000000000001)y = 0.5440,dsh1(sin,1,0.000000000000001)y = 0.5551,dsh

24、1(sin,1,0.0000000000000001)y = 0步长为10-15,真解:cos(1)=05403ans = 0.5403,截断误差用我们原有的数学思维方式就比较容易理解的，而舍入误差则是本课程引入的一个新概念。要真正理解舍入误差，特别是它在计算中的传播及最终对计算结果的影响，是初步具备科学计算能力的重要标志。希望大家在完成实验后，认真仔细去体会截断误差和舍入误差的含义及对计算结果的影响。,图,误差,步长h,实验分析：不论采用怎样的算法，计算结果通常都会有误差。比如算法(1)，由Taylor公式，知：,所以有,利用上式来计算f (x0)，其截断误差为：,所以误差是存在的，并且当步

25、长h越来越小时，(1)的近似程度也越来越好。,截断误差,类似地可以分析(2)的截断误差为：,截断误差,上述截断误差的分析表明(2)是比(1)更好的算法，因为对步长h(1)，(2)比(1)更接近于f (x0)。,计算方法的截断误差是数值计算中误差的重要来源，但不是唯一的！如果在实验中确已将h取到足够小的话，特别在高阶导数的计算中，就会发现当h小到一定程度后，计算结果的误差不但不再减少，反而会变大！(参见图),事实上当步长h过小时，计算结果的误差变大就是由于舍入误差的缘故。,截断误差用我们原有的数学思维方式就比较容易理解的，而舍入误差则是本课程引入的一个新概念。要真正理解舍入误差，特别是它在计算中

26、的传播及最终对计算结果的影响，是初步具备科学计算能力的重要标志。希望大家在完成实验后，认真仔细去体会截断误差和舍入误差的含义及对计算结果的影响。,图,误差,步长h,实验1.2（误差传播与算法稳定性）（P13 12题）,实验目的：体会算法的稳定性在选择算法中的地位,问题提出：考虑一个简单的积分序列,n=1,2,显然In0,n=1,2,当n=1时，得：,当n2时，由分部积分可得：,n=2,3,另外，还有：,实验内容：由递推关系In=1-nIn-1，可得计算积分序列In的两种算法：,算法一、直接使用递推公式得：,In=1-nIn-1 n=2,3,算法二、利用递推公式变形得：,实验要求：用上述两种算法

27、分别在计算中采用5位、6位和7位有效数字，请判断哪种算法给出的结果更精确.,实验分析：,两种算法的优劣可能与你的第一感觉完全不同。,设算法一中I1的误差为e1，由I1递推计算In的误差为en,算法二中IN的误差为N，由IN向前递推计算In (nN)的误差为n,如果假定上述两种算法在后面的计算中都不再引入其他误差，则有：,由此可见，算法一中的e1可能很小，但在计算中它的影响急剧扩散，结果真实的数据很快被淹没了；而算法二中的N可能相对比较大，但在计算中误差影响不扩散，某一步计算产生误差后，该误差对后面的影响不断衰减。,误差扩散的算法是不稳定的，是我们所不期望的；误差衰减的算法是稳定的，是我们努力寻

28、求的，也是贯穿本课程始终的目标。,% 绘制简单的2维图-图3.1% 程序运行后，绘图窗口上出现纵横交叉的两条线，这是% 运行 gtext 的结果。移动鼠标交叉点会随之移动。% 注意程序中 hold 命令是如何使用的 x=-1:0.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,命令文件,