Weierstrass approximation theorem

Every continuous real-valued function on a compact interval can be approximated by polynomials with arbitrarily small error everywhere on the interval. More precisely, if $a<b$ and $f:[a,b]\to \mathbb{R}$ is continuous, then for every $\epsilon >0$ there is a polynomial $p$ withThe error is measured in the supremum norm, so one approximation works at every point. The degenerate interval $a=b$ needs only a constant function. A change of variable $t=(x-a)/(b-a)$ reduces the nondegenerate case to $[0,1]$.^[ref]

This is useful because a polynomial is described by finitely many coefficients and can be evaluated with addition and multiplication. Its surprise is that the target need not be differentiable: the sharp corner of an absolute value function can be approximated by smooth polynomials. The Bernstein approximation of a corner below makes this visible. Approximating values, however, does not by itself approximate derivatives; Weierstrass approximation does not preserve derivatives gives a counterexample.

On $[0,1]$, the polynomials $p_n(x)=x^n/n$ converge in supremum norm to the zero function, since $\Vert p_n{\Vert }_{\infty }=1/n$. But $p_n^{\prime }(1)=1$ for every $n$, whereas the zero function has left derivative zero at that endpoint. Thus uniform convergence of function values does not imply uniform convergence of derivatives. This does not contradict uniform convergence of Bernstein polynomial derivatives, which has a particular approximation construction and additional differentiability hypotheses.

Starting with $p_0=0$ on $[-1,1]$, this polynomial recurrence gives $0\le p_r(x)\le |x|$ and $p_{r+1}(x)\ge p_r(x)$. Indeed the error satisfies $|x|-p_{r+1}=(|x|-p_r)[1-(|x|+p_r)/2]$. Its pointwise limit solves $p^2=x^2$, so it is $|x|$. Dini's theorem gives uniform convergence. Each continuous piecewise linear function is an affine function plus a finite linear combination of $(x-t{)}_{+}=(x-t+|x-t|)/2$. Scaling and translating the recurrence therefore gives polynomial approximation of every such function, and their density gives the Weierstrass approximation theorem.

For a function $f:[0,1]\to \mathbb{R}$ and an integer $n\ge 1$, its Bernstein polynomial isThe Bernstein basis supplies nonnegative weights whose sum is one. Equivalently, the weights are the probabilities of a binomial distribution, and the result is an expected value. At a given $x$, this averages the sampled values $f(k/n)$ with weights concentrated near $k/n=x$.^[ref]

The endpoints are exact: $B_{n}f(0)=f(0)$ and $B_{n}f(1)=f(1)$. Interior sampled points need not be interpolated. For example, binomial distribution moments give $B_n(x)=x$ and $B_n(x^2)=x^2+x(1-x)/n$. Thus every affine function is reproduced exactly, whereas $x^2$ is generally changed. Bernstein polynomial degree preservation is a statement about degree of a polynomial, not equality of the entire polynomial.

For a continuous $f$, the uniform continuity of $f$ and the variance $\mathrm{Var}(K/n)=x(1-x)/n\le 1/(4n)$ explain uniform convergence. Split the expected value of the error into $|K/n-x|<\delta$, where uniform continuity makes the change small, and its complement, whose probability is at most $1/(4n{\delta }^2)$ by Chebyshev's inequality. The bounded function $f$ bounds the remaining error. This proves convergence without assuming differentiability.

For $f\in C([0,1{]}^d)$, the tensor-product Bernstein polynomial is the expected value of $f(X_1/n,\dots ,X_d/n)$ for independent random variables $X_j\sim \mathrm{Bin}(n,x_j)$. The same uniform continuity and coordinatewise variance estimates give uniform convergence for each fixed finite $d$.

Take the continuous function $f(x)=|x-1/2|$ on $[0,1]$. It is Lipschitz continuous with Lipschitz constant one, but is not differentiable at $x=1/2$. For $n=2$, the sample values are $1/2,0,1/2$, soThis is already a useful warning: the Bernstein polynomial is built from grid values but is not generally their polynomial interpolation.

