动机
仪器只在若干时刻测量数值,我们却可能想知道两次测量之间的函数值、某一瞬间的变化率,或整段时间的累积量。插值、数值微分及求积分别处理这三个问题,背后有共同做法:先用简单函数拟合采样值,再对这个函数求值、微分或积分。这个观点既解释公式,也提醒我们公式能保证什么。
完全通过采样点,不代表在点与点之间准确;无数光滑函数都可拟合同一组有限数据。因此,误差保证需要额外假设,例如未知函数的某阶导数有已知上界。以下分开研究以近似函数代替原函数的误差,以及输入采样值的扰动。计算机运算的舍入还可带来第三种误差,不能自动算进前两项。
定义
定义 4.1.1
(插值多项式与 Lagrange 基底)
设 是互异实数节点, 是输入值。以 表示次数不超过 的多项式空间,包括零多项式。插值多项式满足每个条件 。Lagrange 基底及相应构造为
空乘积定义为一,因此 也适用。互异节点保证分母非零。当 时 ,否则为零,故公式拟合全部数据。对常数函数插值又得 。但系数可以为负,所以这未必是凸组合。
定义 4.1.2
(中心差分)
若 ,两个采样点给出中心差分
即通过两个采样点的直线斜率。
定义 4.1.3
(复合梯形公式)
在 上令 、整数 、、,复合梯形公式定义为
它是连续分段线性插值函数的积分。内部节点由左右两段共用,因此合计得到完整权重。这些定义都指对输入值作精确算术。
表示函数至第 阶的导数连续,端点导数由内部连续延伸。最高阶导数的绝对值因此在紧致区间有有限最大值,但如何找到实用的数值上界,仍须另作分析,不能仅从采样表读出。
定理 / 命题
定理 4.1.4
(插值的唯一性与余项)
互异节点的任意数据恰有一个 插值。若数据为 ,且 ,其中区间包含全部节点及求值点 ,则当 不是节点时,在这些点的最小值与最大值之间存在 ,使
在节点误差为零。若整段区间上 ,则绝对误差不超过 。
命题 4.1.5
(数据敏感度与两个离散化误差界)
若采样值的变化为 ,且 ,相应插值多项式满足
若 且 ,则
若 且 ,则
光滑性及导数上界必须在所述整段区间成立,不能只检查节点。若已知上界只适用于节点所覆盖的区间,便不能直接用于区间外的外推。
概念视角结构
同一组数据,不同的线性泛函
固定目标后,三种公式都是采样值的加权和。插值求值的权重为 ,中心微分为 ,梯形积分则有总和等于区间长度的非负权重。各输入值的绝对误差分别不超过 时,权重绝对值之和决定最坏放大倍数,解释了重建导数为何可能远比积分敏感。
证明思路或证明
多加一个零点,得到插值余项
证明
(唯一性与插值余项)
Lagrange 公式已证明存在性。若有两个插值多项式,两者之差次数不超过 ,却有 个互异零点。非零多项式不可能如此,故两者相等。
固定不是节点的 ,令 ,并考虑
它在全部节点及 都为零,共有 个互异零点。依大小排列后,Rolle 定理在每对相邻零点之间各给出一个 的零点,共 个。再对这些导数零点应用同一论证, 至少有 个零点。如此反复, 在原来两端极值之间至少有一个零点 。由于 ,而 是 次首一多项式,
代回 即得余项。在节点直接用插值条件,不能除以零值 。
证明透视
额外零点如何把未知误差转为导数
选择 的目的,是在插值已有的 个零点之外多加一点。反复 Rolle 恰好到达第 阶:插值多项式消失,首一乘积则变成已知常数 。所得 随求值点而变,并非对每个 都共用同一点。
输入数据的扰动
证明
(插值对数据的敏感度)
线性关系给出 ,三角不等式遂给出所述上界。对固定 ,将每个非零系数的误差选为 ,便可取到 。这是各项绝对误差受限时可达到的最坏情况,不是随机误差总会同向累加的断言。合并两种误差得
中心差分的误差平衡
证明
(中心差分的二阶截断误差)
在 展开 Taylor 公式,分别有
相减后除以 ,偶次项消去,留下
两个余项点不必相同,但各导数的绝对值均不超过 ,故得 。若两个输入值各有不超过 的绝对误差,差分值另有最多 的变化。因此,对不确定采样值精确计算时,
前项随步长缩小而减少,后项却增加。当 ,在所有正步长中令此上界最小,得到 ;还须确认步长留在光滑性假设的区间内。这只是最小化已证明的上界,不一定最小化实际误差。公式亦未计入形成 、函数求值、相减及相除时的舍入;分析完整硬件算法须另行说明这些运算。
梯形公式为何出现十二
证明
(逐段估计梯形公式误差)
在长度为 的一段 ,令 通过两个端点值。线性插值余项给出
故 。积分此不等式,不能把未知的 当常数提出:
将 段相加便得 。若 ,由 可知 ,故凸函数的梯形估计偏大。
所有梯形权重非负,总和为 。每个采样值的绝对误差若不超过 ,积分估计的变化便不超过 ,此数据模型下与 无关。这里各项分别受限不表示概率上的独立:允许任何符号及相依关系。增加分段数可减少截断误差上界,却不减少这个最坏数据界。要利用统计抵消,必须另加测量模型;同一内部节点始终是两段共用的一个输入值。即使权重非负,浮点求和仍可能另有误差。
例题详解
例题 4.1.6
(二次函数的求值与噪声放大)
在 对 采样,得到 。在 ,
所以 。唯一性也保证这个结果,因为 。但 ,若三个值的误差为 ,答案会偏移 。求值点位于节点区间内,仍不能保证全部权重非负。
例题 4.1.7
(在零附近对正弦函数作差分)
对 ,有 及 。由 ,截断误差不超过 。当 ,上界是 ,实际误差约为 。若每个输入值有 的绝对不确定性,上界另加 。改用 ,截断界虽降至约 ,数据项却升至 ;步长变小可以削弱整体保证。
例题 4.1.8
(达到梯形误差上界的例子)
对 上的 ,取 、,
精确积分是 ,故偏大 。定理中 ,上界恰为 ,等号成立。若三个采样值各有至多 的误差,权重 给出至多 的数据误差;精确算术下总保证为 。
常见错误
反例模式
更小步长可以放大微分噪声
“减小 必定改善数值导数”即使对真函数 也不成立。输入允许的值 、,中心差分便是 ,但真导数和截断误差皆为零。固定 时,此值随 无界增长。正确说法是:缩小步长可减少光滑函数的截断上界,但数据不确定性仍要独立分析。
常见错误
(以为次数越高必定越准)
提高插值次数并没有无条件的准确度保证。余项涉及更高阶的导数上界 及另一个节点乘积 ,数据敏感度 也可能增大。精确插值带噪声的数据只会重现噪声,并不能去噪。
常见错误
(把余项中的点当作常数)
插值余项中的 以未指明的方式依赖 。把余项公式当作 固定来求导,并无依据。因此中心差分的误差直接由 Taylor 公式推出,而不是由插值余项求导得来。
总结
插值在指定多项式空间内唯一,但逼近未知函数的准确度需要光滑性信息。反复 Rolle 给出余项,Lagrange 权重的绝对值总和则衡量采样敏感度。中心差分同时有 截断界及 数据项。复合梯形公式有 全局界,对凸函数偏大,非负权重也保留简单的数据误差界。每个结论均须连同其假设及误差模型理解。
练习
快速检查
(在节点 插值数据 ,求 的值。若各值的绝对误差至多 ,求可达到的最坏不确定性界。若数据是 上满足 的精确采样,再求该点的近似误差界。)
把插值多项式写成 ,并用 的余项。
解答 · 答案
,故 。权重为 ,绝对值总和为一,所以数据界是 ;两个误差皆取 即达到。余项界为 。若两种不确定性并存,合并界为 。
快速检查
(对 计算 及误差。它是否达到 的上界?加上采样误差至多 的项,当 时在 中最小化此上界。)
展开两个立方, 的偶次项会消去。
解答 · 答案
展开得 ,故 ,误差恰为 。合并上界是 ,其导数为 ,在 为零,且由负转正。上界在正半轴两端皆趋于无穷,故这是最小值点。若采样区间受限,还须检查此步长是否可用。
快速检查
(对 上的 ,分别用 计算 、误差及误差比。若 ,利用定理保证截断误差不超过 的最小正整数 是多少?)
在梯形公式误差界中代入 。
解答 · 答案
、,减去 得偏大误差 ,前者是后者四倍。要求 ,即 ,最小整数为 。此例恰好达到界,但其他函数未必如此。
快速检查
( 及 在节点 的采样均为零。比较两者在 的值及在 的积分,说明当 改变时,单凭采样不能给出一致的插值或积分误差界。)
先计算 ,再比较导数上界。
解答 · 答案
在 ,两函数值为 ;积分则为 。同一组零数据可对应随 任意增大的答案差。每个 都光滑,但 并无一致上界。若另给共同导数界,便能限制 并恢复误差保证;只有光滑性而无定量界仍不够。