I’ve encountered some lovely mathematical results in my time, but the Shanks Transformation for nonlinear series acceleration is truly one of the most delightful.
Let’s start by considering a very slowly converging series for based on the Taylor series of the arctangent function,
We define partial sums of this series as the function
I’ll define a little helper for since we’ll use it repeatedly.
const sum = (f) => (n) => {
let sum = 0;
for (let k = 0; k <= n; k++) sum += f(k);
return sum;
}const A = sum((k) => (4 * (k % 2 ? -1 : 1)) / (2 * k + 1))How slowly does this series converge? Very, very slowly!
Achieving error on the order of requires about terms. Until I learned about Shanks transformation, I simply accepted that a series can be correct without being useful.
Upon closer inspection, this is a silly conclusion. Even cursory visual inspection shows that any two consecutive terms bracket the correct answer.
What happens if we just average two consecutive terms?
At a thousand terms, we go from three digits of accuracy to six, so it would seem we’re onto something! In general we get about twice as many digits out of the average of two consecutive terms, but it still takes a lot of terms to get a decent answer.
The essence of Shanks Transformation is to use consecutive terms to extrapolate as far as we can toward the right answer, only with a better choice than our averaging above. So instead we use three consecutive terms to fit a geometric sequence of three parameters, then solve for its limit.
To get the ball rolling, we write our series in the form of a general geometric sequence,
Each term adds one additional multiplicative factor of . The choice of , and are arbitrary, and it just gets absorbed into if we added more or fewer factors of . Solving the first two equations for yields
Performing the same operation on the second and third equations, we have
Cross-multiplying and solving for gives us
We could backtrack and solve for and , but if the sequence is convergent, then so that as , our second equation for gives
In other words, we only care about and not about or We define quantity the Shanks transformation of series and denote it
We can implement this pretty easily as a higher order JavaScript function (although please note that this is a very, very inefficient implementation for the sake of clarity, with many repeated, unnecessary function evaluations!)
const S = (A) => (n) =>
A(n + 1) - (A(n + 1) - A(n)) ** 2 / (A(n + 1) - 2 * A(n) + A(n - 1))The plot below shows the error of and the Shanks transformation . Hover over various points and observe in the plot and table below how much the transformation accelerates convergence. Suddenly the twentieth term yields accuracy the original series takes nearly ten thousand terms to produce!
But wait, you say! The Shanks transformation gives us a new series which presumably converges to the same limit. Can we apply the Shanks transformation to the Shanks transformation and achieve an even better approximation?
Remarkably, the answer is yes! We can simply apply the Shanks transformation over and over, each time yielding a better and better approximation, each successive iteration requiring only two additional terms of .
const Shanks = (A, n = 1) => [...Array(n).keys()].reduce(S, A)Suddenly, we’re at a pretty remarkable state of affairs. Consider the fifth iterate, The very first term is already , and really only depends upon the first nine terms of the original series, the most accurate of which was !
Let’s be clear about what happened here. We took the first eleven terms of the original series. These values only contain one or two digits of accuracy. But they contain a lot of information. By plugging them over and over into the Shanks transformation, we extract that information and obtain seven digits of accuracy!
Hover over results in the table below and observe the values in the table which follows, keeping in mind that the series itself only enters in the terms of itself and that the Shanks transformation introduces no additional information. I’ve plotted up to , though I’ve truncated the series once they run into machine precision and yield the exactly correct answer.
Since no new information enters the picture via the Shanks transformation, the stunning aspect to me is just how much information is contained even in the original, slowly converging, inaccurate series .
Now we just get reckless and greedy. How about the comically divergent series
const B = sum((k) => k * Math.pow(-1, k - 1))The series diverges, as is should.
B(10000)However, the first term of the fourth iterate shows that the Shanks-transformed series converges just fine to .
Shanks(B, 4)(4)Or perhaps the similarly divergent series
const C = sum((k) => Math.pow(-2, k))The divergent series obviously diverges.
C(100)Again though, a single iteration of the Shanks transformation nails it.
Shanks(C)(1)The Shanks transformation doesn’t magically make divergent series converge, and of course divergent series don’t converge! This extraneous “correctness” (by the yardstick of more sophisticated methods) happens because assumed convergence but didn’t actually enforce whether was the limit to which it was converging or from which it was diverging.
Analytic continuation provides more rigorous tools with which to explain these series, as explained by Mathologer in his video Numberphile v. Math: the truth about 1+2+3+…=-1/12. The eponymous Daniel Shanks also explores these specific issues with more precision and rigor in his 1955 paper Non-linear Transformations of Divergent and Slowly Convergent Sequences. It’s a moderately approachable paper for the non-mathematician, though certainly somewhat involved.
I’ll leave this exploration here for now, though I’d highly recommend digging up a copy of the paper and at the very least browsing through some of the more entertaining results!