3.1 Introduction

The integral transform technique can be applied to solving the option pricing problem under a range of underlying dynamics and payoff types. There are numerous examples where integral transforms have been used in the option pricing literature. Scott (1997) uses Fourier transforms to value European options under jump-diffusion with both stochastic volatility and stochastic interest rates. Carr and Madan (1999) with a particular focus on the variance gamma model use Fourier transforms to motivate numerical algorithms using the fast Fourier transform. The American strangle has been analyzed by Chiarella and Ziogas (2005) using a Fourier transform approach, under the assumption that the underlying dynamics are the classic geometric Brownian motion.

The main advantage of the Fourier transform method is that the solution may be expressed in terms of a general initial value or payoff function, so that a wider variety of American options, such as puts, calls, butterflies, spread options, and max-options can all be handled systematically.

In this section we derive the linked system of integral equations for the price and early exercise boundary of an American call under Merton’s jump-diffusion dynamics. We also derive the limit of the early exercise boundary at maturity, and discuss a numerical algorithm for solving the linked integral equation system. We do so by extending to the jump-diffusion situation the quadrature integration technique of Kallast and Kivinukk (2003). The algorithm used has the added advantage of generating values for the price, delta, and early exercise boundary. The issue of the existence and uniqueness of the solution to the nonlinear integral equation that arises in the solution of the free boundary value problem was raised by Myneni (1992) and finally settled by Peskir (2005) in the case of pure diffusion dynamics. It still remains to extend that analysis to the case of jump-diffusion dynamics.

We focus on deriving solutions to the partial differential equation (PDE) for the American call price. A natural solution technique here is the integral transform approach, which (see Debnath, 1995) has been very successfully employed in a wide range of PDE problems in the natural sciences. One of the difficulties with dealing with American options using this technique arises from the fact that one has to solve the PDE on a region restricted by the early exercise, or free, boundary. McKean (1965), who seems to have been the first to consider the American option pricing problem, solves the homogeneous PDE in a restricted domain by using an incomplete Fourier transform. An alternative approach, developed by Jamshidian (1992), replaces the homogeneous PDE with an equivalent inhomogeneous PDE on an unrestricted domain. The solution to this alternative formulation can then be derived by using the standard Fourier transform, and then through an application of Duhamel’s principle. In this section we provide this extension of Jamshidian’s formulation to the jump-diffusion case.

While some authors, in particular Pham (1997) and Gukhal (2001), derive integral equations for the price and free boundary of American options under jump-diffusion they do not discuss how they can be solved numerically. In this section we solve the linked integral equation system that arises for the American call and its free boundary in the case of jump-diffusion. In developing a numerical scheme for the linked integral equation system we obtain a simplification of the integral terms over the jump-size distribution that reduces the computational burden by reducing the dimension of the multiple integration involved. We give some results on the behavior of the early exercise boundary at expiry that are needed to start the numerical procedure. We use the proposed numerical integration scheme to find the price, delta, and early exercise boundary of American calls with log-normal jump sizes. We also demonstrate that the method is often more efficient than a simple two-pass Crank-Nicolson finite difference scheme and is competitive with the method of lines of Meyer (1998) (alternatively, see Meyer, 2012).

Section 3.2 outlines the free boundary problem that arises from pricing an American call option under Merton’s jump-diffusion model. Section 3.3 applies Jamshidian’s method to derive an inhomogeneous PIDE for the American call price, which is then solved using Fourier transforms. We thus obtain the linked integral equation system for the free boundary and option price. We derive the limit of the free boundary at expiry in Section 3.4, and find that this limit is different from that found for pure diffusion models. Section 3.5 analyzes the integral equations in the case where the jump sizes follow a log-normal distribution, as suggested by Merton (1976). Section 3.7 outlines the numerical integration method used to solve the linked integral equation system for the free boundary, price, and delta of the American call. Since the integral equation for the call value and the integral equation for the free boundary are interdependent, we provide a method to handle this interdependence in order to use the two-pass sequential procedure that works well in the non-jump case. Numerical results detailing the efficiency of this algorithm are provided in Section 3.8. As this section summarizes the paper by Chiarella and Ziogas (2009) we shall refer the reader to that paper for many of the proofs.³

3.2 Problem Statement—Merton’s Model

As we drop the stochastic volatility component of Section 2 we simply write to denote the price of an American option written on the underlying asset at time to expiry . In this case the free boundary only depends on so we write it as . Because in this section is constant the dynamics for follows the jump-diffusion process

(14)

where in addition to the notation introduced in Section 2 we set the instantaneous variance per unit time as a constant and is a standard Wiener process under the physical measure.

The PIDE (4) for in the current case becomes⁴

(15)

which has to be solved in the region and . Given a form for , we can define a new intensity, , and jump-size distribution, , which fully incorporate the term , such that (15) can be written as

(16)

The market incompleteness of the jump-diffusion option pricing problem is reflected in the fact that the choice of and is at the discretion of the model builder, so that the associated risk-neutral density is non-unique. As stated earlier, we take the view here that the model builder would calibrate and directly to market data without needing to determine a risk-neutral density for the pricing problem at hand. Henceforth, for ease of notation, we shall simply refer to the jump risk-adjusted intensity and jump-size density in (16) as and respectively.

By use of (3), the PIDE (16) can be written as

(17)

In the case of an American call option, the initial and boundary conditions (5, 7–10) become

(18)

(19)

(20)

(21)

and the PIDE (17) is solved subject to these.⁵

If we were to use the approach of McKean (1965) we would introduce an incomplete version of the Fourier transform, defined by (note that , and )

(22)

Inversion of the transform is readily carried out, and the end result is a linked system of integral equations for and . This solution method comes at the expense of the drawbacks reported by Chiarella and Ziogas (2009).⁶

We instead seek a more efficient alternative for solving (17–21) using the standard Fourier transform.

3.3 Jamshidian’s Representation

