A rapid robust rootfinder

Author:
Richard I. Shrager

Journal:
Math. Comp. **44** (1985), 151-165

MSC:
Primary 65H05

DOI:
https://doi.org/10.1090/S0025-5718-1985-0771037-8

MathSciNet review:
771037

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: A numerical algorithm is presented for solving one nonlinear equation in one real variable. Given ${F_X}$ with brackets *A* and *B*, i.e., $\operatorname {sign}({F_A}) = - \operatorname {sign}({F_B}) \ne 0$, the algorithm finds a zero of *F*, $A < X < B$. Alternately, a crossover pair is found, i.e., (*X*, *Y*): $\operatorname {sign}({F_X}) = - \operatorname {sign}({F_Y}) \ne 0$ where there is no floating-point number in the system between *X* and *Y*. This feature allows full use of machine precision. Optionally, a tolerance ${\text {TOL}} > 0$ may be given, to permit termination when $|Y - X| < {\text {TOL}}$. The method, once rapid convergence sets in, is alternation of one linear interpolation or extrapolation with one inverse quadratic interpolation. The resulting asymptotic convergence rate is competitive with other methods that refine both brackets and do not require $dF/dX$. Other merits of the algorithm are: robust calculation, efficient three-point interpolation, and superior behavior in bad cases. The algorithm is tested and compared with others.

- Richard P. Brent,
*Algorithms for minimization without derivatives*, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1973. Prentice-Hall Series in Automatic Computation. MR**0339493** - J. C. P. Bus and T. J. Dekker,
*Two efficient algorithms with guaranteed convergence for finding a zero of a function*, ACM Trans. Math. Software**1**(1975), no. 4, 330–345. MR**386254**, DOI https://doi.org/10.1145/355656.355659 - T. J. Dekker,
*Finding a zero by means of successive linear interpolation*, Constructive Aspects of the Fundamental Theorem of Algebra (Proc. Sympos., Zürich-Rüschlikon, 1967) Wiley-Interscience, New York, 1969, pp. 37–48. MR**0256551**
T. J. Dekker, "Correctness proof and machine arithmetic," in - George E. Forsythe, Michael A. Malcolm, and Cleve B. Moler,
*Computer methods for mathematical computations*, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1977. Prentice-Hall Series in Automatic Computation. MR**0458783** - William M. Kahan,
*Personal calculator has key to solve any equation $f(x)=0$*, Hewlett-Packard J.**30**(1979), no. 12, 20–26. MR**574853** - 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**
D. Stevenson & IEEE Task P754 (A working group), "A proposed standard for binary floating-point arithmetic,"

*Performance Evaluation of Numerical Software*(L. D. Fosdick, ed.), Elsevier, New York, 1979.

*Computer*, v. 12, no. 3, 1981, pp. 51-62.

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

Retrieve articles in all journals with MSC: 65H05

Additional Information

Article copyright:
© Copyright 1985
American Mathematical Society