Acceleration of alternating series

Let f(n):\mathbb{N}\to\mathbb{R} be a positive decreasing function such that \lim_{n\to\infty}f(n)=0. Then the alternating series

\displaystyle \sum_{n=0}^{\infty}(-1)^nf(n)

converges. Depending on the rate at which f decays it may however take many terms to get a decent approximation of the sum. Examples of such slowly converging series are

\displaystyle \log(2) = \sum_{n=0}^{\infty}(-1)^n\frac{1}{n+1}

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

A well known method to accelerate the convergence of such alternating series uses the binomial transform of the function f as follows. For m \geq 0 let \Delta^m f be the m-th difference of f:

\displaystyle (\Delta^m f)(n) = \sum_{k=0}^m (-1)^k{m \choose k} f(n+k)

Then it turns out that

\displaystyle \sum_{n=0}^{\infty}(-1)^nf(n) = \sum_{n=0}^{\infty}\frac{(\Delta^n f)(0)}{2^{n+1}}

and the right hand side may converge much faster. The binomial transform for the two examples above can be computed explicitly to obtain

\displaystyle \log(2)=\sum_{n=0}^{\infty}\frac{1}{2^{n+1}(n+1)}

\displaystyle \frac{\pi}{4}=\sum_{n=0}^{\infty}\frac{n!}{2\cdot(2n+1)!!} = \frac{1}{2} + \frac{1}{2\cdot 3} + \frac{2}{2 \cdot 3 \cdot 5} + \frac{2 \cdot 3}{2 \cdot 3 \cdot 5 \cdot 7} + \ldots

Both transformed series indeed converge much faster than the original ones. You may recognize the first as the series for -\log(1-x) taken at x=\tfrac{1}{2}. The second one is harder to spot but it turns out to be the series of

\displaystyle \frac{\arcsin(x)}{\sqrt{2-2x^2}}

taken at x=\tfrac{1}{2}\sqrt{2}.

The binomial transform is a great tool if you can find an explicit expression for it such as in both examples above. This is however not a trivial transform in general. If you do not know an explicit expression for the binomial transform then it is also not very convenient to compute: (\Delta^n f)(0) depends on the values f(k) for all k \leq n.

There is however another much simpler method that only involves the repeated difference \Delta^m f for a single fixed value of m \geq 1. This difference is now easy to compute (numerically) since (\Delta^m f)(n) depends only on m+1 consecutive values of f. It is convenient for the sake of notation to extend f to \mathbb{Z} by setting f(n)=0 for all n < 0. Then (\Delta^m f)(n) = 0 for all n < -m.

Now the following equalities hold in which the second and third sums are taken over \mathbb{Z}:

\displaystyle \sum_{n=0}^{\infty}(-1)^nf(n) = 2^{1-m}\sum_{n \textrm{ even}}(\Delta^m f)(n) = -2^{1-m} \sum_{n \textrm{ odd}} (\Delta^m f)(n)

If all terms (\Delta^m f)(n) are positive for n \geq 0 then partial sums increase for the second series and decrease for the third from n=0 onward. This means that these partial sums are lower and upper bounds for the series which is useful to estimate the remaining error for these partial sums.

As an example take m=2. The series for \log(2) and \tfrac{\pi}{4} now become

\displaystyle \log(2) = \frac{1}{2} +  \sum_{n=0}^{\infty}\frac{1}{(2n+1)(2n+2)(2n+3)} = \frac{3}{4} - \sum_{n=0}^{\infty}\frac{1}{(2n+2)(2n+3)(2n+4)}

\displaystyle \frac{\pi}{4} = \frac{1}{2} +  \sum_{n=0}^{\infty}\frac{4}{(4n+1)(4n+3)(4n+5)} = \frac{5}{6} - \sum_{n=0}^{\infty}\frac{4}{(4n+3)(4n+5)(4n+7)}

This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s