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 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
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' )
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
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
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.