Wynn’s epsilon method

An algorithm for easy implementation of Shanks’ non-linear transformation.

S_n are the partial sums of a series S.
Let \epsilon_{-1}(S_n)=0, \epsilon_0(S_n)=S_n, and for r=0,1,2\dots, let

    \[\epsilon_{r+1}(S_n)=\epsilon_{r-1}(S_{n+1})+\fr{\epsilon(S_{n+1})-\epsilon_r(S_n)}\]

The \epsilon_{2k}(S_n) are the equivalent of applying the kth Shanks transformation to the sequence S_n.

e.g. applied to the series \pi=4-\frac{4}{3}+\frac{4}{5}-\frac{4}{7}+\dots

    \begin{align*} n && \epsilon_0(S_n) && \epsilon_1(S_n) && \epsilon_2(S_n)&& \epsilon_3(S_n)&\\ 0 && 4 && {-3/4} &&\tfrac{8}{3}+1/2=\tfrac{19}{6} &&\tfrac{5}{4}-30=\tfrac{-155}{4} & \\ 1 && 4-\frac{4}{3}=\frac{8}{3}&& 5/4&&\tfrac{52}{15}-1/3=\tfrac{47}{15} &&\tfrac{-7}{4}+84=\tfrac{329}{4} & \\ 2 && \frac{8}{3}+\frac{4}{5}=\tfrac{52}{15}&& {-7/4}&&\tfrac{304}{105}+1/4=\tfrac{1321}{420} &&\tfrac{9}{4}-180=\tfrac{-711}{4} & \\ 3 && \tfrac{52}{15}-\frac{4}{7}=\tfrac{304}{105}&&9/4 && \tfrac{1052}{315}-1/5=\tfrac{989}{315}&& \tfrac{-11}{4}+330=\tfrac{1309}{4}& \\ 4 && \tfrac{304}{105}+\frac{4}{9}=\tfrac{1052}{315}&&{-11/4} && \tfrac{10312}{3465}+1/6=\tfrac{21779}{6930}&& & \\ 5 && \tfrac{1052}{315}-\frac{4}{11}=\tfrac{10312}{3465} &&13/4 && && & \end{align*}

    \begin{align*} &n && \epsilon_4(S_n)&& \epsilon_5(S_n)&& \epsilon_6(S_n)&\\ &0 && \frac{5702}{1815}=3.14159779614\dots &&-\frac{324737}{68} &&\frac{11443792}{3642765}=3.14151255983\dots &\\ &1 && \frac{4288}{1365}=3.14139194139\dots &&\frac{56241}{16} && &\\ &2 &&\frac{99952}{31815}=3.1416627377\dots && && & \end{align*}

Result: Well, the best figure was \epsilon_4(S_0) – 3.14159779\dots – 6 correct digits – and that used only the first 5 terms of the original series, at which point the original partial sum was 3.33968\dots – 1 correct digit only. That might be a fluke – but all the later terms have 4 correct digits, the worst is only 0.006% off. Maybe would be better to start the algorithm after a few terms, not right away.
p.s. 30,84,180,330 are of the form n(n+1)(2n+1), see OEIS

references

Hamming – Numerical methods
P. Wynn – On a Device for Computing the e_m(S_n) Transformation, Math. Tables Aids Comp., vol. 10, pp. 91-96, 1956.

Leave a Reply

Your email address will not be published. Required fields are marked *