One of the major difficulties in solving the PIDE (17) subject to the boundary conditions (18–21) is that the solution is sought on a restricted domain for the stock price , and furthermore the boundary of this domain is itself unknown a priori and needs to be determined as part of the solution process. In the pure diffusion case, Jamshidian (1992) demonstrates that by evaluating the PDE for the American call price when , one can reformulate the free boundary problem in the restricted domain as an inhomogeneous PDE in the unrestricted domain . This inhomogeneous PDE can then be more readily solved by traditional solution techniques such as Fourier transforms. We note that the free boundary value problem (FBVP) given by (17–21) involves a homogeneous PIDE to be solved in the restricted asset price domain . We shall apply Jamshidian’s approach to reformulate the PIDE (17) and associated boundary conditions as an inhomogeneous PIDE on an unrestricted domain.

We highlight the fact that and are continuous for and , as given by the value-matching condition (20) and smooth-pasting condition (21). Jamshidian’s approach can only be applied with confidence when such continuity holds. We now state the main result that converts the homogeneous PIDE on a restricted domain to an inhomogeneous PIDE on an unrestricted domain.

Gukhal (2001) provides clear economic interpretation for the inhomogeneous term that arises in Eq. (23). The term represents the net cash flows received from holding the portfolio whenever is in the stopping region. This is already familiar from the pure diffusion case (see, for example, Kim, 1990). The integral term arises entirely because of the introduction of jumps in the price process for . Note that if no jumps were present (=0) then this term would be zero, and the inhomogeneous term would become the same one presented by Jamshidian (1992). This additional term captures the rebalancing costs incurred by the option holder whenever the price of the underlying jumps down from the stopping region back into the continuation region. Figure 2 illustrates this effect in detail. Consider the case where, during the life of the option contract, the underlying asset price is at . Since the value of is in the stopping region, the holder of the option will currently possess the portfolio . If a jump of size occurs such that , then the portfolio held by the investor will now be worth less than the unexercised American call. This difference is the cost being captured by the integral in the inhomogeneous term in (23).

Having derived the inhomogeneous PIDE for we next use Fourier transforms to find the solution. Our first step is to transform the PIDE to an equation with constant coefficients and a “standardized” strike of 1. Let and , with . The transformed PIDE for is then

(25)

where . Equation (25) is to be solved in the time domain , and the unrestricted region , subject to the initial and boundary conditions

(26)

(27)

(28)

It is worth noting that the smooth-pasting condition still holds, although we do not explicitly require it when solving (25) for since it is incorporated in the inhomogeneous term.⁷

Since the -domain is now the unrestricted region , the Fourier transform of the inhomogeneous PIDE (25) can be found. Define the Fourier transform of , as

(29)

with the corresponding inversion formula

(30)

where is the complex number. Applying this Fourier transform to (25), we can reduce the inhomogeneous PIDE for to an inhomogeneous ordinary differential equation (ODE) for , whose solution is readily found.

When taking the Fourier transform of (25), we note that and do not approach zero as . A number of approaches have been suggested for dealing with this difficulty. Carr and Madan (1999) and Lee (2004) suggest introducing a damping function of the form for some positive constant , and then apply the transform to the dampened option price , which does tend to zero, along with , as . The desired function can be readily recovered after the solution in transform space has been inverted. Lewis (2000) gives another approach which proves that the Fourier transform is still valid when solving for in this case, although one must instead take the complex Fourier transform in a strip of the complex plane. Regardless of which approach is used to make the Fourier transform applicable, it turns out that both methods are equivalent to simply assuming that and tend to zero as , and applying the standard transform accordingly. Thus in order to simplify the technical discussion, we shall simply apply this assumption and suppress the finer details involved.^8,9

The first term on the right-hand side in (34) is the Fourier transform of the PIDE (25) in the case of a European call option under jump-diffusion dynamics. In this case the last term of the right-hand side of (25) does not appear, and it is the latter term involving the free boundary that gives rise to the second term in Eq. (34).

Now that has been found, we may use the inversion formula (30) to recover , the American call price in the - plane. By taking the inverse Fourier transform of (34), we have

(35)

where is the value of the corresponding European call written on and is the early exercise premium for . By performing the inversions, we can determine the analytic forms of and and these are given in Propositions 3.3 and 3.4 below.

Equation (36) is of course Merton’s (1976) solution for a European call option under jump-diffusion, with general jump size density . Next we shall determine the early exercise premium .

On the left-hand side in (40) we introduce the notation to indicate that the dependence on the option price is that of a functional (rather than of a function). It in fact has the form

(42)

for an appropriate function , a notation that will recur in many of the subsequent formulae.

Each of the linear terms in (38) represents discounted expected cash flows incurred by the option holder when , as discussed previously for the interpretation of the inhomogeneous term in (23); the term is the expected value at time to maturity of the component in (23), and the term is the expected value of the integral term in (23). Combining and , we can now write down the integral equation for the American call option price, .

Equation (43) is indeed an integral equation since the unknown option price also appears under the time integral on the right-hand side, in particular through the term. This is in contrast to the pure diffusion case where the equation corresponding to (43) (when and so that the term drops out) is simply an integral expression for the option price that can be evaluated once the free boundary has been determined.

The solution (43) is readily compared with that of Gukhal (2001), who derives (43) by generalizing the compound option approach of Kim (1990) to the jump-diffusion case. The three additive components of the call value in Eq. (43) each have a clear economic interpretation, as outlined by Gukhal (2001). The first term, , represents the European component of the American call option’s value, while the remaining two terms combine to form the total early exercise premium. The middle term is a natural extension of the early exercise premium that arises in the pure diffusion case. More specifically, this term calculates the dividend received when holding the underlying, less the interest payable on a loan of size . Thus captures the potential income to the option holder should the option be exercised to buy the underlying by borrowing at the risk-free rate. The third term, , arises entirely due to the introduction of jumps in the price process for , and captures the rebalancing costs incurred by the option holder whenever the price of the underlying jumps down from the stopping region into the continuation region as illustrated in Figure 2.

