欧拉法的误差分析
上一节中介绍了最简单、最直接、最基础的常微分方程的数值解法——欧拉法。 实际上它是在使用一系列的线段去逼近目标曲线。这是一种很粗糙的近似,可以想象如果迭代步长稍微大一点,误差就会增大。 而且每一步的误差都会累积下来,迭代次数多了之后,很有可能得到错误的结果。所以实际工程中很少使用这种方法。但是欧拉法的数学地位是无法取代的, 很多高级的算法都是从它派生出来的。
因为欧拉法足够精简,对它的误差分析相对方便一些。本节我们准备一些数学基础内容,形式化的给出欧拉法的误差上界。 总体上影响误差大小有三个方面的因素:迭代步长、曲线的曲率、累积误差。
1. 适定问题(Well-Posed Problem)
面对一个物理现象,为了研究它的规律,我们会构建微分方程。通过求解微分方程,我们可以推算出,在给定初始条件下,规律的演化过程。 再根据物理现象,设计各种实验得到观测值。对比理论结果和观测值,最终验证我们构建的微分方程是否合理。 实验观测是一定存在误差的。我们不想看到,微小的观测误差导致理论结果出现巨大偏差。在二十世纪初,数学家们提出了适定性问题(Well-Posed Problem), 用来评价一个数学模型是否稳定,适合求解。
如果区间 \(t \in [a,b]\) 上,初始状态 \(y(a) = \alpha\),如果一阶微分方程 \(\dot{y} = f(t,y)\) 满足如下条件,那么我们说它是适定的:
- 一定存在一个解 \(y(t)\),并且是唯一的。
- 存在常数 \(0 < \varepsilon_0\) 和系数 \(0 < k\)。对于任意 \(0 < \varepsilon < \varepsilon_0\),如果连续函数在区间 \([a,b]\) 上满足 \(|\delta(t)| < \varepsilon\), 那么 \(\dot{z} = f(t,z) + \delta(t)\) 的解 \(z(t)\) 在区间 \([a,b]\) 上都满足 \(|z(t) - y(t)| < k\varepsilon\)。
上述第一个条件没什么好说,如果不存在解或者解不唯一,就没有必要继续了。重点是第二个条件,它描述了一种稳定性。 大体意思就是给原问题增加一个小的扰动,并不会给解带来过大的影响,解的差异被控制在一个与扰动 \(\delta\) 上界的常数 \(k\) 倍。
可以证明,如果函数 \(f\) 连续并且满足 Lipschitz 条件,那么求解其微分方程就是一个适定问题。如果存在一个常数 \(L > 0\), 使得函数 \(f(t,y)\) 在区域 \(D \subset \mathbb{R}^2\) 上都有 $$ \left| f(t, y_1) - f(t, y_2) \right| ≤ L \left| y_1 - y_2 \right| $$ 其中 \((t,y_1), (t,y_2) \in D\)。那么我们说函数 \(f(t,y)\) 满足 Lipschitz 条件,\(L\) 被称为 \(f\) 的 Lipschitz 常数。
2. 欧拉法的误差上界
假设函数 \(f\) 在区域 \(D=\{(t,y) | a ≤ t ≤ b, -\infty < y < \infty \} \) 上连续, 并且微分方程 \(\dot{y} = f(t,y), a ≤ t ≤ b, y(a) = \alpha\) 满足常数为 \(L\) 的 Lipschitz 条件。 如果存在一个常数 \(M\) 使得 \(|\ddot{y}| ≤ M, \forall t \in [a,b]\)。那么通过欧拉法得到的每一步近似估计 \(w_0, \cdots, w_N\) 都有 $$ \begin{equation}\label{f1} |y(t_i) - w_i| ≤ \frac{hM}{2L}\left[ e^{L(t_i - a)} - 1 \right] \end{equation} $$
若欧拉法中迭代步长 \(h = t_{i+1} - t_i\),那么根据泰勒级数,对于 \(i = 0,1,\cdots,N-1\) 有:
$$ y(t_{i+1}) = y(t_i) + h f(t_i, y(t_i)) + \frac{h^2}{2}y''(\xi_i) $$而根据欧拉法的迭代公式,有:
$$ w_{i+1} = w_i + h f(t_i, w_i) $$对上述两式做差,根据三角不等式有:
$$ \left| y_{i+1} - w_{i+1} \right| ≤ \left| y_i - w_i \right| + h\left| f(t_i, y_i) - f(t_i, w_i) \right| + \frac{h^2}{2}\left| y''(\xi_i) \right| $$因为微分方程 \(\dot{y} = f(t,y), a ≤ t ≤ b, y(a) = \alpha\) 满足常数为 \(L\) 的 Lipschitz 条件, 并且存在一个常数 \(M\) 使得 \(|\ddot{y}| ≤ M, \forall t \in [a,b]\)。所以有
$$ \begin{equation}\label{f2} \left| y_{i+1} - w_{i+1} \right| ≤ (1 + hL) \left| y_i - w_i \right| + \frac{h^2M}{2} \end{equation} $$再继续证明之前,我们需要先看一个引理:
如果 \(\psi\) 和 \(\sigma\) 是两个正实数,数列 \(\{a_i\}_{i=0}^k\) 满足 \(-t/s ≤ a_0\) 并且 \(a_{i+1} ≤ (1 + \psi)a_i + \sigma\) 那么有
$$ \begin{equation}\label{f3} a_{i+1} ≤ e^{(i+1)\psi}\left(a_0 + \frac{\sigma}{\psi} \right) - \frac{\sigma}{\psi} \end{equation} $$将式(\(\ref{f3}\))套用到式(\(\ref{f2}\))上,有
$$ \left| y_{i+1} - w_{i+1} \right| ≤ e^{(i + 1)hL} \left( \left| y_0 - w_0 \right| + \frac{h^2M}{2hL} \right) - \frac{h^2M}{2hL} $$因为 \(|y_0 - w_0| = 0\) 且 \((i+1)h = t_{i+1} - t_0 = t_{i+1} - a\),代入上式有
$$ \left| y_{i+1} - w_{i+1} \right| ≤ \frac{hM}{2L} \left(e^{(t_{i+1} - a)L} - 1 \right) \qquad □ $$式(\(\ref{f1}\))就是欧拉法的误差上界。它由三部分组成,描述了现实中决定误差大小的三个因素:
- 迭代步长 \(h\): 全局误差与迭代步长 \(h\) 成正比关系。如果我们将步长缩小一半,那么误差上界也会缩小一半。
- 目标曲线的曲率 \(M\): \(M\) 是 \(y(t)\) 的二阶导数。如果 \(M\) 接近为 0,那么 \(y(t)\) 就会是一条平缓的直线,此时欧拉法基本不会有误差。 \(M\) 越大,曲线变化就越剧烈,直接用直线段来近似就会引入较大的误差。
- 累积误差 \(\left(e^{(t_{i+1} - a)L} - 1 \right)\): 随着迭代时间的 \(t_i\) 的增加,指数项会不断变大,说明误差会不断累积。
