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

《选用算法时应遵循的原则.ppt》由会员分享，可在线阅读，更多相关《选用算法时应遵循的原则.ppt（19页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、3 3 选用算法时应遵循的原则选用算法时应遵循的原则 误差是用来衡量数值方法好与坏的重要标志误差是用来衡量数值方法好与坏的重要标志 为此对每一个算法都要进行误差分析。为此对每一个算法都要进行误差分析。(1)(1)两个相近的数相减，会严重损失有效数字两个相近的数相减，会严重损失有效数字 例如例如x=1958.75=1958.75，y=1958.32=1958.32都具有五位都具有五位 有效数字，但有效数字，但x-y=0.43=0.43只有两位有效数字只有两位有效数字 通常采用的方法是改变计算公式通常采用的方法是改变计算公式,例如当与例如当与 很接近时很接近时,由于由于计算方法计算方法计算方法计算

2、方法用右端代替左端公式计算用右端代替左端公式计算,有效数字就不会损失。有效数字就不会损失。计算方法计算方法当当x很大时可作相应的变换很大时可作相应的变换 则用右端来代替左端。则用右端来代替左端。计算方法计算方法（2 2）防止大数）防止大数“吃掉吃掉”小数小数例例 求二次方程求二次方程x2-105x+1=0的根的根 解：按二次方程求根公式解：按二次方程求根公式 x1=(105+(1010-4)1/2)/2 x2=(105-(1010-4)1/2)/2 在在8 8位浮点数计算得位浮点数计算得 x1=(105+105)/2=105 (正确）正确）,x2=(105-105)/2=0 (错误）错误）计算

3、方法计算方法产生错误的原因产生错误的原因 出现大数出现大数 吃掉小数吃掉小数4 4的情况的情况 分子部分出现两个相近数相减而丧失有效数位常分子部分出现两个相近数相减而丧失有效数位常称为灾难性的抵消称为灾难性的抵消计算方法计算方法（3）绝对值太小的数不宜做除数绝对值太小的数不宜做除数当分母为两个相近数相减时当分母为两个相近数相减时,会丧失有效数字会丧失有效数字这里分子的误差被扩大这里分子的误差被扩大104104倍倍,再如再如若将分母变为若将分母变为0.0011,0.0011,即分母只有即分母只有0.00010.0001的变化时的变化时,计计算结果却有了很大变化算结果却有了很大变化 计算方法计算方

4、法 解解:分子分母分别计算后相除分子分母分别计算后相除(取取9位小数位小数)A=0.00050.01430.0012=0.000007150.0012 =0.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=

5、0.0143/0.0125=1.144000 c=0.0012/0.0135=0.088889(有舍入有舍入)D=abc=1.666667 1.144000 0.088889=0.169482，准确到小数后，准确到小数后5位。位。bca计算方法计算方法（4 4）简化计算步骤，减少运算次数）简化计算步骤，减少运算次数 x255255=xx2 2x4 4x8 8x1616x3232x6464x128128 原先要做原先要做254254次乘法现只需次乘法现只需1414次即可次即可 又如计算多项式又如计算多项式 p(x)=)=an nxn n an-1n-1xn-1 n-1 a1 1x a0 0 的值

6、的值 若直接计算若直接计算ak kxk,再逐项相加，一共要做再逐项相加，一共要做 n+(+(n-1)+-1)+2+1=+2+1=n(n+1)/2+1)/2次乘法和次乘法和n次加法次加法 计算方法计算方法如果将前如果将前n项提出项提出x，则有，则有 p(x)=)=（an nxn-1n-1 an-1n-1xn-2 n-2 a1 1）x a0 0 =(=(an nxn-2n-2 an-1n-1xn-3n-3 a2 2)x a1 1）x a0 0 =(=(an nx an-1n-1)x a2 2)x a1 1)x a0 0写成递推公式写成递推公式 计算方法计算方法于是于是 ,这种多项式求值的算法称为秦

7、这种多项式求值的算法称为秦九韶算法九韶算法,只做只做n次乘法和次乘法和n次加法次加法,程序实现简程序实现简单单 计算方法计算方法 （5 5）选用数值稳定性好的公式，以控制舍入误）选用数值稳定性好的公式，以控制舍入误差的传播差的传播 对于一个数学问题的求解往往有多种数值方法对于一个数学问题的求解往往有多种数值方法在选择数值方法时，要注意所用的数值方法不应将在选择数值方法时，要注意所用的数值方法不应将计算过程中难以避免的误差放大的较快，造成计算计算过程中难以避免的误差放大的较快，造成计算结果完全失真。结果完全失真。计算方法计算方法例例13 13 计算积分计算积分 并估计误差。并估计误差。解解 容易

8、得到递推公式容易得到递推公式计算方法计算方法即即 为为 计算方法计算方法则准确的理论递推式则准确的理论递推式 实际运算的递推式实际运算的递推式 两式相减有两式相减有 计算方法计算方法这就是说这就是说,若若 与与 的误差为的误差为 =-,=-,即即 ，则误差的递推规律为，则误差的递推规律为 于是于是 计算方法计算方法计算计算 时的误差被扩大了时的误差被扩大了 倍倍,显然算法是数值不显然算法是数值不稳定的。稳定的。如果将递推公式如果将递推公式变换一种形式变换一种形式计算方法计算方法准确的理论递推式准确的理论递推式实际运算的递推式实际运算的递推式从而有从而有 即即计算方法计算方法于是有于是有则这个算法的误差传递规律为则这个算法的误差传递规律为 即每计算一步的误差的绝对值是上一步的十分即每计算一步的误差的绝对值是上一步的十分之一，误差的传播逐步缩小，得到很好的控制，这之一，误差的传播逐步缩小，得到很好的控制，这个算法是数值稳定的个算法是数值稳定的 。