事件与连续插值
求解微分方程时,我们可能需要知道物体何时到达指定高度。以标量函数 表示条件,真实解 的事件时刻满足 。已接受步的端点通常不会刚好是事件时刻。
定义 2.4.1
(稠密插值与数值事件函数)
已接受步 的稠密插值是定义在 上、在整步内逼近解的函数 ,通常由该步的数据构成。数值事件函数是 ,而数值事件是 的零点。
我们能计算的是 的零点,而非直接计算未知的 的零点。以下假设 及有关区域上的 连续,故 连续。
先检查端点:若 或 ,该端点已是数值事件。否则,端点异号时可以二分。应使用已接受步的插值,而不是把被拒绝的试探步当成数值轨迹。若应用需要区分向上和向下穿越,可记录符号变化的方向。
定理 2.4.2
(二分法的数值事件夹逼)
设 在 连续且 。以精确算术反复取区间中点;若中点是零点则停止,否则保留端点异号的半区间。经过 次未停止的二分后,区间 包含 的一个零点 ,长度为 ;其中点 满足 。
证明
(对保留区间作归纳)
原区间由介值定理包含零点。若中点不为零,它的符号必与原来两个异号端点中的一个相同,故另一半仍然异号。归纳可知每次都保留异号,区间长度每次减半;由连续性及介值定理,新区间仍有零点。中点到该零点不超过半个区间长度。这并不保证零点唯一,也不保证多个事件中找到的是第一个。
证明透视
证明控制了哪一种误差?
上面的论证始终处理 。 的连续性只经由介值定理使用,而符号的记录正是归纳所保持的不变量。缩小夹逼区间,只会使报告的中点靠近 的零点;插值误差及之前累积的数值误差,仍要另行估计,才能判断与真实事件的距离,这正是下一节的内容。
与真实事件比较
以下的条件估计把所需假设明确写出。
命题 2.4.3
(事件时刻的扰动估计)
设 在区间 上连续, 在 内部可微且 ,并且整个 上 。若 、,其中 ,则
证明
(在数值零点使用中值定理)
因为 ,所以 。若 ,无须再证。否则对 之间使用中值定理,得严格介于两者之间的 ,使 ,故 。两个不等式合起来给出 。
假如二分所得夹逼区间包含于 ,其中点 因而满足 。这里已假设真实事件存在,并非从数值异号自动得出。例如,若 上 ,且对所有 及包含两条轨迹的集合中的 有 ,便可取 。当 很小时,事件时刻对扰动很敏感;当真实曲线与零线相切时,导数下界失效,不能套用此线性时间误差界。
算例
例题 2.4.4
(数值零点定位准确,仍可能有偏移)
令 、,事件为 。真实事件是 。假设已接受步 的插值为 ,则 ;这一偏移可代表起始数值已有 的累积误差。先检查端点异号,再计算 、、,依次保留 、、。下一中点 是 的零点,比真实事件早 。此处 且 ,上述误差界恰好取等。
例题 2.4.5
(Euler 步上的阈值事件及可计算的误差界)
取 、,作一个步长 的 Euler 步,得 。它在 上的线性插值是 。对阈值事件 ,得 ,数值事件 ;而 ,真实事件 。两者都在 内,而且是向下穿越。
由 、 开始二分:,保留 ;,保留 。中点 与 相距不超过 。
至于误差估计, 在 上的导数 ,故最大值为 。又 。因此 。实际距离 ,远在界内。此界偏保守,但其中每个常数都由这一步算出。
例题 2.4.6
(端点皆正却藏有两次穿越)
令 ,区间为 。两端点值都是 ,端点测试没有发现任何事件。在中点取样得 ,于是产生两个夹逼区间 与 。先处理较早的区间,其中点给出 ,算法即停于数值事件 ,不必再减半;这正是定理中的停止情形。较后的区间同样给出 。这次额外取样能找到两次穿越,只因取样点恰好落在两者之间。
符号测试会漏掉什么
异号只是充分条件,不是必要条件。例如 在 的端点都为正,却在中间接触零; 的端点也都为正,中间却穿越两次。仅看端点会漏掉这些事件。额外取样或限制步长有帮助,但没有额外假设时,任何固定的有限取样都不能找出所有连续函数的零点。反之,数值插值异号也不保证真实事件落在这一步内。
反例模式
数值有穿越而该步内没有真实穿越
断言:若 在某已接受步上变号,真实事件函数 必在该步内有零点。再取 、、步长 的一个 Euler 步及线性插值 ,但阈值改为 。则 满足 、,二分夹住数值事件 。真实函数 递减,且 ,所以 在整个 上为正;真实事件 位于下一步。修正正是扰动估计的假设:必须先知道真实事件位于该区间内,或把区间扩大至包含它, 才能控制事件时刻误差。
浮点计算应先处理端点为零的情形,直接比较符号而非相乘,以免溢出;达到时间区间允许宽度便停止。如果中点已不能与端点区分,或函数值非有限,应明确报告而非宣称夹逼成功。
常见错误
(把函数值小当成时间误差小)
在平坦零点附近, 的值很小并不说明时间误差小。对 ,在 的值是 ,时间误差却是 。二分应以夹逼区间的宽度作停止准则,这才是定理所控制的量。
常见错误
(在被拒绝步的插值上搜索事件)
被拒绝的试探步不属于计算轨迹。在它的插值上夹到的事件,未必存在于较短的已接受步;已接受步的事件也可能因此漏掉。只应搜索已接受步的稠密插值。
练习与解答
快速检查
(对 在 二分两次,并写出所得区间。)
解答 · 答案
,保留 ;,保留 。其中点 与 的某个零点(此处为 )相距最多 。
快速检查
(若在一个同时包含真实零点与数值零点的区间上 、,数值夹逼区间包含于该区间且宽度为 ,求其中点与真实事件的距离界。)
解答 · 答案
中点与某个数值零点相距不超过 ,由扰动估计,该数值零点与真实零点相距不超过 ;所以界为 。
快速检查
(,,其中 。事件怎样变化?)
解答 · 答案
在 有事件,而 没有。任意小的一致扰动也可能消除相切事件;由于 ,扰动估计所需的导数下界在该根处失效。