Accelerating an alternating series
This post looks at an algorithm by Cohen et al [1] to accelerate the convergence of an alternating series. This method is much more efficient than the classical Euler-Van Wijngaarden method.
For our example, we'll look at the series
which converges slowly to -^2/12.
The first algorithm in [1] for approximating
using up to the nth term is given by the following Python code.
def cohen_sum(a, n): d = (3 + 8**0.5)**n d = (d + 1/d)/2 b = -1 c = -d s = 0 for k in range(n): c = b - c s += c*a[k] b = (k+n)*(k-n)*b/((k + 0.5)*(k+1)) return s/d
Two notes: First, the algorithm assumes the index of summation starts at zero and so we'll shift our sum to start at zero. We could just define the first term of the sum to be zero and leave the rest of the series alone, but this would produce worse results; it leads to an initial jump in the series that makes the extrapolation in the method less effective. Second, the alternating term (-1)k is not part of the array passed into the function.
Two graphs, especially the second, will illustrate how well the method of Cohen et al performs compared to the direct method of simply taking partial sums. First, here are the sequence of approximations to the final sum on a linear scale.
And here are the errors in the two methods, plotted on a log scale.
The error from using the direct method of computing partial sums is on the order of 1/n^2 while the error from using the accelerated method is roughly 1/20.7n. In this example, it would take around 30,000 terms for the direct method to achieve the accuracy that the accelerated method achieves with 10 terms.
Note that accelerating convergence can be a delicate affair. Different acceleration methods are appropriate for different sums, and applying the wrong method to the wrong series can actually slow convergence as illustrated here.
More on series acceleration[1] Henri Cohen, Fernando Rodriguez Villegas, and Don Zagier. Convergence Acceleration of Alternating Series. Experimental Mathematics 9:1, page 3