1、3 选用和设计算法时选用和设计算法时应遵循的原则应遵循的原则 一一选用数值稳定的计算公式，控制舍入误差的传选用数值稳定的计算公式，控制舍入误差的传播播三三尽量避免两个相近的数相减尽量避免两个相近的数相减二二尽量简化计算步骤以便减少运算次数尽量简化计算步骤以便减少运算次数四四绝对值太小的数不宜作除数绝对值太小的数不宜作除数五五合理安排运算次序，防止大数合理安排运算次序，防止大数“吃掉吃掉”小数小数2023-4-24第一章 第三节 选用和设计算法时应遵循的原则2一一选用数值稳定的计算公式，控制舍入误差选用数值稳定的计算公式，控制舍入误差的传播的传播 对于一个数值算法，如果原始数据或某对于一个数值算
2、法，如果原始数据或某一步有舍入误差，但在计算过程中，这些误一步有舍入误差，但在计算过程中，这些误差能得到控制（即误差不会放大或不影响结差能得到控制（即误差不会放大或不影响结果的精度要求），则称该数值方法是稳定的；果的精度要求），则称该数值方法是稳定的；否则，若误差在计算中传播使计算结果的误否则，若误差在计算中传播使计算结果的误差增长很快，称它是不稳定的。差增长很快，称它是不稳定的。2023-4-24第一章 第三节 选用和设计算法时应遵循的原则3 例例 计算计算 并估计误差并估计误差.1100 1(,)nxnIex e dx n由分部积分可得计算由分部积分可得计算 的递推公式的递推公式 nI11
3、11001(1,2,8),1.nnxInInIee dxe 算法算法1 先计算先计算 I0，再由上式依次计算，再由上式依次计算 I1,I8.设设 In 的计算值为的计算值为 In*,则则In*=1n In-1*，绝对误差绝对误差 n=1,2,8.为为 E(In*)=In*In =-n(In-1*In-1)=-nE(In-1*)，2023-4-24第一章 第三节 选用和设计算法时应遵循的原则4I0 =1-exp(-1)0.63212055882856,取取I0*=0.6321,记初始误差记初始误差 E(I0*)=I0*I0 =-，则，则E(I1*)=-E(I0*)=，E(I2*)=-2E(I1*
4、)=-2，E(I3*)=-3E(I2*)=3!，E(I8*)=-8!=-40320 -0.83，误差在计算过程中传播，增长很快！误差在计算过程中传播，增长很快！所以，这是一个不稳定的算法。所以，这是一个不稳定的算法。E(In*)=-nE(In-1*)2023-4-24第一章 第三节 选用和设计算法时应遵循的原则5k=9;I=zeros(k,1);I(1)=0.6321;for n=1:k-1I(n+1)=1-n*I(n);endformat long;I算算看：算算看：I8*=-0.72800000000019得到：得到：f=inline(x.8.*exp(x-1);I8=quad(f,0,1
5、)利用利用Matlab数值积分内置函数数值积分内置函数quad检验结果：检验结果：I8=0.10093212627740得到：得到：18180 xIx edx 180()If x dx2023-4-24第一章 第三节 选用和设计算法时应遵循的原则6这样的误差还可以接受。但是若这样的误差还可以接受。但是若k继续增加，继续增加，当当k=19，计算，计算I19*，则误差则误差E(I19*)=-19!=1.216451004088320e+017 足够大，使足够大，使 I19*0.如果就取如果就取 I0*=0.63212055882856,则初始误差则初始误差 回顾：回顾：I0 =1-exp(-1)0
6、.63212055882856,E(I0*)=10-13，E(I8*)=40320 f=inline(x.19.*exp(x-1);I19=quad(f,0,1)利用利用Matlab数值积分内置函数数值积分内置函数quad检验结果：检验结果：I19=0.04772276471237得到：得到：1191190 xIx edx 1190()If x dx2023-4-24第一章 第三节 选用和设计算法时应遵循的原则8怎样计算怎样计算I40？注意到？注意到 0 x 1 时，时，1 ex e,把计算把计算In 的递推公式的递推公式 11nnInI 改写一下，得改写一下，得算法算法2 先计算先计算 I4
7、0，再由上式依次计算，再由上式依次计算 I39,I19.11nnIIn (n=40,39,.,20)111111000,nnxnnex dxIex e dxex edx11111,neInn即即可取可取140182,eI2023-4-24第一章 第三节 选用和设计算法时应遵循的原则9或干脆取或干脆取 400.I设设 In 的计算值为的计算值为 In*,则则In-1*=(1 In*)/n,误差误差 E(In-1*)=In-1*In-1=E(In*)/(-n)，n=40,39,20.若若E(I40*)=,则则E(I19*)=-19!/(40!),初始误差的初始误差的影响逐步减少，到最后甚至可以忽略
8、，算法稳定。影响逐步减少，到最后甚至可以忽略，算法稳定。小结：要小结：要选用数值稳定的计算公式，控制舍入误差选用数值稳定的计算公式，控制舍入误差的传播的传播2023-4-24第一章 第三节 选用和设计算法时应遵循的原则10k=41;I=zeros(k,1);I(1)=0;for n=k:-1:21I(n-1)=(1-I(n)/(n-1);endformat long;I(20)算算看：算算看：I19*=0.04772275579621得到：得到：f=inline(x.19.*exp(x-1);I19=quad(f,0,1)利用利用Matlab数值积分内置函数数值积分内置函数quad检验结果：检
9、验结果：I19=0.04772276471237得到：得到：1191190 xIx edx 1190()If x dx2023-4-24第一章 第三节 选用和设计算法时应遵循的原则11二二尽量简化计算步骤以便减少运算次数尽量简化计算步骤以便减少运算次数例例 计算多项式计算多项式 次乘法和次乘法和 n次加法次加法.若用秦九韶算法（又称若用秦九韶算法（又称Horner算法）算法）1110()nnnnnPxa xaxa xa (1)(1)212n nnn 的值，若直接计算的值，若直接计算 再逐项相加，一共需做再逐项相加，一共需做 2023-4-24第一章 第三节 选用和设计算法时应遵循的原则1210
10、,(1,2,1,0),().nnkkknSaSxSaknPxS 只需做只需做n次乘法和次乘法和n次次加法运算。加法运算。Matlab命令命令horner 将符号多项式表为嵌套形式。将符号多项式表为嵌套形式。12110()()nnnnnPxa xaxaxa 231210()nnnna xaxaxaxa 1210()nna xaxaxaxa 2023-4-24第一章 第三节 选用和设计算法时应遵循的原则13三三尽量避免两个相近的数相减尽量避免两个相近的数相减(减法减法)要尽量避免两个相近的数相减，损失有效位数。要尽量避免两个相近的数相减，损失有效位数。1000,1?xxx 四则运算中的稳定性问题四
11、则运算中的稳定性问题 如如若取若取4位位有效数字计算，则有效数字计算，则131.6431.620.02.xx这个结果只有这个结果只有1位位有效数字计算，损失了有效数字计算，损失了3位位有效数字，严重影响了计算结果的精度。有效数字，严重影响了计算结果的精度。2023-4-24第一章 第三节 选用和设计算法时应遵循的原则1421cos2sin (|1)2xxx 如果改变计算公式，避免两个相近的数相减，如果改变计算公式，避免两个相近的数相减，110.01581.1xxxx它仍它仍有有4位有效数字。位有效数字。又如又如在实验课上，用在实验课上，用Matlab运运行此例，结果如何？行此例，结果如何？在在
12、16位，位，32位或位或64位计算机上，举出合适例子，位计算机上，举出合适例子，说明以上问题，并在实验课上，用说明以上问题，并在实验课上，用Matlab运运行。行。2023-4-24第一章 第三节 选用和设计算法时应遵循的原则15四四绝对值太小的数不宜作除数绝对值太小的数不宜作除数(除法除法)3.1416 3141.60.001 如如：分母稍微改变：分母稍微改变：0.0010.00113.1416 28560.0011 如如：在实验课上，用在实验课上，用Matlab运运行此例，结果如何？行此例，结果如何？不仅要尽量避免两个相近的数相减，还要特别不仅要尽量避免两个相近的数相减，还要特别注意避免再
13、用这个差作除数。注意避免再用这个差作除数。2023-4-24第一章 第三节 选用和设计算法时应遵循的原则16（加法）（加法）要防止大数吃掉小数：注意数据排列顺序。如：要防止大数吃掉小数：注意数据排列顺序。如：a=1012,b=10,c=-a，八位计算机上八位计算机上:(a+b)+c=0，应该用：应该用：(a+c)+b=10五五合理安排运算次序，防止大数合理安排运算次序，防止大数“吃掉吃掉”小小数数在实验课上，用在实验课上，用Matlab运运行此例，结果如何？行此例，结果如何？在在16位，位，32位或位或64位计算机上，举出合适例子，位计算机上，举出合适例子，说明以上问题，并在实验课上，用说明以上问题，并在实验课上，用Matlab运运行。行。
