数值计算笔记-误差分析 - 知乎 - 程序猿·D·安宇雨 DeepMind

数值计算笔记-误差分析 - 知乎

安宇雨 - 随手采集
2023-12-07 09:52:25
随手采集
0000-未整理-等待研究

1.1 概述

1. 定义数值计算目标: 寻找一个能迅速完成的（迭代算法）算法，同时估计计算结果的准确度。

1.2 误差分析基础

1. 误差来源：截断误差、舍入误差、数学建模时的近似、测量误差（数据误差）

2. 误差的分类：

绝对误差e(x^)=x^−xe(\hat{x}) = \hat{x} - x ；误差限

相对误差 er(x^)=x^−xxe_r(\hat{x}) = \frac{\hat{x} - x}{x} 或者 er(x^)=x^−xx^e_r(\hat{x}) = \frac{\hat{x} - x}{\hat{x}} ；相对误差限

3. 定义有效数字：从左到右第一位非零数字开始的所有数字

定理：设x与其近似值x^\hat{x} 的第一位有效数字相同，均为d0d_0 ，若x^\hat{x} 有p位正确的有效数字，则其相对误差满足：

|er(x^)|≤1d0×10−p+1 |e_r(\hat{x})| \leq \frac{1}{d_0} \times 10^{-p + 1}

定理：设对x保留p位有效数字后得到近似值 x^\hat{x} ，则相对误差满足：

|er(x^)|=12d0×10−p+1 |e_r(\hat{x})| = \frac{1}{2d_0} \times 10^{-p+1}

定理：设x的第一位有效数字为 d0d_0 ，若近似值x^\hat{x} 的相对误差满足 |er(x^)|≤12(d0+1)×10−p+1|e_r(\hat{x})| \leq \frac{1}{2(d_0 + 1)} \times 10^{-p + 1} 则x^\hat{x} 具有p位正确的有效数字，或者在保留p位有效数字后 x^=x\hat{x} = x

定理：若x的近似值在 x^\hat{x} 相对误差满足 |er(x^)|≤12×10−p|e_r(\hat{x})| \leq \frac{1}{2} \times 10^{-p} ，则 x^\hat{x} 至少有p位正确的有效数字，或者在保留p位有效数字后 x^=x\hat{x} = x

应用：可以不严谨的说如果相对误差不超过 10−p10^{-p} 怎有p位正确的有效数字

4. 区分：精度（precision）：有效数字的位数有关

准确度（accuracy）：与准确的有效数字的位数有关

5. 数据传递误差与计算误差：考虑 f(x),f(x^),f^(x^)f(x), f(\hat{x}), \hat{f}(\hat{x})

计算误差：计算过程中的近似引起的误差，例 f^(x^)−f(x^)\hat{f}(\hat{x}) - f(\hat{x})

数据传递误差：单纯由输入数据误差引起的计算结果的误差，例 f(x^)−f(x)f(\hat{x}) - f(x)

6. 截断误差：实际结果，算法准确计算得到的结果的差

舍入误差：算法精确计算得到的结果，算法经有限精度计算的得到结果的差

7. 敏感性：输入数据的扰动对问题得影响程度得大小

条件数：问题的解的相对变化量输入数据的相对变化量cond=||问题的解的相对变化量||||输入数据的相对变化量|| cond = \frac{||问题的解的相对变化量||}{||输入数据的相对变化量||}

计算公式： cond=|[f(x^)−f(x)]/f(x)(x^−x)/x| cond = |\frac{[f(\hat{x}) - f(x)] / f(x)}{(\hat{x} - x) / x}|

推导可得：问题的解的相对变化量数据传递的相对误差||问题的解的相对变化量||<cond||数据传递的相对误差||cond=|xf′(x)f(x)| ||问题的解的相对变化量|| < cond||数据传递的相对误差|| cond = |\frac{xf'(x)}{f(x)}|

反问题（字面理解）：原问题是y = f(x)，反问题是给定y确定x。反问题的条件数就是探讨反函数 f−1(y)f^{-1}(y) 的敏感性。可以化简得出反问题得条件数和原问题得条件数互为倒数，即 condf−1=1condfcond_{f^{-1}} = \frac{1}{cond_{f}}

8. 算法稳定性

理解：算法很多是迭代得，每一步算法都会不断放大进而传导误差，如果传导误差不会特别大则算法稳定。

分析算法稳定性工具为误差限的四则运算，x^1,x^2\hat{x}_1, \hat{x}_2 的误差限为 ϵ1,ϵ2\epsilon_1, \epsilon_2 ，误差限的四则运算如下：

{ϵ(x^1+x^2)=ϵ1+ϵ2ϵ(x^1x^2)=|x^2|ϵ1+|x^1|ϵ2ϵ(x^1/x^2)=|x^2|ϵ1+|x^1|ϵ2|x^2|2 \begin{cases} \epsilon(\hat{x}_1 + \hat{x}_2) = \epsilon_1 + \epsilon_2 \ \epsilon(\hat{x}_1\hat{x}_2) = |\hat{x}_2|\epsilon_1 + |\hat{x}_1|\epsilon_2\\epsilon(\hat{x}_1 / \hat{x}_2) = \frac{|\hat{x}_2|\epsilon_1 + |\hat{x}_1|\epsilon_2}{|\hat{x}_2|^2} \end{cases}

简单的例题：

计算黄金比例的20次方 ϕ=(5−1)/2,ϕn+1=ϕn−ϕn−1\phi = (\sqrt5 - 1) / 2, \phi^{n + 1} = \phi^{n} - \phi^{n - 1} ，初始的近似值x = 0.618034，对于误差限有一下迭代公式：

{en+1=en−1−ene0=0,e1=x−ϕe2=−e1e3=2e1e4=−3e1⋮ \begin{cases} e_{n + 1} = e_{n - 1} - e_{n}\ e_0 = 0, e_1 = x - \phi \end{cases}\ e_2 = -e_1\ e_3 = 2e_1\ e_4 = -3e_1\ \vdots

可以看到系数在以斐波那契数列增长，因此算法不稳定。