Bernstein polynomial

The n +1 Bernstein basis polynomials of degree n are defined as

${\displaystyle b_{\nu ,n}(x)\mathrel {:} \mathrel {=} {\binom {n}{\nu }}x^{\nu }\left(1-x\right)^{n-\nu },\quad \nu =0,\ldots ,n,}$

where ${\displaystyle {\tbinom {n}{\nu }}}$ is a binomial coefficient.

So, for example, ${\displaystyle b_{2,5}(x)={\tbinom {5}{2}}x^{2}(1-x)^{3}=10x^{2}(1-x)^{3}.}$

The first few Bernstein basis polynomials for blending 1, 2, 3 or 4 values together are:

${\displaystyle {\begin{aligned}b_{0,0}(x)&=1,\\b_{0,1}(x)&=1-x,&b_{1,1}(x)&=x\\b_{0,2}(x)&=(1-x)^{2},&b_{1,2}(x)&=2x(1-x),&b_{2,2}(x)&=x^{2}\\b_{0,3}(x)&=(1-x)^{3},&b_{1,3}(x)&=3x(1-x)^{2},&b_{2,3}(x)&=3x^{2}(1-x),&b_{3,3}(x)&=x^{3}\end{aligned}}}$

The Bernstein basis polynomials of degree n form a basis for the vector space ${\displaystyle \Pi _{n}}$ of polynomials of degree at most n with real coefficients.

A linear combination of Bernstein basis polynomials

${\displaystyle B_{n}(x)\mathrel {:} \mathrel {=} \sum _{\nu =0}^{n}\beta _{\nu }b_{\nu ,n}(x)}$

is called a Bernstein polynomial or polynomial in Bernstein form of degree n.[1] The coefficients ${\displaystyle \beta _{\nu }}$ are called Bernstein coefficients or Bézier coefficients.

The first few Bernstein basis polynomials from above in monomial form are:

${\displaystyle {\begin{aligned}b_{0,0}(x)&=1,\\b_{0,1}(x)&=1-1x,&b_{1,1}(x)&=0+1x\\b_{0,2}(x)&=1-2x+1x^{2},&b_{1,2}(x)&=0+2x-2x^{2},&b_{2,2}(x)&=0+0x+1x^{2}\\b_{0,3}(x)&=1-3x+3x^{2}-1x^{3},&b_{1,3}(x)&=0+3x-6x^{2}+3x^{3},&b_{2,3}(x)&=0+0x+3x^{2}-3x^{3},&b_{3,3}(x)&=0+0x+0x^{2}+1x^{3}\end{aligned}}}$

This proof follows Bernstein's original proof of 1912.[8] See also Feller (1966) or Koralov & Sinai (2007).[9][10]

Suppose K is a random variable distributed as the number of successes in n independent Bernoulli trials with probability x of success on each trial; in other words, K has a binomial distribution with parameters n and x. Then we have the expected value ${\displaystyle \operatorname {\mathcal {E}} \left[{\frac {K}{n}}\right]=x\ }$ and

${\displaystyle p(K)={n \choose K}x^{K}\left(1-x\right)^{n-K}=b_{K,n}(x)}$

By the weak law of large numbers of probability theory,

${\displaystyle \lim _{n\to \infty }{P\left(\left|{\frac {K}{n}}-x\right|>\delta \right)}=0}$

for every δ > 0. Moreover, this relation holds uniformly in x, which can be seen from its proof via Chebyshev's inequality, taking into account that the variance of 1⁄n K, equal to 1⁄n x(1−x), is bounded from above by 1⁄(4n) irrespective of x.

Because ƒ, being continuous on a closed bounded interval, must be uniformly continuous on that interval, one infers a statement of the form

${\displaystyle \lim _{n\to \infty }{P\left(\left|f\left({\frac {K}{n}}\right)-f\left(x\right)\right|>\varepsilon \right)}=0}$

