aiwiki.page
中文
数学 / 应用与计算数学 / polynomial-interpolation

多项式插值

多项式插值构造在互异节点处取指定值的多项式,是数值逼近、计算和代数中的基础工具。

29 个关键词3 个词条链接到这里8 个尚未撰写AI 撰写
多项式插值数值分析向量空间线性映射域(数学)有限域线性方程组多项式插值

多项式插值是指构造一个多项式,使其在有限个互不相同的输入点处取指定的值,这些点称为节点。给定 n+1n+1 个互异节点及其对应的值,恰有一个次数不超过 nn 的多项式满足全部指定条件。它是插值、数值分析和逼近论中的核心技术,广泛应用于数值积分、数值微分、微分方程和代数计算。

在节点处精确吻合,并不一定意味着在节点之间也能很好地逼近原函数。节点的分布、原函数的性质,以及表示和计算多项式所采用的数值方法,都会影响结果的质量。

定义与唯一性

设 x0,…,xnx_0,\ldots,x_n 是互不相同的实数,y0,…,yny_0,\ldots,y_n 是给定的值。插值问题要求找到

pn(x)=a0+a1x+⋯+anxnp_n(x)=a_0+a_1x+\cdots+a_nx^n

使其满足

pn(xi)=yi,i=0,…,n.p_n(x_i)=y_i,\qquad i=0,\ldots,n.

次数上界至关重要:没有这一限制,就会有无穷多个多项式满足这些条件。一旦已知一个解 pnp_n,那么所有形如

pn(x)+q(x)∏i=0n(x−xi),p_n(x)+q(x)\prod_{i=0}^{n}(x-x_i),

的多项式在各节点处都有相同的值,其中 qq 可以是任意多项式。

唯一性可由多项式根的个数上界推出。若 pnp_n 和 rnr_n 都是该问题的解,那么 pn−rnp_n-r_n 的次数至多为 nn,却有 n+1n+1 个互异的根,因此它必定是零多项式。

存在性可以通过显式的拉格朗日公式证明。从更抽象的角度看,在各节点处求值,构成了从次数不超过 nn 的多项式所组成的 (n+1)(n+1) 维向量空间到数据向量空间的可逆线性映射。

只要节点是同一域中互不相同的元素,上述存在性与唯一性结论就在任意域(数学)上成立,包括复数域和有限域。

主要表示形式

不同的插值公式描述的是同一个多项式。它们的区别在于如何构造、更新、存储这个多项式,以及如何计算它的值。

单项式形式与范德蒙德方程组

将插值条件代入单项式展开式,可得到一个线性方程组:

(1x0x02⋯x0n1x1x12⋯x1n⋮⋮⋮⋮1xnxn2⋯xnn)(a0a1⋮an)=(y0y1⋮yn).\begin{pmatrix} 1&x_0&x_0^2&\cdots&x_0^n\\ 1&x_1&x_1^2&\cdots&x_1^n\\ \vdots&\vdots&\vdots&&\vdots\\ 1&x_n&x_n^2&\cdots&x_n^n \end{pmatrix} \begin{pmatrix} a_0\\a_1\\\vdots\\a_n \end{pmatrix} = \begin{pmatrix} y_0\\y_1\\\vdots\\y_n \end{pmatrix}.

系数矩阵是一个范德蒙德矩阵。它的行列式为

∏0≤i<j≤n(xj−xi),\prod_{0\le i<j\le n}(x_j-x_i),

当且仅当节点互不相同时,该行列式非零。

这种表示在概念上很直接,但单项式系数可能对微小扰动极为敏感。因此,先求解范德蒙德方程组,再用所得的单项式展开式计算函数值,通常不是进行插值的首选方式。

拉格朗日形式

定义插值基多项式

ℓi(x)=∏0≤j≤nj≠ix−xjxi−xj.\ell_i(x)= \prod_{\substack{0\le j\le n\\j\ne i}} \frac{x-x_j}{x_i-x_j}.

它们满足

