数值分析 第一章 绪论

误差的来源和分类

按误差来源分类

1. 模型误差
   数学模型通常是由实际问题抽象得到的，一般带有误差，这种误差称为模型误差，一般来说是不可避免的。

2. 观测误差
   数学模型中包含的一些物理参数通常是通过观测和实验得到的，难免带有误差，这种误差称为观测误差。也是不可避免的。

3. 截断误差
   求解数学模型所用的数值方法通常是一种近似方法，这种因方法产生的误差称为截断误差或方法误差。
   例如：利用$ln(x+1)$的Taylor公式:
   $ln(x+1) = x-\frac{1}{2}x^2 + \frac{1}{3}x^3 - \frac{1}{4}x^4 +...+(-1)^{n+1}\frac{1}{n}x^n+...$
   这是一个级数的形式，我们在计算机中无法计算无穷多项
   实际计算时只能截取有限项代数和计算，如取前5项有：
   $ln(2) \approx 1-\frac{1}{2}+\frac{1}{3}-\frac{1}{4}+\frac{1}{5}$
   这里产生的误差为截断误差，记作$R_5$
   $R_5 = -\frac{1}{6} + \frac{1}{7}-\frac{1}{8}+\frac{1}{9}-...$

4. 舍入误差
   由于计算机只能对有限位数进行运算，在运算中像$e$、$\sqrt{2}$、$\frac{1}{3}$等都要按舍入原则保留有限位，这时产生的误差称为舍入误差或计算误差。

截断误差或者说方法误差是由我们主观采用近似方法而产生的误差。舍入误差是由于计算机只能对有限位数进行运算而产生的误差，是不可避免的。

在数值分析中，我们总假定数学模型是准确的，因为不考虑模型误差和观测误差，主要研究截断误差和舍入误差对计算结果的影响。

绝对误差和相对误差

1. 绝对误差

• 设$x$是精确值$x^*$的一个近似值，记
  $e = x^*-x$
  称$e$为近似值$x$的绝对误差，简称误差。
  在本课程中，$x$为近似值，$x^*$为精确值。一般来说，$x^*$仅用于理论分析。

• 如果$\epsilon$满足：
  $|e| \leqslant \epsilon$
  则称$\epsilon$为近似值$x$的绝对误差限，简称为误差限。

• 精确值$x^*$、近似值$x$和误差限$\epsilon$之间满足：
  $x-\epsilon \leqslant x^* \leqslant x+\epsilon$
  简写为
  $x^* = x \pm \epsilon$
  注意，这里的$=$不是精确的

• 绝对误差有时并不能很好地反应近似程度的好坏，如：
  $x^*=10, \epsilon _x = 1, y^* = 10000, \epsilon _y = 5$
  虽然$\epsilon _y$是$\epsilon _x$的5倍，但在10000内差5显然比10内差1好。

2. 相对误差
   记：
   $e_r = \frac{e}{x^*} = \frac{x^*-x}{x^*}$
   称$e_r$为近似值$x$的相对误差。

同样地，由于$x^*$未知，实际使用时总是将$x$的相对误差取为：
$e_r = \frac{e}{x} = \frac{x^*-x}{x}$

$\epsilon _r = \frac{\epsilon}{|x|}$称为近似值$x$的相对误差限。$|e_r| \leqslant \epsilon _r$

例题

例1：设$x=1.24$是由精确值$x^*$经过四舍五入得到的近似值，求$x$的绝对误差限和相对误差限。
解：由已知可得$1.235 \leqslant x^* <1.245$，我们说这个误差是截断误差，是由四舍五入这个方法得到的近似值。
所以$\epsilon = 0.005, \epsilon _r = 0.005 \div 1.24 \approx 0.4\%$
一般地，凡是由精确值经过四舍五入得到的近似值，其绝对误差限等于该近似值末尾的半个单位。

有效数字

有效数字的定义

问题：下列数作为$\pi$的近似值，它们的近似效果都一样吗？每个近似值当中的数字都起作用吗？
$3.14, 3.141, 3.15$
定义1：设数$x$是数$x^*$的近似值，如果$x$的绝对误差限是它的某一数位的半个单位，并且从$x$左起第一个非零数字到该数为共有$n$位，则称这$n$个数字为$x$的有效数字，也称用$x$近似$x^*$时具有$n$位有效数字。

数$x$总可以写成如下形式:
$x = \pm 0.a_1a_2...a_k×10^m$
其中$m$为整数，$a_i$是0到9中的一个数字，$a_1 \not = 0$。
我们称这种形式为标准浮点数，任何一个数都可以转化为标准浮点数。

有效数字和绝对误差限之间的关系

$x$作为$x^*$的近似值，具有$n$位($n \leqslant k$)有效数字当且仅当：
$|x^* - x| \leqslant \frac{1}{2} × 10^{m-n}$
由此可见，近似值的有效数字越多，其绝对误差越小。

例1：为了使$x^* = \sqrt{2}$的近似值的绝对误差小于$10^{-5}$，问应取几位有效数字？
根据$|x^* - x| \leqslant \frac{1}{2} × 10^{m-n}$
解：由于$\sqrt{2} = 1.4...$，则近似值$x$可以写为:
$x = \pm 0.a_1a_2...a_k×10$，$a_1 =1 \not = 0$，式中的$m=1$。
令$|\sqrt{2} -x|\leqslant \frac{1}{2} ×10^{1-n} \leqslant 10^{-5}$
故取$n=6$，即取6位有效数字。此时$x=1.41421$。

注意：精确值的有效数字可认为有无穷多位。
$3.14, 3.141, 3.15$
求它们的近似程度实际上就是求它们的绝对误差限是多少，每个近似值当中的数字都起作用吗？实际上就是求有效数字的位数。

