Why Do Normalized B-Splines Always Sum to One?

  • MHB
  • Thread starter mathmari
  • Start date
  • Tags
    Sum
In summary, the normalized B-splines of a set of nodes of degree $k$ can be represented by a formula with divided differences. It has been shown that the sum of these normalized B-splines is equal to $1$ for all values of $x$ within the range of the nodes. This is due to the mean value theorem for divided differences, where the $n$th derivative of a function is equal to $n!$ times the $n$th divided difference at certain points. In this case, the divided difference evaluates to $1$ when $\xi-x>0$ and $0$ when $\xi-x<0$.
  • #1
mathmari
Gold Member
MHB
5,049
7
Hey! :giggle:

Let $N_j$, $j=-k,\ldots , m-1$ the normalized B-splines of the set of nodes $x_0, \ldots , x_m$ of degree $k$.

Show that $$\sum_{j=-k}^{m-1}N_j(x)=1 \ \text{ for all } x\in [x_0, x_m]$$

A formula with divided differences is
\begin{align*}&N_j(x)=(x_{j+k+1}-x_j)B_j(x) \\& \text{ with } \ B_j=(\cdot -x)_+^k[x_jx_{j+1}x_{j+2}\ldots x_{j+k+1}] =\frac{(\cdot -x)_+^k[x_{j+1}x_{j+2}\ldots x_{j+k+1}]-(\cdot -x)_+^k[x_jx_{j+1}x_{j+2}\ldots x_{j+k}]}{x_{j+k+1}-x_j}\end{align*} where $(x)_+^k=\begin{cases}x^k & \text{ if } x\geq 0 \\ 0 & \text{ if } x<0\end{cases}$.

It holds that $B_j=(\cdot -x)_+^k[x_jx_{j+1}x_{j+2}\ldots x_{j+k+1}]=f_x[x_jx_{j+1}x_{j+2}\ldots x_{j+k+1}]$ with $f_x(y)=(y-x)_+^k$, so is this the function for the divided difference? :unsure:

Then we have \begin{align*}\sum_{j=-k}^{m-1}N_j(x)&=\sum_{j=-k}^{m-1}(x_{j+k+1}-x_j)B_j(x)\\ & =\sum_{j=-k}^{m-1}(x_{j+k+1}-x_j)\frac{(\cdot -x)_+^k[x_{j+1}x_{j+2}\ldots x_{j+k+1}]-(\cdot -x)_+^k[x_jx_{j+1}x_{j+2}\ldots x_{j+k}]}{x_{j+k+1}-x_j}\\ & =\sum_{j=-k}^{m-1}\left ((\cdot -x)_+^k[x_{j+1}x_{j+2}\ldots x_{j+k+1}]-(\cdot -x)_+^k[x_jx_{j+1}x_{j+2}\ldots x_{j+k}]\right ) \\ & = (\cdot -x)_+^k[x_{m}x_{m+1}\ldots x_{m+k}]-(\cdot -x)_+^k[x_{-k}x_{-k+1}x_{-k+2}\ldots x_{0}] \\ & = (\cdot -x)_+^k[x_{m}x_{m+1}\ldots x_{m+k}]-0[x_{-k}x_{-k+1}x_{-k+2}\ldots x_{0}] \\ & =1-0 \\ & =1\end{align*}
I haven't understood the part from the 4th equality.
Why is the sum equal to the last term minus the first term? :unsure:
How do we get the zero and how do we get the one? :unsure:
 
Mathematics news on Phys.org
  • #2
mathmari said:
Why is the sum equal to the last term minus the first term?

Hey mathmari!

It's called a telescoping series.
Consider $$\sum_{i=0}^{N-1} (a_{i+1}-a_i) = (a_1-a_0) + (a_2-a_1)+\ldots +(a_N - a_{N-1}) = a_N-a_0$$ 🤔

mathmari said:
How do we get the zero and how do we get the one?
What does $(\cdot -x)_+^k[x_{m}x_{m+1}\ldots x_{m+k}]$ mean? :unsure:

As for the zero, I can already guess that we get something like $(x_0-x)_+^k$ and for all $x$ in $[x_0,x_m]$ we have that $x_0-x\le 0$, so that $(x_0-x)_+^k=0$. 🤔
 
  • #3
Klaas van Aarsen said:
It's called a telescoping series.
Consider $$\sum_{i=0}^{N-1} (a_{i+1}-a_i) = (a_1-a_0) + (a_2-a_1)+\ldots +(a_N - a_{N-1}) = a_N-a_0$$ 🤔

