误差估计不自动成为证明
自适应求积程序常比较粗网格与细网格的结果。两者接近是有用的信息,但取样点可能漏掉窄峰或振荡。若要得到严格保证,必须有某个条件限制样本之间的函数行为。这里使用的条件是每个子区间上的二阶导数已有经过证明的界。
定义 7.4.1
(中点保证所需的数据)
设 且 。取分割 ,记 、。保证所需的数据包括:
- 已知 ,使整个 上都有 ;
- 对每个中点,有计算区间 确实包含精确值 。
这些数据可以来自解析不等式或严格舍入的区间计算;一般来说,只在中点计算一次 并不能证明整个区间的界。
定理 7.4.2
(有保证的积分区间)
在上述假设下,
若要把该区间作为计算机证明,分割位置、精确中点、取样区间及区间端点运算都必须精确表示,或用向外舍入包围;特别是取样区间必须包含证明所用精确中点的函数值。
证明
(Taylor 余项与关于中点的对称性)
当 位于第 个子区间时,Taylor 定理及余项界给出
积分后,线性项因对称性消失,并且
因为 ,用中点值的下界或上界替换 时,分别保持相应的不等式。对所有子区间求和,就得到 (1)。
证明透视
保证来自哪里?
这里有两种不同的不确定性:中点函数值位于计算区间内,而曲率界控制未取样的图像。式 (1) 把两者结合。仅用区间计算包住取样值,不能控制取样点之间的变化;仅有导数界而没有安全舍入,也不能保证浮点端点正确。
常见错误
(每个区间只在一点取样 )
中点处的 值可能很小,而 在区间内其他位置却大得多。 必须在整个区间上界定 ,依靠解析不等式或 在该区间上的区间包围。单个取样只给出估计,而不是保证。
一个计算与加密网格的作用
例题 7.4.3
(二次函数:一段与两段)
对 上的 ,精确中点函数值为 ,而 。只用一个区间得到
等分成两段时,中点和为 ;由 (1) 得 ,包围区间缩为 。真实积分是 。此处上端恰好达到真实值,是这个凸二次函数的特殊性质;(1) 则不需要预先知道 的符号。
命题 7.4.4
(包围区间的宽度)
若所有 ,记 ,则
如果取样本身也是区间,(1) 的宽度为
特别地,若每个中点区间宽度至多为 ,总宽度至多为 。
证明
(把各区间的宽度相加)
。(1) 的上端减下端为 。由 及 ,它至多为 ,而 (2) 把 界为 。
因此在精确取样、整个分割序列共用同一个上界 时,只要最大网格宽度趋于零,包围区间的宽度 就趋于零。 的连续性保证理论上存在有限全局界,但数值方法必须实际给出一致有界且有效的 。加密网格只能控制 (3) 的第二项。若要求达到指定宽度,取样区间和算术运算也必须足够精确。自适应算法可以按各项经过验证的贡献 决定要细分哪些子区间,但细分后必须重新计算或保留有效的导数界;子区间中点则是新的取样位置。若要由 (2) 保证终止,还需要细分确实使 ,并能把取样和算术不确定性降到足够小。固定精度可能带来无法通过加密网格消除的正误差下限。
例题 7.4.5
(四个区间上的正弦积分)
取 上的 ,,分成四个等长区间,。精确中点值 约为 ,和约为 。中点和为 ,。包围区间约为 ,包含精确值 。只用一个区间时,区间宽得多:。
例题 7.4.6
(零曲率与区间取样)
对 上的线性函数 ,只用一个区间, 是有效的界,所以 。精确中点值为 ,包围区间为 ,与 吻合。若取样只知道位于 ,则 (3) 给出宽度 ,包围区间为 。其余的宽度全部来自取样区间,而不是曲率。
反例模式
误差估计为零,积分仍可能为正
在 上令
单区间 Simpson 公式和分成两半的 Simpson 公式,其全部取样点都属于 ,所以结果都为零。两者之差是零,但 连续、非负,且在这五点以外为正,因此 。事实上其积分为 。若没有关于被积函数的额外信息,两个公式一致不能证明误差很小。
这个限制并非 Simpson 公式独有。对任意固定有限取样点,把对应一次因子相乘后再平方,就得到一个光滑非负函数:它在全部取样点为零,积分却为正。即使只使用点值的确定性自适应算法在零函数上经过有限次取样后停止,相应乘积函数的任意正常数倍在这些点也给出同样的零值,因此算法会走同一条取样路径。放大系数能使该乘积函数的正积分任意大;若不限制函数类别,任何固定有限宽度的区间都不能同时对两者有效。
常见错误
(把端点舍入到最近值)
用普通的就近舍入来计算端点,所得保证可能差一个末位单位:下端可能向上舍入,或上端向下舍入,存储的区间便不再包含精确的包围区间。应按定理要求,下端向下舍入、上端向上舍入。
练习与解答
快速检查
(在 上对 使用一个区间、精确中点值和 ,应用 (1)。)
解答 · 答案
中点公式为 ,,故区间为 。
快速检查
(在 上对 使用 个等长区间和精确中点值,给出保证区间宽度的上界。)
解答 · 答案
、;由 (2),。
快速检查
(对 的分割,若每个中点计算区间宽度为 ,取样区间对 (3) 的贡献是多少?)
解答 · 答案
若各区间宽度都恰为该值,贡献为 ;若只是至多为该值,这就是上界。
快速检查
(为什么每个区间只取样一次 ,本身不能证明 是有效上界?)
解答 · 答案
连续二阶导数在取样点可以很小,而在区间其他位置更大。
快速检查
(如果粗、细 Simpson 公式的结果一致到机器精度,还需什么信息才能得到严格包围区间?)
解答 · 答案
例如,若每个区间的导数界经过验证,取样值得到严格包围,且算术向外舍入,就可用 (1) 给出中点求积的严格区间;两次计算一致本身不能提供这些界。