从微分方程到更新公式
模型可能先告诉我们状态的变化率,而非未来的状态。初值问题同时指定变化率及起始值:
y′(t)=f(t,y(t)),y(0)=y0,0≤t≤T.
先假设区间上存在解。我们在等距网格 tn=nh 上求近似值 yn≈y(tn),其中 Nh=T。把方程在一步内积分,精确关系是
y(tn+1)=y(tn)+∫tntn+1f(s,y(s))ds.
用左端点的斜率乘步长来近似积分,得到第一个方法。
给定步长 h>0 与网格 tn=nh,显式欧拉(Euler)法从 y0 出发,令
yn+1=yn+hf(tn,yn),n=0,1,…,N−1.
目前的状态决定斜率,斜率决定下一个状态。几何上这相当于沿切线前进一步,而不是说真正的解曲线是直线。缩小步长通常减少离散误差,但也需要更多步,浮点舍入误差也可能累积。
单步缺陷与整体误差
为了度量一个更新本身的误差,把精确解而非已有误差的近似值代入更新式。
设 y 是 [0,T] 上的精确解。显式欧拉法在第 n+1 步的单步缺陷为
dn+1=y(tn+1)−y(tn)−hf(tn,y(tn)).
若 y 二次连续可微,并在 [0,T] 上满足 ∥y′′(t)∥≤M,泰勒(Taylor)公式的积分余项给出 ∥dn+1∥≤Mh2/2。这里的绝对单步缺陷是 h2 阶;有些文献再除以 h 才称为局部截断误差,因此报告阶数时要先说明惯例。
设 y 是 [0,T] 上的二次连续可微解,且 ∥y′′∥≤M。假设在包含精确值和数值值的区域内,f 对第二个变量的 Lipschitz 常数为 L≥0。从精确初值开始,显式欧拉法满足
∥y(tn)−yn∥≤⎩⎨⎧2LMh(eLtn−1),2Mtnh,L>0,L=0.因此在固定终止时间、上述界可一致使用时,网格加密所得整体误差是 O(h)。
令 en=y(tn)−yn。精确一步减去数值一步,得
en+1=en+h[f(tn,y(tn))−f(tn,yn)]+dn+1.由三角不等式、Lipschitz 条件及缺陷界,
∥en+1∥≤(1+hL)∥en∥+2Mh2.由 e0=0 反复使用此式,误差不超过 (Mh2/2)j=0∑n−1(1+hL)j。若 L>0,求几何级数并用 (1+hL)n≤eLnh,便得到第一个界;若 L=0,和为 n,得到 Mnh2/2=Mtnh/2。在固定时间内约有 T/h 步,故每步 O(h2) 的缺陷累积成 O(h) 的整体界。
证明透视
收敛估计的条件各有用途
证明由一个精确分解和一条递推组成。分解把 en+1 拆成传播下来的旧误差 en+h[f(tn,y(tn))−f(tn,yn)] 与新的缺陷 dn+1;这一步还没有做任何估计。Lipschitz 假设只用于传播部分,而它之所以适用,是因为两个 f 值都在同一时刻 tn 取值。所以定理要求在同时包含精确值与数值值的区域内有同一个常数 L。界 ∥y′′∥≤M 只用于 dn+1;两个假设不能互相替代。
关键一步是不再逐步估计,而是从 a0=0 展开线性递推 an+1≤(1+hL)an+Mh2/2:第 j+1 步产生的缺陷传到第 n 步时,至多被放大 (1+hL)n−1−j 倍。最后用 1+hL≤ehL 把 n 个放大因子合成与步长无关的 eLtn,证明到此完成;固定终止时间正是在这里用到的。若 f 只在局部满足 Lipschitz 条件,须先证明步长足够小时数值点留在同一个有界区域内,才有单一常数 L 可用。
对 y′=y、y(0)=1,精确解是 et;欧拉法给出 yn=(1+h)n。在 T=1,取 h=1/2 走两步得 y2=(3/2)2=9/4=2.25,小于 e;取 h=1/4 走四步得 (5/4)4=625/256≈2.4414。精确值约为 2.7183。第二个答案更接近,但两次计算本身并不能证明误差阶数;上述定理在其假设下提供误差界。
两个误差约为 0.468 和 0.277,步长减半时比值约为 1.7。展开式 (1+h)1/h=e(1−2h+O(h2)) 表明 h 很小时误差约为 eh/2,所以比值趋于 2,与一阶收敛一致。
每步 O(h2) 的缺陷并不给出 O(h2) 的整体误差。大约有 T/h 个缺陷累积,证明表明总和是 O(h);对 f(t,y)=t,整体误差恰好是 Th/2,见最后一道练习。引用阶数时,要说明指的是单步缺陷、除以 h 后的缺陷,还是整体误差。
稳定性是另一个问题
收敛定理研究固定问题与固定时间区间,并令 h→0 的情况。实际计算的步长却是有限的。为研究误差传播,考虑标量测试方程 y′=λy,其中 λ 可为复数且 Reλ<0。精确解 eλty0 会衰减。显式欧拉法每步却把状态和其扰动乘上
R(z)=1+z,z=hλ.
数值解经过任意多步后也衰减,充要条件是 ∣1+z∣<1。若 λ 为负实数,这等价于 0<h<−2/λ。在 ∣1+z∣=1 时扰动未必衰减;在圆盘外则增长。这是测试方程的绝对稳定条件,并非对所有非线性问题的误差界。
反例模式
衰减的真解可以产生增长的欧拉数列
取 y′=−10y、y(0)=1 和 h=1/4。精确值为正且递减,但欧拉法给出 yn+1=−23yn,所以 y1=−3/2、y2=9/4;迭代值正负交替且振幅增大。同一问题在 h→0 时仍符合欧拉法收敛定理;只是这个步长不在稳定区间 0<h<1/5 内。
隐式欧拉法与刚性衰减
若用右端点近似积分,得到第二个方法。
给定步长 h>0,隐式(后退)欧拉法从 y0 出发,每个 yn+1 取为下列方程的解:
yn+1=yn+hf(tn+1,yn+1).
未知值同时出现在两边,故每一步都需要解方程;方程可能非线性,也不一定唯一可解。例如,若 f 全局 Lipschitz 常数为 L 且 hL<1,右边作为未知值的函数是压缩映射,压缩映射定理保证该步有唯一解。这是充分条件,并非必要条件。
对测试方程,隐式方程是线性的,可以写出闭式解。
命题 1.9.6
(隐式欧拉法使每个衰减测试模态衰减)
设 λ∈C 且 Reλ<0,又设 h>0。对 y′=λy,隐式欧拉法每一步都唯一可解,yn+1=(1−hλ)−1yn,并且当 yn=0 时 ∣yn+1∣<∣yn∣。
记 z=hλ,一步的方程是 (1−z)yn+1=yn。由于 Re(1−z)=1−hReλ>1,1−z 不为零,所以这一步有唯一解 yn+1=(1−z)−1yn。此外 ∣1−z∣≥Re(1−z)>1,故 ∣(1−z)−1∣<1;当 yn=0 时便有 ∣yn+1∣<∣yn∣。
这个假设对 h 没有任何上限。当 λ=−10、h=1/4,因子是 2/7,而非显式法的 −3/2。稳定并不保证准确:一步后 2/7≈0.286 与精确值 e−5/2≈0.0821 相差甚远。大步长即使稳定,也可能错误地描绘快速的暂态变化。
概念视角几何
复平面上的两个稳定区域
以 z=hλ 为变量,显式欧拉法恰好在开圆盘 ∣z+1∣<1(以 −1 为圆心、半径为一)上抑制测试模态。这个圆盘与负实轴的交集是 (−2,0),也就是条件 0<h<−2/λ。隐式欧拉法恰好在 ∣1−z∣>1 处抑制它,即以 1 为圆心、半径为一的闭圆盘之外。这个外部包含整个开左半平面,这正是上述命题;它也包含所有 Rez>2 的 z,在那里一个增长的模态会被错误地抑制。
一个系统可同时包含快、慢衰减模态。例如 u′=−u 与 v′=−1000v 的时间尺度相差很大。即使关心的是较长时间的慢模态,显式欧拉法仍须取 h<0.002 才能抑制快模态。这是刚性的一个简单表现:稳定性要求的步长可能远小于描绘慢变化所需的步长。隐式方法放宽测试方程的稳定性限制,但代价是求解线性或非线性方程;两种方法都仍需检查精度。
取 y′=−y2、y(0)=1,其精确解为 y(t)=1/(1+t),并取 h=1/2。隐式欧拉法要求 y1=1−21y12,即
y12+2y1−2=0,y1=−1±3.两个根都满足步进方程,但只有 3−1≈0.7321 延续解的轨迹;−1−3≈−2.732 与真解无关。实际的求解器从上一步的值开始迭代:对 g(u)=u2+2u−2 由 u=1 起用牛顿(Newton)法,得 1, 0.75, 0.73214,…,收敛到正确的根。与 y(1/2)=2/3≈0.6667 比较,隐式法误差约为 0.065;显式欧拉法给出 1−21=0.5,误差约为 0.167。
对 u′=−u、v′=−1000v 及 h=0.1,每步的显式因子(左)与隐式因子(右)是
1−h=0.9,1−1000h=−99;1+h1≈0.9091,1+1000h1≈0.0099.精确的慢因子是 e−0.1≈0.9048,所以在这个步长下两种方法都能合理地描绘慢模态。可是显式欧拉法每步把快分量乘以 −99:十步后,大小为 10−10 的快扰动变成约 9×109,因为 9910≈9.0×1019。隐式欧拉法每步把它缩小为原来的 1/101,尽管精确的快因子 e−100 还要小得多。边界情形说明显式法的门槛是精确的:当 h=0.002,快因子为 1−2=−1,快扰动正负交替,永远既不增长也不衰减。
上述命题只说隐式欧拉法不会放大衰减的测试模态,并没有说它跟踪该模态有多准确。取 λ=−1000、h=0.1,因子 1/101 是稳定的,但精确因子是 e−100。对增长模态,同一性质也可能误导:若 λ>0 且 hλ>2,则 ∣1−hλ∣>1,隐式欧拉法会把一个实际上增长的解压低。
练习
快速检查
(对 y′=2t、y(0)=0,以步长 h=1/2 用显式欧拉法计算 t=1 时的 y2,并与精确值比较。)
解答 · 答案
t0=0 和 t1=1/2 的斜率分别为 0 和 1,所以 y1=0+21⋅0=0、y2=0+21⋅1=1/2。精确解为 y=t2,在 t=1 的误差是 1/2。
快速检查
(对 y′=y、y(0)=1,以 h=1/2 计算两步隐式欧拉法,并与上面的显式结果 9/4 比较。)
每一步都是线性方程 yn+1=yn+hyn+1。
解答 · 答案
每步解 (1−h)yn+1=yn,而 1−h=1/2=0,得 y1=2、y2=4。显式结果 9/4 小于 e≈2.718,隐式结果 4 大于 e。这个增长模态没有被压低:当 hλ<1 时,隐式欧拉法不会抑制真正增长的解。
快速检查
(对 y′=−4y,哪些正实步长能使显式欧拉法让扰动衰减?非零边界处会发生什么?)
写出放大因子 1+hλ。
解答 · 答案
因子是 1−4h,不等式 ∣1−4h∣<1 等价于 0<h<1/2。在 h=1/2 时因子为 −1,扰动正负交替但不衰减。
快速检查
(设 f(t,y)=t 且初值精确,直接证明在 T=Nh 处显式欧拉法累积误差的绝对值是 Th/2。)
把左端点斜率 tn=nh 相加。
解答 · 答案
精确解是 y(t)=y0+t2/2;欧拉法把左端点相加,得到 yN=y0+h2n=0∑N−1n=y0+h2N(N−1)/2。从 y(T)=y0+N2h2/2 减去数值解,得 Nh2/2=Th/2。这里 L=0、M=1,定理的界 MtNh/2=Th/2 恰好取到等号。