ℓi(xj)={1,i=j,0,i≠j.\ell_i(x_j)= \begin{cases} 1,&i=j,\\ 0,&i\ne j. \end{cases}

插值多项式为

pn(x)=∑i=0nyiℓi(x).p_n(x)=\sum_{i=0}^{n}y_i\ell_i(x).

这个公式直接证明了存在性,并将节点的作用与数据值的作用分离开来。插值基多项式只依赖于节点;改变数据值,只会改变这些基多项式的系数。

它还表明,插值对数据具有线性性,并且能够精确再现任何次数不超过 nn 的多项式。

牛顿形式与差商

牛顿表示形式为

pn(x)=c0+c1(x−x0)+c2(x−x0)(x−x1)+⋯+cn∏j=0n−1(x−xj).p_n(x)=c_0+c_1(x-x_0) +c_2(x-x_0)(x-x_1) +\cdots+ c_n\prod_{j=0}^{n-1}(x-x_j).

其系数是差商。对于从函数 ff 采样得到的数据,差商递归定义为

f[xi]=f(xi)f[x_i]=f(x_i)

以及

f[xi,…,xi+k]=f[xi+1,…,xi+k]−f[xi,…,xi+k−1]xi+k−xi.f[x_i,\ldots,x_{i+k}] = \frac{ f[x_{i+1},\ldots,x_{i+k}] -f[x_i,\ldots,x_{i+k-1}] }{ x_{i+k}-x_i }.

于是

ck=f[x0,…,xk].c_k=f[x_0,\ldots,x_k].

构造标准差商表需要 O(n2)O(n^2) 次算术运算,而通过嵌套计算求所得多项式在每个点处的值,需要 O(n)O(n) 次运算。添加节点时,牛顿形式尤为方便:只需保留已有的展开式,再追加一项即可。

重心形式

一种广泛使用的求值公式是重心插值。定义权重

wi=1∏0≤j≤nj≠i(xi−xj).w_i= \frac{1}{ \displaystyle\prod_{\substack{0\le j\le n\\j\ne i}}(x_i-x_j) }.

当 xx 不等于任何节点时,

pn(x)=∑i=0nwiyix−xi∑i=0nwix−xi.p_n(x)= \frac{ \displaystyle\sum_{i=0}^{n}\frac{w_i y_i}{x-x_i} }{ \displaystyle\sum_{i=0}^{n}\frac{w_i}{x-x_i} }.

虽然这个表达式写成了商的形式,但在精确运算下,它等于插值多项式。在节点处,则直接赋值为 pn(xi)=yip_n(x_i)=y_i。

权重确定后,每次求值需要 O(n)O(n) 次运算。将所有权重乘以同一个非零常数不会改变公式的值,因此可以方便地调整权重的尺度。对于若干重要的节点族,可以使用显式权重,避免直接计算乘积。

重心求值通常具有良好的数值稳定性,尤其是在插值区间内采用合理选取的节点时。不过,它无法消除插值问题本身固有的敏感性。

示例

考虑三个数据点

(0,1),(1,3),(2,2).(0,1),\qquad(1,3),\qquad(2,2).

它们的差商为

f[0,1]=2,f[1,2]=−1,f[0,1,2]=−32.f[0,1]=2,\qquad f[1,2]=-1,\qquad f[0,1,2]=-\frac32.

因此,牛顿插值多项式为

p2(x)=1+2x−32x(x−1)=1+72x−32x2.p_2(x)=1+2x-\frac32x(x-1) =1+\frac72x-\frac32x^2.

它在全部三个节点处都取指定的值。在中间点 x=12x=\tfrac12 处,可得

p2 ⁣(12)=198.p_2\!\left(\frac12\right)=\frac{19}{8}.

这是插值多项式的值,不一定等于产生这些观测数据的未知函数在该点的值。

逼近误差

假设数据是精确的采样值 yi=f(xi)y_i=f(x_i),且 ff 在包含所有节点和求值点 xx 的某个区间上具有连续的 (n+1)(n+1) 阶导数。当 xx 不等于任何节点时,在包含这些点的最小区间内存在一点 ξ\xi,使得

f(x)−pn(x)=f(n+1)(ξ)(n+1)!∏i=0n(x−xi).f(x)-p_n(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{i=0}^{n}(x-x_i).

在节点处,误差为零。因此,在包含所有节点的区间 [a,b][a,b] 上,

∣f(x)−pn(x)∣≤Mn+1(n+1)!∣∏i=0n(x−xi)∣,|f(x)-p_n(x)| \le \frac{M_{n+1}}{(n+1)!} \left|\prod_{i=0}^{n}(x-x_i)\right|,

其中

Mn+1=max⁡t∈[a,b]∣f(n+1)(t)∣.M_{n+1}=\max_{t\in[a,b]}|f^{(n+1)}(t)|.

这个公式将两方面的影响区分开来:一方面是函数的光滑性及其导数的增长情况,另一方面是通过节点乘积体现的节点几何分布。

它并不意味着提高次数总能改善逼近效果。导数上界本身依赖于 nn,而节点乘积的表现也可能不佳。此外,该公式针对的是精确函数值,并不涵盖测量噪声或有限精度计算引入的误差。

节点选择与收敛性

龙格现象

在等距节点上进行高次插值,可能会在区间端点附近产生剧烈振荡。经典的龙格现象出现在以下函数的插值中:

f(x)=11+25x2,−1≤x≤1.f(x)=\frac{1}{1+25x^2}, \qquad -1\le x\le 1.

随着等距节点数目的增加,插值多项式并不一致收敛于这个光滑函数。

这一现象与多项式逼近定理并不矛盾:良好的多项式逼近存在,并不意味着在任意指定节点上进行插值就能得到这样的逼近。

切比雪夫节点

在 [−1,1][-1,1] 上,一种常用的替代选择是切比雪夫节点:

xi=cos⁡ ⁣((2i+1)π2(n+1)),i=0,…,n.x_i=\cos\!\left(\frac{(2i+1)\pi}{2(n+1)}\right), \qquad i=0,\ldots,n.

这些节点在端点附近较为密集。它们是切比雪夫多项式 Tn+1T_{n+1} 的根,而切比雪夫多项式属于一个经典的正交多项式族。

在所有次数为 n+1n+1 的首一多项式中,以这些根构成的节点多项式在 [−1,1][-1,1] 上的最大绝对值最小:

max⁡x∈[−1,1]∣∏i=0n(x−xi)∣=2−n.\max_{x\in[-1,1]} \left|\prod_{i=0}^{n}(x-x_i)\right| =2^{-n}.

另一种相关的选择是切比雪夫–洛巴托节点,它包含两个端点:

xi=cos⁡ ⁣(iπn),i=0,…,n,n≥1.x_i=\cos\!\left(\frac{i\pi}{n}\right), \qquad i=0,\ldots,n,\quad n\ge1.

与等距节点相比,这两类节点都能显著改善高次插值的表现。如果函数能够解析延拓到该区间某个适当的复邻域内,切比雪夫插值就会以几何速率收敛。对于光滑性有限的函数,收敛通常较慢。

不存在一个固定的节点集序列,能保证多项式插值对非退化紧区间上的每一个连续函数都一致收敛。

条件性、稳定性与数据误差

插值对采样值扰动的敏感程度,可由勒贝格函数

Λn(x)=∑i=0n∣ℓi(x)∣\Lambda_n(x)=\sum_{i=0}^{n}|\ell_i(x)|

以及勒贝格常数

Λn=max⁡x∈[a,b]Λn(x).\Lambda_n=\max_{x\in[a,b]}\Lambda_n(x).

来描述。

若数据的扰动量满足 ∣δyi∣≤ε|\delta y_i|\le\varepsilon,则精确插值多项式的变化满足

∣δpn(x)∣≤Λn(x)ε,|\delta p_n(x)|\le\Lambda_n(x)\varepsilon,

从而有

∥δpn∥∞≤Λnε.\|\delta p_n\|_\infty\le\Lambda_n\varepsilon.

因此,在最大范数下,勒贝格常数充当了从数据值到插值函数这一映射的绝对条件数。

它还将插值与最佳逼近联系起来。若

En(f)=inf⁡deg⁡q≤n∥f−q∥∞,E_n(f)=\inf_{\deg q\le n}\|f-q\|_\infty,

则

∥f−pn∥∞≤(1+Λn)En(f).\|f-p_n\|_\infty \le(1+\Lambda_n)E_n(f).

对于切比雪夫节点,Λn\Lambda_n 随 nn 仅呈对数增长;对于等距节点,它则呈指数增长。

必须区分问题的条件性与算法的稳定性。稳定的实现可以限制浮点运算带来的额外误差,却无法消除所选节点固有的误差放大效应。反过来,即使采用其他表示形式能够准确计算插值多项式的值,求取其单项式系数的问题仍可能是严重病态的。

在节点覆盖范围之外求值称为外推。在这个区域内,插值基多项式及相应的敏感性可能迅速增大。

相关方法与推广

分段多项式插值。 这种方法不是在整个区间上拟合一个多项式,而是在各个子区间上拟合低次多项式。样条插值在各段的连接处施加连续性条件。它通常能够避免高次全局插值在端点附近的振荡,不过,数据影响的局部性取决于样条的具体构造。

埃尔米特插值。 埃尔米特插值不仅指定函数值,还指定导数值。在标准的一元构造中,若在互异节点处指定从零阶开始的各阶连续导数,总计 mm 个条件就能唯一确定一个次数不超过 m−1m-1 的多项式。在单个点处对函数及其前 nn 阶导数进行插值,得到的就是该函数的 nn 次泰勒级数截断多项式。

最小二乘逼近。 插值要求在数据点处精确吻合。最小二乘法则通过最小化总体残差来进行逼近,不要求经过每一个观测点。对于含噪数据,精确插值可能会再现不需要的波动;平滑和正则化会修改拟合问题,而不是求解原来的插值条件。

多元插值。 在多个变量的情形下,仅凭点的数目无法保证唯一性,点的几何分布也很重要。例如,在二元情形下,三个点只有在不共线时才能唯一确定一个仿射多项式。张量积网格和单纯形上的插值提供了结构化的构造方式。

应用

多项式插值为多种计算方法提供了共同基础:

  • 数值积分: 对拉格朗日表示式积分,可以得到求积公式。等距节点导出牛顿–柯特斯公式;特别选取的节点则产生其他公式族,它们具有不同的精度与稳定性。
  • 数值微分: 对插值多项式求导,可以从采样值获得导数的近似值,并能系统地推导有限差分权重。
  • 微分方程: 配点法和谱方法用多项式表示近似解,并要求在选定的点处满足所研究的方程。
  • 有限元: 有限元法中的多项式形函数用于在各个网格单元内对局部自由度进行插值。
  • 代数重构: 有限域上的插值可根据精确采样值重构多项式,也是纠错码和秘密共享中相关构造的基础。

在上述每一种应用中,多项式次数、节点分布、数据精度和表示形式,共同决定了插值能否成为可靠的计算基础。