Laplace's method - Alchetron, The Free Social Encyclopedia

In mathematics, Laplace's method, named after Pierre-Simon Laplace, is a technique used to approximate integrals of the form

The idea of Laplace's method

Assume that the function ƒ(x) has a unique global maximum at x₀. Then, the value ƒ(x₀) will be larger than the other values of ƒ(x). If we multiply this function by a large number M, the ratio between Mƒ(x₀) and Mƒ(x) will stay the same (since Mƒ(x₀)/Mƒ(x) = ƒ(x₀)/ƒ(x)), but it will grow exponentially in the function e M f ( x ) (see figure).

Thus, significant contributions to the integral of this function will come only from points x in a neighbourhood of x₀, which can then be estimated.

General theory of Laplace's method

To state and motivate the method, we need several assumptions. We will assume that x₀ is not an endpoint of the interval of integration, that the values ƒ(x) cannot be very close to ƒ(x₀) unless x is close to x₀, and that the second derivative f ″ ( x 0 ) < 0 .

We can expand ƒ(x) around x₀ by Taylor's theorem,

f ( x ) = f ( x 0 ) + f ′ ( x 0 ) ( x − x 0 ) + 1 2 f ″ ( x 0 ) ( x − x 0 ) 2 + R

where R = O ( ( x − x 0 ) 3 ) .

Since ƒ has a global maximum at x₀, and since x₀ is not an endpoint, it is a stationary point, so the derivative of ƒ vanishes at x₀. Therefore, the function ƒ(x) may be approximated to quadratic order

f ( x ) ≈ f ( x 0 ) − 1 2 | f ″ ( x 0 ) | ( x − x 0 ) 2

for x close to x₀ (recall that the second derivative is negative at the global maximum ƒ(x₀)). The assumptions made ensure the accuracy of the approximation

∫ a b e M f ( x ) d x ≈ e M f ( x 0 ) ∫ a b e − M | f ″ ( x 0 ) | ( x − x 0 ) 2 / 2 d x

(see the picture on the right). This latter integral is a Gaussian integral if the limits of integration go from −∞ to +∞ (which can be assumed because the exponential decays very fast away from x₀), and thus it can be calculated. We find

∫ a b e M f ( x ) d x ≈ 2 π M | f ″ ( x 0 ) | e M f ( x 0 ) as M → ∞ .

A generalization of this method and extension to arbitrary precision is provided by Fog (2008).

Formal statement and proof:

Assume that f ( x ) is a twice differentiable function on [ a , b ] with x 0 ∈ [ a , b ] the unique point such that f ( x 0 ) = max [ a , b ] f ( x ) . Assume additionally that f ″ ( x 0 ) < 0 .

Then,

lim n → + ∞ ∫ a b e n f ( x ) d x e n f ( x 0 ) 2 π n ( − f ″ ( x 0 ) ) = 1

This method relies on 4 basic concepts such as

Based on these four concepts, we can derive the relative error of this Laplace's method.

Other formulations

Laplace's approximation is sometimes written as

∫ a b h ( x ) e M g ( x ) d x ≈ 2 π M | g ″ ( x 0 ) | h ( x 0 ) e M g ( x 0 ) as M → ∞

where h is positive.

Importantly, the accuracy of the approximation depends on the variable of integration, that is, on what stays in g ( x ) and what goes into h ( x ) .

In the multivariate case where x is a d -dimensional vector and f ( x ) is a scalar function of x , Laplace's approximation is usually written as:

∫ e M f ( x ) d x ≈ ≈ ( 2 π M ) d / 2 | − H ( f ) ( x 0 ) | − 1 / 2 e M f ( x 0 ) as M → ∞

where H ( f ) ( x 0 ) is the Hessian matrix of f evaluated at x 0 and where | ⋅ | denotes matrix determinant. Analogously to the univariate case, the Hessian is required to be negative definite.

By the way, although x denotes a d -dimensional vector, the term d x denotes an Infinitesimal volume here, i.e. d x := d x 1 d x 2 ⋯ d x d .

Laplace's method extension: Steepest descent

