多项式插值

从离散的观测中重建连续的数学模型，是科学计算的核心命题。在物理实验、传感器数据采集或数值仿真中，我们极少能够掌握解析函数的解析表达，往往只能获取有限的离散采样点：

$$(x_0, y_0), (x_1, y_1), \dots, (x_n, y_n).$$

如何构造一条光滑的连续曲线，使其精确穿过每一个已知的数据点？

多项式是最先进入视野的函数基底：不仅处处光滑可导、微积分运算形式封闭，而且通过 Horner 嵌套乘法可以在计算硬件上以极低代价求值。

本篇笔记聚焦多项式插值的代数结构与算法构造[1][1] R. L. Burden and J. D. Faires, Numerical Analysis, 9th ed. Brooks/Cole, Cengage Learning, 2011., [2][2] M. U. School of Mathematics, “MTH2051: Introduction to Computational Mathematics: Course Lecture Notes and Study Workbooks,” 2026. Monash University course materials and study workbooks, Semester 2, 2026.：

1. 插值问题：在多项式线性空间 $P_n$ 中建立严格的代数匹配条件；
2. 逼近与插值的辨析：阐明 Weierstrass 定理的存在性断言与离散插值的本质分界；
3. Lagrange 形式：利用几何选择子思想构造基多项式（$\ell_i(x_j) = \delta_{ij}$）；
4. 存在与唯一性定理：利用代数基本定理与多项式根的重数，证明解的唯一存在；
5. Newton 差商形式：引入流式增量构造，使新节点的接入仅需 $\mathcal{O}(n)$ 的边际开销。

插值问题与函数空间

定义多项式插值

给定 $n+1$ 个互异的实数节点 $x_0, x_1, \dots, x_n$ 以及对应的数值 $y_0, y_1, \dots, y_n$。若多项式 $P_n \in P_n$ 满足

$$P_n(x_i) = y_i, \quad i = 0, 1, \dots, n,$$

则称 $P_n$ 为该组数据的插值多项式。这里 $P_n$ 表示次数不超过 $n$ 的实系数多项式线性空间：

$$P_n = \left\{ \sum_{k=0}^n a_k x^k : a_k \in \mathbb{R} \right\}.$$

多项式空间 $P_n$ 由 $n+1$ 个自由参数 $a_0, a_1, \dots, a_n$ 唯一确定，其空间维数为 $\dim(P_n) = n+1$。在几何上：

• 2 个互异点唯一确定一条直线（属于 $P_1$）；
• 3 个不共线点唯一确定一条抛物线（属于 $P_2$）；
• 匹配 $n+1$ 个独立的标量约束，刚好需要维数为 $n+1$ 的函数空间提供匹配自由度。

逼近与插值的本质差异

在构造插值函数前，必须厘清两个容易混淆的概念：连续函数的整体逼近与离散采样点的局部插值。

定理Weierstrass 逼近定理

设 $f \in C([a,b])$ 为闭区间上的连续函数。对任意给定的误差容限 $\varepsilon > 0$，必定存在某个非负整数 $m$ 以及对应的多项式 $q_m \in P_m$，满足

$$\max_{x \in [a,b]} |f(x) - q_m(x)| < \varepsilon.$$

Weierstrass 定理给出了一个关于逼近能力的存在性断言：只要多项式阶数足够高，闭区间上的连续函数总能被多项式在全局范围内一致逼近。

然而，Weierstrass 定理并未保证：直接穿过 $n+1$ 个等距采样点的插值多项式，随着节点增多就会一致收敛到原函数。实际上，盲目提高等距节点的插值阶数，可能在边界处激起剧烈发散。两者的分界十分清晰：

• 逼近寻找的是全区间上落在 $\varepsilon$ 误差管道内的某个高次多项式；
• 插值构造的是精确咬合离散采样点 $(x_i, y_i)$ 的唯一特定多项式。

这个交互图需要启用 JavaScript。

Lagrange 基函数与代数构造

为了显式写出这个插值多项式，我们寻找一组能够充当“开关”的特殊基底：对于每个节点 $x_i$，构造基函数 $\ell_i(x)$，使其在自身节点 $x_i$ 处取值为 $1$，而在其余所有外来节点 $x_j$（$j \neq i$）处全部归零。

定义Lagrange 基多项式

对于 $n+1$ 个互异节点 $x_0, \dots, x_n$，第 $i$ 个 Lagrange 基多项式 $\ell_i \in P_n$ 定义为

$$\ell_i(x) = \prod_{\substack{j=0 \\ j \neq i}}^n \frac{x - x_j}{x_i - x_j}.$$

它满足 Kronecker delta 选择子性质：

