Enclosing Chebyshev Expansions in Linear Time

We consider the problem of computing rigorous enclosures for polynomials represented in the Chebyshev basis. Our aim is to compare and develop algorithms with a linear complexity in terms of the polynomial degree. A first category of methods relies on a direct interval evaluation of the given Chebyshev expansion in which Chebyshev polynomials are bounded, e.g., with a divide-and-conquer strategy. Our main category of methods that are based on the Clenshaw recurrence includes interval Clenshaw with defect correction (ICDC), and the spectral transformation of Clenshaw recurrence rewritten as a discrete dynamical system. An extension of the barycentric representation to interval arithmetic is also considered that has a log-linear complexity as it takes advantage of a verified discrete cosine transform. We compare different methods and provide illustrative numerical experiments. In particular, our eigenvalue-based methods are interesting for bounding the range of high-degree interval polynomials. Some of the methods rigorously compute narrow enclosures for high-degree Chebyshev expansions at thousands of points in a few seconds on an average computer. We also illustrate how to employ our methods as an automatic a posteriori forward error analysis tool to monitor the accuracy of the Chebfun feval command.