Real zeroes of polynomials. (English) Zbl 0533.68038

Collins, G. E.; Loos, R.

Computer algebra, symbolic and algebraic computation, Comput. Suppl. 4, 83-94 (1982).

[For the entire collection see Zbl 0491.00019.]
Let \({\mathcal A}\) be a polynomial over \({\mathcal Z}\), \({\mathcal Q}\) or \({\mathcal Q}(\alpha)\) where \(\alpha\) is a real algebraic number. The problem is to compute a sequence of disjoint intervals with rational endpoints, each containing exactly one real zero of \({\mathcal A}\) and together containing all real zeroes of \({\mathcal A}\). In the paper four algorithms are described and the maximum computation times are given: 1) an algorithm due to Kronecker based on the minimum root separation, 2) Sturm’s algorithm, 3) an algorithm based on Rolle’s theorem due to Collins and Loos and 4) the modified Uspensky algorithm due to Collins and Aritas. For the last algorithm a recursive version with correctness proof is given which appears in print for the first time.

Reviewer: G.Matthiessen

MSC:

68W30	Symbolic computation and algebraic computation
65G30	Interval and finite arithmetic
26C15	Real rational functions

Keywords:

zeroes of polynomials; seperation of zeroes; algorithms; minimum root separation

Citations:

Zbl 0491.00019