# 第 5 章 数值计算基础


> 模型的数学形式与它在计算机里的实际行为之间的差距，全部来自浮点数只有有限位这一个事实。本章解释这个差距从哪来、如何量化，并给出 Softmax、方差、累加、插值、迭代求解这些具体场景的稳定写法。

## 学习目标

读完本章，你应当能够：
1. 画出 FP32 与 FP64 的位布局，写出规格化数的表示式，说出机器 epsilon 与可表示范围；
2. 解释 `0.1 + 0.2 ≠ 0.3` 的完整原因，并区分舍入误差、截断误差与灾难性相消；
3. 推导 Softmax 减最大值为何是等价变换，并说明它在掩码注意力中的作用；
4. 推导单遍法 `E[X²] − (E[X])²` 的误差放大因子，说明何时它会给出负数，并写出两遍法替代方案；
5. 写出 Kahan 补偿求和并解释它为什么能把误差从 `O(n·u)` 降到 `O(u)`；
6. 证明插值多项式的存在唯一性，写出 Lagrange 与 Newton 两种形式并构造差商表，解释龙格现象；
7. 推导 Jacobi、Gauss-Seidel 与 SOR 的迭代矩阵与收敛性判据，并与 LU、Cholesky 直接法对比；
8. 定义条件数、推导误差放大界，识别病态问题并用正则化处理；
9. 在编程题里正确选择 `EPS`、正确的舍入模式与正确的同分断号规则。

### 前置知识检查

| 你需要知道 | 在哪一节补齐 |
|---|---|
| 二进制与十进制小数的互相转换 | 5.1.2 |
| 泰勒展开与"截断到若干项"的含义 | 5.2.1 |
| 下三角、上三角与矩阵分块（沿用第 1 章） | 5.5.1 |
| 特征值、谱半径与正定矩阵（沿用第 3 章） | 5.5.2 |

## 5.1 IEEE 754 浮点表示

### 5.1.1 位布局与规格化数

一个浮点数用三段存储：**符号位**、**偏置指数**、**尾数（有效数字）**。

| 格式 | 总位数 | 符号 | 指数位 | 尾数位 | 偏置 | 最小规格化正数 | 最大有限值 | 十进制有效位 |
|---|---|---|---|---|---|---|---|---|
| FP32 | 32 | 1 | 8 | 23 | 127 | `2^(−126) ≈ 1.18e−38` | `≈ 3.40e38` | 约 7 位 |
| FP64 | 64 | 1 | 11 | 52 | 1023 | `2^(−1022) ≈ 2.23e−308` | `≈ 1.80e308` | 约 16 位 |

```
规格化数的表示式（尾数隐含前导 1，故实际精度是"尾数位 + 1"）：
  x = (−1)^s × 1.f₂ × 2^(e − bias)         f₂ 是尾数位构成的二进制小数
  有效位数 p = 尾数位 + 1 = 24（FP32）/ 53（FP64）
  相邻可表示数之间的最大相对间距 = 2^(−p)，称为单位舍入误差 u：
      FP32 u = 2^(−24) ≈ 5.96e−8       FP64 u = 2^(−53) ≈ 1.11e−16
"机器 epsilon" 的两种常见口径（读论文前先确认作者用哪一种）：
  口径一（1 与下一个更大浮点数之差）：ε = 2^(−(p−1))，FP32 ≈ 1.19e−7、FP64 ≈ 2.22e−16
  Python 的 sys.float_info.epsilon 用的是口径一，值为 2.22e−16
```

尾数要隐含那个前导 1，是因为规格化数小数点前必然是 1，省掉它就白得一位精度；代价是真正的 0 无法用规格化形式表示，必须让指数全 0 走**非规格化数**分支，这也是渐进下溢（gradual underflow）的来源。

### 5.1.2 为什么 `0.1 + 0.2 ≠ 0.3`

根因是**十进制小数 `0.1` 在二进制下是无限循环小数**，而尾数只有 52 位。用"乘 2 取整"把它展开：

```
0.1 × 2 = 0.2 → 取整 0      0.1₁₀ = 0.0001100110011001100…₂
0.2 × 2 = 0.4 → 取整 0              └─ 0011 无限循环 ─┘
0.8 × 2 = 1.6 → 取整 1       规格化后：1.1001100110011…₂ × 2^(−4)
1.6 × 2 = 1.2 → 取整 1
0.2 × 2 = 0.4 → 取整 0   ⟲ 回到第二行，循环开始

FP64 中实际存储的值：0.1 → 0.1000000000000000055511151231257827…（偏大）
                     0.2 → 0.2000000000000000111022302462515654…（偏大）
                     0.3 → 0.2999999999999999888977697537484346…（偏小）
  0.1 + 0.2 = 0.3000000000000000444089209850062616… ≠ 0.3

两个误差没有抵消：0.1 与 0.2 的存储值都偏大，相加后误差叠加，
恰好落在 0.3 的存储值的另一侧。只有分母是 2 的幂的十进制小数
（0.5、0.25、0.125）才能在二进制下精确表示。
```

