bernstein_approximation


bernstein_approximation, a MATLAB code which looks at some simple cases of approximation of a function f(x) by a Bernstein polynomial.

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 MIT license

Languages:

bernstein_approximation is available in a MATLAB version.

Related Data and Programs:

bernstein_approximation_test

bernstein_polynomial, a MATLAB code which evaluates the Bernstein polynomials, useful for uniform approximation of functions;

chebyshev, a MATLAB code which computes the Chebyshev interpolant/approximant to a given function over an interval.

lagrange_approx_1d, a MATLAB code which defines and evaluates the Lagrange polynomial p(x) of degree m which approximates a set of nd data points (x(i),y(i)).

pwl_approx_1d, a MATLAB code which approximates a set of data using a piecewise linear function.

spline, a MATLAB code which constructs and evaluates spline interpolants and approximants.

test_approx, a MATLAB code which defines test problems for approximation, provided as a set of (x,y) data.

vandermonde_approx_1d, a MATLAB code which finds a polynomial approximant to a function of 1D data by setting up and solving an overdetermined linear system for the polynomial coefficients, involving the Vandermonde matrix.

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:


Last revised on 28 January 2016.