二、数值计算中的一些基本原则 避免绝对值小的数作除数 避免两个相近的数据相减 要防止大数“吃掉”小数 尽量减少计算工作量 选用数值稳定性好的算法 1/13
1/13 § 避免绝对值小的数作除数 § 避免两个相近的数据相减 § 要防止大数“吃掉”小数 § 尽量减少计算工作量 § 选用数值稳定性好的算法 二、数值计算中的一些基本原则
避免绝对值小的数作除数 这一原则主要指尽量避免除数绝对值远远小于被除数 绝对值的除法。 设z=y/x(x≠0),如果x的绝对值远小于y的绝 对值,由于 ε(')≈x|s(y)+|ys(x) IxP 兴片 2/13
2/13 § 避免绝对值小的数作除数 这一原则主要指尽量避免除数绝对值远远小于被除数 绝对值的除法。 设 ( x≠0),如果 x 的绝对值远小于 y 的绝 对值,由于 z y x 2 | | | | ( ) | | ( ) ( ) x x y y x x y ( ) | | | | | | ( ) 2 x x y x y
避免两个相近的数据相减 如果y≈x,现分析两个数的近似数作减法所得结果的 误差.设=y一x,则利用误差估计 E(z)=8(y)+E(x) 有相对误差估计 当y≈x时,有0,计算结果的相对误差限可能很大, 导致数值计算结果的有效数字位数减少。 3/13
3/13 § 避免两个相近的数据相减 如果 y ≈ x,现分析两个数的近似数作减法所得结果的 误差. 设 z= y – x,则利用误差估计 (z) ( y ) ( x ) ( ) | | | | ( ) | | | | | ( ) x z x y z y z r r r 有相对误差估计 当 y ≈ x 时,有 z≈0,计算结果的相对误差限可能很大, 导致数值计算结果的有效数字位数减少
要防止大数“吃掉”小数 一个绝对值很大的数和一个绝对值很小的数直接相加 时,很可能发生所谓“大数吃小数”的现象。 例如,a=1013,b=4,设想这两个数在具有12位浮点数 计算机系统(12位有效位数系)中相加 a+b=1013+4=1.0000000000000×1013 +0.0000000000004×1013 实际加法操作如下 1.000000000000×1013+0.000000000000×1013 =1.000000000000×1013 4/13
4/13 § 要防止大数“吃掉”小数 一个绝对值很大的数和一个绝对值很小的数直接相加 时,很可能发生所谓“大数吃小数”的现象。 例如,a= 10 13,b= 4,设想这两个数在具有12位浮点数 计算机系统(12位有效位数系)中相加 a + b = 1013 + 4 = 1. 0000000000000 ×1013 +0. 0000000000004 ×1013 实际加法操作如下 1. 00000000000 0 ×1013 + 0. 00000000000 0 ×1013 = 1. 00000000000 0 ×1013
二、数值计算中的一些基本原则 尽量减少计算工作量 在考虑算法时应注意简化计算步骤,减少运算次数 计算工作量小的算法不仅节约运行时间,而且使误差 积累小。 例2设计算法用于计算多项式 P (x)=ao+ax+ax+...+ax" 5/13
5/13 § 尽量减少计算工作量 二、数值计算中的一些基本原则 在考虑算法时应 简化计算步骤,减少运算次数 。 n Pn x a a x a x an x 2 0 1 2 ( ) 计算工作量小的算法不仅节约运行时间,而且使误差 积累小。 例2 设计算法用于计算多项式
·尽量减少计算工作量 Pn(x)=ao+ax+a2x2++anx" 算法一: SSk-1+ax,(k=1,2,,n) (x)=S 这种算法计算复杂性怎么样? xk=x.xk-1 计算一个n次多项值需要用2n-1次乘法。 这种算法是否是最优的呢? 6/13
6/13 § 尽量减少计算工作量 S 0 = a0 , Sk = Sk-1 + ak xk ,( k= 1,2,…,n ) P n(x)= S n 计算一个 n 次多项值需要用 2n-1 次乘法。 这种算法计算复杂性怎么样? 算法一: n Pn x a a x a x an x 2 0 1 2 ( ) 1 k k x x x
·尽量减少计算工作量 秦九 另一种典型算法是秦九韶算法 P(x)=4+4x+42x2+4x3+ax =+x(41+x(42+x(4+x44)》 算法二: S=an Sk-1=ak-1+xSk 、(k=n,n一1,..,1)) P.(x)=S 计算一个n次多项值需要用n次乘法。 7/13
7/13 § 尽量减少计算工作量 S n = a n, Sk-1 = a k -1+ xSk,(k= n,n-1,…,1), P n(x)= S0 另一种典型算法是 算法 计算一个 n 次多项值需要用 n 次乘法。 ( ( ( ))) ( ) 0 1 2 3 4 4 4 3 3 2 4 0 1 2 a x a x a x a xa P x a a x a x a x a x 算法二:
选用数值稳定性好的算法 不同的算法在执行过程中对数据误差的影响是不一样 的。舍入误差对计算结果影响不大的算法被称为数值 稳定的算法 例3利用递推式计算定积分 1n=e∫x"e (=0,1,2,,20)的值。 8/13
8/13 § 选用数值稳定性好的算法 不同的算法在执行过程中对数据误差的影响是不一样 的。舍入误差对计算结果影响不大的算法被称为数值 稳定的算法. I e x e dx n n x 1 0 1 例3 利用递推式计算定积分 ( n= 0, 1, 2, …, 20 )的值。 1 0 1 I e x e dx n x n
算法一: I,e-(x"e-nfx"le"e)=1-n1 其中 I=ee"dx=e"(e-1)=1-e 得递推关系式 I。=1-e-1 In=1-nlm-1(n=1,2,…) 利用递推式可得20个数据如下表: 9/13
9/13 得递推关系式 1 ,( 1,2, ) 1 1 1 0 I nI n I e n n 算法一: 1 1 0 1 1 0 1 ( ) 1 n n x n x I n e x e n x e dx nI 1 1 1 0 1 0 ( 1) 1 I e e dx e e e 其中 x 利用递推式可得20个数据如下表:
S 0.36787944117144 0.07735222935878 S2 0.26424111765712 0.07177324769464 0.20727664702865 0.06694777996972 S 0.17089341188538 S14 0.06273108042387 0.14553294057308 S1 0.05903379364190 0.12680235656152 S16 0.05545930172957 S1 0.11238350406936 0.05719187059731 0.10093196744509 S18 -0.02945367075154 0.09161229299417 1.55961974427919 S四 0.08387707005829 -30.19239488558378 对积分值有估计式: e 10/13
10/13 1 (max ) 1 0 1 0 1 0 n e x e dx e x dx x n x n n S 1 0. 36787944117144 S 11 0. 07735222935878 S 2 0. 26424111765712 S 12 0. 07177324769464 S 3 0. 20727664702865 S 13 0. 06694777996972 S 4 0. 17089341188538 S 14 0. 06273108042387 S 5 0. 14553294057308 S 15 0. 05903379364190 S 6 0. 12680235656152 S 16 0. 05545930172957 S 7 0. 11238350406936 S 17 0. 05719187059731 S 8 0. 10093196744509 S 18 -0. 02945367075154 S 9 0. 09161229299417 S 19 1. 55961974427919 S 10 0. 08387707005829 S 20 -30. 19239488558378 对积分值有估计式: 1 1 1 1 0 1 1 n e x e dx n e n x