September 7, 1999

Approximation by polynomials

Christer O. Kiselman

Contents:

1. Introduction

2. The Weierstrass approximation theorem

3. Estimates for the Bernstein polynomials

4. Weierstrass’ original proof

5. The Stone–Weierstrass approximation theorem

6. Chebyshev’s theorems

7. Approximation by polynomials and trigonometric polynomials 8. The nonexistence of a continuous linear projection

9. Approximation of functions of higher regularity

10. Inverse theorems References

Introductory remarks

These notes comprise the main part of a course on approximation theory presented at Uppsala University in the Fall of 1998, viz. the part on polynomial approximation. The material is mainly classical. As sources I used Cheney [1966], Dzjadyk [1977], Korovkin [1959], and Lorentz [1953], as well as papers listed in the bibliography. The emphasis is on explaining the main ideas behind the most important techniques.

The last part of the course was on rational approximation and is not included here. I followed mainly Cheney [1966, Chapter 5, pp. 150–167]. I also discussed Padé approximation briefly, following Cheney [1966, Chapter 5, pp. 173–177] and the introduction in Rudälv [1998].

I am grateful to Tsehaye Kahsu Araaya for remarks to the manuscript.

1. Introduction

What is approximation theory? Maybe at the end of this course we will be able to give a mature answer to this question. For the time being, let me just sketch a kind of formal framework for the problems we are going to study.

We have a metric space X and we want to approximate a given element x ∈ X by an element a of some subset A of X. The elements of A are “nice” or “tractable” and we want to make the distance between x and a as small as possible: we call this “to make a good approximation of x by elements of A.”

A metric space X is a set X together with a metric d. That d is a metric means that it is a function d: X^{2} → R which satisfies three properties: it is positive definite:

(1.1)  d(x, y) ⩾ 0 for all x, y ∈ X with equality precisely when x = y;

it is symmetric:

(1.2)  d(x, y) = d(y, x) for all x, y ∈ X;

and it satisfies the triangle inequality:

(1.3)  d(x, z) ⩽ d(x, y) + d(y, z) for all x, y, z ∈ X.

Any normed space gives rise to a metric space: we can define the distance between x and y as d(x, y) = ∥x − y∥ or, more generally, as d(x, y) = ∥x − y∥^{α} for any α satisfying 0 < α ⩽ 1.

To any element x of X and any subset A of X we associate the distance d(x, A) from x to A, which by definition is

(1.4)  d(x, A) = inf_{a∈A} d(x, a),  x ∈ X, A ⊂ X.

Obviously we have 0 ⩽ d(x, A) ⩽ +∞ with equality at the second place if and only if A is empty and equality at the first place if and only if a belongs to \overline{A}, the closure of A. So the elements x such that d(x, A) = 0 are those which can be approximated arbitrarily well by nice elements. If d(x, A) > 0 there is a certain unavoidable error.

A very common situation is that we have an increasing sequence (A_{m}) of sets whose union is dense in X, so that d(x, A_{m}) → 0 as m → ∞ for every x ∈ X. Then an interesting question is how fast the convergence is and how the rate of convergence depends on properties of the element x.

It may or may not happen that the infimum in (1.4) is a minimum. In other words, it may happen that there exists an element a, called a best approximant, such that

d(x, a) = d(x, A),

but it may also be the case that

d(x, a) > d(x, A) for all a ∈ A.

In the latter case we are interested in constructing a sequence (a_{j}) of elements of A such that d(x, a_{j}) → d(x, A) as j → ∞. We call such a sequence an approximating sequence. In the first case we may ask if there is a unique best approximant: the set

{a ∈ A; d(x, a) = d(x, A)},

may be empty, have exactly one element, or may have more than one element.

Exercise 1.1. Consider the spaces l_{n}^{p}, i.e., R^{n} with the norm

∥x∥_{p} = (∑ |x_{j}|^{p})^{1/p} when 1 ⩽ p < +∞; ∥x∥_{∞} = max |x_{j}|.

Let A be a closed, convex and nonempty subset of R^{n}. Prove that there is always a unique best approximant when 1 < p < +∞. Prove by examples that there does not necessarily exist a unique closest element in the remaining cases p = 1, +∞. What about 0 < p < 1?

A classical case when we always have a unique best approximant is the following.

Theorem 1.2. Let H be a real or complex Hilbert space and A a nonempty, closed and convex subset of H. Then for any point x ∈ H there is a unique closest point π(x) in A. Any approximating sequence must tend to π(x).

Proof. We may take H as a real Hilbert space. (Why?) After a translation we may assume that x = 0. Let a_{j} be points in A such that d(0, a_{j}) = ∥a_{j}∥ tends to d(0, A) when j → ∞. We note the identity

∥\frac{1}{2}a_{j} + \frac{1}{2}a_{k}∥^{2} + ∥\frac{1}{2}a_{j} − \frac{1}{2}a_{k}∥^{2} = \frac{1}{2}∥a_{j}∥^{2} + \frac{1}{2}∥a_{k}∥^{2},

which is easy to verify if we use the definition ∥x∥ = \sqrt{(x|x)} of the norm in a Hilbert space in terms of the inner product (x|y), x, y ∈ H. Then

\frac{1}{4}∥a_{j} − a_{k}∥^{2} = \frac{1}{2}∥a_{j}∥^{2} + \frac{1}{2}∥a_{k}∥^{2} − ∥\frac{1}{2}a_{j} + \frac{1}{2}a_{k}∥^{2} ⩽ \frac{1}{2}∥a_{j}∥^{2} + \frac{1}{2}∥a_{k}∥^{2} − d(0, A)^{2},

since \frac{1}{2}a_{j} + \frac{1}{2}a_{k} belongs to A in view of the convexity. We see that the right-hand side tends to zero as j, k → ∞. This implies that (a_{j}) is a Cauchy sequence, and it must therefore have a limit in H. The limit cannot depend on the sequence, for if we take two sequences (a_{j}) and (b_{j}) and mix them, the new sequence (a_{0}, b_{0}, a_{1}, b_{1}, a_{2}, ...) must converge by the same argument. We call the limit π(0); by translation we define π(x) ∈ A.

Exercise 1.3. Prove that the mapping π: H → A is continuous; more precisely that

∥π(x) − π(y)∥ ⩽ ∥x − y∥, x, y ∈ H.

Prove also that the set A is contained in a half-space as soon as x ∉ A: in the real case every a ∈ A must satisfy (a − x|π(x) − x) ⩾ ∥π(x) − x∥^{2}. What about the complex case?

Exercise 1.4. Prove that if A is a closed linear subspace, then x−π(x) is orthogonal to π(x). Prove that we get two idempotent mappings π and I − π, and determine all possible relations between the subspaces ker π, ker(I − π), im π, im(I − π).

So Hilbert space is an easy case where the best approximant is unique. However, there are other interesting cases when we can prove uniqueness of the best approximant.

Now we may perhaps dare to say that approximation theory is the study of approximating sequences, best approximants and their uniqueness or nonuniqueness in cases where X is a space of interesting functions, and A is some subspace of nice functions, like polynomials, trigonomentric polynomials,...

2. The Weierstrass approximation theorem

The best starting point for these lectures is the classical Weierstrass^{1} approximation theorem. It says that for any continuous real-valued function f on the interval [0, 1] and any integer k ⩾ 1 there is a polynomial p_{k} such that |f(x) − p_{k}(x)| ⩽ 1/k for all

1Karl Theodor Wilhelm Weierstraß, 1815–1897, my advisor^{5}. x ∈ [0, 1]. However, the degree of p_{k} may have to be much larger than k; we shall return to that story.

Taylor polynomials can serve as approximants—if we are lucky. Given a function with derivatives of all orders at a point a ∈ R, its Taylor^{2} polynomial of degree m at a is

(2.1)  T_{m}(f)(x) = ∑_{0}^{m} f^{(j)}(a)(x − a)^{j}/j!,  x ∈ R, m ∈ N.

