应用中遇到的大多数微分方程都没有闭式解,因此要在网格上逐步计算数值解。本单元介绍显式一步法,并回答实验报告必须回答的问题:误差有多大、它如何依赖步长 h、高阶方法的代价是什么。它延伸实验 3 中的 Euler 实验,并补充隐式 Euler 法与稳定性的意义(该处处理刚性衰减);本单元只讨论显式方法与准确度。
初值问题与 Euler 法
求解 y′=f(t,y),y(t0)=y0,区间为 [t0,T],网格为 tn=t0+nh,h=(T−t0)/N。
定义 15.1.1
(一步法、Euler 法、局部误差与整体误差)
一步法只由 yn 算出 yn+1;若 yn+1 由公式直接给出而无须解方程,则称为显式。Euler 法为
yn+1=yn+hf(tn,yn).以 y(t) 表示精确解,整体误差为 en=y(tn)−yn。若起点为精确值,单独一步所产生的误差称为局部误差。
Euler 法的局部误差。 若 y∈C2,Taylor 定理给出 y(tn+1)=y(tn)+hy′(tn)+2h2y′′(ξn),其中 ξn∈(tn,tn+1),而 y′(tn)=f(tn,y(tn))。因此局部误差为 2h2y′′(ξn),是 h2 阶。
设 f 对 y 满足 Lipschitz 条件,常数为 L>0,即对所有相关的 t,u,v 有 ∣f(t,u)−f(t,v)∣≤L∣u−v∣,且解满足 [t0,T] 上 ∣y′′∣≤M。若 y0 为精确值,则
∣en∣≤2LhM(eL(tn−t0)−1).
把 Euler 公式从 Taylor 展开式中减去:
en+1=en+h[f(tn,y(tn))−f(tn,yn)]+2h2y′′(ξn),所以 ∣en+1∣≤(1+hL)∣en∣+2h2M。由 e0=0,用归纳法得 ∣en∣≤2h2Mk=0∑n−1(1+hL)k=2h2M⋅hL(1+hL)n−1=2LhM((1+hL)n−1)。因 1+hL≤ehL,故 (1+hL)n≤enhL=eL(tn−t0)。
证明透视
每个假设在递推中的位置
Lipschitz 条件只用了一次,就在方括号里:它把精确点与算得点上的斜率之差变成至多 L∣en∣,所以上一步的误差乘以的是 1+hL,而不是某个无法控制的量。界 ∣y′′∣≤M 也只用了一次,在每一步把新产生的局部误差限制在 h2M/2 以内。关键一步是把单行递推 ∣en+1∣≤(1+hL)∣en∣+h2M/2 展开成等比和;这个和约有 1/h 项,每项大小为 h2,所以总和是 h 阶而不是 h2 阶,这正是失去一次幂的确切位置。最后的不等式 1+hL≤ehL 把精确但不易处理的 (1+hL)n 换成不分别依赖 n 和 h 的量,因此出现因子 eL(tn−t0),在长区间上这个因子可以很大。y0 精确使 e0=0;若有初始误差,界就要多出一项 eL(tn−t0)∣e0∣。
因此整体误差是 h 阶:局部误差是 O(h2),但 N∼1/h 步的累积损失一次幂,所以 Euler 法是一阶。
二阶方法
若对光滑的 f,方法的整体误差为 O(hp),称该方法为 p 阶。
两个经典的二阶方法每步计算两次 f。
Heun 法(改进 Euler 法)。
k1=f(tn,yn),k2=f(tn+h,yn+hk1),yn+1=yn+2h(k1+k2).
中点法。
k1=f(tn,yn),k2=f(tn+2h,yn+2hk1),yn+1=yn+hk2.
命题 15.1.4
(Heun 法与中点法的局部误差)
若 f 二阶连续可微,则 Heun 法与中点法的局部误差都是 O(h3)。局部误差 O(h3) 累积成整体误差 O(h2)。
以 f,ft,fy 表示在 (tn,yn) 的值,其中 yn=y(tn)。由于 y′′=ft+ffy,Taylor 定理给出 y(tn+1)=yn+hf+2h2(ft+ffy)+O(h3)。对 Heun 法,k2=f(tn+h,yn+hf)=f+hft+hffy+O(h2),所以 yn+1=yn+hf+2h2(ft+ffy)+O(h3)。两个展开式在 O(h3) 之内一致。中点法的计算相同,此时 k2=f+2hft+2hffy+O(h2),而 k2 前的因子 h 恢复出相同的 2h2 项。
在测试方程 y′=λy 上,令 z=hλ,Heun 法与中点法都给出 yn+1=(1+z+2z2)yn,即 ez 的二次 Taylor 多项式,这解释了二阶准确度。
经典四阶 Runge–Kutta 法
k1k3=f(tn,yn),=f(tn+2h,yn+2hk2),k2k4=f(tn+2h,yn+2hk1),=f(tn+h,yn+hk3),yn+1=yn+6h(k1+2k2+2k3+k4).
这是标准结果:此方法的局部误差为 O(h5),整体误差为 O(h4)。对 y′=λy,可以直接验证它与指数函数的匹配。令 z=hλ、yn=y:k1=λy,k2=λ(1+2z)y,k3=λ(1+2z+4z2)y,k4=λ(1+z+2z2+4z3)y。于是 k1+2k2+2k3+k4=λy(6+3z+z2+4z3),且
yn+1=(1+z+2z2+6z3+24z4)yn,
这是 ez 的四次 Taylor 多项式。
RK4 每步需要计算四次 f,Heun 法两次,Euler 法一次。代价以 f 的计算次数衡量,合理的比较是相同代价下的准确度,而不是相同 h 下的准确度。
以实验度量阶
若 E(h)≈Chp,则 E(h)/E(h/2)≈2p,故 p≈log2E(h/2)E(h)。这个近似只在 h 小到使首项占主导时成立,并且需要精确解(或精细得多的参考解)来计算 E。
详解例子
例题 15.1.5
(三种方法用于 y′=y)
取 y′=y、y(0)=1、T=1。精确值为 y(1)=e≈2.71828。对 y′=λy,每种方法每步都乘以一个固定因子。取 h=21,即 z=21,走两步:
- Euler:因子 1.5,y2=2.25,误差 0.46828。
- Heun:因子 1+21+81=1.625,y2=2.640625,误差 0.07766。
- RK4:因子 1+21+81+481+3841=1.6484375,y2=2.717346,误差 0.000936。
取 h=41(四步):Euler 为 1.254=2.441406,误差 0.27688;Heun 因子 1.28125,y4=2.694856,误差 0.02343;RK4 误差 0.0000719。由 h=21 到 h=41 的误差比为 1.69、3.31、13.0,当 h→0 时趋近 2、4、16,即阶为 1、2、4。
例题 15.1.6
(两种方法在非自治方程上的一步)
设 y′=y−t2+1、y(0)=21,精确解为 y=(t+1)2−21et,故 y(21)=2.25−21e1/2=1.425639。取 h=21。
- Euler:y1=21+21(21−0+1)=1.25。误差 0.1756。
- Heun:k1=f(0,21)=1.5。预测点为 (21,21+21⋅1.5)=(21,1.25),所以 k2=1.25−41+1=2。于是 y1=21+41(1.5+2)=1.375。误差 0.0506。
下面是 Heun 循环的 MATLAB 写法,在这组数据上跟踪(第一轮:k1=1.5,k2=2,y=1.375):
f = @(t,y) y - t.^2 + 1;
h = 0.5; N = 1; t = 0; y = 0.5;
for n = 1:N
k1 = f(t, y);
k2 = f(t + h, y + h*k1);
y = y + h/2*(k1 + k2);
t = t + h;
end
例题 15.1.7
(给定步长下的 Euler 误差界)
对 [0,1] 上的 y′=y:L=1,∣y′′∣=et≤e=:M,所以在 t=1 处 ∣en∣≤2he(e−1)≈2.335h。取 h=0.1 时为 0.2335,而实际的 Euler 误差是 e−1.110=2.71828−2.59374=0.1245。这个界成立,但悲观约两倍。取 h=21 时,界为 e(e−1)/4≈1.168,而第一个详解例子中的实际误差为 0.468,相差约 2.5 倍。
常见错误与细微之处
局部误差为 O(hp+1) 的方法,其整体误差为 O(hp)。Euler 法的局部误差是 2h2y′′,但 Euler 法是一阶;因为有 h2 就称之为二阶,是误解了 N∼1/h 步的累积。
在误差表中把 h 减半时,必须使用同一个精确解和同一个终点 T;比较不同时刻的误差会混入增长因子 eLt。在第一个详解例子中,误差比 1.69、3.31、13.0 都是在 t=1 处取得的。
RK4 的 k2 与 k3 都在中点时刻 tn+2h,但 k2 在 yn+2hk1 处计算,k3 在 yn+2hk2 处计算,而 k4 用完整步 hk3。弄错哪个斜率用在哪一级,是手算中最常见的错误。
Euler 法的收敛界要求 f 对 y 满足 Lipschitz 条件且精确解的二阶导数有界;在奇点附近可能失效,且该界本身通常远非最佳。
反例模式
大步长下高阶方法未必更好
断言:在任何步长下,阶越高的方法误差越小。取 y′=−10y、y(0)=1,走一步,h=21,则 z=hλ=−5,精确值为 e−5≈0.0067。Euler 的因子为 1+z=−4,Heun 为 1+z+2z2=8.5,RK4 为 1−5+12.5−6125+24625≈13.71。三者都远离 0.0067,而且误差随阶的升高而增大。取 h=0.05,z=−0.5,因子分别为 0.5、0.625 和 0.60677,而 e−0.5≈0.60653,此时阶的排序才如预期。阶描述的是 h→0 的极限;它对某个给定的较大 h 下的准确度或稳定性没有任何说明。
练习
快速检查
(对 y′=−2y、y(0)=1、h=41,分别用 Euler 法和 Heun 法计算 y2≈y(21),并与 e−1 比较。)
使用每步因子 1+z 与 1+z+2z2,其中 z=−21。
解答 · 引导解答
Euler:因子 1+hλ=1−21=21,所以 y2=41。Heun:z=−21 时因子 1+z+2z2 为 1−21+81=85,所以 y2=6425=0.390625。精确值为 e−1=0.367879;误差分别为 0.1179(Euler)和 0.0227(Heun)。
快速检查
(证明:Heun 法用于 y′=λy(λ<0 为实数)时,对每个 yn=0 有 ∣yn+1∣<∣yn∣,当且仅当 −2<hλ<0。)
把 1+z+2z2 配方。
解答 · 引导解答
令 z=hλ 为实数,因子为 1+z+2z2=21((z+1)2+1)≥21>0。所以它小于 1 当且仅当 (z+1)2<1,即 −2<z<0。当 z≤−2 或 z≥0 时,它至少为 1。因此 ∣yn+1∣<∣yn∣ 当且仅当 −2<hλ<0。
快速检查
(Euler 法用步长 h、h/2、h/4,在同一时刻的误差为 0.1200、0.0610、0.0307。估计其阶。)
对每一对相邻的值使用 p≈log2(E(h)/E(h/2))。
解答 · 答案
log2(0.1200/0.0610)=log21.967≈0.976,log2(0.0610/0.0307)=log21.987≈0.991。两者都接近 1,与一阶一致。
快速检查
(证明:中点法用于 y′=λy 时,其更新因子与 Heun 法相同。)
令 z=hλ,分别计算两种方法的 k2。
解答 · 引导解答
令 z=hλ。中点法:k1=λy,k2=λ(y+2hλy)=λ(1+2z)y,所以 yn+1=y+hλ(1+2z)y=(1+z+2z2)y。Heun 法:k2=λ(y+hλy)=λ(1+z)y,所以 yn+1=y+2hλy(2+z)=(1+z+2z2)y。两个因子相同。
快速检查
(对 [0,1] 上的 y′=y、y(0)=1,计算 h=21 时的 Euler 误差界,并与第一个详解例子中的实际误差比较。)
使用 L=1、M=e、tn−t0=1。
解答 · 引导解答
∣e2∣≤2(1/2)e(e−1)=4e(e−1)≈1.168。实际误差为 0.468,所以这个界成立,并高估约 2.5 倍。