Preface

Some series converge very slowly based on standard definition of series convergence. In many cases, such series can be transformed into another series with faster rate of convergence.

Return to computing page for the first course APMA0330
Return to computing page for the second course APMA0340
Return to Mathematica tutorial for the second course APMA0340
Return to the main page for the course APMA0330
Return to the main page for the course APMA0340
Return to Part V of the course APMA0330

Glossary

Series Acceleration

Slowly convergent series and sequences as well as divergent series occur quite frequently in the mathematical treatment of scientific problems. There are a number of methods for squeezing faster convergence out of an already computed sequence of numbers regardless of its origin or application. A special techniques for series acceleration are used for improving the rate of convergence of a series that are quite often applied in numerical analysis. One of the approaches is based on a linear combination of our slowly converging series with one or more series whose sum is known. There is a following collection of convergent series:

\begin{align} \alpha_1 &= \sum_{n\ge 1} \frac{1}{n \left( n+1 \right)} = 1 , \label{EqShanks.1} \\ \alpha_2 &= \sum_{n\ge 1} \frac{1}{n \left( n+1 \right)\left( n+2 \right)} = \frac{1}{4} , \label{EqShanks.2} \\ \alpha_2 &= \sum_{n\ge 1} \frac{1}{n \left( n+1 \right)\left( n+2 \right) \left( n+3 \right)} = \frac{1}{18} , \label{EqShanks.3} \end{align}
and in general
\begin{equation} \alpha_p = \sum_{n\ge 1} \frac{1}{n \left( n+1 \right) \cdots \left( n+p \right)} = \frac{1}{p \cdot p!} . \label{EqShanks.4} \end{equation}
The series are combined term by term and the coefficients in the linear combination chosen to cancel the most slowly converging terms.

Example: Usually, it is not a pleasant task to evaluate an alternating series from numerical point of view because of possible calcelations. We consider almost trivial example to demonstrate the idea of series acceleration. Consider the folloing Maclaurin series:

\[ \ln \left( 1 + x \right) = \sum_{n\ge 1} (-1)^{n+1} \,\frac{x^n}{n} . \]
It converges very slowly as x approaches +1. The rate of convergence may be improved by multiplying both sides of the relation above by a polynomial and adjusting the polynomial coefficients to cancel the more slowly converging portions of the series. Consider the simplest possibility with multiplication both its sides by 1 + s x:
\[ \left( 1 + s\,x \right) \ln \left( 1 + x \right) = \sum_{n\ge 1} (-1)^{n+1} \,\frac{x^n}{n} + s \sum_{n\ge 1} (-1)^{n+1} \,\frac{x^{n+1}}{n} . \]
Combining the two series on the right, term by term, we obtain
\begin{align*} \left( 1 + s\,x \right) \ln \left( 1 + x \right) &= \sum_{n\ge 1} (-1)^{n+1} \left[ \frac{1}{n} - \frac{s}{n-1} \right] x^n \\ &= \sum_{n\ge 1} (-1)^{n+1} \, \frac{n \left( 1 - s \right) -1}{n \left( n+1 \right)} \, x^n \end{align*}
Clearly, if we take s = 1, the n in the numerator disappears and our combined series converges as n-2.

Continuing this process, we find that \( \left( 1 + x \right)^2 \ln \left( 1 + x \right) \) vanishes as n-3 and that \( \left( 1 + x \right)^3 \ln \left( 1 + x \right) \) vanishes as n-4. This allows us to represent the series as a ratio:

\[ \ln \left( 1 + x \right) = \frac{1}{1+x} \left[ x + \sum_{n\ge 2} (-1)^n \,\frac{x^n}{n \left( n-1 \right)} \right] . \]
Such rational approximations may be both compact and accurate.    ■

This section does not provide a full description of all aspects of the acceleration of onvergence and the summation of divergent series. The emphasis of it is on convergence acceleration and summation by means of nonlinear sequence transformations that have proved practical applications.

 

Euler Tansformation

 

Van Wijngaarden transformation

 

Aitken delta-squared process

