On the Maximum Errors of Polynomial Approximations Defined by Interpolation and by Least Squares Criteria

A function f(x) is to be approximated by a polynomial of degree n or less over the interval a ≤ x ≤ b. It is proved that the maximum errors of approximations defined by interpolation and by least squares criteria are within factors, independent of f(x), of the least maximum error that can be achieved. Expressions for these factors are given; they are evaluated for approximations obtained by truncating the expansion of f(x) in Chebyshev polynomials and for approximations obtained by interpolation at the zeros of a Chebyshev polynomial. The resultant numbers are not large: for example, if interpolation is used to evaluate a polynomial approximation of degree 20 it may be guaranteed that the resultant maximum error does not exceed the minimax error by more than a factor of four.