Essays/Bernstein Polynomials

From J Wiki
Jump to: navigation, search

Template:Tick

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
Bernstein3.png Bernstein6.png
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'
)

Bezier.png

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
Coef.png
'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) } } Envelope.png
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


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