Let { pn }n ≥ 0 be a sequence which converges to its limit p linearly. That is, there exists a positive number λ such that
\[ \lim_{n\to \infty} \,\frac{\left\vert p_{n+1} - p \right\vert}{\left\vert p_{n} - p \right\vert} = \lambda . \]

In this case, for sufficiently large n, we have

\[ \frac{\left\vert p_{n+1} - p \right\vert}{\left\vert p_{n} - p \right\vert} \approx \lambda . \]
Assume the signs of pn+1 - p and pn - p agree (either both are positive or both are negative) for all n. Then
\[ \frac{p_{n+2} - p}{p_{n+1} - p} \approx \frac{p_{n+1} - p}{p_{n} - p}\qquad \Longleftrightarrow \qquad \left( p_{n+2} - p \right) \left( p_n - p \right) \aaprox \left( p_{n+1} - p \right)^2 . \]
Solving for p, we get
\begin{equation} p \approx \frac{p_n p_{n+2} - p_{n+1}^2}{p_{n+2} - 2\,p_{n+1} + p_n} = p_n - \frac{\left( p_{n+1} - p \right)^2}{p_{n+2} - 2\,p_{n+1} + p_n} . \label{EqAitken.1} \end{equation}
We define a new sequence { qn } as
\begin{equation} q_n = p_n - \frac{\left( p_{n+1} - p \right)^2}{p_{n+2} - 2\,p_{n+1} + p_n} = p_n - \frac{\left( \Delta p_n \right)^2}{\Delta^2 p_n} , \label{EqAitken.2} \end{equation}
where
\Delta p_n = p_{n+1} - p_n , \qquad \Delta^2 p_n = \Delta \left( \Delta p_n \right) = p_{n+2} - 2\,p_{n+1} + p_n , \quad n\ge 0. \]
Algebraically these two formulas are equivalent, but numerically the sequence { qn } converges to p more rapidly (less number of iterations). This methodis called Aitken’s Δ² Method.

 

Shanks Tansformation

For the sequence sn of partial sums

\[ s_n = \sum_{\nu =0}^n a_{\nu} \]
of an infinite series \( \displaystyle \sum_{\nu \ge 0} a_{\nu} , \) Shanks defined the sequence of ratio of two determinantes
\[ e_k \left( s_n \right) = \frac{\Delta_s}{\Delta_1} , \]
where
\[ \Delta_s = \begin{vmatrix} s_n & \ldots & s_{n+k} \\ \Delta s_n & \ldots & \Delta s_{n+k} \\ \vdots & \ddots & \vdots \\ \Delta s_{n+k-1} & \ldots & \Delta s_{n+2k-1} \end{vmatrix} , \qquad \Delta_1 = \begin{vmatrix} 1 & \ldots & 1 \\ \Delta s_n & \ldots & \Delta s_{n+k} \\ \vdots & \ddots & \vdots \\ \Delta s_{n+k-1} & \ldots & \Delta s_{n+2k-1} \end{vmatrix} . \]
Example:     ■

 

Kummer Tansformation

 

  6. Schmidt, J.R., "On the numerical solution of linear simultaneous equations by an iterative method", Philosophical Magazine, 1941, Vol. 32: 369–383. doi: 10.1080/14786444108520797
  7. Shanks, D., Non-linear transformations of divergent and slowly convergent sequences, Journal of Mathematics and Physics, 1955, Vol. 34, pp. 1--42. https://doi.org/10.1002/sapm19553411
  8. Weniger, E.J., Nonlinear sequence transformations for the acceleration of convergence and the summation of divergent series, Computer Physics Reports, 1989, Volume 10, Issues 5–6, December 1989, Pages 189--371. https://doi.org/10.1016/0167-7977(89)90011-7

 

Return to Mathematica page
Return to the main page (APMA0330)
Return to the Part 1 (Plotting)
Return to the Part 2 (First Order ODEs)
Return to the Part 3 (Numerical Methods)
Return to the Part 4 (Second and Higher Order ODEs)
Return to the Part 5 (Series and Recurrences)
Return to the Part 6 (Laplace Transform)
Return to the Part 7 (Boundary Value Problems)