next up previous
Next: Césaro's method Up: Applied Math 475/563b Notes Previous: List of today's

Convergence acceleration in general

Many people were puzzled by the fact that Maple gives two different answers for

depending on whether sum(...) or evalf(Sum(...)) is used. What is the difference between these two, and why do they give different answers sometimes?

BASIC POINT sum works symbolically. evalf(Sum(...)) works numerically.

There is a discussion on p. 43--44 of Essential Maple of this, but this gives no details. The example

is used. Note that this series diverges, but it is part of a family

(this is the famous Riemann function, and this definition holds if when the sequence converges in the conventional sense). If we say

> sum(1/sqrt(k), k=1..infinity);
we get infinity, which is the limit of as , as usual. But if we say
> evalf(Sum(1/sqrt(k), k=1..infinity));
then what we get is the numerical value of . Both facilities are useful sometimes.

How does it work? The best explanation of the sequence acceleration techniques possible is by E. J. Weniger. I have placed a copy of a recent survey report by him, accessible through the course web page. You can either read the html version or print the .dvi file (it's 30 pages, so you may just want to read the opening paragraphs on the web version).

Here I will give an explanation using a simpler technique than the one Maple actually uses.

First we examine why we want to accelerate convergence, sometimes. Consider

which converges for , and in particular converges for . Fine, it converges. Can we compute from this sum?

The Euler-MacLaurin sum formula (see Abramowitz and Stegun, for example) or even just the simple integral test for convergence gives that

which is . So if we need to find 2 decimal places of from straight adding up of terms in this series, we will need or .

This is pretty useless, wouldn't you say? If we assumed that we had a 3 gigaflop machine, capable of flops per second, then it could perform about flops in a year; this means that this 2-decimal place calculation would take about 10 trillion years.

But evalf(Sum(1/k^1.1, k=1..infinity)) with Digits set to 20 gives, in under 5 seconds, the value , which is correct to 20 places (never mind just 2).

The bottom line is that in scientific computing, convergence is not enough. We need fast convergence. There are hundreds of techniques for numerically or analytically improving the speed of convergence of a series or sequence (see Weniger's report).

next up previous
Next: Césaro's method Up: Applied Math 475/563b Notes Previous: List of today's

Robert Corless
Fri Jan 30 13:19:12 EST 1998