The Weierstrass approximation theorem

Power series show that analytic functions are uniform limits of polynomials on closed subintervals of their interval of convergence. But most continuous functions are not analytic, and many are not differentiable anywhere. It is a remarkable fact, proved by Karl Weierstrass in 1885, that every continuous function on a closed bounded interval is nevertheless a uniform limit of polynomials. This lesson proves the theorem using the polynomials that Sergei Bernstein introduced in 1912, and explores its consequences.

The statement

Theorem 6.1 (Weierstrass approximation theorem). Let \(f: [a, b] \to \mathbb{R}\) be continuous. For every \(\varepsilon > 0\) there is a polynomial \(p\) with \[|f(x) - p(x)| < \varepsilon \quad \text{for all } x \in [a, b].\] Equivalently, there is a sequence of polynomials converging uniformly to \(f\) on \([a, b]\).

In the language of lesson 1, the polynomials are dense in the space \(C[a, b]\) of continuous functions with the sup distance: every point of the space can be approached as closely as we like by polynomials. The statement is about uniform approximation on a closed bounded interval, and both features matter. A polynomial that approximates \(f\) uniformly need not be its Taylor polynomial, and need not have anything to do with derivatives of \(f\), which may not exist.

It is enough to prove the theorem on \([0, 1]\). If \(f\) is continuous on \([a, b]\), then \(g(t) = f(a + t(b - a))\) is continuous on \([0, 1]\); if \(q\) is a polynomial with \(|g - q| < \varepsilon\) on \([0, 1]\), then \(p(x) = q(\frac{x - a}{b - a})\) is a polynomial with \(|f - p| < \varepsilon\) on \([a, b]\).

Bernstein polynomials

Definition. For a function \(f\) on \([0, 1]\) and \(n \ge 1\), the \(n\)-th Bernstein polynomial of \(f\) is \[B_n f(x) = \sum_{k=0}^{n} f\Big(\frac{k}{n}\Big)\binom{n}{k}x^k(1 - x)^{n-k}.\]

Write \(p_{n,k}(x) = \binom{n}{k}x^k(1 - x)^{n-k}\). Bernstein's idea was probabilistic. If a coin landing heads with probability \(x\) is tossed \(n\) times, \(p_{n,k}(x)\) is the probability of exactly \(k\) heads. The fraction of heads \(\frac{k}{n}\) is very likely to be close to \(x\) when \(n\) is large, by the law of large numbers, so the average \(B_n f(x)\) of the values \(f(\frac{k}{n})\), weighted by these probabilities, should be close to \(f(x)\). The proof turns this into precise estimates, and needs three identities.

Lemma 6.2. For every \(x\) and \(n \ge 1\): \[\text{(a)}\ \sum_{k=0}^{n} p_{n,k}(x) = 1, \qquad \text{(b)}\ \sum_{k=0}^{n} k\,p_{n,k}(x) = nx, \qquad \text{(c)}\ \sum_{k=0}^{n} (k - nx)^2 p_{n,k}(x) = nx(1 - x).\]

Proof. (a) is the binomial theorem: \(\sum_k \binom{n}{k}x^k(1 - x)^{n-k} = (x + (1 - x))^n = 1\). For (b), use \(k\binom{n}{k} = n\binom{n-1}{k-1}\) for \(k \ge 1\): \[\sum_{k=1}^{n} k\binom{n}{k}x^k(1 - x)^{n-k} = nx\sum_{k=1}^{n}\binom{n-1}{k-1}x^{k-1}(1 - x)^{n-k} = nx(x + 1 - x)^{n-1} = nx.\] In the same way \(k(k - 1)\binom{n}{k} = n(n - 1)\binom{n-2}{k-2}\) for \(k \ge 2\) gives \(\sum_k k(k - 1)p_{n,k}(x) = n(n - 1)x^2\). Hence \(\sum_k k^2 p_{n,k} = n(n - 1)x^2 + nx\), and expanding the square in (c), \[\sum_k (k - nx)^2 p_{n,k} = n(n - 1)x^2 + nx - 2nx\cdot nx + n^2x^2 = nx - nx^2 = nx(1 - x). \quad \square\]

In probabilistic language, (b) and (c) say that the number of heads has mean \(nx\) and variance \(nx(1 - x)\).

The proof