Every finite approximant is differentiable, and symmetry makes its derivative zero at the center. The target instead has left derivative $-1$ and right derivative $1$. Smooth curves can therefore approach a corner in supremum norm while their center derivatives have no target value to approach. The Lipschitz error bound for Bernstein approximation quantifies the improvement in values.

If $f$ is Lipschitz continuous on $[0,1]$ with Lipschitz constant $L$, then Cauchy-Schwarz inequality and the binomial distribution variance giveThis is an explicit error guarantee, rather than only an existence theorem. For the Bernstein approximation of a corner, choosing $n\ge 2500$ guarantees supremum norm error at most $0.01$; $n>2500$ guarantees error strictly less than $0.01$. The guarantee is sufficient, not optimal.

For this specific target, the error reaches its maximum at $x=1/2$. Indeed the derivative of $B_{n}f$ is a weighted average of the slopes $n[f((k+1)/n)-f(k/n)]$, all in $[-1,1]$: see derivatives of Bernstein polynomials. Subtracting the target makes the error nondecreasing to the left of the corner and nonincreasing to its right. For even $n\ge 2$, the symmetric binomial distribution at $x=1/2$ gives the exact valueThe last equality follows by pairing terms about $n/2$ and telescoping the binomial coefficients. It gives $1/4$ for $n=2$ and $3/16$ for $n=4$.

For $K$ with a binomial distribution of parameters $n,x$, the Bernstein image of a monomial is $B_n(x^m)=\mathbb{E}(K/n{)}^m$. Expand $K^m$ in the monic falling factorial basis. Since $\mathbb{E}{K}^{\underline{r}}=n^{\underline{r}}{x}^r$, the leading coefficient becomes $n^{\underline{m}}/n^m$, which is nonzero for $m\le n$. Thus an actual degree-$m$ polynomial retains its degree, even though its lower coefficients generally change.

Differentiating the Bernstein basis $p_{n,j}(x)=\left(\genfrac{}{}{0ex}{}{n}{j}\right)x^j(1-x{)}^{n-j}$ gives $p_{n,j}^{\prime }=n(p_{n-1,j-1}-p_{n-1,j})$, with out-of-range terms zero. Telescoping coefficient differences and induction give the displayed formula, where $(n{)}_r=n!/(n-r)!$ and $0\le r\le n$. For $n>r$, set $g_{n,r}(t)=(n{)}_r{\Delta }_{1/n}^{r}f((n-r)t/n)$; then $B_n^{(r)}f=B_{n-r}{g}_{n,r}$. The rescaled argument compensates for the different sampling meshes.

For fixed $r$ and $f\in C^r[0,1]$, uniform convergence of normalized finite differences to $f^{(r)}$, uniform continuity of $f^{(r)}$, and $(n{)}_r/n^r\to 1$ imply $g_{n,r}\to f^{(r)}$ uniformly. Positivity and partition of unity make Bernstein polynomials contractions in the supremum norm. Consequently $\Vert B_{n-r}{g}_{n,r}-f^{(r)}{\Vert }_{\infty }\le \Vert g_{n,r}-f^{(r)}{\Vert }_{\infty }+\Vert B_{n-r}{f}^{(r)}-f^{(r)}{\Vert }_{\infty }\to 0$. The differentiability assumption is essential; continuity alone does not define the target derivative.

At the sampling point $j/n$, the polynomial inside the Bernstein polynomial has value $n^{-m}j(j-1)\cdots (j-m+1)$. The falling factorial identity $j^{\underline{m}}\left(\genfrac{}{}{0ex}{}{n}{j}\right)=n^{\underline{m}}\left(\genfrac{}{}{0ex}{}{n-m}{j-m}\right)$ and the binomial theorem prove the displayed formula. For fixed $m$, both the input and its scalar factor tend uniformly to $x^m$ as $n$ grows. The supremum norm contraction of the Bernstein polynomial therefore gives $\Vert B_n(x^m)-x^m{\Vert }_{\infty }\le m(m-1)/n$ for $n\ge m$.

