Turning a slow series geometric

The series everything else is measured against made the geometric series the yardstick of convergence: a series converges if its terms eventually fit under some $r^n$ with $r < 1$, and a series that fits under one converges fast, losing a fixed fraction of what is left at every step. The sum that fits in one square is the model: half, a quarter, an eighth, each term a fixed fraction of the last. Many series that matter do not fit under any geometric series. They converge, but slowly, their terms shrinking like a power of $1/n$ rather than like a power of a ratio, and the yardstick has nothing to say about them except that they are on the wrong side of it.

The most famous is the series for $\pi$ found by Madhava in Kerala around 1400 and again by James Gregory and Gottfried Leibniz in the 1670s:

$$\frac{\pi}{4} = 1 - \frac13 + \frac15 - \frac17 + \frac19 - \cdots$$

It is beautiful and almost useless. After $n$ terms the error is about $1/(4n)$, so ten correct decimal places need about five billion terms. This essay is about a family of rules that take the same terms and do something cleverer with them than adding them up — and about the sense in which each such rule is a way of making a slow series geometric.

Forty terms, two digits or thirteen #

The figure takes the first forty terms of Leibniz’s series and feeds them to four procedures. The first simply adds them up. The other three are accelerators: rules that read a sequence of partial sums and return a better estimate of the limit, using nothing but those numbers.

The partial sums creep: forty terms leave an error of $6.2 \times 10^{-3}$, two correct digits. On a logarithmic scale against the number of terms their error is nearly flat, because each tenfold increase in terms buys one more digit. Euler’s transformation of the same forty terms reaches $1.3 \times 10^{-13}$, thirteen digits, and its error is a straight line — a fixed number of digits gained per term, the signature of a geometric series. Wynn’s ε table reaches the same accuracy from only seventeen terms. Aitken’s process applied once is in between, much better than the series and much worse than the other two. The rest of the essay takes these three in turn.

Averaging away the zigzag #

Leibniz’s partial sums overshoot and undershoot by turns: 1, then 0.667, then 0.867, then 0.724, the true value 0.785 always between consecutive sums. An alternating series whose terms shrink steadily behaves this way, and the alternation is itself the error — it is a zigzag around the limit whose amplitude shrinks only like $1/n$.

The obvious repair is to average neighbouring partial sums, so that each overshoot cancels against the following undershoot. That helps a great deal, and then the averages zigzag a little too, so average those, and repeat.

The largest error falls from 0.21 in the partial sums to 0.048 after one round of averaging, 0.015 after two and 0.0051 after three. Each round more than halves it. Carried to the end — averaging a row of $n$ partial sums $n - 1$ times until one number is left — this is Euler’s transformation, which Leonhard Euler published in 1755 not as repeated averaging but as a new series. For an alternating series $a_0 - a_1 + a_2 - \cdots$ it reads

$$\sum_{k \ge 0} (-1)^k a_k = \sum_{n \ge 0} \frac{(-\Delta)^n a_0}{2^{n+1}},$$

where $\Delta$ is the forward difference, $\Delta a_k = a_{k+1} - a_k$. The factor $2^{-(n+1)}$ is the averaging: each round halves.

What one average already knows #

The first round of averaging has a simple meaning that explains why it works. The average of two consecutive partial sums $S_n$ and $S_{n+1}$ is $S_n$ plus half the next term. For an alternating series with steadily shrinking terms the limit lies between any two consecutive partial sums, and when the terms change slowly it lies close to the midpoint, because the tail beyond $S_n$ — the next term, minus the one after, plus the one after that — is itself an alternating series whose value is near half of its first term. So “add half the next term” is a first estimate of the tail, and it is a good one.

How good can be read off the figure: the averaged row’s error falls like $1/n^2$ where the partial sums’ fell like $1/n$, because the estimate is wrong only by how fast the terms change, which for $1/(2k + 1)$ is about $1/(2k^2)$. Each further round estimates the error of the previous one in the same way, gaining another power of $1/n$, and Euler’s transformation is all the rounds at once. The rule was not plucked from the air. It is the observation that an alternating tail is worth about half its first term, applied to its own correction again and again.

A slow series made geometric #

Applied to Leibniz’s terms $a_k = 1/(2k + 1)$, the differences can be worked out exactly, and Euler’s rule turns the series into

$$\frac{\pi}{2} = 1 + \frac13 + \frac{1 \cdot 2}{3 \cdot 5} + \frac{1 \cdot 2 \cdot 3}{3 \cdot 5 \cdot 7} + \cdots = \sum_{n \ge 0} \frac{n!}{(2n + 1)!!},$$

where $(2n + 1)!!$ is the product of the odd numbers up to $2n + 1$. Every term is positive, no cancellation is needed, and each term is the previous one multiplied by $n/(2n + 1)$ — a ratio that climbs towards one half.

