Pricing American options using a space-time adaptive finite difference method

https://doi.org/10.1016/j.matcom.2010.02.008Get rights and content

Abstract

American options are priced numerically using a space- and time-adaptive finite difference method. The generalized Black–Scholes operator is discretized on a Cartesian structured but non-equidistant grid in space. The space- and time-discretizations are adjusted such that a predefined tolerance level on the local discretization error is met. An operator splitting technique is used to separately handle the early exercise constraint and the solution of linear systems of equations from the finite difference discretization of the linear complementarity problem. In numerical experiments three variants of the adaptive time-stepping algorithm with and without local time-stepping are compared.

Introduction

The Black–Scholes equation introduced 1973 by Black and Scholes in [3] and extended the same year by Merton in [18] is an often solved equation to determine the arbitrage free price of an option. Two common types of options are the European option that only can be exercised at the time of maturity T and the American option that can be exercised at any time tT. Because of this feature the problem of pricing American options will have an internal free boundary.

European options can in some cases be priced using analytic formulas. If that is not possible, numerical methods like the Monte Carlo method [4] or partial differential equation (PDE) based methods like finite differences or finite elements, see [1], [23], can be used. American options require a somewhat different approach due to the early exercise feature in the problem and more involved numerical methods must be used. Using Monte Carlo simulations for pricing the American option is a viable but fairly complicated method compared to pricing the European option. This is so because one must solve an optimal stopping problem to find the optimal exercise rule and then compute the expected discounted pay-off using this rule, see e.g. Glasserman [8]. For many underlying assets the Monte Carlo approach is still the only possible way to go but in other cases PDE methods are competitive.

The problem in a PDE approach can be formulated as a linear complementarity problem (LCP) with inequalities involving the Black–Scholes PDE and some extra constraints. One approach used by many researchers is to discretize with e.g. finite differences and reduce the problem to a sequence of LCPs (one for each time-step). One of the most popular methods for the solution of the LCPs in this category is to use projected successive overrelaxation, (PSOR). This approach is described by e.g. Tavella and Randall in [23].

Here we have adopted an operator splitting technique to solve the LCP. This technique has been used in other numerical fields and was implemented for financial problems by Ikonen and Toivanen in several articles and reports (see e.g. [12], [13]). This method is built upon a finite difference discretization (though it could be used also for other discretizations) and separates the solution of the linear systems of equations from the enforcing of the early exercise constraint. This means that the over all computational time needed is very low since no nonlinear systems of equations need to be solved.

In this paper we will price the American option with constant and stochastic volatility and use the adaptive techniques developed in [15], [16], [21]. Three variants of an adaptive time-stepping scheme with the backward differentiation formula of order 2 (BDF2) are considered, the standard scheme, a scheme modified at the free boundary and one with local time-stepping at the free boundary. The three schemes will be denoted by x1a, x1b and x2 respectively where x should be replaced by either C (for constant volatility) or S (for stochastic volatility) depending on what case we study, see Table 1.

Examples of others that have studied numerical pricing of American options under stochastic volatility include Ikonen and Toivanen in a series of papers e.g. [12], [13], [14], and Oosterlee in [20]. For stochastic volatility we have used Heston’s model, see [11]. Heston’s model is a univariate stochastic volatility model. In [2] a review of more general models such as models including the leverage effect and multivariate models is presented. Since we here focus on how the adaptive method presented in e.g. [21] can be used in a stochastic volatility framework we do not consider other choices of stochastic volatility models or how to estimate parameters in such models any further in this paper.

The paper is organized as follows: In Section 2 we discuss the underlying theory of pricing American options and in Section 3 we talk about the discretization of the problem and the differences in the numerical solution of the constant and stochastic volatility problem. Section 4 introduces the operator splitting technique and Section 5 gives an overview of the space and time adaptivity used. In Section 6 we study the approximation of derivatives in the discretized problem near the free boundary. Section 7 then show some numerical results using our methods and Section 8 concludes the paper.

Section snippets

Constant volatility

The original problem is stated as a final value problem with a terminal condition at time T. As in most literature we have here used a transformation of the time-scale, t=Tt˜ (where t˜ is the original time), so that the problem becomes a forward problem with a known initial condition. This makes standard texts on time-integration for an ordinary differential equation (ODE) applicable. Let us first give the transformed Black–Scholes equation for the arbitrage free price F(x,t) of the European

