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:

    \[\boxed{\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 =\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

Leave a Reply

Your email address will not be published.