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," Philos. Mag., 7th Ser., v. 22, 1936, pp. 754-767.
- 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," C.R. Acad. Sci. Paris Sér. A-B, v. 273, 1971, pp. A727-A730.
- 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," Inform. Process. in Japan, v. 15, 1975, pp. 36-40.
- 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
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