New algorithms to estimate the real roots of differentiable functions and polynomials on a closed finite interval

Document Type : Research Article

Author

Department of mathematics, Mahabad Branch, Islamic Azad university, Mahabad, Iran

Abstract

 We propose an algorithm that estimates the real roots of differentiable functions on closed intervals. Then, we extend this algorithm to real differentiable functions that are dominated by a polynomial. For each starting point, our method converges to the nearest root to the right or left hand side of that point. Our algorithm can look for missed roots as well and theoretically it misses no root. Furthermore, we do not find the roots by randomly chosen initial guesses. The iterated sequences in our algorithms converge linearly. Therefore, the rate of convergence can be accelerated considerably to make it comparable to Newton-Raphson and other high-speed methods. We have illustrated our algorithms with some concrete examples. Finally, the pseudo-codes of the related algorithms are presented at the end of this manuscript.

Keywords

References

[1] G. Alefeld, F. Potra, Y. Shi, On enclosing simple roots of nonlinear equations, Math. Comput. 61 (1993) 733–744.
[2] D. Bailey, Krasnoselski's theorem on the real line, Amer. Math. Monthly 81 (1974) 506–507.
[3] D. Borwein, J. Borwein, Fixed point iterations for real functions, J. Math. Anal. Appl. 157 (1991) 112–126.
[4] R.P. Brent, An algorithm with guaranteed convergence for finding a zero of a function, Comput. J. 14 (1971) 422–425.
[5] C. Brezinski, Algorithmes d'Accélération de la Convergence - Étude Numérique, Editions Technip, Paris, 1978.
[6] C. Brezinski, M.R. Zaglia, Generalizations of Aitken's process for accelerating the convergence of sequences, Comput. Appl. Math. 26 (2007) 171–189.
[7] T.R. Chandrupatla, A new hybrid quadratic/bisection algorithm for finding the zero of a nonlinear function without using derivatives, Adv. Eng. Softw. 28 (1977), 145–149.
[8] C. Chidume, Some Geometric Properties of Banach Spaces, Springer, London, 2009.
[9] G.E. Collins, A.G. Akritas, Polynomial real root isolation using Descartes' rule of signs, SYMSAC'76: Proceedings of the third ACM symposium on Symbolic and algebraic computation, (1976) 272–275.
[10] T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, MIT Press, 2009.
[11] J. Delahaye, B. Germain-Bonne, Résultats négatifs en accélération de la convergence, Numer. Math. 35 (1980) 443–457.
[12] J.F. Epperson, An Introduction to Numerical Methods and Analysis, John Wiley & Sons, 2021.
[13] N. Gattal, A. Chibi, An improvement of Steffensen's method for solving nonlinear equations, Glob. J. Pure. Appl. Math. 12 (2016), 935–941.
[14] P. Henrici, Elements of Numerical Analysis, Tech. Rep., John Wiley & Sons, 1964.
[15] B.P. Hillam, A generalization of Krasnoselski's theorem on the real line, Math. Mag. 48 (1975) 167-168.
[16] P. Jain, K. Sethi, Aitken type methods with high efficiency, Trans. A. Razmadze Math. Inst. 172 (2018) 223–237.
[17] H. Khandani, F. Khojasteh, An iterative method for estimation the roots of real-valued functions, Sahand. Commun. Math. Anal. 20 (2023) 95–106.
[18] M. Krasnoselskii, Two observations about the method of successive approximations, Appl. Math. Comput. 10 (1955) 123–127.
[19] Q. Kong, T. Siauw, A. Bayen, Python Programming and Numerical Methods: A Guide for Engineers and Scientists, Academic Press, 2020.
[20] J.M. McNamee, V.Y. Pan, Numerical Methods for Roots of Polynomials - Part II, Academic Press, 2013.
[21] R. Oftadeh, M. Nikkhah-Bahrami, A. Najafi-A, A novel cubically convergent iterative method for computing complex roots of nonlinear equations, Appl. Math. Comput. 217 (2010) 2608–2618.
[22] V.Y. Pan, Solving a polynomial equation: some history and recent progress, SIAM Rev. 39 (1977) 187–220.
[23] C. Ridders, A new algorithm for computing a single root of a real continuous function, IEEE Trans. Circuits Syst. 26 (1979) 979–980.
[24] J.M. Rojas, Book Review: Algorithms in Real Algebraic Geometry by S. Basu, R. Pollack, and M.F. Roy, Springer, 2007.
[25] E. Süli, D.F. Mayers, An Introduction to Numerical Analysis, Cambridge University Press, Cambridge, 2003.
[26] A.J.H. Vincent, Note sur la résolution des équations numériques, J. Math. Pures Appl. 1 (1834) 341–372.
Journal of Mathematical Modeling
Volume 11, Issue 4
December 2023
Pages 631-647

Files

Share

How to cite

Statistics