Laplace's method

For the optimization method called "steepest descent" see gradient descent.

In mathematics, the steepest descent method or saddle-point approximation is a method used to approximate integrals of the form

\int _{a}^{b}\!e^{Mf(x)}\,dx\,

where f(x) is some twice-differentiable function, M is a large number, and the integral endpoints a and b could possibly be infinite. The technique is also often referred to as Laplace's method, especially when applied to real-valued functions f.

The idea of the method

Let x₀ be a global maximum of f(x), which, for simplicity, we will assume to be unique. Then, the value f(x₀) will be larger than other values f(x). If we multiply this function by a large number M, the gap between Mf(x₀) and Mf(x) will only increase, and then it will grow "exponentially" for the function

e^{Mf(x)}\,

As such, significant contributions to the integral of this function will come only from points x in a neighborhood of x₀, and which can be estimated.

General theory

To be able to actually state and prove the method, we need several more assumptions. We will assume that x₀ is not an endpoint of the interval of integration, that the values f(x) cannot be very close to f(x₀) unless x is close to x₀, and that $f''(x_{0})<0$ .

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

f(x)=f(x_{0})+f'(x_{0})(x-x_{0})+{\frac {1}{2}}f''(x_{0})(x-x_{0})^{2}+O\left((x-x_{0})^{3}\right)

Since x₀ is a global maximum and since it is not an endpoint, it is a stationary point, and therefore f'(x₀) = 0. The function f(x) may be approximated to quadratic order as

f(x)\approx f(x_{0})-{\frac {1}{2}}|f''(x_{0})|(x-x_{0})^{2}

for x close to x₀. The assumptions we put ensure the accuracy of the approximation

\int _{a}^{b}\!e^{Mf(x)}\,dx\approx e^{Mf(x_{0})}\int e^{-M|f''(x_{0})|(x-x_{0})^{2}/2}dx

where the integral is taken in a neighborhood of x₀. 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 x₀), and thus it can be calculated. We find

\int _{a}^{b}\!e^{Mf(x)}\,dx\approx {\sqrt {\frac {2\pi }{M|f''(x_{0})|}}}e^{Mf(x_{0})}{\mbox{ as }}M\to \infty \,

In extensions of this method, complex analysis is used to find a contour of steepest descent for an equivalent integral, expressed as a path integral.

Example: Stirling's approximation

The method of the steepest descent can be used to derive Stirling's approximation

N!\approx {\sqrt {2\pi N}}N^{N}e^{-N}\,

for a large integer N.

From the definition of the Gamma function, we have

N!=\Gamma (N+1)=\int _{0}^{\infty }e^{-x}x^{N}dx\,

Now we do a change of variable, let

x=Nz\,

so

dx=Ndz\,

Plug these values back in and we get:

$N!\,$	$=\int _{0}^{\infty }e^{-Nz}\left(Nz\right)^{N}Ndz\,$
	$=N^{N+1}\int _{0}^{\infty }e^{-Nz}z^{N}dz\,$
	$=N^{N+1}\int _{0}^{\infty }e^{-Nz}e^{N\ln z}dz\,$
	$=N^{N+1}\int _{0}^{\infty }e^{N(\ln z-z)}dz\,$