Numerical comparisons of nonlinear convergence accelerators
Authors:
David A. Smith and William F. Ford
Journal:
Math. Comp. 38 (1982), 481499
MSC:
Primary 65B10; Secondary 6504
MathSciNet review:
645665
Fulltext 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 method, Wynn's algorithm, Brezinski's algorithm, and Levin's u transform on a broad range of test problems: linearly convergence alternating, monotone, and irregularsign 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 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.
 [1]
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
(29 #4914)
 [2]
Richard
Bellman and Robert
Kalaba, A note on nonlinear summability techniques in invariant
imbedding., J. Math. Anal. Appl. 6 (1963),
465–472. MR 0148431
(26 #5938)
 [3]
Carl
M. Bender and Tai
Tsun Wu, Anharmonic oscillator, Phys. Rev. (2)
184 (1969), 1231–1260. MR 0260323
(41 #4951)
 [4]
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. 754767.
 [5]
E.
Bodewig, A practical refutation of the
iteration method for the algebraic eigenproblem, Math. Tables and Other Aids to Computation 8 (1954), 237–240. MR 0064479
(16,288d), http://dx.doi.org/10.1090/S0025571819540064479X
 [6]
C. Brezinski, "Accélération de suites à convergence logarithmique," C.R. Acad. Sci. Paris Sér. AB, v. 273, 1971, pp. A727A730.
 [7]
Claude
Brezinski, Computation of the eigenelements of a matrix by the
𝜖algorithm, Linear Algebra and Appl. 11
(1975), 7–20. MR 0371044
(51 #7265)
 [8]
E.
Gekeler, On the solution of systems of
equations by the epsilon algorithm of Wynn, Math. Comp. 26 (1972), 427–436. MR 0314226
(47 #2778), http://dx.doi.org/10.1090/S0025571819720314226X
 [9]
S.
Graffi, V.
Grecchi, and B.
Simon, Borel summability: application to the anharmonic
oscillator, Phys. Lett. 32B (1970), 631–634. MR 0332068
(48 #10395)
 [10]
Robert
T. Gregory and David
L. Karney, A collection of matrices for testing computational
algorithms, WileyInterscience A Division of John Wiley & Sons,
Inc., New YorkLondonSydney, 1969. MR 0253538
(40 #6752)
 [11]
Peter
Henrici, Elements of numerical analysis, John Wiley &
Sons, Inc., New YorkLondonSydney, 1964. MR 0166900
(29 #4173)
 [12]
K. Iguchi, "On the Aitken's process," Inform. Process. in Japan, v. 15, 1975, pp. 3640.
 [13]
Ken
Iguchi, An algorithm of an acceleration process covering the Aitken
𝛿²process, Information Processing in Japan
16 (1976), 89–93. MR 0455267
(56 #13506)
 [14]
David
Levin, Development of nonlinear transformations of improving
convergence of sequences, Internat. J. Comput. Math.
3 (1973), 371–388. MR 0359261
(50 #11716)
 [15]
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, http://dx.doi.org/10.1007/BF02161841
 [16]
Anthony
Ralston, A first course in numerical analysis, McGrawHill
Book Co., New YorkTorontoLondon, 1965. MR 0191070
(32 #8479)
 [17]
Daniel
Shanks, Nonlinear transformations of divergent and slowly
convergent sequences, J. Math. and Phys. 34 (1955),
1–42. MR
0068901 (16,961e)
 [18]
Barry
Simon, Coupling constant analyticity for the anharmonic oscillator.
(With appendix), Ann. Physics 58 (1970),
76–136. MR
0416322 (54 #4397)
 [19]
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
(82a:65012), http://dx.doi.org/10.1137/0716017
 [20]
Milton
Van Dyke, Analysis and improvement of perturbation series,
Quart. J. Mech. Appl. Math. 27 (1974), no. 4,
423–450. MR 0468591
(57 #8423)
 [21]
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 0079833
(18,154b), http://dx.doi.org/10.1090/S00255718195500798330
 [22]
J.
Wimp, Toeplitz arrays, linear sequence transformations and
orthogonal polynomials, Numer. Math. 23 (1974),
1–17. MR
0359260 (50 #11715)
 [23]
P.
Wynn, On a device for computing the
𝑒_{𝑚}(𝑆_{𝑛}) tranformation, Math. Tables Aids Comput. 10 (1956), 91–96. MR 0084056
(18,801e), http://dx.doi.org/10.1090/S00255718195600840566
 [1]
 M. Abramowitz &. I. A. Stegun (eds.), Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, Nat. Bur. Standards Appl. Math. Series No. 55, Superintendent of Documents, U. S. Government Printing Office, Washington, D. C., 1964. MR 0167642 (29:4914)
 [2]
 R. Bellman &. R. Kalaba, "A note on nonlinear summability techniques in invariant imbedding," J. Math. Anal. Appl., v. 6, 1963, pp. 465472. MR 0148431 (26:5938)
 [3]
 C. M. Bender &. T. T. Wu, "Anharmonic oscillator," Phys. Rev., v. 184, 1969, pp. 12311260. MR 0260323 (41:4951)
 [4]
 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. 754767.
 [5]
 E. Bodewig, "A practical refutation of the iteration method for the algebraic eigenvalue problem," MTAC, v. 8, 1954, pp. 237240. MR 0064479 (16:288d)
 [6]
 C. Brezinski, "Accélération de suites à convergence logarithmique," C.R. Acad. Sci. Paris Sér. AB, v. 273, 1971, pp. A727A730.
 [7]
 C. Brezinski, "Computation of the eigenelements of a matrix by the algorithm," Linear Algebra Appl., v. 11, 1975, pp. 720. MR 0371044 (51:7265)
 [8]
 E. Gekeler, "On the solution of systems of equations by the epsilon algorithm of Wynn," Math. Comp., v. 26, 1972, pp. 427436. MR 0314226 (47:2778)
 [9]
 S. Graffi, V. Grecchi &. B. Simon, "Borel summability: Application to the anharmonic oscillator," Phys. Lett. B, v. 32, 1970, pp. 631634. MR 0332068 (48:10395)
 [10]
 R. T. Gregory &. D. L. Karney, A Collection of Matrices for Testing Computational Algorithms, WileyInterscience, New York, 1969. MR 0253538 (40:6752)
 [11]
 P. Henrici, Elements of Numerical Analysis, Wiley, New York, 1964. MR 0166900 (29:4173)
 [12]
 K. Iguchi, "On the Aitken's process," Inform. Process. in Japan, v. 15, 1975, pp. 3640.
 [13]
 K. Iguchi, "An algorithm of an acceleration process covering the Aitken's process," Inform. Process, in Japan, v. 16, 1976, pp. 8993. MR 0455267 (56:13506)
 [14]
 D. Levin, "Development of nonlinear transformations for improving convergence of sequences," Internat. J. Comput. Math., v. 3, 1973, pp. 371388. MR 0359261 (50:11716)
 [15]
 R. S. Martin, C. Reinsch &. J. H. Wilkinson, "Householder's tridiagonalization of a symmetric matrix," Numer. Math., v. 11, 1968, pp. 181195. MR 1553959
 [16]
 A. Ralston, A First Course in Numerical Analysis, McGrawHill, New York, 1965. MR 0191070 (32:8479)
 [17]
 D. Shanks, "Nonlinear transformations of divergent and slowly convergent sequences," J. Math. and Phys., v. 34, 1955, pp. 142. MR 0068901 (16:961e)
 [18]
 B. Simon, "Coupling constant analyticity for the anharmonic oscillator," Ann. Physics, v. 58, 1970, pp. 76136. MR 0416322 (54:4397)
 [19]
 D. A. Smith &. W. F. Ford, "Acceleration of linear and logarithmic convergence," SIAM J. Numer. Anal., v. 16, 1979, pp. 223240. MR 526486 (82a:65012)
 [20]
 M. Van Dyke, "Analysis and improvement of perturbation series," Quart. J. Mech. Appl. Math., v. 27, 1974, pp. 423450. MR 0468591 (57:8423)
 [21]
 J. H. Wilkinson, "The use of iterative methods for finding the latent roots and vectors of matrices," MTAC, v. 9, 1955, pp. 184191. MR 0079833 (18:154b)
 [22]
 J. Wimp, "Toeplitz arrays, linear sequence transformations, and orthogonal polynomials," Numer. Math., v. 23, 1974, pp. 117. MR 0359260 (50:11715)
 [23]
 P. Wynn, "On a device for computing the transformation," MTAC, v. 10, 1956, pp. 9196. MR 0084056 (18:801e)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
65B10,
6504
Retrieve articles in all journals
with MSC:
65B10,
6504
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718198206456651
PII:
S 00255718(1982)06456651
Keywords:
Acceleration of convergence,
iterated Aitken's ,
algorithm,
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