Discretization

For both the constant and the stochastic volatility cases a discretization of the operator in space and time must be performed. We have used the same discretization technique as was used in [21] and will not repeat any details here. All space derivatives are discretized using a centered second order finite difference (FD) approximation on a structured but not equidistant grid in each space dimension. The variable step-sizes will be needed in the space adaptive process described in Section 5.

Operator splitting

Here we explain in short the operator splitting technique used by Ikonen and Toivanen in [12], [13]. Assume that we have the LCP problem formulated as in (3). The operator splitting is based on a reformulation of the problem using an auxiliary variable λ that keeps track of the free boundary. The variable λ can be used to find the location of the free boundary during or after the computations. We have used λ to find where local time-stepping should be used.

Omitting boundary conditions we gett

Space and time adaptivity

The space adaptivity used in this paper is directly based on the method used by the authors in [16] and [21]. The ideas will be repeated here but for the details and formulas the reader is referred to the other papers. The time adaptivity is also similar to the techniques used in the above mentioned papers but adjusted and changed to better handle the problems arising from the discontinuities near the internal free-boundary, see Section 3. The main idea is to first solve the problem on a very

Approximation of the time derivative near the free boundary

The behavior of the solution of the American put option has been studied by many researchers over the years. It is of great interest because the location and behavior of the free boundary, here denoted b(t), is important for traders. It turns out that it is optimal to exercise the American option when the stock price hits the free boundary. See e.g. [19] for analytical results on the free boundary. In this section we will denote partial derivatives by subscripts for ease of notation.

An

Numerical experiments

Here we will show some results from our experiments with the space and time adaptive methods presented in Section 5 for pricing the American put option. We consider the cases described in Table 1. For constant volatility we have used the operator splitting technique proposed by Ikonen and Toivanen in [12] to solve the LCPs and for stochastic volatility we have used the operator splitting technique used in [13]. The adaptive space discretization is very similar to what was used in our previous

Conclusions

For constant volatility we study continuity of derivatives of the solution over the free boundary. We conclude that the second derivatives are not continuous. Studying the numerical approximation of the time derivative near the free boundary, when BDF2 is used, we find that the order of accuracy is reduced from second to first order which motivates the use of a first order method there. With constant volatility we see that the time-stepping algorithm C1b gives similar time-steps and performance

Acknowledgements

The authors wish to thank the reviewer for helpful comments.

References (24)

  • P. Glasserman

    Monte Carlo Methods in Financial Engineering, Applications of Mathematics: Stochastic Modeling and Applied Probability

    (2004)
  • G. Golub et al.

    Matrix Computations

    (1996)
  • Cited by (23)

    • A high order method for pricing of financial derivatives using Radial Basis Function generated Finite Differences

      2020, Mathematics and Computers in Simulation
      Citation Excerpt :

      Instead, we only use the lower-triangular half of the rectangle which reduces the number of computational nodes by a factor of two, and hence the computational complexity significantly. Although the here suggested nonuniform node layout demonstrates very good qualities as we will see in Section 4, we aim in future papers to include an adaptive node placement technique such as in e.g. [3,13,16,12,17]. The numerical experiments are performed on a laptop equipped with a 2.3 GHz Intel Core i7 CPU and 16 GB of RAM.

    • Pricing real estate index options under stochastic interest rates

      2017, Physica A: Statistical Mechanics and its Applications
    • Numerical pricing of American options under two stochastic factor models with jumps using a meshless local Petrov–Galerkin method

      2017, Applied Numerical Mathematics
      Citation Excerpt :

      To demonstrate the excellent capability of the presented method, first example considers the European and American options under SV model. In particular, we consider the same test case reported in [19,46,66,34,33,48,65,35], where the option and model parameters are chosen as in Table 1. This example, illustrates the applicability of the proposed method to five different option pricing problem under SVJ model with the following specifications

    View all citing articles on Scopus
    1

    Funded by FMB, the Swedish Graduate School in Mathematics and Computing.

    2

    Funded by VR, the Swedish Research Council.

    View full text