 时间求解算法)
文档教程教育【免费下载链接】CLRS Solutions to Introduction to Algorithms Third Edition项目地址https://gitcode.com/gh_mirrors/clr/CLRS点击查看免费下载本文围绕《算法导论》第三版CLRS第 28 章「矩阵运算」的问题 28-2Splines展开以 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}) fi(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}) fi(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) f0(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.mdTridiagonal 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)$ 时间。于是整个「构造自然三次样条」的过程为组装三对角方程 $AD Y$$O(n)$对 $A$ 做 LUP 分解并解出 $D$$O(n)$依据问题 28-1 的结论由 $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 章矩阵分解工具如何落地的理想入口。赞分享文档教程教育【免费下载链接】CLRS Solutions to Introduction to Algorithms Third Edition项目地址https://gitcode.com/gh_mirrors/clr/CLRS点击查看免费下载相关推荐三对角线性方程组的 O(n) 求解CLRS 习题 28-1 的 LU/LUP 分解完整解析三对角线性方程组的 O n 求解CLRS 习题 28 1 的 LU/LUP 分解完整解析 三对角矩阵是数值计算中最常见的稀疏结构之一对其求解线性方程组可以做文档教程教育AdGuardHome Sync YAML配置完全指南从入门到精通AdGuardHome Sync YAML配置完全指南从入门到精通 AdGuardHome Sync是一款强大的工具能够帮助用户轻松同步AdGuard HoToeplitz 矩阵快速算法全解CLRS 问题 30-2 的紧凑表示、O(n log n) FFT 乘法与复杂度分析Toeplitz 矩阵快速算法全解CLRS 问题 30 2 的紧凑表示、O n log n FFT 乘法与复杂度分析 本文以《算法导论第三版》第 30 章文档教程教育上一篇CangjieMagic Human-in-the-Loop 实战指南三级事件处理器体系与 interact/handler DSL 详解下一篇LeetCode-Go 题解 709To Lower Case 字符串大写转小写的 Go 实现详解创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
