Divergent Series Redux
Summation Theory
In 1713, Leibniz said that all divergent series
can be evaluated. Can they?
(2012-07-24)
Sum of a Divergent Geometric Series
How a definite sum can be assigned to a divergent series.
Pour moi, j'avoue que tous les raisonnements
fondés sur les séries
qui ne sont pas convergentes [...]
me paraîtront très suspects, même
quand les résultats s'accorderaient
avec des vérités connues d'ailleurs.
D'Alembert, 1768
[Opusc. math., 5, p. 183 ]
Analytic continuations
can make sense of some divergent series in a consistent way.
Consider the following classic summation formula for the
geometric series, which converges only when the common ratio
z is of a small enough magnitude (i.e., |z| < 1 ) :
1 + z +
z2 +
z3 +
z4 + ... +
zn + ...
= 1 / (1-z)
The right-hand-side always makes sense, unless z = 1.
It's tempting to equate it formally
to the left-hand-side, even when the latter diverges!
This viewpoint is part of a larger
consistent body of knowledge
which is still not mature, in spite of its exploration by generations of great
mathematicians.
The following monstrosities do make sense as "sums" of
divergent series :
1 + 2 + 4 + 8 +
16 + ... + 2n + ...
= -1
1 + 3 + 9 + 27 +
81 + ... + 3n + ...
= - ½
In rings, whenever both sides of such equations are defined,
they are necessarily equal. In p-adic
arithmetic, for example, the above geometric series
converges (only) when z is an integer
which is divisible by the modulus p
(use p=2 and p=3, respectively, for our last two examples).
The following series thus converges in
dyadic, triadic or hexadic integers:
1 + 6 + 36 + 216 +
1296 + ... + 6n + ...
= - 1/5
The respective sums can be given "explicitely" in each of those three cases:
Dyadic:
...001100110011001100110011001100110011001100110011
Triadic:
...012101210121012101210121012101210121012101210121
Hexadic:
...111111111111111111111111111111111111111111111111
Convergence in some ad hoc realms is a
comforting luxury which is rarely available.
There's no such thing in the following case of what's arguably
the simplest divergent series
(Grandi's series, 1703)
which has a long history, starting with an incidental remark of
Leibniz, in 1674
(De Triangulo Harmonico) :
1 - 1 +
1 - 1 +
... + (-1)n + ...
= ½
History of Grandi's series
|
Divergent geometric series
|
1 + 2 + 4 + 8 +...
|
1 - 2 + 4 - 8 +...
Videos :
Adding Past Infinity
&
Taming Infinity
by Henry Reich (Minute Physics)
(2012-07-29)
Desirable Properties of General Summation Methods
Two consistent methods give the same result when both are defined.
A summation method is a recipe that assigns a scalar value to
formal series (i.e.,
vectorial objects formed by an infinite sequence of
scalar coefficients).
The resulting mapping ought to possess a few desirable properties:
1 - Stability (or "translativity") :
Stability expresses compatibility with finite sums by the following rule:
Sn an =
a0 +
Sn an+1
Applied repeatedly, this rule says that you can remove a finite number of
the leading terms from the series, provided you add them back, one by one,
to whatever result
is obtained as the sum of the infinite leftover tail.
Conversely, of course, you can put finitely many new terms
in the series and this will modify the sum of the series accordingly.
The stability property is treacherous.
It turns out that it's really a property of the series
and not of the summation method being used.
Convergent series are stable. So are all
geometric series except the special
geometric series whose common ratio is unity.
As we shall see later on,
1 + 1 + 1 + 1 + 1 + ... = -½
If that series was stable, of sum x, the equation x = 1+x
would hold. It ain't so...
We must also postulate that the sum of a series with only finitely many nonzero
terms is equal to the finite sum of those terms. Combined with the prexious
axiom, the following postulate guarantees this much:
Sn 0 = 0
2 - Regularity :
A summation method is said to be regular if it assigns
to any convergent series its
ordinary
sum (i.e., the limit of its partial sums).
3 - Linearity :
Let's split linearity
into two separate requirements :
- Scalability :
Sn l an =
l
Sn an
- Additivity :
Sn
( an + bn ) =
Sn an +
Sn bn
Linear summation methods are thus linear forms defined over the
vector space of formal series
(in any vector space, a form is
generally defined as a function which takes a vector to a scalar).
4 - Multiplicativity :
The formal series form not only a vector space but
also a ring. We'd like the summation of
series to respect that structure and may want the sum
of a Cauchy product to
equal the product of the sums of its two factors, namely:
( Sn an )
( Sn bn )
=
Sn
( S k ≤ n an-k bk )
The ordinary summation of convergent series is certainly
multiplicative in that sense.
A simple example involving divergent series is the following pair of equations,
where the second series is the Cauchy-square of the first:
1 - 1 +
1 - 1 +
1 - 1 +
1 -
... + (-1)n + ...
= ½
1 - 2 + 3
- 4 + 5
- 6 + ...
+ (-1)n (n+1) + ...
= ¼
Not all divergent series are so well-behaved...
Unstable ones aren't:
1 + 1 +
1 + 1 +
1 + 1 +
1 +
... + 1 + ...
= -1/2
1 + 2 + 3
+ 4 + 5
+ 6 + ...
+ (n+1) + ...
= -1/12
5 - Semi-Continuity :
If the limit of
fn (x) is 1 (unity) for every index n,
as x tends to x0 in some limiting process,
then we have, for the same limiting process:
Sn an
= lim x [
Sn an fn (x) ]
This may be summarized: The sum of the limits is the limit of the sum
(the space of formal series is endowed with
the Tychonoff topology).
Historically, the desired continuity of the summation was rarely evoked explicitely
but it has almost always been assumed by everyone...
The traditional parlance, since 1907,
is to call the coefficients fn (x)
convergence factors whenever they allow the above right-hand side to make
sense in a relevant neighborhood of the limit point for x.
It was Charles N. Moore (1882-1967)
who coined that locution in 1907. It appears
in the title of his
Harvard doctoral dissertation
(1908).
The French equivalent (facteur de convergence)
was used systematically in a new chapter (VI) of the second edition
(1928)
of Borel's " Leçons sur les séries divergentes " (1901)
without any indication of its origin (later claimed,
in print, by Moore himself).
| |
Charles N. Moore |
(2012-08-03)
Summation as a covector (i.e., a continuous linear form).
(In infinitely many dimensions, linear forms could be
discontinuous.)
The formal series (irrespective of their convergences)
form a sequence space.
Using Dirac's notation,
a formal series can be described as a ket :
Sn an
=
Sn an | n >
=
| y >
A continuous and linear
summation method is a bra < s |
Such a bra is a member of the continuous dual
of the aforementioned sequence space
(the algebraic dual consisting of all
linear forms is much larger, by the Axiom of Choice).
Formally, a regular summation can only be
equal to the following bra :
< s | =
Sn < n |
However, that expression is of no practical value,
unlike some of the following methods which describe
< s | better.
Let's define the (non-invertible) shift
operator
Û via:
Û | n > = | n+1 >
If < s | is stable,
we have:
< s | y > =
< s | Û | y >
(2012-08-10)
Summation by Convergence
The only method
Cauchy (1789-1857) would ever recognize.
The sequence of the partial sums of a series is the
sequence whose term of index n (usually starting at n = 0)
is obtained by adding the finitely many terms whose index in the
series does not exceed n.
If that sequence of partial sums
converges to a limit S,
the series itself is said to be convergent
(of sum S).
For convergent series (at least)
we make no typographical distinction beetween a series
and its sum. Thus, we express the above as:
|
Sn an
=
|
|
( |
m |
an |
) |
= |
¥ |
an |
| lim |
S |
S |
| m ® ¥ |
n = 0 |
n = 0 |
The second equation merely expresses the conventional notation for what's expressed
in the right-hand-side (of the first equation) namely the limit
(when it exists) of the partial sums. Nothing else.
When that right-hand-side doesn't make sense, Cauchy
argued that the leftmost expression doesn't either.
Two generations before him, the great Euler
had taken the opposite view, rather freely, with great success
(much later, Ramanujan would do the same).
Cauchy, however, had deep concerns that the lack of explicit rules
for manipulating divergent series made any argument based on them doubtful at best.
So he decided to rule them out!
The pendulum has swung back. Nowadays, divergent series can be handled
with complete analytical rigor.
Both Cauchy and Euler would be pleased...
The following sections will trace the historical path away
from Cauchy's strict point of view, then break free completely...
Summation by convergence is just the simplest
regular summation method,
among mutually consistent ones which apply to divergent series as well.
The other such methods, including those described below, can be classifed into
two broad groups:
- Summations by means.
- Summations by convergence factors.
Sometimes, those two types of approach are known to be equivalent.
(2012-09-09) The Functional Analysis Approach
What the Hahn-Banach extension theorem has to say...
By definition, an absolutely regular summation method is
a continous functional defined for every absolutely convergent series
which coincides with the ordinary summation by convergence.
An absolutely regular summation method need not be
regular.
(For example, some permutation of indices leave unchanged the sum of an absolutely convergent
series but may change the sum of other convergent series and, thus, correspond to a summation
method that is not regular...)
Hahn-Banach extension theorem
|
(2012-08-09) Euler Summation (1746)
The earliest method of summation by convergence factors.
Euler introduced the following definition :
|
Sn an
=
|
|
( |
Sn an xn |
) |
| lim |
| x ® 1- |
Arguably, this is the first use of the postulated continuity of summation.
For example, Euler famously derived the following sum:
1 - 2 + 3
- 4 + 5
- 6 + ...
+ (-1)n (n+1) + ...
= ¼
As the limiting case of this convergent summation, as z tends to 1 on [0,1[
1 - 2 z + 3 z2
- 4 z3 + ...
+ (-1)n+1 (n+1) z n + ...
= 1 / (1+z)2
Abel's limit theorem (1826)
(2012-08-21)
Nörlund summation: Linear, stable & regular (1919)
All Nörlund means are consistent with one another.
Following Neils E. Nörlund (1919) let's consider an infinite sequence of
complex ponderation coefficients, the first of which being nonzero:
c0 ¹ 0 , c1 , c2 ,
c3 , c4 , ... , cn , ...
Let's call C the sequence of the partial sums of the corresponding series:
Cn =
c0 + c1 + c2 +
c3 + c4 + ... + cn
We impose the so-called regularity condition :
-
The positive series of term | cn / Cn | is convergent.
In particular, coefficients in geometric progression are thus ruled out,
if the common ratio is greater than 1. So are coefficient sequences that grow faster than
such a geometric sequence.
For any series an with partial sums
A n = a0 + ... + an
we define:
A'n =
( c0 A n + c1 A n-1 + c2 A n-2
+ ... + cn A 0 ) / C n
This expression is called a Nörlund mean.
If A'n tends to a limit S as n tends to infinity,
then S is called the Nörlund-sum of the series an
or, equivalently, the Nörlund-limit of the sequence A n .
Remarkably, the value of S doesn't depend on the choice of the sequence of coefficients
(with the above regularity restrictions).
Nörlund means (1919)
|
Niels E. Nörlund (1885-1981)
Sur une application des fonctions permutables (N.E. Nörlund, 1919)
On Convergence Factors
for Series Summable by Nörlund Means by Charles N. Moore (1935)
(2012-08-26)
Hausdorff summation: Linear, stable & regular (1921)
Consistent with Nörlund summation.
The question of the consistency of Nörlund and
Hausdorff methods was raised by E. Ullirich and it was answered
(in the affirmative) by
W. Jurkat and A. Peyerimhoff, in 1954.
Hausdorff summation
|
Felix Hausdorff (1868-1942)
The consistency of Nörlund and
Hausdorff methods by W. Jurkat and A. Peyerimhoff (1954)
(2012-08-09)
Abel Summation ()
The divergent series are
the invention of the devil, and
it is a shame to base on them
any demonstration whatsoever...
Niels H. Abel (1802-1829)
The summation method proposed by Abel is:
Abel summation
|
Abelian and tauberian theorems
Tauberian conditions (1897)
|
Hardy-Littlewood tauberian theorem (1914)
|
Alfred Tauber (1866-1942)
(2012-08-09)
Lindelöf Summation (1903)
Lindelöf summation (Wikipedia)
|
Lindelöf summation method
|
Ernst Lindelöf (1870-1946)
(2012-07-29)
Borel Summation (1899)
By Euler's integral of the second kind,
the following identity holds for any nonnegative integer n :
ò0¥
tn/n! e-t dt
= 1
Therefore, the following is a trivial equality between identical series :
Sn an
=
Sn
ò0¥
an
tn/n! e-t dt
In 1899, Emile Borel thus proposed to define
the left-hand-side (which could be a divergent series)
by equating it to the right-hand-side of the following formula,
at least when the new series that is so formed
is a power series of t with an infinite
radius of convergence, which makes
the resulting (improper) integral converge:
Sn an
=
ò0¥
( Sn
an
tn/n! ) e-t dt
The bracketed series on the right-hand-side clearly stands a better chance
of converging than the series on the left-hand-side.
For example, in the case of the geometric series
(an = zn ) the above integrand
becomes exp [(z-1)t] which makes the integral
on the right-hand-side converge when the real part of
z is less than one. We thus have convergence of the Borel furmula
for half the plane, whereas the left-hand-side merely converges on a
disk of unit radius.
Borel summation, however, is best understood as a
way to obtain the sum of a series from the sum of another,
even if the latter is not convergent...
For example, armed with the formula for the sum of a
geometric series
(convergent of not) we can use the Borel summation to
make mincemeat of the following series which Euler
(E247, 1746)
called hypergeometric series of Wallis
(the name is obsolete). He evaluated it in half a dozen
distinct consistent ways.
We now call this "Euler's series".
To Euler himself, hypergeometric numbers were what we now call
factorials
(ironically, the latter term had been coined by Wallis, in 1655).
The locution "hypergeometric series"
is reserved for a creation of Gauss (1812).
1 - 1
+ 2
- 6
+ ... + (-1)n n! + ...
=
ò0¥
( 1 + t ) - 1 e-t dt
That's equal to 0.596347362323194074341078499...
Namely,
e E1(1).
The nonalternating series involves a
Cauchy principal value :
1 + 1 + 2 + 6 + 24
+ ... + n! + ...
=
ò0¥
( 1 - t ) - 1 e-t dt
The numerical value of that is 0.76521907949...
Borel summation
|
1-1+2-6+24-120+...
|
Euler series (2.7)
How Euler Did It:
Divergent Series by Ed Sandifer (MAA Online, June 2006)
(2012-08-28)
Mittag-Leffler Summation Method (1908)
As he was reflecting on the summation of the geometric series
in 1908, Mittag-Leffler proposed the most
widely applicable definition he could think of, at the time
(using the Gamma function) :
|
Sn an
=
|
|
( |
Sn |
| an |
 |
| G(1+en) |
|
) |
| lim |
| e ® 0+ |
For the geometric case (an = zn )
the right-hand-side converges except when z is a real greater than or equal to 1.
Mittag-Leffler summation method
|
Mittag-Leffler star
|
Gösta Mittag-Leffler (1846-1927)
(2012-08-09)
Weierstrass Summation (1842)
Analytic continuation viewed as
a summation method...
This applies not only to formal power series
outside of their disk of convergence but also when each term
of the series is an analytic function of z
indexed by n (the
zeta series being the prime example of that).
(2012-07-28)
Zeta Function Regularization (1916)
An approach pioneered by G.H. Hardy and J.E. Littlewood.
1 + 1 + 1 + 1 +
1 + ...
= - 1/2
1 + 2 + 3 + 4 +
5 + ...
= - 1/12
The unstability of the first of the above series is already known to us.
The unstability of the second can be proved by using the
linearity of summation.
(HINT: Add or subtract the respective sides of the above pair of equations.)
2 + 3 + 4 + 5 + 6 + ...
= - 7/12
0 + 1 + 2 + 3 + 4 + ...
= + 5/12
Zeta function regularization
|
Heat-kernel regularization
|
1 + 1 + 1 + 1 +...
|
1 + 2 + 3 + 4 +...
(2012-11-01)
Mercator Series (1668)
The integral of the geometric series :
z +
z2/2 +
z3/3 +
z4/4 +
... +
zn/n +
... = - Log(1-z)
This series belongs to the history of the
invention of logarithms.
It was discovered independently by several authors:
- Grégoire de Saint-Vincent (1584-1667)
knew about it before 1647.
-
Nicholas Mercator
(né Niklaus Kauffman, 1620-1687)
was the first to publish the series, in his Logarithmotechnia treatise (1668).
-
Isaac Newton (1643-1727) also discussed the series, which is
now called either the Mercator series or the Newton-Mercator series.
The Mercator series converges absolutely for |z| < 1.
For z = -1, it's an alternating series that converges to
ln 2, as shown in 1650 by
Pietro Mengoli
(1626-1686).
For z = 1, we obtain the harmonic series
which was shown to be divergent by Nicolas Oresme,
around 1350.
Wikipedia :
Mercator series
(2012-07-29)
Ramanujan's Irregular Summation (1913)
Assigning the Euler-Masheroni constant
g to the harmonic series.
If I tell you this, you will at once point out to me the lunatic asylum.
Second letter of Ramanujan
to G. H. Hardy (1913)
The harmonic series was first
proved not to converge
by Oresme, around 1350.
Yet, that divergent series can be assigned a finite value canonically:
1 +
1/2 +
1/3 +
1/4 +
1/5 +
... +
1/n + ...
= g
Rammanujan's Summation (pdf)
by Eric Delabaere (December 2001, reported by Vincent Puyhaubert)
Ramanujan summation (Wikipedia)
applied by Alejandro
|
Quora
answer by Anders Kaseorg.
(2012-07-31)
Summations of p-adic Integers
Any p-adic series whose
nth term is a multiple of n! converges !
The following series is clearly convergent
in p-adic integers for any p :
1 + 1 + 2 + 6 + 24 +
120 + ... + n! + ...
That's because the result of the sum modulo pk
is not influenced at all by the terms beyond a certain index m
(namely, the least integer whose factorial is a multiple of pk ).
This is also true if the radix (p) is not prime.
The decadic sum is
...94804323593105039052556442336528920420920314
The 2-adic sum is
...101110010110111111000011111011111101000011010
The same remarks apply to the following series:
1 - 1 + 2
- 6 + 24
- 120 + ...
+ (-1)n n! + ...
That series converges in p-adic integers for any radix p (prime or not)
and the sum is not invertible for some of them, which may be perceived as
its finite "factors". Those are the divisors of the following product:
2 2 .
5 . 13 . 37 . 463 . ...
( A064384 )
(2012-08-03)
Stieltjes Functions & Moments
| |
Thomas Stieljes |
Well before the more general notion of
distributions was devised
(in 1944, by my late teacher Laurent
Schwartz) the Dutch mathematician
Thomas Stieltjes considered measures as generalized
derivatives of functions of bounded variations of a real variable
(such functions are differences of two monotonous bounded functions;
they need not be differentiable, or even continuous).
The moment...
Stieltjes series
|
Stieltjes moment problem
|
Thomas Stieltjes (1856-1894)
(2012-07-30)
Shanks Transformation (1955 & R.J. Schmidt 1941)
The transform of a sequence has the same limit but better convergence.
Motivation :
In a convergent sequence of the form
An = L + u vn
we may extract the limit L from 3 consecutive terms, by eliminating
u and v as follows:
- An-1 = L + u vn-1
- An = L + u vn
- An+1 = L + u vn+1
So,
v = ( An - L )
/ ( An-1 - L )
= ( An+1 - L )
/ ( An - L )
Therefore,
( An - L ) 2
= ( An-1 - L )
( An+1 - L )
which boils down to :
L =
( An-1 An+1 - An2 )
/ ( An-1 + An+1 - 2 An )
Thus, the right-hand-side of that expression forms a sequence whose terms are
expected to be close to the limit of An
even when An is not of the special form quoted above.
This motivates the following introduction of a new sequence Sn ,
which is defined for positive indices whenever the denominator doesn't vanish:
Shanks transform Sn
of the sequence An
Sn =
|
An-1 An+1 - An2
|
|
|
An-1 + An+1 - 2 An
|
|
We observe that Shanks' transformation commutes with translation :
( [An-1+k] [An+1+k] - [An+k] 2 )
/ ( [An-1+k] + [An+1+k] - 2 [An+k] )
= k +
( An-1 An+1 - An2 )
/ ( An-1 + An+1 - 2 An )
Thus, wlg, we may focus on the analysis of sequences whose
limit is zero (the difference between a convergent sequence and its limit is
of this type).
| An |
Shanks Transform of An |
|---|
| vn | 0 |
| 1 / n | 1 / 2n |
| 1 / np | ~ 1 / (p+1)np |
| (-1)n / n | (-1)n+1 / [ 4n (n2 - ½) ] |
| (-1)n / np |
~ (-1)n+1 p / [ 4 np+2 ] |
The table shows that the convergence of a sequence that alternates above and below its limit
is greatly accelerated by Shanks' transformation (the distance to the
limit is essentially divided by the square of the index n).
Shanks's transformation is thus highly recommended for alternating series.
No such luck when the sequence approaches its limit from one side only.
The Shanks transform then offers only marginal improvement (by dividing
the distance to the limit by a constant factor, which is usually 2 or 3).
In that case, the approach described in the next section
is preferred.
Wikipedia :
Shanks transformation
|
Dan Shanks (1917-1996)
Aitken's delta-squared process (1926)
|
Alexander Aitken (1895-1966)
(2012-07-30)
Richardson Extrapolation
(1911 &
Takebe 1722)
Accelerating the convergence of
An = L + k1 / n + k2 / n2 + ...
This (very common) pattern of convergence is
the case where the above transformation of Shanks
has the poorest performance. By optimizing for this pattern, we'll
provide a convergence improvement in cases where the Shanks transformation does not deliver.
The method is similar, we eliminate 2 parameters between 3 equations:
- An-1 (n-1)2 = L (n-1)2
+ k1 (n-1) + k2
- An n 2 = L n 2
+ k1 n
+ k2
- An+1 (n+1)2 = L (n+1)2
+ k1 (n+1) + k2
Subtract twice the second equation from the sum of the other two:
An-1 (n-1)2
- 2
An n 2
+
An+1 (n+1)2
= 2 L
This motivates the definition of the (order 2)
Richardson transformation:
Richardson transform Rn
of the sequence An
| Rn =
|
(n-1)2 An-1
- 2 n2 An +
(n+1)2 An+1
|
|
| 2 |
|
Richardson's transform is a linear map
that commutes with translation.
So, without loss of generality we can restrict the analysis of its performance
to convergent sequences whose limit is zero (consider such a sequence
as the difference between some other sequence and its limit, if you must).
| An |
Richardson Transform of An |
~ |
|---|
| 1 / n | 0 |
| 1 / n 2 | 0 |
| 1 / n 3 |
1 / n(n2-1) |
1 / n 3 |
| 1 / n 4 | (3n2-1) /
n2(n2-1)2 |
3 / n 4 |
| 1 / n 5 | (6n4-3n2+1) /
n3(n2-1)3 |
6 / n 5 |
| 1 / n 6 | (10n6-5n4+4n2-1) /
n4(n2-1)4 |
10 / n 6 |
| 1 / n 7 | (15n8-5n6+10n4-5n2+1) /
n5(n2-1)5 |
15 / n 7 |
| (-1)n / n |
2n (-1)n+1
|
| (-1)n / n 2 |
2 (-1)n+1
|
Thus, unlike the Shanks transform, Richardson's transformation
is absolutely catastrophic when applied to the partial sums of an alternating series.
For a typical nonalternating series, it does a perfect job at the cancellation
of the leading terms it's designed to handle and leaves the next order of magnitude virtually untouched.
However, the bad influence of higher-order error terms is significantly amplified (possibly fatally so).
Takebe (or "Tatebe")
=
Takebe Katahiro
=
Takebe Kenko (1664-1739)
"Our" Takebe was the younger brother of Takebe Kataaki (1661-1716) also a
student of Seki.
Wikipedia :
Richardson extrapolation
|
Lewis Fry Richardson (1881-1953)
(2012-09-29)
On a new acceleration method
(Michon, 2012)
First, let's accelerate the convergence of
An = L + k / (n-a) + ...
The transformations presented in the previous section are somewhat unsatisfactory
because they involve explicitely the particular indexation of the sequence
(the value of n). Clearly, if we tune a convergence acceleration to
a truncated expansion of the above shape, the index n will not be involved
because the presence of the parameter a
makes the optimal result invariant by translation of the index.
Note that, if the correction terms of order 1/n3 and beyond are neglected,
our new target is of the same magnitude as our previous one, with
k1 = k and k2 = ak.
Again, we eliminate 2 parameters between 3 equations:
- An-1 (n - a - 1)
= L (n - a - 1) + k
- An (n - a)
= L (n - a) + k
- An+1 (n - a + 1)
= L (n - a + 1) + k
Subtract twice the second equation from the sum of the other two:
( An-1
+ An+1 - 2 An )
(n - a)
+
( An+1 -
An-1 )
= 0
Let's also subtract the second equation from the third:
( An+1 -
An )
(n - a)
+ An+1 = L
Eliminating (n - a)
between those two equations, we obtain:
L =
[ 2 An-1 An+1
- An (
An-1
+ An+1 ) ]
/ ( An-1
+ An+1 - 2 An )
This motivates the following definition of a new sequence Bn ,
which is valid for positive indices whenever the denominator doesn't vanish:
Transform Bn
of the sequence An
Bn =
|
2 An-1 An+1
- An (
An-1
+ An+1 )
|
|
|
An-1 + An+1 - 2 An
|
|
You may want to note that the Shanks transform of
An is (An+Bn)/2.
As this new transform commutes with translation
(the reader is encouraged to check that directly) we may study its performance, without
loss of generality, for sequences whose limits are zero:
| An |
Bn = |
Bn ~ |
|---|
| 1 / n | 0 |
| 1 / n 2 |
-1 / (3n2-1) |
-1 / 3n 2 |
| 1 / n 3 |
-3n / (6n4-3n2+1) |
-1 / 2n 3 |
| 1 / n 4 | -(6n2+1) /
(10n6-5n4+4n2-1) |
-3 / 5n 4 |
| (-1)n / n |
-2n (-1)n / (2n2-1) |
- (-1)n / n |
| (-1)n / n 2 |
-(2n2+1) (-1)n / (2n4-n2-1) |
- (-1)n / n2 |
| vn |
-vn |
(2012-09-30)
Universal Convergence Acceleration
(Michon, 2012)
For all sequences whose behavior is typical of analytical functions.
Building on the above,
let's introduce a parameter u and define:
A'n =
[ (1-u) An + (1+u) Bn ] / 2
This way, the original sequence is obtained for u = -1,
its Shanks transform for u = 0 and the sequence
B of the previous section for u = 1.
A'n =
|
(1+u) An-1 An+1
- u An (
An-1
+ An+1 ) - (1-u) An2
|
|
|
|
An-1 + An+1 - 2 An
|
=
|
An-1 An+1
- An2
- u
(An - An-1 )
(An+1 - An )
|
|
|
|
An-1 + An+1 - 2 An
|
Or, equivalently:
Parametrized transformation of the sequence An
A'n =
An + (1+u)
|
(An - An-1 )
(An+1 - An )
|
|
|
|
(An - An-1 )
-
(An+1 - An )
|
|
The invariance by translation of this parametrized transform
allows us to study it only for sequences whose limit is zero
(without loss of generality among convergent sequences).
Of course, we'll seek the value of u which provides the best acceleration of convergence.
To use the example already analyzed, if An = L+k/n then
A'n = L + (1-u) k/n
As we already know, the best value of u
is indeed +1 (which yields a constant sequence equal to
the limit L).
Here are a few other cases:
Optimal values of u
| An |
u |
A'n ~ |
|---|
| 1 / n | 1 | 0 |
| 1 / n 2 |
1/2 |
-1 / 12n 4 |
| 1 / n 3 |
1/3 |
-1 / 6n 5 |
| 1 / n 4 |
1/4 |
-1 / 4n 6 |
| 1 / n 5 |
1/5 |
-1 / 3n 7 |
| 1 / n 6 |
1/6 |
-5 / 12n 8 |
| (-1)n / n |
0 |
-(-1)n / 4n 3 |
For the partial sums of alternating series, the Shanks transform
(u=0) is optimal. Otherwise,
we can typically build an optimized sequence as:
An ,
A'n ,
A''n ,
A'''n ,
A''''n ,
A'''''n ,
...
For this, we use a special sequence of different parameters
determined by the expected way the sequence approaches its limit
asymptotically.
Typically (but not always) the original sequence
approaches its limit with a remainder roughly proportional to
1/n and one order of magnitude is gained with each iteration
using the sequence:
u0 = 1 ,
u1 = 1/2 ,
u2 = 1/3 , ...
un+1 = 1 / (1 + 1/un )
The computation is particularly easy to perform using a spreadsheet calculator.
We illustrate this by the following computation to 6 decimal places
of the
sum of the reciprocals of the squares,
based on the first 7 terms in the series
(9 terms are given to show that the last two are useless).
Highlighted in blue are the Shanks transforms of the extreme diagonals.
z(2) =
p2/ 6
= 1.644934066848226436472415...
| n | An |
u0 = 1 | u1 = 1/2 | u2 = 1/3 | u3 = 1/4 |
| 1 | 1.000000 | | 1.644704 | | |
| 2 | 1.250000 | 1.650000 | | 1.644921 | |
| 3 | 1.361111 | 1.646825 | 1.644661 | | 1.644934 |
| 4 | 1.423616 | 1.645833 | 1.644811 | 1.644934 | |
| 5 | 1.463611 | 1.645429 | 1.644868 | 1.644934 | 1.644934 |
| 6 | 1.491389 | 1.645235 | 1.644895 | 1.644934 | |
| 7 | 1.511797 | 1.645130 | 1.644909 | | 1.644934 |
| 8 | 1.527422 | 1.645069 | | 1.644931 | |
| 9 | 1.539768 | | 1.644909 | | |
Although many terms of the basic sequence would be easy to compute in this
didactic example, the method is meant to handle situations where this is not the case.
In theoretical physics (quantum field theory)
and pure mathematics, we may only have a few terms available and only
a fuzzy understanding of the behavior of the sequence whose limit has to be guessed
as accurately as possible.
Incidentally, with standard limited-precision floating-point arithmetic,
the relevant computations presented above will be very poorly approximated
because we keep subtracting nearly-equal quantities.
As a rule of thumb, about half the available precision is wasted.
A 13-digit spreadsheet is barely good enough to reproduce the above
6½-digit table.
Extensions of it would be dominated by the glitches caused by limited precision.
Such pathological behavior is lessened by the approach described next.
(2012-10-02) Accelerating a series by transforming its terms.
The series counterpart of the parametrized transform for sequences.
If the sequence An is the partial sum of the series of term
an ...
(2012-09-30) The next order...
An aborted attempt.
Let's target sequences of the form
An = L
+ k1 / (n-a)
+ k2 / (n-a)2
For the purpose of the following computation, we get rid of indices by
considering four consecutive terms in the sequence (A,B,C,D)
and introducing the quantity x
that differs from (n-a) by some integer.
We seek an expression of the limit L as a function of A,B,C,D
by eliminating the three quantities x,
k1 and k2 between the following
four equations:
- A (x+0) 2 = L (x+0) 2 +
k1 (x+0) + k2
[ 1] [ 1]
- B (x+1) 2 = L (x+1) 2 +
k1 (x+1) + k2
[-3] [-2]
- C (x+2) 2 = L (x+2) 2 +
k1 (x+2) + k2
[ 3] [ 1]
- D (x+3) 2 = L (x+3) 2 +
k1 (x+3) + k2
[-1] [ 0]
The two columns of coefficients yield respectively these combinations:
( A - 3B + 3C - D ) x2 + ( -6B + 12C -6D ) x + ( -3B + 12C - 9D) = 0
( A - 2B + C ) x2 + ( -4B + 4C ) x + ( -2B + 2C ) = 2L x
Eliminating x between those two quadratic equations yields:
|
|
A-3B+3C-D
A-2B+C | | -3B+12C-9D
-2B+2C |
|
|
2 |
= |
|
|
A-3B+3C-D
A-2B+C | | -6B+12C-6D
-2B+4C-2L |
|
|
. |
|
|
-6B+12C-6D
-2B+4C-2L | | -3B+12C-9D
-2B+2C |
|
|
Unfortunately, this is now a quadratic equation in L.
(2012-08-01) Fundamentals of Asymptotics
Only zero is asymptotic to zero.
(2012-10-04) Asymptotic expansions about a limit point.
Asymptotic expansions may or may not be convergent.
 (2012-08-01)
Stirling Approximation & Stirling Series
The Stirling series is a divergent asymptotic series.
Stirling approximation
|
Lanczos approximation
|
Implementation of the Gamma function
|
