数学技术之算法概论篇（2）

③ 误差及其计算传播
用计算机求解一个实际问题，从实际问题提出到上机求解、给出计算结果，以数值计算为例，通常须经历以下过程：

经上述过程给出的计算结果，多数情况下只是实际问题相应未知真值的一个近似值，存在误差。计算前、计算中和计算结果处理，不可避免的会出现各种各样的、大大小小的误差。因此，误差成了算法中经常遇到和需要深入研究的一个问题。
算法中的误差论，研究计算机上算法中的误差来源、性质和分类，误差的传播规律，误差影响，误差分析方法和估算误差影响的理论等，为算法研究的基础理论之一。
对输入到计算机中数据的初始误差、引进数学模型中形成的误差、计算过程中出现的各种误差和结果误差进行分类，对各类误差及其关系进行研究和分析，对计算过程中误差的传播和对计算结果的影响进行探讨，从而对所用数值方法的误差上限给出可用的估计，以得到这一算法是否可行、计算结果是否可用或对其改进的可能等进行深入研讨，发现其规律性，探索进一步可采用的新方法和研发的新途径等，这许多方面的研究及其成果就构成了我们所说的算法中的误差论。
常用的误差分析方法有一般误差分析、特殊误差分析、误差定性分析、误差定量分析、向前误差分析、向后误差分析、随机误差分析、区间误差分析等。一般误差分析只分析误差的通用规律性，如误差的数字特征、分布特征及其性态，误差传播的一般规律性，给出最后误差的上限等；特殊误差分析法分析一类数据或算法的误差特性，给出最后误差的上限，如计算机浮点数算术运算的舍入误差分析、线代数方程组迭代解法的误差分析等。

一、真值与误差

真值：所谓“真值”即真实值，是在一定条件下的实际值，通常是未知量，有理论真值、规定真值和相对真值之分。
理论真值：理论真值又称绝对真值，如平面三角形三内角之和恒为180 。
规定真值：国际上公认的某些基准量值，如1982年国际计量局召开的米定义咨询委员会提出米的定义为“米等于光在真空中1／299792458秒时间间隔内所经路径的长度”。这个米基准就当作计量长度的规定真值。规定真值也称约定真值。
相对真值：计量器具按精度不同分为若干等级，上一等级的指示值即为下一等级的真值，此真值称为相对真值。如在力值的传递标准中，用二等标准测力计校准三等标准测力计，此时二等标准测力计的指示值即为三等标准测力计的相对真值。
误差：数值结果x与其相应真值x^*之差

E=x–x^*

称为误差。

二、误差分类

计算机计算中出现的误差种类繁多，常见的有初始误差，即输人计算机内的近似值和其相应真值之差；输入误差，即计算机上输入数据中出现的误差（如用有限小数表示1/3、用有限位二进制数表示1/10等产生的误差）；舍入误差，因应用需要和计算机字长的限制，把位数较多的数用位数较少的数代替原数而产生的误差；数据误差，数学模型中所含参数的误差，这些参数可能是观测得到的，含观测误差，也可能是计算得到的，含计算误差等；由于数学模型的局限与近似等原因产生的模型误差，经离散化处理后出现的离散化误差，经逼近处理后出现的逼近误差，为简化计算、用近似表达式代替精确表达式出现的截断误差等等。
由观测工具不准确和随机干扰等诸多因素引起的观测误差，含系统、随机和疏失等误差项：观测误差中的系统误差是由于仪器本身不精确、或实验方法粗略、或实验原理不完善而产生的误差；偶然误差是由各种偶然因素对实验者、测量仪器、被测物理量的影响而产生的；过失误差会明显地歪曲试验结果，如测错、读错、记错、传错或计算错等。含有过失误差的测量数据是不能采用的，必须利用一定的准则从测得的数据中剔除或修正。因此，在进行误差分析时，只考虑系统误差与随机误差。
在应用中，按误差的性质，可分为绝对误差和相对误差两种。
绝对误差与误差限：设x^*是精确值，x是它的一个近似值，称

e=｜x-x^*｜

为近似值x的绝对误差，简称误差。误差e的上界 ，即 x-x^* ≤ ，称为近似值x的误差限。
相对误差与相对误差限：误差e与精确值的比值

e/x^*= x-x^* /|x|

称为近似值x的相对误差(显然，此时要求x^*不为零)。相对误差不仅表示测量的绝对误差，而且能反映出测量时所达到的精度。

三、有效数字

如果近似值x的误差限 是它某一个数位的半个单位，x准确到该位。从这一位起到前面第一个非0数字位置的所有数字称为x的有效数字。如有x= a₁a₂a₃…a_n时，其中a₁、a₂、a₃、…、a_n是0-9之中的自然数，且a₁≠0，称其有n位精度。

四、数值计算时的误差传播

在计算机上进行数值计算时，带有误差的数据会将所含的误差在以后计算中进行转移、扩散和发展等，谓之误差传播。在四则运算、函数计算等各类算法中误差传播具有如下的一些公式：
四则运算中的误差传播公式
e（x₁+x₂）=e（x₁）+e（x₂）；
e（x₁*x₂）=|x₁|e（x₁）+|x₂|e（x₂）；
e（x₁/x₂）=[|x₁|e（x₁）+|x₂|e（x₂）|]/|x₂|²。
函数f(x)的误差限：|e（f（x））|≤ f′(x) e（x）。

五、数值计算中应注意几个问题

