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 -process has an efficiency of just , 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.

**[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**14**(1975), no. 4, 367–369. MR**0413468****[3]**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****[4]**Richard F. King,*A secant method for multiple roots*, Nordisk Tidskr. Informationsbehandling (BIT)**17**(1977), no. 3, 321–328. MR**0488699****[5]**Richard F. King,*An extrapolation method of order four for linear sequences*, SIAM J. Numer. Anal.**16**(1979), no. 5, 719–725. MR**543964**, 10.1137/0716054**[6]**A. M. Ostrowski,*Solution of equations and systems of equations*, Second edition. Pure and Applied Mathematics, Vol. 9, Academic Press, New York-London, 1966. MR**0216746****[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 Series in Automatic Computation, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1964. MR**0169356****[9]**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**0403205**

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

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

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1980-0583505-8

Keywords:
Linear convergence,
extrapolation,
Aitken's -process,
Steffensen,
efficiency,
multiple polynomial roots,
nonlinear equation,
order of convergence

Article copyright:
© Copyright 1980
American Mathematical Society