2.15 Numerical Integration: Multiple Dimensions
In this section, we extend Riemann sums, the trapezoidal rule and Simpson’s rule to multidimensional integrals of the form
We first define quadrature rules, which are a generalized form of numerical integration. We then present the product rule that constructs quadrature rules for multiple-dimensional integrals from quadrature rules for one-dimensional integrals.
We have defined a partition p as a set of equally spaced points in . We now define a partition more generally as a set of equally spaced points in n. Let Ω = [a1,b1]×[a2,b2]× … ×[an,bn] be a rectangular region of n. Let p1, p2, … , pn be one-dimensional partitions of the respective intervals [a1,b1], [a2,b2], …, [an,bn] for constants m1, m2, …, mn. We define a partition p of Ω as the set p1 × p2 × … × pn of n-dimensional points . This is illustrated for a two-dimensional partition in Exhibit 2.32.
A quadrature rule w(p) is a general rule for approximating integrals on Ω. For any partition p of Ω, the quadrature rule specifies a set w of weights whose sum equals the area of Ω:
The quadrature rule must specify weight in such a manner that, for any function fthat is Riemann integrable on Ω,
For any partition p, a quadrature rule yields the approximation
Riemann sums, the trapezoidal rule and Simpson’s rule are all examples of one-dimensional quadrature rules. For any partition p, they assign weights of, respectively,
2.15.2 The Product Rule
Suppose we have one-dimensional quadrature rules wi(pi) for each of n intervals [ai,bi]. Let Ω = [a1,b1]×[a2,b2]× … ×[an,bn]. It can be shown that for partition p = p1 × p2 × … × pn, we can specify a quadrature rule w(p) by setting all weights equal to the product
2.15.3 Example: Product Rule
As will be discussed in Chapter 3, a two-dimensional joint-normal random vector X with mean vector and covariance matrix
has a probability of both X1 ∈ [2,4] and X2 ∈ [0,3] given by the integral
Let’s use Simpson’s rule and the product rule to approximate this integral. We define partitions p1 and p2 of the intervals [2,4] and [0,3] for m1 = m2 = 4:
We use Simpson’s rule to define quadrature rules
We define the partition p = p1 × p2 and apply the product rule to define a quadrature rule w(p). Calculations are presented in Exhibit 2.33.
2.15.4 Curse of Dimensionality
A problem with using quadrature to solve multidimensional integrals is the fact that the number of points in a partition grows exponentially with the dimensions of the integral. Because the computational expense of valuing [2.190] is directly proportional to the number of points in the partition, that computational expense also grows exponentially. Consider a partition p = p1 × p2 × … × pn, where each component partition pi has m+1 points (m subintervals). The overall partition p then has (m+1)n points. Suppose we set m+1 = 10 and an integral has three dimensions. Valuing the integral using quadrature entails a sum [2.190] of 103 = 1000 values. Now suppose the integral has 12 dimensions. Valuing this will entail a sum [2.190] of 1012 = 1,000,000,000,000 values. This is a staggering number of calculations, but things can get far worse. Applications abound that involve integrals of 50, 100, 1000, or even more dimensions. Valuing such integrals using quadrature entails calculations that are beyond the processing power of any computer that ever was or will be. This problem is known as the curse of dimensionality. It means that quadrature can only be applied to integrals that have a modest number of dimensions. It is a significant problem for us because the task of a VaR measure’s transformation procedure is essentially one of solving a multidimensional integral. Integrals encountered in practical VaR applications routinely exceed 50 dimensions.
Evaluate the integral
two different ways:
- with quadrature using the product rule and Simpson’s rule. Use mi = 6 for each component partition.
2.16 Further Reading for Chapter 2
For information on the Cholesky and related factorizations, see Golub and Van Loan (1996) and Gentle (1998). Burden and Faires (2010) covers various numerical techniques. See Dennis and Schnabel (1983) for Newton’s method in multiple dimensions. For quadrature, see Evans and Swartz (2000).