在计算机上进行数值计算时，必须考虑参与计算的数受计算机字长有限和数值计算中的误差及其传播和累积等许多方面的问题。特别是以下几点，应给予更多的关照：
1.使用数值稳定的算法，即在运算过程中四舍五入误差不增加或增加比较慢的算法；
2.防止两个相近数的相减，降低有效数字的损失；
3.简化计算步骤，降低运算次数；
4.避免除数的绝对值远小于被除数的绝对值；
5.防止大数“吃掉”小数。如大小相差很大的两个数间进行加法运算，因计算机上采用高阶对位，很小的数和很大的数相比进行高阶对位时变为0，俗称“大数‘吃掉’小数”。

六、误差分析

在计算机进行计算时，为保证计算的有效性和可用性，要对计算中出现的各种误差进行分析，其中包括一般误差分析（分析误差的通用规律性，如误差的数字特征，分布特征及其性态，误差传播的一般规律性，给出最后误差的上限等）和特殊误差分析（分析一类数据或算法的误差特性，给出最后误差的上限，如计算机浮点数算术运算的舍入误差分析，线代数方程组迭代解法的误差分析等），误差定性分析（对一类算法计算中的误差进行“质”方面的分析，揭示误差传播的内在规律，给出该算法是否可用的定性描述）和误差定量分析（建立数学模型，依据统计数据，计算出分析对象的各项误差指标及其数值大小，给出该算法是否可用的定量描述）。误差分析方法也很多，常见的有向前误差分析和向后误差分析，区间误差分析和概率误差分析等。
④ 公式及其数值运算
数学上的公式运算和计算机上数学公式的具体数值计算有许多不同，主要表现有：
1．在计算机上，可以通过算法设计，用不同的算法实现数学上同一计算公式的数值计算；不同的算法，计算速度和计算结果精度有时会有显著的不同。
2．数学公式中的加、减、乘、除运算，不考虑实施具体数值计算时，和数的排序无关，和数列的长度无关；在计算机上实施实际数值运算时，由于字长有限和舍入误差的影响，既和数的排序有关，又和数列的长度有关。
3．在数学上，不涉及真正的实际计算时，不考虑加、减、乘、除运算的速度；计算机上的数值运算，特别是核心运算部分，涉及到算法的时间复杂度，要考虑加、减、乘、除的运算速度，如加、减的运算速度相近，乘法速度次之，除法最慢。因此，在程序设计中，常用a+a代替2*a，用0.5*（a+b）代替（a+b）/2.0等，以降低时间复杂度。
4．在计算机上，为提高加、减、乘、除运算的稳定性，想方设法减少有效数字的损失，如极力避免两相近数的减法运算、两相差很大数的加法运算、特大数作乘法和特小数作除法的运算等。
在算法执行过程中会出现舍入误差的积累。对同一个计算问题，在不同的算法中舍入误差对计算结果产生的影响也各不相同。舍入误差对计算结果的精确性影响小的算法，具有较好的数值稳定性；反之，算法的数值稳定性差。例如，若干个正数相加时，按从大到小的次序进行就不如按从小到大的次序进行的数值稳定性好。
再以二次方程 x²+bx+ =0求根为例，说明如何利用不同的算法避免两相近数的减法运算。对二次方程 x²+bx+ =0求根，有如下公式：

若b>0，且b²>>4| |，则由于b和√b²-4ac很接近，用公式(1)计算x1遇到两个相近的数相减，就会使有效数字严重损失。但这时可先用公式(2)计算x₂，然后根据关系x₁x₂= / 计算x₁，会得到比较好的结果。在用消去法解线性代数方程组时，选主元的算法比不选主元的算法的数值稳定性好，同样说明计算机上数值计算顺序选择的重要性。
下面再通过统计计算中的一个简单实例，计算一组观察数据的均值和方差，说明数学中的公式计算和计算机上的数的实际计算的不同。
给出n个数据

？？？？？？？？？？？？？？？ x₁，x₂，…，x_{n？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？} （3）

经常需要计算它们的均值

和方差

在数学上，显然有

（5）、（6）两式恒等，同时成立。现在要问，对一组给出的数据（3），在计算机上用（5）和（6）二式分别进行计算方差时，结果是否还完全相同？和（4）、（5）、（6）相比，能否给出均值和方差计算结果误差更小、计算所用计算机机时更省的公式或算法？
对均值和方差，通常有下面三个不同的算法可用：
1.直接算法

和上面的（4）、（6）相同，只需对数据（3）进行一轮循环处理，即可得到结果。
2.二次均值算法

从数学上看，（10）是一道多余的计算，因此，（9）、（11）和（7）、（8）在理论上是一样的；但在计算机上对实际数据进行处理时，它们可不一样，经常给出有一定差异的计算结果；和（7）、（8）相比，（9）、（10）、（11）要对数据（3）进行三轮循环处理，才能得到结果，计算工作量增大，但可避免“大”吃“小”，舍入误差的影响会更小一些，结果会更为可靠。
3.递推算法
记

这时取初值

对i=2，3，…，n，用

进行递推计算，最后得

利用递推算法（12）–（16），只需对数据（3）进行一轮循环处理，即可得到计算结果。
计算结果的精度受多种因素的影响，如数组取值的大小、排序的不同等，计算结果的精度都会有所不同，三种算法的优劣一时还很难定论；但综合考虑计算量和结果精度并通过实例进行计算的结果表明，递推算法更好一些。