Approximation by Polynomials
Ker‐I Ko · Birkhäuser Boston eBooks · 1991
The classical Weierstrass approximation theorem states that for every continuous function f on [0, 1] and for any n ≥ 0, there is a real-valued polynomial function φ n such that |f(x) - φ n (x){ ≤ 2-n for all x ∈ [0, 1], In this chapter we investigate the polynomial-time version of the Weierstrass approximation theorem: Is the sequence |φ n } polynomial-time computable, if f is known to be polynomial-time computable? Pour-El and Caldwell [1975] proved that the recursive version of the Weierstrass approximation theorem holds. Shepherd-son [1976] has pointed out the importance of this recursive version of the Weierstrass approximation theorem: It provides a straight-line type finite program for function f. Also, some numerical operations on f, such as integration, can be computed by performing the operation on the approximation polynomials φ n . We show that the weak form of the polynomial-time version of the Weierstrass approximation theorem does hold and so a polynomial-time evaluable straight-line program for φ n can be found in polynomial time if f is itself polynomial-time computable. However, the strong form of the theorem that requires the output of the coefficients of φ n fails. Thus, the integrals of φ n may still be hard to compute.