Numerical Quadrature in Finance
Description
Multivariate integrals arise in many application fields, such as statistics,
the valuation of financial derivatives, the discretization of
partial differential and integral equations or the numerical computation
of path integrals. Conventional algorithms for the numerical computation
of such integrals are often limited by the
curse of dimension meaning
that the computing cost grows exponentially with the dimension of the problem.
However, for special function classes, such as spaces of functions which
have bounded mixed derivatives, Smolyak's construction (also known as sparse
grid method) can overcome this curse of dimension to a certain extent. In this
approach, multivariate quadrature formulas are constructed using combinations
of tensor products of suited one-dimensional formulas. In this way, the number
of function evaluations and the numerical accuracy get independent of the
dimension of the problem up to logarithmic factors. Below you see the
quadrature abscissas from a Monte Carlo and a Quasi-Monte Carlo method, a
lattice rule, and a sparse grid, all of which can break the curse of dimension.
Sparse grid quadrature formulas come in various types depending on a
one-dimensional basis integration routine. In the next picture we see sparse
grids based on the trapezoidal, the Clenshaw-Curtis, Patterson and Gauss-Legendre
rules. Theoretical and experimental computations have shown that Patterson
formulas are sort of optimal for Smolyak's construction.
The scope of this project is to apply sparse grid quadrature formulas
to various problems from finance. These problems
typically require the computation of expecations, which are integrals whose
dimension is infinite for continuous processes and finite but high for
discrete processes. The Brownian bridge construction helps to reduce the
effective dimension of these integrals. Below, you see a sample random process,
and corresponding discretizations using a random walk and the Brownian
bridge construction.
Below, you see the location of the integration points for two-step geometric
Asian option. Here, in order to avoid the discontinuity in the derivative
of the (transformed) payoff function, the integration domain was transformed
to the smooth nonzero part of the payoff function.
References
-
T. Bonk, A new algorithm for multi-dimensional adaptive numerical
quadrature, in Adaptive Methods - Algorithms, Theory and Applications,
W. Hackbusch, G. Wittum (eds.), pp. 54-68, Vieweg, Braunschweig, 1994.
-
T. Gerstner, M. Griebel,
Numerical integration using
sparse grids, Numerical Algorithms 18:209-232, 1998.
-
T. Gerstner, M. Griebel,
Dimension-adaptive
tensor-product quadrature, Computing (special issue on sparse grids),
2002, submitted.
-
T. Gerstner, M. Griebel, S. Wahl, Option pricing using sparse
grids, 2001, available on request.
-
E. Novak, K. Ritter, High dimensional integration of smooth functions
over cubes, Numerische Mathematik 75, pp. 79-97, 1996.
-
S.A. Smolyak, Quadrature and interpolation formulas for tensor
products of certain classes of functions, Dokl. Akad. Nauk SSSR 4,
pp. 240-243, 1963.
-
The Sparse Grid
Bibliography.
Related Projects
