Finite Difference Methods

Contents (hide)

1. Introduction
2. The boundary conditions
3. Explicit differences method
4. Implicit differences method
5. The theta-method
6. The Crank-Nicolson method

1. Introduction

Finite differences are routinely used in order to descritize and solve the Black-Scholes partial differential equation. The log-asset price space and the time to maturity are typically discretized. Based on the resulting grids, the partial derivatives are approximated. Depending on the approximation used, the most popular methods are the explicit method, the implicit method and the $\fs4 \theta$ -method. A special case of the latter is the very popular Crank-Nicolson method.

All methods use derivative approximations. In particular, first derivatives can be computed using

Forward differences, where $\fs4 f'(x)\approx [f(x+h)-f(x)]/h$
Backward differences, where $\fs4 f'(x)\approx [f(x)-f(x-h)]/h$
Central differences, where $\fs4 f'(x)\approx [f(x+h)-f(x-h)]/(2h)$

Second derivatives are approximated by $\fs4 f''(x)\approx [f(x+h)-2f(x)+f(x-h)]/h^2$ .

All approximation schemes lead to a linear system of equations. Such systems are typically tridiagonal, and can be solved rapidly using the L-U decomposition. For options with early exercise, such as American or Bermudan options, iterative methods, such as the iterative SOR method can be employed.

In all cases examined here (where the options are not backward looking), the BMS partial differential equation that the derivative price $\fs4 P=P(S,\tau)$ will satisfy is

$\fs4 P_{\tau}(S,\tau) +(r-\delta)SP_{S}( S,\tau) +\frac{1}{2}\sigma^{2}S^{2}P_{SS}(S,\tau) -rP(S,\tau)=0$

In order to transform this differential equation into one with constant coefficients, which is easier to handle, we use the transformation $\fs4 s=\log(S)$ . We will also use the transformation $\fs4 t=-\tau$ , in order for $\fs4 t$ to denote the time to maturity, rather than the actual time. Then, the differential equation becomes (with $\fs4 \mu = r-\delta-\sigma^2/2$ )

$\fs4 -P_{t}( s,t) +\mu P_{s}( s,t) +\frac{1}{2}\sigma^{2}P_{ss}(s,t) -rP(s,t)=0$

In the sections below we assume a rectangular grid over the log-price/time space. Say that we introduce the grid size $\fs4 \delta s$ across the log-price, and $\fs4 \delta t$ across time. We use $\fs4 N_s$ points over the log-price support, and $\fs4 N_t$ points over the interval {0,T$}. We will use the notation $\fs4 P_{i,j}$ to denote the derivative price when the underlying asset log-price is $\fs4 s_i$ and there is $\fs4 t_j$ time to maturity. Recall that although in principle the log-price can take any value in $\fs4 (-\infty,+\infty)$ , in order to implement a numerical solution we will have to truncate the support, over the interval $\fs4 (s_1,s_{N_s})$ .

2. The boundary conditions

All derivatives will satisfy the above relationship, regardless of their payoff structure. Different derivative contracts will specify different boundary conditions. The numerical implementation of a solver will deal with the discretization of the partial derivatives, and the specification of the boundary conditions.

We differentiate between two sets of boundary conditions, with respect to the availability or not of an early exercise feature.

If early exercise is not allowed, the boundary conditions are easy to specify and implement. Plain vanilla European and Barrier options will fall within this category. In the case of a European style contract, the boundary condition on maturity will be $\fs4 P(s_i,0) = V(s_i)$ , where $\fs4 V(s_0)$ is the payoff as a function of the log price. In addition, boundary conditions have to be specified on the option value, as the underlying log-price hits the truncation interval. If barriers are present, these will determine the boundaries: for example, if the option is cancelled when a boundary is crossed, then the option value on this boundary is zero. If boundaries are not specified, the behaviour of the option value as $\fs4 s \rightarrow \pm \infty$ has to be investigated. The option Delta (that is $\fs4 \Delta = \partial P/\partial S$ ) can be used for this assessment. As an example, call (resp. put) options will have $\fs4 \Delta\rightarrow +1$ (resp. $\fs4 \Delta\rightarrow 0$ ) as $\fs4 s\rightarrow +\infty$ , and $\fs4 \Delta\rightarrow 0$ (resp. $\fs4 \Delta\rightarrow -1$ ) as $\fs4 s\rightarrow -\infty$ .

If the option can be exercised early, it follows that the option values have to be at least equal to the payoffs of immediate exercise (otherwise, trivial arbitrage opportunities will exist). This will imply the condition $\fs4 P_{i,j}\ge V(s_i)$ .

3. Explicit differences method

This is the easier to implement method, but also the most unstable numerically. Assume that we are at the interior point $\fs4 (i,j)$ , where the derivative price is $\fs4 P=P_{i,j}$ . We shall approximate:

The time derivatives using forward differences,

$\fs4 P_{t} = \frac{P_{i,j+1}-P_{i,j}}{\delta t}$

The log-price derivatives using central differences,

$\fs4 P_{s} = \frac{P_{i+1,j}-P_{i-1,j}}{2\delta s}$

