Method of steepest descent
|
|
- 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
- <math>\int_a^b\! e^{M f(x)}\, dx\,<math>
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.
| Contents |
The idea of the method
Let x0 be a global maximum of f(x), which, for simplicity, we will assume to be unique. Then, the value f(x0) will be larger than other values f(x). If we multiply this function by a large number M, the gap between Mf(x0) and Mf(x) will only increase, and then it will grow "exponentially" for the function
- <math> e^{M f(x)}.<math>
As such, significant contributions to the integral of this function will come only from points x in a neighborhood of x0, 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 x0 is not an endpoint of the interval of integration, that the values f(x) cannot be very close to f(x0) unless x is close to x0, and that <math>f''(x_0)<0<math>.
We can expand f(x) around x0 by Taylor's theorem,
- <math>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).<math>
Since x0 is a global maximum and since it is not an endpoint, it is a stationary point, and therefore f'(x0) = 0. The function f(x) may be approximated to quadratic order as
- <math> f(x) \approx f(x_0) - \frac{1}{2} |f''(x_0)| (x-x_0)^2<math>
for x close to x0. The assumptions we put ensure the accuracy of the approximation
- <math>\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<math>
where the integral is taken in a neighborhood of x0. 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
- <math>\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.\,<math>
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
- <math>N!\approx \sqrt{2\pi N} N^N e^{-N}\,<math>
for a large integer N.
From the definition of the Gamma function, we have
- <math>N! = \Gamma(N+1)=\int_0^{\infty} e^{-x} x^N dx\,.<math>
After a change of variable z=x/N, we find
- <math>N! = N^{N+1}\int_0^{\infty}e^{N(\ln z-z)} dz.\,<math>
This integral has the form necessary for the method of the steepest descent, with f(z)=ln z - z. The first and second derivative are
- <math>f'(z) = \frac{1}{z}-1\,,<math>
- <math>f''(z) = -\frac{1}{z^2}\,.<math>
The maximum of f(z) lies at z0=1, and the second derivative of f(z) has at this point the value -1. Therefore, we obtain
- <math>N! \approx N^{N+1}\sqrt{\frac{2\pi}{N}} e^{-N}=\sqrt{2\pi N} N^N e^{-N}\,.<math>