数值分析2012 - 图文

当用近似的方式处理数学式时就会出现截尾误差。以积分为例，完全精准的积分需要求出曲线下方无限个梯形的面积和，但用在数值分析中会用有限个梯形的面积和来近似无限个梯形的面积和，此时就会出现截尾误差。若要对一个函数进行微分，其微分量需要趋近于0，但实务上只能选择很小的微分量。

误差估计

既然在计算过程中误差不可避免，那么对近似数的估差就很必要。对没有注明误差限度的公式或数据，一般我们是不敢用的。误差一般分为绝对误差和相对误差。 绝对误差

设x是代表真值x*的一个近似数，则称e*?x*?x为近似数x的绝对误差； 相对误差

*?(x*?x)x*为近似数x的相对误差； 设x是代表真值x*的一个近似数，称er一般近似数的绝对误差好像是直截了当，一眼可见。然而，相对误差应更科

学一些。例如，当我们测量100米的距离时，绝对误差是1米，即近似数为

x?100?1米；当我们测量1000米时，绝对误差是5米，即近似数为y?500?5米。那么，究竟哪一次的测量结果误差大呢？若看绝对误差，后一个数y的误差大，为5米。然而，这是在测量1000米时产生的误差。比较科学的办法应该看

*两次测量当中平均1米产生多大的误差，即看它们的相对误差：erx?1100?1%，

*ery?51000?0.5%；可见，还是第一个数的测量误差较大。

绝对误差与相对误差的估计、有效数字

通常情况下，真值x*是不知道的，因此无法准确地算出它的近似数x的绝对误差或相对误差，只能去估计它的上界。若x*?x???或x*?x??r?，则称??为x的绝对误差限，称?r?为x的相对误差限。

例如，估计近似数x?0.0034的绝对误差限。因为0.0034可能是由0.00344或0.00336经四舍五入得到的，所以，它的绝对误差不超过5?10?5，或写成

110.5?10?4，一般又都写成?10?4，即得x*?x??10?4，其中x?0.0034，x*是

22它的真值。

一般地，设有一个近似数x经四舍五入，可以写为

x??(x1?10?1?x2?10?2???xn?10?n)?10?m

其中x1,x2,?,xn都是0,1,?,9这十个数之一，且x1?0；n是正整数，m是整数，

1?10m?n。也称x具有n位有效数字，还2可以说它准确到第n位。它的相对误差估计式为

则x的绝对误差的估计式即为x*?x?x*?x11m?nm?1?(?10)(x?10)??10?(n?1)。 1*22xx数值稳定性及良置问题

数值稳定性是计算方法（数值分析）中一个重要的主题。若一算法中不论什么原

因产生了误差，此误差不会在运算中明显增加，此算法为数值稳定的算法。若问题为良置（well-conditioned）的，就会符合上述的特性，也就是问题数据微小的变化只会造成其解的微小变化。相反的，若问题数据微小的变化会造成其解的巨大变化，会称问题为非良置或病态（ill-conditioned）。

原始问题及求解问题算法都可以分为良置及非良置，任何的组合都是允许的。 一个求解良置问题的算法可能是数值稳定的，也可能是数值不稳定的。数值分析的重点就是找到适定性问题的数值稳定算法。例如，计算2的平方根（大约是1.41421）本身是一个适定性问题。许多求解的算法都是从一个初始的近似值x1开始去求解，例如x1=1.4，再继续计算x2、x3等。巴比伦法就是一个具有此特性的算法。另一个方法，先称之为X方法，算法为xk + 1 = (xk2?2)2 + xk。[注解 1]以下分别用初始值 x1 = 1.4及x1 = 1.42，用二种方式进行几次迭代。

巴比伦法

巴比伦法

X方法

X方法

x1 = 1.4 x1 = 1.42 x1 = 1.4 x1 = 1.42 x2 = 1.4142857... x2 = 1.41422535... x2 = 1.4016 x2 = 1.42026896 x3 = x3 =

x3 = 1.4028614... x3 = 1.42056... 1.414213564...

1.41421356242...

...

...

x1000000 = 1.41421...

x28 =

7280.2284...

可观察到不论初始值多少，巴比伦法都可以快速的收敛，但X方法在初始值为

1.4时收敛的很慢，在初始值为1.42时X方法会发散。因此巴比伦法是数值稳定的方法，而X方法是数值不稳定的方法。

（解释一下计算数字n的平方根的巴比伦算法

（1）先猜一个答案guess(可以将n/2作为第一个答案） （2）计算r=n/guess

（3）令guess=(guess+r)/2

（4）如有必要返回第2步重复多次。步骤2和步骤3的重复次数越多， guess就越接近n

的平方根。

作业：写一个程序，输入整数作为n的值，重复执行巴比伦算法，直到guess与前一个guess的误差在1%范围内，将答案作为一个double输出)

非良置问题：考虑一函数f(x) = 1/(x ? 1)，f(1.1) = 10，f(1.001) = 1000。当x只改变小于0.1的数值，f(x)的变化将近1000。因此在x = 1的附近计算f(x)是一个非良置的问题。 良置问题：相反的，函数置的问题

在x不接近0时，其值的计算就是一个良

领域研究

计算方法依其待求解的问题不同，分为不同的领域。

函数求值

计算方法中最简单的问题就是求出函数在某一特定数值下的值。最直觉的方法是将数值代入函数中计算，不过有时此方式的效率不佳。像针对多项式函数的求值，较有效率的方式是秦九韶算法，可以减少乘法及加法的次数。若是使用浮点数，很重要的是估计及控制舍入误差。

内插法、外推法、曲线拟合及回归

内插法求解以下的问题：有一未知函数在一些特定位置下的值，求未知函数在已知数值的点之间某一点的值。

外推法类似内插法，但需要知道数值的点是在其他已知数值点的范围以外。一般而言外推法的误差会大于内插法。

曲线拟合是在已知一些数据的条件下，找到一条曲线完全符合现有的数据，数据可能是一些特定位置及其对应的值，也可能是其他资料，例如角度或曲率等。 回归分析类似曲线拟合，也是根据一些特定位置及其对应的值，要找到对应曲线。但回归分析考虑到数据可能有误差，因此所得的的曲线不需要和数据完全符合。一般会使用最小方差法来进行回归分析。

内插法：假设一点钟的气温为20度，三点钟时为14度，可以用线性内插法推测一点半及二点钟时的气温分别是18.5度及17度。

外推法：假设某国家国内生产总值平均每年成长百分之五，去年国内生产总值为一百万元，可推测今年的国内生产总值为一百零五万元。

回归分析：给定几个二维座标上的点，回归分析就是设法找到一条最接近这些点的直线。

最佳化：有一个卖饮料的小贩，若每杯饮料100元，每天可以卖197杯饮料，若饮料单价增加1元，每天就会少卖1杯饮料，若饮料定价为148.5元，其每天的收入为最大值。不过由于饮料单价需为正整数，因此饮料定价可定为149元，对应每天的收入为22,052元。