$\fs4 P_{ss} = \frac{P_{i+1,j}-2P_{i,j}+P_{i-1,j}}{(\delta s)^2}$

Finaly, substituting into the PDE yields the following expression, which has to be satisfied at each time $\fs4 t_j$ .

$\fs4 -\frac{P_{i,j+1}-P_{i,j}}{\delta t} +\mu \frac{P_{i+1,j}-P_{i-1,j}}{2\delta s} +\frac{1}{2}\sigma^{2} \frac{P_{i+1,j}-2P_{i,j}+P_{i-1,j}}{(\delta s)^2} -r P_{i,j}=0$

The solution of the PDE moves in a recursive fashion: Starting at time $\fs4 t_j$ we can use the above relationship to retrieve the value of the function at time $\fs4 t_{j+1}$ . Solving for $\fs4 P_{i,j+1}$ , we can express the PDE solution in an intuitive form

$\fs4 P_{i,j+1} = p_+ P_{i+1,j} + (1-p_0) P_{i,j} + p_- P_{i-1,j}$

where

$\fs4 p_- = \frac{\delta t}{2(\delta s)^2} (\sigma^2 - \mu \delta s)$

$\fs4 p_+ = \frac{\delta t}{2(\delta s)^2} (\sigma^2 + \mu \delta s)$

$\fs4 p_0 = \sigma^2 \frac{\delta t}{(\delta s)^2} + r \delta t$

Therefore, starting on the maturity, where the price of the derivative equals its payoffs, that is to say

$\fs4 P_{i,0} = V$

It is easy to verify that this method is equivalent to a trinomial tree, where the transition probabilities are $\fs4 p_+\delta t$ , $\fs4 p_-\delta t$ , and $\fs4 1-(p_++p_-)\delta t$ . The extra $\fs4 r\delta t$ term discounts the expected payoffs.

Solving backwards through the grid is straightforward. Starting with the values $\fs4 P_{i,0}$ which are set on maturity, we can compute the values of $\fs4 P_{i,1}$ based on the above relationships. We can compute these values for all $\fs4 i=2,3,\ldots,N_s-1$ , but not for the first and the last grid points. For these we employ the boundary conditions, which will set

$\fs4 P_{1,1} = P_{2,1} + \Delta_- (S_1 - S_2)$

$\fs4 P_{N_s,1} = P_{N_s-1,1} + \Delta_+ (S_{N_s} - S_{N_s-1})$

$\fs4 \Delta_-$ and $\fs4 \Delta_+$ denote the Deltas for very small and very large prices, respectively. Using the same procedure we can loop backwards through the whole grid.

4. Implicit differences method

The implicit differences method is implemented by approximating the time derivatives using backward differences.

$\fs4 P_{t} = \frac{P_{i,j}-P_{i,j-1}}{\delta t}$

The PDE now yields:

$\fs4 -\frac{P_{i,j}-P_{i,j-1}}{\delta t} +\mu \frac{P_{i+1,j}-P_{i-1,j}}{2\delta s} +\frac{1}{2}\sigma^{2} \frac{P_{i+1,j}-2P_{i,j}+P_{i-1,j}}{(\delta s)^2} -r P_{i,j}=0$

In order to make this expression comparable to the one we used in the Explicit Differences scheme, we move all time subscripts forward by one, $\fs4 j\rightarrow j+1$ . Then, we have

$\fs4 -\frac{P_{i,j+1}-P_{i,j}}{\delta t} +\mu \frac{P_{i+1,j+1}-P_{i-1,j+1}}{2\delta s} +\frac{1}{2}\sigma^{2} \frac{P_{i+1,j+1}-2P_{i,j+1}+P_{i-1,j+1}}{(\delta s)^2} -r P_{i,j+1}=0$

We can see that now knowing the prices at time $\fs4 t_j$ does not lead to the prices at time $\fs4 j+1$ as easy as before. Nevertheless, we can rewrite the above as

$\fs4 P_{i,j} = -p_+ P_{i+1,j+1} + (1+p_0) P_{i,j+1} - p_- P_{i-1,j+1}$

where the values for $\fs4 p_-$ , $\fs4 p_+$ and $\fs4 p_0$ are defined above. Once again, these equations will apply for all values $\fs4 P_{i,j+1}$ , except the boundary ones. For them, special care has to be taken, and as before we will have (for all $\fs4 j$ )

$\fs4 P_{1,j+1} - P_{2,j+1} = \Delta_- (S_1 - S_2)$

$\fs4 P_{N_s,j+1} - P_{N_s-1,j+1} = \Delta_+ (S_{N_s} - S_{N_s-1})$

We cannot solve each equation for the updated derivative prices, but we can solve all equations, jointly, as a system. If we denote with $\fs4 \mathbf{P}_j$ the (column) vector of the prices at time $\fs4 t_j$ , then we can express the system in the form

$\fs4 \mathbf{A}\cdot\mathbf{P}_{j+1} = \mathbf{C}_j$

Where:

The matrix $\fs4 \mathbf{A}$ is tridiagonal, given by