> [!IMPORTANT]
> 这不是 Python 或某个语言的 bug，而是 IEEE 754 的必然结果：**任何"比较两个浮点数是否相等"的代码都应改写成"比较它们的差是否小于容差"**，完整判据见 5.7 节。

## 5.2 误差来源与传播

### 5.2.1 四类误差

| 误差 | 来源 | 量级 | 典型例子 |
|---|---|---|---|
| 表示/舍入误差 | 结果被舍入到最近的可表示数 | 相对 `≤ u`（FP64 约 `1.1e−16`） | `0.1` 的存储值 |
| 截断误差 | 用有限项近似无限过程 | 由算法阶数决定，与 `u` 无关 | 泰勒展开只取前两项；迭代法提前停止 |
| 灾难性相消 | 两个相近的数相减 | 相对误差放大 `(\|x\|+\|y\|)/\|x−y\|` 倍 | `E[X²] − (E[X])²` |
| 误差传播/放大 | 问题的条件数放大输入扰动 | 放大 `cond(A)` 倍 | 病态线性方程组 |

**关键区分**：舍入误差与截断误差来源完全不同，减小其中一个不能减小另一个。提高浮点精度（FP32 → FP64）只把 `u` 缩小，对截断误差毫无帮助；反之提高算法阶数只减小截断误差。工程上必须同时评估两者。

### 5.2.2 浮点运算模型与灾难性相消

IEEE 754 规定四则运算的结果是**精确结果舍入到最近的可表示数**，于是有标准的误差模型 `fl(x op y) = (x op y)(1 + δ)`，`|δ| ≤ u`。由此看两个带误差的输入相减：

```
设 x̂ = x(1 + δ₁)、ŷ = y(1 + δ₂)，|δ_i| ≤ u，则 x̂ − ŷ = (x − y) + (xδ₁ − yδ₂)，
绝对误差 ≤ u·(|x| + |y|)，相对误差 ≤ u·(|x| + |y|) / |x − y|
⟹ 当 x ≈ y 时分母 → 0，相对误差被放大到无法接受，这就是灾难性相消。
```

相消本身不产生误差（两个相近浮点数相减在 IEEE 下是**精确**的），它只是把输入里原本就存在的、被大数掩盖住的相对误差**暴露**出来。这一点是理解后面三个案例的关键：**解决办法不是提高精度，而是改写公式，避免让大数相减**。

## 5.3 三个数值稳定性的实战案例

### 5.3.1 Softmax 减去最大值

真题 `【2026-08-05 选择 Q1】` 的直接考点。原式 `softmax(x)_i = e^(x_i)/Σ_j e^(x_j)` 会迅速溢出：FP32 中 `e^x` 的上溢阈值是 `x > ln(3.40e38) ≈ 88.7`，FP64 放宽到 `709.8`。一旦某个 `e^(x_i)` 变成 `inf`，整个比值变成 `inf/inf = nan`。把精度从 FP32 换成 FP64 只是把阈值从 88.7 推到 709.8，`x_i = 1000` 时照样溢出。标准解法是减去最大值 `m = max_j x_j`，而这是一个**严格的恒等变换**：

```
        e^(x_i)              e^(−m)·e^(x_i)            e^(x_i − m)
  ─────────────────  =  ─────────────────────────  =  ─────────────────
    Σ_j e^(x_j)          e^(−m)·Σ_j e^(x_j)          Σ_j e^(x_j − m)
```

分子分母同乘一个正常数 `e^(−m)`，比值不变。变换后所有指数自变量落在 `(−∞, 0]`，故 `e^(x_i − m) ∈ (0, 1]`，**永不上溢**；同时分母至少含 `e^(m − m) = 1`，也永不下溢为零。真题的干扰项中，L2 归一化 `x/‖x‖` 与"除以最大值"都改变了各分量之间的差值，算出的是另一个分布；改用 FP64 只是推迟溢出。

> [!IMPORTANT]
> 掩码注意力把被 mask 的位置置为 `−∞`，于是 `e^(−∞) = 0`，这些位置**既不进分子也不进分母**，与"只在有效集合内做 Softmax"严格等价。真题 `【2026-09-02 编程题 1】` 用到这一点：窗口内至少有位置 `i` 自己（`|i − i| = 0 ≤ ω`），所以每行的最大值必为有限数，减最大值这一步永远安全。

### 5.3.2 方差的两遍法与单遍法

**两遍法**先生成均值再求平方偏差的平均；**单遍法**用 `E[X²] − (E[X])²`。二者数学上恒等，数值上差别巨大：

```
记 μ = E[X]，σ² = Var(X)，则 E[X²] = μ² + σ²，单遍法要算 (μ² + σ²) − μ²：
两个操作数量级都是 μ²，真正的结果却只有 σ²。
  放大因子 = (μ² + σ²)/σ² = 1 + (μ/σ)²      ⟹ 相对误差 ~ u·(1 + (μ/σ)²)

本例取 x = {1e8+1, 1e8+2, 1e8+3}，真值 Var = 2/3 ≈ 0.667。
单遍法得 E[X²] ≈ 1e16 + 4e8 + 4.667 与 (E[X])² ≈ 1e16 + 4e8 + 4，
两者量级都是 1e16，而 FP64 在该量级的相邻间距 ulp = 2^(53−52) = 2
（1e16 ≈ 2^53.15，二进制指数为 53），故两个操作数各自被舍入到最近的偶数，
差值只能取 0 或 2，根本得不到 0.667。本例 μ/σ = 1.2e8，放大因子 ~1.5e16，
乘 u ≈ 1.1e−16 得相对误差 ~1.6 > 1：结果完全失真，"方差"甚至可能为负。
```