有效数字和相对误差限的关系

若$x$有$n$位有效数字，则其相对误差限为：
$\epsilon _r \leqslant \frac{1}{2a_1}×10^{-n+1}$
反之，若$x$的相对误差限：
$\epsilon _r \leqslant \frac{1}{2(a_1 +1)} ×10^{-n+1}$，则$x$至少有$n$位有效数字。
因此，知道有效数字可以求出相对误差限，知道相对误差限也可以求出有效数字。

数值计算的若干原则

为了减少舍入误差的影响，设计算法时应遵循如下原则。

1. 避免两个相近的数相减

如果两个相近的数相减，它得到的差会很小。从数值分析的角度上来说，它的有效数字的位数会大大减少。对于近似值，我们要尽可能多地保留有效数字的位数，因此要避免两个相近的数相减。

在数值计算中，如果遇到两个相近的数相减运算，可以考虑改变一下算法以避免两数相减。例如

当$x_1 \approx x_2$时，要求计算$log{x_1} - log{x_2}$，此时可以用对数的运算法则， 用$log{\frac{x_1}{x_2}}$来替换。

当$x \approx 0$时，要求计算$1-cosx$，此时可以用三角函数的和差化积公式来计算，用$2sin^2\frac{x}{2}$。

当$x>>1$时，要求计算$\sqrt{x+1}-\sqrt{x}$，此时可以用$\frac{1}{\sqrt{x+1}+\sqrt{x}}$。

例1：求方程$x^2 -64x+1=0$的两个根，使他们至少具有四位有效数字。（$\sqrt{1023} \approx 31.984$）

解：由求根公式有$x_1 = 32+\sqrt{1023}\approx 63.984$，具有5位有效数字，满足要求

若由$x_2 = 32-\sqrt{1023} \approx 0.016$，仅有两位有效数字。

这里我们需要改变算法，根据两个根之间的关系得$x_2 = \frac{1}{x_1} \approx 0.01563$，则具有四位有效数字。

对两个相近的数相减，若找不到适当的方法代替，只能在计算机上采用双倍字长计算，以提高精度。

2. 防止大数“吃掉”小数

因为在计算机上只能采用有限位数计算，若参加运算的数量级差很大，在它们的加、减运算中，绝对值很小的数往往被绝对值较大的数“吃掉”，造成的计算结果失真。

例如，用八位十进制的浮点计算$A = 26358713+0.8+0.2$

按照加法浮点运算的对阶规则，应有：

$A = 0.26358713×10^8 + 0.000000008×10^8 + 0.000000002×10^8$

由于采用八位数运算，于是$A = 26358713$

若改变计算顺序，计算$0.2+0.8+26358713$，则有

$A = 0.00000001 ×10^8 + 0.26358713×10^8 = 26358714$

可见，在求和或差的过程中应采用由小到大的运算过程。

3. 绝对值太小的数不宜作除数

由于除数很小，将导致商的绝对误差很大，有可能出现“溢出”的现象。

4. 注意简化计算程序，减少计算次数

首先，若算法计算量太大，实际计算无法完成。

例如用线性代数中的Cramer法则求$n$元线性方程组$Ax=b$的解，

需要计算$n+1$个$n$阶行列式，而每个$n$阶行列式按定义$D =\sum_{P_1P_2...P_n}(-1)^t a_{1P1}a_{2P2}...a_{nPn}$需要计算$(n-1)n!$次乘法，则Cramer法则至少需要$(n^2-1)n!$次乘法，当$n=20$时，有$(20^2-1)20! \approx 9.7×10^{20}$次乘法运算。

其次，即使是可行算法，则计算量越大积累的误差也越大，因此计算量越小越好。

因为舍入误差是不可避免地，它会随着计算量传播和积累。

例如计算$n$次多项式：

$P_n(x) = a_nx^n+a_{n-1}x^{n-1}+...+a_1x+a0$

若直接逐项计算，大约需要乘法运算次数为$\frac{n(n+1)}{2}$次。

若将多项式改写为：

$P_n(x) = (...((a_nx+a_{n-1})x +a_{n-2})x+...)x+a_0$

则只需$n$次乘法和$n$次加法运算。

5. 选用数值稳定性好的算法

一种数值算法，如果其计算舍入误差积累是可控制的，则称其为数值稳定的，反之称之为不稳定的。

例如积分：

$I_n = \int _0^1 x^ne^{x-1}dx$

利用分部积分法可得计算$I_n$的递推公式：

$I_n = 1-nI_{n-1},n=1,2,...$

我们还需要一个初始迭代值$I_0$，由于$n=0$时：

$I_0 = \int_0^1 e^{x-1}dx = 1-e^{-1} = 0.632120558...$

也就是说，在取$I_0$时会有一个舍入误差，若取四位有效数字则递推可得：

对任何$n$都应有$I_n>0$，但计算结果显示$I_8<0$，可见，虽然$I_0$的近似误差不超过$0.5×10^{-4}$，但随着计算步骤的增加，误差明显增大。这说明这里的递推公式是数值不稳定的。

这个算法本身是没有截断误差的，而在取$I_0$时产生舍入误差。

根据原因，我们可以修改算法为

$I_{n-1} = \frac{1}{n}(1-I_n),n=k,k-1,...,2,1$

类似地，可得：

$I_k - I_k^* = (-1)^{n-k}\frac{k!}{n!}(I_n-I_n^*), k=n,n-1,...,1,0$

可见，近似误差$I_k-I_k^*$是可控的，因此算法是数值稳定的。