Euler–Maclaurin formula

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 wasdiscovered independently by Leonhard Euler and Colin Maclaurin around 1735 (and later generalized as Darboux's formula). Euler needed it to compute slowly converging infinite series while Maclaurin used it to calculate integrals.

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\left(x\right),dx$

can be approximated by the sum (or vice versa)

:$S=frac\left\{1\right\}\left\{2\right\}f\left(0\right)+fleft\left( 1 ight\right) +cdots+fleft\left( n-1 ight\right) +frac\left\{1\right\}\left\{2\right\}f\left(n\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 "&fnof;"("k") at the end points of the interval 0 and "n". Explicitly, for any natural number "p", we have

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

where "B"1 = −1/2, "B"2 = 1/6, "B"3 = 0, "B"4 = −1/30, "B"5 = 0, "B"6 = 1/42, "B"7 = 0, "B"8 = −1/30, ... are the Bernoulli numbers, and "R" is an error term which is normally small for suitable values of "p".

Note that

: $-B_1\left(f\left(n\right)+f\left(0\right)\right) =frac\left\{1\right\}\left\{2\right\}\left(f\left(n\right)+f\left(0\right)\right).$

Hence, we may also write the formula as follows:

:

By using the substitution rule, one can adapt this formula also to functions "&fnof;" which are defined on some other interval of the real line.

The remainder term

The remainder term "R" is most easily expressed using the periodic Bernoulli polynomials "P""n"("x"). The Bernoulli polynomials "B""n"("x"), "n" = 0, 1, 2, ... are defined recursively as

:$B_0\left(x\right) = 1, ,$

:$B_n\text{'}\left(x\right) = nB_\left\{n-1\right\}\left(x\right)mbox\left\{ and \right\}int_0^1 B_n\left(x\right),dx = 0mbox\left\{ for \right\}n ge 1.$

Then the periodic Bernoulli functions "P""n" are defined as

:$P_n\left(x\right) = B_n\left(x - lfloor x floor\right)mbox\left\{ for \right\}0 < x < 1, ,$

where $scriptstyle lfloor x floor$ denotes the largest integer thatis not greater than "x". Then, in terms of "P""n"("x"), the remainderterm "R" can be written as

:$R = \left(-1\right)^\left\{p+1\right\} int_0^n f^\left\{\left(p\right)\right\}\left(x\right) \left\{P_\left\{p\right\}\left(x\right) over p!\right\},dx,$

The remainder term can be estimated as

:$left|R ight|leqfrac\left\{2\right\}\left\{\left(2pi\right)^\left\{2\left(p+1\right)int_0^nleft|f^\left\{\left(p\right)\right\}\left(x\right) ight|,dx.$

Applications

The Basel problem

The Basel problem asks to determine the sum:$1 + frac14 + frac19 + frac1\left\{16\right\} + frac1\left\{25\right\} + cdots = sum_\left\{n=1\right\}^infty frac\left\{1\right\}\left\{n^2\right\}.$Euler computed this sum to 20 decimal places with only a few terms of the Euler–Maclaurin formula in 1735. This probably convinced him that the sum equals &pi;2 / 6, which he proved in the same year. [David J. Pengelley, [http://www.math.nmsu.edu/~davidp/euler2k2.pdf "Dances between continuous and discrete: Euler's summation formula"] , in: Robert Bradley and Ed Sandifer (Eds), "Proceedings, Euler 2K+2 Conference (Rumford, Maine, 2002)" , Euler Society, 2003.]

ums involving a polynomial

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

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

(see Faulhaber's formula).

Numerical integration

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

Asymptotic expansion of sums

In the context of computing asymptotic expansions of sums and series, usually the most useful form of the Euler–Maclaurin formula is

:$sum_\left\{n=a\right\}^\left\{b\right\}f\left(n\right) sim int_\left\{a\right\}^\left\{b\right\} f\left(x\right),dx+frac\left\{f\left(a\right)+f\left(b\right)\right\}\left\{2\right\}+sum_\left\{k=1\right\}^\left\{infty\right\},frac\left\{B_\left\{2k\left\{\left(2k\right)!\right\}left\left(f^\left\{\left(2k-1\right)\right\}\left(b\right)-f^\left\{\left(2k-1\right)\right\}\left(a\right) ight\right), ,$

where $a$ and $b$ are integers. Often the expansion remains valid even after taking the limits $\left\{scriptstyle a o -infty\right\}$ or $\left\{scriptstyle b o +infty\right\}$, or both. In many cases the integral on the right-hand side can be evaluated in closed form in terms of elementary functions even though the sum on the left-hand side cannot. Then all the terms in the asymptotic series can be expressed in terms of elementary functions. For example,:$sum_\left\{k=0\right\}^\left\{infty\right\}frac\left\{1\right\}\left\{\left(z+k\right)^2\right\} sim underbrace\left\{int_\left\{0\right\}^\left\{infty\right\}frac\left\{1\right\}\left\{\left(z+k\right)^\left\{2,dk\right\}_\left\{=1/z\right\}+frac\left\{1\right\}\left\{2z^\left\{2+sum_\left\{t=1\right\}^\left\{infty\right\}frac\left\{B_\left\{2t\left\{z^\left\{2t+1, .$Here the left-hand side is equal to $\left\{scriptstyle psi^\left\{\left(1\right)\right\}\left(z\right)\right\}$, namely the first-order polygamma function defined through $\left\{scriptstyle psi^\left\{\left(1\right)\right\}\left(z\right)=frac\left\{d^\left\{2\left\{dz^\left\{2ln Gamma\left(z\right)\right\}$; the gamma function $\left\{scriptstyle Gamma\left(z\right)\right\}$ is equal to $\left\{scriptstyle \left(z-1\right)!\right\}$ if $\left\{scriptstyle z\right\}$ is a positive integer. This results in an asymptotic expansion for $\left\{scriptstyle psi^\left\{\left(1\right)\right\}\left(z\right)\right\}$. That expansion, in turn, serves as the starting point for one of the derivations of precise error estimates for Stirling's approximation of the factorial function.

Proofs

Derivation by mathematical induction

We follow the argument given in (Apostol) [Tom M. Apostol, "An Elementary View of Euler's Summation Formula", "American Mathematical Monthly", volume 106, number 5, pages 409&mdash;418 (May 1999). doi|10.2307/2589145.] .

The Bernoulli polynomials "B""n"("x"), "n" = 0, 1, 2, ... may be defined recursively as follows:

:$B_0\left(x\right) = 1, ,$

:$B_n\text{'}\left(x\right) = nB_\left\{n-1\right\}\left(x\right)mbox\left\{ and \right\}int_0^1 B_n\left(x\right),dx = 0mbox\left\{ for \right\}n ge 1.$

The first several of these are

:$B_1\left(x\right)=x-1/2, quad B_2\left(x\right)=x^2-x+1/6,$

:$B_3\left(x\right) = x^3-frac\left\{3\right\}\left\{2\right\}x^2+frac\left\{1\right\}\left\{2\right\}x, quad B_4\left(x\right)=x^4-2x^3+x^2-frac\left\{1\right\}\left\{30\right\}, dots$

The values "B""n"(1) are the Bernoulli numbers. Notice thatfor "n" &ge; 2 we have :$B_n\left(0\right) = B_n\left(1\right) = B_nquad\left(:n ext\left\{th Bernoulli number\right\}\right).$

We define the periodic Bernoulli functions "P""n" by

:$P_n\left(x\right) = B_n\left(x - lfloor x floor\right)mbox\left\{ for \right\}0 < x < 1, ,$

where $lfloor x floor$ denotes the largest integer thatis not greater than "x". So "P""n" agree with the Bernoulli polynomials on the interval (0, 1) and are periodic with period 1. Thus,

:$P_n\left(0\right) = P_n\left(1\right)= B_nquad ext\left\{for \right\} n>1.$

For "n" = 1,

:$P_1\left(0\right) = - P_n\left(1\right)=B_1.$

Now, consider the integral

:$int_k^\left\{k+1\right\} f\left(x\right),dx = int u,dv,$

where

:

Integrating by parts, we get

:

Summing the above from "k" = 0 to "k" = "n" − 1, we get

:

Adding ("&fnof;"(0) + "&fnof;"("n"))/2 to both sides and rearranging, we have

:$sum_\left\{k=0\right\}^n f\left(k\right) = int_0^n f\left(x\right),dx + \left\{f\left(0\right) + f\left(n\right) over 2\right\} + int_0^n f\text{'}\left(x\right) P_1\left(x\right),dx.qquad \left(1\right)$

The last two terms therefore give the error when the integral is taken to approximate the sum.

Next, consider

:$int_k^\left\{k+1\right\} f\text{'}\left(x\right)P_1\left(x\right),dx = int u,dv,$

where

:

Integrating by parts again, we get,

:

Then summing from "k" = 0 to "k" = "n" − 1, and then replacing the last integral in (1) with what we have thus shown to be equal to it, we have

:$sum_\left\{k=0\right\}^n f\left(k\right) = int_0^n f\left(x\right),dx + \left\{f\left(0\right) + f\left(n\right) over 2\right\} + frac\left\{B_2\right\}\left\{2\right\}\left(f\text{'}\left(n\right) - f\text{'}\left(0\right)\right) - \left\{1 over 2\right\}int_0^n f"\left(x\right)P_2\left(x\right),dx.$

By now the reader will have guessed that this process can be iterated. In this way we get a proof of the Euler–Maclaurin summation formula by mathematical induction, in which the induction step relies on integration by parts and on the identities for periodic Bernoulli functions.

In order to get bounds on the size of the error when the sum is approximated by the integral, we note that the Bernoulli polynomials on the interval [0, 1] attain their maximum absolute values at the endpoints (see D.H. Lehmer in References below), and the value "B""n"(1) is the "n"th Bernoulli number.

Derivation by functional analysis

The Euler–MacLaurin formula can be understood as a curious application of some ideas from Hilbert spaces and functional analysis.

First we restrict to the domain of unit interval [0,1] . Let $B_n\left(x\right)$ be the Bernoulli polynomials. A set of functions dual to the Bernoulli polynomials are given by

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

where &delta; 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 ilde\left\{B\right\}_n\left(x\right) f\left(x\right), dx = frac\left\{1\right\}\left\{n!\right\} left \left[ f^\left\{\left(n-1\right)\right\}\left(1\right) - f^\left\{\left(n-1\right)\right\}\left(0\right) ight\right]$

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

:$int_0^1 ilde\left\{B\right\}_m\left(x\right) B_n\left(x\right), dx = delta_\left\{mn\right\}$

and

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

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

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

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

Then value "x" = 0 and rearranging terms, one obtains an expression for "f(0)". Note that the Bernoulli numbers are defined as $B_n=B_n\left(0\right)$, and that these vanish for odd "n" greater than 1.

Then, using the periodic Bernoulli function "P""n" defined above and repeating the argument on the interval [1,2] , one can obtain an expression of "f(1)". This way one can obtain expressions for "f(n)", "n=0,1,2,...,N", and adding them up gives the Euler-MacLaurin formula. 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&pi;"nx") lies in the kernel; the integral of sin(2&pi;"nx") is vanishing on the unit interval, as is the difference of its derivatives at the endpoints.

Notes

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, " [http://numbers.computation.free.fr/Constants/Miscellaneous/bernoulli.html Introduction on Bernoulli's numbers] ", (2002)
* D.H. Lehmer, "On the Maxima and Minima of Bernoulli Polynomials", "American Mathematical Monthly", volume 47, pages 533&ndash;538 (1940)
*

Wikimedia Foundation. 2010.

Look at other dictionaries:

• Fórmula de Euler-Maclaurin — En matemáticas, la fórmula de Euler Maclaurin relaciona a integrales con series. Esta fórmula puede ser usada para aproximar integrales por sumas finitas o, de forma inversa, para evaluar series (finitas o infnitas) resolviendo integrales. La… …   Wikipedia Español

• Formule d'Euler-Maclaurin — En mathématiques, la formule d Euler Maclaurin (appelée parfois formule sommatoire d Euler) est une relation entre sommes discrètes et intégrales. Elle fut découverte indépendamment, aux alentours de 1735, par le mathématicien suisse Leonhard… …   Wikipédia en Français

• Euler — Leonhard Euler « Euler » redirige ici. Pour les autres significations, voir Euler (homonymie). Leonhard Euler …   Wikipédia en Français

• Colin Maclaurin — (1698–1746) Born February, 1698 …   Wikipedia

• List of topics named after Leonhard Euler — In mathematics and physics, there are a large number of topics named in honour of Leonhard Euler (pronounced Oiler ). As well, many of these topics include their own unique function, equation, formula, identity, number (single or sequence), or… …   Wikipedia

• Leonhard Euler — Infobox Scientist name = Leonhard Euler|box width = 300px |200px image width = 200px caption = Portrait by Johann Georg Brucker birth date = birth date|df=yes|1707|4|15 birth place = Basel, Switzerland death date = 18 September (O.S 7 September)… …   Wikipedia

• Contributions of Leonhard Euler to mathematics — The 18th century Swiss mathematician Leonhard Euler (1707–1783) is among the most prolific and successful mathematicians in the history of the field. His seminal work had a profound impact in numerous areas of mathematics and he is widely… …   Wikipedia

• Leonard Euler — Leonhard Euler « Euler » redirige ici. Pour les autres significations, voir Euler (homonymie). Leonhard Euler …   Wikipédia en Français

• Leonhard Euler — « Euler » redirige ici. Pour les autres significations, voir Euler (homonymie). Leonhard Euler Portrait par Johann Georg Brucker Naissance …   Wikipédia en Français

• Leonhard Paul Euler — Leonhard Euler « Euler » redirige ici. Pour les autres significations, voir Euler (homonymie). Leonhard Euler …   Wikipédia en Français