差商与 Newton 插值形式

形式陈述

输入为两两互异节点 $x_0,\ldots,x_n$ 及函数值 $f[x_i]=y_i$ 。高阶差商按递推定义：

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

Newton 插值形式为

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

构造完整三角差商表需要 $O(n^2)$ 次运算和 $O(n^2)$ 存储；若只保留当前一列，可降为 $O(n)$ 存储。加入新节点 $(x_{n+1},y_{n+1})$ 时，旧系数不变，只需沿新对角线计算 $O(n)$ 个差商并追加最高阶系数。

给定系数 $c_k=f[x_0,\ldots,x_k]$ ，用嵌套乘法

q\leftarrow c_n,\qquad q\leftarrow c_k+(x-x_k)q \quad(k=n-1,\ldots,0)

可在 $O(n)$ 时间、 $O(1)$ 额外空间求 $p_n(x)$ 。构造在全部节点被处理后完成，求值在反向扫描全部系数后完成；这两个有限过程没有迭代容差。实现仍须拒绝重复节点造成的零分母，并检查非有限中间值。

直觉

Newton 基

1,\ (x-x_0),\ (x-x_0)(x-x_1),\ldots

按节点到达顺序生长。新增一个采样点时，前面的基和系数都保留，只添加一项来修正新节点上的误差。这正是它比重新求解整个 Vandermonde 系统更适合在线增量数据的原因。

一阶差商是两点割线斜率，高阶差商反复比较较低阶斜率。它与割线求根法共享几何语言，却不是同一算法：这里构造经过数据的多项式，割线法则用局部斜率更新根的近似。

例子与边界

取数据

(x_0,y_0)=(0,1),\quad (x_1,y_1)=(1,2),\quad (x_2,y_2)=(2,5).

一阶差商为 $1$ 与 $3$ ，二阶差商为 $1$ ，所以

p_2(x)=1+x+x(x-1)=x^2+1.

若再加入 $(3,10)$ ，新三阶差商为零，原多项式已经满足第四个数据点。这个增量过程展示的是表示更新；无论节点以何种顺序加入，精确算术下最终插值多项式都相同，但差商系数和浮点中间量会改变。

当 $x_j-x_i$ 很小时，分母会放大数据噪声与舍入误差。对真正重复的节点，普通差商没有定义；取节点合并的极限会出现导数并导向 Hermite 插值，但前提是输入明确提供相应导数，不能把除零当作可忽略异常。

推论与应用

差商同时提供插值系数和增量更新结构。对单次固定节点集的大量求值，重心公式通常更直接；对逐点加入数据、需要显式 Newton 系数或后续求导的任务，差商形式更自然。选择表示应由操作模式决定，而不是把代数等价误当成数值等价。

节点排序不会改变精确 $p_n$ ，却会改变乘积基的增长和舍入路径。高阶、宽区间计算应配合节点缩放、合理排序和误差检查；“能追加一列”不意味着任意数据流都稳定。

参考资料

NIST Digital Library of Mathematical Functions, §3.3 Interpolation, accessed 2026.
Richard L. Burden, J. Douglas Faires, and Annette M. Burden, Numerical Analysis, 10th ed., Cengage, 2016, Ch. 3.
Kendall E. Atkinson, An Introduction to Numerical Analysis, 2nd ed., Wiley, 1989, Ch. 3.