西华师范大学：《算法与程序设计》课程教学资源_第一章 误差（1.3）算法选择

§1-3算法选择 1、正确性:阶段误差不超过用户指定的误 差限;算法稳定;不溢出。 例1.计算定积分 xexi=0,1,2,…7 1 解: x de d e x e ax =1-nl 如果先计算,然后再计算1l2…,l7

§ 1-3 算法选择 1、正确性：阶段误差不超过用户指定的误 差限；算法稳定；不溢出。 例1.  = 1 0 1 x e dx e I n x n 计算定积分 i = 0,1,2,  ,7 n 解 I :  = 1 0 1 n x x de e 1 0 1 n x x e e =  − − 1 0 1 x e dx e n n x = 1−nIn−1 , 0 如果先计算I 1 2 7 然后再计算I ,I ,  ,I

假设计算出l的近似值为,误差为E(l0)=6 则I的近似值/的误差为E(l1)=δ l2的近似值2的误差为E(l2)=26 3的近似值3的误差为E(I3)=38 l的近似值2的误差为E(l)=76=50406 1-1 但如果利用递推公式1, h-1 先计算l,l的误差只有误差的5千分之

, * 0 0 假设计算出I 的近似值为I ( ) =  * 0 误差为E I ( ) =  * 1 * 1 1 则I 的近似值I 的误差为E I ( ) 2 * 2 * I 2 的近似值I 2 的误差为E I = ( ) 3! * 3 * I 3 的近似值I 3 的误差为E I =  ( ) 7! * 7 * I 7 的近似值I 7 的误差为E I = = 5040 n I I n n − − = 1 但如果利用递推公式 1 , 7 先计算I 5 ! I 0 的误差只有I 7 误差的 千分之一

2、高效性 编写程序时,尽量选用高效率的算法,即选用 复杂性低的算法。 例2已知l12l2都是n维向量,I是n阶单位矩阵,求 (-24X-2242)kx 编写程序时,若计算过程为: S1:计算(-2u4),将结果存入二维数组A中 S2:计算(-242),将结果存入二维数组B中 S3:计算AB,存入二维数组C中 S4:计算Cx 该算法的复杂性为n次乘法(S3的计算量)

2、高效性 编写程序时，尽量选用高效率的算法，即选用 复杂性低的算法。 例2 已知 1 2 u ,u 都是n维向量，I是n阶单位矩阵，求 y (I u u )(I u u )x T T = − 2 1 1 − 2 2 2 编写程序时，若计算过程为： S1：计算 ，将结果存入二维数组A中 S2：计算 ，将结果存入二维数组B中 S3：计算AB,存入二维数组C中 S4：计算Cx 该算法的复杂性为 次乘法（S3的计算量） ( ) T I − 2u1 u1 ( ) T I − 2u2 u2 3 n

若令 y1=(-2l22)k=x-2(2x2 此时程序的计算量为4n次乘法,计算法的复杂性 为4n次乘法

若令 此时程序的计算量为4n次乘法，计算法的复杂性 为4n次乘法。 ( ) ( ) ( ) ( ) 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 y I u u y y u y u y I u u x x u x u T T T T = − = − = − = −