AN ALGORITHM WITH GUARANTEED CONVERGENCE FOR FINDING A ZERO OF A FUNCTION

R. P. BRENT

Abstract

An algorithm is presented for finding a zero of a function which changes sign in a given interval. The algorithm combines linear interpolation and inverse quadratic interpolation with bisection. Convergence is usually superlinear, and is never much slower than for bisection. ALGOL 60 procedures are given.

Comments

Only the Abstract is given here. The full paper appeared as [1]. For similar material see [2, Chapter 4]. Related algorithms are described in [3, 4].

References

1. R. P. Brent, “An algorithm with guaranteed convergence for finding a zero of a function”, Computer J. 14 (1971), 422–425. MR 49#4234, Zbl 231.65046. rpb005.

2. R. P. Brent, Algorithms for Minimization without Derivatives, Prentice-Hall, Englewood Cliffs, New Jersey, 1973, 195 pp. MR 49#4251, CR 15#26544. rpb011.

3. T. J. Dekker, “Finding a zero by means of successive linear interpolation”, in Constructive Aspects of the Fundamental Theorem of Algebra (edited by B. Dejon and P. Henrici), Interscience, New York, 1969.

4. J. H. Wilkinson, Two Algorithms based on Successive Linear Interpolation, Technical Report CS 60, Computer Science Department, Stanford University, Stanford, California, 1967.

Department of Computer Science, Stanford University, Stanford, CA 94305, USA

1991 Mathematics Subject Classification. Primary 65H05; Secondary 65-04, 65G05, 65H20, 68-04, 68Q25.

Key words and phrases. Dekker’s algorithm, bisection, interpolation, superlinear convergence, zeroin, zero-finding.

The author wishes to thank Professors G. E. Forsythe and G. H. Golub for their advice and encouragement, the referee for his helpful comments, and the CSIRO for its support.

Received August 1970, revised March 1971.

Copyright \begin{matrix}c \\ ◯ \end{matrix} 1971, British Computer Society.

Comments \begin{matrix}c \\ ◯ \end{matrix} 1993, R. P. Brent.

rpb005a typeset using AMS-L^{A}TEX