Computing real roots of a polynomial in Chebyshev series form through subdivision

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 two families of algorithms for finding the real roots of fN in Chebyshev form. We briefly review existing companion matrix methods—robust, but relatively expensive. We then describe a broad family of new rootfinders employing subdivision. These new methods partition the canonical interval, x∈[−1,1], into Ns subintervals and approximate fN by a low degree Chebyshev interpolant on each subdomain. We derive a rigorous error bound that allows tight control of the error in these local approximations. Because the cost of companion matrix methods grows as the cube of the degree, it is much less expensive for N>50 to calculate the roots of many low degree polynomials, one polynomial on each subdivision, than to directly compute the roots of a single polynomial of high degree.