Essays/Bernstein Polynomials

From J Wiki
Jump to: navigation, search

Wm yes check.png

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 basis Bernstein polynomials of degree :

In J this is defined by

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

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

To illustrate on the interval

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 makes up a complete Bernstein polynomial, also known as a Bézier curve with given control points.

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

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

With control points , 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

coefficients 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 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

Thus

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

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

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 of a family of base Bernstein polynomials is

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.