Euler-Maclaurin formula

From Wikipedia, the free encyclopedia

In mathematics, the Euler-Maclaurin formula provides a powerful connection between integrals (see calculus) and sums. It can be used to approximate integrals by finite sums, or conversely to evaluate finite sums and infinite series using integrals and the machinery of calculus. The formula was discovered independently by Leonhard Euler and Colin Maclaurin around 1735. Euler needed it to compute slowly converging infinite series while Maclaurin used it to calculate integrals.

1 The formula
2 The remainder term
3 Applications
4 Derivation
5 Motivation for the existence
6 References

[edit] The formula

If n is a natural number and f(x) is a smooth (meaning: sufficiently often differentiable) function defined for all real numbers x between 0 and n, then the integral

$I=\int_0^n f(x)\,dx$

can be approximated by the sum

$S=\frac{f\left( 0\right) }{2}+f\left( 1\right) +\cdots+f\left( n-1\right) + \frac{f\left( n\right) }{2} =\frac{f\left( 0\right) +f\left( n\right) }{2}+\sum_{k=1}^{n-1}f\left( k\right)$

(see trapezoidal rule). The Euler-Maclaurin formula provides expressions for the difference between the sum and the integral in terms of the higher derivatives f^(k) at the end points of the interval 0 and n. For any natural number p, we have

$S-I=\sum_{k=1}^p\frac{B_{2k}}{(2k)!}\left(f^{(2k-1)}(n)-f^{(2k-1)}(0)\right)+R$

where B₁ = −1/2, B₂ = 1/6, B₃ = 0, B₄ = −1/30, B₅ = 0, B₆ = 1/42, B₇ = 0, B₈ = −1/30, ... are the Bernoulli numbers, and R is an error term which is normally small for suitable values of p.

By employing the substitution rule, one can adapt this formula also to functions f which are defined on some other interval of the real line.

[edit] The remainder term

The remainder term R is given by

$R = (-1)^{p} \int_0^n f^{(p+1)}(x) {B_{p+1}(x-\lfloor x \rfloor) \over (p+1)!}\,dx,$

where $B_i(x-\lfloor x \rfloor)$ are the periodic Bernoulli polynomials. The remainder term can be estimated as

$\left|R\right|\leq\frac{2}{(2\pi)^{2p}}\int_0^n\left|f^{(2p+1)}(x)\right|\,dx.$

[edit] Applications

If f is a polynomial and p is big enough, then the remainder term vanishes. For instance, if f(x) = x³, we can choose p = 2 to obtain after simplification

$\sum_{i=0}^n i^3=\left(\frac{n(n+1)}{2}\right)^2.$

With the function f(x) = log(x), the Euler-Maclaurin formula can be used to derive precise error estimates for Stirling's approximation of the factorial function.

The Euler-Maclaurin formula is also used for detailed error analysis in numerical quadrature; in particular, extrapolation methods depend on it.

[edit] Derivation

The Euler-MacLaurin formula can be understood as a curious application of some ideas from Hilbert spaces and functional analysis. Let $B n (x)$ be the Bernoulli polynomials. A set of functions dual to the Bernoulli polynomials are given by

$\tilde{B}_n(x)=\frac{(-1)^{n+1}}{n!} \left[ \delta^{(n-1)}(1-x) - \delta^{(n-1)}(x) \right]$

where δ is the Dirac delta function. The above is a formal notation for the idea of taking derivatives at a point; thus one has

$\int_0^1 \tilde{B}_n(x) f(x)\, dx = \frac{1}{n!} \left[ f^{(n-1)}(1) - f^{(n-1)}(0) \right]$

for n > 0 and some arbitrary but differentiable function f(x) on the unit interval. For the case of n = 0, one defines $\tilde{B}_0(x)=1$ . The Bernoulli polynomials, along with their duals, form an orthogonal set of states on the unit interval: one has

$\int_0^1 \tilde{B}_m(x) B_n(x)\, dx = \delta_{mn}$

and

$\sum_{n=0}^\infty B_n(x) \tilde{B}_n(y) = \delta (x-y).$

The Euler-MacLaurin summation formula then follows as an integral over the latter. One has

$f(x)=\int_0^1 \sum_{n=0}^\infty B_n(x) \tilde{B}_n(y) f(y)\, dy$

$=\int_0^1 f(y)\,dy + \sum_{n=1}^{N} B_n(x) \frac{1}{n!} \left[ f^{(n-1)}(1) - f^{(n-1)}(0) \right] - \frac{1}{(N+1)!} \int_0^1 B_{N+1}(x-y) f^{(N)}(y)\, dy.$

Then taking x = 0, and rearranging terms, one obtains the traditional formula, together with the error term. Note that the Bernoulli numbers are defined as $B n = B n (0)$ , and that these vanish for odd n greater than 1. Note that this derivation does assume that f(x) is sufficiently differentiable and well-behaved; specifically, that f may be approximated by polynomials; equivalently, that f is a real analytic function.

The Euler-MacLaurin summation formula can thus be seen to be an outcome of the representation of functions on the unit interval by the direct product of the Bernoulli polynomials and their duals. Note, however, that the representation is not complete on the set of square-integrable functions. The expansion in terms of the Bernoulli polynomials has a non-trivial kernel. In particular, sin(2πnx) lies in the kernel; the integral of sin(2πnx) is vanishing on the unit interval, as is the difference of its derivatives at the endpoints.

[edit] Motivation for the existence

From a formal point of view the existence of the Euler-MacLaurin summation formula can be motivated as follows. The difference operator $Δ$ may formally be written as $Δ = e D - I$ , where $D$ denotes an ordinary differential operator and $I$ the identity operator (not the integral thus denoted above). Since the summation operator $Σ$ is the inverse operator to the difference operator $Δ$ we get

$\Sigma = \Delta^{-1} = \frac1{e^D - I}.$

Now we know that the exponential generating function of the Bernoulli numbers is given by

$\frac{x}{e^x-1} = \sum_{n=0}^{\infin} B_n \frac{x^n}{n!},$

hence formally

$\Sigma = \frac1D \sum_{n=0}^{\infin} B_n \frac{D^n}{n!} = \frac1D -\frac12 I + \frac{1}{12} D + \cdots = \int - \frac12 I + \frac{1}{12} D + \cdots,$

where $\int$ denotes the integral operator. This purely formal derivation indicates the existence of the formula. The idea is due to Legendre.

[edit] References

Pierre Gaspard, "r-adic one-dimensional maps and the Euler summation formula", Journal of Physics A, 25 (letter) L483-L485 (1992). (Describes the eigenfunctions of the transfer operator for the Bernoulli map)
Xavier Gourdon and Pascal Sebah, Introduction on Bernoulli's numbers, (2002)

Retrieved from "http://en.wikipedia.org../../../e/u/l/Euler-Maclaurin_formula_4e7b.html"

Categories: Approximation theory | Asymptotic analysis | Hilbert space | Numerical integration