Euler-Maclaurin-Formel

Die Euler-Maclaurin-Formel oder Eulersche Summenformel (nach Leonhard Euler und Colin Maclaurin) ist eine mathematische Formel, die die Berechnung einer endlichen Summe durch eine (algebraische) Summe von Ableitungen einer Funktion an den Grenzen dieser zu summierenden Funktion ermöglicht – so ist Euler auf sie gestoßen – oder umgekehrt, die die Berechnung eines bestimmten Integrals über die Summierung seiner Stützstellen und zur verbesserten numerischen Approximation noch die Werte der Ableitungen des Integranden an seinen Integrationsgrenzen nutzt – so hat sie historisch Maclaurin hergeleitet – in Verbindung bringt.

Also: entweder man möchte eine diskrete Summe algebraisch (eventuell auch nur numerisch) beschreiben (auswerten), oder man will ein bestimmtes Integral möglichst gut numerisch approximieren.

Notationshinweis

Für eine genügend oft differenzierbare Funktion $f$ einer Veränderlichen $x$ ist im gesamten Artikel für alle $j\in \mathbb {N} _{0}$ die Schreibweise $f\,^{(j)}(c)$ eine Kurznotation für:

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

also die $j$-te Ableitung von $f$ nach $x$ ausgewertet an der Stelle $c$.

Euler-Maclaurin-Formel zur Integralapproximation

Sei $k\in \mathbb {N} _{0},\;g\in C\,^{2k+2}[0,1]$ (also eine Funktion, die auf dem Intervall $[0,1]$ mindestens $2k+2$-mal stetig differenzierbar ist) gegeben. Dann existiert eine Zahl $\xi \in ]0,1[$, so dass

$\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 )$

gilt, wobei $B_{j}$ die Bernoulli-Zahlen $(B_{2}=1/6,B_{4}=-1/30,\ldots )$ sind.

Dies ist eine einfache Form der Euler-Maclaurinschen Summenformel, bei der die Summation nur zwei Terme (mit Index 0 und 1) umfasst. Der Term ${\tfrac {g(0)}{2}}+{\tfrac {g(1)}{2}}$ ist genau die Approximation eines Integrals durch den Flächeninhalt eines Trapezes. Die nachfolgende Summe liefert ein Korrekturglied und der letzte Summand den Fehler, der dabei entsteht. Daher heißt diese Formel in der numerischen Integrationstheorie auch Trapezregel mit Endkorrektur. Mit dieser Formel ist es nur möglich den Fehler der Trapezregel für das Intervall $[0,1]$ zu bestimmen, falls man $\xi$ kennt. Somit stellt diese Formel zwar keine Abschätzung, sondern eine Gleichheit dar, allerdings nur in Form einer Existenzaussage.

Euler-Maclaurin-Formel zur Summenapproximation

Die übliche Fassung obiger Summenformel mit effektiver Restgliedangabe erhält man, indem man sie umstellt zu:

${\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 )$

und dann die Funktion $g$ durch eine Funktion $f$ ersetzt, die in einem beliebigen Intervall mit Endpunkten aus $\mathbb {Z}$ angewendet wird, aber das Restglied explizit als Funktion der „nächsten“ Ableitung berechnet. Dazu summiert man einfach diese Formel, angewendet auf entsprechend viele verschobene Einheitsintervalle, die das gegebene Intervall aus $\mathbb {Z}$ genau abdecken, auf. Sei $m,n\in \mathbb {Z}$ und $f$ auf $[m,n]\subset \mathbb {R}$ mindestens $2k+1$-mal stetig differenzierbar auf $[m,n]$, dann erhält man so:

$\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)$,

wobei:

$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$

mit den Bernoulli-Polynomen $B_{h}\colon [0,1]\mapsto \mathbb {R}$ ist. Dies ist die Euler-Maclaurin-Summenformel um die Reihe für $f(i)$ zu bestimmen, wobei $f\in C\,^{2k}[m,n]$ schon ausreichend ist. Verwendet man ferner die Konvention

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

