Klapring

四种有限差分方法的数学推导

简介

本文默认读者对有限差分方法有一定了解,因此不做过多的前置知识介绍。考虑如下初值问题:

{𝑢′=𝑓(𝑡,𝑢),𝑡∈[0,𝑇]𝑢(0)=𝑢(0)

将 [0,𝑇] 划分为 𝑀 个等距区间,ℎ=𝑇𝑀,我们有以下几种有限差分格式用于求其数值解:

  1. 向前欧拉格式:

    𝑢(𝑛+1)=𝑢(𝑛)+ℎ𝑓(𝑡(𝑛),𝑢(𝑛)).
  2. 向后欧拉格式:

    𝑢(𝑛+1)=𝑢(𝑛)+ℎ𝑓(𝑡(𝑛+1),𝑢(𝑛+1)).
  3. 跃点(Leap frog)格式:

    𝑢(𝑛+1)=𝑢(𝑛−1)+2ℎ𝑓(𝑡(𝑛),𝑢(𝑛)).
  4. 梯形格式:

    𝑢(𝑛+1)=𝑢(𝑛)+ℎ𝑓(𝑡(𝑛),𝑢(𝑛))+𝑓(𝑡(𝑛+1),𝑢(𝑛+1))2.

接下来,对以上四种有限差分格式,我们将进行其准确性(Accuracy)与稳定性(Stability)的数学推导。

准确性推导

首先定义局部截断误差(Local Truncation Error)𝑅(𝑛),其定义为:其他点处的精确解在 𝑡(𝑛) 处按照差分格式计算得到的结果与 𝑡(𝑛) 处的精确解的差值。

警告:上述局部截断误差与通常定义的局部截断误差相差一个 ℎ,参考时请注意。

向前欧拉格式

向前欧拉格式的局部截断误差 𝑅(𝑛) 可表示为如下等式

𝑅(𝑛)=𝑢(𝑡(𝑛+1))−𝑢(𝑡(𝑛))ℎ−𝑢′(𝑡(𝑛)).

对 𝑢(𝑡(𝑛+1)) 进行 Taylor 展开有

𝑢(𝑡(𝑛+1))=𝑢(𝑡(𝑛))+ℎ𝑢′(𝑡(𝑛))+ℎ22𝑢″(𝜉(𝑛)),𝜉(𝑛)∈[𝑡(𝑛),𝑡(𝑛+1)].

于是有

𝑅(𝑛)=ℎ2𝑢″(𝜉(𝑛))=𝑂(ℎ),𝜉(𝑛)∈[𝑡(𝑛),𝑡(𝑛+1)].

误差 𝐸(𝑛) 可表示为如下形式:

𝐸(𝑛+1)−𝐸(𝑛)ℎ+𝑅(𝑛)=𝑓(𝑡(𝑛),𝑢(𝑡(𝑛)))−𝑓(𝑡(𝑛),𝑢(𝑛)).

令 𝑅=max𝑛|𝑅(𝑛)|,对误差 𝐸(𝑛) 有如下估计:

|𝐸(𝑛+1)|≤|𝐸(𝑛)|+ℎ𝑅+ℎ𝐿|𝑢(𝑡(𝑛))−𝑢(𝑛)|=(1+ℎ𝐿)|𝐸(𝑛)|+ℎ𝑅≤(1+ℎ𝐿)𝑛+1|𝐸(0)|+𝑅𝐿((1+ℎ𝐿)𝑛+1−1)≤𝑒𝐿𝑇|𝐸(0)|+𝑅𝐿(𝑒𝐿𝑇−1)≤𝑂(ℎ),𝑛=0,1,⋯,𝑀−1.

向后欧拉格式

向后欧拉格式的局部截断误差 𝑅(𝑛) 可表示为如下等式

𝑅(𝑛)=𝑢(𝑡(𝑛))−𝑢(𝑡(𝑛−1))ℎ−𝑢′(𝑡(𝑛)).

对 𝑢(𝑡(𝑛−1)) 进行 Taylor 展开有

𝑢(𝑡(𝑛−1))=𝑢(𝑡(𝑛))−ℎ𝑢′(𝑡(𝑛))+ℎ22𝑢″(𝜉(𝑛)),𝜉(𝑛)∈[𝑡(𝑛−1),𝑡(𝑛)].

于是有

𝑅(𝑛)=−ℎ2𝑢″(𝜉(𝑛))=𝑂(ℎ),𝜉(𝑛)∈[𝑡(𝑛−1),𝑡(𝑛)].

误差 𝐸(𝑛) 可表示为如下形式:

𝐸(𝑛)−𝐸(𝑛−1)ℎ−𝑅(𝑛)=𝑓(𝑡(𝑛),𝑢(𝑡(𝑛)))−𝑓(𝑡(𝑛),𝑢(𝑛)).

令 𝑅=max𝑛|𝑅(𝑛)|,假定 ℎ𝐿<1,对误差 𝐸(𝑛) 有如下估计:

|𝐸(𝑛)|≤(1−ℎ𝐿)−1|𝐸(𝑛−1)|+ℎ𝑅≤(1−ℎ𝐿)−𝑛|𝐸(0)|+𝑅𝐿(1−ℎ𝐿)((1−ℎ𝐿)−𝑛−1)<(1+ℎ𝐿1−ℎ𝐿)𝑛|𝐸(0)|+𝑅𝐿((1+ℎ𝐿1−ℎ𝐿)𝑛−1)≤exp(𝐿𝑇1−ℎ𝐿)|𝐸(0)|+𝑅𝐿(exp(𝐿𝑇1−ℎ𝐿)−1)≤𝑂(ℎ),𝑛=1,2,3,⋯,𝑀.

跃点格式

跃点格式的局部截断误差 𝑅(𝑛) 可表示为如下等式

𝑅(𝑛)=𝑢(𝑡(𝑛+1))−𝑢(𝑡(𝑛−1))2ℎ−𝑢′(𝑡(𝑛)).

对 𝑢(𝑡(𝑛−1)) 和 𝑢(𝑡(𝑛+1)) 进行 Taylor 展开有

𝑢(𝑡(𝑛−1))=𝑢(𝑡(𝑛))−ℎ𝑢′(𝑡(𝑛))+ℎ22𝑢″(𝜉1(𝑛)),𝜉1(𝑛)∈[𝑡(𝑛−1),𝑡(𝑛)].𝑢(𝑡(𝑛+1))=𝑢(𝑡(𝑛))+ℎ𝑢′(𝑡(𝑛))+ℎ22𝑢″(𝜉2(𝑛)),𝜉2(𝑛)∈[𝑡(𝑛),𝑡(𝑛+1)].

于是有

𝑅(𝑛)=ℎ4(𝑢″(𝜉1(𝑛))+𝑢″(𝜉2(𝑛)))=𝑂(ℎ),𝜉1(𝑛)∈[𝑡(𝑛−1),𝑡(𝑛)],𝜉2(𝑛)∈[𝑡(𝑛),𝑡(𝑛+1)].

误差 𝐸(𝑛) 可表示为如下形式:

𝐸(𝑛+1)−𝐸(𝑛−1)2ℎ−𝑅(𝑛)=𝑓(𝑡(𝑛),𝑢(𝑡(𝑛)))−𝑓(𝑡(𝑛),𝑢(𝑛)).

令 𝑅=max𝑛|𝑅(𝑛)|,对误差 𝐸(𝑛) 有如下估计:

|𝐸(𝑛+1)|≤|𝐸(𝑛−1)|+2ℎ𝐿|𝐸(𝑛)|+2ℎ𝑅.

令 𝜇=1+ℎ2𝐿2−ℎ𝐿,𝜆=1+ℎ2𝐿2+ℎ𝐿,则 𝜇𝜆=1,且 𝜆−𝜇=2ℎ𝐿。于是上式可改写为如下形式:

|𝐸(𝑛+1)|+𝜇|𝐸(𝑛)|≤𝜆(|𝐸(𝑛)|+𝜇|𝐸(𝑛−1)|)+2ℎ𝑅≤⋯≤𝜆𝑛(|𝐸(1)|+𝜇|𝐸(0)|)+𝜆𝑛−1𝜆−12ℎ𝑅≤(1+2ℎ𝐿)𝑛(|𝐸(1)|+𝜇|𝐸(0)|)+(1+2ℎ𝐿)𝑛−1𝜆−12ℎ𝑅≤𝑒2𝐿𝑇(|𝐸(1)|+𝜇|𝐸(0)|)+𝑒2𝐿𝑇−1𝜆−12ℎ𝑅.

不妨假定上式中的 𝐸(1)=𝑢(𝑡(1))−𝑢(1) 是由向前欧拉格式得到的,注意到 ℎ→0 时 ℎ𝜆−1→1𝐿,于是有

|𝐸(𝑛+1)|≤|𝐸(𝑛+1)|+𝜇|𝐸(𝑛)|≤𝑂(ℎ),𝑛=1,2,3,⋯,𝑀−1.

梯形格式

梯形格式的局部截断误差 𝑅(𝑛) 可表示为如下等式

𝑅(𝑛)=𝑢(𝑡(𝑛+1))−𝑢(𝑡(𝑛))ℎ−𝑢′(𝑡(𝑛+1))+𝑢′(𝑡(𝑛))2.

对 𝑢(𝑡(𝑛+1)) 和 𝑢′(𝑡(𝑛+1)) 进行 Taylor 展开有

𝑢(𝑡(𝑛+1))=𝑢(𝑡(𝑛))+ℎ𝑢′(𝑡(𝑛))+ℎ22𝑢″(𝑡(𝑛))+ℎ36𝑢‴(𝜉1(𝑛)),𝜉1(𝑛)∈[𝑡(𝑛),𝑡(𝑛+1)].𝑢′(𝑡(𝑛+1))=𝑢′(𝑡(𝑛))+ℎ𝑢″(𝑡(𝑛))+ℎ22𝑢‴(𝜉2(𝑛)),𝜉2(𝑛)∈[𝑡(𝑛),𝑡(𝑛+1)].

于是有

𝑅(𝑛)=ℎ212(2𝑢‴(𝜉1(𝑛))−3𝑢‴(𝜉2(𝑛)))=𝑂(ℎ2),𝜉1(𝑛)∈[𝑡(𝑛),𝑡(𝑛+1)],𝜉2(𝑛)∈[𝑡(𝑛),𝑡(𝑛+1)].

误差 𝐸(𝑛) 可表示为如下形式:

𝐸(𝑛+1)−𝐸(𝑛)ℎ−𝑅(𝑛)=𝑓(𝑡(𝑛+1),𝑢(𝑡(𝑛+1)))+𝑓(𝑡(𝑛),𝑢(𝑡(𝑛)))2−𝑓(𝑡(𝑛+1),𝑢(𝑛+1))+𝑓(𝑡(𝑛),𝑢(𝑛))2.

令 𝑅=max𝑛|𝑅(𝑛)|,假定 ℎ𝐿<2,对误差 𝐸(𝑛) 有如下估计:

|𝐸(𝑛+1)|≤|𝐸(𝑛)|+ℎ𝐿2(|𝐸(𝑛+1)|+|𝐸(𝑛)|)+ℎ𝑅.|𝐸(𝑛)|≤2+ℎ𝐿2−ℎ𝐿|𝐸(𝑛−1)|+2ℎ𝑅2−ℎ𝐿≤(2+ℎ𝐿)𝑛(2−ℎ𝐿)𝑛|𝐸(0)|+𝑅𝐿((2+ℎ𝐿)𝑛(2−ℎ𝐿)𝑛−1)≤exp(2𝐿𝑇2−ℎ𝐿)|𝐸(0)|+𝑅𝐿(exp(2𝐿𝑇2−ℎ𝐿)−1)≤𝑂(ℎ2),𝑛=1,2,3,⋯,𝑀.

稳定性推导

考虑模型问题

d𝑢d𝑡=𝜆𝑢,

其中 𝜆 为常数。定义 𝜀(𝑛) 为舍入误差,𝑧=ℎ𝜆。我们称差分格式的绝对稳定区域(Absolute Stability Region)为复平面上所有使差分格式的解稳定的 𝑧 的集合。

向前欧拉格式

将格式代入模型问题可得

𝑢(𝑛+1)=(1+ℎ𝜆)𝑢(𝑛).

考虑到舍入误差,我们有 𝑢̄(𝑛) 而非 𝑢(𝑛):

𝑢̄(𝑛+1)=𝑢̄(𝑛)+ℎ𝜆𝑢̄(𝑛)+𝜀(𝑛).

误差 𝐸(𝑛)≔𝑢̄(𝑛)−𝑢(𝑛) 满足

𝐸(𝑛+1)=𝐸(𝑛)+ℎ𝜆𝐸(𝑛)+𝜀(𝑛)=⋯=(1+ℎ𝜆)𝑛+1𝐸(0)+(1+ℎ𝜆)𝑛𝜀(0)+⋯+𝜀(𝑛).

假设 𝜀(𝑛)<𝜀,若 |1+ℎ𝜆|<1,则有

|𝐸(𝑛+1)|≤|1+ℎ𝜆|𝑛+1|𝐸(0)|+|1+ℎ𝜆|𝑛+1+1|ℎ𝜆|𝜀→𝑐𝜀,

其中 𝑐 为常数,所以本格式的绝对稳定区域为 |1+𝑧|<1。

向后欧拉格式

将格式代入模型问题可得

𝑢(𝑛)=(1−ℎ𝜆)𝑢(𝑛+1).

考虑到舍入误差,我们有 𝑢̄(𝑛) 而非 𝑢(𝑛):

𝑢̄(𝑛+1)=𝑢̄(𝑛)+ℎ𝜆𝑢̄(𝑛+1)+𝜀(𝑛).

误差 𝐸(𝑛)≔𝑢̄(𝑛)−𝑢(𝑛) 满足

𝐸(𝑛+1)=𝐸(𝑛)+ℎ𝜆𝐸(𝑛+1)+𝜀(𝑛)=(1−ℎ𝜆)−1𝐸(𝑛)+(1−ℎ𝜆)−1𝜀(𝑛)=⋯=(1−ℎ𝜆)−(𝑛+1)𝐸(0)+(1−ℎ𝜆)−(𝑛+1)𝜀(0)+⋯+(1−ℎ𝜆)−1𝜀(𝑛).

假设 𝜀(𝑛)<𝜀,若 |1−ℎ𝜆|>1,则有

|𝐸(𝑛+1)|≤|1−ℎ𝜆|−(𝑛+1)|𝐸(0)|+|1−ℎ𝜆|−𝑛+1|ℎ𝜆|𝜀→𝑐𝜀,

其中 𝑐 为常数,所以本格式的绝对稳定区域为 |1−𝑧|>1。

跃点格式

将格式代入模型问题可得

𝑢(𝑛+1)=𝑢(𝑛−1)+2ℎ𝜆𝑢(𝑛).

考虑到舍入误差,我们有 𝑢̄(𝑛) 而非 𝑢(𝑛):

𝑢̄(𝑛+1)=𝑢̄(𝑛−1)+2ℎ𝜆𝑢̄(𝑛)+𝜀(𝑛−1).

误差 𝐸(𝑛)≔𝑢̄(𝑛)−𝑢(𝑛) 满足

𝐸(𝑛+1)+𝛼𝐸(𝑛)=1𝛼(𝐸(𝑛)+𝛼𝐸(𝑛−1))+𝜀(𝑛−1)=⋯=1𝛼𝑛(𝐸(1)+𝛼𝐸(0))+1𝛼𝑛−1𝜀(0)+⋯+𝜀(𝑛−1),

其中 𝛼=(ℎ2𝜆2+1)12−ℎ𝜆,多值函数 𝑧12 取将正数映射到正数的解析分支。随后我们有

𝐸(𝑛+1)=𝛼−𝑛(𝐸(1)+𝛼𝐸(0))+∑𝑘=0𝑛−1𝛼𝑘−(𝑛−1)𝜀(𝑘)−𝛼𝐸(𝑛)=⋯=(−1)𝑛−1𝑎𝑛+𝑎−𝑛𝑎2+1(𝐸(1)+𝛼𝐸(0))+∑𝑘=0𝑛−1(−1)𝑛−1−𝑘𝑎𝑛+1−𝑘+𝛼𝑘−(𝑛−1)𝑎2+1𝜀(𝑘)+(−1)𝑛𝛼𝐸(1).

假设 𝜀(𝑛)<𝜀,若 |1+ℎ𝜆|>1,则有

|𝐸(𝑛+1)|≤|𝛼|𝑛+|𝛼|−𝑛|𝛼2+1||𝐸(1)+𝛼𝐸(0)|+|𝛼||𝐸(1)|+|𝑎||𝛼2+1|(|𝛼𝑛+1||𝛼−1+1|+|𝛼−𝑛−1||𝛼−1|)𝜀.

上式同时出现 |𝛼|𝑛 与 |𝛼|−𝑛,所以仅 |𝛼|=1 时跃点格式稳定。令 𝑧=𝑎+𝑏𝑖 有

|𝛼|2=(𝑟cos𝜃−𝑎)2+(𝑟sin𝜃−𝑏)2=𝑟+𝑎2+𝑏2−2𝑟(𝑎cos𝜃+𝑏sin𝜃)=1,

其中

𝑟=(𝑎2−𝑏2+1)2+4𝑎2𝑏2,𝜃=arctan(2𝑎𝑏𝑎2−𝑏2+1)2.

注意到仅 𝑎=0 且 |𝑏|≤1 时上式成立,所以跃点格式的绝对稳定区域为 𝑧=𝑏𝑖,𝑏∈[−1,1]。

梯形格式

将格式代入模型问题可得

𝑢(𝑛+1)=𝑢(𝑛)+ℎ𝜆2(𝑢(𝑛)+𝑢(𝑛+1)).

考虑到舍入误差,我们有 𝑢̄(𝑛) 而非 𝑢(𝑛):

𝑢̄(𝑛+1)=𝑢̄(𝑛)+ℎ𝜆2𝑢̄(𝑛)+ℎ𝜆2𝑢̄(𝑛+1)+𝜀(𝑛).

误差 𝐸(𝑛)≔𝑢̄(𝑛)−𝑢(𝑛) 满足

𝐸(𝑛+1)=𝐸(𝑛)+ℎ𝜆2𝐸(𝑛)+ℎ𝜆2𝐸(𝑛+1)+𝜀(𝑛)=2+ℎ𝜆2−ℎ𝜆𝐸(𝑛)+22−ℎ𝜆𝜀(𝑛)=⋯=(2+ℎ𝜆)𝑛+1(2−ℎ𝜆)𝑛+1𝐸(0)+(2+ℎ𝜆)𝑛(2−ℎ𝜆)𝑛+12𝜀(0)+⋯+22−ℎ𝜆𝜀(𝑛).

假设 𝜀(𝑛)<𝜀,令 𝑧=𝑎+𝑏𝑖,若 𝑎<0,则有

|𝐸(𝑛+1)|≤|(2+ℎ𝜆)𝑛+1||(2−ℎ𝜆)𝑛+1||𝐸(0)|+(|(2+ℎ𝜆)𝑛+1||(2−ℎ𝜆)𝑛+1|−1)→𝑐𝜀,

其中 𝑐 为常数,所以本格式的绝对稳定区域为 Re(𝑧)<0。

计算复杂性

记 𝑛=𝑇ℎ。

对于递推式中不含 𝑓(𝑡(𝑛+1),𝑢(𝑛+1)) 的差分格式,其求解全部 𝑢(𝑛) 只需进行 𝑛 次计算,即计算复杂度为 𝑂(𝑛)。

反之对于递推式中含有 𝑓(𝑡(𝑛+1),𝑢(𝑛+1)) 的差分格式,其计算每一个 𝑢(𝑛) 时都需要求解隐函数零点,这一过程是 𝑂(log𝑛) 的,因此整个求解过程的计算复杂度为 𝑂(𝑛log𝑛)。

数值实验

以下面的例子对四种差分格式进行数值实验。

{𝑢′(𝑡)=𝑓(𝑡,𝑢(𝑡))=−cos(5𝜋𝑡)tan(5𝜋𝑢)𝑢(0)=1/60.

其中 𝑡∈[0,1]。

上述初值问题的解析解为

𝑢(𝑡)=15𝜋arcsin(6−24exp(sin(5𝜋𝑡))).

网格宽度 ℎ=0.01 时,使用差分格式求解上述初值问题,可得如下图表:

对比五种数值方法(u(t)、FE、BE、LF、Tz)在 t=0 到 1 间计算结果的图像。BE 曲线升至 0.1 后保持水平;u(t)、LF、Tz 曲线基本重合,有两个波峰,LF 曲线呈锯齿状;FE 曲线走势相似但峰值较低。
图 1 数值实验结果

结论

由上述数值实验的实验结果,可以看出虽然向前 Euler 格式、向后 Euler 格式和跃点格式的准确性都是 𝑂(ℎ) 的,但是跃点格式的实际准确性明显优于向前 Euler 格式和向后 Euler 格式。

而准确性为 𝑂(ℎ2) 的梯形格式则明显优于所有准确性为 𝑂(ℎ) 的差分格式。

附录

向前欧拉格式:

function [x, result] = forward_euler(T, step, u0, f)
x = linspace(0, T, step + 1);
h = T / step;
result = zeros(1, step + 1);
result(1) = u0;
for k = 2:step + 1
result(k) = result(k - 1) + h * f(x(k - 1), result(k - 1));
end
end

向后欧拉格式:

function [x, result] = backward_euler(T, step, u0, f)
x = linspace(0, T, step + 1);
h = T / step;
result = zeros(1, step + 1);
result(1) = u0;
for k = 2:step + 1
temp_func = @(uk) result(k - 1) + h * f(x(k), uk) - uk;
result(k) = fzero(temp_func, result(k - 1));
end
end

跃点格式:

function [x, result] = leap_frog(T, step, u0, u1, f)
x = linspace(0, T, step + 1);
h = T / step;
result = zeros(1, step + 1);
result(1) = u0;
result(2) = u1;
for k = 3:step + 1
result(k) = result(k - 2) + 2 * h * f(x(k - 1), result(k - 1));
end
end

梯形格式:

function [x, result] = trapezoidal(T, step, u0, f)
x = linspace(0, T, step + 1);
h = T / step;
result = zeros(1, step + 1);
result(1) = u0;
for k = 2:step + 1
temp_func = @(uk) result(k - 1) - uk + ...
h * (f(x(k), uk) + f(x(k - 1), result(k - 1))) / 2;
result(k) = fzero(temp_func, result(k - 1));
end
end