Abstract :
An arbitrary polynomial of degree N, fN(x)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 fNfN 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]x∈[−1,1], into NsNs subintervals and approximate fNfN 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>50N>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.