für die $-1$-te Ableitung, so lässt sich die Formel wesentlich eleganter zu

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

schreiben – man muss nicht bei einem geraden Index die Summation abbrechen um eine Restgliedbestimmung zu machen –, wobei die einzige Bernoulli-Zahl mit ungeradem Index die ungleich 0 ist, $B_{1}=1/2$ ist. Wird nun noch der Grenzübergang $\ell \to \infty$ durchgeführt, erhält man:

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

für die praktische Anwendung. Dabei ist allerdings zu beachten, dass dies oft keine konvergente, sondern nur eine asymptotische Reihe, genauer eine Entwicklung nach Ableitungen der Funktion, darstellt. Dieser „unschöne“ Term $f(m)$ liegt an der Wahl der Bernoulli-Zahlen. Die Alternative $(-1)^{j}B_{j}$, die sich nur beim Index 1 auswirkt und auf $B_{1}^{\ast }=-1/2$ führt, erzeugt anstelle von $f(m)$ den Term $f(n)$ der von der oberen Summationsgrenze stammt. Eine symmetrische Darstellung der Euler-Maclaurin-Formel erhält man, wenn man beide Arten von Bernoulli-Zahlen in den Summanden nutzt (ohne einen $(-1)^{j}$ Faktor einführen zu müssen):

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

Anwendungen

• Das klassische Problem der Bestimmung der Potenzsummen der ersten $n$ natürlichen Zahlen lässt sich nun einfach mittels $f(i)=i^{a}$ umtransformieren zu:

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

wobei $\zeta$ die Riemannsche Zetafunktion bezeichnet. Diese Gleichung gilt für Exponenten $a\in \mathbb {N} _{0}$ sogar exakt (nicht nur asymptotisch), da in diesem Fall alle Summanden ab dem $a\!+\!2$-ten $j$-Index null sind und man somit die Faulhaberschen Formeln erhält. Ferner hat man im klassischen Fall der negativen ganzen Exponenten $a\not =-1$, dass alle Summanden im Grenzübergang $n\to \infty$ verschwinden und erhält somit den Grenzwert

$\sum _{i=1}^{n}i^{a}=\zeta (-a)$,

den Euler erstmalig für gerade negative Exponenten $a$ bestimmte. Die obige Gleichung ist sogar für alle $a\in \mathbb {R}$ benutzbar, wenn man die Binominalkoeffizienten (wie mathematisch üblich) bei reellem Argument als fallende Faktorielle interpretiert und ihre einzige „formale Singularität“, im Fall $a=-1$ den undefinierten Term ${\tfrac {n^{0}}{0}}$, als $\ln(n)$ ansieht und den Wert der Zetafunktion an ihrer Polstelle bei $1$, wie bei der Fouriertransformation auch, als arithmetisches Mittel des links- und rechtsseitigen Grenzwertes interpretiert.

• Ein weiteres klassisches Beispiel ist die Wahl $f(x)=\ln(x)$, wodurch man aus der Summationsformel die allgemeine (logarithmierte) Stirling-Reihe erhält und so die Fakultäten auch für sehr große Argumente schnell, oder für nicht ganzzahlige Argumente effizient berechnen kann.

• Ein Anwendungsgebiet der Numerik wird eröffnet, wenn man die Euler-Maclaurin-Formel nach ihrem Integral umstellt:

$\int _{m}^{n}f(x)\,\mathrm {d} x=\sum _{i=m+1}^{n}\!f(i)\;-\left(\sum _{j=1}^{2k}{\frac {B_{j}}{j!}}\left(f^{(j-1)}(n)-f^{(j-1)}(m)\right)+R_{2k}(m,n)\right)\quad \forall n,m\in \mathbb {Z} \;{\text{ mit }}n>m$,

so dass man eine Formel zur Integration gewinnt. Dies ist auch eine effiziente Anwendung zur numerischen Integration die in der Praxis oft genutzt wird.