> [!WARNING]
> 真题 `【2026-09-04 编程题 1】` 的参考代码里有一行 `if var < 0.0: var = 0.0`，正是为了兜住这种情况：用前缀和求窗口方差时公式 `(P2[hi+1] − P2[lo])/m − μ²` 就是单遍法，大均值小方差的窗口会算出 `−1e−16` 这类负值，而负数开根号会直接抛异常。**这行截断不是"防御性编程"，而是该公式的必然要求。**

| 写法 | 公式 | 数值稳定性 | 能否 `O(1)` 查询任意窗口 | 结论 |
|---|---|---|---|---|
| 两遍法 | 先求 `μ`，再算 `(1/n)Σ(x_i − μ)²` | 好，无相消 | 否，每个窗口都要重扫 | 一次性统计量（如全局 z-score）首选 |
| 单遍法 | `(1/n)Σx_i² − μ²` | 差，放大 `1 + (μ/σ)²` | 能，配合前缀和即可 | 滑动窗口必须用，但要截断负值 |

真题 `【2026-09-04 编程题 1】` 正是这样分工：窗口统计量用两条前缀和（`O(1)` 查询，必须用单遍法），全局 z-score 只用一次（用两遍法更稳）。**当窗口宽度 `w` 与数据量 `n` 同量级时，逐点重扫是 `O(n·w)` 接近 `O(n²)`，前缀和把这一步压到 `O(n)`——这个性能收益值得接受单遍法的精度代价。**

### 5.3.3 大量浮点累加与 Kahan 求和

朴素累加的误差随项数线性增长：大数在前、小数在后时，每个小数都可能被完全丢弃。误差界是 `(n − 1)·u·Σ|x_i|`，注意它相对的是 `Σ|x_i|` 而不是结果——正负项大量抵消时结果的绝对值很小而 `Σ|x_i|` 很大。极端情形：`x = {1e16, 1, −1e16}`，朴素求和得 0，正确结果是 1。**Kahan 补偿求和（compensated summation）**用一个额外变量把每次丢掉的低位收集起来，下一轮补回去：

```python
def kahan_sum(values):
    """补偿求和：把每次加法丢掉的低位收集到 comp 里，下一轮再补回去"""
    total = 0.0
    comp = 0.0                       # 上一轮被舍入丢掉的部分
    for x in values:
        y = x - comp                 # 先把欠账补上
        t = total + y                # 这一步可能丢掉低位
        # (t - total) 在浮点下是精确的（两个相近数相减无误差，见 5.2.2），
        # 因此它能无损地还原 total + y 时被丢掉的量；减去 y 就得到误差本身
        comp = (t - total) - y
        total = t
    return total
```

关键在 `comp = (t − total) − y`：当 `|y|` 远小于 `|total|` 时，`t − total` 在 IEEE 下**精确**，因此能无损地把舍入误差提取出来。于是误差界从 `O(n·u·Σ|x_i|)` 降到 `O(u·Σ|x_i| + n·u²·Σ|x_i|)`，主项与 `n` 无关。代价是每次加法多做 4 次浮点运算，且**不可向量化**。实际取舍：对精度敏感的标量累加（损失累计、期望估计）用 Kahan；对 GPU 上的批量归约改用分块（tree reduction）——它把误差界从 `O(n)` 降到 `O(log n)`，且天然并行，这正是深度学习框架的默认做法。

## 5.4 插值：Lagrange 与 Newton

### 5.4.1 存在唯一性与 Lagrange 形式

给定 `n + 1` 个**互不相同**的节点 `(x₀, y₀), …, (x_n, y_n)`，问：是否存在次数不超过 `n` 且过这些点的多项式？如果有，是否唯一？

```
唯一性：设 p(x)、q(x) 都是次数 ≤ n 且过全部 n+1 个节点的多项式，
  令 r(x) = p(x) − q(x)。则 deg r ≤ n，且对每个节点
      r(x_i) = p(x_i) − q(x_i) = y_i − y_i = 0
  即 r 有 n+1 个互不相同的根。而次数不超过 n 的非零多项式最多有 n 个根，
  所以只能是 r ≡ 0，即 p = q。

存在性（构造）：定义 Lagrange 基函数 ℓ_i(x) = Π_{j ≠ i}(x − x_j)/(x_i − x_j)。
  由构造，ℓ_i(x_i) = 1（分子分母相同），ℓ_i(x_j) = 0（j ≠ i 时分子含 (x_j − x_j)）。
  于是 L(x) = Σ_{i=0}^{n} y_i·ℓ_i(x) 在每个节点取值为 y_i，存在性得证。
```

