插值是指构造一个函数,使其在指定点处取给定的值。给定观测数据 ,插值函数 在每个数据点处都满足 。随后便可用它求取其他自变量处的函数值,这些自变量通常位于观测数据覆盖的区域内。插值是数值分析、科学计算、几何建模和采样信号重建的基础。
仅凭数据通常无法唯一确定一个函数:有无穷多条曲线可以通过有限个点。因此,插值方法还需要指定一类可用的函数,例如次数有上界的多项式、分段多项式或径向核函数的组合。插值方法是否有效,取决于所选函数类能否反映实际问题的特性、采样点的分布,以及计算所得函数的精确程度。
插值不同于允许在观测点处存在偏差的拟合方法,也不同于在数据所约束的区域之外求取模型值的外推。函数在采样点处与数据完全吻合只是一种代数性质,并不保证采样点之间的结果准确。插值的核心问题包括解的存在性与唯一性、逼近误差、对数据的敏感性、计算成本,以及能否保持单调性或周期性等相关特征。
数学表述与唯一性
对于互不相同的实数节点 和给定值 ,基本的插值问题是在选定的空间 中寻找函数 ,使其满足
节点不必等距分布,给定值可以是实数、复数或向量。在多变量情形下,每个节点是某个区域中的一个点,而非直线上的一个位置。更一般的插值条件不仅可以指定函数值,还可以指定导数、平均值或其他线性测量值。
当 是以 为基的有限维向量空间时,可写成
插值条件便转化为一个线性方程组:
对于每一个数据向量,插值函数存在且唯一,当且仅当求值矩阵 可逆。函数空间与采样条件的这一性质称为唯一可解性。在这种方阵形式下,系数个数与条件个数相同是必要条件,但仅凭这一点并不能保证唯一性。
例如,次数不超过 的多项式所构成的空间维数为 ,互不相同的一维节点能保证该空间中的插值问题唯一可解。如果两个这样的多项式对同一组数据进行插值,那么它们的差有 个互不相同的零点,而次数至多为 ,因此这个差必定恒为零。反之,若不加其他限制,有限个函数值无法唯一确定一个连续函数。如果 是这组数据的插值函数,那么对于任意连续函数 ,
也同样是这组数据的插值函数。
因此,插值是一种带约束的函数逼近。当数据来自未知函数 时,通常希望 在整个定义域内都接近 ,而不只是在节点处与之相等。节点处的精确匹配提供了约束,而光滑性、局部性或最小能量原理则提供了额外的结构。
一个简单的例子可以说明为何空间的选择很重要。点 和 确定了线性插值函数 。但对于任意常数 ,这两个点也都在曲线 上。在 处,这些曲线的函数值为 ,可以任意大或任意小。如果没有进一步的假设,仅凭这两个样本无法为中间位置的函数值确定任何界限。
多项式插值与导数约束
对于 个互不相同的节点,次数不超过 的插值多项式 可以写成拉格朗日形式:
每个基多项式 在 处的值为一,在其余所有节点处的值均为零。因此,这个公式直接证明了插值多项式的存在性。它还表明,插值对数据具有线性性:对两组数据的线性组合进行插值,得到的结果等于这两组数据各自的插值函数的同一线性组合。
牛顿形式以另一种方式组织同一个多项式:
其中 ,差商递归定义为
当节点逐个加入时,这种表示尤其方便:已有各项保持不变,只需增加一项即可扩充插值多项式。采用嵌套乘法,无须将多项式展开为 的幂次形式,就能计算其值。
对于等距节点 ,牛顿公式也可以用前向差分来表示。若 ,则
这种与有限差分法的联系,曾是利用印刷数值表进行插值的核心。它也解释了为什么可以利用插值多项式推导数值微分和数值积分公式。
埃尔米特插值在函数值之外还引入导数信息。如果在 个互不相同的节点处都给定 及其一阶导数的值,那么存在唯一一个次数不超过 的多项式,满足这 个条件。更一般地,若在节点 处给定直至 阶的各阶导数值,就得到 个条件,并确定一个次数小于该条件总数的多项式。将零点按重数计数,即可证明唯一性。
泰勒级数的截断多项式是一种特殊情形,其中所有导数条件都集中在同一点。埃尔米特插值则将这类信息分布在多个点上。在一个区间内,两个端点处的函数值和一阶导数值可以确定一个三次多项式。这种三次埃尔米特构造在轨迹设计、微分方程的数值求解,以及必须同时满足位置和切线条件的分段曲线中都很重要。
逼近误差与节点的选取
设 在包含各节点和求值点 的某个区间上具有 阶连续导数。多项式插值的余项为
其中 是该区间内的某一点。这个公式可通过反复应用罗尔定理得到,而罗尔定理是中值定理的一个推论。该公式将误差的两个来源区分开来:函数导数的性态与插值节点的几何分布。
这一余项公式并不意味着提高次数总能改善逼近效果。高阶导数和节点乘积都可能迅速增大。经典的龙格现象出现在以下情形:对函数
在 上逐渐加密的等距网格上进行插值。所得多项式在端点附近的振荡越来越剧烈,其最大误差并不趋于零。这是插值序列本身不收敛,而不仅仅是某种具体实现方式的问题。
节点的选取可以显著改变结果。由
定义的切比雪夫多项式 的根为
这些节点在区间端点附近较为密集。相应的首一节点多项式为 ,它在 上的最大绝对值为 。在所有 次首一多项式中,它在该区间上的最大绝对值最小。与之相关的、包含端点的切比雪夫网格也得到了广泛应用。
对于在某个区间的足够大的复邻域内解析的函数,采用切比雪夫型节点的插值可随着次数增加而按几何速度收敛。即使只在实数自变量处求值,所能达到的收敛速度仍由复奇点的位置决定。对于光滑性有限的函数,收敛通常较慢,且往往仅以多项式次数的某个负幂速度收敛。
一种更一般的误差估计将插值与最佳多项式逼近进行比较。若 为插值算子, 为它在最大范数下的算子范数,则
这将插值与逼近论联系起来,同时揭示了稳定性的重要性。魏尔斯特拉斯逼近定理保证,紧区间上的每个连续函数都可以用多项式以任意高的精度逼近。但它并不保证在任意预先指定的节点序列上构造的插值多项式会收敛。
条件性与可靠的数值求值
插值涉及两个不同的数值问题:数学结果对数据变化有多敏感,以及计算过程会引入多少额外误差。二者分别对应条件性与数值稳定性。稳定的实现无法消除病态插值问题本身的敏感性。
对于多项式插值,函数值中的扰动 会产生
因此,
括号内的表达式称为勒贝格函数;它在区间上的最大值称为勒贝格常数 。它衡量采样值中的误差在最坏情况下的绝对放大倍数。对于等距节点,它随多项式次数呈指数增长;而对于标准切比雪夫节点,它仅呈对数增长。
用单项式表示插值多项式会得到一个范德蒙德矩阵,
这类矩阵可能严重病态,尤其是在多项式次数较高或节点尺度选择不当时。因此,在浮点运算中求解单项式系数可能会损失大量精度。这并不意味着插值多项式在每一点的值都同样不准确:即使用更合适的基进行求值时表现良好,系数表示本身仍可能存在问题。
重心公式通常可以避免显式构造系数。定义
则在非节点处,
在节点处,直接返回该节点的插值值。将所有权重乘以同一个非零常数不会改变结果,因此可以据此对权重进行适当的尺度调整。权重计算完成后,每次求值所需的算术运算次数与节点数成正比。
标准切比雪夫网格具有简单的显式重心权重,无须将大量节点差相乘,从而避免这一过程可能带来的问题。对于任意节点,构造权重时需要注意上溢、下溢和尺度调整。稳定性还取决于求值区域:在节点区间内进行插值时有效的公式,用于外推时可能表现差得多。
对节点位置的敏感性与对函数值的敏感性是两个不同的问题。节点间距过小、坐标存在不确定性以及导数估计,都可能放大位置误差。通过仿射变换将节点缩放到尺度适中的区间,有助于数值表示,但既不能恢复观测中缺失的信息,也不能消除问题固有的病态性。
分段插值与样条
分段插值不在整个区间上使用一个高次多项式,而是在各个子区间上分别使用低次多项式。给定按顺序排列的节点 ,分段线性插值为
其中 。这些权重非负且和为一,因此每个插值都是相邻两个数据值的凸组合,不会超出这两个值所界定的范围。
分段线性插值函数连续,但其一阶导数通常存在跳跃。若 的二阶导数有界,则
因此,将所有子区间的宽度减半,就能使这一误差上界降至原来的四分之一。与等距节点上的全局多项式插值不同,细化分段并不需要提高局部多项式的次数。
样条将各段多项式连接起来,并使其在结点处满足指定的光滑性要求。三次样条在每个区间上都是三次多项式,且通常在内部结点处具有连续的一阶和二阶导数。仅凭节点处的插值条件,还不足以确定三次样条;还需补充端点条件或周期条件,才能使问题完整。自然边界条件规定 。夹持边界条件给定端点处的斜率。非结点条件则要求前两段属于同一个三次多项式,后两段也属于同一个三次多项式。
记 ,则内部节点处的方程为
这些方程与适当的端点方程共同构成一个窄带线性方程组,可在线性时间内求解。对于足够光滑的函数,若端点条件相容,三次样条插值在最大范数下可达到四阶精度。端点条件不匹配可能使精度阶降低。
自然三次样条具有变分刻画:在所有通过给定数据点且具有足够正则性的函数中,它使下式达到最小:
这一积分衡量的是弯曲程度,而非统计误差。然而,光滑性本身并不能保证保形性。即使数据为正或具有单调性,三次样条也可能出现过冲。分段三次埃尔米特方法通过选取满足局部不等式约束的节点斜率来解决这一问题。这类方法通常保留一阶导数的连续性,同时舍弃二阶导数的连续性,体现了光滑性与保持观测数据形状之间的权衡。
有理插值与局部函数模型
有理插值寻求如下形式的插值函数:
其中, 和 是具有指定次数上限的多项式。有理函数可以用比多项式简洁得多的形式表示极点和剧烈变化。例如, 在高次等距节点多项式插值中会带来问题,但它本身就是一个分子次数为零、分母次数为二的有理函数。
若 且 ,则分子与分母的系数存在整体缩放的冗余。因此,一般的插值问题使用 个函数值条件。方程
关于这些系数是线性的。然而,这些方程的非零解并不一定给出有效的插值函数:分母不能在数据节点处为零,除非可以约去公因子,且约分后在该节点的值满足插值条件。次数退化和特殊数据会使存在性与唯一性问题变得复杂。
极点既是优势,也是隐患。它们使有理函数能够忠实地表示附近存在奇点的函数,但插值区间内也可能出现不希望有的极点。分子和分母还可能出现几乎相互抵消的零点,形成看似无害、却在数值上十分敏感的特征。因此,评估有理插值函数时,不能只检查它在数据节点处的残差。
重心有理插值写作
其形式与重心多项式插值相同,但采用更一般的权重时,得到的通常是有理函数,而非多项式。只要每个权重都非零,在节点 处的极限值就是 。2007 年提出的 Floater–Hormann 插值将局部多项式插值函数混合起来;对于按大小排列的互异实节点,在其标准允许参数范围内,所得插值函数在实轴上没有极点。
有理插值与帕德逼近既有联系,又有区别。帕德逼近匹配局部幂级数的系数,而普通的多点有理插值匹配不同自变量处的函数值。两者都利用分子和分母的次数,刻画多项式可能难以高效表示的行为。
这些方法在频率响应建模以及逼近附近存在复奇点的函数时十分重要。其灵活性也带来了额外的模型选择:如何分配分子与分母的次数、如何限制极点,以及如何处理近乎抵消的情形。仅靠精确插值并不能解决这些选择问题,尤其是在观测数据含有噪声时。
周期插值与采样信号
对于周期函数,三角多项式通常比普通多项式更自然。在 -周期域上,复三角插值函数的形式为
其中 是由 个连续整数频率组成的集合。在 个等距节点 上,系数可由离散傅里叶变换求得:
快速傅里叶变换可用 次运算计算这些系数。
当 为奇数时,选取频率 可得到特别对称的表示。当 为偶数时,最高可分辨频率,即奈奎斯特频率,需要采用特定约定,因为其正频率与负频率对应的样本完全相同。对于实数数据,只要一致地处理频率约定,系数的共轭对称性就能使插值函数取实数值。
均匀采样无法区分所有频率。在这些节点上,对任意整数 ,都有
这就是混叠:不同的连续振荡会产生完全相同的采样数据。三角插值从每一类无法区分的频率中选取一个代表;仅凭样本,无法判定原信号中究竟存在哪些更高频率的分量。
采样定理在更强的假设下给出了精确重建的结果。如果信号不含角频率超过 的分量,且采样间隔 满足 ,则理想化的重建公式为
其中 。具体的收敛方式由适当的函数空间假设确定。与有限数据的多项式插值不同,这一结果使用无穷样本序列,并对信号的频率作出全局限制。
对于有限长度的记录,需要进行截断、加窗或周期延拓。如果将非周期记录视为周期记录,其两端的值不匹配就会人为造成不连续。由此得到的傅里叶逼近可能在接合处附近出现持续振荡。光滑周期函数的表现则好得多:足够光滑的函数,其系数会迅速衰减;在实轴周围某个带状区域内解析的周期函数,则可达到几何收敛。
在数字重采样中,有限长插值滤波器用于近似理想的 sinc 重建。插值核的频率响应会影响模糊、振铃以及对不需要的频率分量的衰减。降采样还需要抑制超过新奈奎斯特频率上限的分量;仅对现有样本进行插值并不能防止混叠。
多维插值
多元插值将标量节点替换为点 。此时,几何结构起着核心作用。在一维情形中,互不相同的节点能够唯一确定一个次数适当的多项式。在多维情形中,仅有节点互异且数量适当这两个条件还不够。 个变量、总次数不超过 的多项式所构成的空间,其维数为
但这些点的位置还必须满足一个条件:该空间中不存在在所有这些点上取值均为零的非零多项式。
例如,仿射函数 可由其在平面上三个不共线点处的值确定。三个共线点则无法唯一确定这个函数,因为缺少横向的信息。这种几何上的失效,表现为求值方程组中矩阵的秩的下降。
在矩形网格上,张量积插值沿各个坐标方向应用一维插值规则。矩形上的双线性插值为
其中, 为归一化坐标。对于每个坐标分别呈线性关系的任意函数,这种插值都能精确重现,包括含有与 成正比的项的函数。因此,它通常不是关于变量对 的仿射函数。双三次插值在每个坐标方向上采用三次多项式,需要额外的采样值或导数估计值。
散乱点需要采用不同的构造方法。德劳内三角剖分将平面点集划分为具有空外接圆性质的三角形。每个三角形上的线性插值采用重心坐标:一个点可表示为三个顶点的加权组合,其插值也以相同的权重对三个顶点的函数值作加权组合。相邻三角形在公共边上的插值相同,从而形成连续的分片仿射曲面,但其梯度通常在跨越边时发生跳变。这类局部形函数是有限元法的核心组成部分。
径向基函数插值则采用
核函数仅取决于到中心点的距离。对于互不相同的节点,有些核函数能产生可逆的插值矩阵;另一些则需要补充多项式 ,并对系数施加附加约束。高斯核、多二次核和薄板样条核是其中的典型例子。具有全局支撑的核函数通常产生稠密方程组,而具有紧支撑的核函数则可以产生稀疏方程组。
高维网格面临维数灾难:在 个坐标方向上各取 个样本,就需要 个点。稀疏网格、低秩表示和自适应采样只有利用额外的结构,才能降低这一成本。几何结构也限制了插值结果的解释:在单纯形内部,重心插值是一个凸组合;而在采样区域之外,同一代数公式就变成了外推,不再具有保持取值范围的性质。
含噪数据、平滑与概率解释
插值将观测值视为精确约束。然而,在许多应用中,数据遵循如下模型:
其中, 表示测量误差。精确的插值函数既会复现潜在信号,也会复现实际出现的误差。这样做是否有用,取决于噪声水平、采样密度、函数类别以及预期的预测任务。
最小二乘法拟合则允许存在残差,并选择使残差平方和最小的函数。对于超定线性模型,拟合值不一定等于观测值。因此,插值与回归采用的是不同的约束,而不只是构造平滑曲线的两种不同叫法。低次拟合多项式即使在训练数据上的残差较大,也可能比高次插值多项式更能抵御测量噪声的影响。
正则化将这种权衡明确地体现出来。三次平滑样条最小化的准则具有如下形式:
第一项衡量与观测值的吻合程度,第二项则对弯曲程度施加惩罚。在标准条件下,当 趋于零时,解趋近于自然三次插值样条。随着 增大,曲率惩罚使解越来越倾向于仿射函数的最小二乘拟合。 的数值尺度取决于该准则所采用的单位和归一化方式。
高斯过程提供了与之对应的概率解释。对于协方差核为 的零均值过程,令 ,且 。当观测无噪声且 可逆时,条件均值为
它对观测值进行插值。其条件方差为
在无噪声模型中,观测节点处的这一方差为零。若存在方差为 的独立观测噪声,则将 替换为 ;此时,条件均值通常起平滑作用,而非进行插值。
因此,同一个核公式既可解释为确定性插值,也可解释为概率模型下的条件均值。概率意义上的不确定性仍以所选的核、噪声假设及其他模型设定为条件;精确插值并不能证明这些假设正确。
在机器学习中,具有足够灵活性的模型都可能对训练数据进行插值,但预测误差却可能相差很大。因此,仅凭训练误差为零,不足以判断模型的泛化能力。交叉验证通过评估模型对未参与拟合的观测数据的预测来衡量预测表现,不过,空间和时间上的依赖关系可能使随机留出的数据点比真正远离已有观测的点或未来的观测值更容易预测。
历史发展与计算应用
插值源于使用数值表的实际需要。天文表和数学表只列出离散自变量处的数值,而计算往往需要其间的数值。线性插值是自然而然的初步方法;更高阶的规则则利用相邻的表列值或差分来刻画曲率。在现代函数记号和逼近理论出现之前,多个数学传统中就已有这类做法。
17 世纪,詹姆斯·格雷戈里和艾萨克·牛顿发展出了涉及差分与差商的系统公式。爱德华·沃林于 1779 年发表了一种形式的多项式插值公式,早于约瑟夫-路易·拉格朗日在 1795 年给出的、如今以拉格朗日之名广为人知的表达式。这些不同形式的公式表示的是同一个唯一确定的多项式,但适用于不同的计算组织方式,也揭示了不同的数学性质。
19 世纪,插值与数学分析、数值求积和多项式逼近建立了密切联系。夏尔·埃尔米特的工作为同时匹配函数值与导数提供了系统框架。卡尔·龙格在 1901 年给出的例子表明,在等距节点上提高多项式次数,可能反而使插值效果变差,这有助于区分函数能否被多项式逼近与某种特定插值方法是否收敛这两个问题。
20 世纪,机械计算和电子计算改变了人们对表示形式的偏好。艾萨克·雅各布·舍恩伯格于 1946 年在数学研究中引入了“样条”一词,其名称源于绘制光滑曲线时使用的柔性绘图条。分段多项式方法兼具局部灵活性与计算效率,而 B 样条表示则提供了具有紧支集、结构良好的基。随后,谱方法、快速变换和核方法进一步拓展了实际可处理的插值问题范围。
插值也是其他数值运算的基础组成部分。对插值多项式积分可得到插值型求积公式。对由区间两端点确定的线性插值多项式积分,可得到梯形公式;对通过两端点及其中点的二次插值多项式积分,则得到辛普森公式。在宽度为 的单个区间上,辛普森近似为
类似地,对插值函数求导可得到数值微分权重,不过与求值或积分相比,求导通常会更显著地放大噪声。
现代应用提出了各不相同的要求。图像放大注重局部性,并控制模糊和振铃;几何设计要求切向连续性或曲率连续性;科学计算中的查表则需要在误差界、存储空间和求值成本之间取得平衡。常微分方程的数值求解器利用插值生成的“稠密输出”,估计已计算时间步之间的解,其中也包括为事件检测提供估计。在基于网格的仿真中,在网格之间传递数值时必须区分插值与守恒:匹配点值未必能保持总质量、总动量或总能量不变,因此,守恒重映射可能转而强制要求网格单元上的积分保持一致。