Accelerating an alternating series

Posted on by John

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

\sum_{k=1}^\infty \frac{(-1)^k}{k^2}

which converges slowly to -π²/12.

The first algorithm in [1] for approximating

\sum_{k = 1}^\infty (-1)^k a_k

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² 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

2 thoughts on “Accelerating an alternating series”

  1. I was curious if there was a way to calculate d_n that makes it more obviously an integer. The d_n satisfy a three term recurrence: d_{n+1} = 6*d_n – d_{n-1}, with initial conditions d_1 = 1, d_2 = 3, so you can get the nth term from a matrix power:

    [1 0] * [6 -1; 1 0]^n * [3; 1]

    where the nth power of the matrix can be computed efficiently with the power-by-squaring algorithm. This parallels a similar strategy for computing Fibonacci numbers.

Comments are closed.