In Eq. (43), the value of the American call option is expressed as a function of the underlying asset price , and time to maturity . As we have already noted, Eq. (43) also depends upon the unknown early exercise boundary, . By requiring the expression for to satisfy the early exercise boundary condition (20), we can derive the integral equation for , namely

(44)

Note that the integral Eq. (44) depends upon the unknown call value , which arises entirely from the integral terms that have been introduced by the presence of jumps in the dynamics for .

The structure of the integral equation system consisting of (43) and (44) can be made more transparent by writing it succinctly as

(45)

(46)

where the definitions of the functions and can be inferred from the right-hand sides of Eqs. (43) and (44), respectively. The interdependence of (45) and (46) is obvious, and it is this interdependence that makes numerical implementation more involved than for the corresponding no-jump problem. There the dependence is sequential, that is, first one solves for the free boundary, which then feeds into an integral expression for the option price. In fact, Eqs. (43) and (44) form a linked system of non-linear Volterra integral equations of the second kind. Thus in order to implement these integral equations for the free boundary and call price, we need to develop numerical techniques to solve the linked integral equation system (43) and (44).

Before concluding this subsection, we present an alternative form for the double integral involving the function in Eq. (40) and defined in (41).

From an economic point of view, the modified representation in (47) is less intuitive than the original; however, it offers significant advantages when attempting to evaluate (40) numerically for specific forms of . In particular, we will see in Section 3.5 that when is the log-normal density function given by Merton (1976), the innermost integral in (47) can be evaluated analytically. In this way we are able to reduce (47) to a one-dimensional integral, which makes the task of numerically evaluating (47) much simpler. We remind the reader that the term in turn must be integrated over time to maturity so that altogether the jump term would in this case involve the evaluation of a double integral.

3.4 Limit of the Early Exercise Boundary at Expiry

In order to implement numerical schemes we need to know the value of the free boundary just prior to expiry, at . Early literature, for instance, Amin (1993) and Carr and Hirsa (2003), simply assumed that this limit is identical to the corresponding pure diffusion case. However, Chiarella and Ziogas (2009) show that this limit is in fact more subtle. They derive the limit by analyzing the inhomogeneous term in the PIDE (23), and find that the presence of jumps does in fact have an impact on the early exercise boundary at expiry. This difference is expressed analytically in Proposition 3.7 below, and is based on the analysis of Wilmott et al. (1993). The simple, intuitive method used here is taken from Chiarella et al. (2004) who demonstrate that the approach of Wilmott et al. (1993) is equivalent to setting the inhomogeneous term in Jamshidian’s (1992) form for the PDE to zero, setting , and solving for the free boundary.

It is worthwhile to observe that when Eq. (48) simplifies to the limit derived by Kim (1990) for the pure diffusion American call free boundary. Note that (48) is an implicit expression for , but it can be solved quickly and accurately using standard root-finding techniques. Furthermore, as the solution to the implicit part of Eq. (48) increases without bound. Thus when , becomes infinite, and we observe the well-known property that it is never optimal to exercise an American call option early in the absence of dividends.

Before concluding this subsection, we shall take a closer look at the properties of Eq. (48), specifically with a view to better understanding the solution to

(49)

where

Once (49) is solved, then the operator can be applied. Since the value of the underlying is always non-negative, we consider the domain when solving (49). It is not possible to provide a simple, explicit summary of the behavior of (49) for various values of , because the integral terms depend upon , and the function involves the parameters and , as well as the jump-size density .

First, we see that it is simple to evaluate at the limits of the domain. Specifically, we can show that

(50)

and

(51)

Thus for to be finite at each extremity of the domain, it is sufficient that we have . In this case, it is clear that is continuous, and (49) will have at least one solution. Since appears only in the limits of the integral terms over the density within , we can safely claim that the behavior of with respect to will be bounded by the behavior of . Further exploration appears difficult without specifying the form of , and we provide a more detailed analysis in Section 3.5.

3.5 American Call with Log-Normal Jumps

Before we begin exploring a numerical solution method for the integral equation system (43) and (44), we shall consider the specific example when the jump-size density, is a log-normal distribution as in the original model of Merton (1976). The probability density function for is given by

(52)

where we set , and is the variance of . Furthermore we note that for this choice of we have .

The last term of (53), which involves a double integral, may be further simplified before implementing (53) numerically.

We note that in the form (54) the term in (53) now only involves a single integral, which results in a considerable saving in computational effort.

By use of (44), the integral equation for the early exercise boundary, , in the case of log-normal jump sizes, is given by

(56)

where and are given by (39) and (54), respectively.

3.6 Properties of the Free Boundary at Expiry

Since we are now considering a specific form for , we consider again the topic of analyzing the behavior of the early exercise boundary, , as . First we evaluate (48) for the log-normal density .

To develop an understanding of the case where , we explore numerically the equation

(61)

where

and we recall that . It is not possible to provide a simple, explicit summary of the behavior of (61) for various values of because the cumulative normal density functions depend upon , and the function involves the parameters , , , , and , all of which have a significant impact on the value of . Nevertheless, we can use numerical examples to offer some additional insight into the nature of the solution of (61).

For log-normal jump-sizes we can show that

(62)

When it is clear that is continuous, and (61) will have at least one solution. We can demonstrate by example that is not monotonic, nor is it strictly bounded by the end values in (62). This makes it difficult to prove that for Eq. (61) has at most one solution. Since appears only inside cumulative normal functions within , the behavior of with respect to will be bounded by the behavior of . We recall that and that is a smooth, continuous function of for . From this we postulate that the function will not display any oscillatory features within the domain under consideration.

To provide numerical evidence in support of our claims regarding Eq. (61), we now present a plot of (62) which is typical of what we have obtained for a range of empirically relevant parameter values. Setting , , and , we plot in Figure 3 the functions and for various values of and . When and , we can see that . On the other hand, when and , we now have . In both cases it is clear that is not bounded by these endpoint values, and we can see that the relative values of and directly influence the values of and .

