Bernstein polynomial

thumb|right|Bernstein polynomials approximating a curve

In the mathematical field of numerical analysis, a Bernstein polynomial is a polynomial expressed as a linear combination of Bernstein basis polynomials. The idea is named after mathematician Sergei Natanovich Bernstein.

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

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

thumb|Bernstein basis polynomials for 4th degree curve blending

Definition

Bernstein basis polynomials

The <math>n + 1</math> Bernstein basis polynomials of degree <math>n</math> are defined as

: <math>b_{\nu,n}(x)\ =\ \binom{n}{\nu}\ x^{\nu} \left( 1 - x \right)^{n - \nu}, ~~</math> for <math>~~ \nu = 0\ ,\ \ldots\ , n,</math>

where <math>\tbinom{n}{\nu}</math> is a binomial coefficient.

So, for example, <math>b_{2,5}(x)\ =\ \tbinom{5}{2}x^2(1-x)^3\ =\ 10x^2(1-x)^3</math>.

The first few Bernstein basis polynomials for blending or values together are:

: <math>

\begin{align}

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{align}

</math>

The Bernstein basis polynomials of degree <math>n</math> form a basis for the vector space <math>\Pi_n</math> of polynomials of degree at most <math>n</math>, all with real coefficients.

Bernstein polynomials

A linear combination of Bernstein basis polynomials

:<math>B_n(x)\ =\ \sum_{\nu=0}^{n} \beta_{\nu} b_{\nu,n}(x)</math>

is called a Bernstein polynomial or polynomial in Bernstein form of degree <math>n</math>. The coefficients <math>\beta_\nu</math> are called Bernstein coefficients or Bézier coefficients.

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

: <math>

\begin{align}

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{align}

</math>

Properties

The Bernstein basis polynomials have the following properties:

<math>b_{\nu, n}(x) = 0</math>, if <math>\nu < 0</math> or if <math>\nu > n</math>.
<math>b_{\nu, n}(x) \ge 0</math> for <math>x \in [0,\ 1]</math>.
<math>b_{\nu, n}\left( 1 - x \right) = b_{n - \nu, n}(x)</math>.
<math>b_{\nu, n}(0) = \delta_{\nu, 0}</math> and <math>b_{\nu, n}(1) = \delta_{\nu, n}</math> where <math>\delta_{i,j}</math> is the Kronecker delta function: <math>\delta_{ij} = \begin{cases}

0 &\text{if } i \neq j, \\

1 &\text{if } i=j.

\end{cases}</math>

