B-Splines in Numerical Analysis 📂Numerical Analysis

B-Splines in Numerical Analysis

If you dislike reading texts and formulas, it’s perfectly fine to just look at the images to understand.

Definition ¹

Let’s divide the interval $[a,b]$ into node points such as $a \le x_{0} < x_{1} < \cdots < x_{n} < \cdots x_{N} \le b$. Considering additional nodes $x_{-K} < x_{-K + 1} < \cdots < x_{-1} < x_{0}$ and $x_{N} < x_{N + 1} < \cdots < x_{N+K-1} < x_{N+K}$ for a given degree of freedom $K$, define a recursive function depending on the $i$th node point and degree of freedom $1 \le k \le K$ as $$ B_{i,k}(x) := \begin{cases} \chi_{[x_{i} , x_{i+1} )} (x) & , k=1 \\ {{ x - t_{i} } \over {t_{i+k-1} - t_{i} }} B_{i , k-1} (x) - {{ x - t_{i+k} } \over {t_{i+k} - t_{i+1} }} B_{i+1, k-1} (x) & , k > 1 \end{cases} $$ The spline $\displaystyle \sum_{i=-3}^{n-1} \alpha_{i} B_{i , K} (x)$ that interpolates the given data based on this is called a B-Spline.

Theorems

[1]: The B-Spline for given data is unique.
[2]: For $x \notin (x_{i} , x_{i+K} )$, there is $B_{i, K} (x) = 0$
[3]: For all $x$, there is $0 \le B_{i} (x) \le 1$

$\chi$ represents an indicator function defined as $\chi_{A} (x) := \begin{cases} 0 & , x \notin A \\ 1 & , x \in A \end{cases}$ over the domain $A$.

Explanation

A B-Spline is a spline that performs piecewise polynomial interpolation using basis among splines. The function $B_{i,K}$ uses the letter $B$, meaning Basis, for reconstructing the original function.

Explanation of Theorems

Proof is omitted.

In terms of practicality, B-Splines are widely used in fields like computer graphics and have rich theoretical and mathematical properties, enough to fill an entire book. It’s too difficult to explain in just one post, so let’s just briefly check what the concept is about. The definition may seem complex at first glance, but the actual concept is not that difficult.

[1]: Before splines, the basic intuition for interpolation is essential. The method to show the uniqueness of $\alpha_{i}$ is essentially no different from polynomial interpolation, and the actual difference lies in whether you can imagine a function space or not. Even then, it’s not actually dealing with function spaces, so it’s fine if you’re not familiar with them.
[2]: The reason $B$ is defined this way, reassuring us that the basis is linearly independent. Even if you don’t understand what that means, you’ll get it once you see the diagram.
[3]: The scale of the function values being set and especially not becoming negative means that the actual interpolation of function values largely depends only on the coefficients $\alpha_{i}$. The fact that you don’t need to worry about the shape of the function is another reason why B-Splines are convenient to handle.

Visual Understanding

Before starting the examples, it should be noted that the original nodes covered by B-Splines can be more severe than defined above. There can be identical points, and additional nodes can be far more flexible. However, for ease of understanding, we’ll consider nodes given at uniform intervals in the examples.

$20190415\_145943.png$ For degree of freedom $k=1$, $B_{i,1}$ for interpolating the data is shaped like the above. Their combination to interpolate the original data literally means just adjusting the height of the square columns to roughly fit. However, this is an excellent way to explain the idea of restoring original data through the linear combination of functions.

$20190415\_145953.png$ For degree of freedom $k=2$, it can be easily verified mathematically that $B_{i,2}$ has the shape as seen above. Note, however, that easy and simple are different matters. Compared to degree of freedom $k=1$, $\displaystyle \sum_{i=-3}^{n-1} \alpha_{i} B_{i , K} (x)$ will be somewhat less angular. It’s worth noting that the diagram does not explicitly display this, but additional nodes such as $x_{-1} = -1$ and $x_{5} = 5$ continue to emerge as the degree of freedom increases, and $B_{i,2}$ at those points is also newly formed.

$20190415\_150000.png$ For degree of freedom $k=3$, $B_{i,3}$ is quadratic in each interval. Of course, given the characteristics of $B_{i,k}$ defined recursively, there is no guarantee that it will be quadratic across the entire interval, and in fact, most cases won’t be. The most noticeable difference in the examples above is that it finally becomes a curve.

A B-Spline is a function that interpolates through the linear combination of functions that are easy to handle in specific intervals and elsewhere, the function values are entirely $0$. Hence, although the definition is written complicatedly, the actual concept is about repeating the same task under many more and worse conditions.