Euler-Maclaurin Formula

The Euler-Maclaurin formula or Euler's empirical formula (after Leonhard Euler (1707–1783) and Colin Maclaurin (1698–1746)) is a mathematical formula for calculating a sum of function values ​​through the values ​​of the derivatives of this function at the summation limits - so is Euler came across them. In a modified form, it enables the numerical approximation of a specific integral using individual values ​​of the integrand and its derivatives - this is how Maclaurin derived it.

Notation note

For a sufficiently often differentiable function of a variable , the spelling is a short notation for all throughout the article ${\displaystyle f}$ ${\displaystyle x}$ ${\displaystyle j\in \mathbb {N} _{0}}$ ${\displaystyle f\,^{(j)}(c)}$

${\displaystyle \left.{\frac {\mathrm {d} ^{j}f(x)}{\mathrm {d} x^{j}}}\right|_{x=c},}$

the -th derivative of to , evaluated at the point ${\displaystyle j}$ ${\displaystyle f}$ ${\displaystyle x}$ ${\displaystyle c.}$

Euler-Maclaurin formula for integral approximation

Let be given, i.e. a function that is continuously differentiable at least times on the interval . Then there is a number such ${\displaystyle k\in \mathbb {N} _{0},\;g\in C\,^{2k+2}[0,1]}$ ${\displaystyle g}$ ${\displaystyle [0,1]}$ ${\displaystyle (2k+2)}$ ${\displaystyle \xi \in {]0,1[},}$

${\displaystyle \int _{0}^{1}g(t)\,\mathrm {d} t={\frac {g(1)}{2}}+{\frac {g(0)}{2}}-\sum _{j=1}^{k}{\frac {B_{2j}}{(2j)!}}\left(g\,^{(2j-1)}(1)-g\,^{(2j-1)}(0)\right)-{\frac {B_{2k+2}}{(2k+2)!}}g\,^{(2k+2)}(\xi )}$

holds, where are the Bernoulli numbers . ${\displaystyle B_{j}}$ ${\displaystyle (B_{2}=1/6,B_{4}=-1/30,\ldots )}$

This is a simple form of the Euler-Maclaurin empirical formula in which the summation consists of only two terms (with indices 0 and 1). The term is exactly the approximation of an integral by the area of ​​a trapezoid . The following sum provides a correction term and the last summand the error that arises. This is why this formula is also called “trapezoidal rule with final correction” in numerical integration theory. With this formula it is only possible to determine the error of the trapezoidal rule for the interval if one knows. Thus, this formula does not represent an estimate, but an equality, but only in the form of an existence statement. ${\displaystyle {\tfrac {g(0)}{2}}+{\tfrac {g(1)}{2}}}$ ${\displaystyle [0,1]}$ ${\displaystyle \xi }$

Euler-Maclaurin formula for sum approximation

The usual version of the above empirical formula with the effective remaining term is obtained by converting it to

${\displaystyle {\frac {g(1)}{2}}+{\frac {g(0)}{2}}=\int _{0}^{1}g(t)\,\mathrm {d} t+\sum _{j=1}^{k}{\frac {B_{2j}}{(2j)!}}\left(g\,^{(2j-1)}(1)-g\,^{(2j-1)}(0)\right)+{\frac {B_{2k+2}}{(2k+2)!}}g\,^{(2k+2)}(\xi )}$

and then replace the function with a function that is applied in any interval with endpoints off , but explicitly calculates the remainder as a function of the “next” derivative. To do this, one simply sums up this formula (with an explicit remainder), applied to a corresponding number of displaced unit intervals that exactly cover the given interval . Let and be continuously differentiable at least times , then one obtains like this ${\displaystyle g}$ ${\displaystyle f}$ ${\displaystyle \mathbb {Z} }$ ${\displaystyle \mathbb {Z} }$ ${\displaystyle m,n\in \mathbb {Z} }$ ${\displaystyle f}$ ${\displaystyle [m,n]\subset \mathbb {R} }$ ${\displaystyle (2k+1)}$ ${\displaystyle [m,n]}$

${\displaystyle \sum _{i=m}^{n}f(i)=\int _{m}^{n}f(x)\,\mathrm {d} x+{\frac {f(n)+f(m)}{2}}+\sum _{j=1}^{k}{\frac {B_{2j}}{(2j)!}}\left(f^{(2j-1)}(n)-f^{(2j-1)}(m)\right)+R_{2k}(m,n),}$

in which

