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 Free Access

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?)

    A. C. AITKEN, "On Bernoulli’s numerical solution of algebraic equations," Proc. Roy. Soc. Edinburgh, v. 46, 1926, pp. 289-305.
  • H. Esser, Eine stets quadratisch konvergente Modifikation des Steffensen-Verfahrens, Computing 14 (1975), no. 4, 367–369. MR 413468, DOI
  • A. S. Householder, The numerical treatment of a single nonlinear equation, McGraw-Hill Book Co., New York-Düsseldorf-London, 1970. International Series in Pure and Applied Mathematics. MR 0388759
  • Richard F. King, A secant method for multiple roots, Nordisk Tidskr. Informationsbehandling (BIT) 17 (1977), no. 3, 321–328. MR 488699, DOI
  • Richard F. King, An extrapolation method of order four for linear sequences, SIAM J. Numer. Anal. 16 (1979), no. 5, 719–725. MR 543964, DOI
  • A. M. Ostrowski, Solution of equations and systems of equations, 2nd ed., Pure and Applied Mathematics, Vol. 9, Academic Press, New York-London, 1966. MR 0216746
  • J. F. STEFFENSEN, "Remarks on iteration," Skandinavisk Aktuarietidskrift, v. 16, 1933, pp. 64-72.
  • J. F. Traub, Iterative methods for the solution of equations, Prentice-Hall Series in Automatic Computation, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1964. MR 0169356
  • H. Van de Vel, A method for computing a root of a single nonlinear equation, including its multiplicity, Computing 14 (1975), no. 1-2, 167–171 (English, with German summary). MR 403205, DOI

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 <!– MATH ${\delta ^2}$ –> <IMG WIDTH="24" HEIGHT="23" ALIGN="BOTTOM" BORDER="0" SRC="images/img1.gif" ALT="${\delta ^2}$">-process, Steffensen, efficiency, multiple polynomial roots, nonlinear equation, order of convergence
Article copyright: © Copyright 1980 American Mathematical Society