这套证明同时给出一个必须记住的结论：**插值多项式与节点顺序无关，只由节点集合决定**——这正是真题 `【2026-09-04 选择 Q10】` 的答案 D"两者在数学表达式上恒等唯一"的依据。选项 A、C 说反了：Lagrange 的每个基函数都含全部节点，增加一个节点必须整体重算，适合动态加点的是 Newton 而不是 Lagrange。

### 5.4.2 Newton 形式与差商表

Newton 形式把同一个多项式写成"逐步加项"的嵌套结构，用**差商**作系数：

```
N(x) = f[x₀] + f[x₀,x₁](x − x₀) + f[x₀,x₁,x₂](x − x₀)(x − x₁) + …
                … + f[x₀,…,x_n](x − x₀)(x − x₁)…(x − x_{n−1})

差商递推：f[x_i] = y_i，f[x_i,…,x_{i+k}] = (f[x_{i+1},…,x_{i+k}] − f[x_i,…,x_{i+k−1}])/(x_{i+k} − x_i)
差商表（自上而下、自左而右地算，左下对角线就是 Newton 系数）：
      x_i    f[x_i]        一阶                   二阶
      0      1
                           (2−1)/(1−0) = 1
      1      2                                   (3−1)/(2−0) = 1
                           (5−2)/(2−1) = 3
      2      5

验证（真题 【2026-08-05 选择 Q9】的三个点 (0,1), (1,2), (2,5)）：
  N(x) = 1 + 1·(x − 0) + 1·(x − 0)(x − 1) = 1 + x + x² − x = x² + 1
  N(1.5) = 2.25 + 1 = 3.25  ✓    与直接解方程组 a = 1, b = 0, c = 1 的答案一致
```

| 对比 | Lagrange | Newton |
|---|---|---|
| 数学等价性 | 同一个多项式的两种写法，展开后系数完全一致 | 同左 |
| 动态增加节点 | 每个基函数含全部节点，必须整体重算 | 只需再算一阶差商，原有项全部保留 |
| 计算复杂度 | 求值 `O(n²)` | 差商表 `O(n²)`，用嵌套（秦九韶式）求值 `O(n)` |

### 5.4.3 龙格现象与"插值不等于拟合"

**插值不等于拟合**：插值要求曲线**穿过每一个点**，拟合只要求**整体偏差最小**、不要求穿过任何点。

| 维度 | 插值 | 拟合（最小二乘） |
|---|---|---|
| 约束 | 过全部 `n+1` 个点 | 无硬约束，最小化 `Σ(残差)²` |
| 自由度 | 多项式次数被 `n+1` 个点唯一确定 | 次数由我们选择，可与点数无关 |
| 对噪声 | 极敏感：一个坏点就把整条曲线拽走 | 稳健：噪声被平均掉 |
| 典型用途 | 查表、离散数据补齐（如 `【2026-09-04 编程题 1】` 的线性插值） | 回归、趋势估计、参数辨识 |

**龙格现象（Runge phenomenon）**说明"插值点越多越好"是错的。对 `f(x) = 1/(1 + 25x²)` 在 `[−1, 1]` 上取**等距节点**插值，随节点数 `n` 增大，区间中部收敛，但**两端附近剧烈振荡，最大误差反而发散**。原因是等距节点在两端"密度不足"，高次多项式的导数在端点附近被放大。解决办法是把节点换成 **Chebyshev 节点** `x_k = cos(kπ/n)`——它们在两端自动加密，可使误差随 `n` 一致收敛。

> [!TIP]
> 工程上的通用结论：**节点超过 10 个左右就不要再提高插值多项式的次数**，而应改用分段低次插值（三次样条）或直接转向拟合。真题 `【2026-09-04 编程题 1】` 的第一步用**两点线性插值**，正是"用最低次数的分段插值换取稳定性"的实例。

## 5.5 线性方程组的迭代法

### 5.5.1 三种迭代格式的推导

把系数矩阵拆成对角、严格下三角、严格上三角三部分：`A = D + L + U`。迭代法的共同思路是把 `A` 的一部分留在左端"隐式求解"、另一部分移到右端"用旧值显式求值"。

```
Jacobi：左端只留 D，整轮全用上一轮的旧值
  D x^(k+1) = b − (L + U)x^(k) ⟹ x^(k+1) = −D⁻¹(L + U)x^(k) + D⁻¹b
  迭代矩阵 B_J = −D⁻¹(L + U)；分量形式 x_i^(k+1) = (b_i − Σ_{j≠i} a_ij x_j^(k))/a_ii

Gauss-Seidel：把 L 也挪到左端，算新分量时立刻用上本轮已更新的值
  (D + L)x^(k+1) = b − U x^(k) ⟹ x^(k+1) = −(D + L)⁻¹U x^(k) + (D + L)⁻¹b
  迭代矩阵 B_GS = −(D + L)⁻¹U
  分量形式 x_i^(k+1) = (b_i − Σ_{j<i} a_ij x_j^(k+1) − Σ_{j>i} a_ij x_j^(k))/a_ii
                       └─ 用本轮新值 ─┘          └─ 用上轮旧值 ─┘

SOR（逐次超松弛，松弛因子 ω）：在 Gauss-Seidel 的更新上做外推
  (D + ωL)x^(k+1) = [(1 − ω)D − ωU]x^(k) + ωb ⟹ B_ω = (D + ωL)⁻¹[(1 − ω)D − ωU]
  ω = 1 时退化为 Gauss-Seidel；0 < ω < 2 是收敛的必要条件。
```