We have that
\begin{align*} \sum_{j=-k}^{m-1}&\left ((\cdot -x)_+^k[x_{j+1}x_{j+2}\ldots x_{j+k+1}]-(\cdot -x)_+^k[x_jx_{j+1}x_{j+2}\ldots x_{j+k}]\right )\\ & =(\cdot -x)_+^k[x_{-k+1}x_{-k+2}\ldots x_{1}]-(\cdot -x)_+^k[x_{-k}x_{-k+1}x_{-k+2}\ldots x_{0}]+(\cdot -x)_+^k[x_{-k+2}x_{-k+3}\ldots x_{2}]-(\cdot -x)_+^k[x_{-k+1}x_{-k+2}x_{-k+3}\ldots x_{1}] +\ldots \\ & +\ldots
(\cdot -x)_+^k[x_{m-1}x_{m}\ldots x_{m+k-1}]-(\cdot -x)_+^k[x_{m-2}x_{m-1}x_{m}\ldots x_{m+k-2}]
+(\cdot -x)_+^k[x_{m}x_{m+1}\ldots x_{m+k}]-(\cdot -x)_+^k[x_{m-1}x_{m}x_{m+1}\ldots x_{m+k-1}] \\ & = (\cdot -x)_+^k[x_{m}x_{m+1}\ldots x_{m+k}]-(\cdot -x)_+^k[x_{-k}x_{-k+1}x_{-k+2}\ldots x_{0}]\end{align*}

(Malthe)
Klaas van Aarsen said:
What does $(\cdot -x)_+^k[x_{m}x_{m+1}\ldots x_{m+k}]$ mean? :unsure:

As for the zero, I can already guess that we get something like $(x_0-x)_+^k$ and for all $x$ in $[x_0,x_m]$ we have that $x_0-x\le 0$, so that $(x_0-x)_+^k=0$. 🤔

Since we have that $
B_j=(\cdot -x)_+^k[x_jx_{j+1}x_{j+2}\ldots x_{j+k+1}]=f_x[x_jx_{j+1}x_{j+2}\ldots x_{j+k+1}]
$ with $
f_x(y)=(y-x)_+^k
$ it must be the difference you are reffering to.

So do we have that $$(\cdot -x)_+^k[x_{-k}x_{-k+1}x_{-k+2}\ldots x_{0}]=([x_{-k}x_{-k+1}x_{-k+2}\ldots x_{0}]-x)_+^k$$ or how do we write this? I understand what you say that it is zero because it is negative, but why is the other one equal to $1$ ?

:unsure:
 
  • #4
mathmari said:
So do we have that $$(\cdot -x)_+^k[x_{-k}x_{-k+1}x_{-k+2}\ldots x_{0}]=([x_{-k}x_{-k+1}x_{-k+2}\ldots x_{0}]-x)_+^k$$ or how do we write this?
That does not look right to me.
It does not make sense that we would subtract $x$ from a product of $x_i$'s. The "dimensions" don't match.
So I think something else is intended. Something where we process the $x_i$ one by one or something like that. 🤔
Once we know what it is, we can probably understand how it evaluates to $1$.
 
  • #5
Klaas van Aarsen said:
That does not look right to me.
It does not make sense that we would subtract $x$ from a product of $x_i$'s. The "dimensions" don't match.
So I think something else is intended. Something where we process the $x_i$ one by one or something like that. 🤔
Once we know what it is, we can probably understand how it evaluates to $1$.

Here in Wikipedia it says that it is the n-th divided difference, but I haven't really understood that. :unsure:
 
  • #6
mathmari said:
Here in Wikipedia it says that it is the n-th divided difference, but I haven't really understood that. :unsure:
The mean value theorem for divided differences says:

For any $n + 1$ pairwise distinct points $x_0$, ..., $x_n$ in the domain of an $n$-times differentiable function $f$ there exists an interior point
$$\xi \in (\min\{x_0,\dots,x_n\},\max\{x_0,\dots,x_n\})$$
where the $n$th derivative of $f$ equals $n!$ times the $n$th divided difference at these points:
$$f[x_0,\dots,x_n] = \frac{f^{(n)}(\xi)}{n!}.$$
🧐

In our case we have $x\in[x_0,x_m]$ and:
\[ (\cdot -x)_+^k[x_{m}x_{m+1}\ldots x_{m+k}] =\frac{\left((\cdot -x)_+^k\right)^{(k)}(\xi)}{k!} =\begin{cases}\frac{\left((\cdot -x)^k\right)^{(k)}(\xi)}{k!} &\text{if }\xi-x>0\\ \frac{\left(0\right)^{(k)}(\xi)}{k!} &\text{if }\xi-x< 0 \end{cases} =\begin{cases}1 &\text{if }\xi-x>0\\ 0 &\text{if }\xi-x< 0 \end{cases} \]
Since $\xi$ must be between $x_{m},x_{m+1},\ldots, x_{m+k}$, it follows that $\xi-x>0$. 🤔

