Editing B-spline (section)

==Properties==

A B-spline function is a combination of flexible bands that is controlled by a number of points that are called control points, creating smooth curves. These functions are used to create and manage complex shapes and surfaces using a number of points. B-spline function and Bézier functions are applied extensively in shape optimization methods.<ref name="ssdfgds">{{cite journal | last1 = Talebitooti | first1 = R.| last2 = Shojaeefard | first2 = M. H. | last3 = Yarmohammadisatri | first3 = Sadegh | year = 2015 | title = Shape design optimization of cylindrical tank using b-spline curves | journal = Computer & Fluids | volume = 109 | pages = 100–112 | doi= 10.1016/j.compfluid.2014.12.004 }}</ref>

A B-spline of order <math>n</math> is a piecewise polynomial function of degree <math>n - 1</math> in a variable <math>x</math>. It is defined over <math>1 + n</math> locations <math>t_j</math>, called knots or breakpoints, which must be in non-descending order <math>t_j \leq t_{j+1}</math>. The B-spline contributes only in the range between the first and last of these knots and is zero elsewhere. If each knot is separated by the same distance <math>h</math> (where <math>h = t_{j+1} - t_j</math>) from its predecessor, the knot vector and the corresponding B-splines are called "uniform" (see cardinal B-spline below).

For each finite knot interval where it is non-zero, a B-spline is a polynomial of degree <math>n - 1</math>. A B-spline is a [[continuous function]] at the knots.<ref group=note>Strictly speaking, B-splines are usually defined as being left-continuous.</ref> When all knots belonging to the B-spline are distinct, its derivatives are also continuous up to the derivative of degree <math>n - 2</math>. If the knots are coincident at a given value of <math>x</math>, the continuity of derivative order is reduced by 1 for each additional coincident knot. B-splines may share a subset of their knots, but two B-splines defined over exactly the same knots are identical. In other words, a B-spline is uniquely defined by its knots.

One distinguishes internal knots and end points. Internal knots cover the <math>x</math>-domain one is interested in. Since a single B-spline already extends over <math>1 + n</math> knots, it follows that the internal knots need to be extended with <math>n - 1</math> endpoints on each side, to give full support to the first and last B-spline, which affect the internal knot intervals. The values of the endpoints do not matter, usually the first or last internal knot is just repeated.

The usefulness of B-splines lies in the fact that any spline function of order <math>n</math> on a given set of knots can be expressed as a linear combination of B-splines:
: <math>S_{n,\mathbf t}(x) = \sum_i \alpha_i B_{i,n}(x).</math>
B-splines play the role of [[basis function]]s for the spline function space, hence the name. This property follows from the fact that all pieces have the same continuity properties, within their individual range of support, at the knots.<ref>de Boor, p. 113.</ref>

Expressions for the polynomial pieces can be derived by means of the Cox–de Boor recursion formula<ref>de Boor, p 131.</ref>

:<math>B_{i,0}(x) := \begin{cases}
 1 & \text{if } t_i \leq x < t_{i+1}, \\
 0 & \text{otherwise}.
\end{cases}
</math>

:<math>B_{i,k}(x) := \frac{x - t_i}{t_{i+k} - t_i} B_{i,k-1}(x) + \frac{t_{i+k+1} - x}{t_{i+k+1} - t_{i+1}} B_{i+1,k-1}(x).</math>