If the Taylor polynomials converge to f on some interval ]a − r_{1}, a + r_{2}[ containing a, then f is the restriction to that interval of a holomorphic function defined in a disk in the complex plane, {z ∈ C; |z − a| < max(r_{1}, r_{2})}, thus a rather special function. In particular we see that if f is identically zero near a, then we cannot hope for the Taylor polynomials to converge to f at a point where f is nonzero. To approximate continuous or even general C^{∞} functions we need to find other polynomials.

Theorem 2.1 (The Weierstrass approximation theorem). Let f ∈ C([0, 1]) and let ε be a positive real number. Then there exists a polynomial P such that |f(x)−P (x)| < ε for all x ∈ [0, 1].

There are many generalizations of this theorem. For instance, we could let f be complex-valued, or take values in a real or complex vector space of finite dimension. That is easy. We could let f be a function of several real variables. Then it is also easy to formulate the result. And we could let f be a function of several complex variables. That would require a more profound study, with skillful adaptions of both hypothesis and conclusion. Finally, of course, we may try to let the functions take their values in an infinite-dimensional space.

We start with a trivial identity:

(2.2) 1 = 1^{m} = (x + (1 − x))^{m} = ∑_{0}^{m} \binom{m}{k}x^{k}(1 − x)^{m−k},  x ∈ R, m ∈ N.

Here, as usual,

(2.3)  \binom{m}{k} = \frac{m!}{k!(m − k)!}  m, k ∈ N, k ⩽ m,

is the binomial coefficient.^{3} The formula holds for integers m, k with 0 ⩽ k ⩽ m. It is, however, often convenient to define the coefficient for all k ∈ Z and then set it equal to zero when k is negative or larger than m. Indeed, there is no way you can choose m + 1 apples from m apples. This convention allows us to work more easily with sums, whose limits need not always be indicated.

2Brook Taylor, 1685–1731. 3Read “m choose k” in English, “m super k” in Esperanto, and “m över k” in Swedish.

What could we learn from (2.2) except that 1 can be written in many ways? Well, the function x ↦ \binom{m}{k}x^{k}(1 − x)^{m−k} has a peak at x = k/m. The maximum is equal to

\binom{m}{k} (\frac{k}{m})^{k} (1 − \frac{k}{m})^{m−k} = \binom{m}{k}\frac{k^{k}(m − k)^{m−k}}{m^{m}} ≈ \sqrt{\frac{m}{2πk(m − k)}}.

The approximation holds when k as well as m−k are large, thus for m large and k/m near the middle of [0, 1]. In particular, for k ≈ m/2, the maximum is ≈ \sqrt{2/πm}. We have used here Stirling’s^{4} formula, a simple version of which is

(2.4)  Γ(x) = (x − 1)! ≈ \sqrt{2π}e^{−x}x^{x−1/2},  x ≫ 0.

More precisely, there is an asymptotic expansion valid as |z| tends to +∞ in any sector | arg z| ⩽ π − ε, ε > 0, whose first terms are

(2.5)  \begin{matrix}Γ(z) = (z − 1)! \\ = \sqrt{2π}e^{−z}z^{z−1/2} (1 + \frac{1}{12z} + \frac{1}{288z^{2}} − \frac{139}{51840z^{3}} − \frac{571}{2488320z^{4}} + O(z^{−5})) . \end{matrix}

For large m the function x^{k}(1−x)^{m−k} is pointed. However, it is not very pointed, in the following sense. Let us say that the practical support of a nonnegative function is the set where its value is at least 2^{−7} of its maximum, or perhaps the precise practical support where the value is at least 2^{−10} of the maximum. Then the practical support of x^{k}(1−x)^{m−k} near k = m/2 is an interval of length approximately 3.12/\sqrt{m} (for the precise practical support, the interval is not much longer, viz. 3.72/\sqrt{m}). The terms in the sum define a partition of unity over the interval [0, 1]. However, it is not like the partitions we use in distribution theory when the supports are almost disjoint and one of the function is equal to 1 in a large compact set. In the sum (2.2) the supports overlap massively; using the notion of practical support again we see that 3.12\sqrt{m} of the terms overlap near x = 1/2. See the figures.

Anyway, it is reasonable to expect that

∑ f(k/m)\binom{m}{k}x^{k}(1 − x)^{m−k}, x ∈ R, m ∈ N^{∗} = N ∖ \{0\},

which is a polynomial of degree m, would be a good approximation to f on [0, 1]. So let us define

(2.6)  B_{m}(f)(x) = ∑_{0}^{m} f(k/m)\binom{m}{k}x^{k}(1 − x)^{m−k},  x ∈ R, m ∈ N^{∗}.

We shall call B_{m}(f) the Bernstein^{5} polynomial of f of degree m.

4James Stirling, 1692–1770. 5Sergej Natanovič Bernstein, 1880–1968.

Figure 1. The polynomials p_{m,k}(x) = \binom{m}{k}x^{k}(1 − x)^{m−k} for m = 10, k = 0, 1, ..., 10.

We remark that the functions x ↦ \binom{m}{k}x^{k}(1 − x)^{k} all have the same integral over [0, 1], viz. 1/(m + 1). It follows that the integral of B_{m}(f) is a Riemann sum for f:

(2.7)  ∫_{0}^{1} B_{m}(f)(x)dx = \frac{1}{m + 1} ∑_{0}^{m} f(k/m).

Proposition 2.2. The mapping B_{m}: [0, 1]^{R} → 𝒫_{m} maps the real-valued functions on [0, 1] into the space 𝒫_{m} of polynomials of degree at most m, m ∈ N^{∗}. It is linear. It is increasing, i.e., B_{m}(f) ⩽ B_{m}(g) if f ⩽ g; equivalently, it is positive, i.e., B_{m}(f) ⩾ 0 if f ⩾ 0. Moreover B_{m}(1) = 1 and B_{m}(x)(x) = x. Finally,

(2.8)  B_{m}(x^{2})(x) = x^{2} + \frac{1}{m}x(1 − x),  x ∈ R, m ⩾ 1.

Thus the restriction of B_{m} to the affine functions is the identity in 𝒫_{1}. The restriction of B_{m} to 𝒫_{2} is not exactly the identity, since if p(x) = a_{0} +a_{1}x+a_{2}x^{2} is a polynomial of degree at most 2, then

(2.9)  B_{m}(p)(x) = a_{0} + (a_{1} + \frac{a_{2}}{m} ) x + (a_{2} − \frac{a_{2}}{m} ) x^{2}.

Thus B_{m} maps P_{2} into itself and differs from the identity by an error which is nowhere larger than |a_{2}|(4m)^{−1} and in particular tends to zero as m → +∞. Proof. The linearity and positivity of B_{m} is clear. The fact that B_{m}(1) = 1 is just the identity (2.2) which was the starting point of these deliberations. To see that Figure 2. The polynomials p_{m,k}(x) = \binom{m}{k}x^{k}(1 − x)^{m−k} for m = 100, k = 49, 50. (Illustrating massive overlapping.)

B_{m}(x)(x) = x we perform the following calculation.

B_{m}(x) = ∑_{1}^{m} \binom{m}{k}\frac{k}{m}x^{k}(1 − x)^{m−k} = ∑_{1}^{m} \binom{m − 1}{k − 1}x^{k}(1 − x)^{m−k}

= x ∑_{0}^{m−1} \binom{m − 1}{j}x^{j}(1 − x)^{m−1−j} = xB_{m−1}(1) = x, m ⩾ 2.

The calculation supposes that m ⩾ 2, since B_{m−1} is not defined otherwise; however, it is easy to verify that B_{1}(x) = x separately.

Finally, for f(x) = x^{2} we first perform the same trick as in the case of B_{m}(x) above to get

B_{m}(x^{2}) = ∑_{1}^{m} \binom{m}{k}\frac{k^{2}}{m^{2}} x^{k}(1 − x)^{m−k} = x ∑_{0}^{m−1} \frac{j + 1}{m}\binom{m − 1}{j}x^{j}(1 − x)^{m−1−j}.

Figure 3. The polynomials p_{m,k}(x) = \binom{m}{k}x^{k}(1 − x)^{m−k} for m = 1000, k = 499, 500. (They are indistinguishable.)

Following Dzjadyk [1977:317] we now divide the last expression into two: the first with j, the second with 1, thus B_{m}(x^{2}) is equal to

x\frac{m − 1}{m} ∑_{1}^{m−1} \frac{j}{m − 1}\binom{m − 1}{j}x^{j}(1 − x)^{m−1−j} + \frac{x}{m} ∑_{0}^{m−1} \binom{m − 1}{j}x^{j}(1 − x)^{m−1−j}

= x(1 − \frac{1}{m})B_{m−1}(x)(x) + \frac{x}{m}B_{m−1}(1)(x) = x^{2} + \frac{1}{m}x(1 − x), m ⩾ 2.

Here we need m ⩾ 2 to give a sense to B_{m−1}. However, B_{m}(x^{2})(x) = x = x^{2} + \frac{1}{m}x(1 − x) for m = 1, so (2.8) holds also then. This proves the proposition. Proof of Theorem 2.1. This proof is due to Bernstein [1912]. Let f be any continuous function on [0, 1] and let p be a polynomial of degree 2 which majorizes f. Then B_{m}(f) ⩽ B_{m}(p) = p + a_{2}x(1 − x)/m ⩽ p + |a_{2}|/(4m), where a_{2} is the coefficient for x^{2} in p. So p + |a_{2}|/(4m) is a majorant of B_{m}(f). Now a continuous function is the infimum of all its majorants of degree 2. More precisely, if a number ε > 0 is given, we can find a δ > 0 such that f(x) ⩽ f(x_{0}) + ε when x and x_{0} are any two points with |x − x_{0}| ⩽ δ, for f is uniformly continuous. Also f is bounded on [0, 1], say |f| ⩽ M. Then p(x) = f(x_{0}) + ε + a_{2}|x − x_{0}|^{2} is a majorant of f if we choose a_{2} = 2M/δ^{2}. Taking the Bernstein polynomials of f and p we get

B_{m}(f) ⩽ B_{m}(p) = p + \frac{a_{2}}{m} x(1 − x) ⩽ p + \frac{a_{2}}{4m}.

At the point x_{0} the values are

B_{m}(f)(x_{0}) ⩽ p(x_{0}) + \frac{a_{2}}{4m} = f(x_{0}) + ε + \frac{a_{2}}{4m}.

For large m we get

(2.10)  B_{m}(f)(x_{0}) ⩽ f(x_{0}) + 2ε.

In fact, we have to choose m ⩾ \frac{1}{4}a_{2}ε^{−1} = \frac{1}{2}Mδ^{−2}ε^{−1}. Therefore (2.10) holds for a large m and for all x_{0}. By the same argument we get an estimate from below: B_{m}(f) ⩾ f − 2ε. Thus |B_{m}(f) − f| ⩽ 2ε and the theorem is proved.

While we are at it, we can easily generalize the proof to other operators than B_{m}.

Theorem 2.3. Let A_{m}: C(I) → C(I), m ∈ N^{∗}, where I = [0, 1], be positive linear operators such that A_{m}(1) = 1, A_{m}(x)(x) = x+α_{m}(x), and A_{m}(x^{2})(x) = x^{2}+β_{m}(x). Then (2.11)

∥A_{m}(f) − f∥_{∞} ⩽ ω(δ) (1 + δ^{−2} sup_{y∈I} |β_{m}(y) − 2yα_{m}(y)|) , δ > 0, m ∈ N^{∗},

where ω is the modulus of continuity of f:

ω(δ) = sup_{x,y∈I} (|f(x) − f(y)|; |x − y| ⩽ δ).

Proof. When |x − y| ⩽ δ we have f(x) − f(y) ⩽ ω(δ) by definition. When |x − y| > δ we can divide the interval between x and y into not more than 1 + |x − y|/δ intervals of length at most δ, so that

f(x) − f(y) ⩽ ω(δ)(1 + |x − y|/δ).

Thus in all cases

f(x) − f(y) ⩽ ω(δ)(1 + δ^{−2}(x − y)^{2}), x, y ∈ I, δ > 0.

Here the right-hand side is a polynomial of degree at most two in x for fixed y, so if we apply the mapping A_{m} in the variable x we obtain

A_{m}(f)(x) − f(y) ⩽ ω(δ)[1 + δ^{−2}(x^{2} + β_{m}(x) − 2y(x + α_{m}(x)) + y^{2})]. We now choose x = y and get

A_{m}(f)(y) − f(y) ⩽ ω(δ)(1 + δ^{−2}(β_{m}(y) − 2yα_{m}(y)))

⩽ ω(δ)(1 + δ^{−2} sup_{y∈I} |β_{m}(y) − 2yα_{m}(y)|).

We now apply this result to −f to get an inequality in the other direction. Combining the two we get (2.11) as claimed.

Corollary 2.4. For any continuous function f with modulus of continuity ω, the Bernstein polynomials B_{m}(f) satisfy

∥B_{m}(f) − f∥_{∞} ⩽ \frac{5}{4}ω(1/\sqrt{m}), m ∈ N^{∗}.

Proof. With the notation of the theorem we have in this case α_{m} = 0, |β_{m}(x)| ⩽ (4m)^{−1}, so that the right-hand side of (2.11) becomes ω(δ)(1 + (4mδ^{2})^{−1}). We just have to choose δ = 1/\sqrt{m} to complete the proof.

Exercise 2.5. We have seen that ∥B_{m}(f) − f∥_{∞} ⩽ Cω(1/\sqrt{m}), where the best constant C is at most 5/4. Prove that the best constant cannot be smaller than one. Thus 1 ⩽ C ⩽ 5/4; it appears that the exact value of C is not known.

The Bernstein polynomials do not give the best possible approximation: we shall see that there are polynomials P of degree m such that ∥P − f∥_{∞} ⩽ Cω(1/m).

Exercise 2.6. Prove that if A_{m}, m ∈ N^{∗}, are positive linear operators such that A_{m}(1)(x) = 1 + α_{m}(x), A_{m}(x)(x) = x + β_{m}(x), and A_{m}(x^{2})(x) = x^{2} + γ_{m}(x), where α_{n}, β_{m}, and γ_{m} tend to zero uniformly as m → ∞, then A_{m}(f) → f uniformly for all f ∈ C(I).

Exercise 2.7. Prove that B_{m}(f)(x) → f(x) if f is bounded on [0, 1] and continuous only at the point x.

Exercise 2.8. Prove the formula B_{m}(f)′ = B_{m−1}(g), where

g(x) = m [f(\frac{m−1}{m}x + \frac{1}{m}) − f(\frac{m−1}{m}x)] ,

a difference quotient of f adjusted so that only values of the argument in [0, 1] appear. Deduce that if f is a polynomial of degree at most q, then B_{m}(f) is of degree at most q (and thus of degree ⩽ min(m, q)). Generalize to higher order difference quotients.

Exercise 2.9. Now do everything in several variables: define for f ∈ C([0, 1]^{n}),

B_{m}(f)(x) = ∑_{k∈N^{n}} f(k/m)\binom{m}{k}x^{k}(1 − x)^{m−k}, x ∈ R^{n}, m ∈ (N^{∗})^{n},

where \binom{m}{k}, k/m and x^{k} have to be suitably defined. Prove that these Bernstein polynomials converge uniformly to f ∈ C([0, 1]^{n}).

3. Estimates for the Bernstein polynomials

We shall now take a closer look at the Bernstein polynomials, essentially following Lorentz [1953]. Let us define

(3.1)  p_{mk}(x) = \binom{m}{k}x^{k}(1 − x)^{m−k},  m ∈ N^{∗}, 0 ⩽ k ⩽ m,

and

(3.2)  T_{ms}(x) = ∑_{k=0}^{m}(k − mx)^{s}p_{mk}(x),  m ∈ N^{∗}, s ∈ N.

Since p_{mk} has degree m, it follows that T_{ms} has degree at most m + s. However, we shall see that T_{ms} is of degree at most s in x: a lot of cancellation takes place. Even more remarkable is the fact that T_{ms}(x) is a polynomial also in m. We shall determine its degree.

To understand the role of the T_{ms} let us remark that B_{m}(f) = ∑ f(k/m)p_{mk} and that, if we define u_{as}(x) = (x − a)^{s}, x ∈ [0, 1], s ∈ N, then

B_{m}(u_{as})(x) = ∑ u_{as}(k/m)p_{mk}(x) = m^{−s} ∑(k − ma)^{s}p_{mk}(x),

so that

(3.3)  B_{m}(u_{as})(a) = m^{−s}T_{ms}(a),  a ∈ [0, 1], s ∈ N.

We can expect B_{m}(u_{as})(a) to be smaller than B_{m}(u_{as})(x) when x is at some distance from a, since |u_{as}| has its minimum at a.

We have actually already studied T_{m0}, T_{m1} and T_{m2}. Indeed,

T_{m0}(x) = 1, T_{m1} = 0, and T_{m2}(x) = mx(1 − x).

The first formula is just (2.2); the other two follow from Proposition 2.2. For larger values of s we can state the following.

Proposition 3.1. For a fixed s ∈ N, T_{ms} is a polynomial in x and m. Its degree in x is at most s. Its degree in m is ⌊\frac{1}{2}s⌋ (the integer part of \frac{1}{2}s), thus equal to \frac{1}{2}s when s is even and equal to \frac{1}{2}(s − 1) when s is odd.

Proof. We have

T′_{ms}(x) = −msT_{m,s−1}(x) + ∑_{0}^{m}(k − mx)^{s}p′_{mk}(x)

= −msT_{m,s−1}(x) + ∑_{0}^{m}(k − mx)^{s+1}\binom{m}{k}x^{k−1}(1 − x)^{m−k−1}

= −msT_{m,s−1}(x) + \frac{1}{x(1 − x)}T_{m,s+1}.

We rewrite this as a recursion formula

T_{m,s+1}(x) = x(1 − x)[T′_{ms}(x) + msT_{m,s−1}(x)],

from which we can read off that the degrees in x and m are at most what is stated, starting from what we already know about the polynomials for s = 0, 1, 2. It remains to be seen that the degree in m is not less than ⌊\frac{1}{2}s⌋. However, it is possible to keep track of the coefficient of m^{s} in T_{m,2s} and T_{m,2s+1} (the leading coefficient) and show that it does not vanish.

Exercise 3.2. Show that

∑_{s=0}^{∞} \frac{1}{s!}T_{ms}(x)y^{s} = [e^{−xy}(1 − x + xe^{y})]^{m}.

From this formula various properties of the T_{ms} can be deduced.

Since the degree in m of T_{m,2s} is s, there exists, for each s ∈ N, a constant A_{s} such that

0 ⩽ T_{m,2s}(x) ⩽ A_{s}m^{s}, x ∈ [0, 1], m ∈ N^{∗}.

This also yields an estimate for B_{m}(u_{a,2s})(a):

(3.4)  0 ⩽ B_{m}(u_{a,2s})(a) = m^{−2s}T_{m,2s}(a) ⩽ A_{s}m^{−s}.

Theorem 3.3. Let f be a bounded function on [0, 1] such that f′ exists near a given point a in that interval and such that f′′(a) exists. Then

(3.5)  B_{m}(f)(a) = f(a) + \frac{a(1 − a)}{2m}f′′(a) + o(1/m),  m → ∞.

Proof. We already know that the result is true when f is a polynomial of degree at most 2. For every positive ε there is a constant M such that

f(x) ⩽ p(x) + ε(x − a)^{2} + M(x − a)^{4}, x ∈ [0, 1],

where p is the polynomial of degree at most 2 which agrees with the derivatives up to order 2 of f at the point a. Then by (2.9),

B_{m}(f)(x) ⩽ p(x) + ε(x − a)^{2} + \frac{x(1 − x)}{2m}(p′′(a) + 2ε) + MB_{m}(u_{a4})(x), x ∈ [0, 1].

In particular, taking x = a, we obtain

B_{m}(f)(a) ⩽ p(a) + \frac{a(1 − a)}{2m}(p′′(a) + 2ε) + MB_{m}(u_{a4})(a), a ∈ [0, 1].

Thus, in view of (3.4),

m(B_{m}(f)(a) − f(a)) ⩽ \frac{a(1 − a)}{2}(f′′(a) + 2ε) + MA_{2}m^{−1}, a ∈ [0, 1],

and we can conclude that

lim_{m→∞} m(B_{m}(f)(a) − f(a)) ⩽ \frac{a(1 − a)}{2}(f′′(a) + 2ε).

Since ε is arbitrarily small, we get an inequality which, together with the inequality in the opposite direction, proves (3.5).

Thus for smooth functions the error ∥B_{m}(f) − f∥_{∞} behaves like C/m (and no better, unless of course f ∈ 𝒫_{1}), whereas it is like ω(1/\sqrt{m}) ⩾ C/\sqrt{m} (and no better) for general continuous functions.

Exercise 3.4. Let f be a smooth function such that lots of derivatives vanish at a particular point a: f′′(a) = f′′′(a) = ⋯ = f^{(q)}(a) = 0. Prove that then B_{m}(f)(a) converges to f(a) fast.

Let us also consider the function ψ_{aδ} defined by ψ_{aδ}(x) = 0 when x ∈ [0, 1], |x − a| < δ, and ψ_{aδ}(x) = 1 elsewhere in [0, 1]. We can compare it with u_{a,2s}:

0 ⩽ ψ_{aδ} ⩽ δ^{−2s}u_{a,2s}, a ∈ [0, 1], δ > 0, s ∈ N.

This gives

B_{m}(ψ_{aδ})(x) ⩽ δ^{−2s}B_{m}(u_{a,2s})(x), x, a ∈ [0, 1], s ∈ N,

and, in particular at the point a,

0 ⩽ B_{m}(ψ_{aδ})(a) ⩽ δ^{−2s}B_{m}(u_{a,2s})(a) = m^{−2s}δ^{−2s}T_{ms}(a), a ∈ [0, 1], s ∈ N.

This means that we have proved a useful estimate

∑_{|k/m−a|⩾δ} p_{mk}(a) = ∑_{k=0}^{m} ψ_{aδ}(k/m)p_{mk}(a) = B_{m}(ψ_{aδ})(a)

⩽ δ^{−2s}B_{m}(u_{a,2s})(a) = m^{−2s}δ^{−2s}T_{m,2s}(a). (3.6)

Thus estimates for T_{m,2s} will yield estimates for sums of p_{mk} over those k that satisfy |k/m − a| ⩾ δ. For example it follows from (3.4) that, for any given positive δ and any s ∈ N,

(3.7)  B_{m}(ψ_{aδ})(a) ⩽ m^{−2s}δ^{−2s}T_{m,2s}(a) ⩽ A_{s}δ^{−2s}m^{−s}.

Exercise 3.5. Calculate B_{m}(f)(\frac{1}{2}) for f(x) = |x− \frac{1}{2}|, x ∈ [0, 1]. (The answer should be compared with Bernstein’s result [1913] that for the best polynomial approximation of f the error is O(1/m) and no better; as well as with Stahl’s result [1992] on rational approximation that E_{mm}(|x|; [−1, 1]) = 8e^{−π\sqrt{m}}(1 + o(1)), m → ∞. Here E_{mm} denotes the error when approximating by rational functions whose numerator and denominator are of degree at most m.)

4. Weierstrass’ original proof

We shall take a look at Weierstrass’ original proof of his theorem, Weierstrass [1885]. He used convolution by a kernel which is an entire function, and then the Taylor polynomial of the convolution product. So to describe this we have to define convolution.

Let f and g be two functions defined on all of R^{n}. Then their convolution product is denoted by f ∗ g and defined by

(4.1)  (f ∗ g)(x) = ∫_{R^{n}} f(y)g(x − y)dy,  x ∈ R^{n},

whenever the integral has a sense. We can for instance take f ∈ C_{0}(R^{n}), g ∈ C(R^{n}) or the other way around, i.e., we take two continuous functions (so that the integral over a bounded set exists) and then require that one of them have compact support (so that the integral over all of R^{n} exists). Or we can impose some growth at infinity. More advanced integrals can be used; it is proved in Lebesgue integration theory that (4.1) exists for almost all x ∈ R^{n} if f, g ∈ L^{1}(R^{n}), and that the convolution product is then itself an element of L^{1}(R^{n}). But in that case the integral in (4.1) may not exist for certain values of x.

Given now f ∈ C(I), I = [0, 1], we first have to extend it to the whole axis. This is easy: we just put f(x) = f(0) for negative x and f(x) = f(1) for x > 1. The new function is then an element of C(R). Or we can extend it to an element of C_{0}(R) by declaring it to be zero for x ⩽ −η as well as for x ⩾ 1 + η, and then define it as a first-degree polynomial in [−η, 0] and [1, 1 + η]; thus f ∈ C_{0}(R). Here η is a fixed positive number. Either way the integral

(W_{m} ∗ f)(x) = ∫_{R} W_{m}(y)f(x − y)dy, x ∈ R,

exists if we let W be the function

(4.2)  W (x) = Ce^{−x^{2}},  x ∈ R,

with the constant C determined such that

∫_{R} W (x)dx = 1,

and

W_{m}(x) = mW (mx), x ∈ R, m ∈ N^{∗}.

It is now a well-known result that W_{m} ∗ f converges to f uniformly. Indeed, we have the following theorem.

Theorem 4.1. Let K_{j}, j ∈ N^{∗}, be integrable functions on the real axis which satisfy:

(a) sup_{j} ∫_{R} |K_{j}|dx < +∞;

(b) ∫_{R} K_{j}dx → 1 as j → ∞;

(c) ∫_{|x|>δ} |K_{j}|dx → 0 as j → ∞ for every positive number δ.

Then K_{j} ∗ f → f uniformly as j → ∞ for every f ∈ C_{0}(R).

If K_{j} ⩾ 0 we can simplify the hypotheses to: ∫_{R} K_{j}dx → 1 and ∫_{|x|>δ} K_{j}dx → 0.

Exercise 4.2. Prove this theorem. Determine the constant C in (4.2).

Obviously K_{m} = W_{m} satisfies the hypothesis of the theorem, so we get a sequence of continuous functions f_{m} = W_{m} ∗ f which converges to f ∈ C_{0}(R).

However, W_{m} is not only a continuous function on the real axis; it is also the restriction to R of an entire function, i.e., a function which is holomorphic in the whole complex plane.

Lemma 4.3. Let W (z) = Ce^{−z^{2}}, z ∈ C, and define

(W ∗ f)(z) = ∫_{R} W (z − y)f(y)dy = ∫_{−η}^{1+η} W (z − y)f(y)dy, z ∈ C,

for any function f ∈ C_{0}(R) with support in [−η, 1 + η] for a fixed positive η. Then W ∗ f is holomorphic everywhere in C.

Sketch of proof. We have

W (z − y) = ∑_{j∈N} c_{j}(z − y)^{j}

with uniform convergence when |z − y| ⩽ R and R is any positive number. Therefore we can integrate W (z − y)f(y) with respect to y termwise:

(W ∗ f)(z) = ∑_{j∈N} c_{j} ∫_{−η}^{1+η}(z − y)^{j}f(y)dy.

Now ∫_{−η}^{1+η}(z − y)^{j}f(y)dy is a polynomial in z, thus an entire function. The series converges uniformly for |z| ⩽ R − 1 − η and its sum must therefore be holomorphic for |z| < R − 1 − η, hence everywhere.

Exercise 4.4. Complete the proof with all details.

Exercise 4.5. Give an alternative proof that W ∗f is entire by studying the difference quotient

\frac{(W ∗ F)(a + z) − (W ∗ F)(a)}{z}

and proving that it converges to (W′ ∗f)(a) as z → 0, where W′ denotes the complex derivative of W, W′(z) = (d/dz)Ce^{−z^{2}} = −2Cze^{−z^{2}}.

Now for entire functions the Taylor polynomials (see (2.1)) serve very well as approximants. We thus take the Taylor polynomials of W_{m} ∗ f to a degree which is so large that the error on the interval [−η, 1 + η] is not more than 1/m. This proves the theorem.

Landau^{6} [1908] gave a similar proof: he took K_{j} as a polynomial L_{j} of degree 2j:

L_{j}(x) = α_{j} (1 − (x/c)^{2})^{j} , x ∈ R,

where c is a fixed number larger than 1, and the constant α_{j} is chosen so that

α_{j} ∫_{−c}^{c} (1 − (x/c)^{2})^{j} dx = 1.

We assume that f ∈ C_{0}(R) has its support in [−η, 1 + η], where 1 + 2η = c. We see that K_{j} ∗ f = L_{j} ∗ f is a polynomial in this case. Landau’s proof is thus like

6Edmund Georg Hermann Landau, 1877–1938.

Weierstrass’ except that the last step, when we approximated an entire function by polynomials, is unnecessary.

5. The Stone–Weierstrass approximation theorem

An order relation in a set X is a relation (a subset of X^{2}) which satisfies three conditions: it is reflexive, antisymmetric and transitive. This means, if we denote the relation by ⩽, that for all x, y, z ∈ X,

x ⩽ x;
x ⩽ y and y ⩽ x implies x = y;
x ⩽ y and y ⩽ z implies x ⩽ z.

An ordered set is a set X together with an order relation.

A lattice is an ordered set L where each set consisting of two elements has an infimum and a supremum (a greatest minorant and a least majorant). This means that for any two x, y ∈ L there exists a and b in L such that a ⩽ x, y, and such that z ⩽ x, y implies z ⩽ a; and similarly for b: x, y ⩽ b, and x, y ⩽ z implies b ⩽ z. The supremum and infimum are of course unique. It is customary to denote the infimum and supremum of two elements x, y by x ∧ y and x ∨ y, respectively.

A sublattice is defined just like a subgroup: that L_{1} is a sublattice of L means that for all x, y ∈ L_{1}, x ∧ y and x ∨ y, when calculated in L, are elements of L_{1}.

A lattice is said to be complete if any subset has an infimum and a supremum. Example 5.1. The space of real-valued continuous functions on a topological space is a lattice. The space C^{1}(R^{n}) of continuously differentiable functions on R^{n} is not a sublattice of C(R^{n}). It is not even a lattice on its own. Example 5.2. The set [−∞, +∞]^{R^{n}} of all functions defined on R^{n} and with values in the extended real line [−∞, +∞] = R ∪ {−∞, +∞} is a lattice under the usual order for real numbers, extended in an obvious way to the two infinities. The subset of all convex functions is ordered in the same way, and is also a lattice under this order. However, the convex functions CVX(R^{n}) do not form a sublattice of [−∞, +∞]^{R^{n}}. The supremum of two convex functions is equal to the pointwise supremum of them:

f ∨ g = max(f, g),

but the infima are different in the two lattices: the infimum in the lattice of convex functions is

f ∧_{cvx} g = sup [h; h ∈ CVX(R^{n}), h ⩽ f, g],

where the supremum is calculated in [−∞, +∞]^{R^{n}} and has a sense because that lattice is complete.

Lemma 5.3. Let A be a closed subalgebra of C(K), the algebra of all real-valued continuous functions on a compact topological space K. Then A is a sublattice of C(K).

Proof. In C(K) the lattice operations can be defined in terms of the absolute value:

f ∧ g = \frac{1}{2}(f + g − |f − g|), and f ∨ g = \frac{1}{2}(f + g + |f − g|),

so it is clearly enough to prove that f ∈ A implies |f| ∈ A. We know that f ∈ A implies P ∘ f ∈ A for all polynomials in one variable with P (0) = 0 (we never said that A should contain the constants). Therefore it is enough to find a sequence of polynomials (P_{k}) such that P_{k}(0) = 0 and P_{k}(x) → |x| uniformly on [−1, 1]. Indeed, if f ∈ A, then |f| ⩽ c for some constant c > 0 and cP_{k}(f/c) tends to |f| uniformly on K. (This, of course, is a special case of the Weierstrass approximation theorem.)

One way to find such a sequence of polynomials is to use the binomial series with exponent \frac{1}{2}. We first have to extend the definition of the binomial coefficients (2.3) to non-integers:

(5.1)  \binom{z}{k} = \frac{z(z − 1) ⋯ (z − k − 1)}{k!},  z ∈ C, k ∈ N.

We know that, for complex t such that |1 − t^{2}| < 1,

|t| = \sqrt{1 − (1 − t^{2})} = ∑_{0}^{∞} \binom{\frac{1}{2}}{j}(−1)^{j}(1 − t^{2})^{j}

= 1 − ∑_{1}^{∞} \frac{1 · 3 · 5 ⋯ (2j − 3)}{2^{j}j!}(1 − t^{2})^{j} = 1 − ∑_{1}^{∞} \frac{(2j − 3)!!}{(2j)!!}(1 − t^{2})^{j}.

Here (−1)!! = 1. Thus the series representation holds in particular for real t satisfying 0 < t ⩽ 1. But a closer analysis shows that it is valid also for t = 0, even uniformly for −1 ⩽ t ⩽ 1. For these values of t the last series is majorized termwise by

∑_{1}^{∞} \frac{(2j − 3)!!}{(2j)!!} = 1.

We can now define

P_{k}(t) = ∑_{1}^{k} \frac{(2j − 3)!!}{(2j)!!}(1 − (1 − t^{2})^{j}).

We note that P_{k}(0) = 0 as desired and that P_{k}(t) → |t| uniformly for t ∈ [−1, 1]. The lemma is proved.

Lemma 5.4. Let L be a sublattice of C(K), where K is a compact space. Suppose that every function f ∈ C(K) can be approximated by functions in L at two arbitrary points, i.e., that to every f ∈ C(K), every ε > 0, and every s, t ∈ K there exists g_{st} ∈ A such that |g_{st}(x) − f(x)| < ε for x = s, t. Then L is dense in C(K).

Proof. Fix an arbitrary function f ∈ C(K) and define

U_{st} = {x ∈ K; g_{st}(x) < f(x) + ε} and V_{st} = {x ∈ K; g_{st}(x) > f(x) − ε}.

For any fixed s the family (U_{st})_{t∈K} is an open covering of K. Since K is compact, we can choose points t_{1}, ..., t_{m} in K such that U_{st_{1}} ∪ ⋯ ∪ U_{st_{m}} = K. Then define V_{s} = V_{st_{1}} ∩ ⋯ ∩ V_{st_{m}} and g_{s} = g_{st_{1}} ∧ ⋯ ∧ g_{st_{m}} ∈ L. We now have g_{s} < f + ε in all of K, for if x is an arbitrary point in K, then x belongs to some U_{st_{j}} and then g_{s}(x) ⩽ g_{st_{j}}(x) < f(x) + ε. Moreover, in V_{s} we have g_{s} > f − ε, for x ∈ V_{s} implies g_{st_{j}} > f(x) − ε for all j, hence g_{s} = ⋀_{j=1}^{m} g_{st_{j}} > f(x) − ε.

Now V_{s} is open as a finite intersection of open sets; (V_{s})_{s∈K} is an open covering of K. Choose finitely many points s_{1}, ..., s_{n} in K such that V_{s_{1}} ∪ ⋯ ∪ V_{s_{n}} = K and define g = g_{s_{1}} ∨ ⋯ ∨ g_{s_{n}} ∈ L. In all of K we now have |f − g| < ε, for g_{s_{j}} < f + ε for all j, which implies g = g_{s_{1}} ∨ ⋯ ∨ g_{s_{n}} < f + ε, and, on the other hand, if x ∈ V_{s_{j}} then g(x) ⩾ g_{s_{j}}(x) > f(x) − ε, so that g > f − ε in the union of the V_{s_{j}}, which is all of K.

Theorem 5.5 (The Stone^{7}–Weierstrass theorem). Let A be a subalgebra of C(K), where K is a compact topological space. Suppose that A separates points in K, i.e., that for every pair of points s, t ∈ K with s ≠ t there exists a function g ∈ A such that g(s) ≠ g(t). Then either there exists a point p ∈ K such that

\overline{A} = C_{p}(K) = \{f ∈ C(K); f(p) = 0\},

or else \overline{A} = C(K). A special case is Weierstrass’ approximation theorem: take A = ⋃ 𝒫_{m}|_{I}, the algebra of all polynomials restricted to an interval I. We also immediately get the generalization to the case of a compact set K in R^{n}. Proof. Suppose first that there exists, to any given s ∈ K a function h ∈ A such that h(s) ≠ 0. Then, given any two points s, t ∈ K, s ≠ t, there exists g ∈ A such that 0 ≠ g(s) ≠ g(t) ≠ 0. Indeed, if it happened for instance that g(s) = 0, then we can replace g by g + λh, where h is a function such that h(s) ≠ 0 and λ is sufficiently small. Then there exist, given arbitrary numbers a, b ∈ R, real numbers c, d such that

\{ \begin{matrix}cg(s) + dg^{2}(s) = a \\ cg(t) + dg^{2}(t) = b, \end{matrix}

for the determinant of the system is g(s)g(t)(g(t) − g(s)) ≠ 0. Since cg + dg^{2} belongs to A and \overline{A} is a lattice according to Lemma 5.3, \overline{A} satisfies the hypotheses of Lemma 5.4, and we conclude that \overline{A} = C(K).

If, on the other hand, there exists a point p ∈ K such that all elements g of A satisfy g(p) = 0, we can apply what we already proved to the algebra A + R. To any given f ∈ C_{p}(K) there exists a g ∈ A and a k ∈ R such that |f − g − k| < ε. We note that k must satisfy |k| = |f(p) − g(p) − k| < ε, so that |f − g| ⩽ |f − g − k| + |k| < 2ε. This proves that A is dense in C_{p}(K). Remark. In the complex case things are different. We can let A be the algebra of functions which are continuous on the closed unit disk K in C and holomorphic in its interior. Then A is closed and separates points in K but is different from C(K). However, if we consider algebras A such that f ∈ A implies \overline{f} ∈ A, then the results

7Marshall Harvey Stone, 1903 04 08–1989 01 09. hold as in the real case; we just apply what we have proved to the algebras Re A and Im A.

6. Chebyshev’s theorems

Let us consider the space C(I), where I is a compact interval of the real line. It is a Banach space of infinite dimension, and its subspace 𝒫_{m}|_{I}, the restrictions to I of polynomials of degree at most m, is a finite-dimensional subspace. The distance from a function f to this subspace is also the greatest lower bound for the errors when approximating the function f by polynomials of degree at most m:

(6.1)  E_{m}(f) = d(f, 𝒫_{m}) = inf (∥f − p∥; p ∈ 𝒫_{m}).

(To simplify notation I shall sometimes write 𝒫_{m} where I should have written 𝒫_{m}|_{I}.) Since 𝒫_{m} is closed in C(I) (see proof below), this distance is zero if and only if f itself is a polynomial of degree at most m. The Weierstrass approximation theorem says that the error E_{m}(f) tends to zero as m → ∞, and we even have an idea of how fast it can tend to zero—see Corollary 2.4 and Theorem 3.3.

In this section we shall first prove that the infimum in (6.1) is attained, and then that it is attained at a unique point, although the norm we are using, the supremum norm ∥ · ∥ = ∥ · ∥_{∞}, is very far from being a Hilbert norm.

Theorem 6.1 (Borel [1905]). The infimum in (6.1) is attained for some polynomial in 𝒫_{m}.

Proof. We shall use the theorem that a continuous function on a compact set attains its infimum. So we first have to prove that the function φ(p) = ∥p − f∥ is a continuous function of p ∈ 𝒫_{m}. But what does that mean? We can use the topology induced from C(I), or we can consider the topology from R^{m+1}, using the coefficients (a_{0}, a_{1}, ..., a_{m}) ∈ R^{m+1} as coordinates for p(x) = ∑_{0}^{m} a_{j}x^{j}. However, these two topologies agree; it is a well-known theorem that a finite-dimensional space can have only one Hausdorff (separated) vector space topology. In this particular case it is easy to argue as follows. We first note that

∥p∥ = sup |∑_{0}^{m} a_{j}x^{j}| ⩽ sup_{0⩽j⩽m} sup_{x∈I} |x|^{j} ∑_{0}^{m} |a_{j}| = C∥a∥_{1},

so that the norm of p calculated in C(I) is majorized by a constant times the l^{1} norm of the coefficient vector. Therefore the supremum norm ∥p∥ of p is a continuous function on R^{m+1}. Its infimum on the unit sphere of R^{m+1} is attained and therefore cannot be zero. This gives an inequality in the other direction, and shows that the two norms are actually equivalent. (It follows that 𝒫_{m} is closed in C(I): 𝒫_{m} is complete for the norm in R^{m+1} and therefore for the norm induced by C(I), hence closed in C(I).)

It is easy to see that φ(p) = ∥p−f∥ is a continuous function of p for the topology induced by C(I):

φ(p) − φ(q) = ∥p − f∥ − ∥q − f∥ ⩽ ∥p − q∥.

If we interchange the roles of p and q we see that

|φ(p) − φ(q)| ⩽ ∥p − q∥, p, q ∈ 𝒫_{m}.

But from what we have remarked, this implies that φ(p) depends continuously on p if we use its coefficients as coordinates.

Now R^{m+1} is not compact, so we have to restrict the function φ to a compact subset. Indeed φ is large outside some compact set. To see this we remark that

φ(p) = ∥p − f∥ ⩾ ∥p∥ − ∥f∥ = ∥p∥ − φ(0) > φ(0) if ∥p∥ > 2φ(0),

so that the infimum of the whole space 𝒫_{m} is the same as the infimum over the ball K = {p; ∥p∥ ⩽ 2φ(0)}. The set K is closed and bounded in R^{m+1}, and therefore φ as a function of (a_{0}, ..., a_{m}) attains its infimum there, and this infimum must be the same as the global infimum. This proves the theorem.

Thus there exists for every m ∈ N a best approximant p_{m} to a given continuous function f ∈ C(I). It is easy to see that for m = 0 this polynomial, a constant, is unique and equal to the mean values of sup f and inf f. The best approximant is however unique for all m as was proved by Chebyshev. We shall first introduce his criterion for a function to be a best approximant.

Theorem 6.2 (Chebyshev^{8} [1854]). Let a function f ∈ C(I) be given on I = [a, b]. Then a polynomial p ∈ 𝒫_{m} is a best approximant of f in the supremum norm if and only if there exist at least m+2 points x_{j} in [a, b] with a ⩽ x_{1} < x_{2} < ⋯ < x_{m+2} ⩽ b, such that the difference r = f − p takes alternating values at the x_{j} and its absolute value at each of the points is ∥r∥: (−1)^{j}r(x_{j}) is independent of j and |r(x_{j})| = ∥r∥ for all j. The points x_{j} are called deviation points.^{9} Example 6.3. Let a = −4π, b = 4π and f(x) = sin x. The zero polynomial satisfies the criterion in the theorem for m = 6, so it follows that the zero polynomial is a best approximant to f in 𝒫_{6}. Example 6.4. Let a = −1, b = 1 and take f(x) = x^{m}, m ∈ N^{∗}. Let the best approximant (unique as we shall prove) in 𝒫_{m−1} be p_{m−1}. Then

x^{m} − p_{m−1}(x) = 2^{−m+1} cos(m arccos x) = 2^{−m+1}T_{m}(x),

where the last equation defines a polynomial T_{m}, called the Chebyshev polynomial of degree m. See Figure 4. The error is thus 2^{−m+1}. The criterion is satisfied, as can be easily verified. Proof. Necessity. Assume that p is a best approximant of f. If f itself is a polynomial of degree m, then r is zero and the criterion is trivially satisfied for p = f. Otherwise we have ∥r∥ > 0 and we first note that we must have sup r = ∥r∥ and inf r = −∥r∥.

8Pafnutij L′vovič Čebyšev, 1821–1894. 9In Russian the set of these m + 2 points is called čebyševskij al′ternans.

Figure 4. The Chebyshev polynomial T_{40}.

Indeed, if for instance we had sup r = ∥r∥ − 2δ with δ > 0, then we could find a better approximant q = p − δ:

∥f − q∥ = ∥f − p + δ∥ = max(sup(r + δ), − inf(r + δ)) = ∥r∥ − δ < ∥r∥.

Let us call a point x such that r(x) = ∥r∥ a positive deviation point and similarly a point x such that r(x) = −∥r∥ a negative deviation point. Thus we have proved that there are at least one positive and at least one negative deviation point. For m = 0 the proof of the necessity is now complete. Otherwise we go on to find zeros z_{j} of r with the property that each of the intervals

[a, z_{1}], [z_{1}, z_{2}], ..., [z_{k−1}, z_{k}], [z_{k}, b]

contains only positive or only negative deviation points. To fix ideas we may assume that the first deviation point is positive. Then we choose z_{1} as the largest zero such that [a, z_{1}] contains only positive deviation points; then we choose z_{2} as the largest zero such that [z_{1}, z_{2}] contains at least one negative deviation point but no positive deviation point, provided there is such a zero; otherwise we stop and let k = 1. We go on; for compactness reasons the procedure must stop and there is a last zero z_{k}. There are now k zeros z_{1}, ..., z_{k} of r and there are k + 1 deviation points x_{j} with x_{1} < z_{1} < ⋯ < z_{k} < x_{k+1}. If k ⩽ m we find that the polynomial p + q, where q(x) = δ(x−z_{1}) ⋯ (x−z_{k}) for a small |δ| is a better approximant than p if we choose the sign of δ so that q becomes positive in [a, z_{1}[ . Since this is against the hypothesis, we must have k ⩾ m + 1, and therefore there are at least k + 1 ⩾ m + 2 deviation points, as claimed.

Sufficiency. Let p be a polynomial of degree at most m which satisfies the criterion in the theorem, and assume that there is another polynomial q ∈ 𝒫_{m} which gives a better approximation, i.e., ∥f − q∥ < ∥f − p∥, in particular

|f(x_{j}) − q(x_{j})| ⩽ ∥f − q∥ < ∥f − p∥ = |f(x_{j}) − p(x_{j})|

at every deviation point x_{j} for p. This implies that the sign of

q(x_{j}) − p(x_{j}) = (f(x_{j}) − p(x_{j})) − (f(x_{j}) − q(x_{j}))

is the same as the sign of f(x_{j}) − p(x_{j}), so that p − q changes its sign at least m + 1 times in [a, b]; it follows that p − q has at least m + 1 zeros. Since p − q is not identically zero and of degree at most m, this is impossible. Therefore there are no better approximants than p.

A variant of the last argument gives an even better result: the uniqueness of the best approximant:

Theorem 6.5. For every f ∈ C(I) and every m ∈ N there exists a unique polynomial p_{m} in 𝒫_{m} such that

∥p_{m} − f∥ = inf (∥p − f∥; p ∈ 𝒫_{m}).

Proof. We argue as in the proof of the sufficiency in the last proof. Assume that p and q are both best approximants. Then also their mean value \frac{1}{2}p + \frac{1}{2}q is a best approximant, for

E_{m} ⩽ ∥f − (\frac{1}{2}p + \frac{1}{2}q)∥ ⩽ \frac{1}{2}∥f − p∥ + \frac{1}{2}∥f − q∥ = E_{m},

where E_{m} = d(f, 𝒫_{m}) = ∥f − p∥. By Theorem 6.2 there must exist m + 2 deviation points x_{j} for \frac{1}{2}p + \frac{1}{2}q, which means that

E_{m} = |f(x_{j}) − (\frac{1}{2}p(x_{j}) + \frac{1}{2}q(x_{j})| ⩽ \frac{1}{2}|f(x_{j}) − p(x_{j})| + \frac{1}{2}|f(x_{j}) − q(x_{j})| ⩽ E_{m}.

It follows from this not only that the x_{j} are deviation points also for p and q:

|f(x_{j}) − p(x_{j})| = |f(x_{j}) − q(x_{j})| = E_{m},

but even that the differences f(x_{j})−p(x_{j}) and f(x_{j})−q(x_{j}) must have the same sign. Hence the differences are equal: f(x_{j}) − p(x_{j}) = f(x_{j}) − q(x_{j}) for j = 1, ..., m + 2. The polynomial p − q has m + 2 zeros and is of degree at most m. Hence it vanishes identically: p = q and the best approximant is unique.

There is a variant of Theorem 6.2 for periodic functions.

Theorem 6.6. Let a continuous function f be defined on the real axis with period 2π. Then a trigonometric polynomial T of order m is a best approximant of f in the supremum norm if and only if there exist at least 2m + 2 points t_{j} in an interval [a, a + 2π[ with a ⩽ t_{1} < t_{2} < ⋯ < t_{2m+2} < a+2π, such that the difference r = f −T takes alternating values at the t_{j} and its absolute value at each of the points is ∥r∥: (−1)^{j}r(t_{j}) is independent of j and |r(t_{j})| = ∥r∥ for all j. The proof of this theorem is like that of Theorem 6.2. The polynomial q in the proof of the necessity has to be replaced by

q(t) = δ sin \frac{t − z_{1}}{2} sin \frac{t − z_{2}}{2} ⋯ sin \frac{t − z_{k}}{2} .

Definition 6.7. Let a metric space M be given. A set of m + 1 functions φ_{0}, ..., φ_{m} ∈ C(M) is called a Chebyshev system if M contains at least m + 1 points and if a linear combination ∑ c_{j}φ_{j} can have m + 1 different zeros only if all coefficients c_{j} vanish. Examples. The system φ_{j}(z) = z^{j}, j = 0, ...., m is a Chebyshev system on C, as well as on every subset of C containing at least m + 1 points. The system 1, e^{iz}, e^{−iz}, ..., e^{imz}, e^{−imz} as well as the system 1, cos z, sin z, ..., cos mz, sin mz are Chebyshev on the strip a ⩽ Re z < a + 2π for any a ∈ R, and of course also on any subset of the strip containing at least 2m + 1 points, in particular on the interval [a, a + 2π[. However, it is not Chebyshev on the interval [0, 2π], since sin mt vanishes at 2m + 1 points t = kπ/m, k = 0, ..., 2m. (It is obvious that we should count in R modulo 2π.) It follows that the system 1, cos t, cos 2t, ..., cos mt is Chebyshev on [0, π[ and the system sin t, sin 2t, ..., sin mt is Chebyshev on ]0, π[. Example. The functions φ_{0}(x) = x^{2} − x, φ_{1}(x) = x^{2} + x, φ_{2}(x) = x^{2} + 1 form a Chebyshev system on the real axis. Any two of these three functions do not form a Chebyshev system.

There is a criterion for being Chebyshev in terms of determinants:

Exercise 6.8. Let a metric space M be given with at least m + 1 points. Then φ_{0}, ..., φ_{m} ∈ C(M) is a Chebyshev system if and only if the determinant det(φ_{j}(x_{k})), j, k = 0, ..., m, is nonzero for every choice of different points x_{0}, ..., x_{m} in M.

Exercise 6.9. Let a Chebyshev system φ_{0}, ..., φ_{m} on a metric space M be given and let x_{0}, ..., x_{m} be different points. Then for any real numbers y_{j}, j = 0, ..., m, there exists a linear combination P of the φ_{k} such that P (x_{j}) = y_{j}.

The importance of the notion of Chebyshev system for unique best approximants is made clear by the following theorem.

Theorem 6.10 (Haar^{10} [1918], Kolmogorov^{11} [1948]). Let K be a compact subset of R^{n} containing at least m + 1 points and let φ_{0}, ..., φ_{m} be m + 1 real-valued or complex-valued continuous functions on K. Then there is a unique best approximant in the supremum norm among the linear combinations of φ_{0}, ..., φ_{m} for an arbitrary continuous function on K if and only if φ_{0}, ..., φ_{m} is a Chebyshev system.

10Alfred Haar, 1885–1933. 11Andrej Nikolaevič Kolmogorov, 1903–1987.

I shall not give the proof here. Let me mention that it uses the exercises 6.8 and 6.9 and the arguments developed in the proof of Theorems 6.2 and 6.5.

Nice as this theory may be, it is of limited interest in several variables, for Mairhuber [1956] has proved that if there exists a Chebyshev system with m ⩾ 1 on a compact space K, then K is homeomorphic to a circle or a subset of a circle. So approximation in several variables is different, and the reader is asked to ponder the following exercise:

Exercise 6.11. Let K = [0, 1]^{2} ⊂ R^{2} and define φ_{0}(x) = 1, φ_{1}(x) = x_{1}, φ_{2}(x) = x_{2}. Then there exist functions in C(K) which do not admit a unique best approximant among the linear combinations of φ_{0}, φ_{1}, φ_{2}.

7. Approximation by polynomials and trigonometric polynomials

The purpose of this section is twofold: to introduce results on trigonometric polynomials and approximation by them and, secondly, to prove best possible results—it turns out that the Bernstein polynomials do not give the best possible approximation.

Let us review first some elementary results from the theory of Fourier series. We shall work with periodic functions; it is convenient to let the period be 2π. Let us denote by C_{2π}(R) the space of continuous functions on the real line which are periodic with period 2π. It is the same thing as the continuous functions on the quotient space R/2π = R mod 2π, thus C_{2π}(R) = C(R/2π).

A function f in C_{2π}(R) has a Fourier series

(7.1)  f(x) ∼ \frac{1}{2}a_{0} + ∑_{k=1}^{∞}(a_{k} cos kx + b_{k} sin kx),

where the Fourier coefficients a_{k}, k ∈ N, and b_{k}, k ∈ N^{∗}, are defined by

(7.2)  a_{k} = \frac{1}{π} ∫_{0}^{2π} f(x) cos kx dx,  b_{k} = \frac{1}{π} ∫_{0}^{2π} f(x) sin kx dx.

We also know about two important kernels, the Dirichlet^{12} kernel D_{m} and the Fejér^{13} kernel F_{m}. To wit:

(7.3)  D_{m}(x) = \frac{1}{2} + cos x + cos 2x + ⋯ + cos mx = \frac{sin(m + \frac{1}{2})x}{2 sin \frac{1}{2}x},

(7.4)  F_{m}(x) = \frac{1}{m} ∑_{0}^{m−1} D_{k}(x) = \frac{1}{2m} (\frac{sin \frac{m}{2}x}{sin \frac{1}{2}x})^{2} .

The function D_{m} is not positive, and its total mass ∫_{0}^{2π} |D_{m}(x)|dx tends to infinity like log m. The kernel F_{m}, on the other hand, is positive.

12Peter Gustav Lejeune Dirichlet, 1805–1859. 13Lipót Fejér, 1880–1959, my great-grand-advisor.

We define the convolution product f ∗ g of two functions in C_{2π}(R) as

(7.5)  (f ∗ g)(x) = \frac{1}{π} ∫_{0}^{2π} f(y)g(x − y) dy,  x ∈ R.

With this normalization we have f ∗ 1 = a_{0} = twice the mean value of f. Also (f ∗ cos)(0) = a_{1}, and so on for the higher Fourier coefficients. More generally,

(f ∗ (t ↦ cos kt))(x) = \frac{1}{π} ∫_{0}^{2π} f(y) cos k(x − y) dy

= \frac{1}{π} ∫_{0}^{2π} f(y) cos kx cos ky dy + \frac{1}{π} ∫_{0}^{2π} f(y) sin kx sin ky dy

= a_{k} cos kx + b_{k} sin kx.

Summing over k = 0, ..., m, we see that f ∗ D_{m} is nothing but the partial sum of the Fourier series.

We also know from some course on Fourier analysis that the convolution product f ∗ D_{m} converges uniformly to f if f is of class C^{1}, but that there exist continuous functions such that this partial sum does not converge at a given point. On the other hand, the convolution f ∗F_{m} always converges uniformly to f if f is continuous. This yields the Weierstrass approximation theorem for trigonometric polynomials:

Theorem 7.1. Let f ∈ C_{2π}(R) and let ε be a positive number. Then there exists a trigonometric polynomial T such that |T (x) − f(x)| < ε for all x ∈ R.

Proof. The Fejér kernel does the job: f ∗F_{m}, m ∈ N^{∗}, are trigonometric polynomials, and they converge uniformly to f for every f ∈ C_{2π}(R) as m → ∞.

We shall now try to improve the results of Corollary 2.4, which gave us polynomials converging to f with an error \frac{5}{4}ω(1/\sqrt{m}).

We shall sum Fourier series in a more general way. Let us define

σ_{m}(x) = \frac{1}{2} + ∑_{k=1}^{∞} ρ_{mk} cos kx, x ∈ R, m ∈ N^{∗},

where the ρ_{mk}, m, k ∈ N^{∗}, are real numbers and where for each fixed m, ρ_{mk} = 0 for large k. So the Dirichlet kernel is the special case when ρ_{mk} = 1 for k = 1, ..., m and zero otherwise; the Fejér kernel the special case when ρ_{mk} = 1 − k/m for k = 1, ..., m − 1 and zero otherwise. The convolution

(7.6) (f ∗ σ_{m})(x) = \frac{1}{π} ∫_{0}^{2π} f(y)σ_{m}(x − y)dy = \frac{1}{2}a_{0} + ∑_{k=1}^{∞} ρ_{mk}(a_{k} cos kx + b_{k} sin kx)

is well defined for any integrable periodic function, in particular for any function in C_{2π}(R), and is a trigonometric polynomial of order at most equal to the largest k such that ρ_{mk} is nonzero.

We shall define a kernel, known as the Jackson^{14} kernel as follows:

(7.7)  J_{m}(x) = \frac{6m}{2m^{2} + 1}F_{m}(t)^{2} = \frac{6m}{2m^{2} + 1} [\frac{1}{2} + ∑_{j=1}^{m−1}(1 − j/m) cos jx]^{2}

= \frac{1}{2}j_{0} + ∑_{k=1}^{2m−2} j_{k} cos kx.

It is clear that J_{m} is a positive trigonometric polynomial of order 2m − 2. It is also obvious that c_{m}F_{m}^{2} should be a good kernel in the sense of Theorem 4.1 (adapted to the case of periodic functions) for some choice of c_{m} > 0. So the only thing we need to check is that c_{m} = 6m/(2m^{2} + 1) gives the right mean value. This is easy:

j_{0} = \frac{1}{π} ∫_{0}^{2π} J_{m}(t)dt = \frac{6m}{2m^{2} + 1} [\frac{1}{2} + ∑_{1}^{m−1}(1 − k/m)^{2}]

= \frac{6m}{2m^{2} + 1} (\frac{1}{2} + \frac{(m − 1)m(2m − 1)}{6m^{2}}) = 1,

where the second equality follows from the orthogonality of the cosine functions on [0, 2π].

Exercise 7.2. Calculate j_{1} = ρ_{2m−2,1} for the Jackson kernel.

Lemma 7.3. The first moment of the Jackson kernel can be estimated as follows:

\frac{1}{π} ∫_{0}^{π} tJ_{m}(t)dt ⩽ \frac{3π}{4m}, m ∈ N^{∗}.

Proof. The integral in question is equal to

\frac{3}{2πm(2m^{2} + 1)} [∫_{0}^{π/m} + ∫_{π/m}^{π}] t (\begin{matrix}sin & \frac{mt}{2} \\ sin & \frac{t}{2} \end{matrix} )^{4} dt

⩽ \frac{3}{4πm^{3}} [∫_{0}^{π/m} tm^{4}dt + ∫_{π/m}^{π} t\frac{π^{4}}{t^{4}} dt] ⩽ \frac{3π}{4m}.

Exercise 7.4. Prove that the first moment of the Fejér kernel satisfies

c\frac{log m}{m} ⩽ ∫_{0}^{π} tF_{m}(t)dt ⩽ C \frac{log m}{m}, m ⩾ 2,

for some positive constants c, C.

14Dunham Jackson, 1888–1946.

Let us now estimate how far the trigonometric polynomial f ∗ J_{ν} is from f in supremum norm. We note that

f(x) − (f ∗ J_{ν})(x) = \frac{1}{π} ∫_{0}^{2π} [f(x)J_{ν}(t) − f(x − t)J_{ν}(t)]dt,

so that

(7.8) |(f − f ∗ J_{ν})(x)| ⩽ \frac{1}{π} ∫_{0}^{π} [|f(x + t) − f(x)| + |f(x − t) − f(x)|]J_{ν}(t)dt

⩽ \frac{2}{π} ∫_{0}^{π} ω(t)J_{ν}(t)dt ⩽ ω(1/ν)\frac{2}{π} ∫_{0}^{π}(νt + 1)J_{ν}(t)dt

⩽ ω(1/ν) (2ν \frac{3π}{4ν} + 1) = ω(1/ν) (\frac{3π}{2} + 1) ⩽ 6ω(1/ν).

Now f ∗ J_{ν} is of order 2ν − 2. Given any m, we define ν = m/2 + 1 in case m is even, and ν = (m − 1)/2 + 1 in case m is odd. Then f ∗ J_{ν} is of order at most 2ν − 2 ⩽ m and ω(1/ν) ⩽ 2ω(\frac{1}{m+1}) in all cases, so that

∥f − f ∗ J_{ν}∥ ⩽ 6ω(1/ν) ⩽ 12ω(\frac{1}{m+1}).

Theorem 7.5. (P. P. Korovkin [1959]). Suppose that we have real numbers ρ_{mk}, k, m ∈ N^{∗}, satisfying

(7.9)  σ_{m}(x) = \frac{1}{2} + ∑_{k=1}^{m} ρ_{mk} cos kx ⩾ 0,  x ∈ R,

and

(7.10)  ρ_{m1} → 1 as m → ∞.

Then the convolution f ∗ σ_{m} converges uniformly to f for any f ∈ C_{2π}(R).

This theorem is a consequence of the following more precise result:

Theorem 7.6. (P. P. Korovkin [1959]). If the ρ_{mk} are chosen so that σ_{m} ⩾ 0, then

(7.11)  ∥f ∗ σ_{m} − f∥_{∞} ⩽ ω(δ) (1 + \frac{π}{\sqrt{2}δ} \sqrt{1 − ρ_{m1}}) ,  δ > 0, m ∈ N^{∗},

where ω denotes the modulus of continuity of f.

The remarkable thing here is that conditions (7.10) and (7.11) involve only ρ_{m1}, whereas the ρ_{mk} for k ⩾ 2 do not appear—they play a role of course in the positivity condition.

Lemma 7.7. The first moment of the kernel σ_{m} can be estimated as follows:

\frac{1}{π} ∫_{0}^{π} tσ_{m}(t)dt ⩽ \frac{π}{2\sqrt{2}}\sqrt{1 − ρ_{m1}}, m ∈ N^{∗}.

Proof. We use first the estimate t/π ⩽ sin(t/2), and then the Hölder inequality:

\frac{1}{π} ∫_{0}^{π} tσ_{m}(t)dt ⩽ ∫_{0}^{π} sin \frac{t}{2}σ_{m}(t)dt = ∫_{0}^{π} sin \frac{t}{2}\sqrt{σ_{m}(t)}\sqrt{σ_{m}(t)}dt

⩽ \sqrt{∫_{0}^{π} sin^{2} \frac{t}{2}σ_{m}(t)dt}\sqrt{∫_{0}^{π} σ_{m}(t)dt}.

Here the expression under the first radical sign is

∫_{0}^{π}(\frac{1}{2} − \frac{1}{2} cos t)σ_{m}(t)dt = \frac{π}{4} − \frac{π}{4} ρ_{m1},

and the expression under the second radical sign is π/2. This proves the lemma. Proof of Theorem 7.6. The proof is just like the one for the Jackson kernel: we first use the inequality ω(t) = ω((t/δ)δ) ⩽ (1 + t/δ)ω(δ), where δ is independent of m, and then Lemma 7.7 to estimate the first moment:

|f(x) − (f ∗ σ_{m})(x)| ⩽ \frac{2}{π} ∫_{0}^{π} ω(t)σ_{m}(t)dt ⩽ ω(δ)\frac{2}{π} ∫_{0}^{π}(1 + t/δ)σ_{m}(t)dt

= ω(δ) (\frac{2}{π} ∫_{0}^{π} σ_{m}(t)dt + \frac{2}{πδ} ∫_{0}^{π} tσ_{m}(t)dt) ⩽ ω(δ) (1 + 2\frac{π}{2\sqrt{2}δ} \sqrt{1 − ρ_{m1}}) .

Corollary 7.8. For the Fejér kernel we have

∥f ∗ F_{m} − f∥_{∞} ⩽ (1 + \frac{π}{\sqrt{2}}) ω(1/\sqrt{m}), m ∈ N^{∗}.

Proof. We know that the Fejér kernel is positive and that it satisfies ρ_{m1} = 1 − 1/m. We choose δ = 1/\sqrt{m} in Theorem 7.6 to conclude.

Theorem 7.9 (Jackson’s first theorem). For any f ∈ C_{2π}(R) and every m ∈ N^{∗} there exists a trigonometric polynomial T of order at most m such that

∥f − T ∥_{∞} ⩽ 6ω(\frac{1}{m+1}).

Proof. Following Korovkin we shall define polynomials σ_{m} ⩾ 0 with

ρ_{m1} = cos \frac{π}{m + 2} ⩾ 1 − \frac{π^{2}}{2(m + 2)^{2}} ,

so that

\sqrt{1 − ρ_{m1}} ⩽ \frac{π}{\sqrt{2}(m + 2)},

which is a better estimate than that for the Fejér kernel. With this estimate we may choose δ = 1/(m + 1) in (7.11) and obtain

ω(\frac{1}{m+1}) (1 + \frac{π(m + 1)}{\sqrt{2}}\sqrt{1 − ρ_{m1}}) ⩽ ω(\frac{1}{m+1}) (1 + \frac{π(m + 1)}{\sqrt{2}} \frac{π}{\sqrt{2}(m + 2)})

⩽ ω(\frac{1}{m+1}) (1 + \frac{π^{2}}{2} ) ⩽ 6ω(\frac{1}{m+1}),

the estimate in Theorem 7.9. (The Jackson kernel has ρ_{2m−2,1} = 1 − \frac{3}{2m^{2}} , thus

\sqrt{1 − ρ_{2m−2,1}} = ^{\frac{\sqrt{3/2}}{m}}, almost as good as for the Korovkin kernel.)

So we shall find a positive kernel with this wonderful property. Define

σ_{m}(t) = A_{m}|a_{1} + a_{2}z + a_{3}z^{2} + ⋯ + a_{m+1}z^{m}|^{2},

where

z = cos t + i sin t, A_{m} = \frac{1}{2(a_{1}^{2} + ⋯ + a_{m+1}^{2})}, and a_{k} = sin \frac{kπ}{m + 2}.

We find that (7.12)

ρ_{m1} = \frac{a_{1}a_{2} + a_{2}a_{3} + ⋯ + a_{m}a_{m+1}}{a_{1}^{2} + a_{2}^{2} + ⋯ + a_{m+1}^{2}} = \frac{∑_{1}^{m} sin \frac{kπ}{m+2} sin \frac{k+1}{m+2}}{sin^{2} \frac{π}{m+2} + sin^{2} \frac{2π}{m+2} + ⋯ + sin^{2} \frac{(m+1)π}{m+2}} .

This expression can be calculated, using the formula

cos \frac{π}{m + 2} sin^{2} \frac{kπ}{m + 2} = \frac{1}{2} sin \frac{(k − 1)π}{m + 2} sin \frac{kπ}{m + 2} + \frac{1}{2} sin \frac{kπ}{m + 2} sin \frac{(k + 1)π}{m + 2} .

Summing over k = 1, ..., m + 1 we get a left-hand side equal to

cos \frac{π}{m + 2} ∑_{1}^{m+1} sin^{2} \frac{kπ}{m + 2},

and a right-hand side equal to the numerator in the last expression in (7.12). This proves that ρ_{m1} = cos \frac{π}{m+2}.

Exercise 7.10. We have seen that for the Jackson kernel and the Korovkin kernel we have \sqrt{1 − ρ_{m1}} = O(1/m), m → ∞, which yields a good approximation. Show that we cannot have \sqrt{1 − ρ_{m1}} = o(1/m), m → ∞, as long as σ_{m} ⩾ 0.

Exercise 7.11. Prove that for the Jackson kernel we have

lim_{m→∞} m^{2}(J_{m} ∗ f − f) = \frac{3}{2}f′′

for functions of class C^{2}. Cf. Theorem 3.3.

It is known that one has

(7.13)  E_{m}(f) ⩽ \frac{λ}{2(m + 1)},  m ∈ N, f ∈ C([0, 1]),

for functions with Lipschitz constant λ on [0, 1]. It is easy to see that this estimate cannot be improved. To do so we can use a simple sawtooth function: define f to take the values (−1)^{k} at the points x = k/(m + 1), k = 0, ..., m + 1, and to be affine in between these points. Then its Lipschitz constant is λ = 2(m + 1), and by the Chebyshev criterion (Theorem 6.2), the best approximant in 𝒫_{m} is zero. Therefore E_{m}(f) = ∥f∥ = 1. We see that in any estimate E_{m}(f) ⩽ Cλ/(m + 1) we must have C ⩾ \frac{1}{2}. For the interval [−1, 1] the estimate is E_{m}(f) ⩽ λ/(m + 1) and it is also best possible.

Similarly for the periodic case it is known that

(7.14)  E_{m}(f) ⩽ \frac{πλ}{2(m + 1)}  m ∈ N, f ∈ C_{2π}(R),

if λ is the Lipschitz constant of f. Here we define a function which takes the value ±1 at the points kπ/(m + 1), k = 0, ..., 2m + 2, and is affine in between. There are 2m + 2 deviation points in a period [0, 2π[; note that 0 = 2π in the quotient space. This function shows that in any estimate E_{m}(f) ⩽ C/(m+1) we must have C ⩾ π/2.

For general continuous functions the best estimate is

(7.15)  E_{m}(f) ⩽ ω(π/(m + 1))  m ∈ N,

a result due to Kornejčuk [1962]. It can be shown using piecewise affine functions that this estimate is also best possible among those with E_{m}(f) ⩽ Cω(1/(m + 1)). However these piecewise affine functions are a little more complicated to describe than those we used in the Lipschitz case.

A more careful analysis yields an improvement of Theorem 7.9:

Theorem 7.12. There exists a constant C such that

E_{m}(f) ⩽ Cω_{2}(\frac{1}{m+1}), m ∈ N, f ∈ C_{2π}(R),

where

ω_{2}(δ) = sup_{x,t∈R} [|f(x + 2t) − 2f(x + t) + f(x)|; |t| ⩽ δ]

is the second modulus of continuity.

Proof. We estimate like in (7.8) but a little more carefully, using the fact that J_{ν} is even:

f(x) − (f ∗ J_{ν})(x) = \frac{1}{π} ∫_{0}^{2π} [f(x)J_{ν}(t) − f(x − t)J_{ν}(t)]dt

= \frac{1}{π} ∫_{0}^{π}(2f(x) − f(x − t) − f(x + t))J_{ν}(t)dt,

so that

|(f − f ∗ J_{ν})(x)| ⩽ \frac{2}{π} ∫_{0}^{π} ω_{2}(t)J_{ν}(t)dt.

We then use the fact that ω_{2}(t) = ω_{2}((m+1)t·(1/(m+1))) ⩽ (1+(m+1)t)^{2}ω_{2}(\frac{1}{m+1}) to deduce that

∥f − f ∗ J_{ν}∥ ⩽ ω_{2}(\frac{1}{m+1}) ∫_{0}^{π}(1 + (m + 1)t)^{2}J_{ν}(t)dt,

and the last integral is bounded; the second moment ∫_{0}^{π} t^{2}J_{ν}(t)dt can be estimated as in Lemma 7.7 and one can prove that it does not exceed a constant times (m + 1)^{−2}. This proves the theorem.

There are higher moduli of continuity. We first define the differences

Δ_{t}^{1}f(x) = f(x + t) − f(x),
Δ_{t}^{p+1}f(x) = Δ_{t}^{1}Δ_{t}^{p}f(x),  p ∈ N^{∗}.

Then the pth modulus of continuity is

ω_{p}(f; δ) = sup_{\begin{matrix}x,t∈R \\ |t|⩽δ \end{matrix}} |Δ_{t}^{p}f(x)|.

One can prove a generalization of Theorem 7.12:

(7.16)  E_{m}(f) ⩽ C_{p}ω_{p}(f; \frac{1}{m+1}).

The sequence of errors E_{m}(f) tends to zero if f is continuous as we know. But how slowly? In fact arbitrarily slowly as the next theorem shows.

Theorem 7.13. Given any decreasing sequence (ε_{m})_{m∈N} of positive numbers tending to zero there exists a function f ∈ C([−1, 1]) such that E_{m}(f) ⩾ ε_{m}, m ∈ N.

Proof. Put α_{k} = ε_{k−1} − ε_{k} ⩾ 0 and define f = ∑_{0}^{∞} α_{k}T_{3^{k}}, where T_{m} denotes the Chebyshev polynomial of degree m. Since ∥T_{m}∥ ⩽ 1 and ∑ α_{k} < +∞, f is continuous. We claim that P = ∑_{0}^{m} α_{k}T_{3^{k}} is the best approximant of degree at most 3^{m}. Consider the error function r = f − P = ∑_{m+1}^{∞} α_{k}T_{3^{k}}. If we can show that it has at least 3^{m} + 2 deviation points it will follow by Chebyshev’s criterion that P is a best approximant. Put x_{j} = cos(jπ/3^{m+1}), j = 0, ..., 3^{m+1}. For k ⩾ m + 1 we have T_{3^{k}}(x_{j}) = cos(3^{k}jπ/3^{m+1}) = (−1)^{j} (here it is important that 3^{k}j/3^{m+1} has the same parity as j). Thus T_{3^{k}}(x_{j}) does not depend on k so

r(x_{j}) = (−1)^{j} ∑_{k=m+1}^{∞} α_{k} = (−1)^{j}ε_{m},

and we have

ε_{m} = |r(x_{j})| ⩽ ∥r∥ ⩽ ∑_{m+1}^{∞} α_{k} = ε_{m},

showing that the x_{j} are in fact deviation points, and that there are at least 3^{m+1}+1 ⩾ 3^{m}+2 of them. So P is indeed a best approximant and E_{m}(f) ⩾ E_{3^{m}}(f) = ∥r∥ = ε_{m}.

8. The nonexistence of a continuous linear projection

Let us denote by π_{m}(f) the polynomial in 𝒫_{m} closest to f. In view of Theorem 6.5 there is thus a well-defined operator π_{m}: C(I) → 𝒫_{m}. We may inquire as to its properties. Obviously it is idempotent, π_{m} ∘ π_{m} = π_{m}; it is a projection onto 𝒫_{m}. Moreover, it is positively homogeneous, i.e., it satisfies π_{m}(λf) = λπ_{m}(f) for every positive λ. It is easy to see by examples that π_{m}(f + g) ≠ π_{m}(f) + π_{m}(g) in general. So π_{m} is certainly nonlinear. The Weierstrass theorem says that π_{m}(f) → f for the norm in C(I) as m → ∞. The operator is also continuous, as we shall prove now:

Theorem 8.1. Let π_{m}(f) denote the polynomial of degree at most m ∈ N which is closest to f ∈ C(I) in the supremum norm. Then π_{m} is a continuous operator; more precisely, for every m ∈ N and every f ∈ C(I) there exists a positive number C = C_{m,f} such that for all g ∈ C(I),

∥π_{m}(g) − π_{m}(f)∥ ⩽ C∥g − f∥.

Lemma 8.2. For every m ∈ N and every f ∈ C(I) there exists a positive number γ = γ_{m,f} such that for every polynomial Q ∈ 𝒫_{m} we have

∥Q − f∥ ⩾ ∥π_{m}(f) − f∥ + γ∥Q − π_{m}(f)∥.

Thus the function Q ↦ ∥Q − f∥ on 𝒫_{m}, which attains its infimum at Q = π_{m}(f), has a sharp minimum at that point: the value increases fast as we move away from π_{m}(f). Proof. If f ∈ 𝒫_{m}, then π_{m}(f) = f and the inequality holds with γ = 1. Now assume that ∥π_{m}(f) − f∥ > 0. According to Theorem 6.2 we have m + 2 deviation points x_{j} and signs θ_{j} = ±1 such that, for every j = 1, ..., m + 2, ∥π_{m}(f) − f∥ = θ_{j}(π_{m}(f) − f)(x_{j}). For any Q ∈ 𝒫_{m} ∖ {0} we have max_{j} θ_{j}Q(x_{j}) > 0, for if we assume that the maximum is nonpositive we would get θ_{j}Q(x_{j}) ⩽ 0 for all j, hence, since θ_{j+1} = −θ_{j}, that Q has at least m + 1 zeros counting multiplicities. In fact, we can prove inductively that Q must have k − 1 zeros in [x_{1}, x_{k}]. First, assume for definiteness that Q(x_{1}) ⩽ 0, Q(x_{2}) ⩾ 0 and so on. If Q has a zero in [x_{1}, x_{2}[, we are done for k = 2. If not, then x_{2} must be a zero. If Q has a zero in ]x_{2}, x_{3}[ we have two different zeros in [x_{1}, x_{3}[ ; if not, Q is either positive or negative throughout ]x_{2}, x_{3}[. In the first case Q(x_{3}) = 0; in the second, x_{2} must be a double zero, so that, in either case, there are two zeros in [x_{1}, x_{3}] counting multiplicities. It is now clear how to go on. Thus we have proved by contradiction that max θ_{j}Q(x_{j}) > 0. In view of the compactness we even have

(8.1)  inf_{∥Q∥=1} max_{j} θ_{j}Q(x_{j}) = γ > 0.

The choice of points x_{j} implies that

∥Q − f∥ ⩾ θ_{j}(Q(x_{j}) − f(x_{j})) = θ_{j}(π_{m}(f) − f)(x_{j}) + θ_{j}(Q − π_{m}(f))(x_{j})
= ∥π_{m}(f) − f∥ + θ_{j}(Q − π_{m}(f))(x_{j}).

We now take the maximum over all j:

∥Q − f∥ ⩾ ∥π_{m}(f) − f∥ + max_{j} θ_{j}(Q − π_{m}(f))(x_{j}) ⩾ ∥π_{m}(f) − f∥ + γ∥Q − π_{m}(f)∥,

applying (8.1) in the last step to the normalized polynomial (Q−π_{m}(f))/∥Q−π_{m}(f)∥. Proof of Theorem 8.1. Choose γ according to Lemma 8.2 so that ∥Q − f∥ ⩾ ∥π_{m}(f) − f∥ + γ∥Q − π_{m}(f)∥ for all Q ∈ 𝒫_{m}. In particular we may apply this inequality to Q = π_{m}(g) and obtain

∥π_{m}(f) − f∥ + γ∥π_{m}(g) − π_{m}(f)∥ ⩽ ∥π_{m}(g) − f∥ ⩽ ∥π_{m}(g) − g∥ + ∥g − f∥
⩽ ∥π_{m}(f) − g∥ + ∥g − f∥ ⩽ ∥π_{m}(f) − f∥ + ∥f − g∥ + ∥g − f∥
= ∥π_{m}(f) − f∥ + 2∥g − f∥.

Subtracting ∥π_{m}(f) − f∥ from the first and the last expression above we see that γ∥π_{m}(g) − π_{m}(f)∥ ⩽ 2∥g − f∥, proving the theorem with the constant C = 2/γ.

For trigonometric polynomials we have a similar projection τ_{m}: C_{2π}(R) → 𝒯_{m}. Theorem 8.1 has a counterpart for τ_{m} and even for general Chebyshev systems, since the characterization of best approximant, which was used in Lemma 8.2, holds also in these cases.

We now ask whether there exists an operator like π_{m} or τ_{m} which in addition is linear. The answer is in the negative as is shown by the following result.

Theorem 8.3 (Kharshiladze and Lozinskij^{15}; Lozinskij [1948]). Let there be given, for each m ∈ N, a continuous linear projection L_{m} of C_{2π}(R) onto the space of trigonometric polynomials of order at most m. Then there exists an f ∈ C_{2π}(R) for which {∥L_{m}(f)∥; m ∈ N} is unbounded. A key step in the proof is an estimate from below of the norm of any projection.

Proposition 8.4. Let L be a continuous linear projection of C_{2π}(R) onto the subspace 𝒯_{m} of trigonometric polynomials of order at most m. Then ∥L∥ ⩾ ∥S_{m}∥, where S_{m} denotes the operator assigning to f its partial Fourier series up to order m, i.e., S_{m}(f) = f ∗ D_{m} as defined by (7.3) and (7.5).

Proof. Define the translation operator T_{a} by

T_{a}(f)(x) = f(x − a), x ∈ R, a ∈ R.

Then T_{a} ∘ L ∘ T_{−a} is also a projection. We let L̃ be the mean value of T_{a} ∘ L ∘ T_{−a} over all translations:

L̃(f)(x) = \frac{1}{2π} ∫_{0}^{2π}(T_{a} ∘ L ∘ T_{−a})(f)(x)da, x ∈ R.

We claim that L̃ = S_{m}. To prove this it is enough to prove that L̃(f_{k}) = S_{m}(f_{k}), where f_{k}(x) = e^{ikx}, k ∈ Z, for the linear combinations of these functions are dense in

15Sergej Mihailovič Lozinskij, born 1914.

C_{2π}(R). Now if |k| ⩽ m, S_{m}f_{k} = f_{k} and T_{−a}f_{k} ∈ 𝒯_{m}, so that L ∘ T_{−a}(f_{k}) = T_{−a}(f_{k}) and (T_{a} ∘ L ∘ T_{−a})(f_{k}) = f_{k}. Consequently the mean value L̃(f_{k}) is also equal to f_{k}. On the other hand, if |k| > m, then S_{m}(f_{k}) = 0. Now T_{−a}(f_{k}) = e^{ika}f_{k} so that (T_{a} ∘ L ∘ T_{−a})(f_{k}) = e^{ika}L(f_{k})(x − a). But L(f_{k}) ∈ 𝒯_{m}, so that, for any fixed x, a ↦ L(f_{k})(x − a) is orthogonal to a ↦ e^{ika} for |k| > m. Thus also L̃(f_{k}) = 0.

Now that we know that L̃ = S_{m} we can easily finish the proof of the proposition:

∥L̃(f)∥ = sup_{x} |\frac{1}{2π} ∫_{0}^{2π}(T_{a} ∘ L ∘ T_{−a})(f)(x)dx| ⩽ ∥T_{a} ∘ L ∘ T_{−a}∥∥f∥ ⩽ ∥L∥∥f∥,

thus ∥S_{m}(f)∥ = ∥L̃(f)∥ ⩽ ∥L∥∥f∥. Taking the supremum over all f we get ∥S_{m}∥ ⩽ ∥L∥ as claimed. Proof of Theorem 8.3. We have ∥L_{m}∥ ⩾ ∥S_{m}∥, and the latter norm is

∥S_{m}∥ = sup_{∥f∥⩽1} |\frac{1}{π} ∫_{0}^{2π} D_{m}(x)f(x)dx| = \frac{1}{π} ∫_{0}^{2π} |D_{m}(x)|dx.

It is not difficult to prove that the latter quantity tends to infinity (in fact like a constant times log m). So ∥L_{m}∥ tends to infinity. We now apply the Banach–Steinhaus theorem, also known as the uniform boundedness principle: if {∥L_{m}(f); m ∈ N∥} is bounded for all f, then also {∥L_{m}∥; m ∈ N} is bounded.

One could also consider the functionals f ↦ L_{m}(f)(0) to get a function f such that the set {L_{m}(f)(0); m ∈ N} is unbounded.

The Kharshiladze–Lozinskij theorem was formulated here for periodic functions but has counterparts for C(I).

9. Approximation of functions of higher regularity

In this section we shall consider functions of higher regularity, meaning functions that are k times continuously differentiable for some k ∈ N. Let us write C_{2π}^{k}(R) for the functions in C^{k}(R) which are periodic with period 2π.

The smallest error when approximating by trigonometric polynomials of order at most m will be denoted by E_{m}(f), thus

(9.1)  E_{m}(f) = inf(∥P − f∥_{∞}; P ∈ 𝒯_{m}).

Theorem 9.1. There exist a constant C_{0} such that for all k ∈ N, all f ∈ C_{2π}^{k}(R) and all m ∈ N,

E_{m}(f) ⩽ (\frac{C_{0}}{m + 1})^{k} ∥f^{(k)}∥.

Proof. In the proof we shall need to consider another error,

(9.2)  e_{m}(f) = inf(∥P − f∥_{∞}; P ∈ 𝒯_{m} without constant term),

i.e., when we approximate by trigonometric polynomials with mean value zero. Obviously E_{m}(f) ⩽ e_{m}(f). We know from Jackson’s theorem that E_{m}(f) ⩽ C_{m}∥f′∥ for every f ∈ C_{2π}^{1}(R), where C_{m} = C_{0}/(m + 1). (We proved that one can take C_{0} = 6; the best result is actually C_{0} = π/2; cf. (7.13).) It is an important observation that the proof actually gives also that

(9.3)  e_{m}(f) ⩽ C_{m}∥f′∥

with the same constant if f has mean value zero. This follows from the fact that the approximation is given by a convolution that reproduces the mean value, so that the approximant has mean value zero if the function has mean value zero, a fact that can be read off from (7.6); the mean value of f ∗ σ_{m} is a_{0}/2, the same as for f.

Given f ∈ C_{2π}^{1}(R) without constant term we choose p ∈ 𝒯_{m} as the trigonometric polynomial which is the best approximant to f′ with mean value zero, thus ∥f′−p∥ = e_{m}(f′). Let P ∈ 𝒯_{m} be the primitive function to p with mean value zero. Then, using (9.3),

e_{m}(f) = e_{m}(f − P) ⩽ C_{m}∥f′ − p∥ = C_{m}e_{m}(f′).

Thus e_{m}(f) ⩽ C_{m}e_{m}(f′) if f has mean value zero. Repeated application gives e_{m}(f) ⩽ C_{m}^{k}e_{m}(f^{(k)}) if f is of class C^{k}, for f′ and all higher derivatives have mean value zero. Thus, given any f ∈ C_{2π}^{k}(R), we conclude that

E_{m}(f) = E_{m}(f − a_{0}/2) ⩽ e_{m}(f − a_{0}/2) ⩽ C_{m}^{k}e_{m}(f^{(k)}) ⩽ C_{m}^{k}∥f^{(k)}∥.

This completes the proof.

Theorem 9.2. For every f ∈ C_{2π}^{1}(R) we have

E_{m}(f) ⩽ \frac{C}{m + 1}ω(f′, \frac{1}{m+1}), m ∈ N.

Proof. From Theorem 7.12 we know that E_{m}(f) ⩽ Cω_{2}(\frac{1}{m+1}). It is easy to see that ω_{2}(f; δ) ⩽ δω(f′; δ). Combining the two inequalities we get the desired conclusion.

Using (7.16) we can prove like in Theorem 9.2 that

E_{m}(f) ⩽ \frac{C_{p}}{(m + 1)^{p}} ω(f^{(p)}; \frac{1}{m+1})

for every f ∈ C_{2π}^{p}(R), p ∈ N.

10. Inverse theorems

The theorems we have considered so far are traditionally called direct theorems (smoothness implies good approximation); we now come to the inverse theorems, i.e., those where we assume that we have a certain degree of approximation and conclude that the function possesses a certain smoothness. We shall consider here the case when the error E_{m}(f) is O(m^{−α}) for some real α.

First a famous inequality:

Theorem 10.1 (Bernstein’s inequality). Any trigonometric polynomial T of order m satisfies ∥T′∥_{∞} ⩽ m∥T ∥_{∞}.

Lemma 10.2. Let P be a polynomial of degree m − 1. Then

(10.1)  sup_{x∈[−1,1]} |P (x)| ⩽ m sup_{x∈[−1,1]} |\sqrt{1 − x^{2}}P (x)|.

Proof. Let x_{j} = cos((2j − 1)π/2m), j = 1, ..., m, be the zeros of the Chebyshev polynomial T_{m}. Let M denote the right-hand side of (10.1). If x happens to belong to the interval [x_{m}, x_{1}], it is easy to prove that |P (x)| ⩽ M:

\sqrt{1 − x^{2}} ⩾ \sqrt{1 − x_{1}^{2}} = \sqrt{1 − cos^{2} \frac{π}{2m}} = sin \frac{π}{2m} ⩾ \frac{1}{m},

so that |P (x)| ⩽ m\sqrt{1 − x^{2}}|P (x)| for these values of x.

The case when x is close to ±1 remains to be studied. The Lagrange interpolation theorem with nodes x_{j} takes the form

P (x) = ∑_{1}^{m} P (x_{j})\frac{T_{m}(x)}{T′_{m}(x_{j})(x − x_{j})} = \frac{1}{m} ∑_{1}^{m} P (x_{j})\frac{T_{m}(x)(−1)^{j−1} sin t_{j}}{x − x_{j}} ,

where t_{j} = \frac{(2j−1)}{m} \frac{π}{2} , for it is easy to prove that T′_{m}(x_{j}) = (−1)^{j−1}m/ sin t_{j}. Say for definiteness that x_{1} < x ⩽ 1. Then since |P (x_{j}) sin t_{j}| ⩽ M/m and all the differences x − x_{j} are positive, we obtain

|P (x)| ⩽ \frac{M}{m^{2}} ∑_{1}^{m} |\frac{T_{m}(x)}{x − x_{j}} | = \frac{M}{m^{2}} |∑_{1}^{m} \frac{T_{m}(x)}{x − x_{j}} | .

The last sum is just the derivative of T_{m} (think of the logarithmic derivative of T_{m}) and we note that T′_{m}(cos t) = m sin mt/ sin t is bounded by m^{2} in absolute value. Hence |P (x)| ⩽ M also for these values of x.

Lemma 10.3. Let S be an odd trigonometric polynomial of order m. Then

∥S/ sin ∥ ⩽ m∥S∥.

Proof. Using the well-known formula

\frac{sin(k + 1)t}{sin t} = cos kt + \frac{sin kt}{sin t} cos t

we can prove by induction that sin kt/ sin t is a polynomial in cos t of order k − 1. Hence S(t) = P (cos t) sin t for some algebraic polynomial P of degree m − 1. We now apply Lemma 10.2 to P to conclude. Proof of Theorem 10.1. Consider the function f(s, t) = \frac{1}{2}(T (s + t) − T (s − t)). For fixed s, the trigonometric polynomial t ↦ f(s, t) is odd and of order at most m. Clearly |f(s, t)| ⩽ ∥T ∥, so by Lemma 10.3, |f(s, t)/ sin t| ⩽ m∥T ∥. Hence also T′(s) = lim_{t→0}(f(s, t)/ sin t)(sin t/t) is bounded by m∥T ∥ in modulus.

Theorem 10.4 (Markov’s^{16} inequality). Every polynomial P of degree m satisfies ∥P′∥_{∞} ⩽ m^{2}∥P ∥_{∞}, where the norms are supremum norms on [−1, 1].

Proof. The function T (t) = P (cos t) is a trigonometric polynomial of order m, so Bernstein’s inequality implies |T′(t)| = |P′(cos t) sin t| ⩽ m∥P ∥, which can be written |P′(x)\sqrt{1 − x^{2}}| ⩽ m∥P ∥ for x ∈ [−1, 1]. We now apply Lemma 10.2 to P′ to conclude: ∥P′∥ ⩽ m^{2}∥P ∥.

For any α with 0 < α ⩽ 1, let us define a class Lip_{α}(R) of functions, consisting of those whose modulus of continuity satisfies ω(δ) = O(δ^{α}), δ → 0. The elements of Lip_{1}(R) are called Lipschitz functions.

Theorem 10.5. Let f ∈ C_{2π}(R) and fix 0 < α < 1. Then E_{m}(f) = O(m^{−α}) as m → ∞ if and only if f ∈ Lip_{α}(R).

Proof. That functions in Lip_{α} can be approximated as indicated is Jackson’s first theorem. Assume conversely that we know that E_{m}(f) = O(m^{−α}). Thus there exists trigonometric polynomials T_{m} of order at most m such that ∥f − T_{m}∥ ⩽ Cm^{−α}, m ⩾ 1, for some constant C independent of m. The convergence of the sequence (T_{m}) to f is in general too slow for a telescoping series to be useful. We shall take a subsequence (T_{2^{j}}), which converges faster. By the triangle inequality we have |f(x + t) − f(x)| ⩽ |f(x + t) − T_{2^{k}}(x + t)| + |T_{2^{k}}(x + t) − T_{2^{k}}(x)| + |T_{2^{k}}(x) − f(x)|. Here the first and third terms on the right do not exceed C2^{−αk}, and the second term can be estimated by |t|∥T′_{2^{k}}∥. To estimate this derivative we shall use the telescoping series

T′_{2^{k}} = T′_{1} + ∑_{1}^{k}(T′_{2^{j}} − T′_{2^{j−1}}),

together with the estimate

(10.2) ∥T_{2^{j}} − T_{2^{j−1}}∥ ⩽ ∥T_{2^{j}} − f∥ + ∥f − T_{2^{j−1}}∥ ⩽ C(2^{−αj} + 2^{−α(j−1)}) = C_{1}2^{−αj}.

The last inequality implies in view of Bernstein’s inequality that

∥T′_{2^{j}} − T′_{2^{j−1}}∥ ⩽ C_{1}2^{j}2^{−αj},

so that

∥T′_{2^{k}}∥ ⩽ C_{2} + ∑_{1}^{k} C_{1}2^{j(1−α)} ⩽ C_{2} + C_{3}2^{k(1−α)},

where C_{2} is a bound for T′_{1}. Putting things together we have

|f(x + t) − f(x)| ⩽ 2C2^{−αk} + |t| (C_{2} + C_{3}2^{k(1−α)}) ,

where k is still to be chosen. Given t with |t| ⩽ 1 we pick k such that 2^{k} ⩽ 1/|t| < 2^{k+1} and see that |f(x + t) − f(x)| ⩽ C_{4}|t|^{α} for a new constant C_{4}, |t| ⩽ 1. For larger |t| this is true at the expense of a larger constant. This completes the proof.

Exercise 10.6. Prove that if f is a periodic function with E_{m}(f) = O(1/m), then its modulus of continuity satisfies ω(δ) ⩽ Cδ log δ, 0 < δ < \frac{1}{2}, for some constant C.

It is to be noted that the proof of Theorem 10.5 breaks down for α = 1. Indeed the result is not true in that case. Instead, we have the following theorem.

16Andrej Andreevič Markov, 1856–1922.

Theorem 10.7 (Zygmund’s^{17} Theorem). Let f ∈ C_{2π}(R) be given. Then E_{m}(f) = O(1/m), m → ∞, if and only if ω_{2}(δ) = O(δ), δ → 0.

Exercise 10.8. Construct a function such that ω_{2}(δ) = O(δ), δ → 0, but which is not Lipschitz.

Proof of Theorem 10.7. Theorem 7.12 proves one direction. To prove the other direction, assume that E_{m}(f) = O(1/m), m → ∞, and write f = lim T_{2^{j}}, where T_{2^{j}} is a trigonometric polynomial of order at most 2^{j} such that ∥f − T_{2^{j}}∥ ⩽ C2^{−j}. Thus we can use a telescoping series

(10.3)  f = lim_{k→∞} T_{2^{k}} = T_{1} + ∑_{1}^{∞}(T_{2^{j}} − T_{2^{j−1}}) = ∑_{0}^{∞} V_{j},

where V_{0} = T_{1} and V_{j} = T_{2^{j}} − T_{2^{j−1}}, j ⩾ 1. The second difference of f can then be estimated by

|Δ_{t}^{2}f| ⩽ ∑_{0}^{m−1} |Δ_{t}^{2}V_{j}| + 4 ∑_{m}^{∞} ∥V_{j}∥,

where we still can choose m. From (10.2) we see that ∥V_{j}∥ ⩽ C_{1}2^{−j}, j ⩾ 1. The second difference is easy to estimate by the second derivative, so we can conclude, using Bernstein’s inequality, that for |t| ⩽ δ,

|Δ_{t}^{2}f| ⩽ ∑_{0}^{m−1} δ^{2}∥V′′_{j}∥ + C_{2}2^{−m} ⩽ ∑_{0}^{m−1} δ^{2}2^{2j}∥V_{j}∥ + C_{2}2^{−m} ⩽ C_{1}δ^{2}2^{m} + C_{2}2^{−m}

when |t| ⩽ δ. We now choose m so that 2^{m} ⩽ δ^{−1} < 2^{m+1} and get the desired result.

Theorem 10.9 (Bernstein). Let f ∈ C_{2π}(R) and fix k ∈ N and α ∈ [0, 1[. Then

E_{m}(f) ⩽ Cm^{−k−α}, m ∈ N,

if and only if f ∈ C^{k}(R) and f^{(k)} ∈ Lip_{α}(R).

Proof. We shall prove only one direction: we assume that f admits the approximation E_{m}(f) ⩽ Cm^{−k−α} and shall prove that f^{(k)} exists and is in Lip_{α}(R). We have a representation f = ∑_{0}^{∞} V_{j} as in (10.3) where now

∥V_{j}∥ ⩽ ∥T_{2^{j}} − f∥ + ∥f − T_{2^{j−1}}∥ ⩽ C(2^{j})^{−k−α} + C(2^{j−1})^{−k−α} = C_{1}2^{−j(k+α)}.

From Bernstein’s inequality we deduce that

∥V_{j}^{(k)}∥ ⩽ (2^{j})^{k}∥V_{j}∥ ⩽ C_{1}2^{jk}2^{−jk−jα} = C_{1}2^{−jα}.

Hence ∑ V_{j}^{(k)} converges uniformly to some continuous function g, and since termwise integration is allowed we see that f^{(k)} exists and is equal to g. Now

E_{2^{j}}(f^{(k)}) ⩽ ∥f^{(k)} − ∑_{0}^{j} V_{i}^{(k)}∥ ,

17Antoni Zygmund, 1900–1992. for ∑_{0}^{j} V_{i}^{(k)} is a trigonometric polynomial of order at most 2^{j}. However,

∥f^{(k)} − ∑_{0}^{j} V_{i}^{(k)}∥ = ∥∑_{j+1}^{∞} V_{i}^{(k)}∥ ⩽ C_{2}2^{−jα},

which shows that E_{2^{j}}(f^{(k)}) ⩽ C_{2}2^{−jα}. For any m ∈ N we now choose j such that 2^{j} ⩽ m < 2^{j+1}, which yields the estimate

E_{m}(f^{(k)}) ⩽ E_{2^{j}}(f^{(k)}) ⩽ C_{2}2^{−jα} ⩽ 2^{α}C_{2}m^{−α}.

Now Theorem 10.5 implies that f^{(k)} ∈ Lip_{α}(R).

References

Baker, George A., Jr., and Gammel, John L. (Eds.) 1970 The Padé Approximant in Theoretical Physics. New York and London: Academic Press. xii + 378 pp.

Baker, George A., Jr., and Graves-Morris, Peter 1981 Padé Approximants. Part I: Basic Theory; Part II: Extensions and Applications. Encyclopedia of Mathematics and its Applications, Volumes 13 and 14. Reading, MA: Addison-Wesley. xx + 325 resp. xviii + 215 pp.

Bernstein, Serge 1912 Démonstration du théorème de Weierstrass, fondée sur le calcul des probabilités. Commun. Soc. Math. Kharkow (2) 13 (1912–13), 1–2.

1913 Sur la meilleure approximation de |x| par des polynômes de degrés donnés. Acta Math. 37, 1–57.

Borel, É.

1905 Leçons sur les fonctions de variables réelles. Paris.

Chebyshev, P. L. 1854 Teorija mehanizmov, izvestnyh pod nazvaniem parallelogrammov. [Collected works 1948, vol. 2, 23–51.]

Cheney, E. W.

1966 Introduction to Approximation Theory. McGraw-Hill. xii + 259 pp.

Dzjadyk, V. K. 1977 Vvedenie v teoriju ravnomernogo približenija funkcij polinomami. Moscow: Nauka.

Haar, Alfred 1918 Die Minkowskische Geometrie und die Annäherung an stetige Funktionen. Math. Ann. 78, 293–311.

Jackson, D. 1912 On approximation by trigonometric sums and polynomials. Trans. Amer. Math. Soc. 13, 491–515.

Kolmogorov, A. N. 1948 Zamečanie po povodu mnogočlenov P. L. Čebyševa, naimenee uklonjajuščihsja ot zadannoj funkcii. Uspehi mat. nauk 3, 216–221.

Kornejčuk, N. P. 1962 The exact constant in D. Jackson’s theorem on best uniform approximation of continuous periodic functions. [Russian.] Doklady Akad. Nauk 145, 514– 515.

Korovkin, P. P. 1959 Linejnye operatory i teorija približenij. Moscow: Gosudarstvennoe izdatel′- stvo fiziko-matematičeskoj literatury. English translation: Linear operators and Approximation Theory. Delhi: Hindustan Publishing Company, 1960.

Landau, E. G. H. 1908 Über die Approximation einer stetigen Funktion. Rendiconti Circ. mat. Palermo 25, 337–345.

Lorentz, G. G.

1953 Bernstein polynomials. Toronto: University of Toronto Press.

Lozinskij, S. M. 1948 On a class of linear operators. [Russian.] Doklady Akad. Nauk 61, 193– 196.

Mairhuber, J. 1956 On Haar’s theorem concerning Chebysheff approximation problems having unique solutions. Proc. Amer. Math. Soc. 7, 609–615.

Newman, D.

1964 Rational approximation to |x|. Michigan Math. J. 11, 11–14.

Rivlin, T. J.

1990 Chebyshev Polynomials. 2nd ed. New York: Wiley.

Rudälv, Catarina 1998 Multivariate rational approximation with prescribed poles. Umeå University, Department of Mathematics, Doctoral Thesis No. 16.

Stahl, Herbert 1992 Best uniform rational approximation of |x| on [−1, 1]. [Russian.] Mat. Sb. 183, 85–118.

Stone, M. H. 1937 Applications of the theory of Boolean rings to general topology. Trans. Amer. Math. Soc. 41, 375–481.

1948 The generalized Weierstrass approximation theorem. Math. Mag. 21, 167– 184.

Weierstraß, Karl 1885 Über die analytische Darstellung sogenannter willkürklicher Funktionen einer rellen Veränderlichen. Sitzungsberichte der Akad. zu Berlin, 633–639, 789–805.

Author’s address: Uppsala University, Department of Mathematics,

P. O. Box 480, SE-751 06 Uppsala, Sweden.

Telephone: +46 18 4713216 (office); +46 18 300708 (home) Fax: +46 18 4713201

Electronic mail: kiselman@math.uu.se
URL: http://www.math.uu.se/~kiselman