数值分析 笔记 1

误差分析

通常来说，误差的来源包括：

1. 计算前的误差：
   • 模型误差：例如物理中常见的“忽略空气阻力”
   • 数据误差：已知常数、测量值、前序结果的误差等
2. 计算中的误差
   • 截断误差：计算方法本身的近似带来的误差，例如有限阶的泰勒展开计算非多项式函数
   • 舍入误差：计算时对数据进行舍入，默认为四舍五入

误差及其分类

我们通常使用$x$表示真实值，使用$\hat{x}$表示近似值，那么绝对误差和相对误差分别定义为

$$\begin{align*} e(x) &= \hat{x} - x \\ e_{r}(x) &= \frac{\hat{x} - x}{x} \end{align*}$$

因此当真实值为$0$的时候，讨论相对误差没有意义

在很多情况下（例如测量、舍入计算时）我们无法获取真实值，因此无法计算真实误差，这种情况下会估计误差上限，绝对误差限和相对误差限分别定义为：

$$\begin{align*} \varepsilon(x) &= \max(e(x)) \\ \varepsilon_{r}(x) &= \max(e_{r}(x)) \end{align*}$$

在误差很小的情况下，相对误差可以近似为

$$e_{r}(x) \approx \frac{e(x)}{\hat{x}}$$

关于有效数字的定理

数据传递误差与计算误差

在计算函数$f(x)$的过程中，误差的来源是两部分：

$$\hat{f}(\hat{x}) - f(x) = \big(\hat{f}(\hat{x}) - f(\hat{x}) \big) + \big(f(\hat{x}) - f(x) \big)$$

前者是单纯的计算误差，$f$无法精确计算导致，而后者是数据传递误差，即自变量的误差影响到因变量

考虑使用差商近似微分：

$$f'(x) \approx \frac{f(x + h) - f(x)}{h}$$

由带拉格朗日余项的泰勒公式：

$$f(x + h) = f(x) + f'(x)h + \frac{f''(\xi)}{2}h^{2}\quad \xi \in (x, x + h)$$

因此使用差商会带来截断误差，设$f''(x)$的上界为$M$，则截断误差误差限为：

$$\varepsilon_{T} = \frac{Mh}{2}$$

而舍入误差限为：

$$\varepsilon_{R} = \frac{2\varepsilon}{h}$$

其中$\varepsilon$是每一次计算$f$带来的舍入误差限

因此总误差限为

$$\varepsilon_{\text{tot}} = \frac{Mh}{2} + \frac{2\varepsilon}{h}$$

容易得到，当$h = 2\sqrt{\varepsilon / M}$的时候，总误差限最小

问题的敏感性

我们使用条件数来反应问题的敏感性：

$$\text{cond} = \frac{||解的相对误差||}{||输入的相对误差||}$$

以函数求值问题为例，我们有：

$$\text{cond} = \Big|\frac{[f(\hat{x}) - f(x)]/f(x)}{(\hat{x} - x)/x}\Big| \approx \Big|\frac{xf'(x)}{f(x)}\Big|$$

类似的，我们可以使用绝对误差定义绝对条件数

对于简单多元运算$y = f(x_{1}, \dots, x_{n})$，近似值为$\hat{y} = f(\hat{x}_{1}, \dots, \hat{x}_{n})$我们可以使用Taylor来近似估计相对误差限

$$y - \hat{y} \approx \sum\limits_{i=1}^{n}\frac{\partial f}{\partial x_{i}}(\hat{x}_{1}, \dots, \hat{x}_{n})(x_{i} - \hat{x}_{i})$$

因此

$$\varepsilon(\hat{y}) = \Big|\sum\limits_{i=1}^{n}\frac{\partial f}{\partial x_{i}}(\hat{x}_{1}, \dots, \hat{x}_{n})\Big|\varepsilon(\hat{x}_{i})$$

算法稳定性

对于一个算法，其稳定性可以定义为：

1. 对计算过程中的扰动（四舍五入、保存数据精度等）不敏感的算法更稳定
2. 对包含一系列计算步的过程, 若中间步结果的（相对）误差不放大或放大不严重, 则该过程对应的算法更稳定

例如在计算黄金分割率$\phi$的幂次时，如果采用下列递推式：

$$\begin{align*} \phi^{n + 1} &= \phi ^{n - 1} - \phi^{n} \quad (n \geq 2) \\ \phi^{0} &= 1, \phi^{1} = \hat{\phi} \end{align*}$$

其绝对误差也满足：

$$\begin{align*} e_{n + 1} &= e_{n - 1} - e_{n} \quad (n \geq 2) \\ e_{0} &= 0, e_{1} = \phi - \hat{\phi} \end{align*}$$

可以计算得知，$|e_{n}| = c_{n}|e_{1}|$，其中$c_{n}$为Fibonacci序列，显然当$n$较大时，绝对误差的放大非常严重，相对误差亦然

向后误差

向后误差是一种分析舍入误差的方法，在函数求值的过程中，$f$的计算会有误差$f(x) \to \hat{f}(x)$，这种舍入误差可能是隐含在每一步的计算过程中的，分析过程较为复杂，因此考虑将其转化为输入扰动带来的误差，即：

找到$\hat{x}$，使得$f(\hat{x}) = \hat{y}$，则$\Delta x = \hat{x} - x$称为向后误差

计算机浮点数

计算机浮点数系统

我们定义机器精度为$\varepsilon_{\text{mach}} = 2^{-p}$

则有如下定理：

抵消现象

指在计算过程中有效位数下降的过程，例如$x = 1.02305 \times 10^{3}, y = 1.92137 \times 10^{3}$，则精确计算得到$x - y = 1.68$，有效位数降至3位，可能导致相对误差的放大与准确度的下降

例如在一元二次方程求根公式中，其中一个根为：

$$x_{1} = \frac{-b + \sqrt{b^{2} - 4ac}}{2a}$$

如果$|4ac| << b^{2}$，那$b$与$\sqrt{b^{2} - 4ac}$的值非常接近，可能会出现抵消现象，解决方法为修改求根公式：

$$x_{1} = \frac{2c}{-b - \sqrt{b^{2} - 4ac}}$$

总结

误差简单总结