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

[2.187]

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.

2.15.1 Quadrature

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 ⁿ. Let Ω = [a₁,b₁]×[a₂,b₂]× … ×[a_n,b_n] be a rectangular region of ⁿ. Let p₁, p₂, … , p_n be one-dimensional partitions of the respective intervals [a₁,b₁], [a₂,b₂], …, [a_n,b_n] for constants m₁, m₂, …, m_n. We define a partition p of Ω as the set p₁ × p₂ × … × p_n of n-dimensional points . This is illustrated for a two-dimensional partition in Exhibit 2.32.

Exhibit 2.32: A two-dimensional partition p = p₁ × p₂ of the region Ω = [a₁,b₁]×[a₂,b₂] is constructed from two one-dimensional partitions p₁ and p₂.

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 Ω:

[2.188]

The quadrature rule must specify weight in such a manner that, for any function fthat is Riemann integrable on Ω,

[2.189]

For any partition p, a quadrature rule yields the approximation

[2.190]

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.191]

[2.192]

[2.193]

2.15.2 The Product Rule

Suppose we have one-dimensional quadrature rules w_i(p_i) for each of n intervals [a_i,b_i]. Let Ω = [a₁,b₁]×[a₂,b₂]× … ×[a_n,b_n]. It can be shown that for partition p = p₁ × p₂ × … × p_n, we can specify a quadrature rule w(p) by setting all weights equal to the product

[2.194]

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

[2.195]

has a probability of both X₁ ∈ [2,4] and X₂ ∈ [0,3] given by the integral

[2.196]

Let’s use Simpson’s rule and the product rule to approximate this integral. We define partitions p₁ and p₂ of the intervals [2,4] and [0,3] for m₁ = m₂ = 4:

[2.197]

[2.198]

We use Simpson’s rule to define quadrature rules

[2.199]

[2.200]

We define the partition p = p₁ × p₂ and apply the product rule to define a quadrature rule w(p). Calculations are presented in Exhibit 2.33.

Exhibit 2.33: Calculations for our approximation of the integral [2.196].

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 = p₁ × p₂ × … × p_n, where each component partition p_i has m+1 points (m subintervals). The overall partition p then has (m+1)ⁿ points. Suppose we set m+1 = 10 and an integral has three dimensions. Valuing the integral using quadrature entails a sum [2.190] of 10³ = 1000 values. Now suppose the integral has 12 dimensions. Valuing this will entail a sum [2.190] of 10¹² = 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 value-at-risk measure’s transformation procedure is essentially one of solving a multidimensional integral. Integrals encountered in practicalvalue-at-risk applications routinely exceed 50 dimensions.

Exercises

2.25

Evaluate the integral

[2.201]

two different ways:

1. analytically;
2. with quadrature using the product rule and Simpson’s rule. Use m_i = 6 for each component partition.

Solution

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).