Mathematical Preliminaries

Roundoff Errors

舍入误差 (Roundoff Errors) 是使用有限位数的浮点数替代实数时产生的误差，即计算机进行实数运算时产生的误差。

Absolute/Relative Error

设 \(p^*\) 是 \(p\) 的近似值，则

• 绝对误差 (Absolute Error) 是实际值与近似值之差的绝对值，即 \(|p - p^*|\)
• 相对误差 (Relative Error) 是绝对误差与实际值之比，即 \(\dfrac{|p - p^*|}{|p|}\)

Significant Digits

给定实际值 \(p\) 和近似值 \(p^*\)，设 \(t\) 是满足下式的最大非负整数

则称 \(p^*\) 将 \(p\) 近似到 \(t\) 位有效数字 (Significant Digits)。(approximate \(p\) to \(t\) significant digits)

Stability

• 算法的稳定性 (Stability) 是指算法的输出对于输入（初始数据）的微小变化而言，输出结果的变化也是微小的
• 如果满足该标准，则称为稳定 (stable) 的，反之则是不稳定 (unstable) 的
• 如果仅对满足特定条件的初始数据稳定，则称为条件稳定 (conditionally stable) 的

Linear/Exponential Growth

假设在算法实施的某个阶段引入了大小为 \(E_0\) 的误差，在其后的第 \(n\) 次运算中的误差记为 \(E_n\)，考虑其增长速度。

• 如果 \(E_n\approx CnE_0\)，\(C\) 是与 \(n\) 无关的常数，则称为线性增长 (linear growth)
• 如果 \(E_n\approx C^nE_0\)，\(C>1\) 是与 \(n\) 无关的常数，则称为指数增长 (exponential growth)