第三节 数值计算中需要注意的问题

1、数学学院 信息与计算科学系 第三节第三节 设计算法时应注意的原则设计算法时应注意的原则 一、简化计算步骤一、简化计算步骤, 减少运算次数减少运算次数 计算多项式的值计算多项式的值: 0 ( ) n k nk k Pxa x 每项每项 ak xk 有有k 次乘法运算次乘法运算, 因此计算因此计算 Pn (x) 共需共需 1 1 2 2 n n n 次乘法和次乘法和n 次加法运算。次加法运算。 如将如将 Pn (x) 写成写成: 1210nnnn Pxa xaxaxaxa 例例1 数学学院 信息与计算科学系 用递推算法用递推算法: 01 , , 1,2, . nkkn k uauuxakn 最终最

2、终 Pn (x)=un 共需共需n 次乘法和次乘法和n 次加法运算。次加法运算。 一般地要注意一般地要注意: 能在循环外计算能在循环外计算, 就不要放在循环就不要放在循环 内计算。内计算。 1210nnnn Pxa xaxaxaxa 数学学院 信息与计算科学系 二、二、 注意避免两个相近数的相减注意避免两个相近数的相减 如用四位有效数字计算如用四位有效数字计算: 例例2 17013 13.04 13 0.04 结果只有一位有效数字；结果只有一位有效数字； 两个相近的数相减两个相近的数相减, 有效数字会大大损失。有效数字会大大损失。 170130.0384048 如改为：如改为： 11 1701

3、30.03840 13.041317013 有四位有效数字有四位有效数字, 新算法避免了两个相近数的相减。新算法避免了两个相近数的相减。 数学学院 信息与计算科学系 三、防止大数三、防止大数 “吃掉吃掉” 小数小数 例例3 解解 用五位十进制计算机进行计算用五位十进制计算机进行计算: 0.1被大数被大数“吃掉吃掉”了了,从而从而 有有 1000 1 524920.152492 i 55 5 524920.10.52492 100.000001 10 0.52492 10 1000 1 524920.1 i 计算计算 数学学院 信息与计算科学系 如改为如改为 0.1 就没有被吃掉。就没有被吃掉。

4、 这也是构造算法时要注意的问题这也是构造算法时要注意的问题, 避免重要的参数避免重要的参数 被吃掉。被吃掉。 1000 1 0.15249210052492 i 55 5 0.01 100.52492 10 0.52502 1052505 1000 1 524920.1 i 数学学院 信息与计算科学系 四、避免除数的绝对值远小于被除数的绝对值四、避免除数的绝对值远小于被除数的绝对值 当当| x | y | 时时, 舍入误差会扩大舍入误差会扩大 例例4 73 11 2 14 100.510 1 510 10 xx x x 很小的数作除数有时还会造成计算机的溢出而停机。很小的数作除数有时还会造成计

5、算机的溢出而停机。 3 0.510 的舍入误差均为的舍入误差均为 , 而而 的舍入误差为的舍入误差为:,则则 7 10 xy y x 2 )()()(yxyyxyx yx , 数学学院 信息与计算科学系 五、使用数值稳定的算法五、使用数值稳定的算法 用分部积分公式得递推用分部积分公式得递推 公式公式: 例例5 1 1 0 ,0,1,2, nx n Ix edxn In=1-nIn-1 , 在运算过程中在运算过程中,舍入误差能控制在某个范围内的算法舍入误差能控制在某个范围内的算法 称为称为数值稳定的算法数值稳定的算法,否则就称为否则就称为不稳定的算法不稳定的算法. 用四位有效数字计算用四位有效数

6、字计算: 近似值近似值 的递推公式的递推公式: n I ,1 1 nn nII 误差误差 的递推公式的递推公式:)( n Ie , )()( 1 nn IneIe 0 1 1 0 1 0 6321. 0 1 I edxeI x 数学学院 信息与计算科学系 算法算法 一一 代入得下表代入得下表 1 1 0 ,0,1,2, nx n Ix edxn 于是于是 与精确值已经面目全非。与精确值已经面目全非。 87 ,II 0 1 0 6321. 01IeI 5 6 7 8 9 n 0.1408 0.1120 0.2180 -0.7280 7.5520 0.14553 0.12680 0.11238 0

7、.10093 0.09161 0.6321 0.3678 0.2642 0.2074 0.1704 0.63212 0.36787 0.26424 0.20727 0.17089 0 1 2 3 4 近似值近似值 精确值精确值 In 近似值近似值精确值精确值 In n n I n I ,1 1 nn nII 数学学院 信息与计算科学系 4 0 105 . 0)( Ie 算法一算法一 )()( 1 nn IneIe 由于计算由于计算 有误差有误差 0 I 0 1 0 6321. 01IeI 不计中间再产生的舍入误差不计中间再产生的舍入误差 )(!)( 0 IenIe n 40320!8)( 8

8、Ie 到到 I8 时时 误差扩大了误差扩大了4万倍万倍, 因而该算法是不稳定的。因而该算法是不稳定的。 ,1 1 nn nII 数学学院 信息与计算科学系 可以估计出可以估计出 故故 1 1 0 11 n e I nn 1 1 0 ,0,1,2, nx n Ix edxn 算法二算法二 误差误差 nIeIe nn )()( 1 1111. 0409. 01250. 04046. 0 87 II nII nn )1( 1 则则 如果递推式改为如果递推式改为 In-1 =(1-In )/n 数学学院 信息与计算科学系 由由 列表如下列表如下,)1(,1000. 0 19 nIII nn 4 3 2 1 0 n 0.1709 0.2073 0.2642 0.3679 0.6321 0.17089 0.20272 0.26424 0.36787 0.63212 0.1000 0.1000 0.1125 0.1268 0.1455 0.09161 0.10093 0.11238 0.12680 0.14553 9 8 7 6 5 近似值近似值精确值精确值 In 近似值近