For the zero case, $\xi$ must be betweeen $x_{-k},\ldots,x_0$, so $\xi-x<0$. 🤔
 
Last edited:
  • #7
Klaas van Aarsen said:
In our case we have $x\in[x_0,x_m]$ and:
\[ (\cdot -x)_+^k[x_{m}x_{m+1}\ldots x_{m+k}] =\frac{\left((\cdot -x)_+^k\right)^{(k)}(\xi)}{k!} =\begin{cases}\frac{\left((\cdot -x)^k\right)^{(k)}(\xi)}{k!} &\text{if }\xi-x>0\\ \frac{\left(0\right)^{(k)}(\xi)}{k!} &\text{if }\xi-x< 0 \end{cases} =\begin{cases}1 &\text{if }\xi-x>0\\ 0 &\text{if }\xi-x< 0 \end{cases} \]
Since $\xi$ must be between $x_{m},x_{m+1},\ldots, x_{m+k}$, it follows that $\xi-x>0$. 🤔

For the zero case, $\xi$ must be betweeen $x_{-k},\ldots,x_0$, so $\xi-x<0$. 🤔

I haven't really understood how we get the $1$ in the case $\xi-x>0$ :unsure:
 
  • #8
mathmari said:
I haven't really understood how we get the $1$ in the case $\xi-x>0$
Consider the function $f: \cdot \mapsto (\cdot - x)^k$.
Note that this is not a function of $x$. Instead it's a function of the unspecified $\cdot$.
So we have for instance $f(y) = (y-x)^k$, which is a function of $y$ and we treat $x$ as a constant. 🤔

If we take the derivative of $f$, we get $f'(y)=k(y-x)^{k-1}$.
Repeat for a total of $k$ times, and we get $f^{(k)}(y)=k! (y-x)^0=k!$.
Now we substitute $\xi$ for $y$, but there is no $y$ anymore, so nothing happens. 🤔

We actually have $(y-x)_+^k$ in the formula, which we evaluate for $y-x>0$, so our result is for the case that $\xi -x>0$.
Finally we divide $f^{(k)}(\xi)=k!$ by $k!$ to arrive at $1$. 🤔
 
Last edited:
  • #9
Klaas van Aarsen said:
Consider the function $f: \cdot \mapsto (\cdot - x)^k$.
Note that this is not a function of $x$. Instead it's a function of the unspecified $\cdot$.
So we have for instance $f(y) = (y-x)^k$, which is a function of $y$ and we treat $x$ as a constant. 🤔

If we take the derivative of $f$, we get $f'(y)=k(y-x)^{k-1}$.
Repeat for a total of $k$ times, and we get $f^{(k)}(y)=k! (y-x)^0=k!$.
Now we substitute $\xi$ for $y$, but there is no $y$ anymore, so nothing happens. 🤔

We actually have $(y-x)_+^k$ in the formula, which we evaluate for $y-x>0$, so our result is for the case that $\xi -x>0$.
Finally we divide $f^{(k)}(\xi)=k!$ by $k!$ to arrive at $1$. 🤔

Now it is clear to me! Thanks for explaining! (Sun)
 

Related to Why Do Normalized B-Splines Always Sum to One?

1. What are B-splines?

B-splines are a type of mathematical function used to represent smooth curves and surfaces. They are commonly used in computer graphics, computer-aided design, and numerical analysis.

2. What is the sum of normalized B-splines?

The sum of normalized B-splines is a mathematical operation that combines multiple B-splines into a single function. This is often used in computer graphics to create more complex and realistic curves and surfaces.

3. How is the sum of normalized B-splines calculated?

The sum of normalized B-splines is calculated by adding together the individual B-splines, each multiplied by a weight factor. The weight factors determine the contribution of each B-spline to the final function.

4. What are the applications of the sum of normalized B-splines?

The sum of normalized B-splines has many applications in computer graphics, such as creating smooth and realistic curves in 3D modeling, generating smooth animations, and creating smooth shading effects on surfaces.

5. Are there any limitations to using the sum of normalized B-splines?

While the sum of normalized B-splines is a powerful tool, it does have some limitations. It can be computationally expensive for large numbers of B-splines, and it may not accurately represent certain types of curves or surfaces. Additionally, the weight factors must be carefully chosen to avoid artifacts or undesired effects in the final function.

Similar threads

  • General Math
Replies
4
Views
779
Replies
4
Views
2K
  • General Math
Replies
21
Views
3K
Replies
32
Views
2K
Replies
3
Views
976
Replies
36
Views
6K
Replies
7
Views
1K
Replies
3
Views
2K
Replies
6
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
Back
Top