Essays/Bernstein Polynomials

Bernstein polynomials were first used by Ukrainian mathematician Sergei Bernstein (rus. Сергей Бернштейн) in a proof of the Stone-Weierstrass approximation, an important theorem of numerical analysis, which states that every continuous function can be uniformly approximated by a polynomial. In computer graphics Bernstein polynomials are used to construct a Bézier curve.

Basis Polynomials

There are $k+1$ basis Bernstein polynomials of degree $k$:

$b_{i,k}(t)={k \choose i}t^{i}(1-t)^{k-i},\quad i=0,\dots ,k.$

In J this is defined by

'`t i k'=: (])`({.@[)`({:@[)

b=: (i!k) * (t^i) * (1-t)^(k-i)

To illustrate on the interval $0\leq t\leq 1$

require 'plot'

T=: (% <:@#)i.101

plot T;((i.4),.3) b"1 T	plot T;((i.7),.6) b"1 T

Linear Combination

A linear combination of the basis polynomials with Bernstein coefficients $p_{i}$ makes up a complete Bernstein polynomial, also known as a Bézier curve with given control points.

$B(t)=\sum _{i=0}^{k}p_{i}b_{i,k}(t)$

'`p ik'=: [ ` ( (i. ,. <:)@#@[ )

B=: p +/ . * ik b"1 t

With control points $p_{i}=\{1,4,2,3\}$, we have

3 : 0''
  P=. 1 4 2 3
  pd 'reset;pensize 2'
  pd (;~ (i. % <:)@#) P
  pd T;P B T
  pd 'show'
)

Expansion Coefficients

For expanded basis polynomials

$b_{i,k}(t)=\sum _{j=0}^{k}C_{i,k}^{j}\,t^{j}$

coefficients $C_{i,k}^{j}$ can be found by applying Taylor conjunction t. to the verb expression.

   bik=: 2 : '((*&(u!v))@(^&u * ^&(v-u)@-.))'
   1 bik 3
*&3@(^&1 * ^&2@-.)
   1 bik 3 t. i.4
0 3 _6 3

Thus, a matrix of polymonial coeficients of $k+1$ family (Bernstein matrix) is

   bc=: <: 4 : 'x bik y t. i.>:y'"0~ i.
   bc&.> >:i.5
+-+----+-------+----------+---------------+
|1|1 _1|1 _2  1|1 _3  3 _1|1 _4   6  _4  1|
| |0  1|0  2 _2|0  3 _6  3|0  4 _12  12 _4|
| |    |0  0  1|0  0  3 _3|0  0   6 _12  6|
| |    |       |0  0  0  1|0  0   0   4 _4|
| |    |       |          |0  0   0   0  1|
+-+----+-------+----------+---------------+

Alternatively, to obtain explicit formula, we note for $k=3$

${\begin{array}{cccrrrrrrrrrr}i&t^{i}&(1-t)^{k-i}&\times &&&&&{k \choose i}&&&&\\\hline 0&1&(1-t)^{3}&1-3t+3t^{2}-t^{3}&1&-3&3&-1&\times 1&1&-3&3&-1\\1&t&(1-t)^{2}&t-2t^{2}+t^{3}&0&1&-2&1&\times 3&0&3&-6&3\\2&t^{2}&1-t&t^{2}-t^{3}&0&0&1&-1&\times 3&0&0&3&-3\\3&t^{3}&1&t^{3}&0&0&0&1&\times 1&0&0&0&1\\\end{array}}$

Thus $C_{i,k}^{j}=(-1)^{i+j}{k \choose i}{k-i \choose k-j}$

psig=: _1^(+ i.@>:)
pcoef=: i.@-@>:@] ! -~
bcoef=: (psig * ! * pcoef)/"1

   (i.4) (psig"0 ; ,.@:! ; pcoef"0 ; bcoef@,"0) 3
+-----------+-+-------+----------+
| 1 _1  1 _1|1|1 3 3 1|1 _3  3 _1|
|_1  1 _1  1|3|0 1 2 1|0  3 _6  3|
| 1 _1  1 _1|3|0 0 1 1|0  0  3 _3|
|_1  1 _1  1|1|0 0 0 1|0  0  0  1|
+-----------+-+-------+----------+

bp=: bcoef@[ p. ]

   1 3 (b -: bp) (i.%<:) 11
1

'surface'plot bcoef (,.~ i.@>:) 9

Reduced Linear Combination

A new definition of linear combination of control points and polynomials with explicit coeficients

${\check {B}}(t)=\sum _{i=0}^{k}p_{i}\sum _{j=0}^{k}C_{i,k}^{j}\,t^{j}$

can be obtained

C=: bc@#@p
BC=: p +/ . * C p."1 t

   1 4 2 3 (B -: BC) T
1

which performs better on larger input

ts=: 6!:2 , 7!:2@]

   ts'1 4 2 3 B 200#T'
0.011728 2.62272e6
   ts'1 4 2 3 BC 200#T'
0.00564848 2.09952e6

Further, we note that the right hand sum can be represented as a product of the Bernstein matrix and the Vandermonde matrix of the input points. On the other hand, control points can be associatively pre-multiplied with the Bernstein matrix

V =: i.@#@p ^~/ t               NB. transposed Vandermonde
BV=: (p +/ .* C) +/ .* V

   1 4 2 3 (B -: BV) T
1
   ts'1 4 2 3 BV 200#T'
0.00636254 2.62362e6

Moreover, the left-hand product gives coefficients of the new polynomial

   1 4 2 3 (p +/ .* C) 0
1 9 _15 8

Thus, changing the order of summation, we obtain

${\hat {B}}(t)=\sum _{j=0}^{k}\left(\sum _{i=0}^{k}p_{i}C_{i,k}^{j}\right)t^{j}$

BP=: (p +/ .* C) p. t

   1 4 2 3 (B -: BP) T
1
   ts'1 4 2 3 BP 200#T'
0.00145298 525824

Envelope

Envelope $f_{k}(x)$ of a family of base Bernstein polynomials $b_{i,k}(x)$ is

$f_{k}(x)={1 \over {\sqrt {2\pi k\,x(1-x)}}}$

3 : 0''
  K=. 8
  pd 'reset;type dot;yrange 0 1;pensize 2'
  pd T;((i.K+1),.K) b"1 T
  pd 'type line'
  pd T; % %: 2 * 1p1 * K * T * 1 - T
  pd 'show'
)

See Also

• WikiPedia:Bernstein_polynomial, Wikipedia
• WikiPedia:Bézier_curve, ibid
• MathWorld:BernsteinPolynomial, Mathworld

Contributed by Oleg Kobchenko, with Taylor expansion by Andrew Nikitin.