查看“︁多项式插值”︁的源代码

在[[数值分析]]这个[[数学]]分支中，'''多项式插值'''用[[多项式]]对一组给定数据进行[[插值]]的过程。换句话说就是，对于一组给定的数据（如来自于[[采样]]的数据），其目的就是寻找一个恰好通过这些数据点的多项式。

==应用==

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

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

==定义==

给定一组 ''n''+1 个数据点（''x''<sub>''i''</sub>,''y''<sub>''i''</sub>），其中任意两个 ''x''<sub>''i''</sub> 都不相同， 需要找到一个满足
:<math>p(x_i) = y_i \mbox{ , } i=0,\ldots,n.</math>
的不大于 ''n'' 阶的 ''p'' 阶多项式。'''唯一性定理'''表明存在一个并且仅有一个这样的 ''p'' 阶多项式。

用更加复杂的说法，这个多项式可以表述为：对于 ''n''+1 个插值点 (''x''<sub>''i''</sub>)，多项式插值定义了一个线性[[双射]]
:<math>L_n:\mathbb{K}^{n+1} \to \Pi_n</math>
其中 <math>\Pi_n</math> 是小于或者等于 ''n'' 的多项式的向量空间。

==构建插值多项式==

[[File:Interpolation_example_polynomial.png|right|frame|红色点表示数据点(''x''<sub>''k''</sub>,''y''<sub>''k''</sub>)，蓝色曲线表示插值多项式。]]

假设插值多项式的形式为
:<math>p(x) = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_2 x^2 + a_1 x + a_0. \qquad (1) </math>
''p'' 对数据点进行插值其含义为
:<math>p(x_i) = y_i \qquad\mbox{for all } i \in \left\{ 0, 1, \dots, n\right\}.</math>
如果代入等式（1），就得到系数为 <math>a_k</math> 的[[线性方程系统]]，用矩阵向量形式表示为
:<math>\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}.
</math>
为了构建插值多项式 <math>p(x)</math>，我们要解这个系统计算系数 <math>a_k</math>。

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

==非范德蒙解==

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

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

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

[[伯恩斯坦形式]]最初是[[謝爾蓋·納塔諾維奇·伯恩施坦]]在[[魏尔施特拉斯逼近定理]]的建设性证明中所用的形式，如今它在[[计算机图形学]]的[[贝塞尔曲线]]中得到了非常重要的应用。

==插值误差==

用 ''n'' 阶多项式在节点 ''x''<sub>''0''</sub>、...、''x''<sub>''n''</sub> 对函数 ''f'' 插值的误差为：

:<math>f(x) - p_n(x) = f[x_0,\ldots,x_n,x] \prod_{i=0}^n (x-x_i) </math>

其中 
:<math>f[x_0,\ldots,x_n,x]</math>

是[[均差]]符号。如果 ''f'' 在包含节点 ''x''<sub>''i''</sub> 的最小区间 ''I'' 上 ''n''+1 次连续可导，那么我们可以将在 ''I'' 中 <math>\xi</math> 的误差写成拉格朗日型

:<math> f(x) - p_n(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{i=0}^n (x-x_i) </math>

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

上面的误差范围说明我们要选择使乘积 | &prod; (''x'' &minus; ''x''<sub>''i''</sub>) | 尽可能小的插值点 ''x''<sub>''i''</sub>。[[切比雪夫多项式|切比雪夫节点]]就可以实现这个结果。

==勒贝格常数==
{{main|勒贝格常数}}

在插值节点 ''x''<sub>0</sub>、...、''x''<sub>''n''</sub> 以及包含所有插值节点的区间 [''a'', ''b''] 确定下来，插值的过程就是将函数 ''f'' 映射到多项式 ''p''。这定义了一个 [''a'', ''b''] 区间上所有连续函数从空间 ''C''([''a'', ''b'']) 到其自身的映射。映射 ''X'' 是线性的，并且它是函数 ''f'' 在子空间 &Pi;<sub>''n''</sub> 上的[[投影]]。
勒贝格常数 ''L'' 定义为 ''X'' 的[[算子范数]]，它满足[[勒贝格引理]]：
:<math> \|f-X(f)\| \le (L+1) \|f-p^*\|. </math>
换句话说，插值多项式的误差最多是最优逼近的（''L''+1）倍，这表明我们要找使 ''L'' 最小的插值节点。尤其是选择切比雪夫节点时：
:<math> L \ge \frac2\pi \log(n+1) + C \quad\mbox{for some constant } C. </math>
我们再次证明切比雪夫节点是多项式插值中比较好的选择，但是这些节点并不是最优的。

==收敛性==

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

下面的'''定理'''是一个相当令人振奋的答案：
 
:对于在区间 [''a'',''b''] 内连续的任意函数 ''f''(''x'')，存在一个节点表使得插值多项式 <math>p_n(x)</math> 在 [''a'',''b''] 内一致收敛于 ''f''(''x'')。

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

但是这个方法的缺点是对每个新函数 ''f''(''x'') 都要重新计算插值节点，而这个算法很难用数值方法实现。是不是存在一个节点表能够满足插值多项式序列收敛到任意一个连续函数 ''f''(''x'') 呢？这个问题的答案是否定的，其理由在于下面的'''定理'''的结论：
:对于任何的节点表都存在一个连续函数 ''f''(''x'') 在区间 [''a'',''b''] 上使得插值多项式发散。
这个证明主要是依据勒贝格常数下限的估计，它定义了 'X''<sub>''n''</sub> 的算子范数，其中 'X''<sub>''n''</sub> 是在 &Pi;<sub>''n''</sub> 上的投影算子。现在我们要找一个对于任意的  <math>f \in C([a,b])</math> 符合
:<math>\lim_{n \to \infty} X_n f = f,</math> 
条件的节点表。根据[[一致有界性原理|巴拿赫-斯坦豪斯定理]]，只有当 ''X''<sub>''n''</sub> 的范数一致有界时才存在这样的节点表，但是根据 <math>\|X_n\|\geq \frac{2}{\pi} \log(n+1)+C</math> 我们知道这是不可能的。

例如，如果选择等距点作为插值节点，那么[[龙格现象]]中的函数表明这样的插值就会出现发散现象。需要注意的是这个函数不仅连续而且在 [&minus;1, 1] 内无限可导。但是对于效果较好的[[切比雪夫节点]]，根据下面的定理很难出现这个问题。
:对于每个在 [&minus;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&uuml;li and David Mayers (2003). ''An Introduction to Numerical Analysis,'' Chapter 6. Cambridge University Press. ISBN 0-521-00794-1.

[[Category:插值论|D]]
[[Category:多项式|D]]
[[Category:数学近似]]