the Euler transformation

Euler 1755.
(aka Euler’s method, Euler transform, Euler summation)

Derivation

Buchanan & Turner give a very simple derivation using difference operators and their basic properties.

$\begin{align*} \intertext{The shift operator $E$ :} E(a_n)&=a_{n+1}\\ \intertext{the forward difference operator $\Delta$ :} \Delta(a_n)&=a_{n+1}-a_n\\ \intertext{From} \Delta(a_n)&=a_{n+1}-a_n=E(a_n)-a_n=(E-1)a_n\\ \intertext{we deduce that} E&=1+\Delta \end{align*}$

Consider the summation of an alternating series:

$\begin{align*} \sum(-1)^na_n&=a_0-a_1+a_2-a_3+\dots\\ &=a_0-Ea_0+E^2a_0-E^3a_0+\dots\\ &=(1-E+E^2-E^3+\dots)a_0 \qquad \text{(1)} \end{align*}$

$\fr{1+x}=1-x+x^2-x^3+x^4-\dots \qquad \text{(2)}$

Since $1-E+E^2-E^3+\dots$ is the RHS of $(2)$ , with $x=E$ , we have:

$\sum(-1)^na_n&=\frac{1}{1+E}a_0$

Substituting in $E=1+\Delta$ :

$\begin{align*} &=\frac{1}{2+\Delta}a_0\\ &=\frac{1}{2}\Big(\frac{1}{1+\Delta/2}\Big)a_0 \end{align*}$

Substituting in $(2)$ with $x=\Delta/2$ gets the Euler transform:

$\sum\limits_{n=0}^\infty (-1)^n a_n&=\frac{1}{2}(1-\frac{\Delta}{2}+\frac{\Delta^2}{4}-\frac{\Delta^3}{8}+\frac{\Delta^4}{16}-\dots)a_0$

$\boxed{\sum\limits_{n=0}^\infty (-1)^n a_n=\fr{2}\sum\limits_{i=0}^\infty \frac{(-1)^i}{2^i}\Delta^i a_0}\quad \text{(3)}$

Hamming in Numerical Methods gives a more complicated derivation using summation by parts, arriving at the more general form:

$\sum\limits_{k=0}^\infty a_k t^k = \fr{1-t}\sum\limits_{i=0}^\infty \big( \frac{t}{1-t}\big)^i \Delta^i a_0$

He says “the most frequent case of application is when $t=-1$ ” (i.e. the form in equation $(3)$ ) and gives as an example of its use to make a series converge faster:

$\begin{align*} 1-\fr{2}+\fr{4}-\fr{8}+\dots&=\sum\limits_{k=0}^\infty \frac{(-1)^k}{2^k}\\ \intertext{We have} a_n&=\fr{2^n} \\ \Delta a_n&=\fr{2^{n+1}}-\fr{2^n}=\frac{-1}{2^{n+1}} \\ \Delta^i a_0 &=\frac{(-1)^i}{2^i}\\ \intertext{And so by $(3)$} \sum\limits_{k=0}^\infty \frac{(-1)^k}{2^k} &=\fr{2}\sum\limits_{i=0}^\infty \frac{(-1)^i}{2^i}\frac{(-1)^i}{2^i} = \fr{2}\sum\limits_{i=0}^\infty \fr{4^i}\\ &=\fr{2}(1+\fr{4}+\fr{16}+\fr{64}+\dots) \end{align*}$

which converges more quickly.

(but e.g. with the series $1-\fr{3}+\fr{9}-\fr{27}+\dots$ , in Hamming’s formula $t$ is $-2$ , and the transformation converges no more quickly.)

Numerical Recipes says “Generally it is advisable to do a small number of terms directly, through term $n-1$ , and then apply the transformation to the rest of the series beginning with term $n$ . The formula (for $n$ even) is

$\sum\limits_{s=0}^\infty (-1)^s a_s = a_0-a_1+a_2\dots-a_{n-1}+\sum\limits_{s=0}^\infty \frac{(-1)^s}{2^{s+1}}[\Delta^s a_n]$

the Euler transform is “the result of applying the binomial transform to the sequence associated with [a sequence’s] ordinary generating function.” – wikip, ‘binomial transform’

references

Buchanan, Turner – Numerical Methods and Analysis
Richard Hamming – Numerical methods for scientists and engineers
Numerical Recipes, 3rd ed., Ch.5

adamponting.com

the Euler transformation

Leave a Reply Cancel reply