Numerical comparisons of nonlinear convergence accelerators

Authors:
David A. Smith and William F. Ford

Journal:
Math. Comp. **38** (1982), 481-499

MSC:
Primary 65B10; Secondary 65-04

DOI:
https://doi.org/10.1090/S0025-5718-1982-0645665-1

MathSciNet review:
645665

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: As part of a continuing program of numerical tests of convergence accelerators, we have compared the iterated Aitken’s ${\Delta ^2}$ method, Wynn’s $\varepsilon$ algorithm, Brezinski’s $\theta$ algorithm, and Levin’s *u* transform on a broad range of test problems: linearly convergence alternating, monotone, and irregular-sign series, logarithmically convergent series, power method and Bernoulli method sequences, alternating and monotone asymptotic series, and some perturbation series arising in applications. In each category either the $\varepsilon$ algorithm or the *u* transform gives the best results of the four methods tested. In some cases differences among methods are slight, and in others they are quite striking.

- Milton Abramowitz and Irene A. Stegun,
*Handbook of mathematical functions with formulas, graphs, and mathematical tables*, National Bureau of Standards Applied Mathematics Series, vol. 55, For sale by the Superintendent of Documents, U.S. Government Printing Office, Washington, D.C., 1964. MR**0167642** - Richard Bellman and Robert Kalaba,
*A note on nonlinear summability techniques in invariant imbedding*, J. Math. Anal. Appl.**6**(1963), 465–472. MR**148431**, DOI https://doi.org/10.1016/0022-247X%2863%2990026-X - Carl M. Bender and Tai Tsun Wu,
*Anharmonic oscillator*, Phys. Rev. (2)**184**(1969), 1231–1260. MR**260323**
W. G. Bickley &. J. C. P. Miller, "The numerical summation of slowly convergent series of positive terms," - E. Bodewig,
*A practical refutation of the iteration method for the algebraic eigenproblem*, Math. Tables Aids Comput.**8**(1954), 237–240. MR**64479**, DOI https://doi.org/10.1090/S0025-5718-1954-0064479-X
C. Brezinski, "Accélération de suites à convergence logarithmique," - Claude Brezinski,
*Computation of the eigenelements of a matrix by the $\varepsilon $-algorithm*, Linear Algebra Appl.**11**(1975), 7–20. MR**371044**, DOI https://doi.org/10.1016/0024-3795%2875%2990113-5 - E. Gekeler,
*On the solution of systems of equations by the epsilon algorithm of Wynn*, Math. Comp.**26**(1972), 427–436. MR**314226**, DOI https://doi.org/10.1090/S0025-5718-1972-0314226-X - S. Graffi, V. Grecchi, and B. Simon,
*Borel summability: application to the anharmonic oscillator*, Phys. Lett.**32B**(1970), 631–634. MR**332068**, DOI https://doi.org/10.1016/0370-2693%2870%2990564-2 - Robert T. Gregory and David L. Karney,
*A collection of matrices for testing computational algorithms*, Wiley-Interscience A Division of John Wiley & Sons, Inc., New York-London-Sydney, 1969. MR**0253538** - Peter Henrici,
*Elements of numerical analysis*, John Wiley & Sons, Inc., New York-London-Sydney, 1964. MR**0166900**
K. Iguchi, "On the Aitken’s ${\delta ^2}$-process," - Ken Iguchi,
*An algorithm of an acceleration process covering the Aitken $\delta ^{2}$-process*, Information Processing in Japan**16**(1976), 89–93. MR**455267** - David Levin,
*Development of non-linear transformations of improving convergence of sequences*, Internat. J. Comput. Math.**3**(1973), 371–388. MR**359261**, DOI https://doi.org/10.1080/00207167308803075 - R. S. Martin, C. Reinsch, and J. H. Wilkinson,
*Handbook Series Linear Algebra: Householder’s tridiagonalization of a symmetric matrix*, Numer. Math.**11**(1968), no. 3, 181–195. MR**1553959**, DOI https://doi.org/10.1007/BF02161841 - Anthony Ralston,
*A first course in numerical analysis*, McGraw-Hill Book Co., New York-Toronto-London, 1965. MR**0191070** - Daniel Shanks,
*Non-linear transformations of divergent and slowly convergent sequences*, J. Math. and Phys.**34**(1955), 1–42. MR**68901**, DOI https://doi.org/10.1002/sapm19553411 - Barry Simon,
*Coupling constant analyticity for the anharmonic oscillator. (With appendix)*, Ann. Physics**58**(1970), 76–136. MR**416322**, DOI https://doi.org/10.1016/0003-4916%2870%2990240-X - David A. Smith and William F. Ford,
*Acceleration of linear and logarithmic convergence*, SIAM J. Numer. Anal.**16**(1979), no. 2, 223–240. MR**526486**, DOI https://doi.org/10.1137/0716017 - Milton Van Dyke,
*Analysis and improvement of perturbation series*, Quart. J. Mech. Appl. Math.**27**(1974), no. 4, 423–450. MR**468591**, DOI https://doi.org/10.1093/qjmam/27.4.423 - J. H. Wilkinson,
*The use of iterative methods for finding the latent roots and vectors of matrices*, Math. Tables Aids Comput.**9**(1955), 184–191. MR**79833**, DOI https://doi.org/10.1090/S0025-5718-1955-0079833-0 - J. Wimp,
*Toeplitz arrays, linear sequence transformations and orthogonal polynomials*, Numer. Math.**23**(1974), 1–17. MR**359260**, DOI https://doi.org/10.1007/BF01409986 - P. Wynn,
*On a device for computing the $e_m(S_n)$ tranformation*, Math. Tables Aids Comput.**10**(1956), 91–96. MR**84056**, DOI https://doi.org/10.1090/S0025-5718-1956-0084056-6

*Philos. Mag.*, 7th Ser., v. 22, 1936, pp. 754-767.

*C.R. Acad. Sci. Paris Sér. A-B*, v. 273, 1971, pp. A727-A730.

*Inform. Process. in Japan*, v. 15, 1975, pp. 36-40.

Retrieve articles in *Mathematics of Computation*
with MSC:
65B10,
65-04

Retrieve articles in all journals with MSC: 65B10, 65-04

Additional Information

Keywords:
Acceleration of convergence,
iterated Aitken’s <!– MATH ${\Delta ^2}$ –> <IMG WIDTH="31" HEIGHT="23" ALIGN="BOTTOM" BORDER="0" SRC="images/img1.gif" ALT="${\Delta ^2}$">,
<!– MATH $\varepsilon$ –> <IMG WIDTH="15" HEIGHT="18" ALIGN="BOTTOM" BORDER="0" SRC="images/img2.gif" ALT="$\varepsilon$"> algorithm,
<IMG WIDTH="16" HEIGHT="19" ALIGN="BOTTOM" BORDER="0" SRC="images/img7.gif" ALT="$\theta$"> algorithm,
Levin’s transforms,
linear convergence,
logarithmic convergence,
power series,
Fourier series,
power method,
Bernoulli’s method,
asymptotic series,
perturbation series,
numerical tests

Article copyright:
© Copyright 1982
American Mathematical Society