In extensions of Laplace's method, complex analysis, and in particular Cauchy's integral formula, is used to find a contour of steepest descent for an (asymptotically with large M) equivalent integral, expressed as a line integral. In particular, if no point x₀ where the derivative of ƒ vanishes exists on the real line, it may be necessary to deform the integration contour to an optimal one, where the above analysis will be possible. Again the main idea is to reduce, at least asymptotically, the calculation of the given integral to that of a simpler integral that can be explicitly evaluated. See the book of Erdelyi (1956) for a simple discussion (where the method is termed steepest descents).

The appropriate formulation for the complex z-plane is

∫ a b e M f ( z ) d z ≈ ≈ 2 π − M f ″ ( z 0 ) e M f ( z 0 ) as M → ∞ .

for a path passing through the saddle point at z₀. Note the explicit appearance of a minus sign to indicate the direction of the second derivative: one must not take the modulus. Also note that if the integrand is meromorphic, one may have to add residues corresponding to poles traversed while deforming the contour (see for example section 3 of Okounkov's paper Symmetric functions and random partitions).

Further generalizations

An extension of the steepest descent method is the so-called nonlinear stationary phase/steepest descent method. Here, instead of integrals, one needs to evaluate asymptotically solutions of Riemann–Hilbert factorization problems.

Given a contour C in the complex sphere, a function ƒ defined on that contour and a special point, say infinity, one seeks a function M holomorphic away from the contour C, with prescribed jump across C, and with a given normalization at infinity. If ƒ and hence M are matrices rather than scalars this is a problem that in general does not admit an explicit solution.

An asymptotic evaluation is then possible along the lines of the linear stationary phase/steepest descent method. The idea is to reduce asymptotically the solution of the given Riemann–Hilbert problem to that of a simpler, explicitly solvable, Riemann–Hilbert problem. Cauchy's theorem is used to justify deformations of the jump contour.

The nonlinear stationary phase was introduced by Deift and Zhou in 1993, based on earlier work of Its. A (properly speaking) nonlinear steepest descent method was introduced by Kamvissis, K. McLaughlin and P. Miller in 2003, based on previous work of Lax, Levermore, Deift, Venakides and Zhou. As in the linear case, "steepest descent contours" solve a min-max problem. In the nonlinear case they turn out to be "S-curves" (defined in a different context back in the 80s by Stahl, Gonchar and Rakhmanov).

The nonlinear stationary phase/steepest descent method has applications to the theory of soliton equations and integrable models, random matrices and combinatorics.

Complex integrals

For complex integrals in the form:

1 2 π i ∫ c − i ∞ c + i ∞ g ( s ) e s t d s

with t >> 1, we make the substitution t = iu and the change of variable s = c + ix to get the bilateral Laplace transform:

1 2 π ∫ − ∞ ∞ g ( c + i x ) e − u x e i c u d x .

We then split g(c+ix) in its real and complex part, after which we recover u = t / i. This is useful for inverse Laplace transforms, the Perron formula and complex integration.

Example 1: Stirling's approximation

Laplace's method can be used to derive Stirling's approximation

N ! ≈ 2 π N N N e − N

for a large integer N.

From the definition of the Gamma function, we have

N ! = Γ ( N + 1 ) = ∫ 0 ∞ e − x x N d x .

Now we change variables, letting

so that

Plug these values back in to obtain

N ! = ∫ 0 ∞ e − N z ( N z ) N N d z = N N + 1 ∫ 0 ∞ e − N z z N d z = N N + 1 ∫ 0 ∞ e − N z e N ln ⁡ z d z = N N + 1 ∫ 0 ∞ e N ( ln ⁡ z − z ) d z .

This integral has the form necessary for Laplace's method with

f ( z ) = ln ⁡ z − z

which is twice-differentiable:

f ′ ( z ) = 1 z − 1 , f ″ ( z ) = − 1 z 2 .

The maximum of ƒ(z) lies at z₀ = 1, and the second derivative of ƒ(z) has the value −1 at this point. Therefore, we obtain

N ! ≈ N N + 1 2 π N e − N = 2 π N N N e − N .

Example 2: parameter estimation and probabilistic inference

Azevedo-Filho & Shachter 1994 reviews Laplace's method results (univariate and multivariate) and presents a detailed example showing the method used in parameter estimation and probabilistic inference under a Bayesian perspective. Laplace's method is applied to a meta-analysis problem from the medical domain, involving experimental data, and compared to other techniques.

References

Laplace's method Wikipedia

(Text) CC BY-SA

Contents