$\fs4 \mathbf{A} = \left( \begin{array}{CCC} \begin{array}{CCCC} 1 & -1 & & \\ -p_- & 1+p_0 & -p_+ & \\ & -p_- & 1+p_0 & -p_+ \end{array} & & {\LARGE 0} \\ &{\LARGE \ddots}& \\ {\LARGE 0} & & \begin{array}{CCCC} -p_- & 1+p_0 & -p_+ & \\ & -p_- & 1+p_0 & -p_+ \\ & & -1 & 1 \end{array} \end{array} \right)$

The vector $\fs4 \mathbf{C}_j$ is nearly identical to the vector of the prices $\fs4 \mathbf{P}_j$ , apart from the boundary elements, given by

$\fs4 \mathbf{C}_j = \left( \begin{array}{C} \Delta_- (S_1 - S_2) \\ P_{2,j}\\ P_{3,j}\\ \vdots \\ P_{N_s-1,j} \\ \Delta_+ (S_{N_s} - S_{N_s-1}) \end{array} \right)$

The above tridiagonal system can be solved numerically using the L-U decomposition, or other methods. If the derivative has American features, then the solution has to be subject to the constraint $\fs4 P_{i,j+1}\ge V(s_i)$ . Such contrained problems can be solved using the iterative SOR method.

5. The theta-method

The $\fs4 \theta$ method is somehow between the Explicit and Implicit schemes, being a weighted average of the two.

It is perhaps easier for the exposition, if we trivially express the Implicit method as a matrix equation, in order to be of a form similar to the Explicit one

$\fs4 \mathbf{I}\cdot\mathbf{P}_{j+1} = \mathbf{D}_j$

where $\fs4 \mathbf{I}$ is the identity matrix, and $\fs4 \mathbf{D}_j$ has elements the right hand sides of the Explicit method solution, namely

$\fs4 \mathbf{D}_j = \left( \begin{array}{C} \Delta_- (S_1 - S_2) \\ p_+ P_{2,j} + (1-p_0) P_{2,j} + p_- P_{1,j}\\ p_+ P_{4,j} + (1-p_0) P_{3,j} + p_- P_{2,j}\\ \vdots \\ p_+ P_{N_s,j} + (1-p_0) P_{N_s-1,j} + p_- P_{N_s-2,j} \\ \Delta_+ (S_{N_s} - S_{N_s-1}) \end{array} \right)$

The $\fs4 \theta$ method is a cocktail of $\fs4 \theta\%$ Implicit and $\fs4 (1-\theta)\%$ Explicit. By multiplying the two corresponding systems with their respective weights, and summing up, we end up with a tridiagonal system of the form

$\fs4 \left[ \theta\mathbf{A}+(1-\theta\mathbf{I})\right] \cdot\mathbf{P}_{j+1} = \theta\mathbf{C}_j+(1-\theta)\mathbf{D}_j$

As a triagonal system, it can be solved using any of the methods described with the Implicit scheme.

6. The Crank-Nicolson method

The Crank-Nicolson method (often misspelled as Crank-Nicholson) is a special case of $\fs4 \theta=1/2$ . In this case, the above systems simplify to

$\fs4 \mathbf{A}^\ast\cdot\mathbf{P}_{j+1} = \mathbf{C}^\ast_j$

with

$\fs4 \mathbf{A}^\ast = \left( \begin{array}{CCC} \begin{array}{CCCC} 1 & -1 & & \\ \frac{-p_-}{2} & 1+\frac{p_0}{2} & \frac{-p_+}{2} & \\ & \frac{-p_-}{2} & 1+\frac{p_0}{2} & \frac{-p_+}{2} \end{array} & & {\LARGE 0} \\ &{\LARGE \ddots}& \\ {\LARGE 0} & & \begin{array}{CCCC} \frac{-p_-}{2} & 1+\frac{p_0}{2} & \frac{-p_+}{2} & \\ & \frac{-p_-}{2} & 1+\frac{p_0}{2} & \frac{-p_+}{2} \\ & & -1 & 1 \end{array} \end{array} \right)$

and

$\fs4 \mathbf{C}^\ast_j = \left( \begin{array}{C} \Delta_- (S_1 - S_2) \\ \frac{p_+}{2} P_{2,j} + (1-\frac{p_0}{2}) P_{2,j} + \frac{p_-}{2} P_{1,j}\\ \frac{p_+}{2} P_{4,j} + (1-\frac{p_0}{2}) P_{3,j} + \frac{p_-}{2} P_{2,j}\\ \vdots \\ \frac{p_+}{2} P_{N_s,j} + (1-\frac{p_0}{2}) P_{N_s-1,j} + \frac{p_-}{2} P_{N_s-2,j} \\ \Delta_+ (S_{N_s} - S_{N_s-1}) \end{array} \right)$

What links here?

Got a question?

A short note

''To stop bots posting Viagra adverts as comments I have put a password in place. It just reads AEKARA, which you can use to edit the pages on this site. Sorry for any inconvenience but it was getting a real pain.

Comments^(add/edit)

jpeclqpdfukyuofzgqui, http://carolinaartmag.com/ Buy Zoloft, wAvKhQA.

Main.SideBar (edit)

pmwiki.org