Bernstein polynomial

From Wikipedia, the free encyclopedia

For the Bernstein polynomial in D-module theory, see Bernstein-Sato polynomial.

Bernstein polynomials approximating a curve

In the mathematical subfield 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.

1 Definition
2 Notes
3 Example
4 Approximating continuous functions
5 Proof
6 See also
7 References

[edit] Definition

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

$b_{\nu,n}(x) = {n \choose \nu} x^{\nu} (1-x)^{n-\nu}, \qquad \nu=0,\ldots,n.$

where

${n \choose \nu}$

is a binomial coefficient.

The Bernstein basis polynomials of degree n form a basis for the vector space $Π n$ of polynomials of degree n.

A linear combination of Bernstein basis polynomials

$B(x) = \sum_{\nu=0}^{n} \beta_{\nu} b_{\nu,n}(x)$

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

[edit] Notes

The Bernstein basis polynomials have the following properties:

$b ν, n (x) = 0$ , if ν < 0 or ν > n
$b ν, n (0) = δ ν,0$ and $b ν, n (1) = δ ν, n$ where $δ$ is the Kronecker delta function.
$b ν, n (x)$ has a root with multiplicity ν at point x = 0 (note if ν is 0 there is no root at 0)
$b ν, n (x)$ has a root with multiplicity n − ν at point x = 1 (note if ν = n there is no root at 1)
$b ν, n (x)$ ≥ 0 for x in [0,1]
$b ν, n (1 - x) = b n - ν, n (x)$
If ν ≠ 0, then $b ν, n (x)$ has a unique local maximum on the interval [0,1] at x = ν/n. This maximum takes the value

$\nu^{\nu}n^{-n}(n-\nu)^{n-\nu}{n\choose \nu}.$

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

$\sum_{\nu=0}^n b_{\nu,n}(x) = \sum_{\nu=0}^n {n \choose \nu} x^{\nu}(1-x)^{n-\nu} = (x+(1-x))^n = 1.$

[edit] Example

The first few Bernstein basis polynomials are

$b_{0,0}(x) = 1\,$

$b_{0,1}(x) = 1-x \mbox{ , } b_{1,1}(x) = x\,$

$b_{0,2}(x) = (1-x)^2 \mbox{ , } b_{1,2}(x) = 2x(1-x) \mbox{ , } b_{2,2}(x) = x^2.\,$

[edit] Approximating continuous functions

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

$B_n(f)(x) = \sum_{\nu=0}^{n} f\left(\frac{\nu}{n}\right) b_{\nu,n}(x).$

It can be shown that

$\lim_{n\rightarrow\infty} 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\rightarrow\infty} \sup\{\,\left|f(x)-B_n(f)(x)\right|:0\leq x\leq 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 \rightarrow 0,$

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

[edit] 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\to\infty}P\left(\left|\frac{K}{n}-x\right|>\delta\right)=0$

for every $δ > 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\rightarrow\infty} P\left(\left|f(K/n)-f(x)\right|>\varepsilon\right)=0.$

Consequently

$\lim_{n\rightarrow\infty} P\left(\left|f(K/n)-E(f(K/n))\right|+\left|E(f(K/n))-f(x)\right|>\varepsilon\right)=0.$

$\lim_{n\rightarrow\infty} P\left(\left|f\left(\frac{K}{n}\right)-E\left(f\left(\frac{K}{n}\right)\right)\right|>\varepsilon/2\right)+P\left( \left|E\left(f\left(\frac{K}{n}\right)\right)-f(x)\right|>\varepsilon/2\right)=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).