差商与 Newton 插值形式

形式陈述 ​

输入为两两互异节点 $x_0,\dots ,x_n$ 及函数值 $f[x_i]=y_i$。高阶差商按递推公理库递推关系Recurrence relation用先前项规定序列当前项的关系。定义：

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

Newton 插值形式为

$$p_n(x)=f[x_0]+\sum _{k=1}^{n}f[x_0,\dots ,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,\dots ,x_k]$，用嵌套乘法

$$q\leftarrow c_n,q\leftarrow c_k+(x-x_k)q(k=n-1,\dots ,0)$$

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

直觉 ​

Newton 基

$$1,(x-x_0),(x-x_0)(x-x_1),\dots$$

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

一阶差商是两点割线斜率，高阶差商反复比较较低阶斜率。它与割线求根法公理库割线法Secant method用最近两点的割线斜率近似导数，在无导数的一维求根中取得局部超线性收敛。共享几何语言，却不是同一算法：这里构造经过数据的多项式，割线法则用局部斜率更新根的近似。

例子与边界 ​

取数据

$$(x_0,y_0)=(0,1),(x_1,y_1)=(1,2),(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 插值，但前提是输入明确提供相应导数，不能把除零当作可忽略异常。

推论与应用 ​

差商同时提供插值系数和增量更新结构。对单次固定节点集的大量求值，重心公式公理库重心 Lagrange 插值Barycentric Lagrange interpolation · Barycentric interpolation预计算重心权后以线性成本稳定求值 Lagrange 插值多项式，并显式处理节点命中与权重尺度。通常更直接；对逐点加入数据、需要显式 Newton 系数或后续求导的任务，差商形式更自然。选择表示应由操作模式决定，而不是把代数等价误当成数值等价。

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

参考资料

• NIST Digital Library of Mathematical Functions, §3.3 Interpolation.
• 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.