$$\ell_i(x_j) = \delta_{ij} = \begin{cases} 1, & j = i, \\ 0, & j \neq i. \end{cases}$$

这种代数设计的意图非常清晰：

1. 分子项 $\prod_{j \neq i} (x - x_j)$ 具有 $n$ 阶次数，在外来所有节点处布设零点；
2. 分母项 $\prod_{j \neq i} (x_i - x_j)$ 是非零标量常数，将本节点 $x = x_i$ 处的函数值归一化为 $1$。

定义Lagrange 插值多项式

给定采样值 $y_i = f(x_i)$，Lagrange 插值多项式定义为基函数的线性组合：

$$P_n(x) = \sum_{i=0}^n y_i \ell_i(x).$$

将任意节点 $x_k$ 代入 $P_n(x)$，由选择子性质，求和项中只剩下单项存活：

$$P_n(x_k) = \sum_{i=0}^n y_i \ell_i(x_k) = \sum_{i=0}^n y_i \delta_{ik} = y_k.$$

这证明 $P_n$ 严格满足全部 $n+1$ 个插值条件。

例三节点二次 Lagrange 插值算例

给定采样数据 $(0, 1)$、$(1, 3)$ 和 $(2, 2)$，阶数 $n = 2$。对应的三个二次基函数为：

$$\begin{aligned} \ell_0(x) &= \frac{(x - 1)(x - 2)}{(0 - 1)(0 - 2)} = \frac{1}{2}(x - 1)(x - 2), \\ \ell_1(x) &= \frac{(x - 0)(x - 2)}{(1 - 0)(1 - 2)} = -x(x - 2), \\ \ell_2(x) &= \frac{(x - 0)(x - 1)}{(2 - 0)(2 - 1)} = \frac{1}{2}x(x - 1). \end{aligned}$$

将各采样值加权装配：

$$\begin{aligned} p_2(x) &= 1 \cdot \ell_0(x) + 3 \cdot \ell_1(x) + 2 \cdot \ell_2(x) \\ &= \frac{1}{2}(x^2 - 3x + 2) - 3(x^2 - 2x) + (x^2 - x) \\ &= -\frac{3}{2}x^2 + \frac{7}{2}x + 1. \end{aligned}$$

代入节点检验：$p_2(0) = 1$、$p_2(1) = 3$、$p_2(2) = 2$，与输入完全吻合。

命题Lagrange 基底性质

集合 $\{\ell_0, \ell_1, \dots, \ell_n\}$ 满足：

1. 在线性空间 $P_n$ 中线性无关；
2. 构成 $P_n$ 的一组基；
3. 满足单位分解恒等式：

$$\sum_{i=0}^n \ell_i(x) = 1 \quad \text{对所有 } x \in \mathbb{R} \text{ 成立}。$$

证明

为证线性无关，设线性组合恒等于零：$\sum_{i=0}^n c_i \ell_i(x) \equiv 0$。将各节点 $x_k$ 依次代入：

$$\sum_{i=0}^n c_i \ell_i(x_k) = \sum_{i=0}^n c_i \delta_{ik} = c_k = 0, \quad k = 0, 1, \dots, n.$$

所有系数必须全部为零，故基函数组线性无关。由于 $\dim(P_n) = n+1$，这 $n+1$ 个线性无关向量自然张成整块空间 $P_n$。

最后考察常数函数 $f(x) \equiv 1 \in P_n$。由唯一性，穿过这组节点的插值多项式就是常数函数自身。将其按 Lagrange 基展开，立刻得到 $\sum_{i=0}^n 1 \cdot \ell_i(x) = 1$。

存在与唯一性定理

定理多项式插值的存在唯一性

设 $x_0, x_1, \dots, x_n$ 为 $n+1$ 个两两互异的实数，且 $y_0, y_1, \dots, y_n$ 为任意给定的实数。在多项式空间 $P_n$ 中，存在且仅存在一个多项式 $P_n$ 满足

$$P_n(x_i) = y_i, \quad i = 0, 1, \dots, n.$$

证明

存在性：前述显式构造的 Lagrange 多项式 $P_n(x) = \sum_{i=0}^n y_i \ell_i(x)$ 是 $P_n$ 中元素的线性组合，因而属于 $P_n$，且满足所有插值条件。

唯一性：假设另有多项式 $q_n \in P_n$ 同样满足 $q_n(x_i) = y_i$（$i = 0, \dots, n$）。定义差多项式：

$$r(x) = P_n(x) - q_n(x).$$

因为 $P_n$ 是线性空间，所以 $r \in P_n$。检验 $r$ 在各节点处的取值：