So the transformed series is a geometric series with ratio one half, give or take a factor that changes slowly: the sixtieth term is 0.115 times $2^{-59}$, and that factor shrinks like $1/\sqrt n$, by Stirling’s formula. This is the sense in which Euler’s rule makes a slow series geometric. The original terms shrink like $1/n$; the transformed terms shrink like $2^{-n}$; and the series everything else is measured against now applies. Each term adds about $\log_{10} 2 = 0.3$ correct digits, which is the slope of the straight line in the first figure.

Nothing has been added and nothing taken away. The transformed series uses exactly the information in the original terms, rearranged by a linear rule. What has changed is the order in which that information is spent: the partial sums spend it on a zigzag that cancels slowly, and Euler’s rule spends it on the cancellation directly. It is a sharper version of the warning in rearranged into any answer, which found that reordering the terms of a slowly converging alternating series can change its sum entirely. Euler’s rule is a recombination that provably does not.

Exact on a geometric error #

The second accelerator starts from a different idea. Suppose the error of a sequence were exactly geometric: $x_n = L + c\,r^n$, with unknown limit $L$, constant $c$ and ratio $r$. Three consecutive terms give three equations in those three unknowns, and solving them gives the limit directly:

$$L = x_{n+2} - \frac{(x_{n+2} - x_{n+1})^2}{x_{n+2} - 2x_{n+1} + x_n}.$$

That is Aitken’s $\Delta^2$ process, published by Alexander Aitken in 1926; the Japanese mathematician Seki Takakazu is said to have used the same device in the seventeenth century to improve an estimate of $\pi$.

On a sequence with geometric error the process is not an approximation at all: any three terms of $2 + 0.7(-0.8)^n$ return 2 exactly, to the last digit the arithmetic carries. On Leibniz’s series the error is not geometric, and the process is only an improvement — a large one, since the error falls like $1/n^3$ afterwards instead of $1/n$, so doubling the terms divides the error by about eight. That is still a power of $n$ rather than a power of a ratio, which is why Aitken once sits in the middle of the first figure. Geometric errors are common elsewhere, though, and there the process shines. Solving an equation by iterating $x_{n+1} = g(x_n)$ produces a sequence whose error shrinks by a factor close to $g'(L)$ at every step — a geometric error, slowly varying — and applying Aitken’s formula to each three iterates and restarting from the result is Johan Steffensen’s method of 1933. It converges quadratically, doubling the correct digits at each round like Newton’s method, without ever computing a derivative. The process was designed for exactly that kind of sequence, and on it the design is rewarded.

The way forward is to treat the error as a sum of several geometric pieces rather than one. Daniel Shanks generalised Aitken’s process in 1955 to fit $k$ geometric terms at once, and Peter Wynn found in 1956 a recursion, the ε-algorithm, that computes Shanks’s estimates for every $k$ in a single triangular table. On an alternating series like Leibniz’s, whose terms are a smooth function of $n$, the error is very nearly a combination of a few geometric terms, and the table converges spectacularly: twelve places from seventeen terms. The method is the same as Aitken’s, with more patience about the shape of the error.

Where Aitken halves the error #

Every accelerator so far has fed on alternation. The zigzag gave Euler something to average and gave Aitken a geometric pattern to fit. A series whose terms are all positive offers neither, and the classic example is Euler’s own most famous sum,

$$\frac{\pi^2}{6} = 1 + \frac14 + \frac19 + \frac{1}{16} + \cdots,$$

whose partial sums fall short of the limit by about $1/n$ — the same rate as Leibniz’s series, but approached from one side, with no oscillation. That it converges at all is the case $p = 2$ of the repair at the boundary, which turned every $1/n^p$ back into a geometric series by grouping terms at doubled spacing; that grouping proves convergence and does nothing to speed it up.

Aitken’s process, given these partial sums, does almost nothing: the shortfall after it is still about $1/n$, merely halved. Fitting a geometric error to a sequence whose error is $1/n$ is fitting the wrong shape, and the fit is consistently off. Wynn’s table, which reached twelve places from seventeen terms of Leibniz’s series, does no better here: given seventeen terms of this one it is still off by $1.2 \times 10^{-2}$, an error that again shrinks only like $1/n$ as terms are added. A sum of geometric pieces is no closer to the shape of a $1/n$ error than a single geometric piece is, and the table’s extra patience buys nothing when the model itself is wrong. What works is fitting the right shape. Lewis Fry Richardson proposed in 1911 the method now called Richardson extrapolation: if the error is known to be a combination of $1/n$, $1/n^2$, $1/n^3$ and so on — which sums of powers read off a staircase explains for sums like this one, through the Euler–Maclaurin formula — then combining the partial sums at $n$, $2n$, $4n$ and so on with suitable weights cancels those terms one at a time. From the partial sums at 5, 10, 20, 40, 80 and 160 terms it reaches $1.7 \times 10^{-11}$, against $6.2 \times 10^{-3}$ for the 160-term partial sum alone.

