↑ arvau

Wikipedia / Bernstein polynomial

In the mathematical field of numerical analysis, a Bernstein polynomial is a polynomial expressed as a linear combination of Bernstein basis polynomials. The idea is named after mathematician Sergei Natanovich Bernstein.

Polynomials in this form were first used by Bernstein in a constructive proof of the Weierstrass approximation theorem. With the advent of computer graphics, Bernstein polynomials, restricted to the interval [0,1], became important in the form of Bézier curves.

A numerically stable way to evaluate polynomials in Bernstein form is de Casteljau's algorithm.

Definition

Bernstein basis polynomials

Bernstein basis polynomials are defined as

is a binomial coefficient.

.

The first few Bernstein basis polynomials for blending or values together are:

form a basis for the vector space, all with real coefficients.

Bernstein polynomials

A linear combination of Bernstein basis polynomials

is called a Bernstein polynomial or polynomial in Bernstein form. are called Bernstein coefficients or Bézier coefficients.

The first few Bernstein basis polynomials from above in monomial form are:

Properties

The Bernstein basis polynomials have the following properties:

Approximating continuous functions

Let be a continuous function on the interval [0,1]. Consider the Bernstein polynomial

It can be shown that

uniformly on the interval[0,1].

Bernstein polynomials thus provide one way to prove the Weierstrass approximation theorem that every real-valued continuous function on a real interval [a,b] can be uniformly approximated by polynomial functions over.

A more general statement for a function with continuous kth derivative is

is the falling factorial, and additionally

is an eigenvalue of Bn; the corresponding eigenfunction is a polynomial of degreek.

Probabilistic proof

This proof follows Bernstein's original proof of 1912. See also Feller (1966) or Koralov & Sinai (2007).

Motivation

on a lattice, and then (2) smooth out the function outside the lattice to make a polynomial.

on such a point lattice, given that "smoothing out" a function is not always trivial. Taking the expectation of a random variable with a simple distribution is a common way to smooth. Here, we take advantage of the fact that Bernstein polynomials look like Binomial expectations. We split the interval into a lattice of n discrete values. Then, to evaluate any f(x), we evaluate f at one of the n lattice points close to x, randomly chosen by the Binomial distribution. The expectation of this approximation technique is polynomial, as it is the expectation of a function of a binomial RV. The proof below illustrates that this achieves a uniform approximation of f by uniform continuity.

Bernstein's proof

Suppose K is a random variable distributed as the number of successes in n independent Bernoulli trials with probability x of success on each trial; in other words, K has a binomial distribution with parameters n andx. Then we have the expected value and

By the weak law of large numbers of probability theory,

for every >0. Moreover, this relation holds uniformly in x, which can be seen from its proof via Chebyshev's inequality, taking into account that the variance of K, equal to x(1x), is bounded from above by irrespective of x.

Because , being continuous on a closed bounded interval, must be uniformly continuous on that interval, one infers a statement of the form

uniformly in x. Taking into account that ƒ is bounded (on the given interval) one finds that

uniformly in x. In the interval where the difference does not exceed ε, the expectation clearly cannot exceed ε. In the other interval, the difference still cannot exceed 2M, where M is an upper bound for |(x)| (since uniformly continuous functions are bounded). However, by our 'closeness in probability' statement, this interval cannot have probability greater than ε. Thus, this part of the expectation contributes no more than 2M times ε, which can be made arbitrarily small by choosing small ε.

Finally, one observes that the absolute value of the difference between expectations never exceeds the expectation of the absolute value of the difference, a consequence of Hölder's Inequality. Thus, using the above expectation, we see that (uniformly in x)

Noting that our randomness was over K while x is constant, the expectation of f(x) is just equal to f(x) converges to f(x) is a polynomial in x (the subscript reminding us that x controls the distribution of K). Indeed, it is:

Uniform convergence rates between functions

In the above proof, recall that convergence in each limit involving f depends on the uniform continuity of f, which implies a rate of convergence dependent on f 's modulus of continuity and the interval size. Thus, the approximation only holds uniformly across x for a fixed f, but one can readily extend the proof to uniformly approximate a set of functions with a set of Bernstein polynomials in the context of equicontinuity.

Elementary proof

The probabilistic proof can also be rephrased in an elementary way, using the underlying probabilistic ideas but proceeding by direct verification:

The following identities can be verified:

  1. ("probability")

  2. ("mean")

  3. ("variance")

In fact, by the binomial theorem

.

Within these three identities, use the above basis polynomial notation

and let

Thus, by identity (1)

so that

Since f. But then

times

  1. (Chebyshev's inequality)

It follows that the polynomials fn tend to f uniformly.

Generalizations to higher dimension

Bernstein polynomials can be generalized to dimensions – the resulting polynomials have the form . In the simplest case only products of the unit interval are considered; but, using affine transformations of the line, Bernstein polynomials can also be defined for products . For a continuous function on the -fold product of the unit interval, the proof that can be uniformly approximated by

is a straightforward extension of Bernstein's proof in one dimension.

See also

Notes

References

  • , English translation

  • , Russian edition first published in 1940