$$r(x_i) = P_n(x_i) - q_n(x_i) = y_i - y_i = 0, \quad i = 0, 1, \dots, n.$$

这意味着次数不超过 $n$ 的多项式 $r(x)$ 拥有至少 $n+1$ 个互异的实根。根据代数基本定理推论，非零多项式的根数不可能严格超过其阶数。因此 $r(x)$ 必为零多项式：

$$r(x) \equiv 0 \implies P_n(x) = q_n(x) \quad \text{对所有 } x \in \mathbb{R} \text{ 成立}。$$

Newton 差商形式与增量计算

虽然 Lagrange 形式在理论证明中极为明晰，但在实际计算中却缺乏动态扩展能力：一旦新增一个采样点 $(x_{n+1}, y_{n+1})$，原先所有基函数 $\ell_i(x)$ 的分子分母全部失效，必须消耗 $\mathcal{O}(n^2)$ 的复杂度从头重算。

Newton 差商插值采用渐进叠加的思路化解了这一矛盾：

$$P_k(x) = P_{k-1}(x) + a_k \prod_{j=0}^{k-1} (x - x_j).$$

新加入的基多项式 $\prod_{j=0}^{k-1} (x - x_j)$ 在历史节点 $x_0, \dots, x_{k-1}$ 处全部为零，完全不破坏此前已经匹配好的前序点，只需要确定一个新的系数 $a_k$ 即可。

定义差商（均差）

设 $x_0, \dots, x_n$ 为互异节点，函数值为 $f(x_0), \dots, f(x_n)$。零阶差商定义为函数值自身：

$$f[x_i] = f(x_i).$$

一阶差商为两个相邻点的割线斜率：

$$f[x_i, x_{i+1}] = \frac{f[x_{i+1}] - f[x_i]}{x_{i+1} - x_i}.$$

对于 $k \ge 2$，高阶差商由相邻低阶差商递归生成：

$$f[x_i, x_{i+1}, \dots, x_{i+k}] = \frac{f[x_{i+1}, \dots, x_{i+k}] - f[x_i, \dots, x_{i+k-1}]}{x_{i+k} - x_i}.$$

注意：$k$ 阶差商的分母跨度，始终对应外层两个最远节点的坐标差 $x_{i+k} - x_i$。

定理Newton 插值多项式公式

穿过互异节点 $x_0, \dots, x_n$ 的插值多项式 $P_n \in P_n$，可以展开为 Newton 差商形式：

$$P_n(x) = f[x_0] + \sum_{k=1}^n f[x_0, x_1, \dots, x_k] \prod_{j=0}^{k-1} (x - x_j).$$

证明

记 $P_{0, k}(x)$ 为穿过 $x_0, \dots, x_k$ 的唯一 $k$ 次插值多项式。考察相邻两阶的差值：

$$P_{0, k}(x) - P_{0, k-1}(x).$$

由于这两个多项式在 $x_0, \dots, x_{k-1}$ 这 $k$ 个点上的取值相同，它们的差必以此 $k$ 个点为根。根据因式定理：

$$P_{0, k}(x) - P_{0, k-1}(x) = c_k \prod_{j=0}^{k-1} (x - x_j),$$

其中 $c_k$ 正是 $P_{0, k}(x)$ 的最高次项系数。

将上式从 $k = 1$ 累加到 $n$，形成裂项相消：

$$P_n(x) = P_{0, n}(x) = P_{0, 0}(x) + \sum_{k=1}^n c_k \prod_{j=0}^{k-1} (x - x_j).$$

利用 Neville 递推关系：

$$P_{0, k}(x) = \frac{(x - x_0) P_{1, k}(x) - (x - x_k) P_{0, k-1}(x)}{x_k - x_0}.$$

比较两端 $x^k$ 的系数，可知最高次项系数严格遵循差商递推结构：

$$c_k = \frac{\operatorname{coeff}(P_{1, k}, x^{k-1}) - \operatorname{coeff}(P_{0, k-1}, x^{k-1})}{x_k - x_0}.$$

由数学归纳法可知，$c_k$ 恰好等于 $k$ 阶差商 $f[x_0, \dots, x_k]$。

差商表的构建与读取

在数值计算中，通常采用下三角差商表统一存储与递推：

$$\begin{array}{c|cccc} x_i & f[x_i] & \text{一阶差商} & \text{二阶差商} & \text{三阶差商} \\ \hline x_0 & \mathbf{f[x_0]} & & & \\ & & \mathbf{f[x_0, x_1]} & & \\ x_1 & f[x_1] & & \mathbf{f[x_0, x_1, x_2]} & \\ & & f[x_1, x_2] & & \mathbf{f[x_0, x_1, x_2, x_3]} \\ x_2 & f[x_2] & & f[x_1, x_2, x_3] & \\ & & f[x_2, x_3] & & \\ x_3 & f[x_3] & & & \end{array}$$

