计算方法-[1]绪论与计算误差

发表于 2019/03/06 更新于 2019/05/08 分类于计算方法

计算方法课程第一章绪论与计算误差整理，来自课程内容，因 Github 无法渲染公式，故整理在此.

源文件：https://github.com/fish-404/Notes/tree/master/%E8%AE%A1%E7%AE%97%E6%96%B9%E6%B3%95

计算方法研究内容与意义

研究对象

计算方法研究的是运用计算机来解决各种数学问题的近似计算方法与理论。

计算方法是研究求解各类数学问题在一定范围内的在一定范围内的 数值解 的方法，以及这些方法的 误差传播规律、收敛性、稳定性，与如何 在计算机上 编程 有效实现 等问题的学科。

意义

计算机只能解决以四则运算为基础的，能在有穷步内结束的计算问题，高等数学和线性代数的许多理论与方法不能在计算机上直接应用。
众多生产实践与科学研究问题本身并不具备解析形式，或者用纯数学方法难以找到问题的解析解。
一些问题虽然具有解析形式，但过于复杂，计算机无法在可接受的时间内求解。
一些问题的解析解可能含有无穷多项，只能使用近似的计算方法去逼近问题的解。
在分析实验，观察数据时，需要使用插值、拟合等多种数值计算方法把一系列离散的数据关联起来。

计算方法的主要特点

严谨性：

计算方法的收敛性、稳定性与可靠性需要以数学理论为基础
实践性：

与实际应用、实际计算过程紧密相连
近似性:

用有穷取代无穷，变不可解为可解的方法，对数学问题近似求解，逐步求精
结构性：

由有穷步的四则运算构成：计算复杂性低；方法、流程与计算机程序一致

误差的基本概念

计算机中数的浮点表示

计算机中参与运算的数是用浮点表示的

\[ x = \pm a_1a_2 \cdots a_s \times \beta^c \]

其中 $1 \le a_1 < \beta, 0 \le a_i < \beta, i = 2, 3, \cdots, s\ge$, $c$是阶码

计算机中的舍入误差

大多数计算机以二进制形式存储数字，由于计算机字长有限，不是所有数字都可以被准确地表示，它们必须被舍入到适合计算机的字长，意味着被执行的算术运算使不精确的。

误差来源

观察误差

由于仪器的精密程度、实验手段、周围环境、人工作态度及能力等因素，观察或测量结果存在误差。

求解过程中，使用带有误差的观察数据作为数学模型的原始输入数据或已知参数引入观察误差。

模型误差

在建立数学模型时抓住问题最本质、起主导作用的方面，略去非本质的次要因素，将问题理想化再进行数学概括，模型与实际之间存在一定误差。

在将实际问题转化为数学模型的阶段引入模型误差。

截断误差

为了让计算机能解决数学上需要无穷次运算才能获得精确解的问题，通过有限次计算得到问题近似解，近似解与理论上的准确解存在误差。

在使用计算方法逼近数学模型的理论精确解的过程中引入截断误差，也称为「方法误差」。

舍入误差

由于计算机字长有限，在计算过程中的数据通过四舍五入或类似操作来保留有限位的有效数字，引入舍入误差。

误差与误差限

绝对误差

\[ e(x^\*) = x - x^\* \]

$x$ 为精确值， $x^\*$ 为 $x$ 的近似值

$e(x^\*)$可正可负。

绝对误差限

$|e(x^\*)|$的上限称为$ x^*$ 的绝对误差限，记为 $\varepsilon(x^\*)$

$\varepsilon(x^\*)$不唯一，越小越有参考价值

给定近似值$x^\*$ 的误差限$\varepsilon(x^\*)$，就可以直到准确值 $x$ 的区间，实际应用中一般记为 $x = x^\* \pm \varepsilon(x^\*)$

相对误差

\[ e_r(x^\*) =\frac{e(x^\*)}{x} = \frac{(x - x^\*)}{x} \] #### 相对误差限 $|e_r(x^\*)|$ 的上限称为 $x^\*$ 的相对误差限，记为 $\varepsilon_r(x^\*)$

有效数字与误差限的关系

