TOPICS
Search

Convergence Improvement


The improvement of the convergence properties of a series, also called convergence acceleration or accelerated convergence, 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

sum_(n=1)^(infty)1/(n(n+1))=1
(1)
sum_(n=1)^(infty)1/(n(n+1)(n+2))=1/4
(2)
sum_(n=1)^(infty)1/(n(n+1)(n+2)(n+3))=1/(18)
(3)
sum_(n=1)^(infty)1/(n(n+1)...(n+p))=1/(p·p!).
(4)

Kummer's transformation takes a convergent series

 s=sum_(k=0)^inftya_k
(5)

and another convergent series

 c=sum_(k=0)^inftyc_k
(6)

with known c such that

 lim_(k->infty)(a_k)/(c_k)=lambda!=0.
(7)

Then a series with more rapid convergence to the same value is given by

 s=lambdac+sum_(k=0)^infty(1-lambda(c_k)/(a_k))a_k
(8)

(Abramowitz and Stegun 1972).

The Euler transform takes a convergent alternating series

 sum_(k=0)^infty(-1)^ka_k=a_0-a_1+a_2-...
(9)

into a series with more rapid convergence to the same value to

 s=sum_(k=0)^infty((-1)^kDelta^ka_0)/(2^(k+1)),
(10)

where

 Delta^ka_0=sum_(m=0)^k(-1)^m(k; m)a_(k-m)
(11)

(Abramowitz and Stegun 1972; Beeler et al. 1972).

A general technique that can be used to acceleration converge of series is to expand them in a Taylor series about infinity and interchange the order of summation. In cases where a symbolic form for the Taylor series can be found, this come sometimes even allow the sum over the original variable to be done symbolically. For example, consider the case of the sum

 c=sum_(k=2)^infty1/kln(k/(k-1))=0.7885305659115...
(12)

(OEIS A085361) that arises in the definition of the Alladi-Grinstead constant. The summand can be expanded about infinity to get

c=sum_(k=2)^(infty)k^(-2)+1/2k^(-3)+1/3k^(-4)+...
(13)
=sum_(k=2)^(infty)sum_(n=1)^(infty)1/(nk^(n+1)).
(14)

Interchanging the order of summation then gives

c=sum_(n=1)^(infty)sum_(k=2)^(infty)1/(nk^(n+1))
(15)
=sum_(n=1)^(infty)(zeta(n+1)-1)/n,
(16)

where zeta(n) is the Riemann zeta function, which converges much more rapidly.

A transformations of the form

 T(S_n)=(S_(n+1)S_(n-1)-S_n^2)/(S_(n+1)-2S_n+S_(n-1)),
(17)

where

 S_n=sum_(k=0)^na_k,
(18)

is the nth partial sum of a sequence {a_k}_(k=0)^infty, can often be useful for improving series convergence (Hamming 1986, p. 205). In particular, T(S_n) can be written

T(S_n)=((S_n+a_(n+1))(S_n-a_n)-S_n^2)/(S_n+a_(n+1)-2S_n+S_n-a_n)
(19)
=S_n+(a_na_(n+1))/(a_n-a_(n+1)).
(20)

The application of this transformation can be efficiently carried out using Wynn's epsilon method. Letting epsilon_0(S_n)=S_n, epsilon_(-1)(S_n)=0, and

 epsilon_(r+1)(S_n)=epsilon_(r-1)(S_(n+1))+1/(epsilon_r(S_(n+1))-epsilon_r(S_n))
(21)

for r=1, 2, ... (correcting the typo of Hamming 1986, p. 206). The values of epsilon_(2k)(S_n) are there equivalent to the results of applying k transformations to the sequence S_n (Hamming 1986, p. 206).

Given a series of the form

 S=sum_(n=1)^inftyf(1/n),
(22)

where f(z) is an analytic at 0 and on the closed unit disk, and

 f(z)|_(z->0)=O(z^2),
(23)

then the series can be rearranged to

S=sum_(n=1)^(infty)sum_(m=2)^(infty)f_m(1/n)^m
(24)
=sum_(m=2)^(infty)sum_(n=1)^(infty)f_m(1/n)^m
(25)
=sum_(m=2)^(infty)f_mzeta(m),
(26)

where

 f(z)=sum_(m=2)^inftyf_mz^m
(27)

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 |z|<=1/n_0 for some positive integer n_0, then

 S=sum_(n=1)^(n_0-1)f(1/n)+sum_(m=2)^inftyf_m[zeta(m)-1/(1^m)-...-1/((n_0-1)^m)],
(28)

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


See also

Euler Transform, Lozenge Algorithm, Wilf-Zeilberger Pair, Wynn's Epsilon Method

Explore with Wolfram|Alpha

References

Abramowitz, M. and Stegun, I. 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 et al. Item 120 in Beeler, M.; Gosper, R. W.; and Schroeppel, R. HAKMEM. Cambridge, MA: MIT Artificial Intelligence Laboratory, Memo AIM-239, p. 55, Feb. 1972. http://www.inwap.com/pdp10/hbaker/hakmem/series.html#item120.Flajolet, P. and Vardi, I. "Zeta Function Expansions of Classical Constants." Unpublished manuscript. 1996. http://algo.inria.fr/flajolet/Publications/landau.ps.Hamming, R. W. Numerical Methods for Scientists and Engineers, 2nd ed. New York: Dover, pp. 206-207, 1986.Shanks, D. "Nonlinear Transformations of Divergent and Slowly Convergent Sequences." J. Math. Phys. 34, 1-42, 1955.Sloane, N. J. A. Sequence A085361 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Convergence Improvement

Cite this as:

Weisstein, Eric W. "Convergence Improvement." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/ConvergenceImprovement.html

Subject classifications