Changing the values of the jump-parameters will vary the value of . In addition, changes to , , and will resize the curve , although the basic shape remains unchanged. This claim is based on further numerical examples, which can be found in Chiarella and Ziogas (2009).

The last and most important scenario we consider here is when . In this case, is no longer finite, instead increasing without bound as . Figure 4 demonstrates the behavior of with for a different selection of parameter values. It is clear from the plot that there is no solution to . Furthermore, the only way that Eq. (61) will be satisfied when is by taking the limit as , in which case both sides of (61) will increase without bound. This reflects in yet another way the fact that when , the free boundary at becomes infinite, and it is never optimal to exercise an American call early in the absence of dividends.

3.7 Numerical Implementation

We now provide a numerical scheme with which to evaluate the linked integral equation system for the option price and free boundary formed by (53–56). The proposed method is an extension of the quadrature scheme used by Kallast and Kivinukk (2003) for the pure diffusion case. Here we focus on the adjustments that are needed to deal with the introduction of jumps into the dynamics for . We first discretize the time to maturity variable, , into equally spaced intervals of length . Thus for , and . We denote the call price profile at time step by , and similarly the free boundary at time step by = . Using a standard numerical technique that is applied to Volterra integral equations, we can solve the system (53–56) for increasing values of , until eventually the entire free boundary and price profile are found. When calculating the infinite summations, we continue adding terms until the size of the Poisson coefficient for a given value of is less than . For the parameter values considered here, this typically results in the use of around 30 terms in the summation. In order to start the algorithm we require the initial value of , which is simply the payoff function, and , where , which is given by Eq. (60).

Since the integral term in (54) depends upon , an approximation will be needed for . At each time step we have found that a suitable approximation is given by , which is simply the American call price at the previous time step. The price at the time step is calculated for a suitably large number of evenly spaced values. Here we use 25 points in the range . All necessary interpolation is conducted using cubic splines fitted locally through seven values of . We then use Newton’s method to solve for the early exercise boundary, as in Kallast and Kivinukk (2003), with two necessary additions. The first addition addresses the evaluation of the inner integral (54) over the interval . This is computed using Gaussian integration of moments, with parameter . Full details of this Gauss quadrature scheme can be found in Abramowitz and Stegun (1970) (Chapter 25, p. 921). The second addition relates to finding the derivative of (56) with respect to for use in Newton’s method. This is given by (57) for , evaluated at . Since it is difficult to determine the limit of the integrands in (57) as , we resolve this by taking the limits as for the option price integrands in (53) and differentiating these with respect to , as is done by Kallast and Kivinukk (2003). These limits are all finite, including the new limit required for the jump-related integral term, and the required derivatives are easily determined. Since we need to evaluate the expression (57) for for use in Newton’s method, there is no significant additional computation time required to evaluate the American call delta once the free boundary has been estimated.

Having determined the discretized forms for the price and delta of , we then use Newton’s method to solve for . Before proceeding to the next time step, we use to calculate a new approximation for , which is required when evaluating the double integral term at all subsequent time steps. This update for is essential to ensure that the estimated free boundary remains monotonic. Note that as the value of increases, the computational burden will also increase at a “faster than linear” rate (the reason being that the integration at step depends on all values of and for ).

It should be noted that the proposed numerical scheme does not involve any iterations with respect to the approximation of the integral term. It is possible to improve the accuracy of the algorithm by updating the approximation for the integral term at the th time step using the most recently computed estimates for and . In practice we have found that such an iteration does not add significantly to the accuracy of the results (up to the order of accuracy considered in Section 3.8), and that computation time is at least doubled by the introduction of the iteration process. Thus we have chosen not to iterate with respect to the integral term approximation.

To explore the efficiency of the proposed numerical integration method, we compare it with two alternative numerical methods. The first method involves a finite difference solution for the PIDE (17). We apply the Crank-Nicolson scheme to all terms except for the integral. We initially estimate the integral term by approximating with the explicit approximation , as in Carr and Hirsa (2003). We then evaluate the integral using the Hermite-Gauss quadrature scheme (see Abramowitz and Stegun, 1970). The resulting tridiagonal matrix is inverted using LU-decomposition, and the early exercise condition is then applied to the solution at each time step. An evenly spaced grid is used, and the free boundary is estimated at each time step using cubic spline interpolation of the price profile, combined with the bisection method.

To improve the accuracy of the Crank-Nicolson solution, we use a two-step procedure at each time step, details of which are given by Chiarella and Ziogas (2009).

The second method we consider is the method of lines approach as presented by Meyer (1998). Meyer only considers discrete jump-size distributions. Here we extend this method to allow for a continuous jump-size density, , again evaluating the integral term using a Hermite-Gauss quadrature scheme, combined with local cubic spline interpolation of the price profile at each iteration. The method of lines readily provides estimates for both the price and delta for the American call option, without the need for additional computation. Unlike the Crank-Nicolson scheme, the method of lines solution is allowed to iterate until the largest observed change in the option price profile is less than . The scheme we use is second-order accurate in time, and a first-order scheme is applied for the first three time steps.

3.8 Numerical Results

To analyze the efficiency of the numerical integration method, we compute the price and delta of an American call option with 6 months to maturity, and a strike price of . The global variance¹¹ of returns, , is set equal to . The jump intensity is set to , and the jump variance is . We then consider six different parameter sets, specifically taking values of 0.95, 1.00, and 1.04, along with the combinations , and , . Note that implies upward jumps on average, and implies downward jumps on average. When , the expected price change from a jump is zero. The diffusion coefficient, , is chosen such that the global variance was preserved for varying values of . Table 1 summarizes the values of used to ensure that the global variance was the same for each combination of and .

We compute the root mean-square error (RMSE) using option prices and deltas with , and . This is repeated for each of the six parameter sets, from which the average runtime and RMSE are then calculated. Note that in all cases the runtimes include the time required to compute the free boundary, price, and delta for the American call. For the integration method we use 20 integration points for the Gauss quadrature scheme, and consider a sequence of 10 different time step values, with .

