which represents a polynomial as a linear combination of certain elementary polynomials
.
On-Line Geometric Modeling Notes
Overview
Polynomials are incredibly useful mathematical tools as they are
simply defined, can be calculated quickly on computer systems and
represent a
tremendous variety of functions.
They can be differentiated
and integrated easily, and can be pieced together to form spline curves
that can approximate any function to any accuracy desired. Most
students are
introducted to polynomials at a very early stage in their
studies of mathematics, and would probably recall them in the form
below:
which represents a polynomial as a linear combination
of certain
elementary polynomials .
In general, any polynomial function that has degree less than or equal to n, can be written in this way, and the reasons are simply
form a
basis
for
this vector space - that is, any polynomial of degree less than or
equal to n can be
uniquely written as a linear combinations of these functions.
In these notes we discuss another of the commonly used bases for the space of polynomials, the Bernstein basis, and discuss its many useful properties.
For a postscript version of these notes look here.
The Bernstein polynomials of degree n are defined by
for i = 0,1,...,n, where
There are n+1 nth-degree Bernstein
polynomials. For mathematical convenience, we usually set 
, if i<0 or i>n.
These polynomials are quite easy to write down: the coefficients
can be obtained from Pascal's triangle; the exponents on the t term increase
by one as i increases; and the exponents on the (1-t) term
decrease by one as i increases. In the simple cases, we obtain
as
as
as
A Recursive Definition of the Bernstein Polynomials
The Bernstein polynomials of degree n can be defined by blending together two Bernstein polynomials of degree n-1. That is, the kth nth-degree Bernstein polynomial can be written as
To show this, we need only use the
definition of the Bernstein polynomials
and some simple algebra:
The Bernstein Polynomials are All Non-Negative
A function f(t) is non-negative over an
interval [a,b] if 
for 
. In the case of the
Bernstein polynomials of degree n, each is non-negative over the
interval [0,1].
To show this we use the
recursive definition property above
and mathematical induction.
It is easily seen that
the functions 
and 
are
both non-negative for 
. If we assume that
all Bernstein polynomials of degree less than k are non-negative,
then by using the recursive definition of the Bernstein polynomial, we
can write
and argue that 
is also non-negative for 
,
since all components on the right-hand side of the equation are
non-negative components for 
. By induction, all
Bernstein polynomials are non-negative for 
.
In this process, we have also shown that each of the Bernstein polynomials is positive when 0 < t < 1.
The Bernstein Polynomials form a Partition of Unity
A set of functions 
is said to partition unity if they sum to
one for all values of t. The k+1 Bernstein polynomials of degree k form a partition of unity in that they all sum to one.
To show that this is true, it is easiest to first show a slightly different fact:
for each k,
the sum of the k+1 Bernstein polynomials of degree k is equal to
the sum of the k Bernstein polynomials of degree k-1. That is,
This calculation is straightforward, using
the recursive definition
and cleverly rearranging the sums:
(where we have utilized 
).
Once we have established this equality, it is simple to write
The partition of unity is a very important property when utilizing Bernstein polynomials in geometric modeling and computer graphics.
In particular, for any set of points
,
,
...,
,
in three-dimensional space,
and for any t, the expression
is an
affine combination
of the set of points 
and if
, it is a convex combination of the points.
Any of the lower-degree Bernstein polynomials (degree < n)
can be expressed as a linear combination of Bernstein polynomials
of degree n. In particular, any Bernstein polynomial of degree n-1
can be written as a linear combination of Bernstein polynomials of degree n.
We first note that
and
and finally
Using this final equation, we can write an arbitrary Bernstein
polynomial in terms of Bernstein polynomials of higher degree. That
is,
which expresses a Bernstein polynomial of degree n-1 in terms of a
linear combination of Bernstein polynomials of degree n.
We can easily extend this to show that any Bernstein polynomial of degree
k (less than n)
can be written as a linear combination of Bernstein
polynomials of degree n - e.g., a Bernstein polynomial of degree
n-2 can be expressed as a linear combination of two Bernstein polynomials of
degree n-1, each of which can be expressed as a linear combination
of two Bernstein polynomials of degree n, etc.
Converting from the Bernstein Basis to the Power Basis
Since the power basis 
forms a
basis
for the space of polynomials of degree less than or equal to n,
any Bernstein polynomial of degree n can be written in terms of
the power basis. This can be directly calculated using the definition
of the Bernstein polynomials and the binomial theorem, as follows:
where we have used the binomial theorem to expand 
.
To show that each power basis element can be written as a linear
combination of Bernstein Polynomials, we use the degree elevation
formulas and induction to calculate:
where the induction hypothesis was used in the second step.
Derivatives
Derivatives of the nth degree Bernstein polynomials are polynomials of degree
n-1. Using the definition of the Bernstein polynomial we can show that this derivative can be written as a linear combination of Bernstein polynomials.
In particular
for 
. This can be shown by direct differentiation
That is, the
derivative of a Bernstein polynomial can be expressed as the degree of the
polynomial, multiplied by the difference of two Bernstein polynomials of degree
n-1.
The Bernstein Polynomials as a Basis
Why do the Bernstein polynomials of order n form a basis for the space of polynomials of degree less than or equal to n?
This is easily seen if one realizes that The power basis spans the space of polynomials and any member of the power basis can be written as a linear combination of Bernstein polynomials.
so that the identity
's must be zero.
If this were true, then we could write
Since the power basis is a linearly independent set, we must have that
which implies that 
(
is clearly
zero, substituting this in the second equation gives 
,
substituting these two into the third equation gives ...)
A Matrix Representation for Bernstein Polynomials
In many applications, a matrix formulation for the Bernstein polynomials is useful. These are straightforward to develop if one only looks at a linear combination in terms of dot products.
Given a polynomial written as a linear combination of the Bernstein
basis functions
It is easy to write this as a dot product of two vectors
We can convert this to
where the 
are the coefficients of the power basis that are used
to determine the respective Bernstein polynomials.
We note that the
matrix in this case is lower triangular.
In the quadratic case (n=2), the matrix representation is
and in the cubic case (n=3), the matrix representation is
|
This document maintained by
Ken Joy
All contents copyright (c) 1996, 1997 |
|
