数值计算误差

• 误差
  • 定义
    • $a$ 为计算值，$A$ 为真实值。
    • 绝对误差：$\Delta A=a - A$，上界称为误差限，一般用 $\varepsilon_a$ 或 $|\Delta| a \le (\star)$ 表示。
    • 相对误差：$\delta A = \dfrac{\Delta A}{A} \approx \dfrac{\Delta A}{a}$，上界称为相对误差限，一般用 $\eta_a$ 或 $|\delta| a \le (\star)$ 表示。
  • 分类
    • 模型误差
    • 观测误差
    • 截断误差 / 方法误差：精确公式用近似公式计算产生的误差，如级数仅使用前几项计算。
    • 舍入误差：数值计算只能保留有限的字长，舍入产生误差。
• 舍入方法
  • 截断法
    • 在 $A$ 的小数点后第 $n$ 位舍去所有数字。
    • 绝对误差限为 $10^{-n}$。
  • 四舍五入法
    • 保留 $A$ 的小数点后第 $n$ 位，第 $n+1$ 位为 $5$ 及以上时进位。
    • 绝对误差限为 $0.5\times 10^{-n}$。
• 有效数字
  • 定义
    • 有效数字为满足误差限的近似数，通过四舍五入法近似。
    • 有效数字位数为第一位非 $0$ 数到最后一位的个数。
    • 对于有效数字 $a$，绝对误差 $|\Delta a| \le 0.5 \times 10^{-n}$，即不超过其末位数字的半个单位。（对应四舍五入）
    • 对于有效数字 $a$，相对误差 $|\delta a| \le \left|\dfrac{0.5 \times 10^{-n}}{a}\right| \le \dfrac{5}{a_0}\cdot 10^{-(m+n+1)}$，$a_0$ 为 $a$ 的第一位。
  • 与误差限相关的处理
    • 对数 $a$ 及其误差限 $|\Delta a|$ 做舍入处理，则保留的小数位数为最小的 $k$，满足 $|\Delta a| \le 0.5\times 10^{-k}$。
      • 如 $a = 1.2345,|\Delta a| \le 0.00083$，则 $0.00083 = 0.083 \times 10^{-2} \le 0.5 \times 10^{-2}$，取 $k = 2$，$a$ 舍入为 $1.23$。
      • 满足去伪存真原则，小于误差限的小数部分都被舍去。
    • 根据误差限 $|\Delta a| \le \varepsilon$ 确定计算 $a$ 要保留的小数位数 $k$，则最小的 $k$ 至少满足 $0.5 \times 10^{-k} \le \varepsilon$。
      • 如要求 $|\Delta a| \le \varepsilon = 0.003$，则 $0.5 \times 10^{-2} \le 0.003 = 0.3 \times 10^{-2}$，取 $k = 2$，$|\Delta a| = 0.5 \times 10^{-2}$。
• 误差传递
  • 加减 $c = x + y$
    • $|\mathrm dc| = |\mathrm dx + \mathrm dy| \le |\mathrm dx| + |\mathrm dy| \le \varepsilon_x +\varepsilon_y$
  • 乘 $c = xy$
    • $|\mathrm dc| = |x\mathrm dy + y\mathrm dx| \le |x|\varepsilon_y + |y|\varepsilon_x$
    • $|\delta c| = \left|\dfrac{x\mathrm dy + y\mathrm dx}{xy}\right| = |\delta x + \delta y| \le |\delta x| + |\delta y|$
  • 除 $c=\dfrac{x}{y}$
    • $|\mathrm dc| = \left|\dfrac{y\mathrm dx-x\mathrm dy}{y^2}\right|$
    • $|\delta c| = \left|\dfrac{y\mathrm dx-x\mathrm dy}{y^2 \cdot \frac{x}{y}}\right| = \left|\dfrac{\mathrm dx}{x}-\dfrac{\mathrm dy}{y}\right| \le |\delta x| + |\delta y|$
  • 函数 $y=f(x_1, x_2, \dots, x_n)$
    • $|\mathrm dy| = \left|\sum\limits_{i = 1}^n \dfrac{\partial f}{\partial x_i} \mathrm dx_i\right| \le \sum\limits_{i = 1}^n \left|\dfrac{\partial f}{\partial x_i}\right| \left|\mathrm dx_i\right|$
    • $|\delta y| = \left|\sum\limits_{i = 1}^n \dfrac{\partial f}{\partial x_i}\dfrac{x_i}{y} \dfrac{\mathrm dx_i}{x_i}\right| \le \sum\limits_{i = 1}^n \left|\dfrac{\partial f}{\partial x_i}\dfrac{x_i}{y}\right| \left|\delta x_i\right|$
  • 注意事项
    • 两个相近数相减时，有效数字可能丢失很多。
    • 分母很小时，商的绝对误差可能很大。
• 误差分配
  • 误差配置原理
    • 计算模型的近似解相对参数模型的精确解的总误差为截断误差和舍入误差，$\varepsilon = R + \epsilon$。
    • $R < \epsilon$ 时，误差主要体现在舍入误差，分配不合理，可以提高运算的字长。
    • $R > \epsilon$ 时，误差主要体现在截断误差，分配不合理。
    • $R \approx \epsilon$ 时，分配比较合理。
  • 处理方法
    • 处理误差、字长、计算方法之间的关系时，应当考虑按照 $R \approx \epsilon$ 进行。
    • 给定 $\epsilon$，确定字长
      • 已知 $y = f(x_1, x_2, \dots, x_n)$，并且要求 $|\mathrm dy| \le \epsilon$，确定 $x_1,x_2,\dots,x_n$ 使用的字长。
      • 令 $\max\{|\mathrm dx_1|,|\mathrm dx_2|,\dots,|\mathrm dx_n|\} \le \Delta$，则 $|\mathrm dy| \le \sum\limits_{i = 1}^n \left|\dfrac{\partial f}{\partial x_i}\right| \Delta \le \epsilon$。
      • 解出 $\Delta$ 即 $x_1, x_2, \dots, x_n$ 的误差限，可以确定字长。
    • 给定数值公式，确定字长
      • 已知数值公式则可以确定 $R$，根据 $R \approx \epsilon$ 可确定 $\epsilon$，可以确定字长。
    • 给定 $\varepsilon$，确定数值公式的项数和字长
      • 应当确定 $R \approx \epsilon \approx = \dfrac{\varepsilon}{2}$，利用数值公式的余项确定项数，再用 $\epsilon$ 确定字长。
    • 给定字长，确定数值公式的项数
      • $\epsilon$ 的计算依赖于项数，所以 $R$ 和 $\epsilon$ 不能分开考虑，需要枚举可能的项数。
      • 对于某个项数，确定其 $R$ 和 $\epsilon$，如果 $R \approx \epsilon$，则比较合理，否则需要增大项数。
      • 一般项数越多，$R$ 越小，$\epsilon$ 越大。