Spline (mathematics)

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
Single knots at 1/3 and 2/3 establish a spline of three cubic polynomials meeting with C2 continuity. Triple knots at both ends of the interval ensure that the curve interpolates the end points. The shown curve is a parametric spline and not a polynomial function.

In mathematics, a spline is a function defined piecewise by polynomials. Spline functions are used to interpolate intervals between data points and are used extensively in the computer science subfields of computer-aided design and computer graphics to represent arbitrary curves and surfaces.

Splines are popular curves in these subfields because of the simplicity of their construction, their ease and accuracy of evaluation, and their capacity to approximate complex shapes through curve fitting and interactive curve design.[citation needed] In interpolation problems, spline interpolation is often preferred to polynomial interpolation because polynomial interpolation over a number of data points can lead to polynomials of high degrees and oscillations due to Runge's phenomenon, while a spline is made up of lower degree polynomials which avoid this problem.

The term spline comes from the flexible wooden strips called splines historically used by shipbuilders and draftsmen to draw smooth shapes.[1]

Introduction[edit]

The term "spline" is used to refer to a wide class of functions that are used for two main purposes:

  • Interpolation: Given a set of data points, a spline function is fitted to pass through each point while, typically, minimizing some measure of curvature to produce a smooth curve.
  • Smoothing: Given a set of data points, often including noise, a spline function is fitted to give a 'line of best fit', in a process similar to least squares approximation. The objectives of fitting the spline are to minimize a combination of some measure of distance between the spline and data points, and some measure of curvature. By changing the weights of each objective, the resulting spline can provide a better fit to the data points, or a smoother curve, respectively.

Splines are described by the type of polynomial functions they are composed of. Common examples are:

  • Polynomial spline, which are often described by the degree of the polynomial used, such as linear, quadratic, cubic, etc.
  • B-spline or basis spline.
  • Bézier spline as a spline constructed of piece-wise Bézier curves.
  • Periodic spline, used to approximate periodic functions. The spline is constructed such that the polynomial in the last interval is the same as in the first.[2]
  • Cubic Hermite spline or cubic Hermite interpolator is a spline where each piece is a third-degree polynomial specified in Hermite form.
  • NURBS, or Non-Uniform Rational B-Spline. In these the piecewise polynomial is a ratio, or rational function, of B-spline functions. NURBS are able to model exactly lines, planes, conic sections and quadric surfaces.[3]

Splines may be univariate (e.g., 2-D curves), bivariate (e.g., 3-D surfaces) or be multivariate to describe functions of higher dimension.

Definition[edit]

The spline maps values from an interval to the set of real numbers

For the piecewise definition of the interval is partitioned in subintervals that together make up the whole interval. This is done by selecting additional numbers , representing points within this interval, such that

yielding subintervals

such that

For each of these subintervals a polynomial will be constructed

Excluding the right endpoints of each subinterval (with exception of the rightmost) allows the piecewise definition of on by the polynomials on the subinterval

If the polynomials each have degree at most , then the spline is said to be of degree (or is of order ).

Parametric Representation[edit]

The definition given above described the spline explicitly in terms of the independent variable . Splines may also be represented parametrically in terms of an independent parameter called, for example, .

A parametric curve in can be defined as a continuous map from an interval, the domain of the parameter, to the space For example, a plane curve is a mapping from the interval to the Euclidean plane

with and being real functions on

If both functions and are simple spline functions of the same degree with the same extended knot vectors on that interval, then

specifies a spline curve in .

Continuity[edit]

The polynomial functions are continuous within each subinterval of the spline, and by definition meet exactly at the boundaries. This requirement means splines have at least class parametric continuity (i.e., continuity of position at the sub-interval boundaries). If the first derivatives of the polynomials are equal at subinterval boundaries, the spline has class continuity (continuity of slope). Equal second derivatives gives class continuity (continuity of curvature), and so on. As the degree of continuity increases, the spline becomes increasingly smooth.[4]

If the first derivatives of the two polynomials match at then has continuity at Assuming a spline of degree , the loss of smoothness (with respect to the maximal nontrivial smoothness) at the point is given by A loss of at , i.e. establishes continuity there by imposing the condition a smaller loss, yields additional equations for involving the derivatives up to the desired smoothness. Collecting the values yields the smoothness vector of the spline .

Natural splines are those where second derivatives at and are set to zero.

Locally negative continuity[edit]

It might be asked what meaning more than n multiple knots in a knot vector have, since this would lead to continuities like

at the location of this high multiplicity. By convention, any such situation indicates a simple discontinuity between the two adjacent polynomial pieces. This means that if a knot ti appears more than n + 1 times in an extended knot vector, all instances of it in excess of the (n + 1)th can be removed without changing the character of the spline, since all multiplicities n + 1, n + 2, n + 3, etc. have the same meaning. It is commonly assumed that any knot vector defining any type of spline has been culled in this fashion.

Knots[edit]

The points are called knots. The vector is called a knot vector for the spline. If the knots are equidistantly distributed in the interval the spline is called uniform, otherwise it is non-uniform.

