Vincent’s Theorem Real Root Isolation Method Bisection Method Continued Fraction Method Descartes’ Method Modified Uspensky’s Method
Issue Date:
2008
Publisher:
Institute of Mathematics and Informatics Bulgarian Academy of Sciences
Citation:
Serdica Journal of Computing, Vol. 2, No 1, (2008), 89p-104p
Abstract:
In 2000 A. Alesina and M. Galuzzi presented Vincent’s theorem “from a modern point of view” along with two new bisection methods derived from it, B and C. Their profound understanding of Vincent’s theorem is
responsible for simplicity — the characteristic property of these two methods. In this paper we compare the performance of these two new bisection
methods — i.e. the time they take, as well as the number of intervals they examine in order to isolate the real roots of polynomials — against that of
the well-known Vincent-Collins-Akritas method, which is the first bisection
method derived from Vincent’s theorem back in 1976. Experimental results
indicate that REL, the fastest implementation of the Vincent-Collins-Akritas
method, is still the fastest of the three bisection methods, but the number
of intervals it examines is almost the same as that of B. Therefore, further
research on speeding up B while preserving its simplicity looks promising.
