差商与 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

按节点到达顺序生长。新增一个采样点时，前面的基和系数都保留，只添加一项来修正新节点上的误差。原因是新基函数 $\prod_{j=0}^n(x-x_j)$ 在所有旧节点处为零，不会破坏已经满足的条件。新系数因此必须取

c_{n+1}=\frac{y_{n+1}-p_n(x_{n+1})}{\prod_{j=0}^n(x_{n+1}-x_j)}.

分子是尚未解释的新数据，分母是新基在该处的值；差商递推正是在不反复展开多项式的情况下算出这个系数。这正是它比重新求解整个 Vandermonde 系统更适合在线增量数据的原因。

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

差商与 Newton 插值：差商表对角系数扩展 Newton 基 — 差商系数与 Newton 基的对应

例子与边界

取数据

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

先作相邻割线斜率： $f[0,1]=(2-1)/(1-0)=1$ ， $f[1,2]=(5-2)/(2-1)=3$ 。二阶差商还要除以最外侧节点距离，故 $f[0,1,2]=(3-1)/(2-0)=1$ ，不能只把两个斜率相减。于是

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

例如在 $x=3/2$ 求值，嵌套步骤先得 $q=1$ ，再得 $q=1+(3/2-1)\cdot1=3/2$ ，最后得 $q=1+(3/2)\cdot(3/2)=13/4$ 。

若再加入 $(3,10)$ ， $p_2(3)=10$ ，新增项的分子为零，因而三阶差商为零。若该观测改成 $10+\varepsilon$ ，则新增系数为 $\varepsilon/(3\cdot2\cdot1)=\varepsilon/6$ ，只须加上 $(\varepsilon/6)x(x-1)(x-2)$ 。原多项式满足第四点的情形因此就是零修正的特例。这个增量过程展示的是表示更新；无论节点以何种顺序加入，精确算术下最终插值多项式都相同，但差商系数和浮点中间量会改变。

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

明确给导数后，可以使用合流差商：将每个节点重复所需次数并连续排列，同一点重复 $r+1$ 次的差商定义为 $f^{(r)}(x)/r!$ ；最外节点不同时仍使用普通递推。Newton 乘积也按重复点列书写。存在唯一性的重零点证明已有Hermite 插值接口，不必由数值表猜测。

例如输入 $f(0)=1,f'(0)=0,f(1)=2,f'(1)=3$ ，点列为 $(0,0,1,1)$ 。一阶差商为 $(0,1,3)$ ，二阶为 $(1,2)$ ，三阶为一，因此 Newton 系数为 $(1,0,1,1)$ ，得到 $p=1+x^2+x^2(x-1)=1+x^3$ 。四条值与斜率条件逐项满足。这里分母为零的格子使用给定导数，不是统一填零。

总条件数为 $M=\sum_jm_j$ 时，若实目标属于 $C^M[a,b]$ ，对应 Hermite 多项式的余项为 $f^{(M)}(\xi_x)\prod_j(x-x_j)^{m_j}/M!$ 。证明沿用插值余项：减去适当倍数的节点乘积，得到在各节点按重数计共 $M$ 个零点，并额外在查询点为零；反复 Rolle 时每个重零点少一重，邻点之间再产生一根，最终第 $M$ 阶导数有零点。若查询点本身是节点，余项直接为零。导数数据的舍入或噪声须另算，不能由这个精确数据公式消去。

推论与应用

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

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

参考资料

NIST Digital Library of Mathematical Functions, §3.3(iii) Divided Differences, 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.
NIST DLMF，§3.3(iv) Newton公式末段：合并节点的差商取导数除以阶乘；本页给出合流表算例与重零点余项证明。

形式陈述 ​

反向链接

形式陈述