An inner knot can be "deleted" by making it equal to a neighboring knot . By identifying with the polynomial piece disappears, and the pieces and join with the sum of the continuity losses for and . That is,

where

This leads to a more general understanding of a knot vector. The continuity loss at any point can be considered to be the result of multiple knots located at that point, and a spline type can be completely characterized by its degree and its extended knot vector

where is repeated times for . Obviously, does not refer anymore to the number of components in this vector.

Spline Space[edit]

Given a knot vector , a degree , and a smoothness vector for this knot vector, one can consider the set of all splines of degree having this knot vector and this smoothness vector . Equipped with the operation of adding two piecewise defined polynomial functions (pointwise addition) and taking their real multiples, together with the zero function, this set becomes a real vector space. This spline space is commonly denoted by . Briefly this means that adding any two splines of a given type produces spline of that given type, and multiplying a spline of a given type by any constant produces a spline of that given type.

The dimension of the space containing all splines of a certain type can be counted from the extended knot vector:

The dimension is equal to the sum of the degree plus the multiplicities

If a type of spline has additional linear conditions imposed upon it, then the resulting spline will lie in a subspace. The space of all natural cubic splines, for instance, is a subspace of the space of all cubic splines.

Polynomial Interpolation Splines[edit]

Suppose it is desired to provide a continuous interpolation for a data set given by the points

where

There will be intervals, each with a polynomial:

If these polynomials have a degree , then spline will have a continuous derivative on .

Linear Spline[edit]

A linear spline has degree 1 (i.e., ) and is of the form:

Each polynomial has two coefficients and two boundary conditions, . Solving for the coefficients gives the final form of the spline:

Quadratic Spline[edit]

The quadratic spline has degree 2 and so has continuous first derivatives across subintervals. Its form is

Thus there are coefficients to solve for. In addition to the positional boundary conditions (i.e., ), the first derivatives of the polynomials must be equal at the interior knots, i.e.,

This provides a further boundary conditions for a total of equations with which to solve for the coefficients. To derive a unique solution, the analyst must supply one more constraint, a value for the first derivative at either end point of the spline. The values of the coefficients may then be determined to give the final equations for the spline.

Cubic spline[edit]

The cubic spline polynomials are:

The continuity requirements become

Continuity of the resulting spline is of class .

There are a total of equations here to solve for the polynomial coefficients, so two more constraints are needed. Choices available to the analyst include:

  • so-called natural cubic spline conditions :
  • use estimates of the actual second derivatives at the interval end points :
  • so-called not-a-knot condition on the first interior points, i.e., eliminate the knots at which has the effect of making the polynomials on either side of these knots identical, i.e., .
  • so-called complete cubic spline condition where slopes of the end points are specified :

Using one of these options, a linear system of equations for the unknown polynomial coefficients may be set up and solved.

A somewhat shorter solution can be obtained by applying some of the boundary conditions to the polynomials and providing an initial simplification to reduce the number of coefficients needing to be found. The polynomial form becomes

where

  • are the values of the second derivative at the knot.
  • are the values of the function at the knot.

The second derivatives at the knots, , are unknown yet, except for values possibly assigned to the end points . A system of linear equations in these unknown values may be set up as

where

The matrix has a tridiagonal form

which may be solved easily using a tridiagonal matrix algorithm.

Examples[edit]

Quadratic interpolation spline[edit]

A quadratic spline is to be created to interpolate the points

The polynomial equations are:

Substituting the subinterval end points into each polynomial gives

Equating the derivatives of the polynomials gives

For the remaining constraint, we select the derivative at giving

Solving for the unknown coefficients finds their values as

The spline function then becomes



A common spline is the natural cubic spline of degree 3 with continuity C2. The word "natural" means that the second derivatives of the spline polynomials are set equal to zero at the endpoints of the interval of interpolation

Algorithm for computing natural cubic splines[edit]

Cubic splines have polynomial pieces of the form Given coordinates we find polynomials, and which satisfy for :

and

One such polynomial is given by a 4-tuple where and correspond to the coefficients as used above.

Computation of Natural Cubic Splines:
Input: a set of coordinates
Output: a spline as a set of polynomial pieces, each represented by a 5-tuple.

  1. Create a new array a of size n + 1, and for set
  2. Create new arrays b, d and μ each of size n
  3. Create a new array h of size k and for set
  4. Create a new array β of size n-1 and for set
  5. Create new arrays c, l, and z each of size .
  6. Set
  7. For
    1. Set
    2. Set
    3. Set
  8. Set
  9. For
    1. Set
    2. Set
    3. Set
  10. Create the spline as a new set of polynomials and call it output_set. Populate it with n 4-tuples for the polynomials Pi.
  11. For
    1. Set Pi,a = ai
    2. Set Pi,b = bi
    3. Set Pi,c = ci
    4. Set Pi,d = di
  12. Output output_set

History[edit]

Traditionally, splines were long flexible strips of wood used for lofting the complex curves of boat hulls. These drafting techniques were adopted as well by the aircraft and automobile body styling industries. The strips would be held in place at discrete points by weights (called "ducks", "dogs" or "rats") and between these points would assume shapes of minimum strain energy. It was discovered in the mid-1700s by Euler and the brothers Bernoulli that the shape of the spline forms a piecewise cubic polynomial with no curvature at the ends (i.e., the "natural spline" condition).[5]