For the Crank-Nicolson method the integral term is approximated using 50 integration points, and we again use 10 time step values, with . We set the number of space steps equal to double the number of time steps. Similarly, we use 50 integration points to estimate the integral term in the method of lines. We also use 10 time step values, with , and the number of space steps is set to five times the number of time steps. The code for all methods has been implemented using LAHEY^TMFORTRAN 95 running on a PC with a Pentium 4 2.40 GHz processer, 512 MB of RAM, and running the Windows XP Professional operating system.

In assessing the efficiency of the numerical integration method, we use a Crank-Nicolson solution with 10,000 time steps and 5000 space steps for the true solution. Since the numerical integration scheme requires evaluation of the option delta as part of the solution, it is also worthwhile to consider the efficiency with which delta is calculated. The true delta is estimated from the Crank-Nicolson solution using the central difference approximation for . To demonstrate that this is a valid choice for the true solution, we also compute the prices and deltas using the method of lines approach with 1000 time steps and 5000 space steps. As mentioned previously, the method of lines computes the price, delta, and early exercise boundary simultaneously. The prices are provided in Table 2, with the deltas given in Table 3. We also provide the root mean-square differences (RMSD) between the two methods for each set of parameters, along with an average RMSD value. In both cases we find that for the values of under consideration these methods are consistent to at least four decimal places, and thus we conclude that the Crank-Nicolson method using 10,000 time steps and 5000 steps in the space variable provides a satisfactory estimate for the true price and delta.

The relative efficiency of each method is shown in Figure 5 by comparing the RMSE as a function of runtime. Figure 5a shows the average RMSE error for the American call price, and Figure 5b displays the same information for the delta. Note that the average runtimes for each discretization level are the same in Figure 5a and b since the price and delta were found using a single algorithm. Firstly, we find that for the parameters and discretizations considered, the numerical integration method consistently displays greater efficiency than the Crank-Nicolson scheme for the American call price, and furthermore, numerical integration is more efficient than Crank-Nicolson when computing delta for computation times of up to 50 s.

We find that the method of lines consistently outperforms the Crank-Nicolson scheme, and in the majority of cases, the delta values computed by the method of lines are more accurate than those obtained using numerical integration. When computing prices for runtimes of between 1 and 20 s, however, numerical integration is able to outperform the method of lines. We also note that the numerical integration algorithm has a slower rate of convergence for the delta relative to the other two methods. This could be attributed to cumulative numerical integration error as the number of time steps, and hence integration points, is increased. The rate of convergence for the numerical integration method is clearly better when computing the option price.

Thus from Figure 5¹² we conclude that of the three methods under consideration, the method of lines is consistently more accurate for runtimes beyond 20 s. We also find that the numerical integration method consistently outperforms the Crank-Nicolson scheme when computing the option price, and is competitive with Crank-Nicolson when computing the delta for runtimes of less than 50 s. Thus we can see that a simple extension of the numerical integration scheme presented by Kallast and Kivinukk (2003) to include log-normal jumps produces a numerical method that is comparable with both the method of lines and the Crank-Nicolson scheme; however, there is room for improvement in the computation of delta, in particular when the number of time steps is increased beyond 40. We also note that since the magnitude of the RMSE is much larger for the option price, the best way to select the optimal numerical method is to maximize the pricing efficiency while being aware of the RMSE for the deltas. For example, for a runtime of 20 s the method of lines is more efficient than numerical integration, since both methods have similar pricing accuracy, but the method of lines offers a better delta estimate in this case. Alternatively, for a runtime of 5 s, numerical integration is the most efficient, since it provides better price estimates than the method of lines for the same accuracy in delta.

Chiarella and Ziogas (2009) give a lengthy discussion of the impact of jumps on the free boundary and option prices. However, lack of space prevents us from summarizing that discussion here so we refer the interested reader to the paper.

4.1 Numerical Solution Using the Method of Lines

Given that it worked well in the jump-diffusion situation of Section 3.5 we continue with the method of lines, which has also been applied to the stochastic volatility case by Adolfsson et al. (2013). As we pointed out in Section 3.5 the method of lines also has the advantage that the price, free boundary, delta, and gamma are all found as part of the computation. The method of discretizing the PIDE is basically the same as in Section 3.5 and in this section we show how to adapt the implementations to also incorporate stochastic volatility. The section is a shortened version of Chiarella et al. (2009) to which we refer the reader for more details.

The key idea behind the method of lines is to replace an PIDE with an equivalent system of one-dimensional integro-differential equations (IDEs), whose solution is more readily obtained using numerical techniques. When volatility is constant, the system of IDEs is developed by discretizing the time derivative as discussed in Section 3.5. For the PIDE (11), we must also discretize the derivative terms involving the variance, , and adjust the algorithm for dealing with the integral term to cater for the fact that the option price and free surface also depend upon the variance .

We begin by setting , where . Typically we will set the maximum variance to be . Furthermore, as in Section 3.5 we discretize the time to expiry according to , where . We denote the option price along the variance line and time line by , and set

(63)

which is of course the option delta at the grid point.

We now select finite difference approximations for the derivative terms with respect to . For the second-order term, at the grid point we use the standard central difference scheme

(64)

and for the cross-derivative term at the grid point we use the central difference approximation

(65)

Since the coefficients of the second-order derivative terms go to zero as , we use an upwinding finite difference scheme (see Duffy, 2006, Chapter 8) for the first-order derivative term, such that, at the grid point we have

(66)

Since the second-order derivative terms both vanish as , upwinding helps to stabilize the finite difference scheme with respect to .

The integral term in (11) at each grid point is estimated using numerical integration as in Section 3.5. Assuming, as in that section, that the jump sizes are log-normally distributed, with distribution ¹³ given by (52). Note that the method developed here could allow a wide range of choices for , for instance, the double exponential distribution of Kou (2002).

Making the change of variable , the integral term in (11) becomes

(67)

We approximate (67) at the grid point with the discretization obtained by applying the Hermite-Gauss quadrature scheme, namely

