On enclosing simple roots of nonlinear equations

Alefeld, G.; Potra, F. A.; Shi, Yixun

doi:10.1090/S0025-5718-1993-1192965-2

On enclosing simple roots of nonlinear equations
HTML articles powered by AMS MathViewer

by G. Alefeld, F. A. Potra and Yixun Shi PDF

Math. Comp. 61 (1993), 733-744 Request permission

Abstract:

In this paper we present two efficient algorithms for enclosing a simple root of the nonlinear equation $f(x) = 0$ in the interval [a, b]. They improve recent methods of Alefeld and Potra by achieving higher efficiency indices and avoiding the solution of a quadratic equation per iteration. The efficiency indices of our methods are 1.5537... and 1.618... , respectively. We show that our second method is an optimal algorithm in some sense. Our numerical experiments show that the two methods of the present paper compare well with the above methods of Alefeld and Potra as well as efficient solvers of Dekker, Brent, and Le. The second method in this paper has the best behavior of all, especially when the termination tolerance is small.

References

G. Alefeld and F. A. Potra, On two higher order enclosing methods of J. W. Schmidt, Z. Angew. Math. Mech. 68 (1988), no. 8, 331–337 (English, with German and Russian summaries). MR 967516, DOI 10.1002/zamm.19880680802
Götz E. Alefeld and Florian A. Potra, Some efficient methods for enclosing simple zeros of nonlinear equations, BIT 32 (1992), no. 2, 334–344. MR 1172194, DOI 10.1007/BF01994885
Ned Anderson and Ȧke Björck, A new high order method of regula falsi type for computing a root of an equation, Nordisk Tidskr. Informationsbehandling (BIT) 13 (1973), 253–264. MR 339474, DOI 10.1007/bf01951936
Kendall E. Atkinson, An introduction to numerical analysis, 2nd ed., John Wiley & Sons, Inc., New York, 1989. MR 1007135
Richard P. Brent, Algorithms for minimization without derivatives, Prentice-Hall Series in Automatic Computation, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1973. MR 0339493
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
R. F. King, Methods without secant steps for finding a bracketed root, Computing 17 (1976), no. 1, 49–57 (English, with German summary). MR 416006, DOI 10.1007/BF02252259
D. Le, An efficient derivative-free method for solving nonlinear equations, ACM Trans. Math. Software 11 (1985), no. 3, 250–262. MR 814340, DOI 10.1145/214408.214416
D. Le, Three new rapidly convergent algorithms for finding a zero of a function, SIAM J. Sci. Statist. Comput. 6 (1985), no. 1, 193–208. MR 773291, DOI 10.1137/0906016
A. M. Ostrowski, Solution of equations in Euclidean and Banach spaces, Pure and Applied Mathematics, Vol. 9, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1973. Third edition of Solution of equations and systems of equations. MR 0359306
F. A. Potra, On $Q$-order and $R$-order of convergence, J. Optim. Theory Appl. 63 (1989), no. 3, 415–431. MR 1031398, DOI 10.1007/BF00939805
J. W. Schmidt, Eingrenzung von Lösungen nichtlinearer Gleichungen durch Verfahren mit höherer Konvergenzgeschwindigkeit, Computing (Arch. Elektron. Rechnen) 8 (1971), 208–215 (German, with English summary). MR 314265, DOI 10.1007/bf02234103