6.7. The Weierstrass Approximation Theorem

In part 4.5. we already used the Lagrange interpolating polynomials to connect given points in the xy-plane. The main issue then however was to capture finitely many values exactly. If these values are values of a function we normally have no idea how acurate its other values are hit.. This part now will prove that polynomials are able to match any continuous function on a closed interval with arbitrary acuracy within the whole range. K. Weierstrass proved this approximation behaviour in 1886, the constructive proof presented here however is due to S. N. Bernstein and originates from 1912.

Theorem (Weierstrass approximation theorem): For any

f \in C^{0} ([a, b])

and any

ε > 0

there is a polynomial p such that

| f (x) - p (x) | < ε for all x \in [a, b]

[6.7.1]

At first we only consider the interval $[0,1]$ . It will be sufficient to carry out the essential prove for this special interval. To this end we construct a sequence of polynomials $(B_{n} f)$ which converges on $[0,1]$ uniformly to f, thus a sequence which allows an $n_{0} \in ℕ^{*}$ for each $ε > 0$ such that

| f (x) - B_{n} f (x) | < ε for all n \geq n_{0} and all x \in [0,1]

[6.7.2]

$B_{n_{0}} f$ for example would then be a polynomial to prove the Weierstrass theorem.

We now introduce the approximating polynomials using the binomial coefficients $(\begin{matrix} n \\ k \end{matrix})$ .

Definition: Let $f : [0,1] \to ℝ$ be any function. For an arbitrary $n \in ℕ^{*}$ we call

B_{n} f ≔ \sum_{k = 0}^{n} f (\frac{k}{n}) (\begin{matrix} n \\ k \end{matrix}) X^{k} {(1 - X)}^{n - k}

[6.7.3]

the n-th Bernstein polynomial of f.

The first Bernstein polynomials for an arbitrary f are easily calculated:

$\begin{array}{l} B_{1} f & = f (\frac{0}{1}) (\begin{matrix} 1 \\ 0 \end{matrix}) X^{0} {(1 - X)}^{1} + f (\frac{1}{1}) (\begin{matrix} 1 \\ 1 \end{matrix}) X^{1} {(1 - X)}^{0} \\ = (f (1) - f (0)) X + f (0) \end{array}$
$\begin{array}{l} B_{2} f & = f (\frac{0}{2}) (\begin{matrix} 2 \\ 0 \end{matrix}) X^{0} {(1 - X)}^{2} + f (\frac{1}{2}) (\begin{matrix} 2 \\ 1 \end{matrix}) X^{1} {(1 - X)}^{1} + f (\frac{2}{2}) (\begin{matrix} 2 \\ 2 \end{matrix}) X^{2} {(1 - X)}^{0} \\ = (f (0) - 2 f (\frac{1}{2}) + f (1)) X^{2} + 2 (- f (0) + f (\frac{1}{2})) X + f (0) \end{array}$

With the function $| X - \frac{1}{2} |$ e.g. we have $B_{1} | X - \frac{1}{2} | = \frac{1}{2}$ and $B_{2} | X - \frac{1}{2} | = X^{2} - X + \frac{1}{2}$ .

To prove [6.7.2] we need some conclusions from the generalized binomial theorem:

{(a + b)}^{n} = \sum_{k = 0}^{n} (\begin{matrix} n \\ k \end{matrix}) a^{n - k} b^{k}

Proposition: For all $n \in ℕ^{*}$ and each $x \in ℝ$ we have

$\sum_{k = 0}^{n} (\begin{matrix} n \\ k \end{matrix}) x^{k} {(1 - x)}^{n - k} = 1$

[6.7.4]

$\sum_{k = 0}^{n} k (\begin{matrix} n \\ k \end{matrix}) x^{k} {(1 - x)}^{n - k} = n x$

[6.7.5]

$\sum_{k = 0}^{n} k (k - 1) (\begin{matrix} n \\ k \end{matrix}) x^{k} {(1 - x)}^{n - k} = n (n - 1) x^{2}$

[6.7.6]

$\sum_{k = 0}^{n} k^{2} (\begin{matrix} n \\ k \end{matrix}) x^{k} {(1 - x)}^{n - k} = n x - n x^{2} + n^{2} x^{2}$

[6.7.7]

$\sum_{k = 0}^{n} {(k - n x)}^{2} (\begin{matrix} n \\ k \end{matrix}) x^{k} {(1 - x)}^{n - k} \leq \frac{n}{4}$

[6.7.8]

Proof:
1. ► The assertion results immediately from the generalized binomial theorem:

\sum_{k = 0}^{n} (\begin{matrix} n \\ k \end{matrix}) x^{k} {(1 - x)}^{n - k} = {(x + 1 - x)}^{n} = 1

2. ► If $n = 1$ there is nothing to show in essence. If $n > 1$ we quote [6.7.4] with $n - 1$ and calculate as follows (note the index shift):

\begin{array}{l} n x & = n x \sum_{k = 0}^{n - 1} (\begin{matrix} n - 1 \\ k \end{matrix}) x^{k} {(1 - x)}^{n - 1 - k} \\ = \sum_{k = 0}^{n - 1} \frac{n!}{k! (n - 1 - k)!} x^{k + 1} {(1 - x)}^{n - k - 1} \\ = \sum_{k = 1}^{n} \frac{n!}{(k - 1)! (n - k)!} x^{k} {(1 - x)}^{n - k} \\ = \sum_{k = 1}^{n} k \frac{n!}{k! (n - k)!} x^{k} {(1 - x)}^{n - k} \\ = \sum_{k = 0}^{n} k (\begin{matrix} n \\ k \end{matrix}) x^{k} {(1 - x)}^{n - k} \end{array}

3. ► Only $n > 2$ is non trivial and in that case we proceed similar as before:

\begin{array}{l} n (n - 1) x^{2} & = n (n - 1) x^{2} \sum_{k = 0}^{n - 2} (\begin{matrix} n - 2 \\ k \end{matrix}) x^{k} {(1 - x)}^{n - 2 - k} \\ = \sum_{k = 0}^{n - 2} \frac{n!}{k! (n - 2 - k)!} x^{k + 2} {(1 - x)}^{n - 2 - k} \\ = \sum_{k = 2}^{n} \frac{n!}{(k - 2)! (n - k)!} x^{k} {(1 - x)}^{n - k} \\ = \sum_{k = 2}^{n} k (k - 1) \frac{n!}{k! (n - k)!} x^{k} {(1 - x)}^{n - k} \\ = \sum_{k = 0}^{n} k (k - 1) (\begin{matrix} n \\ k \end{matrix}) x^{k} {(1 - x)}^{n - k} \end{array}

4. ► We just need to join [6.7.5] and [6.7.6]:

\begin{array}{l} n x - n x^{2} + n^{2} x^{2} & = n x + n (n - 1) x^{2} \\ = \sum_{k = 0}^{n} k (\begin{matrix} n \\ k \end{matrix}) x^{k} {(1 - x)}^{n - k} + \sum_{k = 0}^{n} k (k - 1) (\begin{matrix} n \\ k \end{matrix}) x^{k} {(1 - x)}^{n - k} \\ = \sum_{k = 0}^{n} (k + k (k - 1)) (\begin{matrix} n \\ k \end{matrix}) x^{k} {(1 - x)}^{n - k} \\ = \sum_{k = 0}^{n} k^{2} (\begin{matrix} n \\ k \end{matrix}) x^{k} {(1 - x)}^{n - k} \end{array}

5. ► For all x we have $0 \leq {(2 x - 1)}^{2} = 4 x^{2} - 4 x + 1 \Leftrightarrow 4 x (1 - x) \leq 1$ . Thus:

x (1 - x) \leq \frac{1}{4}

This estimate and the results obtained so far now yield:

\begin{array}{l} \sum_{k = 0}^{n} {(k - n x)}^{2} (\begin{matrix} n \\ k \end{matrix}) x^{k} {(1 - x)}^{n - k} \\ = & \sum_{k = 0}^{n} k^{2} (\begin{matrix} n \\ k \end{matrix}) x^{k} {(1 - x)}^{n - k} - 2 n x \sum_{k = 0}^{n} k (\begin{matrix} n \\ k \end{matrix}) x^{k} {(1 - x)}^{n - k} + n^{2} x^{2} \sum_{k = 0}^{n} (\begin{matrix} n \\ k \end{matrix}) x^{k} {(1 - x)}^{n - k} \\ = & n x - n x^{2} + n^{2} x^{2} - 2 n x \cdot n x + n^{2} x^{2} \\ = & n x (1 - x) \\ \leq & \frac{n}{4} \end{array}

Now we are prepared to prove version [6.7.2] of the Weierstrass theorem. For any $f \in C^{0} ([a, b])$ and any $ε > 0$ we have to find an $n_{0} \in ℕ^{*}$ such that

| f (x) - B_{n} f (x) | < ε for all n \geq n_{0} and every x \in [0,1]

We may abbreviate $m ≔ \sup {f (x) | x \in [0,1]}$ as f is bounded on $[0,1]$ according to [6.6.4]. As f is uniformly continuous on $[0,1]$ (see [6.5.5]) there is a $δ > 0$ such that

| f (x) - f (y) | < \frac{ε}{2} for all x \in [0,1] satisfying | x - y | < δ

[1]

Using the equality $f (x) = f (x) \sum_{k = 0}^{n} (\begin{matrix} n \\ k \end{matrix}) x^{k} {(1 - x)}^{n - k} = \sum_{k = 0}^{n} f (x) (\begin{matrix} n \\ k \end{matrix}) x^{k} {(1 - x)}^{n - k}$ (see [6.7.4]) as well as the triangle inequality we see that every n holds the estimate

| f (x) - B_{n} f (x) | \leq \sum_{k = 0}^{n} | f (x) - f (\frac{k}{n}) | (\begin{matrix} n \\ k \end{matrix}) x^{k} {(1 - x)}^{n - k}

[2]

For a fixed x we now split the addends involved into two disjoint lots:

\begin{array}{l} A ≔ {k \in {0, \dots, n} | | x - \frac{k}{n} | < δ} \\ B ≔ {k \in {0, \dots, n} | | x - \frac{k}{n} | \geq δ} \end{array}

If $k \in A$ we have $| f (x) - f (\frac{k}{n}) | < \frac{ε}{2}$ due to [1] For $A \neq \emptyset$ we thus may estimate as follows (In case $A = \emptyset$ [3] is valid as well as the empty sum's value equals 0):

\begin{array}{l} \sum_{k \in A} | f (x) - f (\frac{k}{n}) | (\begin{matrix} n \\ k \end{matrix}) x^{k} {(1 - x)}^{n - k} \\ < & \sum_{k \in A} \frac{ε}{2} (\begin{matrix} n \\ k \end{matrix}) x^{k} {(1 - x)}^{n - k} \\ = & \frac{ε}{2} \sum_{k \in A} (\begin{matrix} n \\ k \end{matrix}) x^{k} {(1 - x)}^{n - k} = \frac{ε}{2} \end{array}

[3]

If $k \in B$ the equivalence $| \frac{k}{n} - x | \geq δ \Leftrightarrow \frac{{(k - n x)}^{2}}{n^{2}} \geq δ^{2} \Leftrightarrow \frac{{(k - n x)}^{2}}{n^{2} δ^{2}} \geq 1$ allows to employ [6.7.8]:

\begin{array}{l} \sum_{k \in B} | f (x) - f (\frac{k}{n}) | (\begin{matrix} n \\ k \end{matrix}) x^{k} {(1 - x)}^{n - k} \\ \leq & 2 m \sum_{k \in B} (\begin{matrix} n \\ k \end{matrix}) x^{k} {(1 - x)}^{n - k} \\ \leq & 2 m \sum_{k \in B} \frac{{(k - n x)}^{2}}{n^{2} δ^{2}} (\begin{matrix} n \\ k \end{matrix}) x^{k} {(1 - x)}^{n - k} \\ = & \frac{2 m}{n^{2} δ^{2}} \sum_{k \in B} {(k - n x)}^{2} (\begin{matrix} n \\ k \end{matrix}) x^{k} {(1 - x)}^{n - k} \\ \leq & \frac{2 m}{n^{2} δ^{2}} \sum_{k = 0}^{n} {(k - n x)}^{2} (\begin{matrix} n \\ k \end{matrix}) x^{k} {(1 - x)}^{n - k} \\ \leq & \frac{2 m}{n^{2} δ^{2}} \cdot \frac{n}{4} = \frac{m}{2 n δ^{2}} \end{array}

[4]

Choosing now a natural number $n_{0} > \frac{m}{ε δ^{2}}$ and employing [3] and [4] we may, for $n \geq n_{0}$ , extend the estimate [2] to

| f (x) - B_{n} f (x) | < \frac{ε}{2} + \frac{m}{2 n δ^{2}} \leq \frac{ε}{2} + \frac{ε}{2} = ε

Thus the Weierstrass theorem is valid for the interval $[0,1]$ . The general case is easily reduced to this special one:

For an arbitrary interval $[a, b]$ we consider the linear (and thus continuous) function $g ≔ (b - a) X + a$ . It is a bijection from $[0,1]$ to $[a, b]$ with $f \in C^{0} ([a, b])$ being equivalent to $f \circ g \in C^{0} ([0,1])$ . Thus for any $ε > 0$ there is a polynomial p such that

| f \circ g (x) - p (x) | < ε for all x \in [0,1]

[5]

As the inverse of g is linear the function $p \circ g^{- 1}$ is a polynomial as well. The equivalence of $x \in [a, b]$ and $g^{- 1} (x) \in [0,1]$ now allows to restate [5] as follows:

| f (x) - p \circ g^{- 1} (x) | = | f \circ g (g^{- 1} (x)) - p (g^{- 1} (x)) | < ε for all x \in [a, b]

The applet below creates and illustrates the Bernstein polynomials for three selected functions.

6.6. 6.8.