(68)

where and are the weights and abscissas for the Hermite-Gauss quadrature scheme with integration points. As in Section 3.5 we refer the reader to Abramowitz and Stegun (1970) for the computation of the weights and abscissas. We interpolate for the required non-grid-point values of using cubic splines fitted in along the line at the grid point (). We handle the discretization for the time derivative as in Section 3.5.

Applying (64–68) and the time discretization to the PIDE (11), we must now solve a system of second-order IDEs at each time step and variance grid point. For the first three steps, the IDE at the grid point and is

(69)

and for all subsequent time steps the IDE is

(70)

We require two boundary conditions in the -direction, one at and the other at . For large values of , the rate of change of the option price with respect to diminishes. So for sufficiently large values of , one can treat this rate of change as zero without any impact on the accuracy of the solution at other values of . Thus we set along the variance boundary . When is zero, we fit a quadratic polynomial through the option prices at , , and , and then use this to extrapolate an approximation of the price at . This provides us with a satisfactory estimate of the price along for the purpose of generating a stable solution for small values of .

After taking the boundary conditions into consideration, at each time step we must solve a system of second-order IDEs along the variance lines. This is done using a two-stage iterative scheme. As in Section 3.5 first we treat the IDEs as ODEs by using as an initial approximation for in the integral term . We then solve the ODEs for increasing values of , using the latest available estimates for , and . The initial estimates for and are simply and . Otherwise we use the latest estimates for and found during the current iteration through the variance lines. We iterate until the price profile converges to a desired level of accuracy. Second, once the price has converged, we update the estimate of the integral term using the current price profile estimate, and repeat the process until convergence is obtained for both levels of iteration. We then proceed to the next time step.

The generic first-order form for (69) and (70) is

(71)

(72)

where is a function of , , , , , , and . We solve (71) and (72) using the Riccati transform (see Meyer and van der Hoek, 1997 for details).¹⁴ Note that we are only able to apply the Riccati transform to the system (71) and (72) provided that both equations are treated as ODEs. This is made possible by approximating using the values of the previous time step, as stated earlier, and then using an iterative technique in which the integral term is updated until the price converges. For later use we note that the right-hand sides of Eqs. (71) and (72), respectively, yield the delta and gamma at each point of the grid.

The Riccati transformation is given by

(73)

where and are solutions to the initial value problems

(74)

(75)

and is the solution to

(76)

where we denote the free boundary at grid point by .¹⁵ Since is independent of , we begin by solving (74) and storing the solution. Next we solve (75) for increasing values of , ranging from , where we select sufficiently large such that will be guaranteed. We then step forward in using the generated values of and until we encounter the value such that¹⁶

(77)

and thus is the value of the free boundary at grid point .¹⁷ Once has been determined we then solve (76) starting at and sweeping back to . Finally we use the calculated values of , and in (73) to determine the option price at each grid point along the variance lines at time to maturity .

In Figure 6 we illustrate one sweep through the grid points on the plane. In Figure 7 we show the stencil for the typical grid point in Figure 6; this essentially shows the grid point values of that enter the term on the right-hand side of (72). Figure 8 then illustrates the solution of (75) along a line in the -direction from a typical grid point in the plane.

4.2 Numerical Solution Using the Componentwise Splitting Method

Ikonen and Toivanen (2007) have proposed a non-standard finite difference method that involves discretization of the spot price on non-uniform grids in order to solve the American option pricing problem under stochastic volatility. We employ the same method, with the only difference being that we extend it to handle the integral over jumps term. Here, we give the basic details of the componentwise splitting method in order to make clear how the jump term is incorporated. We refer the reader to Ikonen and Toivanen (2007) (henceforth IT) for full details.

For a reference grid point , we have neighboring grid points at and at , where and are the local left and right grid step sizes for the spot price, respectively. We discuss later how these step sizes are chosen. In the variance direction we employ a uniform grid with the step size and, hence, neighboring grid points are at and at .

By use of the Taylor expansions at and , the first-order and second-order derivatives in the -direction are given by the finite difference approximations

(78)

and

(79)

The first-order and second-order derivatives in the -direction are handled in the usual way with a central difference for the first-order derivative.

IT discuss the second-order cross-derivative terms when the correlation is positive; however, we wish to handle both the positive and negative correlation cases. Hence, here we detail the negative correlation case and refer the reader to IT for the case of positive correlation. By considering Taylor expansions at and IT obtain for the second-order cross-derivative terms the approximations

(80)

and

(81)

which involve derivatives only in the - and -directions. In order to obtain a discretization with the desired so-called M-Matrix properties (that is, positive diagonal elements and negative sub-diagonal and super-diagonal elements) IT suggest the convex combination

(82)

of (80) and (81) for the second-order cross-derivative. The weighting parameter has a value between zero and one. For most of the grid points we use the weight . On the boundaries¹⁸ where the boundary condition (7) is posed we use to avoid crossing the boundary in the -direction. On the boundaries , where the boundary condition (9) is imposed, we use the weight to avoid crossing the boundary in the -direction. For small the weight is set to zero to obtain the -Matrix property. We refer the reader to IT for a discussion analogous to the above for the positive correlation case.

Using the approximation (82) for the cross-derivative in the partial differential equation (11), we obtain a form which contains only the partial derivatives in the -direction and in the -direction. This intermediate form reads

(83)

where the last item, , is the jump term from (67) which is approximated as in (68).

A seven point finite difference stencil around the typical point, which is displayed in Figure 9, is obtained by using the finite difference approximations introduced in the previous part of this section for the spatial derivatives appearing in (83). We will discretize and solve (83) without jumps first and then we will add the jump term back later. The spatial discretization leads to a semi-discrete equation which has the matrix representation

(84)

where is a block tridiagonal matrix and is a vector of length .

Next, we implement the Crank-Nicolson method to discretize the semi-discrete problem (84) as

(85)

where is the number of time steps and is the identity matrix.

