# 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.

## Contents

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