• Benutzt man anstelle der Trapezregel die Mittelpunktsregel – also ersetzt die Summation der Funktionswerte durch $\textstyle \sum \nolimits _{i=m+1}^{n}f(i-{\tfrac {1}{2}})$ –, kann man die manchmal problematische Funktionsauswertung an den Rändern vermeiden. Dies ist besonders dann der Fall, wenn der Integrand auf dem Rand numerisch instabil (z. B. ${\tfrac {x}{\sin x}}$ für $x=0$) oder nicht definiert ist (bspw. ${\tfrac {1+x}{\pi -\arccos x}}$ für $x=-1$). Hierbei werden die Differenzen der ungeraden Ableitungen jeweils um den Faktor $(1-2^{-j})$ verkleinert. Die Beiträge der Differenzen zum Gesamtfehler werden also kleiner, wie es bei Anwendung der Mittelpunktsregel zu erwarten ist. Der Faktor findet sich ähnlich auch in der Romberg-Integration gerader und ungerader Funktionen wieder. Es ist zu berücksichtigen, dass sich auch bei Anwendung der Mittelpunktsregel die Differenzen der Ableitung auf die Integralränder beziehen.

• Eine wichtige Anwendung hat die Euler-Maclaurin-Formel bei periodischen Funktionen, die über eine oder mehrere Perioden integriert werden sollen. Für solche Funktionen sind auch alle Ableitungen an den Integralgrenzen identisch gleich und deshalb verschwinden dort (auch) die Summe der Differenzen der (ungeraden) Ableitungen. Das Integral lässt sich also durch $n$-fache Anwendung der Trapezregel mit einem Fehler der Ordnung $O(2n)$ approximieren. Dies erklärt unter anderem, warum die diskrete Fouriertransformation durch Summation und die Approximation mittels Tschebyschow-Polynomen eine so hohe Genauigkeit haben. Hierbei ist zu bemerken, dass sich die diskrete Fouriertransformation üblicherweise auf die Euler-Maclaurin-Formel mit Trapezregel bezieht, während die Approximation mit Tschebyschow-Polynomen die Mittelpunktsregel nutzt. Bei Anwendungen kann man aber auch mit der jeweils anderen Summationsregel arbeiten. Die Gleichwertigkeit wird mit der Euler-Maclaurin-Formel bewiesen.

• Die Euler-Maclaurin-Formel hat ebenfalls eine wichtige Anwendung bei Funktionen, die an beiden Integralgrenzen so gespiegelt werden können, dass sie zusammen mit allen Ableitung stetig fortgesetzt werden können. Für solche Funktionen sind alle ungeraden Ableitungen an den Integralgrenzen gleich Null und deshalb verschwindet die Summe der Differenzen der ungeraden Ableitungen ebenfalls. Folglich ist auch hier der Fehler von der Ordnung $O(2n)$. Unabhängig von den theoretischen Hintergründen der Gauß-Quadratur lässt sich die Gauß-Tschebyschew-Integration bzw. das Integral $\int _{0}^{\pi }\,g(\cos \,t)\,\mathrm {d} t$ allein mit der Euler-Maclaurin-Formel herleiten.

Literatur

• Donald Ervin Knuth: The Art of Computer Programming. In: Fundamental Algorithms. 3. Auflage. Band 1. Addison Wesley Longman, Amsterdam 1997, ISBN 0-201-89683-4, Kap. 1.2.11.2, S. 111–115. 
• Konrad Knopp: Theorie und Anwendung der unendlichen Reihen. 6. Auflage. Springer, Berlin/Heidelberg 1996, ISBN 3-540-59111-7, Kap. XIV, S. 536 ff. (Ausgabe von 1964 [abgerufen am 26. Dezember 2012]). 
• Josef Stoer, Roland Bulirsch: Einführung in die Numerische Mathematik II. 5. Auflage. Springer, New York/Berlin/Heidelberg u. a. 2005, ISBN 978-3-540-23777-8, Kap. 3.3.