动机
微分方程在每一瞬间描述变化率,电脑却只能存储有限个数值。数值积分把连续演化转成时间网格上的递推式。不过,一串看来平滑的数值本身不是误差保证;我们必须说明它与原方程的解有什么关系。
考虑初值问题
y′(t)=f(t,y(t)),y(0)=y0,0≤t≤T.
未知量可以是 Rd 中的向量。以下假设经典解在整段区间存在;若解可能在有限时间爆破,这项存在性必须另行检查。在一个网格点,微分方程给出切向量。沿此方向走一小段时间便得到前向 Euler 方法。关键是连续走很多步后会怎样,因为后来的切向量是在近似状态上计算的。
误差有两个来源。即使从精确解出发,切线也会偏离弯曲的解轨迹;而起点的扰动又可能改变后续数值。相容性量度前者,对扰动的稳定性控制后者。收敛证明把两者结合。这套分工也适用于 Runge–Kutta 方法及偏微分方程的时间离散。
定义
定义 1.1.1
(前向 Euler、整体误差与单步缺陷)
取正整数 N,令 h=T/N、tn=nh。前向 Euler 方法为
Y0=y0,Yn+1=Yn+hf(tn,Yn),0≤n<N.大写 Yn 是近似值,小写 y(tn) 是精确值。固定 Rd 上的一个范数,定义整体误差 en=y(tn)−Yn。固定终点的误差,与只走一步所产生的误差,是不同的量。
把精确解代入方法,定义未缩放的单步缺陷
dn+1=y(tn+1)−y(tn)−hf(tn,y(tn)),以及缩放后的缺陷 τn+1=dn+1/h。不同教材可能把其中任何一个称为局部截断误差,因此使用名称时要说清楚约定。以下假设下,Euler 方法有 dn+1=O(h2),而 τn+1=O(h);幂次相差一是因为定义不同。
定义 1.1.2
(收敛阶与 Lipschitz 条件)
记号 ah=O(hp) 表示存在与网格大小无关的正常数 C,h0,使 0<h≤h0 时有 ∥ah∥≤Chp。对误差序列而言,一致估计要求同一常数适用于固定时间 T 前的所有网格点。一阶收敛估计写成
0≤n≤Nmax∥en∥≤CTh.常数可以依赖方程和 T,但不能暗中随 N=T/h 增长。证明使用状态变量的 Lipschitz 条件:对所有 t∈[0,T] 及 u,v∈Rd,
∥f(t,u)−f(t,v)∥≤L∥u−v∥,L≥0.这里采用全局条件,免去数值轨迹是否留在某个较小区域的额外证明。若只知道局部条件,必须同时控制精确轨迹与所有数值状态的位置。
概念视角分析
把 Euler 看成左端点求积法则
把方程在一步上积分,得到精确恒等式
y(tn+1)=y(tn)+∫tntn+1f(s,y(s))ds.前向 Euler 用左矩形 hf(tn,Yn) 代替这个积分,并把被积函数冻结在计算状态上。缺陷 dn+1 恰好是矩形法则对被积函数 y′(s) 的求积误差;用 Yn 代替 y(tn) 带来的额外变化,则由 Lipschitz 常数控制。当 f 不依赖 y 时,Euler 正是左 Riemann 和。
定理/命题
若 y∈C2([0,T];Rd),而整段区间满足 ∥y′′(t)∥≤M,则每一步都有 ∥dn+1∥≤Mh2/2。
设 f 连续,对状态变量全局 Lipschitz,常数为 L≥0;精确解 y∈C2 且 ∥y′′∥≤M。初值精确时,若 L>0,则
∥en∥≤2LMh((1+hL)n−1)≤2LMh(eLtn−1).若 L=0,则 ∥en∥≤Mtnh/2。所以当 h→0,Euler 方法在固定区间的所有网格点上一致收敛。
证明思路
两次使用微积分基本定理,得到积分形式的 Taylor 展开:
y(t+h)=y(t)+hy′(t)+∫tt+h(t+h−s)y′′(s)ds.代入 y′=f(t,y),余下的积分就是缺陷。权重 t+h−s 的积分为 h2/2,取范数便得第一个命题。这个向量证明不需要假设所有分量共享同一个 Taylor 中间点。
把数值递推式从精确恒等式相减:
en+1=en+h(f(tn,y(tn))−f(tn,Yn))+dn+1.因此
∥en+1∥≤(1+hL)∥en∥+Mh2/2.由 e0=0 反复代入,出现等比级数。L>0 时其和为 ((1+hL)n−1)/(hL);L=0 时为 n。再使用 1+x≤ex,便得所述估计。这是最坏情况的上界,并没有声称每一步误差实际上都沿同一方向相加。
证明透视
两个假设在哪里起作用
光滑性只用了一次,就在缺陷命题中,而且只沿精确解使用:积分形式的 Taylor 公式把 ∥y′′∥≤M 化成 ∥dn+1∥≤Mh2/2。Lipschitz 条件也只用了一次,用来比较精确状态与计算状态上的斜率 f(tn,y(tn))、f(tn,Yn);这个比较产生放大因子 1+hL。由于条件是全局的,无须另证 Yn 留在局部常数有效的区域内。
关键一步是以标量不等式 ∥en+1∥≤(1+hL)∥en∥+Mh2/2 取代向量递推,并把它当作等比级数精确求解。约有 T/h 个大小为 h2 的缺陷被加入,每个至多被放大 (1+hL)n≤eLT 倍,这个因子与 h 无关。若不计此因子,只把局部缺陷乘以步数,便忽略了放大作用,算不上证明。没有 Lipschitz 界,这个因子根本无法建立;“常见错误”中的反例显示结论此时可以失效。
若初始误差不超过 ε,误差界须加上 (1+hL)nε。若每一步另有加性扰动 ρj+1,其累积贡献不超过
j=0∑n−1(1+hL)n−1−j∥ρj+1∥.
这个公式可用来分析已指定模型下的舍入或求解误差。若每步的绝对扰动不随步长下降,无限缩小步长便不保证浮点结果无限改善。
例题详解
对 y′=−y、y(0)=1,有 Yn=(1−h)n。取 h=1/4,依次得到 1,0.75,0.5625,0.421875,0.31640625。在 T=1,精确值为 e−1≈0.36787944,故有号误差约为 0.05147319。
这里 L=1、∣y′′∣≤1,定理给出较宽的上界 (e−1)/8≈0.21478523。上界不是对实际误差的预测。取 h=1/8,得到 Y8≈0.34360892,误差约为 0.02427052;两误差之比约为 2.12,接近一阶收敛所预期的两倍关系。
对 y′=2t、y(0)=0,精确解为 t2,每步缺陷恰为 h2。直接求和得
Yn=2h2j=0∑n−1j=h2n(n−1),en=nh2=tnh.因 f 不依赖状态,可以取 L=0,而 M=2。定理的界 Mtnh/2 恰好等于真实误差。虽然没有旧误差的放大,新缺陷仍会累积;单步的 h2 与终点的 Th 必须区分。
仍考虑 y′=−y、y(0)=1,要求 [0,1] 每个网格点的绝对误差不超过 0.01。充分条件为 h(e−1)/2≤0.01,即 h≤0.02/(e−1)≈0.0116395。取 N=86,上界约为 0.00999001。
这是有证明的充分步数,未必最少。Lipschitz 界没有利用解的衰减,因而偏保守。较粗网格的实验也可能符合容许误差,但实验观察与理论保证的逻辑地位不同。
细化实验及其局限
若不知道精确解,可以在共同终点比较 h,h/2,h/4。假设存在展开 Yh=y(T)+Ch+O(h2) 且 C=0,则相邻差值的比趋近二。单次观察到接近二的比值只是证据,并非所有分量都已进入渐近区间的证明。若首项系数消失,比值也可能不同。
在上述展开下,2Yh/2−Yh 可消去一阶项。不过,仅有一个 O(h) 误差界,不足以推出此展开;外推的理由需要更强假设。应区分定理已证明的内容与实验采用的误差模型。
取得常数而非假设常数
常数也应从方程取得。若 f 有连续一阶偏导,沿解有 y′′=ft+Dyff。在包含精确轨迹的区域上控制这三项,便可估计 M,不必先知道解的公式。微分不等式、守恒量或先验界有时能提供该区域。若区域尚未证实,任意指定一个 M 并不能完成保证。
在凸区域内,沿两状态之间的线段积分 Jacobian,可由 Dyf 的算子范数界推出 Lipschitz 条件。矩阵各元素的界可以转成算子范数界,但常数依赖所选范数与维数。证明中途混用最大范数与欧氏范数而不调整常数,可能令数值保证失效。
误差递推式也可以用归纳法仔细核对。第一步只有新缺陷;第二步包含被放大一次的第一个缺陷,以及刚加入的第二个缺陷。到第几步,较早的缺陷便经历较多次传播。取范数和三角不等式会失去正负抵销的信息,这正是上界有时远大于观察误差的原因。若要利用衰减方向或误差抵销,必须提出额外结构,不能在一般证明中直接假设它们存在。
实际报告结果时,应同时记录步数与终点。比较两个网格的终点值之前,先确认它们对应相同时间;若使用整数步数截断到较早时间,差值便同时混入时间位置的差异。若最后一步特别缩短以到达指定终点,可用下面的非均匀步长分析,而不是把最后一段仍当作原来的步长。这些记录让细化实验与理论中的固定时间比较保持一致。
非均匀步长
等距网格并非必要。设正步长 hj=tj+1−tj 的总和为 T,最大步长为 H。每步使用实际的 hj,缺陷界为 Mhj2/2。误差传播因子是若干个 1+Lhj 的乘积,最多为 eLT。又因 j∑hj2≤Hj∑hj=HT,所以初值精确时有
nmax∥en∥≤MeLTTH/2.
此界虽不如均匀网格的等比级数界锐利,却说明只要最大步长趋零便收敛。大量极小步不能抵销保留一个大步的影响。以局部缺陷选步长,也仍须考虑整体误差的传播。
一阶保证容许某些问题更精确。当 f 为常数,Euler 在所有网格点都精确;某些问题的首项误差也可能在特定终点消失。阶数描述假设下的一般速率,不是每次把步长减半都必然令任何误差恰好减半。
常见错误
相容性必须沿精确解计算。把缺陷中的 y(tn) 换成 Yn,所得已是另一种残差或误差表达式,Taylor 论证并不控制它。
常见错误
(因缺陷为 O(h2) 而称 Euler 为二阶)
未缩放缺陷 dn+1 为 O(h2),缩放缺陷 τn+1 为 O(h)。方法的阶数指整体误差的阶数,与 τ 相同:约 T/h 个大小 h2 的缺陷累积成 O(h);精确例子 y′=2t 正好给出 en=tnh。
固定 T 的收敛定理在 T→∞ 时并不一致。对 y′=−y,误差界按 eT 增长,但解与实际误差都在衰减。衰减、振荡、守恒和长时间行为需要更细致的稳定性分析。
Taylor 证明还需要解在整个区间足够光滑,而非只在部分区域有一条看似可微的公式。
反例模式
没有 Lipschitz 条件,误差未必趋零
有人以为 f 连续且解光滑便已足够。考虑 [0,1] 上的 y′=2∣y∣、y(0)=0。函数 y(t)=t2 是解,因为 y′=2t=2t2;它属于 C2 且 ∣y′′∣=2。然而 Euler 每一步都算出 Yn+1=Yn+2h∣Yn∣=0,所以对每个 h 都有 eN=y(1)−YN=1。同一初值还有解:t≤a 时为 0、t≥a 时为 (t−a)2,每个 a≥0 各一个,因此根本没有唯一的解可供逼近。右端在零附近不满足 Lipschitz 条件:u→0 时 ∣2∣u∣−0∣/∣u∣→∞。恢复 Lipschitz 常数后,唯一性与误差界便重新成立。
总结
Euler 使用左端点的向量场。二阶导数有界给出 Mh2/2 的单步缺陷;Lipschitz 条件控制旧误差的传播,得到固定区间上一阶的整体误差。有效的误差声明应列明范数、初值精度、光滑性、时间区间及缺陷的缩放约定。
练习
快速检查
(对 y′=y+t、y(0)=1,用步长 1/2 走两步。求 Y1,Y2 及 t=1 的有号误差;已知 y(t)=2et−t−1。)
解答 · 答案
初始斜率为 1,所以 Y1=1.5。在 t1=0.5,斜率为 1.5+0.5=2,故 Y2=2.5。精确值为 2e−2,所以 e2=2e−4.5≈0.93656366。把新状态与旧时间混用会变成另一方法。
快速检查
(对 y′=3t2、y(0)=0,求精确单步缺陷,并直接证明 [0,1] 终点误差是一阶。)
使用 y=t3 与整数平方和公式。
解答 · 答案
缺陷为 (tn+h)3−tn3−3htn2=3tnh2+h3。令 N=1/h,直接求和得 YN=3h3(N−1)N(2N−1)/6=1−3h/2+h2/2。故 eN=3h/2−h2/2,确为一阶。一般定理取 M=6、L=0 也给出有效的较宽界 3h。
快速检查
(设 L=2、M=3、T=1、初始误差不超过 10−4、h=0.01。给出包含两种贡献的整体误差界。)
解答 · 答案
所需界为 e210−4+(3×0.01/4)(e2−1)≈0.04865683。第一项约为 0.00073891,第二项约为 0.04791792。忽略第一项便等于擅自假设初值完全精确。