home | index | units | counting | geometry | algebra | trigonometry & functions | calculus
analysis | sets & logic | number theory | recreational | misc | nomenclature & history | physics

Final Answers
© 2000-2014   Gérard P. Michon, Ph.D.

Divergent Series Redux
Cauchy  vs.  Ramanujan

All [ Hardy's ] books gave him some degree of
pleasure, but this one, his last, was his favourite.
[ ... ]  He believed in its value (as well he might).
Preface, by  John E. Littlewood, to the last book of
G.H. Hardy (1877-1947):  "Divergent Series" (1949)
 

Related articles on this site:

Related Links (Outside this Site)

Complex Variables, Contour Integration  by  Joceline Lega  (1998).
Padé and Algebraic Approximants applied to the Quantum Anharmonic Oscillator (pdf)
by  Christopher Orth,  University of Minnesota, Morris  (2005-12-12)
Assigning Values to Divergent Series (pdf)  by  David M. Bressoud  (2006-03-29)
Effective Resummation Methods for an Implicit Resurgent Function  by  Eric Delabaere  (2006)
 
The Everything Seminar:  Sum Divergent Series  by  Matt Noonan  1 | 2 | 3
Adding, Multiplying and the Mellin Transform  by  Greg Muller  (2007).
 
The n-category Café  (discussing papers by  Tom Leinster,  in 2006 & 2007):
Euler characteristic of a category (2006-10-11)
Euler characteristic of a category as the sum of a divergent series (2007-07-09)
 
This Week's Finds in Mathematical Physics  by  John C. Baez :  124 | 125 | 126 (1998)
Euler's Proof that  z(-1) = -1/12 (2003)   |   The Number 24 (2008)
 
Open Problems in Asymptotics Relevant to Sequence Transformations with Special Emphasis to the Summation of Divergent Stieltjes Series
by  Ernst Joachim Weniger,  Universität Regensburg  (1995-03-15).
 
Euler-Maclaurin formula, Bernoulli numbers, Zeta function & analytic continuation  by  Terry Tao  (2010).
Basic Resummation Theory  by  H. Kleinert  and  V. Schulte-Frohlinde.
Resummation, regularization, renormalization  by  Jose Javier Garcia Moreta
 
The Devil's Invention:  Asymptotic, Superasymptotic and
Hyperasymptotic Series
  by  John P. Boyd,  University of Michigan  (1999).
 
Mathsspiel :   Strange case (2006)... Euler-Masheroni (2009)... To sum or not to sum... Definition(s)... Diverging appeal... Borel, Abel, Cesaro, Nörlund: I, II, III.
 
StackExchange:   | Divergent Series (recent) | Apéry |
 
Divergence of perturbation theory:  Steps towards a convergent series.
by  Gerardo Enrique Oleaga Apadula  &  Sergio A. Pernice   (1998)
[ On the applicability of Lebesgue's  dominated convergence theorem ]

Wikipedia :   Power Series   |   Formal Power Series   |   Taylor Series   |   Analytic Continuation
Regularization (Physics)   |   Renormalization   |   Eilenberg-Mazur swindle   |   Telescoping sum
Resummation   |   Divergent series   |   Series acceleration   |   Perturbation theory   |   Asymptotics
Watson's lemma (1918)   |   WKB approximation (Jeffreys, 1923)
Monotone convergence theorem   |   Fatou's lemma (mnemonic, video proof)
Lebesgue's dominated convergence theorem   |   Fatou-Lebesgue theorem
Vitali convergence theorem
 
Encyclopedia of Mathematics :   Summation methods   |   Semi-continuous summation methods
Rogosinski summation (1925)

 
Mathematical Physics  by  Carl M. Bender  (PSI, 2010)
 Carl Bender at the blackboard
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15

Introductory videos :   Adding past infinity  &  Taming infinity  ("Minute Physics" 2011,  by Henry Reich).
One minus one plus one minus one...  by  James Grime  (in "Numberphile" 2013,  by  Brady Haran).
1+2+3+4+5+... = -1/12  (again)  by  Ed Copeland  &  Tony Padilla  (in "Numberphile" 2014).

 
border
border
 Leibniz 
 1646-1716  Leonhard Euler 
 1707-1783  Jean-Le-Rond d'Alembert  
 1717-1783  Louis Augustin Cauchy 
 1789-1857  Niels Abel 
 1802-1829

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  +  z +  z +  z +  ...  +  z +  ...   =   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  +  ...  +  2 +  ...   =   -1
1  +  3  +  9  +  27  +  81  +  ...  +  3 +  ...   =   - ½

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  +  ...  +  6 +  ...   =   - 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) +  ...   =   ½

History of Grandi's series   |   Divergent geometric series   |   1 + 2 + 4 + 8 +...   |   1 - 2 + 4 - 8 +...


(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 + b)   =   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  a)  ( Sn  b)   =   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) +  ...     =   ½
-  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  x in some limiting process, then we have, for the same limiting process:

