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