  A wide range of numerical methods exists for computing polynomial
approximations of solutions of ordinary differential equations based on
Chebyshev series expansions or Chebyshev interpolation polynomials. We consider
the application of such methods in the context of rigorous computing (where we
need guarantees on the accuracy of the result), and from the complexity point
of view. It is well-known that the order-n truncation of the Chebyshev
expansion of a function over a given interval is a near-best uniform polynomial
approximation of the function on that interval. In the case of solutions of
linear differential equations with polynomial coefficients, the coefficients of
the expansions obey linear recurrence relations with polynomial coefficients.
Unfortunately, these recurrences do not lend themselves to a direct recursive
computation of the coefficients, owing among other things to a lack of initial
conditions. We show how they can nevertheless be used, as part of a validated
process, to compute good uniform approximations of D-finite functions together
with rigorous error bounds, and we study the complexity of the resulting
algorithms. Our approach is based on a new view of a classical numerical method
going back to Clenshaw, combined with a functional enclosure method.