${\displaystyle R_{2k}(m,n)=\int _{m}^{n}{\frac {B_{2k+1}(x-\lfloor x\rfloor )}{(2k+1)!}}f^{(2k+1)}(x)\,\mathrm {d} x=(-1)^{2k+1}\int _{m}^{n}{\frac {B_{2k}(x-\lfloor x\rfloor )}{(2k)!}}f^{(2k)}(x)\,\mathrm {d} x}$

with the Bernoulli polynomials . This is the Euler-Maclaurin empirical formula for determining the series for , where is sufficient. If one also uses the convention ${\displaystyle B_{h}\colon [0,1]\mapsto \mathbb {R} }$ ${\displaystyle f(i),}$ ${\displaystyle f\in C\,^{2k}[m,n]}$

${\displaystyle f^{(-1)}(x)=\int f(x)\,\mathrm {d} x}$

for the " -th derivative", the formula can be much more elegant ${\displaystyle (-1)}$

${\displaystyle \forall \ell \leq 2k\colon \quad \sum _{i=m}^{n}f(i)=f(n)+\sum _{j=0}^{\ell }{\frac {B_{j}}{j!}}\left(f^{(j-1)}(n)-f^{(j-1)}(m)\right)+R_{\ell }(m,n)}$

rewrite - you do not have to cancel the summation with an even index in order to determine the remainder of the term - whereby the only Bernoulli number is not equal to 0 with an odd index. If the border crossing is now carried out, one receives ${\displaystyle B_{1}=-1/2}$ ${\displaystyle \ell \to \infty }$

${\displaystyle \sum _{i=m}^{n}f(i)=f(n)+\sum _{j=0}^{\infty }{\frac {B_{j}}{j!}}\left(f^{(j-1)}(n)-f^{(j-1)}(m)\right)}$

for practical use. It should be noted, however, that this often does not represent a convergent series, but only an asymptotic series , more precisely a development according to derivatives of the function.

If you also use the so-called Bernoulli numbers of the second kind and for all other indices - note for all odd ones  - the above equation can be rewritten in a more symmetrical form: ${\displaystyle B_{j}^{\ast }=(-1)^{j}B_{j},\,B_{1}^{\ast }=-B_{1}=1/2}$ ${\displaystyle B_{j}^{\ast }=B_{j}}$ ${\displaystyle B_{j}=0}$ ${\displaystyle j\neq 1}$

${\displaystyle \sum _{i=m}^{n}f(i)=\sum _{j=0}^{\infty }{\frac {1}{j!}}\left(B_{j}^{\ast }f^{(j-1)}(n)-B_{j}f^{(j-1)}(m)\right)}$

Applications

• The classic problem of determining the power sums of the first natural numbers can now be easily transformed using to ${\displaystyle n}$ ${\displaystyle f(i)=i^{a}}$

${\displaystyle \sum _{i=1}^{n}i^{a}=f(1)+\sum _{j=0}^{\infty }{\frac {B_{j}^{\ast }}{j!}}{\frac {a!}{(a-j+1)!}}\left(n^{a-j+1}-1\right)=\zeta (-a)+\sum _{j=0}^{\infty }{\frac {B_{j}^{\ast }}{a+1}}{a+1 \choose j}n^{a+1-j},}$

where the Riemann zeta function denotes. This equation even applies exactly to exponents (not only asymptotically), since in this case all summands from the -th index onwards are the same and one thus obtains Faulhaber's formulas . The above equation can even be used for everyone if one interprets the binomial coefficients (as usual) with a real argument by means of the falling factorial and regards their only "formal singularity", in the case of the undefined term , as and the value of the zeta function at its pole position As with the Fourier transformation , interpreted as the arithmetic mean of the left and right-hand limit values. ${\displaystyle \zeta }$ ${\displaystyle a\in \mathbb {N} _{0}}$ ${\displaystyle (a\!+\!2)}$ ${\displaystyle j}$ ${\displaystyle 0}$ ${\displaystyle a\in \mathbb {R} }$ ${\displaystyle a=-1}$ ${\displaystyle {\tfrac {n^{0}}{0}}}$ ${\displaystyle \ln(n)}$ ${\displaystyle 1}$

• Another classic example is the choice , whereby the general (logarithmized) Stirling series can be obtained from the summation formula and thus the faculties can be calculated quickly even for very large arguments or the gamma function for non-integer arguments. ${\displaystyle f(x)=\ln(x)}$
• A field of application of numerics is opened up if the Euler-Maclaurin formula is converted according to its integral:

${\displaystyle \forall n,m\in \mathbb {Z} \colon }$

