A rapid robust rootfinder
HTML articles powered by AMS MathViewer
- by Richard I. Shrager PDF
- Math. Comp. 44 (1985), 151-165 Request permission
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.References
- Richard P. Brent, Algorithms for minimization without derivatives, Prentice-Hall Series in Automatic Computation, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1973. 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 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 Performance Evaluation of Numerical Software (L. D. Fosdick, ed.), Elsevier, New York, 1979.
- George E. Forsythe, Michael A. Malcolm, and Cleve B. Moler, Computer methods for mathematical computations, Prentice-Hall Series in Automatic Computation, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1977. 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," Computer, v. 12, no. 3, 1981, pp. 51-62.
Additional Information
- © Copyright 1985 American Mathematical Society
- Journal: Math. Comp. 44 (1985), 151-165
- MSC: Primary 65H05
- DOI: https://doi.org/10.1090/S0025-5718-1985-0771037-8
- MathSciNet review: 771037