Van Wijngaarden transformation

From Wikipedia, the free encyclopedia

In mathematics and numerical analysis, in order to accelerate convergence, Euler's transform can be implemented as follows: compute the partial sums of an alternating series:

s_{k,0} = \sum_{n=0}^k(-1)^n a_n.

Form a new sequence by simply taking the average of two consecutive terms, i.e.

s_{k,j+1} = (s_{k,j}+s_{k+1,j})/2, \quad k=0,1,2,\ldots,

where \, j=0. Keep on doing this for j=1,2,\ldots. The partial sums of Euler's transform are s_{0,0}, s_{0,1}, s_{0,2},\dots

Van Wijngaarden's contribution was to point out that it is better not to carry this procedure through to the very end, but to stop two-thirds of the way[1]. E.g. if you have a_0,a_1,\ldots,a_{12} available, then \, s_{4,8} is almost always a better approximation to the sum than s\, _{0,12}.

For example, Leibniz's series

4 (1 - 1/3 + 1/5 - 1/7 + \cdots) = \pi = 3.14159265\ldots

gives \,s_{0,12} = 3.1416008, whereas \,s_{4,8} = 3.1415931.

[edit] References

  1. ^ A. van Wijngaarden, in: Cursus: Wetenschappelijk Rekenen B, Process Analyse, Stichting Mathematisch Centrum, (Amsterdam, 1965) pp 51-60