Misplaced Pages

Euler–Maclaurin formula

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.

This is an old revision of this page, as edited by Ozob (talk | contribs) at 04:24, 18 March 2017 (Undid revision 770721359 by Angry bee (talk) No, it was correct before). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Revision as of 04:24, 18 March 2017 by Ozob (talk | contribs) (Undid revision 770721359 by Angry bee (talk) No, it was correct before)(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

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. For example, many asymptotic expansions are derived from the formula, and Faulhaber's formula for the sum of powers is an immediate consequence.

The formula was discovered 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 m and n are natural numbers and f(x) is a complex or real valued continuous function for real numbers x in the interval , then the integral

I = ∫ m n f ( x ) d x {\displaystyle I=\int _{m}^{n}f(x)\,dx}

can be approximated by the sum (or vice versa)

S = f ( m + 1 ) + ⋯ + f ( n − 1 ) + f ( n ) {\displaystyle S=f(m+1)+\cdots +f(n-1)+f(n)}

(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(x) evaluated at the end points of the interval, that is to say when x = m and x = n.

Explicitly, for a natural number p and a function f(x) that is p times continuously differentiable in the interval , we have

S − I = ∑ k = 1 p B k k ! ( f ( k − 1 ) ( n ) − f ( k − 1 ) ( m ) ) + R {\displaystyle S-I=\sum _{k=1}^{p}{{\frac {B_{k}}{k!}}\left(f^{(k-1)}(n)-f^{(k-1)}(m)\right)}+R}

where Bk is the kth Bernoulli number (with B1 = ⁠1/2⁠) and R is an error term which is normally small for suitable values of p and depends on n, m, p, and f.

The formula is often written with the subscript taking only even values, since the odd Bernoulli numbers are zero except for B1, in which case we have

∑ i = m + 1 n f ( i ) = ∫ m n f ( x ) d x + f ( n ) − f ( m ) 2 + ∑ k = 1 ⌊ p 2 ⌋ B 2 k ( 2 k ) ! ( f ( 2 k − 1 ) ( n ) − f ( 2 k − 1 ) ( m ) ) + R . {\displaystyle \sum _{i=m+1}^{n}f(i)=\int _{m}^{n}f(x)\,dx+{\frac {f(n)-f(m)}{2}}+\sum _{k=1}^{\left\lfloor {\frac {p}{2}}\right\rfloor }{\frac {B_{2k}}{(2k)!}}\left(f^{(2k-1)}(n)-f^{(2k-1)}(m)\right)+R.}

The Bernoulli polynomials and periodic function

The formula is derived below using repeated integration by parts applied to successive intervals for integers r = m, m + 1, …, n − 1. The derivation uses the periodic Bernoulli functions, Pk(x), which are defined in terms of the Bernoulli polynomials Bk(x) for k = 0, 1, 2….

The Bernoulli polynomials may be defined recursively by

B 0 ( x ) = 1 B k ′ ( x ) = k B k − 1 ( x )  and  ∫ 0 1 B k ( x ) d x = 0  for  k ≥ 1 {\displaystyle {\begin{aligned}B_{0}(x)&=1\\B_{k}'(x)&=kB_{k-1}(x)\quad {\text{ and }}\quad \int _{0}^{1}B_{k}(x)\,dx=0{\text{ for }}k\geq 1\end{aligned}}}

and the periodic Bernoulli functions are defined as

P k ( x ) = B k ( x − ⌊ x ⌋ ) {\displaystyle P_{k}(x)=B_{k}\left(x-\lfloor x\rfloor \right)}

where ⌊x⌋ denotes the largest integer that is not greater than x so that x − ⌊x⌋ always lies in the interval [0,1).

It can be shown that Bk(1) = Bk(0) for all k ≠ 1 so that except for P1(x), all the periodic Bernoulli functions are continuous. The functions Pk(x) are sometimes written as B̃k(x).

The remainder term

The remainder term R can be written as

R = ( − 1 ) p + 1 ∫ m n f ( p ) ( x ) P p ( x ) p ! d x . {\displaystyle R=(-1)^{p+1}\int _{m}^{n}f^{(p)}(x){\frac {P_{p}(x)}{p!}}\,dx.}

When k > 0, it can be shown that

| B k ( x ) | ≤ 2 ⋅ k ! ( 2 π ) k ζ ( k ) {\displaystyle \left|B_{k}(x)\right|\leq {\frac {2\cdot k!}{(2\pi )^{k}}}\zeta (k)}

where ζ denotes the Riemann zeta function; one approach to prove this inequality is to obtain the Fourier series for the polynomials Bk(x). The bound is achieved for even k when x is zero. The term ζ(k) may be omitted for odd k but the proof in this case is more complex (see Lehmer). Using this inequality, the size of the remainder term can be estimated using

| R | ≤ 2 ζ ( p ) ( 2 π ) p ∫ m n | f ( p ) ( x ) | d x . {\displaystyle \left|R\right|\leq {\frac {2\zeta (p)}{(2\pi )^{p}}}\int _{m}^{n}\left|f^{(p)}(x)\right|\,dx.}

Applicable formula

We can use the formula as a means of approximating a finite integral, with the following simple formula:

I = ∫ x 0 x N f ( x ) d x = h ( f 0 2 + f 1 + f 2 + ⋯ + f N − 1 + f N 2 ) + h 2 12 ( f 0 ′ − f N ′ ) − h 4 720 ( f 0 ‴ − f N ‴ ) + ⋯ , {\displaystyle {\begin{aligned}I&=\int _{x_{0}}^{x_{N}}f(x)\,dx\\&=h\left({\frac {f_{0}}{2}}+f_{1}+f_{2}+\cdots +f_{N-1}+{\frac {f_{N}}{2}}\right)+{\frac {h^{2}}{12}}\left(f'_{0}-f'_{N}\right)-{\frac {h^{4}}{720}}\left(f'''_{0}-f'''_{N}\right)+\cdots ,\end{aligned}}}

where N is the number of points in the interval of integration from x0 to xN and h is the distance between points so that h = ⁠xN − x0/N⁠. Note the series above is usually not convergent; indeed, often the terms will increase rapidly after a number of iterations. Thus, attention generally needs to be paid to the remainder term.

This may be viewed as an extension of the trapezoid rule by the inclusion of correction terms.

Applications

The Basel problem

The Basel problem asks to determine the sum

1 + 1 4 + 1 9 + 1 16 + 1 25 + ⋯ = ∑ n = 1 ∞ 1 n 2 . {\displaystyle 1+{\tfrac {1}{4}}+{\tfrac {1}{9}}+{\tfrac {1}{16}}+{\tfrac {1}{25}}+\cdots =\sum _{n=1}^{\infty }{\frac {1}{n^{2}}}.}

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 ⁠π/6⁠, which he proved in the same year. Parseval's identity for the Fourier series of f(x) = x gives the same result.

Sums involving a polynomial

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

∑ i = 0 n i 3 = ( n ( n + 1 ) 2 ) 2 {\displaystyle \sum _{i=0}^{n}i^{3}=\left({\frac {n(n+1)}{2}}\right)^{2}}

(see Faulhaber's formula).

Numerical integration

The Euler–Maclaurin formula is also used for detailed error analysis in numerical quadrature. It explains the superior performance of the trapezoidal rule on smooth periodic functions and is used in certain extrapolation methods. Clenshaw–Curtis quadrature is essentially a change of variables to cast an arbitrary integral in terms of integrals of periodic functions where the Euler–Maclaurin approach is very accurate (in that particular case the Euler–Maclaurin formula takes the form of a discrete cosine transform). This technique is known as a periodizing transformation.

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

∑ n = a b f ( n ) ∼ ∫ a b f ( x ) d x + f ( b ) + f ( a ) 2 + ∑ k = 1 ∞ B 2 k ( 2 k ) ! ( f ( 2 k − 1 ) ( b ) − f ( 2 k − 1 ) ( a ) ) {\displaystyle \sum _{n=a}^{b}f(n)\sim \int _{a}^{b}f(x)\,dx+{\frac {f(b)+f(a)}{2}}+\sum _{k=1}^{\infty }{\frac {B_{2k}}{(2k)!}}\left(f^{(2k-1)}(b)-f^{(2k-1)}(a)\right)}

where a and b are integers. Often the expansion remains valid even after taking the limits a → −∞ or b → +∞ 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,

∑ k = 0 ∞ 1 ( z + k ) 2 ∼ ∫ 0 ∞ 1 ( z + k ) 2 d k ⏟ = 1 z + 1 2 z 2 + ∑ t = 1 ∞ B 2 t z 2 t + 1 . {\displaystyle \sum _{k=0}^{\infty }{\frac {1}{(z+k)^{2}}}\sim \underbrace {\int _{0}^{\infty }{\frac {1}{(z+k)^{2}}}\,dk} _{={\frac {1}{z}}}+{\frac {1}{2z^{2}}}+\sum _{t=1}^{\infty }{\frac {B_{2t}}{z^{2t+1}}}.}

Here the left-hand side is equal to ψ(z), namely the first-order polygamma function defined through ψ(z) = D(log Γ(z)); the gamma function Γ(z) is equal to (z − 1)! if z is a positive integer. This results in an asymptotic expansion for ψ(z). 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.

Examples

  • ∑ k = 1 n 1 k s = 1 n s − 1 + s ∫ 1 n ⌊ x ⌋ x s + 1 d x with  s ∈ R ∖ { 1 } , {\displaystyle \sum _{k=1}^{n}{\frac {1}{k^{s}}}={\frac {1}{n^{s-1}}}+s\int _{1}^{n}{\frac {\lfloor x\rfloor }{x^{s+1}}}dx\quad {\text{with }}s\in \mathbb {R} \setminus \{1\},}
  • Harmonic numbers:
∑ k = 1 n 1 k = log ⁡ n + 1 2 + 1 2 n − ∫ 1 n x − ⌊ x ⌋ − 1 2 x 2 d x ≈ log ⁡ n + γ + 1 2 n − 1 12 n 2 + 1 120 n 4 − 1 252 n 6 {\displaystyle {\begin{aligned}\sum _{k=1}^{n}{\frac {1}{k}}&=\log n+{\frac {1}{2}}+{\frac {1}{2n}}-\int _{1}^{n}{\frac {x-\lfloor x\rfloor -{\frac {1}{2}}}{x^{2}}}dx\\&\approx \log n+\gamma +{\frac {1}{2n}}-{\frac {1}{12n^{2}}}+{\frac {1}{120n^{4}}}-{\frac {1}{252n^{6}}}\end{aligned}}}
where γ ≈ 0.5772156649015328606065… is the Euler constant,
  • ∑ k = 1 n 1 k 2 ≈ π 2 6 − 1 n + 1 2 n 2 − 1 6 n 3 + 1 30 n 5 − 1 42 n 7 . {\displaystyle \sum _{k=1}^{n}{\frac {1}{k^{2}}}\approx {\frac {\pi ^{2}}{6}}-{\frac {1}{n}}+{\frac {1}{2n^{2}}}-{\frac {1}{6n^{3}}}+{\frac {1}{30n^{5}}}-{\frac {1}{42n^{7}}}.}

Proofs

Derivation by mathematical induction

We follow the argument given in Apostol.

The Bernoulli polynomials Bn(x) and the periodic Bernoulli functions Pn(x) for n = 0, 1, 2, ... were introduced above.

The first several Bernoulli polynomials are

B 1 ( x ) = x − 1 2 B 2 ( x ) = x 2 − x + 1 6 B 3 ( x ) = x 3 − 3 2 x 2 + 1 2 x B 4 ( x ) = x 4 − 2 x 3 + x 2 − 1 30 ⋮ {\displaystyle {\begin{aligned}B_{1}(x)&=x-{\tfrac {1}{2}}\\B_{2}(x)&=x^{2}-x+{\tfrac {1}{6}}\\B_{3}(x)&=x^{3}-{\tfrac {3}{2}}x^{2}+{\tfrac {1}{2}}x\\B_{4}(x)&=x^{4}-2x^{3}+x^{2}-{\tfrac {1}{30}}\\&\qquad \vdots \end{aligned}}}

The values Bn(0) are the Bernoulli numbers. Notice that for n ≠ 1 we have

B n ( 0 ) = B n ( 1 ) = B n ( n th Bernoulli number ) {\displaystyle B_{n}(0)=B_{n}(1)=B_{n}\quad (n{\text{th Bernoulli number}})}

For n = 1,

B 1 ( 0 ) = − B 1 ( 1 ) = B 1 {\displaystyle B_{1}(0)=-B_{1}(1)=B_{1}}

The functions Pn agree with the Bernoulli polynomials on the interval and are periodic with period 1. Furthermore, except when n = 1, they are also continuous. Thus,

P n ( 0 ) = P n ( 1 ) = B n for  n ≠ 1 {\displaystyle P_{n}(0)=P_{n}(1)=B_{n}\quad {\text{for }}n\neq 1}

Let k be an integer, and consider the integral

∫ k k + 1 f ( x ) d x = ∫ k k + 1 u d v {\displaystyle \int _{k}^{k+1}f(x)\,dx=\int _{k}^{k+1}u\,dv}

where

u = f ( x ) d u = f ′ ( x ) d x d v = P 0 ( x ) d x since  P 0 ( x ) = 1 v = P 1 ( x ) {\displaystyle {\begin{aligned}u&=f(x)\\du&=f'(x)\,dx\\dv&=P_{0}(x)\,dx&&{\text{since }}P_{0}(x)=1\\v&=P_{1}(x)\end{aligned}}}

Integrating by parts, we get

∫ k k + 1 f ( x ) d x = [ u v ] k k + 1 − ∫ k k + 1 v d u = [ f ( x ) P 1 ( x ) ] k k + 1 − ∫ k k + 1 f ′ ( x ) P 1 ( x ) d x = B 1 ( 1 ) f ( k + 1 ) − B 1 ( 0 ) f ( k ) − ∫ k k + 1 f ′ ( x ) P 1 ( x ) d x {\displaystyle {\begin{aligned}\int _{k}^{k+1}f(x)\,dx&={\Big }_{k}^{k+1}-\int _{k}^{k+1}v\,du\\&={\Big }_{k}^{k+1}-\int _{k}^{k+1}f'(x)P_{1}(x)\,dx\\&=B_{1}(1)f(k+1)-B_{1}(0)f(k)-\int _{k}^{k+1}f'(x)P_{1}(x)\,dx\end{aligned}}}

Using B1(0) = −⁠1/2⁠, B1(1) = +⁠1/2⁠, and summing the above from k = 0 to k = n − 1, we get

∫ 0 n f ( x ) d x = ∫ 0 1 f ( x ) d x + ⋯ + ∫ n − 1 n f ( x ) d x = f ( 0 ) 2 + f ( 1 ) + ⋯ + f ( n − 1 ) + f ( n ) 2 − ∫ 0 n f ′ ( x ) P 1 ( x ) d x {\displaystyle {\begin{aligned}\int _{0}^{n}f(x)\,dx&=\int _{0}^{1}f(x)\,dx+\cdots +\int _{n-1}^{n}f(x)\,dx\\&={\frac {f(0)}{2}}+f(1)+\cdots +f(n-1)+{\frac {f(n)}{2}}-\int _{0}^{n}f'(x)P_{1}(x)\,dx\end{aligned}}}

Adding ⁠f(n) − f(0)/2⁠ to both sides and rearranging, we have

∑ k = 1 n f ( k ) = ∫ 0 n f ( x ) d x + f ( n ) − f ( 0 ) 2 + ∫ 0 n f ′ ( x ) P 1 ( x ) d x ( 1 ) {\displaystyle \sum _{k=1}^{n}f(k)=\int _{0}^{n}f(x)\,dx+{\frac {f(n)-f(0)}{2}}+\int _{0}^{n}f'(x)P_{1}(x)\,dx\qquad (1)}

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

Next, consider

∫ k k + 1 f ′ ( x ) P 1 ( x ) d x = ∫ k k + 1 u d v {\displaystyle \int _{k}^{k+1}f'(x)P_{1}(x)\,dx=\int _{k}^{k+1}u\,dv}

where

u = f ′ ( x ) d u = f ″ ( x ) d x d v = P 1 ( x ) d x v = 1 2 P 2 ( x ) {\displaystyle {\begin{aligned}u&=f'(x)\\du&=f''(x)\,dx\\dv&=P_{1}(x)\,dx\\v&={\tfrac {1}{2}}P_{2}(x)\end{aligned}}}

Integrating by parts again, we get

[ u v ] k k + 1 − ∫ k k + 1 v d u = [ f ′ ( x ) P 2 ( x ) 2 ] k k + 1 − 1 2 ∫ k k + 1 f ″ ( x ) P 2 ( x ) d x = B 2 2 ( f ′ ( k + 1 ) − f ′ ( k ) ) − 1 2 ∫ k k + 1 f ″ ( x ) P 2 ( x ) d x {\displaystyle {\begin{aligned}{\Big }_{k}^{k+1}-\int _{k}^{k+1}v\,du&={\Big }_{k}^{k+1}-{\frac {1}{2}}\int _{k}^{k+1}f''(x)P_{2}(x)\,dx\\&={\frac {B_{2}}{2}}(f'(k+1)-f'(k))-{\frac {1}{2}}\int _{k}^{k+1}f''(x)P_{2}(x)\,dx\end{aligned}}}

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

∑ k = 1 n f ( k ) = ∫ 0 n f ( x ) d x + f ( n ) − f ( 0 ) 2 + B 2 2 ( f ′ ( n ) − f ′ ( 0 ) ) − 1 2 ∫ 0 n f ″ ( x ) P 2 ( x ) d x . {\displaystyle \sum _{k=1}^{n}f(k)=\int _{0}^{n}f(x)\,dx+{\frac {f(n)-f(0)}{2}}+{\frac {B_{2}}{2}}\left(f'(n)-f'(0)\right)-{\frac {1}{2}}\int _{0}^{n}f''(x)P_{2}(x)\,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 which can be formalized by mathematical induction, in which the induction step relies on integration by parts and on the identities for periodic Bernoulli functions.

See also

Notes

  1. Lehmer, D. H. (1940). "On the maxima and minima of Bernoulli polynomials". The American Mathematical Monthly. 47 (8): 533–538. doi:10.2307/2303833.
  2. ^ Devries, Paul L.; Hasbrun, Javier E. (2011). A First Course in Computational Physics (2nd ed.). Jones and Bartlett Publishers. p. 156.
  3. Pengelley, David J. "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.
  4. Abramowitz & Stegun (1972), 23.1.30
  5. Apostol, T. M. (1 May 1999). "An Elementary View of Euler's Summation Formula". The American Mathematical Monthly. 106 (5). Mathematical Association of America: 409–418. doi:10.2307/2589145. ISSN 0002-9890. JSTOR 2589145.

References

Categories: