Accelerating convergence with Aitken’s method

The previous post looked at Euler’s method for accelerating the convergence of a slowly converging alternating series. Both hypotheses are necessary. The signs must alternate between terms, and applying the method to a series that is already converging quickly can slow down convergence.

This post looks at Aitken’s method for speeding up the convergence of a series. It does not matter whether the series is an alternating series or not. Aitken’s method works best when the series is converging approximately like a geometric series, which is often true for power series of analytic functions.

Aitken acceleration estimates the sum of a series by taking the last three partial sums and extrapolating to where the partial sums appear to be going. That is, it estimates the sum as

s_{n+2} - \frac{(s_{n+2} - s_{n+1})^2}{s_{n+2} - 2s_{n+1} + s_n}

We’ll use the exponential function as our example, estimating exp(0.3) first by using six terms of the Taylor series for exp(x) and then by applying Aitken’s method.

Here’s a little Python code to carry out our example.

from math import exp, factorial
from numpy import cumsum

def aitken(s0, s1, s2):
    return s2 - (s2 - s1)**2/(s2 - 2*s1 + s0)

def exp_partial_sums(x, N):
    terms = [x**n/factorial(n) for n in range(N)]
    return cumsum(terms)

x, N = 0.3, 6
partial = exp_partial_sums(x, N)

# estimate taking the last partial sum
p = partial[-1]

# estimate applying Aitken acceleration
a = aitken( partial[-3], partial[-2], partial[-1] )

# error analysis
error_p = exp(x) - p
error_a = exp(x) - a
print(error_p, error_a, error_p/error_a)

This says the error simply using partial sums is 1.0576e-06. The error using Aitken acceleration is -2.3498e-07, which is 4.5 times smaller.

If we go back to the example of the Struve function in the previous post, the approximation error using Aitken acceleration is about 3 times smaller than simply using partial sums. So Aikten acceleration would have been more appropriate than Euler acceleration.

For more content like this post, see Computational math.