<math>b_{\nu, n}(x)</math> has a root with multiplicity <math>\nu</math> at point <math>x = 0</math> (note: when <math>\nu = 0</math>, there is no root at ).
<math>b_{\nu, n}(x)</math> has a root with multiplicity <math>\left( n - \nu \right)</math> at point <math>x = 1</math> (note: if <math>\nu = n</math>, there is no root at ).
The derivative can be written as a combination of two Bernstein polynomials of lower degree: <math display="block">b_{\nu, n}'(x) = n \bigl[\ b_{\nu - 1, n - 1}(x)\ -\ b_{\nu, n - 1}(x)\ \bigr].</math>
The -th derivative at : <math display="block">b_{\nu, n}^{(k)}(0)\ =\ \frac{n!}{(n - k)!} \binom{k}{\nu} (-1)^{\nu + k}.</math>
The -th derivative at 1: <math display="block">b_{\nu, n}^{(k)}(1)\ =\ (-1)^k b_{n - \nu, n}^{(k)}(0).</math>
The transformation of the Bernstein polynomial to monomials is <math display="block">b_{\nu,n}(x)\ =\ \binom{n}{\nu}\sum_{k=0}^{n-\nu} \binom{n-\nu}{k}(-1)^{k} x^{\nu+k}\ =\ \sum_{\ell=\nu}^n \binom{n}{\ell}\binom{\ell}{\nu}(-1)^{\ell-\nu}x^\ell,</math> and by the inverse binomial transformation, the reverse transformation is <math display="block">x^k\ =\ \sum_{i=0}^{n-k} \frac{ \binom{n-k}{i} }{ \binom{n}{i} } b_{n-i,n}(x)\ =\ \frac{1}{\binom{n}{k \sum_{j=k}^n \binom{j}{k}b_{j,n}(x).</math>
The indefinite integral is given by <math display="block">\int b_{\nu, n}(x)\ \operatorname{d} x = \frac{1}{n+1} \sum_{j=\nu+1}^{n+1} b_{j, n+1}(x).</math>
The definite integral is constant for a given : <math display="block">\int_0^1 b_{\nu, n}(x)\ \operatorname{d} x = \frac{1}{n+1}</math> for all <math>\nu = 0, 1,\ \dots\ , n.</math>
If <math>n \ne 0</math>, then <math>b_{\nu, n}(x)</math> has a unique local maximum on the interval <math>[0,\, 1]</math> at <math>x = \frac{\nu}{n}</math>. This maximum takes the value <math display="block">\nu^\nu n^{-n} \left( n - \nu \right)^{n - \nu} {n \choose \nu}.</math>
The Bernstein basis polynomials of degree <math>n</math> form a partition of unity: <math display="block">\sum_{\nu = 0}^n b_{\nu, n}(x)\ =\ \sum_{\nu = 0}^n {n \choose \nu} x^\nu \left(1 - x\right)^{n - \nu}\ =\ \left(x + \left( 1 - x \right) \right)^n = 1.</math>
By taking the first <math>x</math>-derivative of <math>(x + y)^n</math>, treating <math>y</math> as constant, then substituting the value <math>y = 1-x</math>, it can be shown that <math display="block">\sum_{\nu=0}^{n} \nu\ b_{\nu, n}(x) = n\ x.</math>
Similarly the second <math>x</math>-derivative of <math>(x+y)^n</math>, with <math>y</math> then again substituted <math>y = 1-x,</math> shows that <math display="block">\sum_{\nu=1}^{n} \nu \left( \nu-1 \right)\ b_{\nu, n}(x) = n\left( n-1 \right)\ x^2.</math>
A Bernstein polynomial can always be written as a linear combination of polynomials of higher degree: <math display="block">b_{\nu, n - 1}(x)\ =\ \left( \frac{n - \nu}{n}\right)\ b_{\nu, n}(x)\ +\ \left( \frac{\nu + 1}{n}\right)\ b_{\nu + 1, n}(x).</math>
The expansion of the Chebyshev polynomials of the first kind into the Bernstein basis is <math display="block">T_n(u)\ =\ (2n-1)!!\ \sum_{k=0}^n \frac{~ (-1)^{n-k}\ }{\ (2k-1)!!\ (2n-2k-1)!!\ }\ b_{k,n}(u).</math>

Approximating continuous functions

Let &fnof; be a continuous function on the interval [0, 1]. Consider the Bernstein polynomial

:<math>B_n(f)(x) = \sum_{\nu = 0}^n f\left( \frac{\nu}{n} \right) b_{\nu,n}(x).</math>

It can be shown that

:<math>\lim_{n \to \infty}{ B_n(f) } = f </math>

uniformly on the interval [0, 1].

Bernstein polynomials thus provide one way to prove the Weierstrass approximation theorem that every real-valued continuous function on a real interval [a, b] can be uniformly approximated by polynomial functions over <math>\mathbb R</math>.

A more general statement for a function with continuous kth derivative is

:<math>{\left\| B_n(f)^{(k)} \right\|}_\infty \le \frac{ (n)_k }{ n^k } \left\| f^{(k)} \right\|_\infty \quad\ \text{and} \quad\ \left\| f^{(k)}- B_n(f)^{(k)} \right\|_\infty \to 0,</math>

where <math> (n)_k </math> is the falling factorial, and additionally

:<math>\frac{ (n)_k }{ n^k } = \left( 1 - \frac{0}{n} \right) \left( 1 - \frac{1}{n} \right) \cdots \left( 1 - \frac{k - 1}{n} \right)</math>

is an eigenvalue of Bn; the corresponding eigenfunction is a polynomial of degree k.

Probabilistic proof

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

The following identities can be verified:

<math> \sum_k {n \choose k} x^k (1-x)^{n-k} = 1</math> ("probability")
<math> \sum_k {k\over n} {n \choose k} x^k (1-x)^{n-k} = x</math> ("mean")
<math> \sum_k \left( x -{k\over n}\right)^2 {n \choose k} x^k (1-x)^{n-k} = {x(1-x)\over n}. </math> ("variance")

In fact, by the binomial theorem

<math display="block">(1+t)^n = \sum_k {n \choose k} t^k,</math>

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

Within these three identities, use the above basis polynomial notation

:<math> b_{k,n}(x) = {n\choose k} x^k (1-x)^{n-k},</math>

and let

:<math> f_n(x) = \sum_k f(k/n)\, b_{k,n}(x).</math>

Thus, by identity (1)

:<math>f_n(x) - f(x) = \sum_k [f(k/n) - f(x)] \,b_{k,n}(x), </math>

so that

:<math>|f_n(x) - f(x)| \le \sum_k |f(k/n) - f(x)| \, b_{k,n}(x).</math>

Since f is uniformly continuous, given <math>\varepsilon > 0</math>, there is a <math>\delta > 0</math> such that <math>|f(a) - f(b)| < \varepsilon</math> whenever

<math>|a-b| < \delta</math>. Moreover, by continuity, <math>M= \sup |f| < \infty</math>. But then

:<math> |f_n(x) - f(x)| \le \sum_{|x -{k\over n}|< \delta} |f(k/n) - f(x)|\, b_{k,n}(x) + \sum_{|x -{k\over n}|\ge \delta} |f(k/n) - f(x)|\, b_{k,n}(x) .</math>

The first sum is less than ε. On the other hand, by identity (3) above, and since <math>|x - k/n| \ge \delta</math>, the second sum is bounded by <math>2M</math> times

:<math>\sum_{|x - k/n|\ge \delta} b_{k,n}(x) \le \sum_k \delta^{-2} \left(x -{k\over n}\right)^2 b_{k,n}(x) = \delta^{-2} {x(1-x)\over n} < {1\over4} \delta^{-2} n^{-1}.</math>

:(Chebyshev's inequality)

It follows that the polynomials fn tend to f uniformly.

Generalizations to higher dimension

Bernstein polynomials can be generalized to dimensions – the resulting polynomials have the form .