After the discretization of the underlying PIDE with two spatial variables an approximate price of an American option can be obtained by solving the sequence of linear complementarity problems (LCPs) (see Wilmott et al., 1993)

(86)

for . The matrices and in (86) are defined by (85) for the Crank-Nicolson method. The initial value is given by the discrete form of the payoff function of the option, so that the th element of is given by

(87)

In order to solve the sequence (86) of LCPs more efficiently, we implement the componentwise splitting method for LCPs based on the decomposition of the matrix in (84) according to

(88)

The matrices contain the couplings of the finite difference stencil in the -direction, in the -direction, and in the -direction, respectively. We refer the reader to IT for the full details of this decomposition.

We follow IT in using a second-order accurate splitting method by performing a Strang symmetrization (see Strang, 1968) for the splitting method which uses the Crank-Nicolson method. We choose to perform first a half time step with and then with , a full time step with , and finally a half time step with and then with . The notations used are

(89)

in terms of which the original LCP (86) is approximated by following five LCPs in successive directions:

(90)

(91)

where and run successively over the values

and

while runs over the values .

We will omit the details of the implementations¹⁹ of the above system but again refer the reader to IT.

To be consistent with the Strang symmetrization given by (90) and (91), the evaluation of the integral term should also be decomposed and distributed among the five partial time steps. In fact, we add the integral term to the explicit terms²⁰ of (90) separately and it is evaluated in a similar way as it is in Section 4.1 by using a cubic spline interpolation on the stock prices from the previous time step. The integral jump term is handled in the following way: first, we evaluate at payoff from the previous time step or the result from the latest iteration; then we add 1/6 of to the -direction which is the explicit term of LCPs (90) for and ; we add another 1/6 of to the -direction which is the explicit term of LCPs (90) for and ; next we add 1/3 of to the -direction which is the explicit term of LCPs (90) for and ; and we add 1/6 of to the -direction which is the explicit term of LCPs (90) for and ; finally we add 1/6 of to the -direction which is the explicit term of LCPs (90) for and . Now we have added a full time step integral to the original LCP (86). Next, we evaluate the integral term with cubic spline interpolation based on the new price and calculate the average difference of the successive iterations in the grid. We continue to add the integral terms to LCPs and to calculate the new price based on the new integral if the difference is larger than some tolerance; otherwise, we will proceed to the next time step.

4.3 Numerical Solution Using Finite Difference Method with PSOR

We have implemented a finite difference PSOR to find the benchmark prices of the American options. The implementation of PSOR is detailed in this subsection.

Three variables , and are discretized as

The option prices at those discrete points thus are

with an initial condition:

Similar to the discussions in Ekstrom et al. (2009), we use central differences to approximate most of the first and second derivatives in the PDE but use the forward and backward finite difference approximations on the boundaries other than the time derivative in (11). Thus we set,

and

At , we fit a quadratic polynomial through the option prices at , , and which are the points closest to , and then use this to extrapolate an approximation of the price at . We use the boundary conditions at the boundaries . Those conditions are similarly handled to those in Section 4.1.

All other derivative terms in the -direction vanish at due to the factor occurring in (11), and hence, these terms do not require further treatment.

Boundary conditions at the boundaries and for a call option are

while those for a put option should be set as:

We follow Ikonen and Toivanen (2007) to indicate which grid point values we use to approximate the second-order mixed derivative in order to obtain non-positive off-diagonal weights in the finite difference stencil, which makes the matrix an M-matrix as far as possible.

In the above scheme a nine points stencil will be used. In order to simplify the algorithm and take into account the correlation between the underlying asset and the variance, we use a seven points stencil instead and the mixed derivatives are approximated as by

(92)

and when we have

(93)

The spatial discretization above leads to a semi-discrete equation which has the matrix representation

(94)

where is a block tridiagonal matrix and is a vector of length .

Next, we implement a more general -scheme which includes the implicit (), the Crank-Nicolson (), and the explicit () approaches to discretize the semi-discrete problem (94) as

(95)

where is the number of time steps and is the identity matrix.

After the discretization of the underlying PIDE with two spatial variables an approximate price of an American option can be obtained by solving a sequence of linear complementarity problems (LCPs)

(96)

for . The matrices and in (96) are defined by the left-hand side and right-hand side of (95), respectively. The initial value is given by the discrete form of the payoff function of the option, so that the th element of is given by

(97)

In order to avoid the oscillations that often occur with the CN scheme, we use the implicit Euler scheme () for the first three time steps and then switch to the CN scheme () for the rest of the time steps. We have implemented a PSOR finite difference scheme (see Section 6.2.3 in Kwok (2008)) to solve the sequence (96) of LCPs. The jumps have been handled in the same way as in Section 4.2.

In order to accelerate the convergence of the PSOR, we select the over-relaxation parameter in the algorithm. The free (or early exercise) boundary of the American option is obtained using Newton’s method. However, the option prices are updated with the American condition inside the PSOR, which makes it hard to obtain the free boundary. To solve this problem, original unprojected prices where the American condition is posed are saved and these prices are then used to obtain the free boundary later.

4.4 Numerical Results

To demonstrate the performance of the method of lines algorithm outlined in Section 4.1 we implement the method for a given set of parameter values, chosen in order to best illustrate the impact that stochastic volatility and jump-diffusion may have on the early exercise boundary for an American call option. The parameter values used are listed in Table 4.

We consider the case where , and a time to maturity of 6 months, as this best demonstrates the changes that arise in the free boundary when jumps are introduced. The value of is chosen intentionally large in order to emphasize the impact of stochastic volatility on the free boundary. We assume that jump sizes are log-normally distributed about a mean value of so that in a sense the jumps up and down average out. This allows us to focus on the impact that the Wiener correlation, , has on the free boundary. In addition, the small value of has been chosen so as to avoid further increases to the overall variance of .

When implementing the method of lines we take the following case as an example to show its convergence pattern. We use time steps and variance lines, up to a maximum variance of . We take a non-uniform grid in , splitting the domain into three intervals. Given that the strike price is , the maximum value for is set to 400, with a total of 1138 grid points (denoted by ), distributed between the three intervals such that there are 40 points for , there are 198 points for , and finally 900 grid points for .

