4

This is a copy of the following question on the Computer Science Stack Exchange: https://cs.stackexchange.com/questions/11655/how-come-the-bernstein-operator-creates-a-polynomial-of-the-same-degree-as-its-i

The original answer left me a bit puzzled, so I tried finding a way myself.

I read that the Bernstein operator

$$ \mathfrak{B}_f(t) = \sum_{i=0}^n f\left(\frac{i}{n}\right) \; B^n_i(t) $$

applied to a polynomial $f(x)$ of degree $m \leq n$ with the Bernstein polynomial

$$ B^n_i(t) = \binom{n}{i} \; t^i \; (1-t)^{n-i} $$

returns a new polynomial also of degree $m$. In other words, the Bernstein operator does not increase its degree when applied to $f$.

How is this possible? Since we're only sampling $f$ at a certain interval, wouldn't the original degree of $f$ become irrelevant? How can the degree of the result be smaller than $n$, since we will have at least one $t^n$ in the expression resulting from one of the Bernstein polynomials?

I've done some more research, and I've been able to change the expression as such:

$$ f(x) = \sum_{j=0}^m c_j \cdot x^j $$ $$ \mathfrak{B}_f(t) = \sum_{j=0}^m c_j \left[ \sum_{i=0}^m \left( \frac{i}{n} \right)^j \binom{n}{i} t^i (1-t)^{n-i} + \sum_{i=0}^{n-m} \left( \frac{i}{n} \right)^j \binom{n}{i} t^i (1-t)^{n-i} \right] $$

Now all that is left to do is to show that

$$ \sum_{j=0}^m \sum_{i=0}^m \left( \frac{i}{n} \right)^j \binom{n}{i} t^i (1-t)^{n-i} \neq 0 $$

and

$$ \sum_{j=0}^m \sum_{i=0}^{n-m} \left( \frac{i}{n} \right)^j \binom{n}{i} t^i (1-t)^{n-i} = 0 $$

However, I am afraid my math skills end here. I have no idea how to proceed.

Community
  • 1
robrene
  • 43

2 Answers2

4

You can do it with a lot of tedious manipulation.

Let $f(x) = x^m$, $m\le n$, and $\phi = {\cal B}(f)$. Then (expanding the $x^i(1-x)^{n-i}$ terms as well): \begin{eqnarray} \phi(x) &=& \frac{1}{n^m} \sum_{i=0}^n \sum_{j=0}^{n-i} i^m \binom{n}{i} \binom{n-i}{j} x^i (-x)^j \\ &=& \frac{1}{n^m} \sum_{(i,j) \in {\cal I}} i^m \binom{n}{i} \binom{n-i}{j} (-1)^j x^{i+j} \end{eqnarray} where ${\cal I} = \{ (i,j) | i=0,...,n, \ \ j=0,...,i \}$. Noting that we can write ${\cal I} = \{ (l,k-l) | k=0,...,n, \ \ l=0,...,k \}$, we have

\begin{eqnarray} \phi(x) = \frac{1}{n^m} \sum_{k=0}^n \sum_{l=0}^k l^m \binom{n}{l} \binom{n-l}{k-l} (-1)^{k-l} x^k \end{eqnarray} Now notice that $\binom{n}{l} \binom{n-l}{k-l} = \binom{n}{k} \binom{k}{l}$, which gives (along with the fact that $(-1)^{-l} = (-1)^l$):

\begin{eqnarray} \phi(x) &=& \frac{1}{n^m} \sum_{k=0}^n \sum_{l=0}^k l^m \binom{n}{k} \binom{k}{l} (-1)^{k-l} x^k \\ &=& \frac{1}{n^m} \sum_{k=0}^n \binom{n}{k} (-1)^k x^k \ \left( \sum_{l=0}^k l^m \binom{k}{l} (-1)^{l} \right) \end{eqnarray} Let $\beta_k = \sum_{l=0}^k l^m \binom{k}{l} (-1)^{l}$. We want to show that $\beta_k = 0$ for $k>m$.

(This is the main 'trick' in the proof.) Choose $k>m$, let $p(x) = (x-1)^k$ and define the linear operator $(Lf)(x) = x \frac{df(x)}{dx}$. Omitting the tedious details, we have that the polynomial $x-1$ divides $L^m p$ (ie, the operator $L$ applied $m$ times to $p$), and hence $(L^m p) (1) = 0$. Furthermore note that $L^m (t \mapsto t^l)(x) = l^m x^l$, which gives \begin{eqnarray} (L^m p) (1) &=& 0 \\ &=& L^m(t \mapsto (t-1)^k)(1) \\ &=& L^m \left(t \mapsto \sum_{l=0}^k \binom{k}{l} (-1)^{k-l} t^l \right)(1)\\ &=& \sum_{l=0}^k \binom{k}{l} (-1)^{k-l} L^m( t \mapsto t^l )(1) \\ &=& \sum_{l=0}^k \binom{k}{l} (-1)^{k-l} l^m \\ &=& (-1)^k \sum_{l=0}^k \binom{k}{l} (-1)^{l} l^m \\ & = & (-1)^k \beta_k \end{eqnarray}

copper.hat
  • 172,524
1

Let $c_0, \ldots, c_n$ be given numbers, and define the polynomial function $$ \phi(t) = \sum_{i=0}^n c_i B^n_i(t) $$ where $B^n_i(t)$ is the $i$-th Bernstein polynomial of degree $n$. You can think of $\phi$ as a real-valued Bezier curve, if that helps. It is well known (and easy to show by direct calculation) that $$ \phi'(t) = n\sum_{i=0}^{n-1} \Delta c_i B^{n-1}_i(t) $$ where $\Delta c_i$ denotes the forward difference $c_{i+1} - c_i$. Arguing inductively, we can generalise this to get a formula (also well known) for the $r$-th derivative for $r = 1,2,\ldots,n$ : $$ \phi^{(r)}(t) = \frac{n!}{(n-r)!}\sum_{i=0}^{n-r} \Delta^{r} c_i B^{n-r}_i(t) $$

If we apply this to the case where $f$ is some given function, and $c_i = f\left(\frac{i}{n}\right)$, then we have $\phi = \mathfrak{B}_f$. If $f$ is a polynomial of degree $m$, where $m < n$, then we have $\Delta^{r} c_i = 0$ for $r > m$. Therefore, using the formula above, we see that the $r$-th derivative $\phi^{(r)}$ is zero for $r>m$, which means that $\phi$ (i.e. $\mathfrak{B}_f$) must have degree $m$.

This result appears as an exercise in section 2.1 of the book "Bezier and B-Spline Techniques" by Prautzsch, Boehm and Paluszny.

bubba
  • 43,483
  • 3
  • 61
  • 122