Sn  a   =   lim xSn  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
Charles N. Moore

For regular summation methods, whenever the series involved on the right-hand-side are convergent and their sums have a finite limit, that limit is the same for all factors of convergence  (this is left as an exercise for the reader)  and can thus be used as a definition of the sum of the series on the left-hand-side if it happens to be divergent.  What the semi-continuity of a summation method ultimately states is that the above equation also holds when sums of divergent series are involved on the right-hand-side...


(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 >

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 >


 Louis Augustin Cauchy 
 1789-1857 (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, a permutation of the indices always leaves unchanged the sum of any absolutely convergent series.  However, it may change the sum of other convergent series and, thus, induce a non-regular summation method.

 Come back later, we're
 still working on this one...

Hahn-Banach extension theorem


 Leonhard Euler
 1707-1783 (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:

-  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[

-  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).

 Come back later, we're
 still working on this one...

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.

 Come back later, we're
 still working on this one...

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   ()

 Niels Henrik Abel  
 1802-1829 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:

 Come back later, we're
 still working on this one...

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)

 Come back later, we're
 still working on this one...

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  a    =    Sn  ò0¥  a 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  a    =    ò0¥  ( Sn  a 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 = z)  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...  Namelye 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
vinculum
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.

 Come back later, we're
 still working on this one...

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).

 Come back later, we're
 still working on this one...


(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

 Come back later, we're
 still working on this one...

Zeta function regularization   |   Heat-kernel regularization   |   1 + 1 + 1 + 1 +...   |   1 + 2 + 3 + 4 +...


 Nicholas Mercator, FRS 
 (1620-1687) (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 ( 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

 Come back later, we're
 still working on this one...

Rammanujan summation (Wikipedia)
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  p).  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  +  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 Stieltjes 
 (1856-1894)
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...

 Come back later, we're
 still working on this one...

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
vinculum
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 )    QED

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
vn0
1 / n1 / 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 2Richardson transformation:

Richardson transform  Rn  of the sequence  An
Rn   =     (n-1)2 An-1  -  2 n2 An  +  (n+1)2 An+1
vinculum
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 /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 transformRichardson'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).

Caution!

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 shape presented here, 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 )
vinculum
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 /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

Thus, the above transform is very effective when the leading error term is harmonic  (1/n).  For other types of convergence, the above table suggest using a linear mix of A and B for best acceleration,  as investigated next.


(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      
vinculum
An-1 + An+1 - 2 An
 
   =    
 
An-1 An+1  -  An2  -  u (An - An-1 ) (An+1 - An )      
vinculum
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 )      
vinculum
(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 /10
  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 p   1/p   (1-p) / 12n p+2  
  (-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...
nAn u0 = 1u1 = 1/2u2 = 1/3u3 = 1/4
11.000000 1.644704  
21.2500001.650000 1.644921 
31.3611111.6468251.644661 1.644934
41.4236161.6458331.6448111.644934 
51.4636111.6454291.6448681.6449341.644934
61.4913891.6452351.6448951.644934 
71.5117971.6451301.644909 1.644934
81.5274221.645069 1.644931 
91.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 ,  then we have  an = An - An-1   (for n≥1)  and the above boils down to:

 
    A'n   =   An   +   (1+u)  
 
an an+1      
vinculum
an - an+1

Subtracting from that value the counterpart for  A'n-1 ,  we obtain:

 
    a'n   =   an   +   (1+u)  
 
an an+1   -   (1+u)   an-1 an      
vinculum vinculum
an - an+1 an-1 - an

 Come back later, we're
 still working on this one...


(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.

 Come back later, we're
 still working on this one...


(2012-10-04)   Asymptotic expansions about a limit point.
Asymptotic expansions may or may not be convergent.

 Come back later, we're
 still working on this one...


 James Stirling (the Venetian) 
 1692-1770 (2012-08-01)   Stirling Approximation  & Stirling Series
The  Stirling series  is a divergent  asymptotic series.

 Come back later, we're
 still working on this one...

Stirling approximation   |   Lanczos approximation   |   Implementation of the Gamma function

border
border
visits since July 24, 2012
 (c) Copyright 2000-2014, Gerard P. Michon, Ph.D.