For the Hermite-Gauss quadrature scheme in (68) we use abscissa points. All iterative calculations utilize the stopping condition that the maximum over all of is less than , where the superscript denotes the solution at the th iteration. We note that for the parameter values given in Table 4, the solution along the variance lines typically converges in less than iterations, and convergence with respect to updating the integral term (67) generally needs no more than six iterations. Furthermore, the number of iterations along the variance lines reduces by more than a quarter after the first update of the integral term and continues to reduce by more than a half after each update of the integral term. A typical sequence is shown in Table 5. It is also of interest to observe how the total number of variance iterations changes as the number of variance lines changes; this effect is shown in Table 6. It seems that the number of variance iterations increases faster than the number of lines in the -direction. This deterioration in convergence is similar to that observed in a standard Gauss-Seidel scheme, and is probably due to the fact that as in Gauss-Seidel iteration we are using the latest updates for the values as we step through the () grid. It is also worth noting that of all the components within the iterative scheme, computing the integral term (68) is the most computationally intensive, since we must perform extrapolations of with respect to at every point in the grid. Thus we are required to fit a total of cubic splines at each iteration with respect to the integral term, and each spline is fitted using every grid point in .

We refer the reader to Chiarella et al. (2009) for a graph of the free surface, where we note that the free surface generated by the method of lines is smooth, even when jumps are present, a feature not often displayed in the free boundary estimates generated using finite difference methods, such as Ikonen and Toivanen (2004).

We contrast the relative pricing accuracy of both the method of lines (MOL) and componentwise splitting (CS) methods. Using the parameter values in Table 4, and setting the spot variance to , we generate American call option prices for values of equal to , and using the three numerical methods discussed above: the method of lines as outlined in Section 4.1, a componentwise splitting (CS) approach which is detailed in Section 4.2 and the Crank-Nicolson scheme where the system of difference equations is solved using PSOR in Section 4.3. The integral term is approximated in the same manner as for the MOL and CS; we iterate at each time step and update the integral term until the price profile converges.²¹ We use abscissa points for the integral term in all methods. We experimented with each of the above methods with an increase in the number of abscissa points from to , but this led to a significant increase in the run time with no significant change in the option prices.

For both finite difference methods, we find that it is more efficient to update the integral term external to solving the system of difference equations.²² Note that while we do not prove convergence for these iterative schemes with respect to the value of the integral term, convergence is always observed in practice for the parameter values under consideration. The source code for all methods was implemented using NAG Fortran with the IMSL library running on the UTS, Faculty of Business F&E HPC Linux Cluster which consists of eight nodes running Red Hat Enterprise Linux 4.0 (64 bit) with GHz 4 MB Cache Xeon 5160 (dual core) Processors, 8 GB 667 MHz DDR2-RAM.

In the following, we treat the solution for the price from PSOR with 1000 time steps, 3000 variance steps, and 6000 share price steps as the “true” solution for the purpose of comparing the efficiency of both the MOL and CS methods. We treat the delta and gamma from the MOL with 500 time steps, 1000 variance steps, and share price steps as the “true” deltas and gammas. We compute the root mean-square relative difference²³ (RMSRD) using the option prices with values of , and with a spot variance .

Table 7 gives the American call prices produced by the method of lines (MOL), componentwise splitting (CS), and PSOR in the case of negative correlation.²⁴ As a basis for comparison, we also provide runtimes for the different methods, and compute the root mean-square relative differences (RMSRDs) for each method in relation to the “true” solution from PSOR. This allows us to make some further observations about the relative performance of the other two methods. We find that increasing the number of time steps for the MOL has little impact on the prices, while the price accuracy improves more when the grid size in the variance and share price directions is refined. Clearly, the CS method runs faster when the grid is small compared with the MOL; with RMSRD as high as within 98 s it is almost 10 times faster than the MOL and produces results even more accurate than the MOL. However, the accuracy deteriorates when the number of time steps is increased somewhat. It is also observed that the CS method produces prices with some oscillations especially in the case of negative correlation.

If one wishes to achieve a given level of accuracy, we can see from the tables that the MOL seems the best method as it produces a higher accuracy with an RMSRD of within just half the time of CS, which produces results with an RMSRD of . Thus we are confident in asserting that the method of lines is very competitive for evaluating American options under stochastic volatility and jump-diffusion.

To see the overall efficiency of the three methods, we plot in Figures 10–13 below the comparisons of the average accuracy of the American call price, delta, and gamma with the MOL, the CS method, and PSOR. Note that these figures are plotted up to the point on the horizontal axis where the “exact” solution curves start to become artificially steep due to the fact that these are the solutions taken to be the “exact” ones. The RMSRD on the vertical axis in each of Figures 10–12 is calculated for the corresponding set of values, call prices, deltas, or gammas, at the underlying prices of , and and with both correlations, namely, and . In Figure 13 we display the average of the sum of the above three RMSRDs. The runtime on the horizontal axis in all graphs is the computer time taken to produce all three quantities, namely, the call prices, deltas, and gammas.

A number of comments based on the figures and the calculations are warranted. First, it is clear from Figure 13 that the method of lines (MOL) performs best in calculating, to similar accuracy, the call prices, deltas, and gammas. For instance, it costs MOL around 1000 s to achieve an overall relative accuracy of while it costs CS around 1,000,000 s to achieve the same overall accuracy and it takes PSOR even longer. Second, the results from the calculations (see Figures 11 and 12) show that the American call deltas and gammas seem to have a faster convergence rate than the American call prices with the MOL. This is natural because for MOL, within each iteration, the call prices are obtained after working out the deltas and gammas to the same degree of accuracy. We also see from the calculations that the value of the deltas and gammas does not change up to five decimals when refining the grid size which is also evidence indicating that the deltas and gammas with the MOL are much closer to the “true” deltas and gammas than those for both CS and PSOR.²⁵