定理1 如果近似数 $x^\* = \pm r^m \times (a_1 r^{-1} + a_2 r ^{-2} + \cdots + a_n r^{-n})$ 具有 $n$ 位有效数字，则可以得到 $x^\*$ 的一个绝对误差限： \[ |e(x^\*) | = |x - x^\*| \le \varepsilon(x ^\*) = \frac{1}{2} \times r^{m-n} \]
定理2 如果近似数 $x^\* = \pm r^m \times (a\_1 r^{-1} + a_2 r ^{-2} + \cdots + a_n r^{-n})$ 具有 $n$ 位有效数字，则可以得到 $x^\*$ 的一个相对误差限： \[ |e(x^\*) | = |x - x^\*| \le \varepsilon(x ^\*) = \frac{1}{2} \times r^{-(n - 1)} \]
定理3 如果近似数 $x^\* = \pm r^m \times (a_1 r^{-1} + a_2 r ^{-2} + \cdots + a_n r^{-n})$ 满足 \[ |e_r(x^\*)|\le \frac{1}{2(a_1+ 1)}\times r^{-(n-1)} \] 那么$x^\*$至少有 $n$ 位有效数字。

注意：任意移动小数点位置不影响有效数字位数。 #### 四则运算的误差传播公式 ##### 加减法 \[ \varepsilon(x^\* \pm y^\*) = \varepsilon(x^\*) + \varepsilon (y ^\*) \] ##### 乘法 \[ \varepsilon(x^\*y^\*) = |x^\*|\varepsilon(y^\*) + |y^\*|\varepsilon(x^\*) \] ##### 除法 \[ \varepsilon(\frac{x^\*}{y^\*})=\frac{|x^\*|\varepsilon(y^\*)+|y^\*|\varepsilon(x^\*)}{|y^\*|^2}, y \ne0, y^\* \ne 0 \]

(误差传播公式和求导公式有些相似）

设计计算方法的原则

计算方法的评判标准

稳定性的好坏
精度的高低
计算量的大小
存储量的大小
逻辑是否简单

基本原则

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

两个相近的数相减将导致有效数字的严重丢失。在设计计算方法时应设法避免这种情况发生，常用方法时变换计算公式：

常见变换公式： \[ \sqrt{x+ \varepsilon} - \sqrt{x} = \frac{\varepsilon}{\sqrt{x + \varepsilon} + \sqrt{x}}, \varepsilon \to 0 \] \[ ln(x + \varepsilon) - ln x = ln(1+\frac{\varepsilon}{x}),\varepsilon \to 0, 且 |x| \gg 0 \] \[ 1-cosx = 2sin^2 \frac{x}{2} , x\to 0 \] \[ e^x - 1 = (1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \cdots) - 1 = x (1 + \frac{x}{2} + \frac{x^2}{6} + \cdots), x\to 0 \] ##### 2.防止大数吃小数

当两个绝对值差异很大的数进行加减法运算时，绝对值小的数有可能因为计算机附点运算的特点而被“吃掉“，导致计算结果严重失真。

求二次方程的根 \[ \begin{cases} x_1 = \frac{-2c}{b + sgn(b)\sqrt{b^2 - 4ac}}, \quad sgn(b) = \begin{cases} 1, b\ge 0 \\\\ -1, b < 0 \end{cases}\\\\ x_2 = \frac{c}{ax_1} \end{cases} \]
在处理多个数求和操作时，一般按照从小到大的顺序累加，可以使求和的误差减到最小。

3. 避免采用绝对值很小的数作为除数

当采用绝对值很小的数作为分母时，容易产生浮点溢出现象，同时可能引起大数吃小数的情况出现，导致误差很大。

4. 简化运算步骤，减少运算次数

良好的计算方法应该具有可接受的时间复杂度和（存储）空间复杂度。
简化运算步骤不但能够有效地减少运算时间，同时也能减少舍入误差的积累。
计算机处理速度顺序 \[ (+, -)>(\times, \div)>(exp) \]
在设计计算方法时应该尽量使用速度较快的加减运算。

5. 控制计算方法的误差传播，保证计算方法的稳定性

稳定性算法：在运算过程中误差逐步衰减的算法
不稳定算法：误差的积累越来越大的算法

参考资料

《数值计算》