
_START_ARTICLE_
多项式插值
_START_PARAGRAPH_
在数值分析这个数学分支中，多项式插值用多项式对一组给定数据进行插值的过程。换句话说就是，对于一组给定的数据（如来自于采样的数据），其目的就是寻找一个恰好通过这些数据点的多项式。
_START_SECTION_
应用
_START_PARAGRAPH_
多项式可以根据少数给定的数据点来逼近复杂的曲线，如字体排印学中的文字。一个相关的应用是估计自然对数和三角函数的值：选择几个已知的数据点、构建一个查找表、然后在这些数据点之间进行插值。这样可以得到非常快速的计算。另外多项式插值也是数值积分和数值常微分方程中算法的基础。_NEWLINE_多项式插值在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 乘法来说，这项技术的速度要比普通数目输入的二次乘法速度要快，尤其是在用并行的硬件实现的时候更是这样。
_START_SECTION_
非范德蒙解
_START_PARAGRAPH_
我们要在n 阶多项式向量空间 中构建唯一的一个插值多项式。当用单项式基表示  时，为了建立插值多项式的系数 我们要解范德蒙矩阵，这个过程可能会耗费大量的计算量。通过为 选择另外一种基我们可以简化系数的计算，但是如果需要用单项式基表示的话当然需要一些额外的计算工作。_NEWLINE_其中一个方法是将插值多项式表示成牛顿型多项式，并且使用均差方法建立系数。其代价是0运算，而高斯消去需要O运算。另外，如果在数据集中添加了额外的点，也只需要很少的额外运算；而其它方法通常都需要全部重新计算。_NEWLINE_另外一个方法是使用拉格朗日型的插值多项式，得到的结果公式马上就表明在满足上面定理所定义条件下存在插值多项式。_NEWLINE_Bernstein form 最初是Sergei Natanovich Bernstein 在魏尔施特拉斯逼近定理的建设性证明中所用的形式，如今它在计算机图形学的贝塞尔曲线中得到了非常重要的应用。
_START_SECTION_
相关概念
_START_PARAGRAPH_
龙格现象表明高阶插值多项式可能在数据点之间出现震荡，通常可以通过样条插值来解决这个问题，在这种情况下，它不仅仅是一个多项式，而且是样条：一串低阶多项式组合。_NEWLINE_使用调和分析函数对周期函数的插值通常是使用傅立叶级数实现的，如在离散傅立叶变换中所作的那样。这可以看作是一种带有调和基函数的多项式插值，参见三角插值与三角多项式。_NEWLINE_埃尔米特插值问题是不仅给出了多项式p 的值，而且给出了一些导数。伯克霍夫插值是给定一些导数而没有给定p 自身的值的插值方法的一般形式。_NEWLINE_微分与积分方程的配置法解法都是基于多项式插值。