BERNSTEIN_POLYNOMIAL
The Bernstein Polynomials

BERNSTEIN_POLYNOMIAL is a C++ library which evaluates the Bernstein polynomials.

The k-th Bernstein basis polynomial of degree n is defined by

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

        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) +
      

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)
      

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.

Related Data and Programs:

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

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

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

HERMITE_CUBIC, a C++ 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.

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

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

TEST_APPROX, a C++ library which defines test problems for approximation, provided as a set of (x,y) data.

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

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:

• bernstein_polynomial.cpp, the source code.
• bernstein_polynomial.hpp, the include file.
• bernstein_polynomial.sh, BASH commands to compile the source code.

Examples and Tests:

• bernstein_polynomial_prb.cpp, a sample calling program.
• bernstein_polynomial_prb.sh, BASH commands to compile and run the sample program.
• bernstein_polynomial_prb_output.txt, the output file.

List of Routines:

• BERNSTEIN_MATRIX returns the Bernstein matrix.
• BERNSTEIN_MATRIX_INVERSE returns the inverse Bernstein matrix.
• BERNSTEIN_POLY_01 evaluates the Bernstein polynomials based in [0,1].
• BERNSTEIN_POLY_01_VALUES returns some values of the Bernstein polynomials.
• BERNSTEIN_POLY_AB evaluates at X the Bernstein polynomials based in [A,B].
• BERNSTEIN_POLY_AB_APPROX: Bernstein approximant to F(X) on [A,B].
• I4_MAX returns the maximum of two I4's.
• I4_MIN returns the minimum of two I4's.
• R8_ABS returns the absolute value of an R8.
• R8_CHOOSE computes the binomial coefficient C(N,K) as an R8.
• R8_MAX returns the maximum of two R8's.
• R8_MOP returns the I-th power of -1 as an R8 value.
• R8_UNIFORM_01 returns a unit pseudorandom R8.
• R8MAT_IS_IDENTITY determines if an R8MAT is the identity.
• R8MAT_MM_NEW multiplies two matrices.
• R8MAT_NORM_FRO returns the Frobenius norm of an R8MAT.
• R8MAT_PRINT prints an R8MAT.
• R8MAT_PRINT_SOME prints some of an R8MAT.
• R8VEC_DOT_PRODUCT computes the dot product of a pair of R8VEC's.
• R8VEC_LINSPACE_NEW creates a vector of linearly spaced values.
• R8VEC_SUM returns the sum of an R8VEC.
• TIMESTAMP prints the current YMDHMS date as a time stamp.

You can go up one level to the C++ source codes.