为什么先预测再校正?
梯形法把旧、新端点的斜率取平均;但新端点斜率依赖未知的新数值,因此一般每一步都要解代数方程。若已有前两个斜率,Adams–Bashforth 预测可以廉价地估计新端点,再用该处斜率校正一次。这省去隐式求解,代价是所得公式成为另一个显式两步法:只校正一次,并不保证预测值等于梯形方程的解。
定义 4.3.1
(一次 AB2 预测与一次梯形校正)
设 ,固定步长 ,,。由两个起始值计算
校正后,要重新计算并存储 ,供下一步使用。把预测点的 当作 沿用,得到的是另一算法。可用显式中点法等单步法求 ,令其误差为 或更小;任意起始值不一定保留所需阶数。
概念视角算法
不动点迭代的一次扫描
把梯形方程写成 ,其中 。校正值恰好是 :从 AB2 猜测值出发的一次不动点扫描。由于 的 Lipschitz 常数为 ,校正值到梯形解 的距离按这个因子缩小:。在下面的单步例子中, 与 分别偏离 达 与 ,比值正是 。
从局部误差到收敛
定理 4.3.2
(有限时间区间上的二阶收敛)
假设 对状态变量在所有时间上一致地全局 Lipschitz,常数为 ,且精确解在 上三阶导数有界。若 和 均为 ,则当 时,所有满足 的格点有 。同一论证适用于固定有限维空间中的任何范数。
证明
(精确起步缺陷与两层 Gronwall 论证)
把前两个精确值代入预测式。在 附近对 和 作泰勒(Taylor)展开,可知预测端点 与 之差一致地为 。由于 有界,对 的梯形积分公式有 的状态缺陷。将精确端点斜率改成 ,所得校正值最多改变 ;故从精确历史出发的校正缺陷为 。
比较两组数值历史,令 为它们在第 和 点差的范数最大值。Lipschitz 条件令两个预测值的差不超过 ,因此两个校正值的差不超过 。当 ,此式不超过 ,其中 。把数值历史与精确解的采样比较,再加上每步 的缺陷,可得
迭代不多于 次,得到 。各行的常数可以适当放大,故结论成立。这是有限时间结论,并不保证每一个大步长都稳定。
证明透视
为什么一次不精确的校正不损失阶数
证明的相容性部分取决于一次乘法。从精确历史出发,预测值与 相差 。这个误差只通过斜率 进入校正式,而斜率乘以 ,其改变又不超过 乘状态误差。因此预测值只贡献 ,比梯形缺陷 低一阶。这是关键一步:预测器的精度比校正器低一阶便已足够。
稳定性部分要处理两步法,所以追踪 ,即相邻两层误差的较大者。Lipschitz 常数用了两次:一次经过预测式,其中权重二分之三与二分之一给出 ;一次经过校正式。步长界 把 吸收进 。起始假设 只在最后出现,离散 Gronwall 界把它乘以 。由于刚性问题的 可以极大,这个有限时间定理对大步长毫无说明;下面的线性稳定区间才回答这个问题。
实际算法的稳定性
令 ,。消去预测值后,实际递推式及其特征方程为
每个特征根 对应一个递推模态。采用有界根的惯例:两根模长均不超过一,且单位圆上的根必须是单根,才称 稳定。重单位根须排除,因为它还产生 模态。
定理 4.3.3
(负实轴稳定区间)
当 、,上述一次校正算法恰在 时稳定。若 ,两根都严格位于单位圆内; 时重根 使递推不稳定。
证明
(实二次式的根位置判别)
对实系数首一二次式 ,两根严格位于单位圆内的充要条件是 、 和 。复共轭根的模长平方等于 ;若两根为实数,前两个不等式排除只有一根超出任一端点,最后一个排除两根同时超出同一端点。反过来,由两根在圆内可直接得到三个不等式。
此处 、,上述三项分别是 、、;三者同时为正恰好等价于 。 时根为 。 时 ;例如 、 给出 。若 ,两根之积 ,故至少有一根模长大于一。
详解例子
例题 4.3.4
(实际计算一步)
取 、、、。因 、,得 ,。下一步存储的斜率是 ,不是预测斜率 。相同的 若用完全隐式梯形法,须解 ,得到 。两种方法确实给出不同结果。
例题 4.3.5
(衰减振荡和不稳定边界)
对 ,当 时两根为 ,模长均为 :任何历史都会衰减,虽可能改变符号。当 时两根均为 ,某些历史线性增长。相比之下,梯形法在测试方程的放大因子为 ;当 ,其模长不超过一。一次校正算法不继承这种 A 稳定性。
例题 4.3.6
(以精确起步作细化检查)
取 上的 、,并用精确起始值 、,使定理适用。把方法推进至 ,得
相邻误差之比约为 与 ,逐渐接近二阶方法应有的因子四。此处 远在稳定区间之内,传播不会干扰。这些比值与定理相符,但只是证据,不是证明。
常见误解
常见错误
(存储预测斜率)
预测值只是中间状态,不是最终接受值。校正后必须计算并存储 。在实际计算一步的例子中,存储的斜率是 ,不是预测斜率 ;沿用后者便定义了另一方法,其稳定性分析也不同。
常见错误
(边界根只检查模长)
在 ,两根的模长都是一,只看模长便会接受这个值。但根 是重根,递推有解 ,按有界根惯例此值不稳定。
常见错误
(任意选取第二个起始值)
收敛定理假设 。若直接取 ,对非常数解的起始误差是 阶,便不能再套用定理。显式中点法等单步起步法可满足此假设。
局部缺陷小,还要控制误差的累积才能推出精度;同样,齐次测试递推的稳定性不是一般非线性方程的误差界。以上区间也只适用于固定步长的一次校正公式;增加校正次数或改变步长会得到不同递推。
反例模式
校正后的方法不继承 A 稳定性
既然校正式就是梯形法,有人会以为方法像梯形法一样,对每个 都稳定。取 、,即 。此时 、,特征方程 的根为
由 、,递推给出 、,而精确解按 衰减。同一 的梯形法因子为 。修正后的命题就是上面证明的稳定区间:在负实轴上,一次校正方法只在 时稳定。
小检查
快速检查
(预测值并不精确,为什么校正仍可有二阶精度?)
追踪预测误差如何经端点斜率进入。
解答 · 答案
从精确历史出发,端点预测误差为 ;相应斜率误差再乘 ,只对校正状态产生 影响。梯形公式的缺陷本已有 ,所以精确起步缺陷仍为 。
练习与解答
快速检查
(对 、,按有界根惯例判断递推是否稳定。)
计算 。
解答 · 答案
位于 ,两根都严格位于单位圆内,两个模态均衰减。
快速检查
(对 、、、,计算第一次校正。)
使用 、。
解答 · 答案
预测值为 ;校正值为 ,应存储的斜率是 。
快速检查
(在 ,求 、 的解,并解释其意义。)
特征多项式是 。
解答 · 答案
递推有重根 ,故 ;由起始值得 。再小的非零起始扰动也会随 无界增长。
快速检查
(学生使用精确 ,但取 ,可否套用上述二阶收敛定理?)
把起始误差与假设比较。
解答 · 答案
不可以。第二个起始误差为 ,不是 ,而定理要求两个起始误差均为 。单凭这点并不能判定其后每个值的误差,只是失去了保证。