| 方法 | 迭代矩阵 | 每轮是否用新值 | 需要存储 |
|---|---|---|---|
| Jacobi | `−D⁻¹(L + U)` | 否，全用旧值 | 两份 `x`（旧、新） |
| Gauss-Seidel | `−(D + L)⁻¹U` | 是 | 一份 `x`，可原地更新 |
| SOR | `(D + ωL)⁻¹[(1 − ω)D − ωU]` | 是 | 一份 `x` |

真题 `【2026-09-09 选择 Q8】` 问的就是 Gauss-Seidel 的迭代矩阵，答案是 `−(D + L)⁻¹U`。三个干扰项各有出处：`−D⁻¹(L + U)` 是 **Jacobi** 的迭代矩阵（只把 `D` 留在左端）；把 `L` 与 `U` 对调得到的是**后向 Gauss-Seidel**（按逆序更新）；丢掉负号与 `L` 的组合不对应任何标准格式。

### 5.5.2 收敛性判据

把误差 `e^(k) = x^(k) − x*` 代入迭代式 `x^(k+1) = B x^(k) + c`，立刻得到 `e^(k) = B^k e^(0)`，于是收敛（对任意初值）等价于 `B^k → 0`，即 **`ρ(B) < 1`**——这是充要条件，不能用范数代替。**严格对角占优**（`|a_ii| > Σ_{j≠i}|a_ij|` 对所有 `i` 成立）是充分条件：

```
B_J = −D⁻¹(L + U) 的对角元为 0，非对角元为 −a_ij/a_ii，故
  ‖B_J‖_∞ = max_i Σ_{j≠i} |a_ij| / |a_ii| < 1        （正是严格对角占优的定义）
而谱半径不超过任何诱导范数：ρ(B_J) ≤ ‖B_J‖_∞ < 1，故迭代收敛。
Gauss-Seidel 的证明更复杂，但结论相同：严格对角占优时它也收敛。
```

> [!WARNING]
> **`ρ(B) < 1` 是充要条件，`‖B‖ < 1` 只是充分条件。** 完全可能出现 `ρ(B) < 1` 但某个诱导范数大于 1 的情况——此时迭代仍然收敛，只是前若干轮误差可能先增长再衰减。判断收敛性要看谱半径，不能用范数代替。

### 5.5.3 与直接法的对比

| 维度 | 直接法（LU、Cholesky） | 迭代法（Jacobi、GS、SOR） |
|---|---|---|
| 计算量 | LU `O(n³)`；对称正定用 Cholesky 约 `O(n³/3)` | 每轮 `O(nnz)`，即非零元个数 |
| 稀疏矩阵 | 分解产生**填充**，破坏稀疏性、内存爆炸 | 只做矩阵-向量乘，稀疏性完全保留 |
| 误差 | 一次求解，误差由条件数决定 | 逐步逼近，可随时停机 |
| 适用规模 | 中小规模稠密问题（`n` 到几千） | 大规模稀疏问题（`n` 到百万） |
| 前提条件 | 可分解（Cholesky 要求对称正定） | 收敛性 `ρ(B) < 1` 不总成立 |

**为什么大规模稀疏问题必须用迭代法**：一个 `n = 10⁶` 的稀疏矩阵，直接分解产生的填充可能让非零元从 `O(n)` 涨到 `O(n²)`，内存需求超出任何机器；而迭代法每轮只需一次稀疏矩阵-向量乘，内存恒为 `O(nnz)`。第 6 章的梯度下降与第 9 章的正规方程求解都在同一权衡上做选择。

## 5.6 条件数与病态问题

**条件数（condition number）**衡量"输入的小扰动会被放大多少倍"，对可逆矩阵 `A` 定义为 `cond(A) = ‖A‖·‖A⁻¹‖ = σ_max(A)/σ_min(A)`。误差放大界的推导：

```
设 Ax = b，而实际算了 A(x + δx) = b + δb。两式相减得 A·δx = δb，即 δx = A⁻¹δb，
故 ‖δx‖ ≤ ‖A⁻¹‖·‖δb‖；又由 b = Ax 得 ‖b‖ ≤ ‖A‖·‖x‖，即 1/‖x‖ ≤ ‖A‖/‖b‖。
两式相乘：‖δx‖/‖x‖ ≤ ‖A‖·‖A⁻¹‖·‖δb‖/‖b‖ = cond(A)·‖δb‖/‖b‖
```

