New bounds for the Descartes method
We give a new bound for the number of recursive Subdivisions in the Descartes method for polynomial real root isolation. Our proof uses Ostrowski's theory of normal power series from 1950 which has so far been overlooked in the literature. We combine Ostrowski's results with a theorem of Davenport from 1985 to obtain Our bound. We also characterize normality of cubic polynomials by explicit conditions oil their roots and derive a generalization of one of Ostrowski's theorems. (c) 2005 Elsevier Ltd. All rights reserved.
polynomial real roof isolation descartes rule of signs modified uspensky method recursion tree analysis normal polynomials root separation bounds history of mathematics mobius transformations coefficient sign variations cylindrical algebraic decomposition