多项式插值-族谱新闻-族谱网

多项式插值

2020-10-16

出处：族谱网

作者：阿族小谱

浏览:887次

转发:0次

评论:0

应用多项式可以根据少数给定的数据点来逼近复杂的曲线，如字体排印学中的文字。一个相关的应用是估计自然对数和三角函数的值：选择几个已知的数据点、构建一个查找表、然后在这些数据点之间进行插值。这样可以得到非常快速的计算。另外多项式插值也是数值积分和数值常微分方程中算法的基础。多项式插值在sub-quadratic乘法以及平方运算中也很关键。例如，有a=f(x)=a0x+a1x+...以及b=g(x)=b0x+b1x+...那么乘积ab等于W(x)=f(x)g(x)。基于这些点的插值将得到W(x)以及乘积ab。对于Karatsuba乘法来说，这项技术的速度要比普通数目输入的二次乘法速度要快，尤其是在用并行的硬件实现的时候更是这样。定义给定一组n+1个数据点（xi,yi），其中任意两个xi都不相同，需要找到一个满足的不大于n阶的p阶多项式。唯一性定理表明存在一个并且仅有一个这样的p阶多项式。用更加复...

应用

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

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

定义

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

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

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

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

构建插值多项式

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

假设插值多项式的形式为

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

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

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

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

非范德蒙解

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

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

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

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

插值误差

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

其中

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

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

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

勒贝格常数

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

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

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

收敛性

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

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

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

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

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

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

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