牛顿插值法

定义

给定一组互不相同的节点 $x_0,x_1,\dots,x_n$ 及其上的函数值，插值问题要求找一个次数不超过 $n$ 的多项式，使它在每个节点处都等于给定的函数值。牛顿插值多项式就是按差商展开的这类多项式，其形式为 $N_n(x)=f[x_0]+f[x_0,x_1](x-x_0)+f[x_0,x_1,x_2](x-x_0)(x-x_1)+\cdots+f[x_0,x_1,\dots,x_n](x-x_0)(x-x_1)\cdots(x-x_{n-1})$，其中 $f[x_0,x_1,\dots,x_k]$ 表示函数在相应节点上的 $k$ 阶差商。^[3][4]

它的余项可以写成高一阶差商与连乘积的乘积，即 $R_n(x)=f[x,x_0,\dots,x_n]\omega_{n+1}(x)$，其中 $\omega_{n+1}(x)=(x-x_0)(x-x_1)\cdots(x-x_n)$。由插值多项式的存在唯一性可以知道，牛顿形式与拉格朗日形式给出的是同一个多项式，区别只在于所选用的基函数不同。^[4]

原理

差商的定义是递推的：一阶差商等于两个函数值之差除以对应节点之差；二阶差商由两个一阶差商相减，再除以首末节点之差；一般地，$k$ 阶差商由两个 $k-1$ 阶差商作同样处理得到。^[3] 调换节点次序不会改变差商的值，它还可以写成各个函数值的线性组合。^[4]

牛顿形式便于扩展，关键在于它所选用的基函数为 $\phi_0(x)=1$，$\phi_1(x)=x-x_0$，$\phi_2(x)=(x-x_0)(x-x_1)$，依次类推。这组基函数线性无关，构成次数不超过 $n$ 的多项式空间的一组基，因此插值多项式可以逐次生成：$p_{n+1}(x)=p_n(x)+u_{n+1}(x)$。^[3]

各阶差商通常排成一张差商表，表中每个内层元素由相邻两个低一阶差商相减、再除以相应节点间距得到：

flowchart LR

a["f(x₀)"] --> d1["f[x₀,x₁]"]

b["f(x₁)"] --> d1

b --> d2["f[x₁,x₂]"]

c["f(x₂)"] --> d2

d1 --> d3["f[x₀,x₁,x₂]"]

d2 --> d3

算出系数后，求多项式在某一点的值可以改用嵌套乘法，即从最高阶差商起逐层乘 $(x-x_i)$ 并累加。计算整张差商表大致需要 $O(n^2)$ 次运算，而在差商已经算出的情况下，求单个点处的值只需 $O(n)$ 次运算。 若节点等距，差商退化为有限差分，插值公式还能进一步简化为前插、后插等专用形式。^[2]

发展历程

牛顿关于插值的贡献主要收在几份文献里：1675年的一封书信、《差分方法》(Methodus differentialis)、《自然哲学的数学原理》第三编第5号引理，以及一份久未刊布的文稿。^[5] 他研究这一问题的动因之一，是当时编制函数表的需要。^[6]

1687年问世的《自然哲学的数学原理》第三编中，牛顿以引理的形式给出两种插值公式，一种针对等间距数据，另一种适用于任意间距的数据；《差分方法》虽写于17世纪70年代中期，却迟至1711年才正式刊行。^[6]

等间距情形下的公式与詹姆斯·格雷戈里早先得到的结果相近，因此有时被合称为格雷戈里－牛顿公式。有文献指出，牛顿在1676年的讲演中已经讲授过自己的插值方法。^[6]

拉格朗日形式的插值公式出现在1795年拉格朗日在巴黎高等师范学校的课程中，沃林(Waring)在1779年已有相近的结果。两种形式表示的是同一个多项式，后人按各自的需要选用。^[7]

应用

在实验与工程数据处理中，常遇到只能测到离散点、或只能以数值解表示对应关系的情形，此时可用牛顿插值对数据作拟合，求出中间点的近似函数值；由于步骤条理清楚、便于编程，它在实验分析中使用较多。^[1]

差商本身可以充当判断函数光滑程度的指示器：函数平缓时高阶差商迅速衰减，遇到跳跃或尖角时，跨越该区域的高阶差商绝对值会显著增大。计算流体力学中的本质非振荡(ENO)与加权本质非振荡(WENO)格式正是利用这一性质挑选不跨越间断的插值模板，以抑制激波附近的数值振荡。^[8]

在金融领域，收益率曲线可以由期限与收益率的数据点用牛顿形式构建；当市场上出现新的数据点时，递推结构允许直接在原有模型上补入一项，而不必整体重算。类似做法也被用来把若干已知状态上算出的复杂函数值整理成插值多项式，作为计算量很小的代理模型反复调用。^[8]

对于多个变量的函数，可以用张量积把牛顿插值推广到高维；对二维数据，也可以先沿一个方向插值、再沿另一个方向插值，从而把零散的测点拼成连续曲面，例如芯片上的温度分布或化学反应的能量面。^[9]

局限

插值多项式的次数并非越高越好。20世纪初，德国数学家龙格(Runge)以 $f(x)=1/(1+x^2)$ 在区间 $[-5,5]$ 上的等距节点插值为例说明，随着节点增多，插值多项式在区间两端会出现剧烈振荡，并不收敛于原函数，这一现象称为龙格现象。^[10]

受此影响，实际计算中很少采用七八次以上的高次插值，等间隔数据的插值点数达到约8点以上时就应谨慎，通常改用分段低次插值或样条插值。^[11]

插值多项式只适合在数据点之间作估计。若用它预测数据范围之外的情形，误差会迅速增大，所得结果可能严重偏离真实情况。^[12]

多项式插值在数值上还可能是病态的：输入数据的细微变动有时会引起结果的显著改变。^[13] 此外，牛顿形式的差商与全部数据有关，每加入一个新的函数值，都要计算相应的新差商。

参见

• 拉格朗日插值法 —— 另一种插值多项式的表示形式，与牛顿插值法给出的是同一个多项式

• 差商 —— 牛顿插值多项式系数的来源

• 龙格现象 —— 高次等距节点插值在区间两端出现的振荡

• 样条插值 —— 为克服高次插值振荡而常用的分段低次方法

• 埃米尔特插值 —— 同时利用函数值与导数值的插值方法

• 有限差分 —— 等距节点下差商退化为差分，可简化插值公式