1. §1.2 Roundoff Errors and Computer Arithmetic

1.1. 截断误差和舍入误差

• 截断误差(truncation error): 使用截断的（或者说有限的）求和来近似无穷级数的和产生的误差。
  • 理论：$e=\sum\limits_{n=0}^{\infty} \frac{1}{n!}$
  • 计算机: $e=\sum\limits_{n=0}^{N} \frac{1}{n!}$
• 舍入误差(roundoff error): 当计算机执行实数计算时产生的误差。这是因为计算机中的算术运算涉及到的数字只有有限位数。
  • 理论：$0.3333333\cdots$
  • 计算机: $0.333333$

1.2. 截断法和舍入法

使用截断法或舍入法产生的误差都叫做 舍入误差(roundoff error)。

• 截断法(chopping)：0.1119 -> 0.111
• 舍入法(rounding)：0.1119 -> 0.112

给定一个 实数的标准十进制浮点形式(normalized decimal floating-point form of a real number) $y = 0.d_1d_2d_3\ldots d_kd_{k+1}\ldots \times 10^n$，则使用 chopping 或 rounding 的结果为：

1.3. 绝对误差与相对误差

用 $p^*$ 表示 $p$ 的 近似值(approximation)。

• 绝对误差(absolute error)：$|p^* - p|$
• 相对误差(relative error)：$\dfrac{|p^* - p|}{|p|}$

有效位(significant digit / significant figure)：对于 $p$ ，若近似值 $p^\ast$ 满足 $\displaystyle{\dfrac{|p^* - p|}{|p|}<5 \times 10^{-t}}$ 则称 $p^{\ast}$ 有 $t$ 有效位。

1.4. 秦九韶算法 | Horner’s Method

乘法较多会导致式子的误差较大，秦九韶算法(Horner’s Method) 通过不断提取 $x$ 来减少乘法的次数，即把多项式 $f(x) = a_nx^n + a_{n-1}x^{n-1} + \ldots + a_1x + a_0$ 写成如下形式：

然后从最内层开始计算。

2. §1.3 Algorithms and Convergence

2.1. 稳定性 | Stability

一个算法，如果初始数据的小变化会导致最终结果的小变化，则称为 稳定(stable)；否则称为 不稳定(unstable)。如果只有在某些初始数据的选择下才稳定，则称为条件稳定(conditionally stable)。

2.2. 误差增长

假设 $E_0 > 0$ 是 初始误差(initial error)，$E_n$ 是第 $n$ 步的误差。

• 如果 $E_n \approx CnE_0$，则称为 线性增长(linear growth)。

线性增长的误差通常是无法避免的，当 $C$ 和 $E_0$ 都很小的时候，结果通常是可以接受的。

• 如果 $E_n \approx C^nE_0$，则称为 指数增长(exponential growth)。

指数增长的误差应该避免，因为即使 $E_0$ 很小，$C^n$ 也会变得很大。这会导致不可接受的不准确性。

2.3. 收敛率 | Rate of Convergence

收敛率(rate of convergence)：设 $\displaystyle{\lim_{h\to 0} F(h) = L}$，$\displaystyle{\lim_{h\to 0} G(h) = 0}$。如果存在正常数 $K$ 使得 $\displaystyle{|F(h)-L| \leq K|G(h)|}$ 对于足够小的 $h$ 成立，则记为 $F(h)=L+O(G(h))$。我们通常取 $G(h)=h^p\ (p>0)$，且一般只对最大的 $p$ 值感兴趣。

3. IEEE 754 Floating Representation

• 符号位 sign：一般来说正数就是 0 负数就是 1。
• 尾数 significand / fraction：去除符号位后应被移到 $1.\text{xxxxx}$ 的形式，所以最高位的 1 可以被省略。
  • 对于一些不使用 hidden 1 策略的表示方式则移到 $0.1\text{xxxxx}$ 的形式，注意不同的方式会影响阶码的值。
• 指数 exponent：用移码表示，单精度浮点数的 偏移(bias) 为 $127$，双精度浮点数的偏移为 $1023$（刚好是范围的一半）。

• 单精度浮点数
  • 最小值：指数 = 00000001，小数 = 000...000；$x = \pm (1+0.0) \times 2^{1-127} = \pm 1.0 \times 2^{-126} \approx \pm 1.2 \times 10^{-38}$
  • 最大值：指数 = 11111110，小数 = 111...111；$x = \pm (1+0.111\ldots 111) \times 2^{254-127} \approx \pm 2.0 \times 2^{127} \approx \pm 3.4 \times 10^{38}$
  • 最小分度：$2^{-23}$；$\log_{10}{2^{-23}}\approx -6.92$，故约为小数点后 6 位有效数字
• 双精度浮点数：
  • 最小值：指数 = 00000000001，小数 = 000...000；$x = \pm (1+0.0) \times 2^{1-1023} = \pm 1.0 \times 2^{-1022} \approx \pm 2.2 \times 10^{-308}$
  • 最大值：指数 = 11111111110，小数 = 111...111；$x = \pm (1+0.111\ldots 111) \times 2^{2046-1023} \approx \pm 2.0 \times 2^{1023} \approx \pm 1.8 \times 10^{308}$
  • 最小分度: $2^{-52}$；$\log_{10}{2^{-52}}\approx -15.65$，故约为小数点后 15 位有效数字

4. 参考资料

• Chapter 1 Mathematical Preliminaries - Jiepeng's notes