Numerical comparisons of nonlinear convergence accelerators

Smith, David A.; Ford, William F.

doi:10.1090/S0025-5718-1982-0645665-1

Numerical comparisons of nonlinear convergence accelerators
HTML articles powered by AMS MathViewer

by David A. Smith and William F. Ford PDF

Math. Comp. 38 (1982), 481-499 Request permission

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.

References

Milton Abramowitz and Irene A. Stegun, Handbook of mathematical functions with formulas, graphs, and mathematical tables, National Bureau of Standards Applied Mathematics Series, No. 55, U. S. Government Printing Office, Washington, D.C., 1964. For sale by the Superintendent of Documents. 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 10.1016/0022-247X(63)90026-X
Carl M. Bender and Tai Tsun Wu, Anharmonic oscillator, Phys. Rev. (2) 184 (1969), 1231–1260. MR 260323

Philos. Mag.

E. Bodewig, A practical refutation of the iteration method for the algebraic eigenproblem, Math. Tables Aids Comput. 8 (1954), 237–240. MR 64479, DOI 10.1090/S0025-5718-1954-0064479-X

C.R. Acad. Sci. Paris Sér. A-B

Claude Brezinski, Computation of the eigenelements of a matrix by the $\varepsilon$-algorithm, Linear Algebra Appl. 11 (1975), 7–20. MR 371044, DOI 10.1016/0024-3795(75)90113-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 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 10.1016/0370-2693(70)90564-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

Inform. Process. in Japan

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 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 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 10.1002/sapm19553411
Barry Simon, Coupling constant analyticity for the anharmonic oscillator. (With appendix), Ann. Physics 58 (1970), 76–136. MR 416322, DOI 10.1016/0003-4916(70)90240-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 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 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 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 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 10.1090/S0025-5718-1956-0084056-6