Abstract
Letf 0(x) be a function of one variable with a simple zero atr 0. An iteration scheme is said to be locally convergent if, for some initial approximationsx 1, ...,x s nearr 0 and all functionsf which are sufficiently close (in a certain sense) tof 0, the scheme generates a sequence {x k} which lies nearr 0 and converges to a zeror off. The order of convergence of the scheme is the infimum of the order of convergence of {x k} for all such functionsf. We study iteration schemes which are locally convergent and use only evaluations off,f′, ...,f [d] atx 1, ...,x k−1 to determinex k, and we show that no such scheme has order greater thand+2. This bound is the best possible, for it is attained by certain schemes based on polynomial interpolation.
Similar content being viewed by others
References
Traub, J. F.: Iterative methods for the solution of equations. New Jersey: Prentice-Hall, Inc. 1964.
Brent, Richard P.: Algorithms for minimization without derivatives. New Jersey: Prentice-Hall, Inc. 1972.
Ostrowski, A. M.: Solution of equations and systems of equations (second edition). New York: Academic Press 1966.
Feldstein, M. Alan, Firestone, Roger M.: Hermite interpolatory iteration theory and parallel numerical analysis. Report, Division of Applied Mathematics, Brown University, Providence, Rhode Island (October 1967).
Brent, Richard P.: The computational complexity of iterative methods for systems of nonlinear equations. Proc. Complexity Symposium. Yorktown Heights. March 1972. Plenum Press (1972).
Ralston, A.: On differentiating error terms. Amer. Math. Monthly70, 187–188 (1963).
Author information
Authors and Affiliations
Additional information
This work was supported (in part) by the Office of Naval Research under contract numbers N0014-69-C-0023 and N0014-71-C-0112.
Rights and permissions
About this article
Cite this article
Brent, R., Winograd, S. & Wolfe, P. Optimal iterative processes for root-finding. Numer. Math. 20, 327–341 (1972). https://doi.org/10.1007/BF01402555
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01402555