A possible solution to the spurious oscillations in finite difference methods for Partial Differential Equations.
Vivien Begot
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, F(n)={f,f:R+×En→Rn}.
In this article, I will work on PDE of the following form:
The first line can be rewritten ∂tun=Lnun. To simplify notations, we will mix up both notations when there is no ambiguities.
The method
Our goal is to compute u(T,x) for a particular T∈R+. To that, we will in a first step time discretise the problem.
Let (nx,nt)∈N2, (xmin,xmax)∈E2, δx=(xmax−xmin)/(nx−1) and δt=T/(nt−1).
We define x∈En, t∈R+ by ∀i∈[0;nx−1],xi=xmin+iδx and ∀i∈[0;nt−1],ti=iδt
Spatial discretisation
The first step consists in discretising the operator Lnx. To that, we approximate the spatial partial derivatives with finite differences:
Now, we have to discretise in the boundary. To that, we assume that ∂x2u(t,x0)=∂x2u(t,xnx−1)=0 (I take simple boundary conditions, as this is not the
purpose of this article). We can write:
Now that we rewrote our problem as (1), we are in a classical differential equation of the form ∂tf(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), and the explicit f(t+δt)=f(t)−g(t+δt)δt+O(δt2).
Let’s return to (1):
Let u~ defined by the following induction (Explicit Euler scheme (EE)):
We showed P(0) and P(i)⇒P(i+1), then ∀i∈N,P(i). In particular, P(nt−1):
u~nt−1=u(tnt−1,x)+O((nt−1)δtΔx2+(nt−1)δt21)
Using nt−1=δTT, we have
u(T,x)−u~nt−1=O(Δx2+δt1)
We note that the error at T is of order 2, while it is of order 3 between t and t+δt. In general, when the error is of order n+1
on a time step, it will be at order n at T.
If we defined u~ by the following induction (Implicit Euler scheme (IE)), we have the same results using a similar demonstration:
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 of a θ-scheme is a EE time step (1−θ)δt followed by a IE time step θδ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 θ scheme, will have the same behavior (except the case θ=1), as each step of a θ scheme can
be decomposed into an explicit step followed by an implicit. To see the problem, we consider the simple following PDE:
Where a,b,c∈R+×R×R. We discretise x and t as in the previous section. Let i0∈[0;nx−1] such that xi0≤0<xi0+1.
We note that ∀i≤i0,u~i0=0 and ∀i>i0,u~i0=1. Let’s look at the value of u near 0 after the first step:
The previous condition can be easily violated if δx2≪δt. It implies that if we decrease δx with fixed δt, spurious oscillations will appear, while a good scheme should increase
precision when δt or δ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 with 2δt, ie if 1<δt(δx2a−2c), 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 and the one with two time step 2δt, and cancel the smallest order term of the error.
We define our scheme with the following induction:
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)
with the initial condition u(0,x)=1x>0. Surprising, isn’t it ?
I will start expressing analytically the solution at T∈R+. Using the Feynman-Kac formula on v defined by v(t,x)=u(T−t,x), we have:
∀x∈R,u(T,x)dX(t)=E[1X(T)>0∣X(0)=x]=2dW(t) where W is a standard brownian motion
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)
We can conclude that u(T,x)=ϕ(2Tx) where ϕ is the cumulative distribution function of the standard normal distribution.
Before showing some graphics, I will briefly discuss the choice of xmin and xmax. First, we can remark that the problem is almost symmetric.
Thus, taking xmin=−xmax is a good idea. To preserve the symmetry, we can also take nx even, then 0 will fall between two grid points, and the initial vector
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 σ the standard deviation of the concerned Gaussian law, the random variates will leave the interval [−5σ;5σ] with
a probability lower than 10−6.
Thus, I take xmax=52T 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:
Txminxmax=1=−52=52
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 nx−11∑i=0nx−1(u~int−u(T,xi))2.
Test case I: nt=3,nx=20(δt=21,δx≈0.74):
Test case II: nt=3,nx=30(δt=21,δx≈0.49):
Test case III: nt=2,nx=200(δt=1,δx≈0.07):
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: