Accelerating convergence with Aitken’s method

Posted on by John

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.

Aitken’s method

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.

Example

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.

When to use

Why would you use an acceleration method rather than just adding up more terms of the series. The latter might be the thing to do, depending on context. If the terms of the series are expensive to calculate, acceleration will be more economical since it only requires a few arithmetic operations. If the terms of your series involve special functions, the additional cycles needed to apply Aitkin acceleration are negligible.

Sometimes you only have a limited number of terms, such as when you’ve derived the first few terms from a hand calculation. For example, maybe you’ve computed a series solution to a differential equation. In that case, Aitken’s method lets you squeeze a little more accuracy out of the terms you have.

More computational posts