# 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'
)
`