1.3 选用算法时应遵循的原则.ppt

1、,3 选用算法时应遵循的原则,误差是用来衡量数值方法好与坏的重要标志 为此对每一个算法都要进行误差分析。 (1)两个相近的数相减，会严重损失有效数字 例如x =1958.75，y =1958.32都具有五位 有效数字，但x-y=0.43只有两位有效数字 通常采用的方法是改变计算公式,例如当与 很接近时,由于,计算方法,计算方法,用右端代替左端公式计算,有效数字就不会损失。,计算方法,当x很大时可作相应的变换,则用右端来代替左端。,计算方法,（2）防止大数“吃掉”小数 例 求二次方程x2-105x+1=0的根 解：按二次方程求根公式 x1=(105+(1010-4)1/2)/2 x2=(105-

2、(1010-4)1/2)/2 在8位浮点数计算得 x1=(105+105 )/2=105 (正确）, x2=(105-105 )/2=0 (错误）,计算方法,产生错误的原因, 出现大数 吃掉小数4的情况 分子部分出现两个相近数相减而丧失有效数位常称为灾难性的抵消,计算方法,（3）绝对值太小的数不宜做除数 当分母为两个相近数相减时,会丧失有效数字,这里分子的误差被扩大104倍,再如 若将分母变为0.0011,即分母只有0.0001的变化时,计算结果却有了很大变化,计算方法,解: 分子分母分别计算后相除(取9位小数),A=0.00050.01430.0012=0.000007150.0012 =0

3、.000000009(有舍入),B=0.00030.01250.0135=0.000003750.0135 =0.000000051(有舍入),D=A/B=0.17647,真值为0.16948148，所以D只准确到小数后一位,例： 计算,计算方法,算法2。分成三组因子。每组只取六位小数计算 a=0.0005/0.0003=1.666667(有舍入) b=0.0143/0.0125=1.144000 c=0.0012/0.0135=0.088889 (有舍入) D=abc=1. 666667 1.144000 0.088889 =0.169482，准确到小数后5位。,计算方法,（4）简化计算步骤

4、，减少运算次数 x255=xx2x4x8x16x32x64x128 原先要做254次乘法现只需14次即可 又如计算多项式 p(x)=anxn an-1xn-1 a1x a0 的值 若直接计算akxk,再逐项相加，一共要做 n+(n-1)+2+1=n(n+1)/2次乘法和n次加法,计算方法,如果将前n项提出x，则有 p(x)=（anxn-1 an-1xn-2 a1 ）x a0 =(anxn-2an-1xn-3 a2)xa1）x a0 =(anx an-1)xa2)x a1)x a0 写成递推公式,计算方法,于是 ,这种多项式求值的算法称为秦九韶算法,只做n次乘法和n次加法,程序实现简单,计算方法,（5）选用数值稳定性好的公式，以控制舍入误差的传播 对于一个数学问题的求解往往有多种数值方法在选择数值方法时，要注意所用的数值方法不应将计算过程中难以避免的误差放大的较快，造成计算结果完全失真。,计算方法,例13 计算积分 并估计误差。 解 容易得到递推公式,计算方法,即 为,计算方法,则准确的理论递推式 实际运算的递推式 两式相减有,计算方法,这就是说,若 与 的误差为 = - ,即 ，则误差的递推规律为,于是,计算方法,计算 时的误差被扩大了 倍,显然算法是数值不稳定的。,如果将递推公式 变换一种形式,计算方法,准确的理论递推式 实际运算的递推式 从而有,即