Computing real roots of a polynomial in Chebyshev series form through subdivision with linear testing and cubic solves

An arbitrary polynomial of degree N, fN(x), can always be represented as a truncated Chebyshev polynomial series (“Chebyshev form”). This representation is much better conditioned than the usual “power form” of a polynomial. We describe a new method for finding the real roots of fN(x) in Chebyshev form. The canonical interval, x ∈ [−1, 1], is subdivided into Ns subintervals. Each is tested for zeros using the error bound for linear interpolation. On “zero-possible” intervals, fN is approximated by a cubic polynomial, whose roots are then found by the usual sixteenth century formulas.