**识别与处理**：`cond(A) ≫ 1/u` 时结果完全不可信——用 FP64 的 `u ≈ 1.1e−16` 代入，`cond(A) ≈ 1e16` 意味着输入的第 16 位有效数字被放大到第 1 位。四个征兆：消元中出现极小主元；最小奇异值接近 0（见第 3 章）；列近似线性相关；解代回后残差很大。**但残差小并不代表解准**：病态问题的残差可以很小而误差很大。最常用的处理是岭回归（Tikhonov 正则化）：

```
min_x ‖Ax − b‖² + λ‖x‖²
对 x 求导置零：2Aᵀ(Ax − b) + 2λx = 0 ⟹ (AᵀA + λI)x = Aᵀb ⟹ x = (AᵀA + λI)⁻¹Aᵀb
为什么能改善条件数：AᵀA 的奇异值是 σ_i²，而 AᵀA + λI 的是 σ_i² + λ，于是
  cond(AᵀA + λI) = (σ_max² + λ)/(σ_min² + λ) < σ_max²/σ_min² = cond(AᵀA)
λ 越大条件数越接近 1，但偏差也越大——这就是第 4 章 4.6.3 节的偏差—方差权衡。
第 8 章会从贝叶斯角度再解释：λ‖x‖² 等价于对权重施加均值为 0、方差为 1/(2λ) 的
高斯先验，岭回归就是该先验下的 MAP 估计。同一件事在数值分析里叫"改善条件数"，
在统计学习里叫"正则化"，在贝叶斯里叫"先验"，三者是同一个数学对象。
```

## 5.7 浮点比较与 EPS 工程实践

```
① 绝对容差 |a − b| ≤ EPS，适用于量级已知且相差不大的场景（坐标、评分）
② 相对容差 |a − b| ≤ EPS·max(1, |a|, |b|)，适用于量级未知或跨度很大的场景
   （max 中的 1 是为了兼容 a、b 接近 0）
③ 组合判据（Python math.isclose 的默认行为）：|a − b| ≤ max(REL·max(|a|,|b|), ABS)
选择 EPS 的唯一原则：EPS 必须【大于】累加噪声（约 n·u·尺度），同时远【小于】真实需要区分的最小间隙。
```

用真题 `【2026-09-09 编程题 2】` 的数字代入：簇内代价由若干项乘加累加而成，噪声量级约 `1e−15`；而题目要求区分的是"数学上相等"与"真正更优"，后者往往相差 `1e−6` 以上。于是取 `EPS = 1e−9`：比噪声大 6 个数量级，比真实间隙小 3 个数量级，两端都留足余量。

**场景一：同分断号（`【2026-09-09 编程题 2】`）。** 题目规定"多个 CDN 距离相同时选序号靠前的"，实现上通常写成"只有严格更优才更新"；但若直接写成 `cost < best_cost`，两个候选代价**数学上相等**时浮点可能相差 `1e−15`，谁胜出完全由末位误差决定，规则就失控了。

```python
EPS = 1e-9   # 比累加噪声（约 1e-15）大一个量级，又远小于真实可分辨的代价间隙

def pick_best(costs):
    """按 (代价, 序号) 字典序取最优：代价相等时保留序号靠前的那个"""
    best_idx, best_cost = -1, 0.0
    for i, cost in enumerate(costs):
        # 判据是 cost < best_cost − EPS 而不是 cost < best_cost：
        # 只有"超出容差地更优"才改判，数学上相等的两者由先遍历到的（序号小的）胜出
        if best_idx < 0 or cost < best_cost - EPS:
            best_idx, best_cost = i, cost
    return best_idx
```

**场景二：方差截断（`【2026-09-04 编程题 1】`）。** 前缀和求窗口方差时 `var` 可能算出 `−1e−16`，必须截断到 0 再开方（理由见 5.3.2）；同理 `σ = 0` 时 z-score 的分母为 0，应直接规定 `z_i = 0`，而不是依赖 IEEE 的 `0/0 = nan`。

**场景三：距离恰好等于半径（`【2026-08-05 编程题 1】`）。** 判断"点是否落在圆内"时 `d ≤ r` 与 `d² ≤ r²` 数学上等价，但两条路径的舍入误差不同：开方引入一次舍入，平方也可能引入。稳妥做法是统一在**平方域**比较（少一次开方，也避免 `sqrt` 在定义域边界附近放大相对误差），确需比较 `d` 与 `r` 本身时写成 `d ≤ r + EPS`。

> [!TIP]
> 舍入模式也是陷阱。题目要求"恰为 `.5` 时向上取整"（half-up），而 Python 内置的 `round()` 用的是**银行家舍入（banker's rounding）**：`round(0.5) = 0`、`round(1.5) = 2`、`round(2.5) = 2`。真题 `【2026-09-04 编程题 1】` 的最后一问必须写成 `int(math.floor(x + 0.5))`——先用 `floor` 固定"下取整"语义，再靠 `+0.5` 实现 half-up；写成 `round()` 会在 `.5` 处与题面要求系统性对不上。

## 本章小结

