Computing Zeros on a Real Interval through Chebyshev Expansion and Polynomial Rootfinding

Author:
Publisher website
Google Scholar
Abstract
Robust polynomial rootfinders can be exploited to compute the roots on a real interval of a nonpolynomial function f(x) by the following: (i) expand f as a Chebyshev polynomial series, (ii) convert to a polynomial in ordinary, series-of-powers form, and (iii) apply the polynomial rootfinder. (Complex-valued roots and real roots outside the target interval are discarded.) The expansion is most efficiently done by adaptive Chebyshev interpolation with N equal to a power of two, where N is the degree of the truncated Chebyshev series. All previous evaluations of f can then be reused when N is increased; adaption stops when N is sufficiently large so that further increases produce no significant change in the interpolant. We describe two conversion strategies. The "convert-to-powers" method uses multiplication by mildly ill-conditioned matrices to create a polynomial of degree N. The "degree-doubling" strategy defines a polynomial of larger degree 2N but is very well-conditioned. The "convert-to-powers" method, although faster, restricts N to moderate values; this can always be accomplished by subdividing the target interval. Both these strategies allow simultaneous approximation of many roots on an interval, whether simple or multiple, for nonpolynomial f(x).

This publication has 11 references indexed in Scilit: