多项式插值

多项式可以根据少数给定的数据点来逼近复杂的曲线，如字体排印学中的文字。一个相关的应用是估计自然对数和三角函数的值：选择几个已知的数据点、构建一个查找表、然后在这些数据点之间进行插值。这样可以得到非常快速的计算。另外多项式插值也是数值积分和数值常微分方程中算法的基础。

多项式插值在 sub-quadratic 乘法以及平方运算中也很关键。例如，有 a = f(x) = a₀x⁰ + a₁x¹ + ... 以及 b = g(x) = b₀x⁰ + b₁x¹ + ... 那么乘积 ab 等于 W(x) = f(x)g(x)。基于这些点的插值将得到 W(x) 以及乘积 ab。对于 Karatsuba 乘法来说，这项技术的速度要比普通数目输入的二次乘法速度要快，尤其是在用并行的硬件实现的时候更是这样。

给定一组 n+1 个数据点（x_i,y_i），其中任意两个 x_i 都不相同， 需要找到一个满足

${\displaystyle p(x_{i})=y_{i}{\mbox{ , }}i=0,\ldots ,n.}$

的不大于 n 阶的 p 阶多项式。唯一性定理表明存在一个并且仅有一个这样的 p 阶多项式。

用更加复杂的说法，这个多项式可以表述为：对于 n+1 个插值点 (x_i)，多项式插值定义了一个线性双射

${\displaystyle L_{n}:\mathbb {K} ^{n+1}\to \Pi _{n}}$

其中 ${\displaystyle \Pi _{n}}$ 是小于或者等于 n 的多项式的向量空间。

红色点表示数据点(x_k,y_k)，蓝色曲线表示插值多项式。

假设插值多项式的形式为

