Method of steepest descent

From Wikipedia, the free encyclopedia

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^{M f(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, which in fact concerns the special case of real-valued functions f admitting a maximum at a real point.

1 The idea of Laplace's method
2 General theory of Laplace's method
3 Complex integrals
4 Example: Stirling's approximation
5 References
6 See also

[edit] The idea of Laplace's method

Assume that the function f(x) has a unique global maximum x₀. 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^{M f(x)}. \,$

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

[edit] General theory of Laplace's method

To state and prove the method, we need several 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^{M f(x)}\, dx\approx e^{M f(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^{M f(x)}\, dx\approx \sqrt{\frac{2\pi}{M|f''(x_0)|}}e^{M f(x_0)} \mbox { as } M\to\infty. \,$

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

An intriguing extension of the steepest descent method is the so-called nonlinear stationary phase/steepest descent method. Instead of integrals one needs to asymptotically evaluate solutions of Riemann-Hilbert factorization problems: given a contour C in the complex sphere, a function f 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 f 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 asymptotically reduce the solution of the given Riemann-Hilbert problem to that of a simpler, explicitly solvable, Riemann-Hilbert problem. Naturally, Cauchy's theorem is used to justify deformations of the jump contour. The nonlinear stationary phase has been introduced by Deift and Zhou in 1993, based on earlier work of Its. A (properly speaking) nonlinear steepest descent method has been introduced by Kamvissis, K.McLaughlin and P.Miller in 2003, based on previous work of Lax, Levermore, Deift, Venakides and Zhou. The importance of the nonlinear stationary phase/steepest descent method relies in the abundance of applications to the theory of soliton equations, random matrices and combinatorics.

[edit] Complex integrals

For complex integrals in the form:

$\frac{1}{2\pi i}\int_{c-i\infty}^{c+i\infty} g(s)e^{st} \,ds$

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

$\frac{1}{2 \pi}\int_{-\infty}^{\infty} g(c+ix)e^{-ux}e^{icu} \, dx.$

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.

[edit] Example: Stirling's approximation

Laplace's method 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 change variables, letting

$x = N z \,$

so that

$dx = N dz. \,$

Plug these values back in to obtain

$N! \,$	$= \int_0^{\infty} e^{-N z} \left(N z \right)^N N dz \,$
	$= N^{N+1}\int_0^{\infty}e^{-N z} z^N dz \,$
	$= N^{N+1}\int_0^{\infty}e^{-N z} e^{N\ln z} dz \,$
	$= N^{N+1}\int_0^{\infty}e^{N(\ln z-z)} dz. \,$

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

$f \left( z \right) = \ln{z}-z$

which is twice-differentiable:

$f'(z) = \frac{1}{z}-1\,,$

$f''(z) = -\frac{1}{z^2}.\,$

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

$N! \approx N^{N+1}\sqrt{\frac{2\pi}{N}} e^{-N}=\sqrt{2\pi N} N^N e^{-N}.\,$

[edit] References

P. Deift, X. Zhou, A steepest descent method for oscillatory Riemann-Hilbert problems. Asymptotics for the MKdV equation, Ann. of Math. (2), v.137 (1993), no. 2, 295–368.
A. Erdelyi, Asymptotic Expansions, Dover, 1956.
S. Kamvissis, K. T.-R. McLaughlin, P. Miller, Semiclassical Soliton Ensembles for the Focusing Nonlinear Schrödinger Equation, Annals of Mathematics Studies, v.154, Princeton University Press, 2003.