ODE and PDE solvers: finite differences and stability

The Black–Scholes equation is a diffusion equation run backwards in time, and finite differences solve it on a grid. The subject has one central pitfall — an explicit scheme that looks correct and blows up — and understanding why is most of what an interview will ask.

Proposition 5.1

Setting up the grid

Discretise in the underlying and in time, impose the payoff as the terminal condition, and step backwards. The boundary conditions come from the economics: a call is worth nothing at zero spot and behaves like the forward minus the discounted strike at high spot.

Holds when

Work in $\ln S$ rather than $S$ : it makes the coefficients constant and the grid uniform in a variable that actually behaves uniformly.
Put a grid node exactly at the strike, or the kink smears across two nodes and the convergence rate falls.
Truncate the spatial domain at several standard deviations, and check the answer is insensitive to where.

Aspect	Explicit	Implicit	Crank–Nicolson
Each step	Direct arithmetic	Solve a tridiagonal system	Solve a tridiagonal system
Stability	Conditional	Unconditional	Unconditional
Accuracy in time	$O(\Delta t)$	$O(\Delta t)$	$O(\Delta t^2)$
Cost per step	Lowest	Low — tridiagonal is $O(n)$	Low
Weakness	Tiny time steps required	First-order only	Oscillates near a discontinuity

Table 5.2 · The three schemes. A tridiagonal solve is

O(n)

by the Thomas algorithm, so the implicit schemes cost barely more per step than the explicit one — which is why the conditional stability of the explicit scheme is rarely worth accepting.

Equation 5.3

The explicit stability condition

Halving the space step requires quartering the time step. Refining the grid therefore costs eight times the work, not twice.

\Delta t \le \frac{(\Delta x)^2}{\sigma^2}

$(\Delta x)^2$: The quadratic dependence is what makes this so restrictive.

Figure 5.4 · The explicit scheme has a cliff. Below

\lambda = 1/2

each step shrinks the error; above it the factor exceeds one and the grid oscillates itself to infinity in a few dozen steps. Halving the space step therefore forces a quarter of the time step, which is the whole reason Crank–Nicolson is worth the extra solve.

ODE and PDE solvers: finite differences and stability

After this lesson you should be able to

Setting up the grid

The explicit stability condition

The rest of this lesson is in Premium