| 关键结论 | 一句话表述 | 常见错误 |
|---|---|---|
| IEEE 754 位布局 | `1+8+23`（FP32）、`1+11+52`（FP64），尾数隐含前导 1 | 把机器 epsilon 的两种口径混用 |
| `0.1 + 0.2 ≠ 0.3` | 十进制小数在二进制下循环，尾数截断后误差叠加；`u ≈ 1.1e−16`（FP64） | 把它当成语言 bug |
| 灾难性相消 | 相近数相减，相对误差放大 `(\|x\|+\|y\|)/\|x−y\|` 倍 | 以为提高精度就能解决 |
| Softmax 稳定化 | 减 `max` 是唯一保值的等价变换；`e^(−∞) = 0` 让掩码自洽 | 用 L2 归一化或除以最大值代替 |
| 方差单遍法 | 放大因子 `1 + (μ/σ)²`，大均值小方差时结果可为负 | 忘记 `var < 0` 截断 |
| 前缀和 vs 两遍法 | 窗口统计必须用前缀和（`O(1)`），全局统计优先两遍法 | 在所有场景都硬用单遍法 |
| Kahan 求和 | `comp = (t − total) − y` 精确捕获舍入误差，误差界与 `n` 无关 | 在 GPU 归约上强行使用 |
| 迭代矩阵 | Jacobi `−D⁻¹(L+U)`；GS `−(D+L)⁻¹U`；SOR `(D+ωL)⁻¹[(1−ω)D−ωU]` | 把 Jacobi 与 GS 的迭代矩阵张冠李戴 |
| 收敛判据 | `ρ(B) < 1` 是充要条件；严格对角占优是充分条件 | 用范数代替谱半径判断 |
| `EPS` 选择 | 大于累加噪声、远小于真实间隙；等号写成 `\|a−b\| ≤ EPS` | 直接用 `==` 比较浮点数 |
| 同分断号 | 写成 `cost < best − EPS`，让先遍历到的一方胜出 | 写成 `cost < best`，胜负由末位误差决定 |
| 舍入模式 | half-up 用 `floor(x + 0.5)`；`round()` 是银行家舍入 | 用 `round()` 实现"恰为 .5 向上" |

## 自测题

**Q1**（计算）FP64 中 `1e16 + 1` 等于多少？请用 ulp 解释。
<details><summary>答案与解析</summary>

结果是 `1e16`，加上的 1 被完全丢弃。

```
1e16 ≈ 2^53.15，二进制指数为 53，而 FP64 尾数 52 位，
故该量级下的相邻可表示数间距 ulp = 2^(53 − 52) = 2。
1e16 附近的浮点数只有 …、1e16、1e16+2、1e16+4、…
1 小于半个 ulp，按"舍入到最近"落到 1e16 本身。
```

**要点**：ulp 随量级变化，不是固定常数；相对精度恒定（约 `u = 1.1e−16`），绝对精度随量级线性变差。这正是 5.3.2 节方差单遍法崩溃的根源。
</details>

**Q2**（推导）证明 Softmax 减去最大值是等价变换，并说明为什么"除以最大值"不是。
<details><summary>答案与解析</summary>

```
等价性：令 m = max_j x_j，分子分母同乘正常数 e^(−m)：
    e^(x_i)         e^(−m)·e^(x_i)        e^(x_i − m)
  ───────────  =  ─────────────────  =  ───────────────     比值不变
   Σ_j e^(x_j)     e^(−m)·Σ_j e^(x_j)   Σ_j e^(x_j − m)
防溢出：减去 m 后 x_i − m ≤ 0，故 e^(x_i − m) ∈ (0, 1]，分子永不上溢；
分母至少含 e^(m − m) = 1，永不整体下溢为零。
```

**"除以最大值"为什么错**：`e^(x_i/m)` 改变了各分量之间的差值。原式只依赖 `x_i − x_j`，除以 `m` 之后依赖的是 `(x_i − x_j)/m`——当 `x` 含负分量时比值符号都可能翻转，算出来的是另一个分布；`x/‖x‖` 同理。**只有减去同一个常数（平移）才保持指数上的差分不变。** 延伸：掩码注意力把无效位置置为 `−∞`，`e^(−∞) = 0`，这些位置既不进分子也不进分母，前提是每行至少有一个有限值——窗口内位置 `i` 自己必定在窗口内。
</details>

**Q3**（推导）设 `x = {1e8+1, 1e8+2, 1e8+3}`，用误差放大因子估算单遍法算出的方差还剩几位有效数字，并给出两遍法的计算过程。
<details><summary>答案与解析</summary>

```
真值：μ = 1e8 + 2，σ² = 2/3 ≈ 0.6667
放大因子 = 1 + (μ/σ)² ≈ 1.5e16，相对误差 ≈ u × 放大因子 ≈ 1.1e−16 × 1.5e16 ≈ 1.6
⟹ 相对误差超过 1，一位有效数字都不剩：结果可能是 0、2，甚至负数。
两遍法：第一步 μ = ((1e8+1) + (1e8+2) + (1e8+3))/3 = 1e8 + 2
        第二步 偏差 = {−1, 0, 1}，平方和 = 2，σ² = 2/3 ≈ 0.6667（无相消，精确）
```