That is, <math>B_{j,0}(x)</math> is piecewise constant one or zero indicating which knot span ''x'' is in (zero if knot span ''j'' is repeated). The recursion equation is in two parts: 
:<math>\frac{x - t_i}{t_{i+k} - t_i}</math> 
ramps from zero to one as ''x'' goes from <math>t_i</math> to <math>t_{i+k}</math>, and
:<math>\frac{t_{i+k+1} - x}{t_{i+k+1} - t_{i+1}}</math>
ramps from one to zero as ''x'' goes from <math>t_{i+1}</math> to <math>t_{i+k+1}</math>. The corresponding ''B''s are zero outside those respective ranges. For example, <math>B_{i,1}(x)</math> is a [[triangular function]] that is zero below <math>x = t_i</math>, ramps to one at <math>x = t_{i+1}</math> and back to zero at and beyond <math>x = t_{i+2}</math>. However, because B-spline basis functions have local [[support (mathematics)|support]], B-splines are typically computed by algorithms that do not need to evaluate basis functions where they are zero, such as [[de Boor's algorithm]].

This relation leads directly to the [[FORTRAN]]-coded algorithm BSPLV, which generates values of the B-splines of order ''n'' at ''x''.<ref>de Boor, p. 134.</ref> The following scheme illustrates how each piece of order ''n'' is a linear combination of the pieces of B-splines of order ''n''&nbsp;−&nbsp;1 to its left.

:<math>
\begin{matrix}
   &   & 0 \\
   & 0 & \\
 0 &   & B_{i-2,2} \\
   & B_{i-1,1} & \\
 B_{i,0} & & B_{i-1,2}\\
   & B_{i,1} & \\
 0 &   & B_{i,2} \\
   & 0 & \\
   &   & 0
\end{matrix}
</math>

Application of the recursion formula with the knots at <math>(0, 1, 2, 3)</math> gives the pieces of the uniform B-spline of order 3 
:<math>
\begin{align}
 B_1 &= x^2/2, & 0 &\le x < 1, \\
 B_2 &= (-2x^2 + 6x - 3)/2, & 1 &\le x < 2, \\
 B_3 &= (3 - x)^2/2, & 2 &\le x < 3.
\end{align}
</math>
These pieces are shown in the diagram. The continuity property of a quadratic spline function and its first derivative at the internal knots are illustrated, as follows
: <math>
\begin{align}
& \text{At }x = 1\colon\ B_1 = B_2 = 0.5,\ \frac{dB_1}{dx} = \frac{dB_2}{dx} = 1. \\[6pt]
& \text{At }x = 2\colon\ B_2 = B_3 = 0.5,\ \frac{dB_2}{dx} = \frac{dB_3}{dx} = -1.
\end{align}
</math>
The second derivative of a B-spline of degree 2 is discontinuous at the knots:
: <math>\frac{d^2B_1}{dx^2} = 1,\ \frac{d^2B_2}{dx^2} = -2,\ \frac{d^2B_3}{dx^2} = 1.</math>

Faster variants of the de Boor algorithm have been proposed, but they suffer from comparatively lower stability.<ref>{{cite journal |last=Lee |first=E. T. Y. |date=December 1982 |title=A Simplified B-Spline Computation Routine |journal=Computing |volume=29 |issue=4 |pages=365–371 |doi=10.1007/BF02246763|s2cid=2407104 }}</ref><ref>{{cite journal | author = Lee, E. T. Y. | journal = Computing | issue = 3 | pages = 229–238 | doi=10.1007/BF02240069 |title = Comments on some B-spline algorithms | volume = 36 | year = 1986| s2cid = 7003455 }}</ref>

===Cardinal B-spline===

A cardinal B-spline has a constant separation ''h'' between knots. The cardinal B-splines for a given order ''n'' are just shifted copies of each other. They can be obtained from the simpler definition.<ref>de Boor, p. 322.</ref>

:<math>B_{i,n,t}(x) = \frac{x-t_i}{h} n[0, \dots, n](\cdot - t_i)^{n-1}_+.</math>

The "placeholder" notation is used to indicate that the ''n''-th [[divided difference]] of the function <math>(t-x)^{n-1}_+</math> of the two variables ''t'' and ''x'' is to be taken by fixing ''x'' and considering <math>(t - x)^{n-1}_+</math> as a function of ''t'' alone.

A cardinal B-spline has uniformly spaced knots, therefore interpolation between the knots equals convolution with a smoothing kernel.

Example, if we want to interpolate three values in between B-spline nodes (<math>\textbf{b}</math>), we can write the signal as

: <math>\mathbf{x} = [\mathbf{b}_1, 0, 0, \mathbf{b}_2, 0, 0, \mathbf{b}_3, 0, 0, \dots, \mathbf{b}_n, 0, 0].</math>

Convolution of the signal <math>\mathbf{x}</math> with a rectangle function <math>\mathbf{h} = [1/3, 1/3, 1/3]</math> gives first order interpolated B-spline values. Second-order B-spline interpolation is convolution with a rectangle function twice <math>\mathbf{y} = \mathbf{x} * \mathbf{h} * \mathbf{h}</math>; by iterative filtering with a rectangle function, higher-order interpolation is obtained.

Fast B-spline interpolation on a uniform sample domain can be done by iterative mean-filtering. Alternatively, a rectangle function equals [[sinc]] in [[Fourier domain]]. Therefore, cubic spline interpolation equals multiplying the signal in Fourier domain with sinc<sup>4</sup>.

See [[Irwin–Hall distribution#Special cases]] for algebraic expressions for the cardinal B-splines of degree 1–4.

===P-spline===

The term P-spline stands for "penalized B-spline". It refers to using the B-spline representation where the coefficients are determined partly by the data to be [[Curve fitting|fitted]], and partly by an additional [[penalty function]] that aims to impose [[smoothness]] to avoid [[overfitting]].<ref>Eilers, P. H. C. and Marx, B. D. (1996). Flexible smoothing with B-splines and penalties (with comments and rejoinder). Statistical Science 11(2): 89–121.</ref>

Two- and multidimensional P-spline approximations of data can use the [[face-splitting product]] of matrices to the minimization of calculation operations.<ref name="spline">{{cite journal |last1=Eilers |first1=Paul H. C. |last2=Marx |first2=Brian D. |year=2003 |title=Multivariate calibration with temperature interaction using two-dimensional penalized signal regression |journal=Chemometrics and Intelligent Laboratory Systems |volume=66 |issue=2 |pages=159–174 |doi=10.1016/S0169-7439(03)00029-7}}</ref>