info prev up next book cdrom email home

Convergence Improvement

The improvement of the convergence properties of a Series, also called Convergence Acceleration, such that a Series reaches its limit to within some accuracy with fewer terms than required before. Convergence improvement can be effected by forming a linear combination with a Series whose sum is known. Useful sums include

$\displaystyle \sum_{n=1}^\infty {1\over n(n+1)}$ $\textstyle =$ $\displaystyle 1$ (1)
$\displaystyle \sum_{n=1}^\infty {1\over n(n+1)(n+2)}$ $\textstyle =$ $\displaystyle {1\over 4}$ (2)
$\displaystyle \sum_{n=1}^\infty {1\over n(n+1)(n+2)(n+3)}$ $\textstyle =$ $\displaystyle {1\over 18}$ (3)
$\displaystyle \sum_{n=1}^\infty {1\over n(n+1)\cdots (n+p)}$ $\textstyle =$ $\displaystyle {1\over p\cdot p!}.$ (4)

Kummer's transformation takes a convergent series
\begin{displaymath}
s=\sum_{k=0}^\infty a_k
\end{displaymath} (5)

and another convergent series
\begin{displaymath}
c=\sum_{k=0}^\infty c_k
\end{displaymath} (6)

with known $c$ such that
\begin{displaymath}
\lim_{k\to\infty} {a_k\over c_k}=\lambda\not=0.
\end{displaymath} (7)

Then a series with more rapid convergence to the same value is given by
\begin{displaymath}
s=\lambda c+\sum_{k=0}^\infty \left({1-\lambda{c_k\over a_k}}\right)a_k
\end{displaymath} (8)

(Abramowitz and Stegun 1972).


Euler's Transform takes a convergent alternating series

\begin{displaymath}
\sum_{k=0}^\infty (-1)^k a_k=a_0-a_1+a_2-\ldots
\end{displaymath} (9)

into a series with more rapid convergence to the same value to
\begin{displaymath}
s=\sum_{k=0}^\infty {(-1)^k\Delta^k a_0\over 2^{k+1}},
\end{displaymath} (10)

where
\begin{displaymath}
\Delta^k a_0=\sum_{m=0}^k\equiv (-1)^m{k\choose m} a_{k-m}
\end{displaymath} (11)

(Abramowitz and Stegun 1972; Beeler et al. 1972, Item 120).


Given a series of the form

\begin{displaymath}
S=\sum_{n=1}^\infty f\left({1\over n}\right),
\end{displaymath} (12)

where $f(z)$ is an Analytic at 0 and on the closed unit Disk, and
\begin{displaymath}
f(z)\vert _{z\to 0}={\mathcal O}(z^2),
\end{displaymath} (13)

then the series can be rearranged to
$\displaystyle S$ $\textstyle =$ $\displaystyle \sum_{n=1}^\infty \sum_{m=2}^\infty f_m\left({1\over n}\right)^m$  
  $\textstyle =$ $\displaystyle \sum_{m=2}^\infty \sum_{n=1}^\infty f_m\left({1\over n}\right)^m=\sum_{m=2}^\infty f_m\zeta(m),$ (14)

where
\begin{displaymath}
f(z)=\sum_{m=2}^\infty f_mz^m
\end{displaymath} (15)

is the Maclaurin Series of $f$ and $\zeta(z)$ is the Riemann Zeta Function (Flajolet and Vardi 1996). The transformed series exhibits geometric convergence. Similarly, if $f(z)$ is Analytic in $\vert z\vert\leq 1/n_0$ for some Positive Integer $n_0$, then


\begin{displaymath}
S=\sum_{n=1}^{n_0-1}f\left({1\over n}\right)+\sum_{m=2}^\inf...
...\left[{\zeta(m)-{1\over 1^m}-\ldots-{1\over(n_0-1)^m}}\right],
\end{displaymath} (16)

which converges geometrically (Flajolet and Vardi 1996). (16) can also be used to further accelerate the convergence of series (14).

See also Euler's Transform, Wilf-Zeilberger Pair


References

Abramowitz, M. and Stegun, C. A. (Eds.). Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, 9th printing. New York: Dover, p. 16, 1972.

Arfken, G. Mathematical Methods for Physicists, 3rd ed. Orlando, FL: Academic Press, pp. 288-289, 1985.

Beeler, M.; Gosper, R. W.; and Schroeppel, R. HAKMEM. Cambridge, MA: MIT Artificial Intelligence Laboratory, Memo AIM-239, Feb. 1972.

Flajolet, P. and Vardi, I. ``Zeta Function Expansions of Classical Constants.'' Unpublished manuscript. 1996. http://pauillac.inria.fr/algo/flajolet/Publications/landau.ps.



info prev up next book cdrom email home

© 1996-9 Eric W. Weisstein
1999-05-26