A wooden spline

It is commonly accepted that the first use of the term "spline function" is in the 1946 papers by Schoenberg[6][7], which described it in terms of a smooth, piecewise polynomial approximation.[8]

In the foreword to (Bartels et al., 1987)[9], Robin Forrest describes lofting used in the British aircraft industry during World War II to construct templates, or patterns, that contained the full-size geometric data needed for airplane manufacturing. Aircraft factories stored large numbers of these templates, and Forrest suggests one possible impetus for moving from physical to mathematical models for aircraft geometry was the potential catastrophic loss of the critical design data should the loft be hit by an enemy bomb. This desire gave rise to "conic lofting", which used conic sections to model the position of the curve between the ducks. Conic lofting was replaced by what we would call splines in the early 1960s based on work by J. C. Ferguson[10] at Boeing and (somewhat later) by M. A. Sabin at British Aircraft Corporation.

The use of splines for modeling automobile bodies seems to have several independent beginnings. Credit is claimed on behalf of de Casteljau at Citroën, Pierre Bézier at Renault, and Birkhoff[11], Garabedian, and de Boor at General Motors (see Birkhoff and de Boor, 1965), all for work occurring in the very early 1960s or late 1950s. At least one of de Casteljau's papers was published, but not widely, in 1959. De Boor's work at General Motors resulted in a number of papers being published in the early 1960s, including some of the fundamental work on B-splines.

Work was also done at Pratt & Whitney Aircraft, where two of the authors of (Ahlberg et al., 1967)[12]—the first book-length treatment of splines—were employed, and the David Taylor Model Basin, by Feodor Theilheimer. The work at General Motors is detailed nicely in (Birkhoff, 1990)[13] and (Young, 1997)[14]. Davis (1997)[15] summarizes some of this material.

References[edit]

  1. ^ Wegman, Edward J., and Ian W. Wright (1983). "Splines in statistics". Journal of the American Statistical Association. 78 (382): 351–365. JSTOR 2288640.CS1 maint: Multiple names: authors list (link)
  2. ^ Schumaker, Larry (2007). Spline functions : basic theory (3rd ed.). Cambridge University Press. p. 297. ISBN 978-0521705127.
  3. ^ Rogers, David F. (2000). An introduction to NURBS : with historical perspective. Morgan Kaufmann Publishers. p. 129. ISBN 978-1558606692.
  4. ^ Schumaker, Larry (2007). Spline functions : basic theory (3rd ed.). Cambridge University Press. p. 13. ISBN 978-0521705127.
  5. ^ Schumaker, Larry (2007). Spline functions : basic theory (3rd ed.). Cambridge University Press. p. 6. ISBN 978-0521705127.
  6. ^ Schoenberg, Isaac J. (1946). "Contributions to the Problem of Approximation of Equidistant Data by Analytic Functions: Part A.—On the Problem of Smoothing or Graduation. A First Class of Analytic Approximation Formulae" (PDF). Quarterly of Applied Mathematics. 4 (2): 45–99.
  7. ^ Schoenberg, Isaac J. (1946). "Contributions to the Problem of Approximation of Equidistant Data by Analytic Functions: Part B.—On the Problem of Osculatory Interpolation. A Second Class of Analytic Approximation Formulae" (PDF). Quarterly of Applied Mathematics. 4 (2): 112–141.
  8. ^ Schumaker, Larry (2007). Spline functions : basic theory (3rd ed.). Cambridge University Press. p. 6. ISBN 978-0521705127.
  9. ^ Bartels, Richard H.; Beatty, Brian A.; Barsky, John C. (1987). An Introduction to Splines for Use in Computer Graphics and Geometric Modeling. San Mateo: Morgan Kaufmann. ISBN 0-934613-27-3.
  10. ^ Ferguson, James C. (1964). "Multivariable Curve Interpolation". Journal of the ACM. 11 (2): 221–228. doi:10.1145/321217.321225.
  11. ^ Birkhoff; de Boor (1965). "Piecewise polynomial interpolation and approximation". In Garabedian, H. L. (ed.). Proc. General Motors Symposium of 1964. New York and Amsterdam: Elsevier. pp. 164–190.
  12. ^ Ahlberg, J. Harold; Nielson, Edwin N.; Walsh, Joseph L. (1967). The Theory of Splines and Their Applications. New York: Academic Press. ISBN 0-12-044750-9.
  13. ^ Birkhoff (1990). "Fluid dynamics, reactor computations, and surface representation". In Nash, Steve (ed.). A History of Scientific Computation. Reading: Addison-Wesley. ISBN 0-201-50814-1.
  14. ^ Young (1997). "Garrett Birkhoff and applied mathematics". Notices of the AMS. 44 (11): 1446–1449.
  15. ^ Davis (1997). "B-splines and Geometric design". SIAM News. 29 (5).

External links[edit]

Theory

Online utilities

Computer Code