Computing zeros on a real interval through Chebyshev expansion and polynomial rootfinding

摘要

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 2 N 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). [References: 14]