The rounded Bernstein polynomial replaces each coefficient $\left(\genfrac{}{}{0ex}{}{n}{k}\right)f(k/n)$ in the unnormalized basis $x^k(1-x{)}^{n-k}$ by its floor function. It therefore has integer coefficients in the ordinary monomial basis. If $f(0),f(1)\in \mathbb{Z}$, only interior rounding errors remain andTo prove this, bound each interior rounding error by one. On $[0,1/4]$, sum the resulting powers as a geometric series of ratio at most $1/3$ and maximize $x(1-x{)}^{n-1}$; reflect for $[3/4,1]$. On the middle interval each degree-$n$ product is at most $(3/4{)}^n$. integer endpoints are necessary for this convergence: a noninteger endpoint produces a fixed nonzero rounding error there.

For $m\ge 1$ and $n\ge 2$, the Bernstein polynomial of the monomial $x^m$ satisfiesIt follows by applying $k\left(\genfrac{}{}{0ex}{}{n}{k}\right)=n\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$ and expanding $k=(k-1)+1$ with the binomial theorem. The coefficients sum to one; only the first tends to one as $n\to \infty$. Induction on $m$ proves uniform convergence of these monomial approximants, starting from $B_n(1)=1$.

On the fixed finite-dimensional space of polynomials of degree at most $d$, uniform convergence of $B_n$ on each monomial and equivalence of norms in finite dimensions imply ${\epsilon }_n=\Vert B_n-I{\Vert }_{\mathrm{op}}\to 0$. A Neumann series then gives $\Vert B_n^{-1}-I{\Vert }_{\mathrm{op}}\le {\epsilon }_n/(1-{\epsilon }_n)$ for sufficiently large $n$. Consequently the displayed convergence holds. A strictly positive polynomial has positive minimum on the compact interval, so its inverse Bernstein approximants are also strictly positive for all sufficiently large $n$.

These $n+1$ nonnegative polynomials form a basis of polynomials of degree at most $n$, and sum to one on $[0,1]$. For $0\le j\le n$,where ratios for $j=0$ equal one and terms with $k<j$ vanish. The identity follows from $\left(\genfrac{}{}{0ex}{}{n}{k}\right)(k{)}_j/(n{)}_j=\left(\genfrac{}{}{0ex}{}{n-j}{k-j}\right)$ and the binomial theorem. It gives explicit basis coefficients using the falling factorial.

Write $p(x)=a_1{x}^2+2a_{2}x(1-x)+a_3(1-x{)}^2$ on $[0,1]$. Endpoint evaluation gives $a_1=p(1)$ and $a_3=p(0)$, while midpoint evaluation gives $a_2=2p(1/2)-[p(0)+p(1)]/2$. Thus $\Vert p{\Vert }_{\infty }\le 1$ implies $|a_1|,|a_3|\le 1$ and $|a_2|\le 3$. These bounds are sharp: $p(x)=8x^2-8x+1$ has uniform norm one and coefficients $(1,-3,1)$.

If a polynomial $f$ is strictly positive on $[0,1]$, take $g_n=B_n^{-1}f$. By inverse Bernstein approximation on a fixed-degree polynomial space, eventually $g_n>0$ on the interval. Thereforehas strictly positive coefficients. The converse implication to nonnegativity follows immediately because each basis term is nonnegative. Strict positivity is essential for the general existence result: a nonzero polynomial vanishing at an interior point cannot have a nonnegative-coefficient representation in this basis, whose individual terms are positive throughout the open interval.

Write $f={\sum }_k{\beta }_{k,n}{b}_{k,n}$ in the Bernstein basis. Representing the same polynomial at degrees $n$ and $n+1$ gives the displayed convex combinations for internal indices; the endpoint coefficients are copied. Therefore the minimum coefficient cannot decrease under degree elevation. In the unnormalized basis $x^k(1-x{)}^{n-k}$, the elevated coefficients are $c_k^{\prime }=c_{k-1}+c_k$ with the corresponding endpoint convention, so nonnegativity certificates are preserved.