uniformly in x. Taking into account that ƒ is bounded (on the given interval) one gets for the expectation

${\displaystyle \lim _{n\to \infty }{\operatorname {\mathcal {E}} \left(\left|f\left({\frac {K}{n}}\right)-f\left(x\right)\right|\right)}=0}$

uniformly in x. To this end one splits the sum for the expectation in two parts. On one part the difference does not exceed ε; this part cannot contribute more than ε. On the other part the difference exceeds ε, but does not exceed 2M, where M is an upper bound for |ƒ(x)|; this part cannot contribute more than 2M times the small probability that the difference exceeds ε.

Finally, one observes that the absolute value of the difference between expectations never exceeds the expectation of the absolute value of the difference, and

${\displaystyle \operatorname {\mathcal {E}} \left[f\left({\frac {K}{n}}\right)\right]=\sum _{K=0}^{n}f\left({\frac {K}{n}}\right)p(K)=\sum _{K=0}^{n}f\left({\frac {K}{n}}\right)b_{K,n}(x)=B_{n}(f)(x)}$

The probabilistic proof can also be rephrased in an elementary way, using the underlying probabilistic ideas but proceeding by direct verification:[11][12][13][14][15]

The following identities can be verified:

1. ${\displaystyle \sum _{k}{n \choose k}x^{k}(1-x)^{n-k}=1}$ ("probability")
2. ${\displaystyle \sum _{k}{k \over n}{n \choose k}x^{k}(1-x)^{n-k}=x}$ ("mean")
3. ${\displaystyle \sum _{k}\left(x-{k \over n}\right)^{2}{n \choose k}x^{k}(1-x)^{n-k}={x(1-x) \over n}.}$ ("variance")

In fact, by the binomial theorem

$${\displaystyle (1+t)^{n}=\sum _{k}{n \choose k}t^{k},}$$

and this equation can be applied twice to ${\displaystyle t{\frac {d}{dt}}}$. The identities (1), (2), and (3) follow easily using the substitution ${\displaystyle t=x/(1-x)}$.

Within these three identities, use the above basis polynomial notation

${\displaystyle b_{k,n}(x)={n \choose k}x^{k}(1-x)^{n-k},}$

and let

${\displaystyle f_{n}(x)=\sum _{k}f(k/n)\,b_{k,n}(x).}$

Thus, by identity (1)

${\displaystyle f_{n}(x)-f(x)=\sum _{k}[f(k/n)-f(x)]\,b_{k,n}(x),}$

so that

${\displaystyle |f_{n}(x)-f(x)|\leq \sum _{k}|f(k/n)-f(x)|\,b_{k,n}(x).}$

Since f is uniformly continuous, given ${\displaystyle \varepsilon >0}$, there is a ${\displaystyle \delta >0}$ such that ${\displaystyle |f(a)-f(b)|<\varepsilon }$ whenever ${\displaystyle |a-b|<\delta }$. Moreover, by continuity, ${\displaystyle M=\sup |f|<\infty }$. But then

${\displaystyle |f_{n}(x)-f(x)|\leq \sum _{|x-{k \over n}|<\delta }|f(k/n)-f(x)|\,b_{k,n}(x)+\sum _{|x-{k \over n}|\geq \delta }|f(k/n)-f(x)|\,b_{k,n}(x).}$

The first sum is less than ε. On the other hand, by identity (3) above, and since ${\displaystyle |x-k/n|\geq \delta }$, the second sum is bounded by ${\displaystyle 2M}$ times

${\displaystyle \sum _{|x-k/n|\geq \delta }b_{k,n}(x)\leq \sum _{k}\delta ^{-2}\left(x-{k \over n}\right)^{2}b_{k,n}(x)=\delta ^{-2}{x(1-x) \over n}<{1 \over 4}\delta ^{-2}n^{-1}.}$

(Chebyshev's inequality)

It follows that the polynomials f_n tend to f uniformly.