动机
固定步长在解变化缓慢时可能浪费运算,在变化急剧时又可能太粗。自适应方法先试算,再比较同一时间区间上的两个近似,据此决定是否保留。要把这个想法变成算法,单说“误差大就缩短步长”并不足够:我们还须指定保留哪个值、拒绝后从哪里重试、如何到达终点,以及何时宣布失败。
这里选显式 Euler 法,令每个阶段都能手算。控制器刻意保守:拒绝时步长减半,接受后不增大。前一节已讨论嵌入式 Runge–Kutta 估计与四阶法的步长加倍;本节集中把一阶法的比较写成完整有限算法,并仔细区分指标和严格误差界。
定义
考虑 y ′ = f ( t , y ) y'=f(t,y) y ′ = f ( t , y ) ,y ( t 0 ) = y 0 ∈ R d y(t_0)=y_0\in\mathbb R^d y ( t 0 ) = y 0 ∈ R d ,时间区间为 [ t 0 , T ] [t_0,T] [ t 0 , T ] ,其中 T > t 0 T>t_0 T > t 0 。从已接受状态 ( t , Y ) (t,Y) ( t , Y ) 试步长 h > 0 h>0 h > 0 ,计算
k 0 = f ( t , Y ) , C = Y + h k 0 , M = Y + h 2 k 0 , k m = f ( t + h 2 , M ) , F = M + h 2 k m , D = F − C . \begin{aligned}
k_0&=f(t,Y),& C&=Y+hk_0,\\
M&=Y+\tfrac h2k_0,& k_m&=f(t+\tfrac h2,M),\\
F&=M+\tfrac h2 k_m,& D&=F-C.
\end{aligned} k 0 M F = f ( t , Y ) , = Y + 2 h k 0 , = M + 2 h k m , C k m D = Y + h k 0 , = f ( t + 2 h , M ) , = F − C .
C C C 是一个完整 Euler 步,F F F 是两个半步。两者必须从同一个数值状态 Y Y Y 出发,而非比较两条分别累积误差的轨迹。
给定绝对容许量 a j > 0 a_j>0 a j > 0 与相对容许量 r j ≥ 0 r_j\ge0 r j ≥ 0 ,试算的尺度及按尺度调整的指标为
s j = a j + r j max ( ∣ Y j ∣ , ∣ F j ∣ ) , E = max 1 ≤ j ≤ d ∣ D j ∣ s j . s_j=a_j+r_j\max(|Y_j|,|F_j|),\qquad
E=\max_{1\le j\le d}\frac{|D_j|}{s_j}. s j = a j + r j max ( ∣ Y j ∣ , ∣ F j ∣ ) , E = 1 ≤ j ≤ d max s j ∣ D j ∣ . 当 E ≤ 1 E\le1 E ≤ 1 时试算被接受 ,传递的是较细的 F F F ,而非 C C C 。
a j a_j a j 与对应状态分量有相同单位,r j r_j r j 无单位。正的绝对容许量使分母在状态为零时仍为正。精确算术下,完整控制器如下:
设 H = T − t 0 H=T-t_0 H = T − t 0 、t = t 0 t=t_0 t = t 0 、Y = y 0 Y=y_0 Y = y 0 、深度 q = 0 q=0 q = 0 ,并选非负整数最大深度 Q Q Q 。
若 t = T t=T t = T ,返回成功和 Y Y Y ;否则令 h = min ( H 2 − q , T − t ) h=\min(H2^{-q},T-t) h = min ( H 2 − q , T − t ) ,按上式算出 C , F , D , E C,F,D,E C , F , D , E 。
若 E ≤ 1 E\le1 E ≤ 1 ,设 ( t , Y ) ← ( t + h , F ) (t,Y)\leftarrow(t+h,F) ( t , Y ) ← ( t + h , F ) ,保留 q q q ,返回步骤 2。需要输出轨迹时记录接受的点。
若 E > 1 E>1 E > 1 且 q < Q q<Q q < Q ,丢弃两个试算值,令 q ← q + 1 q\leftarrow q+1 q ← q + 1 ,在原来的 ( t , Y ) (t,Y) ( t , Y ) 返回步骤 2;若 E > 1 E>1 E > 1 且 q = Q q=Q q = Q ,返回失败和最后接受的点。
二进分割规则放弃自动增大步长,换取清楚的有限次数上界。在本算法的精确算术下,由于 H = T − t 0 H=T-t_0 H = T − t 0 且 q q q 不递减,先前各接受步和全区间长度都是目前名义步长的整数倍;因此到达终点前截短不会发生。保留取最小值的步骤,是为初始 H H H 可任选的变体或谨慎实现的浮点运算提供终点防护。有限精度运算还须在阶段值或指标非有限、t + h = t t+h=t t + h = t ,或中点无法与端点区分时宣布失败;终点亦须用一致的表示。不可把这些情况误报为成功。
定理 / 命题
设 f f f 在时间–状态空间的开集 U U U 上为 C 1 C^1 C 1 ,且 f t , f y f_t,f_y f t , f y 局部 Lipschitz。令 K ⊂ U K\subset U K ⊂ U 为紧致集,假设对起点 ( t , Y ) ∈ K (t,Y)\in K ( t , Y ) ∈ K 及 0 < h ≤ h 0 0<h\le h_0 0 < h ≤ h 0 ,精确解线段和两个 Euler 阶段点均位于包含于 U U U 的同一固定紧邻域。令 ϕ h ( t , Y ) \phi_h(t,Y) ϕ h ( t , Y ) 表示以 Y Y Y 为时间 t t t 初值的精确解在 t + h t+h t + h 的值。对 ( t , Y ) ∈ K (t,Y)\in K ( t , Y ) ∈ K 一致地,当正的 h h h 充分小时,
D = h 2 4 A ( t , Y ) + O ( h 3 ) , ϕ h ( t , Y ) − F = D + O ( h 3 ) , A = f t + f y f . D=\frac{h^2}{4}A(t,Y)+O(h^3),\qquad
\phi_h(t,Y)-F=D+O(h^3),\quad
A=f_t+f_yf. D = 4 h 2 A ( t , Y ) + O ( h 3 ) , ϕ h ( t , Y ) − F = D + O ( h 3 ) , A = f t + f y f . 余项在该紧致集上一致。对有限的 Q Q Q ,只要阶段值及指标均有定义且有限,上述精确算术控制器只试算有限次,并在 T T T 成功或于深度 Q Q Q 的拒绝步返回失败。成功只证明显示的接受测试通过,并不证明精确解的误差界。
概念视角 分析
把指标看成两个斜率之差 两条公式相减,精确地得到
D = h 2 ( k m − k 0 ) = h 2 ( f ( t + h 2 , M ) − f ( t , Y ) ) . D=\frac h2\bigl(k_m-k_0\bigr)=\frac h2\Bigl(f\bigl(t+\tfrac h2,M\bigr)-f(t,Y)\Bigr). D = 2 h ( k m − k 0 ) = 2 h ( f ( t + 2 h , M ) − f ( t , Y ) ) . 指标是半步内斜率变化的 h / 2 h/2 h /2 倍,相当于把 y ′ ′ = A y''=A y ′′ = A 的差商乘以 h 2 / 4 h^2/4 h 2 /4 。这既解释了 D D D 的展开式,也解释了下面零比较的例子:那里两个采样斜率相同,所以无论两者之间发生什么,D = 0 D=0 D = 0 。
证明思路或证明
对中点阶段在时间和状态两个变量展开,得
k m = f ( t , Y ) + h 2 ( f t + f y f ) ( t , Y ) + O ( h 2 ) . k_m=f(t,Y)+\frac h2(f_t+f_yf)(t,Y)+O(h^2). k m = f ( t , Y ) + 2 h ( f t + f y f ) ( t , Y ) + O ( h 2 ) . 所以 F = Y + h f + h 2 A / 4 + O ( h 3 ) F=Y+hf+h^2A/4+O(h^3) F = Y + h f + h 2 A /4 + O ( h 3 ) ,而 C = Y + h f C=Y+hf C = Y + h f 。由微分方程有 y ′ ′ = f t + f y f y''=f_t+f_yf y ′′ = f t + f y f ,精确解展开为 ϕ h = Y + h f + h 2 A / 2 + O ( h 3 ) \phi_h=Y+hf+h^2A/2+O(h^3) ϕ h = Y + h f + h 2 A /2 + O ( h 3 ) 。相减即得两个估计。这里的“精确起点”是把当前的 Y Y Y 视为局部初值,并没有声称整条计算轨迹上的 Y Y Y 等于原问题的 y ( t ) y(t) y ( t ) 。导数控制及紧邻域保证余项一致。
终止性方面,每次拒绝都令 q q q 增加;在接受或失败之前最多增加 Q Q Q 次。在目前深度 q q q ,因 q q q 从不减少,先前每个接受步以及总长 H H H 均为 H 2 − q H2^{-q} H 2 − q 的整数倍。所以正的剩余长度至少等于名义步长,截短不会发生。每个接受步至少长 H 2 − Q H2^{-Q} H 2 − Q ,故最多接受 2 Q 2^Q 2 Q 步,总试算次数亦有限。这个结论没有保证在深度 Q Q Q 以内一定可达所选容许量。
证明透视
误差结论需要三个独立环节 展开只把 D D D 和局部缺陷联系至一个余项;接受测试只检查 D D D 相对于指定尺度的大小;要得到终点误差界,还要计算该余项的上界并控制已累积误差的传播。这些都不会单凭 E ≤ 1 E\le1 E ≤ 1 自动成立,因此不能说测试通过便保证每个真正局部误差都小于其尺度。
若某分量 A j ( t , Y ) ≠ 0 A_j(t,Y)\ne0 A j ( t , Y ) = 0 且尺度连续变化,按尺度调整后的主导指标按 h 2 h^2 h 2 变化,步长减半后大约变为四分之一。不过这个算法每次拒绝后都重新计算 E E E ,不依靠渐近比例作接受决定。若主导项为零,较高阶项或抵消可能主导比较,比例便不一定成立。
例如,若 L ≥ 0 L\ge0 L ≥ 0 ,各相关精确流的 Lipschitz 因子不大于 1 + L h 1+Lh 1 + L h ,并且已知真正局部缺陷的上界 δ n \delta_n δ n ,则 e n + 1 ≤ ( 1 + L h n ) e n + δ n e_{n+1}\le(1+Lh_n)e_n+\delta_n e n + 1 ≤ ( 1 + L h n ) e n + δ n ,因此
e N ≤ e L ( T − t 0 ) ( e 0 + ∑ n = 0 N − 1 δ n ) . e_N\le e^{L(T-t_0)}\left(e_0+\sum_{n=0}^{N-1}\delta_n\right). e N ≤ e L ( T − t 0 ) ( e 0 + n = 0 ∑ N − 1 δ n ) .
这是有条件的确定性界,不能未经证明便把 δ n \delta_n δ n 换成 ∥ D n ∥ \|D_n\| ∥ D n ∥ :必须先控制未知余项。而每一步的局部容许量也不会自动限制这些上界之和。
例题详解
例题 2.3.3
(完整计算:稍后状态也可能遭拒绝)
取 y ′ = y y'=y y ′ = y 、y ( 0 ) = 1 y(0)=1 y ( 0 ) = 1 、T = 1 T=1 T = 1 、a = 1 / 32 a=1/32 a = 1/32 、r = 0 r=0 r = 0 、Q = 3 Q=3 Q = 3 。此时 C = Y ( 1 + h ) C=Y(1+h) C = Y ( 1 + h ) 、F = Y ( 1 + h / 2 ) 2 F=Y(1+h/2)^2 F = Y ( 1 + h /2 ) 2 、D = Y h 2 / 4 D=Yh^2/4 D = Y h 2 /4 。下表列的是未除以尺度的 D D D ;因状态均为正,接受条件为 D ≤ 1 / 32 D\le1/32 D ≤ 1/32 。
第四个四分之一步有 531441 > 524288 531441>524288 531441 > 524288 ,故 D > 1 / 32 D>1/32 D > 1/32 ,时间保持在 3 / 4 3/4 3/4 。最后的接受值是
Y ( 1 ) = ( 9 8 ) 6 ( 17 16 ) 4 = 44386483761 17179869184 ≈ 2.58363340. Y(1)=\left(\frac98\right)^6\left(\frac{17}{16}\right)^4
=\frac{44386483761}{17179869184}\approx2.58363340. Y ( 1 ) = ( 8 9 ) 6 ( 16 17 ) 4 = 17179869184 44386483761 ≈ 2.58363340. 精确值 e ≈ 2.71828183 e\approx2.71828183 e ≈ 2.71828183 与它相差约 0.13464843 0.13464843 0.13464843 ,大于局部门槛 1 / 32 1/32 1/32 。这展示误差累积;由于算法没有承诺全局容许量,并无违反任何全局定理。若 Q = 2 Q=2 Q = 2 ,第四个四分之一步会在 t = 3 / 4 t=3/4 t = 3/4 返回失败。
取 y ′ = t ( t − 1 / 2 ) y'=t(t-1/2) y ′ = t ( t − 1/2 ) 、y ( 0 ) = 0 y(0)=0 y ( 0 ) = 0 ,区间为 [ 0 , 1 ] [0,1] [ 0 , 1 ] 。t = 0 t=0 t = 0 与 t = 1 / 2 t=1/2 t = 1/2 的两个 Euler 阶段斜率均为零,因此 C = F = D = 0 C=F=D=0 C = F = D = 0 ,任何正尺度都会接受整段。但积分得到 y ( 1 ) = 1 / 3 − 1 / 4 = 1 / 12 y(1)=1/3-1/4=1/12 y ( 1 ) = 1/3 − 1/4 = 1/12 。采样时间之间的光滑多项式对这项比较不可见。零指标并不证明精确。
对 y ′ = − 100 y y'=-100y y ′ = − 100 y 和 h = 0.1 h=0.1 h = 0.1 ,两个半步的放大因子为 ( 1 − 5 ) 2 = 16 (1-5)^2=16 ( 1 − 5 ) 2 = 16 ,但精确因子是 e − 10 e^{-10} e − 10 。重复这样的步长会增长而非衰减。若绝对容许量刻意设得很宽,算法可接受它:令 Y = 1 Y=1 Y = 1 、a = 30 a=30 a = 30 ,则 C = − 9 C=-9 C = − 9 、F = 16 F=16 F = 16 、E = 25 / 30 < 1 E=25/30<1 E = 25/30 < 1 。收紧容许量可能使步长变短,但接受规则本身并非无条件稳定的保证。
常见错误
阶数 p p p 的方法在共同主导缺陷展开成立时,细步误差的倍数是 1 / ( 2 p − 1 ) 1/(2^p-1) 1/ ( 2 p − 1 ) 。这里 p = 1 p=1 p = 1 ,倍数为一;套用 Runge–Kutta 步长加倍公式的四阶分母 15 15 15 ,会把 Euler 估计低估十五倍。D D D 虽在渐近意义下近似细步带符号误差,也不因此自动成为严格上界。
拒绝后不可把试算状态当成重试的起点。必须先以 T − t T-t T − t 截短,再算两个近似,否则比较的不再是同一区间。若已知事件或不连续点,应在该点分段并采用合适的单侧模型;没有论证便不可把光滑展开跨越跳跃。
逐分量最大值测试的是所选尺度。改变某分量的单位而不相应改变其绝对容许量 a j a_j a j ,测试的含义也会改变。
总结
步长加倍比较一个 Euler 整步与两个半步;在光滑条件下,两者之差给出细步局部缺陷的主导近似。有限深度的接受/拒绝程序可到达终点,或明确回报失败。通过局部比较本身并不能认证全局容许量或稳定性。
练习
快速检查
(对 y ′ = 2 t y'=2t y ′ = 2 t 、y ( 0 ) = 0 y(0)=0 y ( 0 ) = 0 ,从 t = 0 t=0 t = 0 试步长 h h h 。求 C , F , D C,F,D C , F , D 和精确细步局部误差;此例的估计是否恰好相等?)
解答 · 答案 第一个斜率为零,中点斜率为 h h h ,故 C = 0 C=0 C = 0 、F = h 2 / 2 F=h^2/2 F = h 2 /2 、D = h 2 / 2 D=h^2/2 D = h 2 /2 。积分得 y ( h ) = h 2 y(h)=h^2 y ( h ) = h 2 ,因此 y ( h ) − F = h 2 / 2 = D y(h)-F=h^2/2=D y ( h ) − F = h 2 /2 = D 。此例中高阶余项恰好为零,但任意光滑 f f f 不一定有此等式。
快速检查
(考虑允许初始 H H H 任选的控制器变体中一次独立试算,设 y ′ = y y'=y y ′ = y 、Y = 1 Y=1 Y = 1 、T − t = 1 / 2 T-t=1/2 T − t = 1/2 、a = 1 / 32 a=1/32 a = 1/32 、r = 0 r=0 r = 0 、目前名义步长为 1 1 1 。进行截短试算;若现有深度已是最大值,该变体返回什么?)
解答 · 答案 截短后 h = 1 / 2 h=1/2 h = 1/2 ,故 C = 3 / 2 C=3/2 C = 3/2 、F = ( 5 / 4 ) 2 = 25 / 16 F=(5/4)^2=25/16 F = ( 5/4 ) 2 = 25/16 、D = 1 / 16 D=1/16 D = 1/16 。比例指标 E = 2 E=2 E = 2 ,试算被拒绝。在最大深度时算法返回失败及最后接受点 ( t , 1 ) (t,1) ( t , 1 ) ,既不推进时间,也不保留试算状态。
快速检查
(从精确初值出发,若证明每步真正局部缺陷的范数至多为 δ \delta δ ,精确流因子至多为 1 + L h n 1+Lh_n 1 + L h n ,其中 L ≥ 0 L\ge0 L ≥ 0 ,求总时间 T − t 0 T-t_0 T − t 0 内 N N N 个接受步后的误差界。为何单凭 ∥ D n ∥ ≤ δ \|D_n\|\le\delta ∥ D n ∥ ≤ δ 不足?)
解答 · 答案 由上述界及 e 0 = 0 e_0=0 e 0 = 0 ,得 e N ≤ e L ( T − t 0 ) N δ e_N\le e^{L(T-t_0)}N\delta e N ≤ e L ( T − t 0 ) N δ 。此界可能偏大,但符合所列假设。比较值只控制 D n D_n D n ,真正缺陷还包括余项;若未对余项设界,就不能把 δ \delta δ 直接当作每步真正缺陷的上界。
快速检查
(对 y ′ = − λ y y'=-\lambda y y ′ = − λ y 、λ > 0 \lambda>0 λ > 0 ,求两个半 Euler 步的放大因子绝对值不超过一的所有正步长。边界会怎样?)
解答 · 答案 细步放大因子 ( 1 − λ h / 2 ) 2 ≥ 0 (1-\lambda h/2)^2\ge0 ( 1 − λh /2 ) 2 ≥ 0 。它不超过一恰当且仅当 − 1 ≤ 1 − λ h / 2 ≤ 1 -1\le1-\lambda h/2\le1 − 1 ≤ 1 − λh /2 ≤ 1 ,即 0 < h ≤ 4 / λ 0<h\le4/\lambda 0 < h ≤ 4/ λ 。在 h = 4 / λ h=4/\lambda h = 4/ λ 时放大因子为一:数值状态的绝对值不衰减,虽然精确解会衰减。在严格区间内,非零状态每步均衰减。