${\displaystyle n>m\Rightarrow \int _{m}^{n}f(x)\,\mathrm {d} x=\sum _{i=m+1}^{n}\!f(i)\;-\left(\sum _{j=1}^{2k}{\frac {B_{j}^{\ast }}{j!}}\left(f^{(j-1)}(n)-f^{(j-1)}(m)\right)+R_{2k}(m,n)\right),}$

so that you get a formula for integration. This is also an efficient application for numerical integration , which is often used in practice.

• If you use the midpoint rule instead of the trapezoidal rule , i.e. if you replace the summation of the function values ​​with , you can avoid the sometimes problematic function evaluation at the edges. This is particularly the case if the integrand on the boundary is numerically unstable (e.g. for ) or not defined (e.g. for ). The differences between the odd derivatives are reduced by the factor . The contributions of the differences to the total error are therefore smaller, as is to be expected when applying the midpoint rule. The factor can also be found similarly in the Romberg integration of even and odd functions. It must be taken into account that the differences in the derivative refer to the integral margins even when the midpoint rule is applied. ${\displaystyle \textstyle \sum \nolimits _{i=m+1}^{n}f(i-{\tfrac {1}{2}}),}$ ${\displaystyle {\tfrac {x}{\sin x}}}$ ${\displaystyle x=0}$ ${\displaystyle {\tfrac {1+x}{\pi -\arccos x}}}$ ${\displaystyle x=-1}$ ${\displaystyle (1-2^{-j})}$
• The Euler-Maclaurin formula has an important application for periodic functions that are to be integrated over one or more periods. For such functions, all derivatives at the integral limits are identical and therefore the sum of the differences of the (odd) derivatives (also) disappear there. The integral can thus be approximated with an error of the order by applying the trapezoidal rule . This explains, among other things, why the discrete Fourier transform by summation and the approximation by means of Chebyshev polynomials have such a high accuracy. It should be noted here that the discrete Fourier transform usually refers to the Euler-Maclaurin formula with trapezoidal rule, while the approximation with Chebyshev polynomials uses the midpoint rule. In applications, however, you can also work with the other summation rule. The equivalence is proven with the Euler-Maclaurin formula. ${\displaystyle n}$ ${\displaystyle {\mathcal {O}}(2n)}$
• The Euler-Maclaurin formula also enables an important application for functions that can be mirrored at both integral limits in such a way that they can be continued continuously together with all derivatives. For such functions all odd derivatives at the integral boundaries are equal to zero, and therefore the sum of the differences of the odd derivatives also vanishes. Consequently, here too the error is of the order. Independent of the theoretical background of the Gaussian quadrature , the Gauss-Chebyshev integration or the integral can be derived solely from the Euler-Maclaurin formula. ${\displaystyle {\mathcal {O}}(2n).}$ ${\displaystyle \textstyle \int _{0}^{\pi }\,g(\cos \,t)\,\mathrm {d} t}$

literature

• Donald Ervin Knuth : The Art of Computer Programming . In: Fundamental Algorithms . 3. Edition. tape 1 . Addison-Wesley Longman, Amsterdam 1997, ISBN 0-201-89683-4 , chap. 1.2.11.2, p. 111-115 .
• Konrad Knopp : Theory and Application of Infinite Series . 6th edition. Springer, Berlin / Heidelberg 1996, ISBN 3-540-59111-7 , chap. XIV, S. 536 ff . ( 1964 edition [accessed December 26, 2012]).
• Josef Stoer, Roland Bulirsch : Introduction to Numerical Mathematics II . 5th edition. Springer, New York / Berlin / Heidelberg a. a. 2005, ISBN 978-3-540-23777-8 , chap. 3.3.

Individual evidence

1. ↑ ^{a b} Josef Stoer: Introduction to Numerical Mathematics . 4th edition. Springer, New York / Berlin / Heidelberg a. a. 1983, ISBN 3-540-12536-1 , chap. 3.2, p. 114 .
2. ^ Matthias Gerdts (University of Würzburg): Numerical Mathematics I. (PDF; 1.6 MB) In: unibw.de. Universität der Bundeswehr Munich, pp. 172–175 , accessed on July 2, 2019 (WiSe 2009/2010). 
3. ↑ Ilja Nikolajewitsch Bronstein, Konstantin Adolfowitsch Semendjajew; Günter Grosche, Viktor Ziegler, Dorothea Ziegler: Teubner Pocket Book of Mathematics . "The Bronstein". Ed .: Eberhard Zeidler. 1st edition. B. G. Teubner, Stuttgart / Leipzig / Wiesbaden 1996, ISBN 3-8154-2001-6 , p. 1134 .