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

《1.3 选用算法时应遵循的原则》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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)/2x2=(105-(1010-4

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

3、9(有舍入)B=0.0003×0.0125×0.0135=0.00000375×0.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.144000c=0.0012/0.0135=0.088889(有舍入)D=a×b×c=1.666667×1.144000×0.088889=0.169482，准确到小数后5位。bca计算方法（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-2an-1xn-3…a2)xa1）xa0=(…(anxan-1)x…a2)xa1)xa0写成递推公式计算方法于是,这种多项式求值的算法称为秦九韶算法,只做n次乘法和n次

5、加法,程序实现简单计算方法（5）选用数值稳定性好的公式，以控制舍入误差的传播对于一个数学问题的求解往往有多种数值方法在选择数值方法时，要注意所用的数值方法不应将计算过程中难以避免的误差放大的较快，造成计算结果完全失真。计算方法例13计算积分并估计误差。解容易得到递推公式计算方法即为计算方法则准确的理论递推式实际运算的递推式两式相减有计算方法这就是说,若与的误差为=-,即，则误差的递推规律为于是计算方法计算时的误差被扩大了倍,显然算法是数值不稳定的。如果将递推公式变换一种形式计算方法准确的理论递推式实际运算的递推式从而有即计算方法于是有则这个算法的误差传递规律为即

6、每计算一步的误差的绝对值是上一步的十分之一，误差的传播逐步缩小，得到很好的控制，这个算法是数值稳定的。