Partial Differential Equation (PDE) solving is an important part of numerical analysis in mathematical finance. The classical approach to solve PDE that appears in finance is to use finite difference method. As most of numerical analysis problems, the goal is to find a solution with an error that converges quickly.

The academic way to achieve this goal is to use Crank-Nicolson to solve our PDE, which provides an “order 2” discretisation scheme in time. However, it appears that in practice, Crank-Nicolson is not that good, especially in the absence of regular initial conditions, and produces some spurious oscillations. The goal of this article is to provide a scheme that is also at “order 2” in time, but which does not produce oscillations.

To that, I will work on a simple case that is easily generalisable. In a first part, I will provide some reminders about finite difference methods for PDE and convergence order. Then, I will explain why Crank-Nicolson can produce such oscillations. Our oscillation free scheme will be presented in the last part.

Before we start, I would like to precise that this article is not about spatial discretisation and boundary conditions.

Reminders about finite difference

The framework

Let E⊂R\mathbb E \subset \mathbb R, F(n)={f,f:R+×En→Rn}\mathcal F (n) = \{f, f: \mathbb R ^ + \times \mathbb E^n \rightarrow \mathbb R^n\}.

In this article, I will work on PDE of the following form:

(∗){∀(t,x)∈R+×E,∂tu(t,x)=a(t,x)∂x2u(t,x)+b(t,x)∂xu(t,x)+c(t,x)u(t,x)∀x∈Eu(0,x)=f(x) (*)\left \{ \begin{array}{lrl} \forall (t, x) \in \mathbb R ^ + \times \mathbb E,& \partial_t u (t, x) & \hspace{-5pt} = a(t, x) \partial^2_x u(t, x) + b(t, x) \partial_x u(t, x) + c(t, x) u(t, x)\\ \forall x \in \mathbb E & u(0, x) & \hspace{-5pt} = f(x) \end{array} \right.

where aa, bb and c∈F(1)c \in \mathcal F(1), a≥0a \geq 0 and f:E→Rf: \mathbb E \rightarrow \mathbb R.

We introduce the following convention: let f∈F(1)f\in \mathcal F(1), we define

fn:R+×En→Rnt,x↦(f(t,x0),…,f(t,xn−1))T \begin{align*} f_n: \mathbb R ^ + \times \mathbb E ^ n & \rightarrow \mathbb R^n\\ t, x & \mapsto (f(t, x_0), \ldots , f(t, x_{n - 1})) ^ T \end{align*}

and also extend the partial differentiation operators to fn∈F(n)f_n \in \mathcal F (n):

∂tfn(t,x)=(∂tf(t,x0),…,∂tf(t,xn−1))T∂xfn(t,x)=(∂xf(t,x0),…,∂xf(t,xn−1))T \begin{align*} \partial_t f_n (t, x) & = (\partial_t f (t, x_0), \ldots , \partial_t f (t, x_{n - 1}))^T\\ \partial_x f_n (t, x) & = (\partial_x f (t, x_0), \ldots , \partial_x f (t, x_{n - 1}))^T\\ \end{align*}

(∗)(*) is then equivalent to:

{∀(t,x)∈R+×En,∂tun(t,x)=an(t,x)TIn∂x2un(t,x)+bn(t,x)TIn∂xun(t,x)+cn(t,x)TInun(t,x)∀x∈E,u(0,x)=f(x) \left \{ \begin{array}{lrl} \forall (t, x) \in \mathbb R ^ + \times \mathbb E^n,& \partial_t u_n (t, x) & \hspace{-5pt} = a_n(t, x)^T I_n \partial^2_x u_n(t, x) + b_n(t, x)^T I_n \partial_x u_n(t, x)\\ && + c_n(t, x)^T I_n u_n(t, x)\\ \forall x \in \mathbb E, & u(0, x) & \hspace{-5pt} = f(x) \end{array} \right.

The first line can be rewritten ∂tun=Lnun\partial_t u_n = \mathcal L_n u_n. To simplify notations, we will mix up both notations when there is no ambiguities.

The method

Our goal is to compute u(T,x)u(T, x) for a particular T∈R+T \in \mathbb R^+. To that, we will in a first step time discretise the problem. Let (nx,nt)∈N2(n_x, n_t) \in \mathbb N^2, (xmin,xmax)∈E2(x_{min}, x_{max}) \in \mathbb E^2, δx=(xmax−xmin)/(nx−1)\delta x = (x_{max} - x_{min})/(n_x - 1) and δt=T/(nt−1)\delta t = T/(n_t - 1). We define x∈Enx \in \mathbb E^n, t∈R+t \in \mathbb R^+ by ∀i∈[0;nx−1],xi=xmin+iδx\forall i \in [0; n_x - 1], x_i = x_{min} + i \delta x and ∀i∈[0;nt−1],ti=iδt\forall i \in [0; n_t - 1], t_i = i \delta t

Spatial discretisation

The first step consists in discretising the operator Lnx\mathcal L_{n_x}. To that, we approximate the spatial partial derivatives with finite differences:

∀i∈[1;nx−2],∂xu(t,xi)=u(t,xi+1)−u(t,xi−1)2δx+O(δx2)∂x2u(t,xi)=u(t,xi+1)−2u(t,xi)+u(t,xi−1)δx2+O(δx2) \begin{align*} \forall i \in [1; n_x - 2], &\\ \partial_x u (t, x_i) & = \frac{u (t, x_{i + 1}) - u(t, x_{i - 1})}{2\delta x} + O (\delta x^2)\\ \partial^2_x u (t, x_i) & = \frac{u (t, x_{i + 1}) - 2u(t, x_i) + u(t, x_{i - 1})}{\delta x^2} + O (\delta x^2)\\ \end{align*}

thus

∀i∈[1;nx−2],∂tu(t,xi)=a(t,xi)u(t,xi+1)−2u(t,xi)+u(t,xi−1)δx2+b(t,xi)u(t,xi+1)−u(t,xi−1)2δx+c(t,xi)u(t,xi)+O(δx2)=(a(t,xi)δx2−b(t,xi)2δx)u(t,xi−1)+(c(t,xi)−2a(t,xi)δx2)u(t,xi)+(a(t,xi)δx2+b(t,xi)2δx)u(t,xi+1)+O(δx2) \begin{align*} \forall i \in [1; n_x - 2], &\\ \partial_t u(t, x_i) & = a(t, x_i) \frac{u (t, x_{i + 1}) - 2u(t, x_i) + u(t, x_{i - 1})}{\delta x^2} + b(t, x_i) \frac{u (t, x_{i + 1}) - u(t, x_{i - 1})}{2\delta x}\\ & + c(t, x_i) u(t, x_i) + O (\delta x^2)\\ & = \left(\frac{a(t, x_i)}{\delta x ^ 2} - \frac{b(t, x_i)}{2\delta x}\right)u(t, x_{i - 1}) + \left(c(t, x_i) - 2 \frac{a(t, x_i)}{\delta x ^ 2} \right)u(t, x_i)\\ & + \left(\frac{a(t, x_i)}{\delta x ^ 2} + \frac{b(t, x_i)}{2\delta x}\right)u(t, x_{i + 1}) + O (\delta x^2) \end{align*}

Now, we have to discretise in the boundary. To that, we assume that ∂x2u(t,x0)=∂x2u(t,xnx−1)=0\partial^2_xu(t, x_0) = \partial^2_xu(t, x_{n_x - 1}) = 0 (I take simple boundary conditions, as this is not the purpose of this article). We can write:

∂xu(t,x0)=u(t,x1)−u(t,x0)δx+O(δx),∂xu(t,xnx−1)=u(t,xnx−1)−u(t,xnx−2)δx+O(δx) \partial_x u(t, x_0) = \frac{u(t, x_1) - u(t, x_0)}{\delta x} + O(\delta x), \hspace{10pt} \partial_x u(t, x_{n_x - 1}) = \frac{u(t, x_{n_x - 1}) - u(t, x_{n_x - 2})}{\delta x} + O(\delta x)

what leads to

∂tu(t,x0)=(c(t,x0)−b(t,x0)δx)u(t,x0)+b(t,x0)δxu(t,x1)+O(δx)∂tu(t,xnx−1)=−b(t,xnx−1)δxu(t,xnx−2)+(b(t,xnx−1)δx+c(t,xnx−1))u(t,xnx−1)+O(δx) \begin{align*} \partial_t u (t, x_0) & = \left(c(t, x_0) - \frac{b(t, x_0)}{\delta x}\right) u(t, x_0) + \frac{b(t, x_0)}{\delta x} u(t, x_1) + O(\delta x)\\ \partial_t u (t, x_{n_x - 1}) & = - \frac{b(t, x_{n_x - 1})}{\delta x}u(t, x_{n_x - 2}) + \left( \frac{b(t, x_{n_x - 1})}{\delta x} + c(t, x_{n_x - 1}) \right) u(t, x_{n_x - 1}) + O(\delta x) \end{align*}

Let Δx2∈Rnx\Delta x^2 \in \mathbb R ^ {n_x} defined by ∀i∈[1;nx−2],(Δx2)i=δx2,(Δx2)0=(Δx2)nx−1=δx\forall i \in [1; n_x - 2], (\Delta x^2)_i = \delta_x ^ 2, (\Delta x^2)_0 = (\Delta x^2)_{n_x - 1} = \delta x.

We can write:

∂tunx(t,x)=Lnx(t,x)unx(t,x)+O(Δx2)(1) \partial_t u_{n_x} (t, x) = \mathrm L_{n_x} (t, x) u_{n_x}(t, x) + O(\Delta x^2) \hspace{50pt} (1)

where Lnx(t,x)\mathrm L_{n_x}(t, x) in a nx×nxn_x \times n_x tridiagonal real matrix defined by

Lnx(t,x)0,0=c(t,x0)−b(t,x0)δxLnx(t,x)0,1=b(t,x0)δx \begin{align*} \mathrm L_{n_x}(t, x)_{0, 0} & = c(t, x_0) - \frac{b(t, x_0)}{\delta x}\\ \mathrm L_{n_x}(t, x)_{0, 1} & = \frac{b(t, x_0)}{\delta x} \end{align*}

Lnx(t,x)i,i−1=a(t,xi)δx2−b(t,xi)2δxLnx(t,x)i,i=c(t,xi)−2a(t,xi)δx2Lnx(t,x)i,i+1=a(t,xi)δx2+b(t,xi)2δx \begin{align*} \mathrm L_{n_x}(t, x)_{i, i - 1} & = \frac{a(t, x_i)}{\delta x ^ 2} - \frac{b(t, x_i)}{2\delta x}\\ \mathrm L_{n_x}(t, x)_{i, i} &= c(t, x_i) - 2 \frac{a(t, x_i)}{\delta x ^ 2}\\ \mathrm L_{n_x}(t, x)_{i, i + 1} &= \frac{a(t, x_i)}{\delta x ^ 2} + \frac{b(t, x_i)}{2\delta x} \end{align*}

Lnx(t,x)nx−1,nx−2=−b(t,xnx−1)δxLnx(t,x)nx−1,nx−1=b(t,xnx−1)δx+c(t,xnx−1) \begin{align*} \mathrm L_{n_x}(t, x)_{n_x - 1, n_x - 2} & = - \frac{b(t, x_{n_x - 1})}{\delta x}\\ \mathrm L_{n_x}(t, x)_{n_x - 1, n_x - 1} &= \frac{b(t, x_{n_x - 1})}{\delta x} + c(t, x_{n_x - 1}) \end{align*}

time discretisation

Now that we rewrote our problem as (1)(1), we are in a classical differential equation of the form ∂tf(t)=g(t)\partial_t f(t) = g(t). Classical ways to solve this kind of equation are the Euler schemes (implicit and explicit). The implicit scheme uses f(t+δt)=f(t)+g(t)δt+O(δt2)f(t + \delta t) = f(t) + g(t) \delta t + O (\delta t ^2), and the explicit f(t+δt)=f(t)−g(t+δt)δt+O(δt2)f(t + \delta t) = f(t) - g (t + \delta t) \delta t + O (\delta t^2).
Let’s return to (1)(1):

Let u~\tilde u defined by the following induction (Explicit Euler scheme (EE)):

u~0=u(0,x)u~i+1=u~i+L(ti,x)u~iδt=(I+δtL(ti,x))u~i \begin{align*} \tilde u_0 & = u(0, x)\\ \tilde u_{i + 1} & = \tilde u_i + \mathrm L(t_i, x) \tilde u_i \delta t = (I + \delta t \mathrm L (t_i, x)) \tilde u_i \end{align*}

We can show that u~nt−1−u(T,x)=O(Δx2+δt1)\tilde u_{n_t - 1} - u(T, x) = O(\Delta x ^ 2 + \delta t \mathbf 1):

To that, we show by an induction P(i):u~i−u(ti,x)=O(iδtΔx2+iδt21)P(i): \tilde u_i - u(t_i, x) = O(i\delta t \Delta x ^ 2 + i \delta t ^ 2 \mathbf 1):
the case i=0i = 0 is trivial as the equality hold by construction (without big OO).

We suppose P(i)P(i):

∂tu(ti,x)=L(ti,x)u(ti,x)+O(Δx2)⇒u(ti+1,x)=(I+δtL(ti,x))u(ti,x)+O(δtΔx2+δt1)=(I+δtL(ti,x))(u~i+O(iδtΔx2+iδt21))+O(δtΔx2+δt1)=(I+δtL(ti,x))u~i+O((i+1)δtΔx2+(i+1)δt21)⇒u~i+1−u(ti+1,x)=O((i+1)δtΔx2+(i+1)δt21) \begin{align*} \partial_t u(t_i, x) & = \mathrm L(t_i, x)u(t_i, x) + O(\Delta x^2)\\ \Rightarrow u(t_{i + 1}, x) & = (I + \delta t \mathrm L(t_i, x)) u (t_i, x) + O(\delta t \Delta x^2 + \delta t\mathbf 1)\\ & = (I + \delta t \mathrm L(t_i, x)) (\tilde u_i + O(i \delta t \Delta x ^ 2 + i \delta t ^ 2 \mathbf 1)) + O(\delta t \Delta x^2 + \delta t\mathbf 1)\\ & = (I + \delta t \mathrm L(t_i, x)) \tilde u_i + O((i+1) \delta t \Delta x ^ 2 + (i+1) \delta t ^ 2 \mathbf 1)\\ \Rightarrow \tilde u_{i + 1} - u(t_{i + 1}, x) & = O\left((i+1) \delta t \Delta x ^ 2 + (i+1) \delta t ^ 2 \mathbf 1\right) \end{align*}

We showed P(0)P(0) and P(i)⇒P(i+1)P(i) \Rightarrow P(i+1), then ∀i∈N,P(i)\forall i \in \mathbb N, P(i). In particular, P(nt−1)P(n_t - 1):

u~nt−1=u(tnt−1,x)+O((nt−1)δtΔx2+(nt−1)δt21) \tilde u_{n_t - 1} = u(t_{n_t - 1}, x) + O((n_t - 1)\delta t \Delta x ^ 2 + (n_t - 1) \delta t ^ 2 \mathbf 1)

Using nt−1=TδTn_t - 1 = \frac{T}{\delta T}, we have

u(T,x)−u~nt−1=O(Δx2+δt1) u(T, x) - \tilde u_{n_t - 1} = O(\Delta x ^ 2 + \delta t \mathbf 1)

We note that the error at TT is of order 2, while it is of order 3 between tt and t+δtt + \delta t. In general, when the error is of order n+1n + 1 on a time step, it will be at order nn at TT.

If we defined u~\tilde u by the following induction (Implicit Euler scheme (IE)), we have the same results using a similar demonstration:

u~0=u(0,x)u~i+1=u~i−L(ti+1,x)u~i+1δt⇒u~i+1=(I−δtL(ti+1,x))−1u~i \begin{align*} \tilde u_0 & = u(0, x)\\ \tilde u_{i + 1} & = \tilde u_i - \mathrm L(t_{i + 1}, x) \tilde u_{i + 1} \delta t\\ \Rightarrow \tilde u_{i + 1} & = (I - \delta t \mathrm L (t_{i+1}, x))^{-1} \tilde u_i \end{align*}

Now, we can use a mixture of the two scheme to try to increase the time order:

u~0=u(0,x)u~i+1=u~i−θL(ti+1,x)u~i+1δt+(1−θ)L(ti,x)u~i⇒u~i+1=(I−θδtL(ti+1,x))−1(I+(1−θ)δtL(ti,x))u~i \begin{align*} \tilde u_0 & = u(0, x)\\ \tilde u_{i + 1} & = \tilde u_i - \theta \mathrm L(t_{i + 1}, x) \tilde u_{i + 1} \delta t + (1 - \theta) \mathrm L(t_i, x)\tilde u_i \\ \Rightarrow \tilde u_{i + 1} & = (I - \theta \delta t \mathrm L (t_{i+1}, x))^{-1} (I + (1 - \theta)\delta t \mathrm L (t_i, x))\tilde u_i \end{align*}

It is easy to show that taking θ=12\theta = \frac{1}{2}, we have an order 2 time scheme:

u(t+δt,x)=u(t,x)+δt∂tu(t,x)+δt22∂t2u(t,x)+O(δt3)u(t,x)=u(t+δt,x)−δt∂tu(t+δt,x)+δt22∂t2u(t+δt,x)+O(δt3) \begin{align*} u(t + \delta t, x) & = u(t, x) + \delta t \partial_t u(t, x) + \frac{\delta t^2}{2} \partial_t ^ 2 u(t, x) + O(\delta t ^ 3)\\ u(t, x) & = u(t + \delta t, x) - \delta t \partial_t u(t + \delta t, x) + \frac{\delta t^2}{2} \partial_t ^ 2 u(t + \delta t, x) + O(\delta t ^ 3) \end{align*}

We rewrite the second line:

u(t+δt,x)=u(t,x)+δt∂tu(t+δt,x)−δt22∂t2u(t+δt,x)+O(δt3)=u(t,x)+δt∂tu(t+δt,x)−δt22(∂t2u(t,x)+O(δt))+O(δt3)=u(t,x)+δt∂tu(t+δt,x)−δt22∂t2u(t,x)+O(δt3) \begin{align*} u(t + \delta t, x) & = u(t, x) + \delta t \partial_t u(t + \delta t, x) - \frac{\delta t^2}{2} \partial_t ^ 2 u(t + \delta t, x) + O(\delta t ^ 3)\\ & = u(t, x) + \delta t \partial_t u(t + \delta t, x) - \frac{\delta t^2}{2} (\partial_t ^ 2 u(t, x) + O (\delta t)) + O(\delta t ^ 3)\\ & = u(t, x) + \delta t \partial_t u(t + \delta t, x) - \frac{\delta t^2}{2} \partial_t ^ 2 u(t, x) + O(\delta t ^ 3)\\ \end{align*}

applied on a θ\theta scheme:

u(t,x)+θδt∂tu(t+δt,x)+(1−θ)δt∂tu(t,x)−u(t+δt,x)=(2θ−1)δt22∂t2u(t,x)+O(δt3) u(t, x) + \theta \delta t \partial_t u (t + \delta t, x) + (1 - \theta) \delta t \partial_t u(t, x) - u(t + \delta t, x) = (2\theta - 1)\frac{\delta t^2}{2}\partial_t^2u(t, x) + O(\delta t ^ 3)

taking θ=12\theta = \frac{1}{2}:

u(t,x)+12δt∂tu(t+δt,x)+12δt∂tu(t,x)−u(t+δt,x)=O(δt3) u(t, x) + \frac{1}{2} \delta t \partial_t u (t + \delta t, x) + \frac{1}{2}\delta t \partial_t u(t, x) - u(t + \delta t, x) = O(\delta t ^ 3)

what leads to an order 2 in time scheme. This scheme is the so called Crank-Nicolson scheme.

We can also remark that a time step δt\delta t of a θ\theta-scheme is a EE time step (1−θ)δt(1 - \theta)\delta t followed by a IE time step θδt\theta \delta t. In the particular Crank-Nicolson case, this is a EE half time step followed by a IE half time step.

What’s wrong with Crank-Nicolson?

The undesired behavior of Crank-Nicolson scheme comes from the Explicit Euler part, and each θ\theta scheme, will have the same behavior (except the case θ=1\theta = 1), as each step of a θ\theta scheme can be decomposed into an explicit step followed by an implicit. To see the problem, we consider the simple following PDE:

∀(t,x)∈R+×R,∂tu(t,x)=a∂x2u(t,x)+b∂xu(t,x)+cu(t,x)∀x∈R,u(0,x)=1x>0 \begin{align*} \forall (t, x) \in \mathbb R^+ \times \mathbb R, \partial_t u(t, x) & = a \partial_x ^ 2 u(t, x) + b \partial_x u(t, x) + c u(t, x)\\ \forall x \in \mathbb R, u(0, x) = \mathbf 1_{x > 0} \end{align*}

Where a,b,c∈R+×R×Ra, b, c \in \mathbb R^+ \times \mathbb R \times \mathbb R. We discretise xx and tt as in the previous section. Let i0∈[0;nx−1]i_0 \in [0; n_x - 1] such that xi0≤0<xi0+1x_{i_0} \leq 0 \lt x_{i_0+1}. We note that ∀i≤i0,u~i0=0\forall i \leq i_0, \tilde u^0_i = 0 and ∀i>i0,u~i0=1\forall i \gt i_0, \tilde u^0_i = 1. Let’s look at the value of u near 00 after the first step:

u~i01=u~i00+δt(au~i0+10+u~i0−10−2u~i00δx2+bu~i0+10−u~i0−102δx+cu~i00)=δt(a1δx2+b12δx) \begin{align*} \tilde u ^ 1_{i_0} & = \tilde u ^ 0_{i_0} + \delta t \left(a \frac{\tilde u^0_{i_0 + 1} + \tilde u^0_{i_0 - 1} - 2 \tilde u^0_{i_0}}{\delta x ^ 2} {}+ b\frac{\tilde u^0_{i_0 + 1} - \tilde u^0_{i_0 - 1}}{2\delta x} + c \tilde u^0_{i_0}\right)\\ & = \delta t \left(a \frac{1}{\delta x ^ 2} + b\frac{1}{2\delta x}\right) \end{align*}

and

u~i0+11=u~i0+10+δt(au~i0+20+u~i00−2u~i0+10δx2+bu~i0+20−u~i002δx+cu~i0+10)=1+δt(a−1δx2+b12δx+c) \begin{align*} \tilde u ^ 1_{i_0 + 1} & = \tilde u ^ 0_{i_0 + 1} + \delta t \left(a \frac{\tilde u^0_{i_0 + 2} + \tilde u^0_{i_0} - 2 \tilde u^0_{i_0 + 1}}{\delta x ^ 2} {}+ b\frac{\tilde u^0_{i_0 + 2} - \tilde u^0_{i_0}}{2\delta x} + c \tilde u^0_{i_0 + 1}\right)\\ & = 1 + \delta t \left(a \frac{-1}{\delta x ^ 2} + b\frac{1}{2\delta x} + c\right) \end{align*}

We can reasonably think that for a small δt\delta t, u(δt,xi0)≤u(δt,xi0+1)u(\delta t, x_{i_0}) \leq u(\delta t, x_{i_0 + 1})

u~i0+11−u~i01=1+δt(a−1δx2+b12δx+c)−δt(a1δx2+b12δx)=1−δt(2aδx2−c)u~i0+11−u~i01≥0⇔1≥δt(2aδx2−c) \begin{align*} \tilde u ^ 1_{i_0 + 1} - \tilde u ^ 1_{i_0} &= 1 + \delta t \left(a \frac{-1}{\delta x ^ 2} + b\frac{1}{2\delta x} + c\right) - \delta t \left(a \frac{1}{\delta x ^ 2} + b\frac{1}{2\delta x}\right)\\ & = 1 - \delta t \left( \frac{2a}{\delta x^2} - c \right)\\ \tilde u ^ 1_{i_0 + 1} - \tilde u ^ 1_{i_0} \geq 0 & \Leftrightarrow 1 \geq \delta t \left( \frac{2a}{\delta x^2} - c \right) \end{align*}

The previous condition can be easily violated if δx2≪δt\delta x ^ 2 \ll \delta t. It implies that if we decrease δx\delta x with fixed δt\delta t, spurious oscillations will appear, while a good scheme should increase precision when δt\delta t or δx\delta x decrease.

We remind one more time that the Crank-Nicolson scheme is nothing but a EE half time step followed by a IE half time step. The condition for the Crank-Nicolson to bad behave is then the same, replacing δt\delta t with δt2\frac{\delta t}{2}, ie if 1<δt(aδx2−c2)1 < \delta t \left( \frac{a}{\delta x^2} - \frac{c}{2} \right), the Crank-Nicolson scheme will oscillate.

Another time order 2 scheme that does not use explicit time step

Our goal is to find a scheme with a time order 2, without using explicit scheme. The idea is to use extrapolation method, in particular the Richardson Extrapolation. What we will do is to take a convex combination of the solution obtained with a time step δt\delta t and the one with two time step δt2\frac{\delta t}{2}, and cancel the smallest order term of the error.

We define our scheme with the following induction:

u~0=u(0,x)vi+1=(I−δtL(ti+1,x))−1u~iwi+1=(I−δt2L(ti+1,x))−1(I−δt2L(ti+δt2,x))−1u~iu~i+1=(1−ω)vi+1+ωwi+1 \begin{align*} \tilde u_0 & = u(0, x)\\ v_{i + 1} & = \left(I - \delta t \mathrm L (t_{i+1}, x)\right)^{-1} \tilde u_i\\ w_{i + 1} & = \left(I - \frac{\delta t}{2} \mathrm L (t_{i+1}, x)\right)^{-1} \left(I - \frac{\delta t}{2} \mathrm L (t_i + \frac{\delta t}{2}, x)\right)^{-1} \tilde u_i\\ \tilde u_{i + 1} & = (1 - \omega) v_{i + 1} + \omega w_{i + 1}\\ \end{align*}

Let’s examine the error on the two implicit scheme, to find the ω\omega that will cancel the smallest order term of the error:

Error on the IE time step:

u(t+δt,x)=u(t,x)+δt∂tu(t+δt,x)−δt22∂t2u(t+δt,x)+O(δt3)⇒u(t,x)+δt∂tu(t+δt,x)−u(t+δt,x)=δt22∂t2u(t+δt,x)+O(δt3) \begin{align*} & u(t + \delta t, x) = u(t, x) + \delta t \partial_t u(t + \delta t, x) - \frac{\delta t^2}{2} \partial_t^2u(t + \delta t, x) + O (\delta t^3)\\ & \Rightarrow u(t, x) + \delta t \partial_t u(t + \delta t, x) - u(t + \delta t, x) = \frac{\delta t^2}{2} \partial_t^2u(t + \delta t, x) + O (\delta t^3) \end{align*}

Error made on the two half IE time steps:

{u(t+δt2,x)=u(t,x)+δt2∂tu(t+δt2,x)−δt28∂t2u(t+δt2)+O(δt3)u(t+δt,x)=u(t+δt2,x)+δt2∂tu(t+δt,x)−δt28∂t2u(t+δt,x)+O(δt3) \left\{\begin{array}{rl} u(t + \frac{\delta t}{2}, x) & \hspace{-5pt} = u(t, x) + \frac{\delta t}{2} \partial_t u(t + \frac{\delta t}{2}, x) - \frac{\delta t^2}{8} \partial_t^2u(t + \frac{\delta t}{2}) + O (\delta t^3)\\ u(t + \delta t, x) & \hspace{-5pt} = u(t + \frac{\delta t}{2}, x) + \frac{\delta t}{2} \partial_t u(t + \delta t, x) - \frac{\delta t^2}{8} \partial_t^2u(t + \delta t, x) + O (\delta t^3)\\ \end{array}\right.\\ ⇒e1/2=u(t,x)+δt2∂tu(t+δt2,x)+δt2∂tu(t+δt,x)−u(t+δt,x)=δt28(∂t2u(t+δt,x)+∂t2u(t+δt2,x))+O(δt3)=δt28(∂t2u(t+δt,x)+(∂t2u(t+δt,x)+O(δt)))+O(δt3)=δt24∂t2u(t+δt,x)+O(δt3) \begin{align*} \Rightarrow e_{1/2} &= u(t, x) + \frac{\delta t}{2} \partial_t u(t + \frac{\delta t}{2}, x) + \frac{\delta t}{2} \partial_t u (t + \delta t, x) - u(t + \delta t, x)\\ &= \frac{\delta t ^ 2}{8} (\partial_t^2u(t + \delta t, x) + \partial_t^2u(t + \frac{\delta t}{2}, x)) + O(\delta t^3)\\ &= \frac{\delta t ^ 2}{8} (\partial_t^2u(t + \delta t, x) + (\partial_t^2u(t + \delta t, x) + O(\delta t))) + O(\delta t^3)\\ &= \frac{\delta t ^ 2}{4} \partial_t^2u(t + \delta t, x) + O(\delta t^3) \end{align*}

The error on our new scheme is then:

eω=(1−ω)(u(t,x)+δt∂tu(t+δt,x))+ω(u(t,x)+δt2∂tu(t+δt2,x)+δt2∂tu(t+δt,x))−u(t+δt,x)=(1−ω)δt22∂t2u(t+δt,x)+ωδt24∂t2u(t+δt,x)+O(δt3)=δt24∂t2u(t+δt,x)(2−ω)+O(δt3) \begin{align*} e_\omega & = (1 - \omega)(u(t, x) + \delta t \partial_t u(t + \delta t, x)) + \omega \left(u(t, x) + \frac{\delta t}{2} \partial_t u(t + \frac{\delta t}{2}, x) + \frac{\delta t}{2} \partial_t u (t + \delta t, x)\right)\\ & \hspace{10pt} - u(t + \delta t, x) \\ & = (1-\omega) \frac{\delta t^2}{2}\partial_t^2u(t + \delta t, x) + \omega \frac{\delta t^2}{4}\partial_t^2u(t + \delta t, x) + O(\delta t ^ 3)\\ & = \frac{\delta t^2}{4}\partial_t^2u(t + \delta t, x)(2 - \omega) + O(\delta t ^ 3) \end{align*}

The value of ω\omega that cancel the order 2 term is 22. Then, taking ω=2\omega = 2 leads to a time order 2 time scheme. This scheme is:

u~0=u(0,x)vi+1=(I−δtL(ti+1,x))−1u~iwi+1=(I−δt2L(ti+1,x))−1(I−δt2L(ti+δt2,x))−1u~iu~i+1=2wi+1−vi+1 \begin{align*} \tilde u_0 & = u(0, x)\\ v_{i + 1} & = \left(I - \delta t \mathrm L (t_{i+1}, x)\right)^{-1} \tilde u_i\\ w_{i + 1} & = \left(I - \frac{\delta t}{2} \mathrm L (t_{i+1}, x)\right)^{-1} \left(I - \frac{\delta t}{2} \mathrm L (t_i + \frac{\delta t}{2}, x)\right)^{-1} \tilde u_i\\ \tilde u_{i + 1} & = 2 w_{i + 1} - v_{i + 1}\\ \end{align*}

Here we are ! We found a scheme that is order 2 in time without using explicit time step. Let’s experiment all that in the next section.

Numerical examples

For the numerical examples, I will work with the basic heat equation

∂tu(t,x)=∂x2u(t,x) \partial_t u(t, x) = \partial_x ^ 2 u(t, x)

with the initial condition u(0,x)=1x>0u(0, x) = \mathbf 1_{x > 0}. Surprising, isn’t it ?

I will start expressing analytically the solution at T∈R+T \in \mathbb R^+. Using the Feynman-Kac formula on vv defined by v(t,x)=u(T−t,x)v(t, x) = u(T - t, x), we have:

∀x∈R,u(T,x)=E[1X(T)>0∣X(0)=x]dX(t)=2dW(t) where W is a standard brownian motion \begin{align*} \forall x \in \mathbb R, u(T, x) & = \mathbb E [\mathbf 1_{X(T) > 0} | X(0) = x]\\ dX(t) &= \sqrt 2 dW(t) \text{ where $W$ is a standard brownian motion}\\ \end{align*}

Then:

∀x∈R,u(T,x)=E[1x+2W(T)>0]=P(x+2W(T)>0)=P(2TZ>−x) where Z∼N(0,1)=P(2TZ<x) \begin{align*} \forall x \in \mathbb R, u(T, x) &= \mathbb E [\mathbf 1_{x + \sqrt 2 W(T) \gt 0}]\\ & = \mathbb P (x + \sqrt 2 W(T) \gt 0)\\ & = \mathbb P (\sqrt {2T} Z \gt -x) \text{ where $Z \sim \mathcal N(0, 1)$}\\ & = \mathbb P (\sqrt {2T} Z \lt x) \end{align*}

We can conclude that u(T,x)=ϕ(x2T)u(T, x) = \phi \left(\frac{x}{\sqrt {2T}}\right) where ϕ\phi is the cumulative distribution function of the standard normal distribution.

Before showing some graphics, I will briefly discuss the choice of xminx_{min} and xmaxx_{max}. First, we can remark that the problem is almost symmetric. Thus, taking xmin=−xmaxx_{min} = -x_{max} is a good idea. To preserve the symmetry, we can also take nxn_x even, then 00 will fall between two grid points, and the initial vector u~0\tilde u_0 will be symmetric.

The last thing we can remark is on the probabilistic formulation of the PDE: the value depends on a Gaussian law, that is highly concentrated into a small interval. For example, if we call σ\sigma the standard deviation of the concerned Gaussian law, the random variates will leave the interval [−5σ;5σ][-5\sigma; 5\sigma] with a probability lower than 10−610^{-6}.

Thus, I take xmax=52Tx_{max} = 5\sqrt{2T} for my example, what will cause the boundary error to be negligible, according to my previous remark.

I briefly provide all the fixed parameters I used for my test:

T=1xmin=−52xmax=52 \begin{align*} T & = 1\\ x_{min} &= -5\sqrt 2\\ x_{max} &= 5\sqrt 2 \end{align*}

For each test case, I draw three graphics: one for Implicit Euler, one for Crank-Nicolson and one for the scheme obtained with Richardson Extrapolation. On each graphic, the dotted red line is the exact value, and the blue line is the value obtained with the corresponding scheme. There is also on the bottom of each graphic a Root Mean Squared error that measure the error done by the scheme. The formula to compute the RMS is 1nx−1∑i=0nx−1(u~int−u(T,xi))2\frac{1}{n_x - 1}\sum_{i=0}^{n_x - 1} (\tilde u ^ {n_t}_i - u(T, x_i))^2.

Test case I: nt=3,nx=20(δt=12,δx≈0.74)n_t = 3, n_x = 20 \hspace{5pt} \left(\delta t = \frac{1}{2}, \delta x \approx 0.74\right):

Test case II: nt=3,nx=30(δt=12,δx≈0.49)n_t = 3, n_x = 30 \hspace{5pt} \left(\delta t = \frac{1}{2}, \delta x \approx 0.49\right):

Test case III: nt=2,nx=200(δt=1,δx≈0.07)n_t = 2, n_x = 200 \hspace{5pt} \left(\delta t = 1, \delta x \approx 0.07\right):

On the test case I, we see that the error is of the same order in the case of Crank-Nicolson and Extrapolation, and is bigger in the Implicit Euler case. On the test case II (lower space step), we see Crank-Nicolson has a bad behavior, while Implicit Euler and Extrapolation are better than in the test case II, and Extrapolation is still the best. The test case III is an extreme test case to show how wrong can be Crank-Nicolson, and how fast the scheme using extrapolation converge in time.

Conclusion

After a brief study of classical PDE finite difference scheme, I showed that the Crank-Nicolson one, supposed to be a good one, behaves badly in some cases, due to the explicit part of the scheme. I proposed a new scheme based on Richardson Extrapolation that has the same theoretical order in space that the Crank-Nicolson one, but that doesn’t oscillate. The theoretical aspect is confirmed by the numerical results I presented in the last part. We can also note that the method can be extended to multi space dimension PDE with little effort.

I invite the reader who wants to go further on this topic to read: