7.3 Univariate Bernstein Polynomials

The Weierstraß approximation theorem (Theorem A.10 and Theorem A.12) states that continuous functions on compact intervals can be arbitrarily well approximated by polynomials.

One usually finds non-constructive proofs in text books and the question how to determine these polynomials remains. One constructive way to obtain such polynomials are Bernstein polynomials which were first introduced by Sergei N. Bernstein in the univariate case. A generalization to multidimensional intervals and its properties are presented in the next section. Generalizations to multidimensional simplices using barycentric coordinates and other properties of Bernstein polynomials can be found e.g. in [67,12,109,108,5,35,96].

In this section we concern ourselves with univariate Bernstein polynomials. In order to keep the formulas simple we only consider functions on the interval $[0,1]$. Using the isomorphism $\phi: [a,b]\to[0,1]$, $\phi(x):=(x-a)/(b-a)$ the results can immediately be applied to arbitrary compact intervals $[a,b]$.

The Bernstein polynomials are defined as follows.

Definition 7..1 (Bernstein Polynomials)   Let $n\in\mathbb{N}$ and $f$ be a function. The polynomials

$$B_{f,n}(x):=\sum_{k=0}^n f\left({k\over n}\right) {n\choose k} x^k (1-x)^{n-k}$$

are called the Bernstein polynomials of $f$.

This theorem is due to Sergei N. Bernstein.

Theorem 7..2 (Bernstein)   Let $f: [0,1]\to\mathbb{R}$ be a continuous function. Then the Bernstein polynomials $B_{f,n}$ converge uniformly to $f$ for $n\to\infty$.

A proof can be found in [12,67]. We will give a proof of the multivariate counterpart (Theorem 7.10). If $f$ even satisfies a Lipschitz condition, the following stronger result can be shown giving an error bound.

Theorem 7..3   If $f: [0,1]\to\mathbb{R}$ is a continuous function satisfying the Lipschitz condition $\vert f(x)-f(y)\vert < L \vert x-y\vert$ on $(0,1)$, then the inequality

$$\vert B_{f,n}(x)-f(x)\vert < {L \over 2\sqrt{n}}$$

holds.

Theorem 7..4   If $f\in C[0,1]$ has a finite second order derivative $f''(x)$ at $x$, then

$$B_{f,n}(x)-f(x)={f''(x)\over2n} x(1-x) + {\delta(n)\over n},$$

where $\delta(n)\to 0$ for $n\to\infty$.

This implies that the order of convergence of $B_{f,n}$ to  $f\in C[0,1]$ cannot be greater than $1/n$ unless $f$ is a linear function.

Finally it is important to note that also the derivatives of the Bernstein polynomials converge uniformly to those of the given function. This is especially important for optimization tasks.

Theorem 7..5   If $f\in C[0,1]$ has a continuous $i$-th order derivative $f^{(i)}(x)$ on $(0,1)$, then $B_{f,n}^{(i)}(x)$ converges uniformly to $f^{(i)}(x)$ on $(0,1)$.