Bernstein polynomial

In the mathematical field of numerical analysis, a Bernstein polynomial, named after Sergei Natanovich Bernstein, is a polynomial in the Bernstein form, that is a linear combination of Bernstein basis polynomials.

A numerically stable way to evaluate polynomials in Bernstein form is de Casteljau's algorithm.

Polynomials in Bernstein form were first used by Bernstein in a constructive proof for the Stone-Weierstrass approximation theorem. With the advent of computer graphics, Bernstein polynomials, restricted to the interval "x" ∈ [0, 1] , became important in the form of Bézier curves.

Definition

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

:$b\_\{\; u,n\}(x)\; =\; \{n\; choose\; u\}\; x^\{\; u\}\; (1-x)^\{n-\; u\},\; qquad\; u=0,ldots,n.$

where $\{n\; choose\; u\}$ is a binomial coefficient.

The Bernstein basis polynomials of degree "n" form a basis for the vector space $Pi\_n$ of polynomials of degree "n".

A linear combination of Bernstein basis polynomials

:

is called a Bernstein polynomial or polynomial in Bernstein form of degree "n". The coefficients β_ν are called Bernstein coefficients or Bézier coefficients.

Example

The first few Bernstein basis polynomials are:$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\; .$

Properties

The Bernstein basis polynomials have the following properties:
*$b\_\{\; u,n\}(x)\; =\; 0$, if &nu; < 0 or &nu; > "n"
*$b\_\{\; u,n\}(0)\; =\; delta\_\{\; u,0\}$ and $b\_\{\; u,n\}(1)\; =\; delta\_\{\; u,n\}$ where $delta$ is the Kronecker delta function.
*$b\_\{\; u,n\}(x)$ has a root with multiplicity &nu; at point "x" = 0 (note if &nu; is 0 there is no root at 0)
*$b\_\{\; u,n\}(x)$ has a root with multiplicity "n" − &nu; at point "x" = 1 (note if &nu; = "n" there is no root at 1)
*$b\_\{\; u,n\}(x)$ &ge; 0 for "x" in [0,1]
*$b\_\{\; u,n\}(1\; -\; x)\; =\; b\_\{n-\; u,n\}(x)$
*The derivative can be written as a combination of two polynomials of lower degree:::$b\text{'}\_\{\; u,n\}(x)\; =\; nleft(b\_\{\; u-1,n-1\}(x)\; -\; b\_\{\; u,n-1\}(x)\; ight)$

*If &nu; &ne; 0, then $b\_\{\; u,n\}(x)$ has a unique local maximum on the interval [0,1] at "x" = &nu;/"n". This maximum takes the value::$u^\{\; u\}n^\{-n\}(n-\; u)^\{n-\; u\}\{nchoose\; u\}.$

*The Bernstein basis polynomials of degree "n" form a partition of unity:

::$sum\_\{\; u=0\}^n\; b\_\{\; u,n\}(x)\; =\; sum\_\{\; u=0\}^n\; \{n\; choose\; u\}\; x^\{\; u\}(1-x)^\{n-\; u\}\; =\; (x+(1-x))^n\; =\; 1.$

*A Bernstein polynomial can always be written as a linear combination of polynomials of higher degree.

::$b\_\{\; u,n-1\}(x)=frac\{n-\; u\}\{n\}b\_\{\; u,n\}(x)+frac\{\; u+1\}\{n\}b\_\{\; u+1,n\}(x).$

Approximating continuous functions

Let "f"("x") be a continuous function on the interval [0, 1] . Consider the Bernstein polynomial

:$B\_n(f)(x)\; =\; sum\_\{\; u=0\}^\{n\}\; fleft(frac\{\; u\}\{n\}\; ight)\; b\_\{\; u,n\}(x).$

It can be shown that :$lim\_\{n\; ightarrowinfty\}\; B\_n(f)(x)=f(x)$

uniformly on the interval [0, 1] . This is a stronger statement than the proposition that the limit holds for each value of "x" separately; that would be pointwise convergence rather than uniform convergence. Specifically, the word "uniformly" signifies that

:$lim\_\{n\; ightarrowinfty\}\; sup\{,left|f(x)-B\_n(f)(x)\; ight|:0leq\; xleq\; 1,\}=0.$

Bernstein polynomials thus afford one way to prove the Stone-Weierstrass approximation theorem that every real-valued continuous function on a real interval ["a","b"] can be uniformly approximated by polynomial functions over R.

A more general statement for a function with continuous k-th derivative is

:$|\; B\_n(f)^\{(k)\}\; |\_infty\; le\; \{(n)\_k\; over\; n^k\}\; |\; f^\{(k)\}\; |\_infty$ and $|f^\{(k)\}-\; B\_n(f)^\{(k)\}\; |\_infty\; ightarrow\; 0,$

where additionally $\{(n)\_k\; over\; n^k\}=\; left(1-\{0\; over\; n\}\; ight)left(1-\{1\; over\; n\}\; ight)\; cdots\; left(1-\{k-1\; over\; n\}\; ight)$ is an eigenvalue of $B\_n$; the corresponding eigenfunction is a polynomial of degree k.

Proof

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 E("K/n") = "x".

Then the weak law of large numbers of probability theory tells us that

:$lim\_\{n\; oinfty\}Pleft(left|frac\{K\}\{n\}-x\; ight|>delta\; ight)=0$

for every $delta\; >\; 0$.

Because "f", being continuous on a closed bounded interval, must be uniformly continuous on that interval, we can infer a statement of the form

:$lim\_\{n\; ightarrowinfty\}\; Pleft(left|f(K/n)-f(x)\; ight|>varepsilon\; ight)=0.$

Consequently

:$lim\_\{n\; ightarrowinfty\}Pleft(left|f(K/n)-E(f(K/n))\; ight|+left|E(f(K/n))-f(x)\; ight|>varepsilon\; ight)=0.$

:$lim\_\{n\; ightarrowinfty\}Pleft(left|fleft(frac\{K\}\{n\}\; ight)-Eleft(fleft(frac\{K\}\{n\}\; ight)\; ight)\; ight|>varepsilon/2\; ight)+Pleft(left|Eleft(fleft(frac\{K\}\{n\}\; ight)\; ight)-f(x)\; ight|>varepsilon/2\; ight)=0.$

And so the second probability above approaches 0 as "n" grows. But the second probability is either 0 or 1, since the only thing that is random is "K", and that appears "within the scope of the expectation operator E". Finally, observe that E("f"("K/n")) is just the Bernstein polynomial "B"_"n"("f","x").

ee also

*Bézier curve
*Polynomial interpolation
*Newton form
*Lagrange form

References

*
*