BERNSTEIN_POLYNOMIAL
The Bernstein Polynomials


BERNSTEIN_POLYNOMIAL is a FORTRAN90 library which evaluates the Bernstein polynomials.

A Bernstein polynomial of degree n is a linear combination of the (n+1) Bernstein basis polynomials of degree n: BP(n,x) = sum ( 0 <= k <= n ) CP(n,k) * B(n,k)(x).

For 0 <= k <= n, the k-th Bernstein basis polynomial of degree n is:

        B(n,k)(x) = C(n,k) * (1-x)^(n-k) * x^k
      
where C(n,k) is the combinatorial function "N choose K" defined by
        C(n,k) = n! / k! / ( n - k )!
      

For an arbitrary value of n, the set B(n,k) forms a basis for the space of polynomials of degree n or less.

Every basis polynomial B(n,k) is nonnegative in [0,1], and may be zero only at the endpoints.

Except for the case n = 0, the basis polynomial B(n,k)(x) has a unique maximum value at

        x = k/n.
      

For any point x, (including points outside [0,1]), the basis polynomials for an arbitrary value of n sum to 1:

        sum ( 1 <= k <= n ) B(n,k)(x) = 1
      

For 0 < n, the Bernstein basis polynomial can be written as a combination of two lower degree basis polynomials:

        B(n,k)(x) = ( 1 - x ) * B(n-1,k)(x) + x * B(n-1,k-1)(x) +
      
where, if k is 0, the factor B(n-1,k-1)(x) is taken to be 0, and if k is n, the factor B(n-1,k)(x) is taken to be 0.

A Bernstein basis polynomial can be written as a combination of two higher degree basis polynomials:

        B(n,k)(x) = ( (n+1-k) * B(n+1,k)(x) + (k+1) * B(n+1,k+1)(x) ) / ( n + 1 )
      

The derivative of B(n,k)(x) can be written as:

        d/dx B(n,k)(x) = n * B(n-1,k-1)(x) - B(n-1,k)(x)
      

A Bernstein polynomial can be written in terms of the standard power basis:

        B(n,k)(x) = sum ( k <= i <= n ) (-1)^(i-k) * C(n,k) * C(i,k) * x^i
      

A power basis monomial can be written in terms of the Bernstein basis of degree n where k ≤ n:

        x^k = sum ( k-1 <= i <= n-1 ) C(i,k) * B(n,k)(x) / C(n,k)
      

Over the interval [0,1], the n-th degree Bernstein approximation polynomial to a function f(x) is defined by

        BA(n,f)(x) = sum ( 0 <= k <= n ) f(k/n) * B(n,k)(x)
      
As a function of n, the Bernstein approximation polynomials form a sequence that slowly, but uniformly, converges to f(x) over [0,1].

By a simple linear process, the Bernstein basis polynomials can be shifted to an arbitrary interval [a,b], retaining their properties.

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Languages:

BERNSTEIN_POLYNOMIAL is available in a C version and a C++ version and a FORTRAN77 version and a FORTRAN90 version and a MATLAB version and a Python version.

Related Data and Programs:

CHEBYSHEV, a FORTRAN90 library which computes the Chebyshev interpolant/approximant to a given function over an interval.

DIVDIF, a FORTRAN90 library which uses divided differences to interpolate data.

GEGENBAUER_POLYNOMIAL, a FORTRAN90 library which evaluates the Gegenbauer polynomial and associated functions.

HERMITE, a FORTRAN90 library which computes the Hermite interpolant, a polynomial that matches function values and derivatives.

HERMITE_CUBIC, a FORTRAN90 library which can compute the value, derivatives or integral of a Hermite cubic polynomial, or manipulate an interpolating function made up of piecewise Hermite cubic polynomials.

INTERP, a FORTRAN90 library which can be used for parameterizing and interpolating data;

JACOBI_POLYNOMIAL, a FORTRAN90 library which evaluates the Jacobi polynomial and associated functions.

LAGUERRE_POLYNOMIAL, a FORTRAN90 library which evaluates the Laguerre polynomial, the generalized Laguerre polynomial, and the Laguerre function.

LEGENDRE_POLYNOMIAL, a FORTRAN90 library which evaluates the Legendre polynomial and associated functions.

LOBATTO_POLYNOMIAL, a FORTRAN90 library which evaluates Lobatto polynomials, similar to Legendre polynomials except that they are zero at both endpoints.

NMS, a FORTRAN90 library which includes a wide variety of numerical software, including solvers for linear systems of equations, interpolation of data, numerical quadrature, linear least squares data fitting, the solution of nonlinear equations, ordinary differential equations, optimization and nonlinear least squares, simulation and random numbers, trigonometric approximation and Fast Fourier Transforms.

PPPACK, a FORTRAN90 library which implements piecewise polynomial functions, including, in particular, cubic splines, by Carl deBoor.

SPLINE, a FORTRAN90 library which constructs and evaluates spline interpolants and approximants.

TEST_APPROX, a FORTRAN90 library which defines a number of test problems for approximation and interpolation.

TEST_INTERP_1D, a FORTRAN90 library which defines test problems for interpolation of data y(x), depending on a 1D argument.

TOMS446, a FORTRAN90 library which manipulates Chebyshev series for interpolation and approximation;
this is a version of ACM TOMS algorithm 446, by Roger Broucke.

Reference:

  1. Kenneth Joy,
    "Bernstein Polynomials",
    On-Line Geometric Modeling Notes,
    idav.ucdavis.edu/education/CAGDNotes/Bernstein-Polynomials.pdf
  2. David Kahaner, Cleve Moler, Steven Nash,
    Numerical Methods and Software,
    Prentice Hall, 1989,
    ISBN: 0-13-627258-4,
    LC: TA345.K34.
  3. Josef Reinkenhof,
    Differentiation and integration using Bernstein's polynomials,
    International Journal of Numerical Methods in Engineering,
    Volume 11, Number 10, 1977, pages 1627-1630.

Source Code:

Examples and Tests:

List of Routines:

You can go up one level to the FORTRAN90 source codes.


Last revised on 27 January 2016.