Method of steepest descent
Encyclopedia
In mathematics
, Laplace's method, named after Pierre-Simon Laplace
, is a technique used to approximate integral
s of the form
where ƒ(x) is some twice-differentiable
function
, M is a large number, and the integral endpoints a and b could possibly be infinite. This technique was originally presented in Laplace (1774, pp. 366–367).
at x0. Then, the value ƒ(x0) will be larger than other values ƒ(x). If we multiply this function by a large number M, the gap between Mƒ(x0) and Mƒ(x) will only increase, and then it will grow exponentially for the function
Thus, significant contributions to the integral of this function will come only from points x in a neighborhood of x0, which can then be estimated.
.
We can expand ƒ(x) around x0 by Taylor's theorem
,
Since ƒ has a global maximum at x0, and since x0 is not an endpoint, it is a stationary point
, so the derivative of ƒ vanishes at x0. Therefore, the function ƒ(x) may be approximated to quadratic order
for x close to x0 (recall that the second derivative is negative at the global maximum ƒ(x0)). The assumptions made ensure the accuracy of the approximation
(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 so because the exponential decays very fast away from x0), and thus it can be calculated. We find
A generalization of this method and extension to arbitrary precision is provided by Fog (2008).
, 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 x0 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
for a path passing through the saddle point at z0.
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).
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.
The nonlinear stationary phase/steepest descent method has applications to the theory of soliton equations
and integrable models, random matrices and combinatorics
.
with t >> 1, we make the substitution t = iu and the change of variable s = c + ix to get the Laplace bilateral transform:
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.
for a large integer
N.
From the definition of the Gamma function
, we have
Now we change variables, letting
so that
Plug these values back in to obtain
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, Laplace's method, named after Pierre-Simon Laplace
Pierre-Simon Laplace
Pierre-Simon, marquis de Laplace was a French mathematician and astronomer whose work was pivotal to the development of mathematical astronomy and statistics. He summarized and extended the work of his predecessors in his five volume Mécanique Céleste...
, is a technique used to approximate integral
Integral
Integration is an important concept in mathematics and, together with its inverse, differentiation, is one of the two main operations in calculus...
s of the form
where ƒ(x) is some twice-differentiable
Derivative
In calculus, a branch of mathematics, the derivative is a measure of how a function changes as its input changes. Loosely speaking, a derivative can be thought of as how much one quantity is changing in response to changes in some other quantity; for example, the derivative of the position of a...
function
Function (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...
, M is a large number, and the integral endpoints a and b could possibly be infinite. This technique was originally presented in Laplace (1774, pp. 366–367).
The idea of Laplace's method
Assume that the function ƒ(x) has a unique global maximumMaxima and minima
In mathematics, the maximum and minimum of a function, known collectively as extrema , are the largest and smallest value that the function takes at a point either within a given neighborhood or on the function domain in its entirety .More generally, the...
at x0. Then, the value ƒ(x0) will be larger than other values ƒ(x). If we multiply this function by a large number M, the gap between Mƒ(x0) and Mƒ(x) will only increase, and then it will grow exponentially for the function
Thus, significant contributions to the integral of this function will come only from points x in a neighborhood of x0, 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 x0 is not an endpoint of the interval of integration, that the values ƒ(x) cannot be very close to ƒ(x0) unless x is close to x0, and that the second derivative.We can expand ƒ(x) around x0 by Taylor's theorem
Taylor's theorem
In calculus, Taylor's theorem gives an approximation of a k times differentiable function around a given point by a k-th order Taylor-polynomial. For analytic functions the Taylor polynomials at a given point are finite order truncations of its Taylor's series, which completely determines the...
,
- where
Since ƒ has a global maximum at x0, and since x0 is not an endpoint, it is a stationary point
Stationary point
In mathematics, particularly in calculus, a stationary point is an input to a function where the derivative is zero : where the function "stops" increasing or decreasing ....
, so the derivative of ƒ vanishes at x0. Therefore, the function ƒ(x) may be approximated to quadratic order
for x close to x0 (recall that the second derivative is negative at the global maximum ƒ(x0)). The assumptions made ensure the accuracy of the approximation
(see the picture on the right). This latter integral is a Gaussian integral
Gaussian integral
The Gaussian integral, also known as the Euler-Poisson integral or Poisson integral, is the integral of the Gaussian function e−x2 over the entire real line.It is named after the German mathematician and...
if the limits of integration go from −∞ to +∞ (which can be assumed so because the exponential decays very fast away from x0), and thus it can be calculated. We find
A generalization of this method and extension to arbitrary precision is provided by Fog (2008).
Laplace's method extension: Steepest descent
In extensions of Laplace's method, complex analysisComplex analysis
Complex analysis, traditionally known as the theory of functions of a complex variable, is the branch of mathematical analysis that investigates functions of complex numbers. It is useful in many branches of mathematics, including number theory and applied mathematics; as well as in physics,...
, and in particular
Cauchy's integral formula
Cauchy's integral formula
In mathematics, Cauchy's integral formula, named after Augustin-Louis Cauchy, is a central statement in complex analysis. It expresses the fact that a holomorphic function defined on a disk is completely determined by its values on the boundary of the disk, and it provides integral formulas for all...
,
is used to find a contour of steepest descent for an (asymptotically with large M) equivalent integral, expressed as a line integral
Line integral
In mathematics, a line integral is an integral where the function to be integrated is evaluated along a curve.The function to be integrated may be a scalar field or a vector field...
. In particular,
if no point x0 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
for a path passing through the saddle point at z0.
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.
The nonlinear stationary phase/steepest descent method has applications to the theory of soliton equations
and integrable models, random matrices and combinatorics
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
.
Complex integrals
For complex integrals in the form:with t >> 1, we make the substitution t = iu and the change of variable s = c + ix to get the Laplace bilateral transform:
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 approximationStirling's approximation
In mathematics, Stirling's approximation is an approximation for large factorials. It is named after James Stirling.The formula as typically used in applications is\ln n! = n\ln n - n +O\...
for a large integer
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
N.
From the definition of the Gamma function
Gamma function
In mathematics, the gamma function is an extension of the factorial function, with its argument shifted down by 1, to real and complex numbers...
, we have
Now we change variables, letting
so that
Plug these values back in to obtain
-
This integral has the form necessary for Laplace's method with
which is twice-differentiable:
The maximum of ƒ(z) lies at z0 = 1, and the second derivative of ƒ(z) has at this point the value −1. Therefore, we obtain
Example 2: parameter estimation and probabilistic inference
Azevedo-Filho and Shachter (1994) reviews Laplace's method results (univariateUnivariateIn mathematics, univariate refers to an expression, equation, function or polynomial of only one variable. Objects of any of these types but involving more than one variable may be called multivariate...
and multivariate) and presents a detailed example showing the method used in parameter estimation and probabilisticProbabilityProbability is ordinarily used to describe an attitude of mind towards some proposition of whose truth we arenot certain. The proposition of interest is usually of the form "Will a specific event occur?" The attitude of mind is of the form "How certain are we that the event will occur?" The...
inferenceInferenceInference is the act or process of deriving logical conclusions from premises known or assumed to be true. The conclusion drawn is also called an idiomatic. The laws of valid inference are studied in the field of logic.Human inference Inference is the act or process of deriving logical conclusions...
under a bayesianBayesianBayesian refers to methods in probability and statistics named after the Reverend Thomas Bayes , in particular methods related to statistical inference:...
perspective. Laplace's method is applied to a meta-analysisMeta-analysisIn statistics, a meta-analysis combines the results of several studies that address a set of related research hypotheses. In its simplest form, this is normally by identification of a common measure of effect size, for which a weighted average might be the output of a meta-analyses. Here the...
problem from the medicalMedicineMedicine is the science and art of healing. It encompasses a variety of health care practices evolved to maintain and restore health by the prevention and treatment of illness....
domain, involving experimental dataDataThe term data refers to qualitative or quantitative attributes of a variable or set of variables. Data are typically the results of measurements and can be the basis of graphs, images, or observations of a set of variables. Data are often viewed as the lowest level of abstraction from which...
, and compared to other techniques. (article)