企业官网建设流程全解析

• 文档
• 教程
• 教育

本文围绕《算法导论》第三版（CLRS）第 28 章「矩阵运算」的问题 28-2（Splines）展开，以 docs/Chap28/Problems/28-2.md 的题解为主体，完整推导自然三次样条（natural cubic spline）的系数求解公式、由二阶导连续性导出的三对角线性方程组（式 28.21–28.23）、对应的对称三对角矩阵方程，以及借助三对角矩阵 LUP 分解实现的 O(n) 整体算法，并进一步推广到非均匀节点的一般情形。读完本文，你将掌握样条插值从「分段多项式构造」到「线性方程组求解」的完整推导链条，理解它为什么是 问题 28-1 所研究的三对角系统的一个直接应用。

1. 背景：分段三次样条插值问题

实际工程中，用一条曲线插值一组离散数据点是常见需求，三次样条（cubic spline）就是其中一种实用方法。给定 $n + 1$ 个点值对

$${(x_i, y_i) : i = 0, 1, \ldots, n}, \quad x_0 < x_1 < \cdots < x_n,$$

我们希望用一条分段三次曲线（样条）$f(x)$ 拟合这些点。也就是说，$f(x)$ 由 $n$ 个三次多项式

$$f_i(x) = a_i + b_ix + c_ix^2 + d_ix^3, \qquad i = 0, 1, \ldots, n - 1$$

拼接而成：当 $x$ 落在区间 $x_i \le x \le x_{i + 1}$ 时，曲线取值为 $f(x) = f_i(x - x_i)$。各多项式拼接处的节点 $x_i$ 称为结点（knots）。为简化讨论，题目先假设 $x_i = i$（即等间距、间距为 1）。

为保证 $f(x)$ 连续，需要满足

$$ \begin{aligned} f(x_i) & = f_i(0) = y_i, \ f(x_{i + 1}) & = f_i(1) = y_{i + 1} \end{aligned} $$

对所有 $i = 0, 1, \ldots, n - 1$ 成立。为保证曲线足够光滑，还要求一阶导数在每个结点处连续：

$$f'(x_{i + 1}) = f'i(1) = f'{i + 1}(0), \qquad i = 0, 1, \ldots, n - 2.$$

以上条件确定了「$4n$ 个系数、$3n$ 个约束」的问题框架，接下来要回答的核心问题是：如何确定每条三次曲线的 4 个系数，以及各结点处的一阶导数 $D_i = f'(x_i)$？

2. 已知结点导数时：4n 个系数的求解（问题 a）

假设除了点值对 ${(x_i, y_i)}$，我们还知道每个结点处的一阶导数 $D_i = f'(x_i)$，那么每个 $f_i$ 的系数都可以直接用 $y_i$、$y_{i + 1}$、$D_i$、$D_{i + 1}$ 表示。

由定义直接得到前两个系数：

• $a_i = f_i(0) = y_i$；
• $b_i = f_i'(0) = f'(x_i) = D_i$。

利用 $f_i(1) = a_i + b_i + c_i + d_i$ 与 $f_i'(1) = b_i + 2c_i + 3d_i$，结合 $f_i(1) = y_{i + 1}$、$f_i'(1) = D_{i + 1}$，解二元一次方程组可得：

$$d_i = D_{i + 1} - 2y_{i + 1} + 2y_i + D_i,$$

$$c_i = 3y_{i + 1} - 3y_i - D_{i + 1} - 2D_i.$$

验证一下推导：由 $c_i + d_i = y_{i + 1} - y_i - D_i$ 与 $2c_i + 3d_i = D_{i + 1} - D_i$，对第一个等式乘 2 再相减即可解出 $d_i$，回代即得 $c_i$，与上式一致。

由于每个系数都可以从已知量在常数时间内算得，计算全部 $4n$ 个系数只需线性时间$O(n)$。这一步是整个问题的基础——它把「求样条」归结为「先求出 $n + 1$ 个未知导数 $D_i$」。

3. 二阶导数连续：内部结点方程（问题 b）

问题转化为如何选择各结点处的一阶导数。题目给出的方法是要求二阶导数在结点处连续：

$$f''(x_{i + 1}) = f''i(1) = f''{i + 1}(0), \qquad i = 0, 1, \ldots, n - 2.$$

由于 $f_i''(x) = 2c_i + 6d_ix$，连续性条件 $f_i''(1) = f_{i + 1}''(0)$ 等价于

$$2c_i + 6d_i = 2c_{i + 1}, \quad\text{即}\quad c_i + 3d_i = c_{i + 1}.$$

代入第 2 节得到的 $c_i$、$d_i$ 表达式（对 $f_{i + 1}$ 同理），可得

$$D_i + 2D_{i + 1} + 3y_i - 3y_{i + 1} = 3y_{i + 2} - 3y_{i + 1} - D_{i + 2} - 2D_{i + 1}.$$

