Before we begin, some basic definitions. Suppose is a sequence that converges to a limit . We say that the convergence is *linear* if

and . If then the convergence is *super-linear*. Convergence is *quadratic* if

again with . See the wikipedia page for more details. It is not hard to show that if a sequence converges linearly then the increase of significant figures is a linear function of , and if the convergence is quadratic then the number of significant figures roughly doubles at each step.

### Aitken’s delta-squared process

This is named for the esteemed mathematician Alexander Craig Aitken, who published it in 1926. To derive it, assume that

and solve for . This will produce

or equivalently as

We can now invoke the terminology of differences, of which the forward difference can be written

Then the second forward difference is

Comparing this with the expression for above, we can write

We can use this to produce a new sequence defined by

If the initial sequence converges linearly, then this new sequence will converge faster. If the sequence is obtained from a fixed point process (so that ) then this is called Steffensen’s method, and can be shown to have quadratic convergence. However, our interest is in series approximation.

As an example, we’ll take the first few cumulative sums of our standard sequence

And for simplicity, we’ll use a numerical package (Matlab, GNU Octave, Scilab, etc).

>> N = 13; >> n = 0:N-1; >> a = (-1).^n./(2*n+1); >> s = cumsum(a); >> 4*s' ans = 4.000000000000000 2.666666666666667 3.466666666666667 2.895238095238096 3.339682539682540 2.976046176046176 3.283738483738484 3.017071817071818 3.252365934718877 3.041839618929403 3.232315809405594 3.058402765927333 3.218402765927333

As we would expect, the final result is very innacurate. So we’ll give Aitken’s method a go, first taking out subsequences of length so as to be able to compute all the differences we need:

>> s0 = s(1:N-2); >> s1 = s(2:N-1); >> s3 = s(3:N); >> t = s0 - (s1-s0).^2./(s2-2*s1+s0); >> 4*t' ans = 3.166666666666667 3.133333333333334 3.145238095238096 3.139682539682540 3.142712842712843 3.140881340881342 3.142071817071818 3.141254823607766 3.141839618929403 3.141406718496503 3.141736099260667

and already the last value is surprisingly accurate: with and error of only , compared to an initial error (in the first sequence of cumulative sums) of . And we can apply the delta-squared process to this new sequence:

>> N = N-2; >> t0 = t(1:N-2); >> t1 = t(2:N-1); >> t2 = t(3:N); >> u = t0 - (t1-t0).^2./(t2-2*t1+t0); >> 4*t' ans = 3.142105263157895 3.141450216450217 3.141643323996266 3.141571290201428 3.141602841602842 3.141587320947787 3.141595655236941 3.141590862710498 3.141593774239114

and we have increased the accuracy again. If we applied this process to successively decreasing sequences, the final values would be:

3.218402765927333 3.141736099260667 3.141593774239114 3.141592673909636 3.141592654277287 3.141592653625053 3.141592653591176

and this last value is in error only by about .

Starting with a sequence of partial sums, we can write a simple Matlab program to compute Aitken’s process times, where is the length of the sequence:

function out = aitken(s) % Applies Aitken's delta-squared process to a vector s, which we suppose to % represent a sequence converging to some limit L N = length(s); M = N; % length of current vector a = reshape(s,N,1); % ensures we are working with column vectors out = a; for i = 1:floor(N/2) a0 = a(1:M-2); a1 = a(2:M-1); a2 = a(3:M); b = a0 - (a1-a0).^2./(a2-2*a1+a0); bcol = zeros(N,1); bcol(2*i+1:N) = b; out = [out bcol]; M = M-2; a = b; end

For example, let’s look at the sequence

>> N = 13; n = 1:N; a = (-1).^(n+1)./(n.^2+2*n); s = cumsum(a); >> s.' ans = 0.333333333333333 0.208333333333333 0.275000000000000 0.233333333333333 0.261904761904762 0.241071428571429 0.256944444444444 0.244444444444444 0.254545454545455 0.246212121212121 0.253205128205128 0.247252747252747 0.252380952380952 >> atk = aitken(s); >> atk(end,:).' ans = 0.252380952380952 0.250007568189386 0.250000065527560 0.250000001161480 0.250000000036343 0.250000000001713 0.250000000000078