An efficient one-point extrapolation method for linear convergence
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.
-  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 0413468, https://doi.org/10.1007/BF02253547
-  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 0488699
-  Richard F. King, An extrapolation method of order four for linear sequences, SIAM J. Numer. Anal. 16 (1979), no. 5, 719–725. MR 543964, https://doi.org/10.1137/0716054
-  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
-  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 0403205, https://doi.org/10.1007/BF02242315
- 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, v. 14, 1975, pp. 367-369. MR 0413468 (54:1582)
- A. S. HOUSEHOLDER, The Numerical Treatment of a Single Nonlinear Equation, McGraw-Hill, New York, 1970. MR 0388759 (52:9593)
- R. F. KING, "A secant method for multiple roots," BIT, v. 17, 1977, pp. 321-328. MR 0488699 (58:8217)
- 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)
- A. M. OSTROWSKI, Solution of Equations and Systems of Equations, 2nd ed., Academic Press, New York, 1966. MR 0216746 (35:7575)
- 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, Englewood Cliffs, N.J., 1964. MR 0169356 (29:6607)
- 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)
Keywords: Linear convergence, extrapolation, Aitken's -process, Steffensen, efficiency, multiple polynomial roots, nonlinear equation, order of convergence
Article copyright: © Copyright 1980 American Mathematical Society