多项式插值 Polynomial Interopolation

插值法又称「内插法」，是利用函数 f(x) 在某区间中已知的若干点的函数值，作出适当的特定函数，在区间的其他点上用这特定函数的值作为函数 f(x) 的近似值，这种方法称为插值法。如果这特定函数是多项式，就称它为多项式插值。常用的几种多项式插值法有：直接法、拉格朗日插值法和牛顿插值法。

定义

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

P（x_i）=y_i，i=0，… ，n

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

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

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

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

在实际应用中，这些插值点可能来自某次实验测量所得的数据，也可能来自某个复杂函数 y=f(x) 的值。通过计算插值多项式，我们可以找到这些实验数据间的规律，或者使用简单的多项式函数 y=P(z) 来近似复杂的函数 y=f(x) 。

构建多项式插值

假设插值多项式的形式为

$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），就得到系数为 $a_{k}$ 的线性方程系统，用矩阵向量形式表示为 ${\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}}.$

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

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

多项式插值的应用

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

多项式插值在 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 。对于卡拉楚巴乘法来说，这项技术的速度要比普通数目输入的二次乘法速度要快，尤其是在用并行的硬件实现的时候更是这样。

参考来源

【1】https://zh.wikipedia.org/wiki/%E5%A4%9A%E9%A1%B9%E5%BC%8F%E6%8F%92%E5%80%BC