为什么使用网格?
单一高次多项式会把所有样本联系到整个区间:新增一点便可能改变各处的插值,而且节点选得不好时,提高次数未必提高准确度。另一种简单做法是用直线连接相邻样本。这会牺牲节点处的平滑斜率,却令每个值只依赖左右两个相邻观测,尤其适合本来就不等距的样本。
以下组合所给样本时假设使用精确算术;量度误差与浮点运算是不同问题。
定义与局部权重
定义 5.3.1
(网格上的分段线性插值)
设 ,。给定数据 ,在 上定义
在共同节点,两侧公式都给出 ,所以 连续。每个区间内部的斜率为 。区间内两个权重非负且总和为一,故插值介于两端数据之间,数据为负亦然。这不代表插值在节点可微:两边斜率可以不同。
若 ,记插值为 ,并令 。下标描述整个划分,并不要求等距。
定理 5.3.2
(不等距网格上的误差与敏感度)
若 ,,则对 ,
在区间内部,
若每个给定样本与 相差不超过 ,所得插值 满足
导数估计只用于区间内部;插值在节点未必有导数。 时,上述近似误差均为零。
证明:两种不同误差
证明
(余项、平均斜率与凸数据权重)
对区间内部的 ,两点插值余项给出
其中 。证明是减去适当倍数的 ,使辅助函数多一个零点,再两次应用罗尔(Rolle)定理。端点的误差为零。到两端的非负距离之乘积最多为 ,便得到第一个界。
斜率方面,微积分基本定理给出
由 ,在 处分开积分,便得到上述导数界。两端距离的平方和最多为 ,故可进一步界定为 。这论证也适用于节点处的单侧斜率极限;若左右斜率不同,不能因此说节点有导数。
最后,设样本误差为 。在每段上,含误差插值与精确数据插值之差,是 的同一凸组合,绝对值最多为 。利用三角不等式便可把数据误差加到近似误差界。所有误差都等于 时常数一可以达到;若数据质量不变,增加节点不会降低这种最坏情况的误差界。
证明透视
为什么函数值与斜率的收敛阶不同
证明以两种不同方式使用 。函数值方面,罗尔定理在同一段内应用两次,所以只涉及该段上的 ;因子 是两个距离之积, 正由此而来。斜率方面,关键一步是把段上斜率写成 在该段的平均值。于是斜率误差是 的平均, 只作为 的 Lipschitz 常数出现:一个距离,一次 。
数据项依赖第三个事实:函数值权重非负且总和为一,所以样本误差只会被平均,不会被放大。数据斜率却是权重为 的差商,没有这个性质。这正是导数界需要精确样本的原因,也是下面交替误差反例成立的原因。最后由三角不等式把两部分相加,论证闭合。
例子:不等距划分
例题 5.3.3
(插值一个二次函数)
取 ,节点为 。在 上插值为 ,在 上则为 。于 ,插值为 ,真值为 。此处 、,局部函数值误差界 恰好达到。节点 的左、右斜率分别为 和 ;虽然原函数平滑,插值却有折角。
在 ,斜率误差为 。当点从第二段内部趋向左端时,斜率误差趋向 ,即上界 。因此这两个常数作为这些假设下的一致界都是锐利的,尽管斜率误差的上确界可出现在单侧端点极限。
例题 5.3.4
(带噪声样本的线性函数)
设 上 ,节点为 ,记录所得样本为 ,即误差 。这是 的边界情形:若数据精确,插值就等于 。因此函数值误差界只剩数据项 。第一段的斜率为 ,插值为 ,误差 留在 内。斜率误差为 ,是这个数据扰动所容许的最大值。样本本身已含的误差,任何网格细分都无法消除。
例题 5.3.5
(为容许误差选择等距网格)
要在 上以精确样本插值 ,并使一致误差不超过 ,取 。定理要求 ,即
所以 个等距段已足够: 给出 ,而 给出约 ,不合要求。证明只在每段内使用 ,因此 可换成该段的最大值 。在 附近这个最大值接近一,不等距网格在那里可用长至约 的段。
对插值积分
逐段积分得到不等距复合梯形公式
命题 5.3.6
(不等距复合梯形公式的误差)
若 ,,且 ,则
若改为对每个 都有 ,右方最多再增加 。
证明
(积分逐点余项界)
对精确样本,可直接积分逐点误差界,而非把最大值乘以段长。令 ,
若 ,由于积分权重非负且总和为 ,还需加上最多 。
这些都是绝对最坏情况估计;两个网格所得结果接近,单凭此不能认证误差。
反例模式
函数值近似良好,斜率不一定良好
在 取 ,等距网格步长为 ,精确样本交替受到 扰动。整个插值与零的距离仍不超过 ,但每段斜率的绝对值均为 。固定 而细分网格,导数误差反而增加。必须同时考虑样本精度和网格大小;上面的导数定理假设样本精确。
常见错误
常见错误
(在不等距网格的误差界中使用平均步长)
函数值误差界由最宽的一段决定,而非 。对节点 上的 ,平均步长 会给出 ,但 的误差却是 。应使用 ,或更好的逐段界 。
常见错误
(在节点为插值指定导数)
插值在每个节点连续,但通常有两个不同的单侧斜率。在二次函数的例子中, 处的斜率分别为 和 ,所以 不存在。导数估计是开区间段上的结论;在节点只能报告单侧极限。
练习
快速检查
(对 上的 ,取节点 。计算 的插值、实际误差及局部定理界。)
先找出包含 的一段。
解答 · 答案
第二段端点的值为 和 。从 到 占段长的 ,所以插值为 ,误差为 。代入 ,逐点界为 ,全段界为 。
快速检查
(同一函数以 为节点。计算 上复合梯形近似,并与精确积分和立方和误差界比较。)
两段的长度分别为一和二。
解答 · 答案
公式给出 。精确积分为 ,误差为 。取 ,误差界 ,在此恰好达到。
快速检查
(设 上 ,样本误差最多 ,。求一致函数值误差界;能否认证误差小于 ?)
把近似项与数据项相加。
解答 · 答案
误差界为 ,不能认证小于 。这只是上界,并不证明实际误差超过该门槛。
快速检查
(每个节点误差最多为 。求长度 的一段上斜率扰动界,并说明它可以达到。)
一段的斜率是两个样本的差商。
解答 · 答案
含误差斜率与精确数据斜率之差为 ,绝对值最多 。取 、 即可达到。