Approximating the sum of an infinite series (2)

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

    \[ \lim_{n\to\infty}\frac{s_{n+1}-L}{s_n-L}=\mu \]

and 0<\mu<1. If \mu=0 then the convergence is super-linear. Convergence is quadratic if

    \[ \lim_{n\to\infty}\frac{s_{n+1}-L}{(s_n-L)^2}=\mu \]

again with 0<\mu<1. 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 n, 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

    \[ \frac{s_{n+1}-L}{s_n-L}=\frac{s_{n+2}-L}{s_{n+1}-L} \]

and solve for L. This will produce

    \[ L = \frac{s_ns_{n+2}-s_{n+1}^2}{s_{n+1}-2s_{n+1}+s_n} \]

or equivalently as

    \[ L = s_n-\frac{(s_{n+1}-s_n)^2}{s_{n+1}-2s_{n+1}+s_n}. \]

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

    \[ \Delta s_n = s_{n+1}-s_n. \]

Then the second forward difference is

    \[ \Delta^2s_n=\Delta(s_{n+1}-s_n)=(s_{n+2}-s_{n+1})-(s_{n+1}-s_n)=s_{n+2}-2s_{n+1}+s_n. \]

Comparing this with the expression for L above, we can write

    \[ L = s_n-\frac{(\Delta s_n)^2}{\Delta^2s_n}. \]

We can use this to produce a new sequence t_n defined by

    \[ t_n = s_n-\frac{(\Delta s_n)^2}{\Delta^2s_n}. \]

If the initial sequence converges linearly, then this new sequence will converge faster. If the sequence s_n is obtained from a fixed point process (so that s_n=f(s_{n-1})) 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

    \[ \sum_{n=0}^\infty \frac{(-1)^n}{2n+1}=\frac{\pi}{4}. \]

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 11 = N-2 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 10^{-4}, compared to an initial error (in the first sequence of cumulative sums) of 10^{-1}. 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 10^{-12}.

Starting with a sequence s=s_n of partial sums, we can write a simple Matlab program to compute Aitken’s process \lfloor N/2 \rfloor times, where N 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

    \[ \sum_{n=1}^\infty\frac{(-1)^{n+1}}{n^2+2n}=\frac{1}{4}. \]

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

Leave a Reply

Your email address will not be published. Required fields are marked *