原因是 `1e16` 量级上 ulp = 2，而 `E[X²]` 与 `(E[X])²` 的差只有 0.667，小于一个 ulp。**工程取舍：一次性统计量用两遍法；滑动窗口必须用前缀和（单遍法）时，务必把负方差截断到 0。**
</details>

**Q4**（推导）证明过 `n+1` 个互异节点、次数不超过 `n` 的插值多项式存在且唯一，并说明为什么由此可知 Lagrange 与 Newton 是同一个多项式。
<details><summary>答案与解析</summary>

**唯一性**：设 `p`、`q` 都满足条件，令 `r = p − q`，则 `deg r ≤ n` 且 `r(x_i) = 0` 对全部 `n+1` 个节点成立，即 `r` 有 `n+1` 个互异根；而次数不超过 `n` 的非零多项式最多有 `n` 个根，故 `r ≡ 0`，即 `p = q`。

**存在性（构造）**：取 `ℓ_i(x) = Π_{j≠i}(x − x_j)/(x_i − x_j)`，则 `ℓ_i(x_i) = 1`、`ℓ_i(x_j) = 0 (j ≠ i)`，于是 `L(x) = Σ_i y_i ℓ_i(x)` 在每个节点取值 `y_i` 且次数不超过 `n`。

**Lagrange 与 Newton 的等价**：两者都过相同节点、次数都不超过 `n`，由唯一性立得恒等——这正是真题 `【2026-09-04 选择 Q10】` 的答案 D。区别只在书写形式与更新成本：Lagrange 加点必须整体重算，Newton 只需再算一阶差商。**"精度不同"是错误说法，同一个多项式不可能有两种精度。**
</details>

**Q5**（推导）写出 Jacobi、Gauss-Seidel 与 SOR 的迭代矩阵，并说明严格对角占优为什么能保证 Jacobi 收敛。
<details><summary>答案与解析</summary>

```
Jacobi：       D x^(k+1) = b − (L + U)x^(k)    ⟹ B_J = −D⁻¹(L + U)
Gauss-Seidel： (D + L)x^(k+1) = b − U x^(k)    ⟹ B_GS = −(D + L)⁻¹U
SOR：          (D + ωL)x^(k+1) = [(1 − ω)D − ωU]x^(k) + ωb
                                               ⟹ B_ω = (D + ωL)⁻¹[(1 − ω)D − ωU]
严格对角占优 ⟹ Jacobi 收敛：B_J 的对角元为 0，非对角元为 −a_ij/a_ii，故
  ‖B_J‖_∞ = max_i Σ_{j≠i} |a_ij| / |a_ii| < 1        （正是对角占优的定义）
谱半径不超过任何诱导范数：ρ(B_J) ≤ ‖B_J‖_∞ < 1，由 5.5.2 节判据得收敛。
```
</details>

## 与真题的关联

| 真题 | 考查角度 | 对应本章小节 |
|---|---|---|
| `【2026-08-05 选择 Q1】` | Softmax 数值稳定性：减最大值是唯一保值的等价变换 | 5.3.1 |
| `【2026-09-02 编程题 1】` | 滑动窗口注意力：减窗口内最大值、`−inf` 掩码 | 5.3.1 |
| `【2026-08-05 选择 Q9】` | 三点二次插值的计算，`p(1.5) = 3.25` | 5.4.2 |
| `【2026-09-04 选择 Q10】` | Lagrange 与 Newton 是同一个多项式，Newton 更适合动态加点 | 5.4.1、5.4.2 |
| `【2026-09-09 选择 Q8】` | Gauss-Seidel 迭代矩阵 `−(D+L)⁻¹U` 及其三个干扰项 | 5.5.1 |
| `【2026-09-04 编程题 1】` | 前缀和窗口统计、`var < 0` 截断、总体口径方差、half-up 舍入 | 5.3.2、5.7 |
| `【2026-09-09 编程题 2】` | `EPS = 1e−9` 容差判"严格更优"，实现同分断号 | 5.7 |
| `【2026-08-05 编程题 1】` | 几何判定中的浮点比较（距离与半径的关系） | 5.7 |
| `【2026-09-11 编程题 2】` | 距离比较统一用平方域，避免开根号放大误差 | 5.7 |

## 延伸阅读

- Higham, N. J., *Accuracy and Stability of Numerical Algorithms*, 2nd ed.：第 1、2 章（浮点模型与舍入误差界）、第 4 章（求和与 Kahan 补偿）、第 26 章（灾难性相消的完整分类）。
- Trefethen, L. N. & Bau, D., *Numerical Linear Algebra*：第 12 讲（条件数）、第 15–16 讲（最小二乘与正则化）、第 20–22 讲（迭代法与谱半径）。篇幅短、直觉强，是本主题的最佳入门。
- Golub, G. H. & Van Loan, C. F., *Matrix Computations*, 4th ed.：第 4 章（LU 与 Cholesky）、第 10–11 章（经典迭代法与 SOR 理论）。


---

> 作者: [破戒僧](https://onlyblacktea.cn)  
> URL: https://onlyblacktea.cn/book/ai/ch05/  