Theorem 6.3 (Bernstein, 1912). If \(f\) is continuous on \([0, 1]\), then \(B_n f \to f\) uniformly on \([0, 1]\).

Proof. Since \([0, 1]\) is closed and bounded, \(f\) is bounded, say \(|f| \le M\), and uniformly continuous, by the extreme value and Heine–Cantor theorems of MATH-241. Let \(\varepsilon > 0\) and choose \(\delta > 0\) such that \(|f(s) - f(t)| < \varepsilon\) whenever \(|s - t| < \delta\). Fix \(x \in [0, 1]\). By identity (a), \(f(x) = \sum_k f(x)p_{n,k}(x)\), so \[|B_n f(x) - f(x)| = \Big|\sum_{k=0}^{n}\Big(f\Big(\frac{k}{n}\Big) - f(x)\Big)p_{n,k}(x)\Big| \le \sum_{k=0}^{n}\Big|f\Big(\frac{k}{n}\Big) - f(x)\Big|\,p_{n,k}(x),\] using \(p_{n,k}(x) \ge 0\). Split the sum into the indices with \(|\frac{k}{n} - x| < \delta\) and those with \(|\frac{k}{n} - x| \ge \delta\).

For the first group, each \(|f(\frac{k}{n}) - f(x)| < \varepsilon\), so their contribution is at most \(\varepsilon\sum_k p_{n,k}(x) = \varepsilon\).

For the second group, each \(|f(\frac{k}{n}) - f(x)| \le 2M\), and \(|k - nx| \ge n\delta\), so \(1 \le \frac{(k - nx)^2}{n^2\delta^2}\). Therefore their contribution is at most \[2M\sum_{|k/n - x| \ge \delta} p_{n,k}(x) \le \frac{2M}{n^2\delta^2}\sum_{k=0}^{n}(k - nx)^2 p_{n,k}(x) = \frac{2M\,x(1 - x)}{n\delta^2} \le \frac{M}{2n\delta^2},\] by identity (c) and \(x(1 - x) \le \frac{1}{4}\).

Together, \(|B_n f(x) - f(x)| \le \varepsilon + \frac{M}{2n\delta^2}\) for every \(x \in [0, 1]\). The right side does not depend on \(x\), and it is less than \(2\varepsilon\) once \(n > \frac{M}{2\delta^2\varepsilon}\). So \(\|B_n f - f\|_\infty \to 0\). \(\square\)

Each \(B_n f\) is a polynomial of degree at most \(n\), so theorem 6.3 proves theorem 6.1 on \([0, 1]\), and the rescaling above proves it on every \([a, b]\). The estimate in the second group is Chebyshev's inequality from probability, in disguise: the weight that the binomial distribution puts more than \(\delta\) away from its mean is at most the variance divided by \(\delta^2\).

Bernstein polynomials in practice

The proof is constructive: it tells us how to build the approximating polynomial and how large \(n\) must be. The code approximates \(|x|\) on \([-1, 1]\). After the change of variable \(x = 2t - 1\) this is the function \(g(t) = |2t - 1|\) on \([0, 1]\), and the worst error turns out to be at the corner \(t = \frac{1}{2}\).

import math

def bernstein(f, n, t):
    """B_n f(t) = sum f(k/n) C(n,k) t^k (1-t)^(n-k), with weights from logarithms to avoid overflow."""
    if t in (0.0, 1.0):
        return f(t)
    total = 0.0
    for k in range(n + 1):
        logw = (math.lgamma(n + 1) - math.lgamma(k + 1) - math.lgamma(n - k + 1)
                + k * math.log(t) + (n - k) * math.log(1 - t))
        total += f(k / n) * math.exp(logw)
    return total

g = lambda t: abs(2 * t - 1)               # |x| on [-1, 1] with x = 2t - 1
grid = [i / 400 for i in range(401)]
print("   n    error at x = 0   sup error on grid   sqrt(2/(pi n))   error at x = 0.5")
for n in [4, 16, 64, 256, 1024]:
    errs = [abs(bernstein(g, n, t) - g(t)) for t in grid]
    e0 = abs(bernstein(g, n, 0.5) - g(0.5))
    e5 = abs(bernstein(g, n, 0.75) - g(0.75))
    print(f"{n:5d}   {e0:12.5f}     {max(errs):12.5f}      {math.sqrt(2 / (math.pi * n)):12.5f}    {e5:12.2e}")

   n    error at x = 0   sup error on grid   sqrt(2/(pi n))   error at x = 0.5
    4        0.37500          0.37500           0.39894        5.47e-02
   16        0.19638          0.19638           0.19947        2.36e-03
   64        0.09935          0.09935           0.09974        4.04e-07
  256        0.04982          0.04982           0.04987        2.30e-14
 1024        0.02493          0.02493           0.02493        2.31e-13

