Finite-Difference Methods
1 Setting
The Black-Scholes PDE for a European call with strike \(K\) and maturity \(T\) has value function \(u(t,x)\), a function of time \(t\) and asset price \(x\), solving the PDE
\[ \begin{cases} \partial_t u + rx\,\partial_x u + \dfrac{1}{2}\sigma^2x^2\,\partial_{xx}u - ru = 0, \\[1ex] u(T,x) = (x-K)_+ . \end{cases} \tag{1} \]
Here \(r\) is the risk-free rate and \(\sigma\) the volatility. The finite difference (FD) method discretises the continuous domain of \((t,x)\) into a mesh with steps \((\Delta t,\Delta x)\) and replaces each derivative by a difference quotient obtained from a Taylor expansion around the mesh point.
2 Difference Quotients
For example, the time derivative is the limit
\[ \partial_t u = \lim_{\delta t\to 0}\frac{u(t+\delta t,x)-u(t,x)}{\delta t} \approx \frac{u(t+\Delta t,x)-u(t,x)}{\Delta t} + O(\Delta t), \]
for small \(\Delta t\). This is a forward difference. There are three first-order approximations.
- Forward difference: \[ \partial_t u \approx \frac{u(t+\Delta t,x)-u(t,x)}{\Delta t}, \]
- Backward difference: \[ \partial_t u \approx \frac{u(t,x)-u(t-\Delta t,x)}{\Delta t}, \]
- Central difference: \[ \partial_t u \approx \frac{u(t+\Delta t,x)-u(t-\Delta t,x)}{2\Delta t}. \]
The same formulas hold for \(\partial_x u\) with \(x\) in place of \(t\). The forward and backward differences have error \(O(\Delta t)\), the central difference \(O(\Delta t^2)\).
For second derivatives, taking the forward difference of the backward difference (or the reverse) gives the same quotient.
\[ \partial_{xx}u \approx \frac{u(t,x+\Delta x)-2u(t,x)+u(t,x-\Delta x)} {(\Delta x)^2}, \]
with error \(O((\Delta x)^2)\), so accuracy improves faster under mesh refinement than for the first-order quotients above.
3 The Mesh
Specify \(x_{\min}\), \(x_{\max}\), \(t_{\min}\), \(t_{\max}\), \(\Delta x\) and \(\Delta t\). For the call (1) we take \(x_{\min}=0\) and \(t_{\min}=0\), since price and time are non-negative, and \(x_{\max}=N\Delta x\) large, \(T=M\Delta t\). Write
\[ u_n^m = u(m\Delta t,\,n\Delta x),\qquad n=0,\dots,N,\quad m=0,\dots,M. \]
4 Explicit Scheme
Use the forward difference in time \(\partial_t u\approx(u_n^{m+1}-u_n^m)/\Delta t\), and the central and symmetric differences in space,
\[ \partial_x u\approx\frac{u_{n+1}^{m+1}-u_{n-1}^{m+1}}{2\Delta x},\qquad \partial_{xx}u\approx\frac{u_{n+1}^{m+1}-2u_n^{m+1}+u_{n-1}^{m+1}}{(\Delta x)^2}, \]
all evaluated at the later time level. Substituting into (1) with \(x=n\Delta x\) and solving for \(u_n^m\) gives the backward recursion
\[ u_n^{m}=P_n^+u_{n+1}^{m+1}+P_n^0u_n^{m+1}+P_n^-u_{n-1}^{m+1}, \]
where
\[ P_n^{\pm}=\frac{\Delta t}{2}\left(\sigma^2n^2\pm rn\right),\qquad P_n^0=1-\Delta t\left(\sigma^2n^2+r\right). \]
The terminal condition is \(u_n^M=(n\Delta x-K)_+\), with boundary values \(u_0^m=0\) and \(u_N^m\approx N\Delta x-Ke^{-r(T-m\Delta t)}\). The recursion looks like a trinomial tree run backwards in time. It is cheap, but only stable if \(\Delta t\) is small enough that \(P_n^0\ge 0\), roughly \(\Delta t\le 1/(\sigma^2N^2+r)\).
5 Implicit and Crank-Nicolson Schemes
The implicit scheme evaluates the spatial differences at the earlier time level \(m\). This gives, for each \(m\), a tridiagonal linear system
\[ A\,u^{m}=u^{m+1}, \]
for the vector \(u^m=(u_n^m)_n\), which is solved backwards in time. It is unconditionally stable. The Crank-Nicolson scheme averages the explicit and implicit spatial differences, which makes it second-order accurate in time as well as in space (error \(O(\Delta t^2+\Delta x^2)\)) and also unconditionally stable.
6 American Options
The explicit scheme is consistent with early exercise, since it is a tree-like procedure that moves backwards in time. As for a tree, we force \(V\ge G\) for the value function \(V(t,s)\) and immediate payoff \(G(t,s)=(K-s)_+\) (an American put) by taking the maximum of the two at every grid point,
\[ V_n^{m}\leftarrow \max\{V_n^{m},\,G_n^{m}\}. \]
This gives the correct price because each \(V_n^m\) is computed from the later level \(m+1\) and is never changed again. After solving, one exercises early exactly where \(V(t,s)=G(t,s)\), which gives the exercise boundary.
For the implicit scheme this pointwise maximum is wrong. The scheme couples \(V_{n-1}^m\), \(V_n^m\) and \(V_{n+1}^m\) in one linear equation, so altering one grid point changes its neighbours and eventually every \(V_i^m\).
Instead one uses projected SOR (PSOR), which solves the linear system \(AV^m=b\) by successive over-relaxation and projects each iterate onto \(V\ge G\):
\[ V_i^{m,(k+1)}=\max\left\{G_i^m,\;(1-w)V_i^{m,(k)}+\frac{w}{A_{ii}}\left( b_i-\sum_{j<i}A_{ij}V_j^{m,(k+1)}-\sum_{j>i}A_{ij}V_j^{m,(k)}\right)\right\}, \]
where \(k\) is the iteration index and \(w\in(1,2)\) the relaxation parameter. The iteration converges to the solution of the system restricted to \(\{V\ge G\}\). As before, the exercise boundary is where \(V=G\).
7 References
- Wilmott, P., Howison, S. and Dewynne, J. (1995). The Mathematics of Financial Derivatives. Cambridge University Press.