存在以及唯一性定理:如果存在有\(1n+\)个不重复的点\((x_0,y_0),(x_1,y_1),...,(x_n,y_n)\),那么一定存在且只有一组系数\(a_1,a_2...a_n\)使得
\[p(x)=a_0+a_1x+a_2x^2+...+a_nx^n \]成立。
存在性证明:
首先引入\(Lagrange\ Polynomials\)即拉格朗日多项式
\[L_i(x)=\prod_{j=0,j\neq i}^n\frac{x-x_j}{x_i-x_j},\ \ \text{for all}\ i\in\{0,1,...n\} \]那么我们可以得出:
\[L_{i}\left(x_{k}\right)=\left\{\begin{array}{cl} 1 & \text { if } i=k \\ 0 & \text { otherwise } \end{array}\right\}=\delta_{i, k} \]所以 \(p(x)=\sum_{k=0}^ny_kL_k(x)\), 满足\(p\left(x_{i}\right)=y_{i}\) for all \(i \in\{0, \ldots, n\}\)。就是我们要求的多项式
唯一性证明:
假设我们找到了两组多项式\(p\)和\(q\),那么\(p(x_i)=q(x_i)=y_i\)。令\(r(x)=p(x)-q(x)\),则\(r(x)\)满足\(r(x_i)=0\), for all \(i \in\{0, \ldots, n\}\)。
由于无论是\(p(x)\)还是\(q(x)\)度最多就只有\(n\)也就是说\(r(x)\)的度最大就是\(n\),但是\(r(x)=0\)却有\(n+1\)个解。因此\(r(x)=0\)。
尽管在上面的正名之中,我们已经得出了\(p(x)=\sum_{k=0}^n L_k(x)y_k\),但是在实际之中几乎没有人会使用\(Lagrange\ Polynomials\)来求解多项式插值。原因主要有以下两点
Newton多项式的参数\(b\)如下所示:
\[N_i(x)=\prod_{j=0}^{i-1}(x-x_j) \]多项式如下所示:
\[p(x)=\sum_{i=0}^nb_iN_i(x) \]我们需要迭代地解出\(b_i\),迭代的方法如下所示
\[\begin{aligned} y_{0}=p\left(x_{0}\right) &=b_{0} \\ y_{1}=p\left(x_{1}\right) &=b_{0}+b_{1}\left(x_{1}-x_{0}\right) \\ & \vdots \\ y_{n}=p\left(x_{n}\right) &=b_{0}+b_{1}\left(x_{n}-x_{0}\right)+\ldots+b_{n}\left(x_{n}-x_{0}\right) \ldots\left(x_{n}-x_{n-1}\right) \end{aligned} \]假设\((x_0,y_0),(x_1,y_1)...\)是若干点,有两个函数\(f\),\(g\)满足
然后我们就可以建立起一个新的divided-difference 函数
\[h(x)=f(x)+\frac{g(x)-f(x)}{x_{n}-x_{0}}\left(x-x_{0}\right) \]该函数满足:
\(h\left(x_{i}\right)=y_{i}\) for all \(i \in\{0, \ldots, n\}\)。