So the two series with the same rate of convergence call for different accelerators, and each accelerator fails on the other’s series. Euler’s rule, in the form given here, needs the signs to alternate. Aitken’s process is defeated by an error without geometric structure. Richardson’s method needs the form of the error to be known in advance, and applied blindly to a sequence whose error has a different form it cancels terms that are not there.

No rule for every series #

It is natural to hope for a single rule that accelerates every slowly converging sequence. Jean-Paul Delahaye and Bernard Germain-Bonne proved in 1980 that there is none. Their theorem concerns logarithmically convergent sequences, the class that includes the partial sums of $\sum 1/k^2$: no algorithm, however it is built from the terms, accelerates the convergence of every sequence in that class. Given any proposed accelerator, a logarithmically convergent sequence can be built on which it does no better than the original.

The theorem says something about what an accelerator is. Each one is a model of the error — geometric for Aitken, a sum of geometrics for Shanks and Wynn, a power series in $1/n$ for Richardson, a zigzag for Euler — and it succeeds exactly on the sequences whose errors match its model. A sequence can always be built whose error matches none of the models a given method assumes. Acceleration is extrapolation, and extrapolation needs knowledge of what is being extrapolated.

The same moral appears elsewhere in this collection. A sum read from inside evaluated $1 - 1/2 + 1/3 - \cdots$ by continuity from a power series, a method that works because the series is the boundary value of a function. The length round an ellipse found Gauss’s arithmetic–geometric mean doubling its digits at every step where a power series in $h$ needed hundreds of terms. In each case the fast method uses structure the slow one ignores.

How $\pi$ is actually computed #

Nobody computes $\pi$ from Leibniz’s series, accelerated or not, and the reasons say something about what acceleration can and cannot buy. The series is the value at $x = 1$ of the arctangent’s series, $\arctan x = x - x^3/3 + x^5/5 - \cdots$, and at $x = 1$ it is as slow as it can be. John Machin observed in 1706 that $\pi/4 = 4 \arctan\frac15 - \arctan\frac{1}{239}$, and at $x = 1/5$ the same series is geometric from the start, each term about a twenty-fifth of the one before. Machin computed a hundred digits by hand. The geometric behaviour that Euler’s rule had to manufacture is there for free once the series is evaluated at a smaller argument.

The record computations of the last half-century go further. Series of Ramanujan’s type, refined by David and Gregory Chudnovsky in 1988, gain about fourteen digits per term, a geometric ratio near $10^{-14}$. The Gauss–Legendre algorithm of Richard Brent and Eugene Salamin, from 1976, is built on the arithmetic–geometric mean and doubles the number of correct digits at every step, as that mean did for the length round an ellipse. Each is a better series or a better iteration rather than a better accelerator, and the lesson is the one Delahaye and Germain-Bonne made precise: an accelerator can only find structure that is already in the sequence, while a new formula can put better structure there.

What the pictures cannot show #

The figures show four methods on two series, at one choice of terms. They cannot show that Euler’s transformation works on every alternating series with steadily shrinking terms — it does, under a condition on the differences, and the condition is checked here only for Leibniz’s — nor that Wynn’s table always behaves as well as it does here; on series whose terms are not smooth in $n$ it can be erratic, and it divides by differences that can come close to nought. The straight lines are measurements on a finite range, and the slopes they show are slopes of these examples.

Nor can any finite set of experiments show the impossibility theorem. Delahaye and Germain-Bonne’s result is about every possible algorithm, and the figure for $\pi^2/6$ shows only one method failing and one succeeding; the proof constructs, for any method, the sequence it fails on.

Still open: whether the next sum in the family is rational #

Leibniz’s series has a natural sequel, the sum of the reciprocals of the odd squares with alternating signs:

$$G = 1 - \frac19 + \frac{1}{25} - \frac{1}{49} + \cdots = 0.915965594177\ldots,$$

Catalan’s constant. It converges as slowly as Leibniz’s series does, and the accelerators here work on it just as well: Euler’s transformation turns it into a series converging like a power of one half, and its decimal expansion is known to billions of digits. Yet nobody knows whether $G$ is rational. Leibniz’s series sums to a rational multiple of $\pi$, and $\sum 1/k^2$ to a rational multiple of $\pi^2$, as the sine rebuilt from its zeros derives; the alternating sum of odd reciprocal squares has no such expression, and the question of whether it is a fraction at all has stayed open for as long as the constant, named after Eugène Catalan, has been studied.

Acceleration is the reason the question can be asked sharply. It produces the digits — enough of them to rule out any fraction with a denominator below an astronomical bound — and it cannot produce the proof. Knowing a number to a hundred billion places says nothing about whether it is a ratio of two integers larger than that, and a series made geometric is still only a way of computing a number, not a way of knowing what kind of number it is.