Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



An efficient one-point extrapolation method for linear convergence

Author: Richard F. King
Journal: Math. Comp. 35 (1980), 1285-1290
MSC: Primary 65B99; Secondary 65H05
MathSciNet review: 583505
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: For iteration sequences otherwise converging linearly, the proposed one-point extrapolation method attains a convergence rate and efficiency of 1.618. This is accomplished by retaining an estimate of the linear coefficient from the previous step and using the estimate to extrapolate. For linear convergence problems, the classical Aitken-Steffensen $ {\delta ^2}$-process has an efficiency of just $ \sqrt 2 $, while a recently proposed fourth-order method reaches an efficiency of 1.587. Not only is the method presented here more efficient, but it is also quite straightforward. Examples given are for Newton's method in finding multiple polynomial roots and for locating a fixed point of a nonlinear function.

References [Enhancements On Off] (What's this?)

  • [1] A. C. AITKEN, "On Bernoulli's numerical solution of algebraic equations," Proc. Roy. Soc. Edinburgh, v. 46, 1926, pp. 289-305.
  • [2] H. ESSER, "Eine stets quadratisch konvergente Modifikation des Steffensen-Verfahrens," Computing, v. 14, 1975, pp. 367-369. MR 0413468 (54:1582)
  • [3] A. S. HOUSEHOLDER, The Numerical Treatment of a Single Nonlinear Equation, McGraw-Hill, New York, 1970. MR 0388759 (52:9593)
  • [4] R. F. KING, "A secant method for multiple roots," BIT, v. 17, 1977, pp. 321-328. MR 0488699 (58:8217)
  • [5] R. F. KING, "An extrapolation method of order four for linear sequences," SIAM J. Numer. Anal., v. 16, 1979, pp. 719-725. MR 543964 (80f:65051)
  • [6] A. M. OSTROWSKI, Solution of Equations and Systems of Equations, 2nd ed., Academic Press, New York, 1966. MR 0216746 (35:7575)
  • [7] J. F. STEFFENSEN, "Remarks on iteration," Skandinavisk Aktuarietidskrift, v. 16, 1933, pp. 64-72.
  • [8] J. F. TRAUB, Iterative Methods for the Solution of Equations, Prentice-Hall, Englewood Cliffs, N.J., 1964. MR 0169356 (29:6607)
  • [9] H. VAN DE VEL, "A method for computing a root of a single nonlinear equation, including its multiplicity," Computing, v. 14, 1975, pp. 167-171. MR 0403205 (53:7017)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65B99, 65H05

Retrieve articles in all journals with MSC: 65B99, 65H05

Additional Information

Keywords: Linear convergence, extrapolation, Aitken's $ {\delta ^2}$-process, Steffensen, efficiency, multiple polynomial roots, nonlinear equation, order of convergence
Article copyright: © Copyright 1980 American Mathematical Society

American Mathematical Society