牛顿插值

牛顿插值把通过给定数据点的多项式写成逐步加项的形式。给互异节点 $x_{0}, \dots, x_{n}$ 和数值 $y_{i}$ ，定义差商 $f [x_{i}] = y_{i}$ ，递推 $f [x_{i}, \dots, x_{i + k}] = \frac{f [x_{i + 1}, \dots, x_{i + k}] - f [x_{i}, \dots, x_{i + k - 1}]}{x_{i + k} - x_{i}} .$ 对应多项式为 $P_{n} (x) = f [x_{0}] + \sum_{k = 1}^{n} f [x_{0}, \dots, x_{k}] \prod_{j = 0}^{k - 1} (x - x_{j})$ 。

三个点逐项添加

取 $(x_{0}, y_{0}) = (0, 1)$ 、 $(x_{1}, y_{1}) = (1, 2)$ 、 $(x_{2}, y_{2}) = (2, 5)$ 。一阶差商分别为 1、3；二阶差商为 $(3 - 1) / (2 - 0) = 1$ 。所以 $P_{2} (x) = 1 + 1 (x - 0) + 1 (x - 0) (x - 1) = x^{2} + 1.$ 代回 $x = 0, 1, 2$ 得 1、2、5。若再增加第四个节点，已有前三项可保留，只需计算新差商并加一项，这是牛顿形式的实用之处。

图中青色抛物线经过三个给定点；金色虚线若只取两端点连直线，虽穿过 $(0, 1)$ 、 $(2, 5)$ ，却在 $x = 1$ 预测 3 而不是观测值 2。这说明仅两节点不足以固定第三点。实际牛顿构造按 $x_{0} = 0, x_{1} = 1, x_{2} = 2$ 的顺序：前两点先给直线 $1 + x$ ，它在 $x = 2$ 预测 3；新项 $x (x - 1)$ 在前两点为零、在第三点为 2，恰将预测值修正到 5。

过零一、一二、二五三点的青色二次曲线与只过两端点的金色虚线比较；中间节点处虚线为三而二次曲线为二 — 牛顿插值增加二阶项后通过第三个节点。

与误差的区别

插值多项式在节点处精确等于给定值，不表示节点之间必然精确符合未知函数。若真实函数 $f$ 在相应区间具有 $n + 1$ 阶导数，则对每个目标点 $x$ ，存在位于节点与 $x$ 所围区间内的 $ξ$ ，使 $f (x) - P_{n} (x) = \frac{f^{(n + 1)} (ξ)}{(n + 1)!} \prod_{i = 0}^{n} (x - x_{i}) .$ 节点间距、阶数与函数的高阶变化都影响误差；盲目增加等距节点可能出现端点振荡。

误差式可由重复使用罗尔定理证明。若 $x$ 不是节点，令 $K = (f (x) - P_{n} (x)) / \prod_{i} (x - x_{i})$ ，并设 $h (t) = f (t) - P_{n} (t) - K \prod_{i} (t - x_{i})$ 。它在 $n + 1$ 个节点及目标点 $x$ 共取零 $n + 2$ 次；连续求导并反复应用罗尔定理，得到某个 $ξ$ 使 $h^{(n + 1)} (ξ) = 0$ 。因为 $P_{n}^{(n + 1)} = 0$ ，乘积项的 $n + 1$ 阶导数为 $(n + 1)!$ ，便解得所写的 $K$ 。若 $x$ 本身是节点，误差与右侧乘积都为零，不需这个除法步骤。

参考资料