插值与逼近

n次多项式恰好有n+1个自由系数,而固定n+1个点的值恰好用尽这么多自由度——不多不少——因此只有容纳一个解的余地,没有容纳两个不同解的余地。

第一步(存在性)。拉格朗日构造 $P(x) = \sum_{i=0}^{n} y_i L_i(x)$(其中 $L_i(x) = \prod_{j\ne i} \dfrac{x-x_j}{x_i-x_j}$)已经对每个 $k$ 满足 $P(x_k)=y_k$,因为 $L_i(x_k)$ 在 $i=k$ 时等于 $1$,否则为 $0$,故求和坍缩为单项 $y_k \cdot 1 = y_k$。因此至少存在一个满足条件的 $P$,且每个 $L_i$ 的次数恰为 $n$($n$ 个一次因子之积),故 $P$ 的次数不超过 $n$。

第二步(假设存在两个解)。设 $Q$ 是任意另一个次数不超过 $n$ 且对每个 $i$ 满足 $Q(x_i)=y_i$ 的多项式。考虑差 $D(x) = P(x) - Q(x)$。由于 $P$ 与 $Q$ 的次数都不超过 $n$,故 $D$ 亦然。

第三步(计数差的根)。对每个节点 $x_i$,有 $D(x_i) = P(x_i)-Q(x_i) = y_i - y_i = 0$。由于存在 $n+1$ 个互异节点 $x_0, x_1, \dots, x_n$,故 $D$ 至少有 $n+1$ 个互异的根。

第四步(迫使D恒为零)。一个次数不超过 $n$ 的非零多项式至多有 $n$ 个根(每个根贡献一个一次因子,而次数为 $n$ 的多项式不能包含超过 $n$ 个这样的因子)。由于 $D$ 有 $n+1$ 个根,超出其次数所允许的数目,除非 $D$ 是零多项式,因此我们得出 $D(x)\equiv0$,即 $Q=P$。故第一步所得的插值多项式是唯一的。

插值多项式在节点处与f精确吻合,但对节点之间的f一无所知,因此剩余误差必须在每个节点处为零——这正是乘积项所强制的——并由一个衡量f弯曲程度(超出n次多项式所能捕捉范围)的剩余导数来调节大小。

第一步(巧妙的辅助函数)。固定一个不是节点的点 $x$(若是节点,误差平凡地为 $0$)。设 $w(t) = \prod_{i=0}^{n} (t - x_i)$,并定义常数 $c = \dfrac{f(x)-P(x)}{w(x)}$(由于 $w(x)\ne0$ 故有良好定义)。定义辅助函数 $g(t) = f(t) - P(t) - c\, w(t)$。

第二步(计数g的根)。在每个节点 $x_i$ 处,由插值性质 $f(x_i)-P(x_i)=0$,且由 $w$ 的定义 $w(x_i)=0$,故在全部 $n+1$ 个节点处都有 $g(x_i)=0$。此外,由 $c$ 的选取,$g(x) = f(x)-P(x) - c\,w(x) = f(x)-P(x) - [f(x)-P(x)] = 0$。故 $g$ 有 $n+2$ 个互异的根:$n+1$ 个节点加上 $x$ 本身。

第三步(反复应用罗尔定理)。在 $g$ 的每对相邻根之间($n+2$ 个根之间共有 $n+1$ 个这样的间隔),罗尔定理给出一点使 $g'$ 为零,故 $g'$ 至少有 $n+1$ 个根。对 $g', g'', \dots$ 重复此论证,每求一次导就减少一个根,故经过 $n+1$ 次应用后,$g^{(n+1)}$ 在该区间内至少有一个根 $\xi$。

第四步(求导并解出误差)。由于 $P$ 的次数不超过 $n$,其 $(n+1)$ 阶导数为 $0$;而 $w$ 是次数为 $n+1$ 的首一多项式,故对一切 $t$ 都有 $w^{(n+1)}(t) = (n+1)!$。对 $g$ 求导得 $g^{(n+1)}(t) = f^{(n+1)}(t) - 0 - c\,(n+1)!$,令 $g^{(n+1)}(\xi)=0$ 得 $c = \dfrac{f^{(n+1)}(\xi)}{(n+1)!}$。回想 $c=\dfrac{f(x)-P(x)}{w(x)}$ 并解出误差,恰好得到 $f(x) - P(x) = \dfrac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{i=0}^{n} (x - x_i)$。

经过多个点的单一高次多项式往往会剧烈摆动,但将许多平缓的三次片段拼接起来、只要求它们在接缝处平滑衔接,就恰好提供了足够的自由度来拟合数据而不产生剧烈振荡,而自然边界条件恰好提供了使整个方程组可解所需的两个额外方程。

第一步(未知量:各节点处的二阶导数)。设 $i=0,\dots,n$ 时 $M_i = S''(x_i)$。自然边界条件立即固定 $M_0=0$ 与 $M_n=0$,剩下 $n-1$ 个未知量 $M_1,\dots,M_{n-1}$ 待定。

第二步(由M值重构每个三次段)。在 $[x_i,x_{i+1}]$ 上,由于 $S$ 是三次的,故 $S''$ 是线性的,必为经过 $(x_i,M_i)$ 与 $(x_{i+1},M_{i+1})$ 的直线。将该线性函数积分两次,并利用 $S(x_i)=y_i$ 与 $S(x_{i+1})=y_{i+1}$ 固定两个积分常数,便完全确定了该段上的 $S$,用 $M_i, M_{i+1}, y_i, y_{i+1}$ 及间距 $h_i=x_{i+1}-x_i$ 表示。因此一旦所有 $M_i$ 已知,$S$ 便完全确定。

第三步(斜率匹配给出线性方程组)。按构造,$S$ 与 $S''$ 在每个节点处已经连续。要求一阶导数 $S'$ 在每个内部节点 $x_i$($i=1,\dots,n-1$)处从两侧也一致,便在每个内部节点处产生一个关联三个连续未知量的线性方程:$h_{i-1} M_{i-1} + 2(h_{i-1}+h_i) M_i + h_i M_{i+1} = 6\left(\dfrac{y_{i+1}-y_i}{h_i} - \dfrac{y_i-y_{i-1}}{h_{i-1}}\right)$。这给出关于 $n-1$ 个未知量 $M_1,\dots,M_{n-1}$(利用 $M_0=M_n=0$)的 $n-1$ 个线性方程。

第四步(方程组有唯一解)。该方程组的系数矩阵是三对角矩阵,对角元为 $2(h_{i-1}+h_i)$,非对角元为 $h_{i-1}$ 与 $h_i$;由于所有间距 $h_i>0$,故 $2(h_{i-1}+h_i) > h_{i-1}+h_i$,该矩阵严格对角占优,而严格对角占优矩阵总是可逆的。因此关于 $M_1,\dots,M_{n-1}$ 的线性方程组恰有一个解,由第二步这唯一确定了一条样条 $S$,从而同时证明了存在性与唯一性。