整理后得到内部结点方程

$$D_i + 4D_{i + 1} + D_{i + 2} = 3(y_{i + 2} - y_i).$$

换指标 $i \to i - 1$，即对 $i = 1, 2, \ldots, n - 1$ 有

$$D_{i - 1} + 4D_i + D_{i + 1} = 3(y_{i + 1} - y_{i - 1}). \tag{28.21}$$

注：原题解文档中该式编号写作「(23.21)」，与同节其余编号 (28.22)、(28.23) 不一致，本文按第 28 章上下文统一为 (28.21)。

4. 自然边界条件：端点方程（问题 c）

内部结点的二阶导连续性给出了 $n - 1$ 个方程，而未知导数有 $n + 1$ 个，还差两个条件。题目在首尾两个结点补充假设

$$f''(x_0) = f''0(0) = 0, \qquad f''(x_n) = f''{n - 1}(1) = 0,$$

使 $f(x)$ 成为自然三次样条（natural cubic spline）。

左端点。条件 $f_0''(0) = 0$ 给出 $2c_0 = 0$，即 $c_0 = 0$。由第 2 节公式 $c_0 = 3y_1 - 3y_0 - D_1 - 2D_0$，得

$$2D_0 + D_1 = 3(y_1 - y_0). \tag{28.22}$$

右端点。条件 $f_{n - 1}''(1) = 0$ 给出 $2c_{n - 1} + 6d_{n - 1} = 0$，即 $c_{n - 1} + 3d_{n - 1} = 0$。代入 $i = n - 1$ 时的 $c$、$d$ 公式，得

$$D_{n - 1} + 2D_n = 3(y_n - y_{n - 1}). \tag{28.23}$$

至此，$n + 1$ 个未知导数恰好对应 $n + 1$ 个线性方程：内部 $n - 1$ 个（28.21）加两端 2 个（28.22）、（28.23）。

5. 矩阵形式：对称三对角系统（问题 d）

将方程 (28.21)–(28.23) 重写为矩阵方程 $AD = Y$，其中 $D = \langle D_0, D_1, \ldots, D_n \rangle^{\text T}$ 是未知向量。系数矩阵 $A$ 是 $(n + 1) \times (n + 1)$ 的对称三对角矩阵：

$$ \begin{pmatrix} 2 & 1 & 0 & 0 & \cdots & 0 \ 1 & 4 & 1 & 0 & \cdots & 0 \ 0 & \ddots & \ddots & \ddots & \cdots & \vdots \ \vdots & \cdots & 1 & 4 & 1 & 0 \ 0 & \cdots & 0 & 1 & 4 & 1 \ 0 & \cdots & 0 & 0 & 1 & 2 \end{pmatrix} \begin{pmatrix} D_0 \ D_1 \ D_2 \ \vdots \ D_{n - 1} \ D_n \end{pmatrix}

\begin{pmatrix} 3(y_1 - y_0) \ 3(y_2 - y_0) \ 3(y_3 - y_1) \ \vdots \ 3(y_n - y_{n - 2}) \ 3(y_n - y_{n - 1}) \end{pmatrix}. $$

矩阵 $A$ 的结构要点：

• 对称：$A = A^{\text T}$；
• 三对角：非零元素只出现在主对角线与两条次对角线上，其余位置全为 0；
• 主对角线：首尾为 2，中间为 4；
• 次对角线：全部为 1；
• 由于每一行 $|A_{ii}|$ 都严格大于同行非对角元素绝对值之和（2 > 1、4 > 2），$A$ 是严格对角占优矩阵，因而非奇异，且对称正定——这意味着其 LU 分解无需行交换即可进行，同时结合第 6 节的三对角结构可达到线性时间。

6. 为什么能做到 O(n)：三对角系统的 LUP 分解（问题 e）

回答「自然三次样条能否在 $O(n)$ 时间内插值 $n + 1$ 个点」的关键在于：系数矩阵 $A$ 是三对角的。这与 docs/Chap28/Problems/28-1.md（Tridiagonal systems of linear equations）中建立的理论直接对应。

问题 28-1 的第 (e) 问证明了：对任意 $n \times n$ 非奇异三对角矩阵 $A$ 和任意 $n$ 维向量 $b$，可以通过对 $A$ 做 LUP 分解在 $O(n)$ 时间内解出 $Ax = b$。其原因是三对角矩阵每行每列只有常数个非零元，于是 LUP 分解过程中：

• 主元选择（在至多两行中取最大）降为 $O(1)$；
• 消元循环中涉及的 $a_{ik}$、$a_{kj}$ 等非零项数量为常数，内层循环也只需 $O(1)$；
• 外层循环仍执行 $O(n)$ 次，故整个分解为 $O(n)$；
• 前代（forward substitution）与回代（back substitution）同样每步只花常数时间，各为 $O(n)$。