The error at the corner decreases like \(\sqrt{\frac{2}{\pi n}}\), so quadrupling the degree only halves the error, and away from the corner it is much smaller. Bernstein polynomials converge slowly, roughly like \(\frac{1}{n}\) even for smooth functions, which is why numerical analysts use other constructions, such as interpolation at Chebyshev points, when efficiency matters. Their virtue is the clean, complete proof, and properties such as preserving monotonicity and convexity that make them useful in computer graphics, where they underlie Bézier curves.

Approximation is not interpolation

A natural first idea for proving the Weierstrass theorem is to take the polynomial of degree \(n\) that agrees with \(f\) at \(n + 1\) equally spaced points and let \(n \to \infty\). This does not work. In 1901 Carl Runge showed that for \(f(x) = \frac{1}{1 + 25x^2}\) on \([-1, 1]\), an analytic function, the interpolating polynomials at equally spaced nodes oscillate more and more wildly near the endpoints, and their sup distance from \(f\) tends to infinity. Interpolation at the Chebyshev points \(\cos\frac{(2j + 1)\pi}{2n + 2}\), which cluster near the endpoints, behaves much better and converges rapidly for smooth functions, but Georg Faber proved in 1914 that no fixed scheme of interpolation nodes converges for every continuous function.

Bernstein polynomials avoid the problem because they do not interpolate: \(B_nf\) agrees with \(f\) only at the endpoints, in general, and is an average of the values \(f(\frac{k}{n})\) with positive weights. Positivity is what makes the proof work. An average of values that are all close to \(f(x)\) is close to \(f(x)\), and the weights far from \(x\) are small; an interpolating polynomial, in contrast, can be written as a combination of the values \(f(x_j)\) with weights of both signs and large total size, so small errors at the nodes can be amplified enormously between them.

History

Weierstrass published the theorem in 1885, at the age of 70, in a paper on the representation of 'arbitrary' functions. His proof smoothed \(f\) by convolving it with the Gaussian kernel \(\frac{1}{\sqrt{\pi}t}e^{-(x/t)^2}\), which produces an entire function close to \(f\), and then truncated its power series. In the following decades many other proofs appeared. Henri Lebesgue's first paper, in 1898, reduced the theorem to approximating the single function \(|x|\); Lipót Fejér proved the trigonometric analog in 1900 using averages of Fourier partial sums; and Bernstein's 1912 proof, given here, was one of the first applications of probability to pure analysis. In 1937 Marshall Stone proved a far-reaching generalization, now called the Stone–Weierstrass theorem, which he simplified in 1948.

The Stone–Weierstrass theorem says that if \(K\) is a compact metric space and \(\mathcal{A}\) is a collection of continuous real functions on \(K\) that is closed under addition, multiplication and multiplication by constants, contains the constants, and separates points, in the sense that for \(x \ne y\) some \(g \in \mathcal{A}\) has \(g(x) \ne g(y)\), then every continuous function on \(K\) is a uniform limit of functions in \(\mathcal{A}\). Polynomials on \([a, b]\) satisfy these conditions, and so do polynomials in several variables on a closed bounded set in \(\mathbb{R}^n\), and trigonometric polynomials on the circle. Its proof belongs to a later course.

Consequences

Two further remarks. First, the Weierstrass theorem says nothing about derivatives: a polynomial uniformly close to \(f\) can have a wildly different derivative, as it must when \(f\) is nowhere differentiable. Second, the theorem gives a short proof of a fact used in lesson 9: the space \(C[a, b]\) with the sup distance is separable, meaning it has a countable dense subset, namely the polynomials with rational coefficients. Indeed, any polynomial on \([a, b]\) is uniformly approximated by one with rational coefficients, obtained by rounding each coefficient.