插值多项式的存在性与唯一性

第一步(存在性)。拉格朗日构造 $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$。故第一步所得的插值多项式是唯一的。