回到本题：一旦解出各 $D_i$，第 2 节已证明每个 $f_i$ 的 4 个系数都可以在常数时间内算出，$n$ 段共 $O(n)$ 时间。于是整个「构造自然三次样条」的过程为：

1. 组装三对角方程 $AD = Y$（$O(n)$）；
2. 对 $A$ 做 LUP 分解并解出 $D$（$O(n)$，依据问题 28-1 的结论）；
3. 由 $D_i$ 与 $y_i$ 计算全部 $4n$ 个系数（$O(n)$）。

三步合计 $O(n)$。作为对比，若试图通过显式构造 $A^{-1}$ 来求解，则仅写出逆矩阵就需要 $O(n^2)$ 个元素，在渐近意义上严格更慢——这正是问题 28-1 第 (d)、(e) 问强调的要点。

7. 一般化：非均匀结点的自然三次样条（问题 f）

前面假设 $x_i = i$ 只是为了书写方便。实际数据点往往不满足等间距，因此需要处理 $x_0 < x_1 < \cdots < x_n$ 但间距不等的一般情形。

设 $h_i = x_{i + 1} - x_i$，并将多项式改写成以 $x_i$ 为原点的形式 $f_i(t) = a_i + b_it + c_it^2 + d_it^3$（$t = x - x_i$）。此时连续性条件变为：

$$f(x_{i + 1}) = f_i(h_i) = y_{i + 1}, \qquad f'(x_{i + 1}) = f_i'(h_i) = f_{i + 1}'(0), \qquad f''(x_{i + 1}) = f_i''(h_i) = f_{i + 1}''(0).$$

按照第 2 节完全相同的思路，$a_i = y_i$、$b_i = D_i$ 仍然成立，而

$$c_i = \frac{3(y_{i + 1} - y_i)}{h_i^2} - \frac{2D_i + D_{i + 1}}{h_i}, \qquad d_i = \frac{(D_i + D_{i + 1})h_i - 2(y_{i + 1} - y_i)}{h_i^3}.$$

可以验证：当 $h_i = 1$ 时，上式恰好还原为第 2 节的 $c_i$、$d_i$ 公式。同样把二阶导连续性条件 $c_i + 3d_ih_i = c_{i + 1}$ 展开并整理，可以得到以 $D$ 为未知量的三对角方程组（对 $i = 1, \ldots, n - 1$）：

$$h_i^{-1}D_{i - 1} + 2\left(h_i^{-1} + h_{i + 1}^{-1}\right)D_i + h_{i + 1}^{-1}D_{i + 1} = 3\left[\frac{y_i - y_{i - 1}}{h_i^2} + \frac{y_{i + 1} - y_i}{h_{i + 1}^2}\right].$$

端点方程同样需要乘上相应的间距权重。该方程组的系数矩阵依然是对称三对角的（只是非零元从常数 1、4 变为含 $h_i$ 的加权形式），因此求解方式与简单情形完全一致：组装系统后做三对角矩阵的 LUP 分解，再前代、回代，最终总运行时间仍为 $O(n)$。题解原文对这一问的表述是「解会稍微繁琐一些，但归根结底和简单情形一样，在 $O(n)$ 时间内解出」，上述推导正是一个可验证的展开版本。

8. 配套内容与仓库位置

本题属于 CLRS Solutions 仓库第 28 章「矩阵运算」的章末问题，仓库中各文件的对应关系如下：

• 本题完整题解：docs/Chap28/Problems/28-2.md；
• 本题直接依赖的三对角系统理论（LU/LUP 分解的 O(n) 论证）：docs/Chap28/Problems/28-1.md；
• 章内相关练习：LU 分解与前代/回代（docs/Chap28/28.1.md）、矩阵求逆与矩阵乘法的等价性（docs/Chap28/28.2.md）、对称正定矩阵与最小二乘拟合（docs/Chap28/28.3.md）；
• 全仓库为《算法导论》第三版习题解答，以 Markdown + KaTeX 编写并由 MkDocs 渲染，导航与构建配置见 mkdocs.yml，站点说明见 docs/index.md。

总结

自然三次样条插值问题的本质是一条清晰的推导链：分段三次多项式连续性 + 一阶导连续给出系数与结点导数 $D_i$ 的显式关系；二阶导连续 + 自然边界条件将确定 $D_i$ 的问题转化为 $n + 1$ 元对称三对角线性方程组（28.21–28.23）；三对角结构的 LUP 分解使整个求解在 $O(n)$ 时间内完成，非均匀节点情形只是把常数系数替换为间距相关的权重，算法框架与复杂度不变。本题是「数值计算问题归结为稀疏线性代数问题」的经典案例，也是理解 CLRS 第 28 章矩阵分解工具如何落地的理想入口。

• 文档
• 教程
• 教育