${\displaystyle p(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{2}x^{2}+a_{1}x+a_{0}.\qquad (1)}$

p 对数据点进行插值其含义为

${\displaystyle p(x_{i})=y_{i}\qquad {\mbox{for all }}i\in \left\{0,1,\dots ,n\right\}.}$

如果代入等式（1），就得到系数为 ${\displaystyle a_{k}}$ 的线性方程系统，用矩阵向量形式表示为

${\displaystyle {\begin{bmatrix}x_{0}^{n}&x_{0}^{n-1}&x_{0}^{n-2}&\ldots &x_{0}&1\\x_{1}^{n}&x_{1}^{n-1}&x_{1}^{n-2}&\ldots &x_{1}&1\\\vdots &\vdots &\vdots &&\vdots &\vdots \\x_{n}^{n}&x_{n}^{n-1}&x_{n}^{n-2}&\ldots &x_{n}&1\end{bmatrix}}{\begin{bmatrix}a_{n}\\a_{n-1}\\\vdots \\a_{0}\end{bmatrix}}={\begin{bmatrix}y_{0}\\y_{1}\\\vdots \\y_{n}\end{bmatrix}}.}$

为了构建插值多项式 ${\displaystyle p(x)}$ ，我们要解这个系统计算系数 ${\displaystyle a_{k}}$ 。

左侧的矩阵通常叫作范德蒙矩阵，它的行列式不为零，这也就证明了唯一性定理：存在唯一的一个插值多项式。

我们要在 n 阶多项式向量空间 ${\displaystyle \Pi _{n}}$ 中构建唯一的一个插值多项式。当用单项式基表示 ${\displaystyle \Pi _{n}}$ 时，为了建立插值多项式的系数 ${\displaystyle a_{k}}$ 我们要解范德蒙矩阵，这个过程可能会耗费大量的计算量。通过为 ${\displaystyle \Pi _{n}}$ 选择另外一种基我们可以简化系数的计算，但是如果需要用单项式基表示的话当然需要一些额外的计算工作。

其中一个方法是将插值多项式表示成牛顿型多项式，并且使用均差方法建立系数。其代价是0${\displaystyle (n^{2})}$ 运算，而高斯消去需要 O${\displaystyle (n^{3})}$ 运算。另外，如果在数据集中添加了额外的点，也只需要很少的额外运算；而其它方法通常都需要全部重新计算。

另外一个方法是使用拉格朗日型的插值多项式，得到的结果公式马上就表明在满足上面定理所定义条件下存在插值多项式。

Bernstein form 最初是 Sergei Natanovich Bernstein 在魏尔施特拉斯逼近定理的建设性证明中所用的形式，如今它在计算机图形学的贝塞尔曲线中得到了非常重要的应用。

用 n 阶多项式在节点 x₀、...、x_n 对函数 f 插值的误差为：

${\displaystyle f(x)-p_{n}(x)=f[x_{0},\ldots ,x_{n},x]\prod _{i=0}^{n}(x-x_{i})}$

其中

${\displaystyle f[x_{0},\ldots ,x_{n},x]}$

是均差符号。如果 f 在包含节点 x_i 的最小区间 I 上 n+1 次连续可导，那么我们可以将在 I 中 ${\displaystyle \xi }$ 的误差写成拉格朗日型

${\displaystyle f(x)-p_{n}(x)={\frac {f^{(n+1)}(\xi )}{(n+1)!}}\prod _{i=0}^{n}(x-x_{i})}$

这样，拉格朗日型泰勒定理的余数就是所有插值节点 x_i 都相同的情况下的插值误差特例。 如果插值节点等距分布 ${\displaystyle x_{i}=x_{0}+ih}$ ，那么插值误差为 O${\displaystyle (h^{n})}$ 。但是，这并不意味着随着 n → ∞ 插值误差将趋近于 0；实际上，在接近区间 ${\displaystyle [x_{0},x_{n}]}$ 端点的时候，误差甚至可能会变得无限大，这种现象叫作龙格现象。

上面的误差范围说明我们要选择使乘积 | ∏ (x − x_i) | 尽可能小的插值点 x_i。切比雪夫节点就可以实现这个结果。

在插值节点 x₀、...、x_n 以及包含所有插值节点的区间 [a, b] 确定下来，插值的过程就是将函数 f 映射到多项式 p。这定义了一个 [a, b] 区间上所有连续函数从空间 C([a, b]) 到其自身的映射。映射 X 是线性的，并且它是函数 f 在子空间 Π_n 上的投影。 勒贝格常数 L 定义为 X 的算子范数，它满足勒贝格引理：

${\displaystyle \|f-X(f)\|\leq (L+1)\|f-p^{*}\|.}$

换句话说，插值多项式的误差最多是最优逼近的（L+1）倍，这表明我们要找使 L 最小的插值节点。尤其是选择切比雪夫节点时：

${\displaystyle L\geq {\frac {2}{\pi }}\log(n+1)+C\quad {\mbox{for some constant }}C.}$

我们再次证明切比雪夫节点是多项式插值中比较好的选择，但是这些节点并不是最优的。

很自然我们有一个疑问，即对于什么类型的函数以及什么样的插值节点情况下，插值多项式才能够收敛到被插值的函数。收敛性有不同的类型，如点态收敛、一致收敛或者积分收敛。下面将讨论一致收敛。

下面的定理是一个相当令人振奋的答案：

对于在区间 [a,b] 内连续的任意函数 f(x)，存在一个节点表使得插值多项式 ${\displaystyle p_{n}(x)}$ 在 [a,b] 内一致收敛于 f(x)。

证明：根据魏尔施特拉斯逼近定理，我们知道最优逼近多项式序列 ${\displaystyle p_{n}^{*}(x)}$ 一致收敛到 f(x)。 现在我们只需证明每个 ${\displaystyle p_{n}^{*}(x)}$ 都可以通过在特定节点的插值得到，但是根据切比雪夫交错定理这是最优逼近多项式的一个特性。我们明确地得知这样的多项式至少与函数 f(x) 相交 n+1 次。将这些交点作为插值的节点，那么插值多项式就是最优逼近多项式。

但是这个方法的缺点是对每个新函数 f(x) 都要重新计算插值节点，而这个算法很难用数值方法实现。是不是存在一个节点表能够满足插值多项式序列收敛到任意一个连续函数 f(x) 呢？这个问题的答案是否定的，其理由在于下面的定理的结论：

对于任何的节点表都存在一个连续函数 f(x) 在区间 [a,b] 上使得插值多项式发散。

这个证明主要是依据勒贝格常数下限的估计，它定义了 'Xn 的算子范数，其中 'X_n 是在 Π_n 上的投影算子。现在我们要找一个对于任意的 ${\displaystyle f\in C([a,b])}$ 符合

${\displaystyle \lim _{n\to \infty }X_{n}f=f,}$

条件的节点表。根据 Banach-Steinhaus定理，只有当 X_n 的范数一致有界时才存在这样的节点表，但是根据 ${\displaystyle \|X_{n}\|\geq {\frac {2}{\pi }}\log(n+1)+C}$ 我们知道这是不可能的。

例如，如果选择等距点作为插值节点，那么龙格现象中的函数表明这样的插值就会出现发散现象。需要注意的是这个函数不仅连续而且在 [−1, 1] 内无限可导。但是对于效果较好的切比雪夫节点，根据下面的定理很难出现这个问题。

对于每个在 [−1, 1] 区间绝对连续的函数，在切比雪夫节点上构建的插值多项式序列一致收敛于 f(x)。

龙格现象表明高阶插值多项式可能在数据点之间出现震荡，通常可以通过样条插值来解决这个问题，在这种情况下，它不仅仅是一个多项式，而且是样条：一串低阶多项式组合。

使用调和分析函数对周期函数的插值通常是使用傅立叶级数实现的，如在离散傅立叶变换中所作的那样。这可以看作是一种带有调和基函数的多项式插值，参见三角插值与三角多项式。

埃尔米特插值问题是不仅给出了多项式 p 的值，而且给出了一些导数。伯克霍夫插值是给定一些导数而没有给定 p 自身的值的插值方法的一般形式。

微分与积分方程的配置法解法都是基于多项式插值。

• Kendell A. Atkinson (1988). An Introduction to Numerical Analysis (2nd ed.), Chapter 3. John Wiley and Sons. ISBN 0-471-50023-2
• L. Brutman (1997), Lebesgue functions for polynomial interpolation — a survey, Ann. Numer. Math. 4, 111–127.
• M.J.D. Powell (1981). Approximation Theory and Method, Chapter 4. Cambridge University Press. ISBN 0-521-29514-9.
• Michelle Schatzman (2002). Numerical Analysis: A Mathematical Introduction, Chapter 4. Clarendon Press, Oxford. ISBN 0-19-850279-6.
• Endre Süli and David Mayers (2003). An Introduction to Numerical Analysis, Chapter 6. Cambridge University Press. ISBN 0-521-00794-1.