每一项均由其左侧的两项做差、并除以对应最外层节点的差值得到。Newton 公式所需的系数，正是表中第一行（主对角线）加粗的各项。

例差商表构建与动态增点演示

设初始包含三个点：$(1, 2)$、$(2, 3)$ 和 $(4, 9)$。

1. 零阶项：$f[x_0] = 2$、$f[x_1] = 3$、$f[x_2] = 9$。
2. 一阶差商：

$$f[x_0, x_1] = \frac{3 - 2}{2 - 1} = 1, \quad f[x_1, x_2] = \frac{9 - 3}{4 - 2} = 3.$$

3. 二阶差商：

$$f[x_0, x_1, x_2] = \frac{3 - 1}{4 - 1} = \frac{2}{3}.$$

读取对角线系数，得到二次多项式：

$$p_2(x) = 2 + 1 \cdot (x - 1) + \frac{2}{3}(x - 1)(x - 2).$$

若此时新增第 4 个点 $(5, 12)$，无需重构整张表，只需顺次追加一行边界：

• $f[x_2, x_3] = \frac{12 - 9}{5 - 4} = 3$；
• $f[x_1, x_2, x_3] = \frac{3 - 3}{5 - 2} = 0$；
• $f[x_0, x_1, x_2, x_3] = \frac{0 - 2/3}{5 - 1} = -\frac{1}{6}$。

更新后的三次多项式只需单项追加：

$$p_3(x) = p_2(x) - \frac{1}{6}(x - 1)(x - 2)(x - 4).$$

在已有节点 $1, 2, 4$ 处，新增的乘积项自然归零，完美保留先前的匹配结果。

Horner 嵌套快速求值

将 Newton 形式展开成单项式标准幂级数 $a x^2 + b x + c$ 既不经济，又容易引发高阶舍入误差。工业实现统一使用 Horner 嵌套乘法：

$$P_n(x) = a_0 + (x - x_0) \Big( a_1 + (x - x_1) \Big( a_2 + \dots + (x - x_{n-1}) a_n \Big) \Big).$$

算法 1 Newton 插值的 Horner 嵌套求值算法

Require: 节点数组 $x_0, \dots, x_n$、Newton 系数 $a_0, \dots, a_n$、目标求值点 $x$

Ensure: 求值结果 $y = P_n(x)$

1:$y \gets a_n$

2:for $k \gets n - 1$ downto $0$ do

3:$y \gets a_k + (x - x_k) \cdot y$

4:end for

5:return $y$

求值过程只需 $n$ 次乘法与 $n$ 次加法，计算复杂度为严格的 $\mathcal{O}(n)$。各多项式插值形式的算法特征对比如下[1][1] R. L. Burden and J. D. Faires, Numerical Analysis, 9th ed. Brooks/Cole, Cengage Learning, 2011.：

插值形式的算法对比

评估维度	Lagrange 形式	Newton 差商形式
多项式构造复杂度	$\mathcal{O}(n^2)$	$\mathcal{O}(n^2)$
新增单点复杂度	$\mathcal{O}(n^2)$ 全部重算	$\mathcal{O}(n)$ 仅追加对角线单项
单点求值复杂度	直接法 $\mathcal{O}(n^2)$（重心法 $\mathcal{O}(n)$）	Horner 嵌套法 $\mathcal{O}(n)$
主要应用场景	理论推导、封闭解构造	动态流式数据接入、工程数值库实现

由唯一性定理保证，无论选择哪种构造形式，最终在代数上确定的都是同一条数学曲线。

节点之外的世界

我们已经解决了“如何穿过已知点”的代数构造问题。但数值计算更关切的深层问题是：插值多项式在节点之间的区间内表现如何？

不断增加采样点，多项式真的会越来越贴近真实函数吗？

在下一篇插值误差与 Chebyshev 节点中，我们将严格推导 Cauchy 形式的插值误差余项，解构等距节点下恶性振荡的 Runge 现象，并展示如何通过非均匀的 Chebyshev 节点化解这一危机。

参考文献

1. [1] R. L. Burden and J. D. Faires, Numerical Analysis, 9th ed. Brooks/Cole, Cengage Learning, 2011. a b
2. [2] M. U. School of Mathematics, “MTH2051: Introduction to Computational Mathematics: Course Lecture Notes and Study Workbooks,” 2026. Monash University course materials and study workbooks, Semester 2, 2026. ↩