Pricing American options using a space-time adaptive finite difference method
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 . 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, (where 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 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 get
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 , 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)
- et al.
Monte Carlo methods for security pricing
Journal of Economic Dynamics & Control
(1997) - et al.
Operator splitting methods for pricing American options
Applied Mathematical Letters
(2004) - et al.
Space-time adaptive finite difference method for European multi-asset options
Computers and Mathematics with Applications
(2007) - et al.
Penalty methods for American options with stochastic volatility
Journal of Computational and Applied Mathematics
(1998) - Y. Achdou, O. Pironneau, Computational methods for option pricing, SIAM, 2005, in the series Frontiers in applied...
- et al.
Multivariate stochastic volatility: a review
Econometrics Reviews
(2006) - et al.
The pricing of options and corporate liabilities
Journal of Political Economy
(1973) - X. Chen, J. Chadam, A mathematical analysis for the optimal exercise boundary of American put option, preprint,...
- N. Clarke, K. Parrott, The multigrid solution of two-factor American put options, Tech. Re 96-16, Oxford Comp. Lab,...
- et al.
Multigrid for American option pricing with stochastic volatility
Applied Mathematical Finance
(1999)
Monte Carlo Methods in Financial Engineering, Applications of Mathematics: Stochastic Modeling and Applied Probability
Matrix Computations
Cited by (23)
A semi-Lagrangian mixed finite element method for advection–diffusion variational inequalities
2023, Mathematics and Computers in SimulationA high order method for pricing of financial derivatives using Radial Basis Function generated Finite Differences
2020, Mathematics and Computers in SimulationCitation 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 ApplicationsNumerical pricing of American options under two stochastic factor models with jumps using a meshless local Petrov–Galerkin method
2017, Applied Numerical MathematicsCitation 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
Efficient numerical pricing of American options based on multiple shooting method: a PDE approach
2023, Applicable AnalysisSemi-implicit FEM for the valuation of American options under the Heston model
2022, Computational and Applied Mathematics
- 1
Funded by FMB, the Swedish Graduate School in Mathematics and Computing.
- 2
Funded by VR, the Swedish Research Council.