多项式插值问题

形式陈述 ​

给定域 $\mathbb{F}$ 上两两互异的节点

$$x_0,x_1,\dots ,x_n$$

以及数据 $y_0,\dots ,y_n\in \mathbb{F}$，多项式插值问题要求寻找 $p\in \mathbb{F}[x]$，使

$$\mathrm{deg}p\le n,p(x_i)=y_i(0\le i\le n).$$

这样的 $p$ 存在且唯一。存在性可由 Lagrange 基

$${\ell }_j(x)=\prod _{\begin{array}{c}0\le k\le n\\ k\ne j\end{array}}\frac{x-x_k}{x_j-x_k}$$

直接验证：${\ell }_j(x_i)={\delta }_{ij}$，所以 $p=\sum _{j=0}^n{y}_j{\ell }_j$ 满足全部条件。唯一性则只需观察：若 $p$ 与 $q$ 都符合条件，次数不超过 $n$ 的差多项式 $p-q$ 有 $n+1$ 个互异根，只能恒为零。这是多项式公理库多项式环Polynomial ring系数来自给定环、以形式不定元构造的多项式集合。对象的结论，不依赖选用单项式、Lagrange、Newton 或 Chebyshev 基。

若写成单项式系数 $p(x)=\sum _{k=0}^n{a}_k{x}^k$，条件等价于 Vandermonde 系统 $Va=y$，其中 $V_{ik}=x_i^k$，且

$$\det V=\prod _{0\le i<j\le n}(x_j-x_i)\ne 0.$$

行列式非零再次证明唯一性，却不说明直接求解该系统具有良好数值性质。存在唯一的数学对象、选择何种表示，以及怎样在浮点数中计算，是三个不同问题。

直觉 ​

$n+1$ 个互异节点给次数至多 $n$ 的多项式施加 $n+1$ 个独立线性条件，恰好确定这个 $(n+1)$ 维空间中的一个元素。插值关注“逐点穿过数据”；逼近关注在某个范数下整体接近目标函数；最小二乘允许不穿过所有点，以换取对噪声或超定数据的整体平衡。

同一插值多项式可以穿不同的“坐标衣服”。单项式系数便于代数识别，Newton 形式适合逐点增加数据，重心 Lagrange 形式适合稳定求值。表示改变不会改变精确多项式，却会显著改变中间量和舍入误差。

例子与边界 ​

三组数据

$$(-1,1),(0,0),(1,1)$$

唯一确定次数不超过 $2$ 的多项式 $p(x)=x^2$。这个简单例子中单项式系数很好辨认，但定理只保证对象唯一；节点数增多或尺度悬殊时，Vandermonde 系统即使可逆也可能非常病态。

若两个普通插值节点重合而给出不同函数值，约束彼此矛盾；若给出相同函数值，它们又是重复条件，不能唯一确定原来的次数上限。Hermite 插值通过在重合节点补充导数数据建立另一套独立条件，但那不是把普通差分公式中的零分母直接保留下来。

即使数据没有噪声，精确穿过节点也不保证区间上逼近良好。经典 Runge 函数 $f(x)=1/(1+25x^2)$ 在 $[-1,1]$ 的高次等距节点插值会在端点附近产生越来越明显的振荡；问题的插值多项式仍然唯一，失败发生在节点选择和逼近稳定性，而不是存在唯一性。若数据本身还带噪，精确穿过每个观测又可能把噪声当成信号，此时回归、最小二乘或平滑样条对应的是另一种任务目标。

推论与应用 ​

重心 Lagrange 插值公理库重心 Lagrange 插值Barycentric Lagrange interpolation · Barycentric interpolation预计算重心权后以线性成本稳定求值 Lagrange 插值多项式，并显式处理节点命中与权重尺度。、差商与 Newton 形式公理库差商与 Newton 插值形式Divided differences · Newton interpolation用递归差商构造可增量扩展的 Newton 插值表示，并以嵌套乘法在线性时间求值。都计算本页定义的同一多项式。插值余项公理库多项式插值余项Interpolation remainder · Polynomial interpolation error在足够光滑条件下以高阶导数和节点乘积表示插值函数误差，并明确该表达式的适用边界。研究当数据来自函数采样时，插值多项式离原函数多远；Lebesgue 常数公理库Lebesgue 常数与插值条件性Lebesgue constant · Interpolation conditioning用插值算子的无穷范数刻画节点集合对采样扰动和最佳逼近误差的放大。研究节点集合怎样放大采样扰动。

有限域上的秘密共享与 Reed–Solomon 译码也使用多项式插值的唯一性，但其误差模型和计算语境不同。本页以实、复数值计算为主要背景，不把有限域的精确代数步骤误写成浮点算法。

参考资料

• NIST Digital Library of Mathematical Functions, §3.3 Interpolation.
• MIT OpenCourseWare, 18.330 Introduction to Numerical Analysis, interpolation notes.
• Philip J. Davis, Interpolation and Approximation, Dover, 1975, Chs. 1–2.