Spline (mathematics)
In mathematics, a spline is a special function defined piecewise by polynomials. In interpolating problems, spline interpolation is often preferred to polynomial interpolation because it yields similar results, even when using low degree polynomials, while avoiding Runge's phenomenon for higher degrees. In the computer science subfields of computer-aided design and computer graphics, the term spline more frequently refers to a piecewise polynomial (parametric) curve. 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. The term spline comes from the flexible spline devices used by shipbuilders and draftsmen to draw smooth shapes. Introduction. The term "spline" is used to refer to a wide class of functions that are used in applications requiring data interpolation and/or smoothing. The data may be either one-dimensional or multi-dimensional. Spline functions for interpolation are normally determined as the minimizers of suitable measures of roughness (for example integral squared curvature) subject to the interpolation constraints. Smoothing splines may be viewed as generalizations of interpolation splines where the functions are determined to minimize a weighted combination of  the average squared approximation error over observed data and the roughness measure. For a number of meaningful definitions of the roughness measure, the spline functions are found to be finite dimensional in nature, which is the primary reason for their utility in computations and representation. For the rest of this section, we focus entirely on one-dimensional, polynomial splines and use the term "spline" in this restricted sense. Definition. We begin by limiting our discussion to polynomials in one variable. In this case, a spline is a piecewise polynomial function. This function, call it "S", takes values from an interval  ["a","b"] and maps them to formula_1, the set of real numbers, We want "S" to be piecewise defined. To accomplish this, let the interval ["a","b"] be covered by "k" ordered, disjoint subintervals, On each of these "k" "pieces" of ["a","b"], we want to define a polynomial, call it "P". On the "i"th subinterval of ["a","b"], "S" is defined by "P", The given "k+1" points "t" are called knots. The vector formula_11 is called a knot vector for the spline. If the knots are equidistantly distributed in the interval ["a","b"] we say the spline is uniform, otherwise we say it is  non-uniform. If the polynomial pieces "P" each have degree at most "n", then the spline is said to be of degree formula_12 (or of order "n+1"). If formula_13 in a neighborhood of "t", then the spline is said to be of smoothness (at least) formula_14 at "t". That is, at "t" the two polynomial pieces "P" and "P" share common derivative values from the derivative of order 0 (the function value) up through the derivative of order "r" (in other words, the two adjacent polynomial pieces connect with loss of smoothness of at most "n" - "r") A vector formula_19  such that the spline has smoothness formula_14 at "t" for formula_21 is called a smoothness vector for the spline. Given a knot vector formula_22, a degree "n", and a smoothness vector formula_23 for formula_22, one can consider the set of all splines of degree formula_12 having knot vector formula_22 and smoothness vector formula_23. Equipped with the operation of adding two functions (pointwise addition) and taking real multiples of functions, this set becomes a real vector space. This spline space is commonly denoted by formula_28. In the mathematical study of polynomial splines the question of what happens when two knots, say  t and "t", are moved together has an easy answer. The polynomial piece "P"("t") disappears, and the pieces "P"("t") and "P"("t") join with the sum of the continuity losses for "t" and "t". That is, 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 "n" and its extended knot vector where "t" is repeated "j" times for formula_32. A parametric curve on the interval ["a","b"] is a  spline curve if both "X" and "Y" are spline functions of the same degree with the same extended knot vectors on that interval. Examples. Suppose the interval ["a","b"] is [0,3] and the subintervals are [0,1], [1,2], and [2,3]. Suppose the polynomial pieces are to be of degree 2, and the pieces on [0,1] and [1,2] must join in value and first derivative while the pieces on [1,2] and [2,3] join simply in value (at "t" = 2). This would define a type of spline "S"("t") for which would be a member of that type, and also would be a member  of that type. The extended knot vector for this type of spline would be (0, 1, 2, 2, 3). The simplest spline has degree 0. It is also called a step function. The next most simple spline has degree 1. It is also called a linear spline. A closed linear spline (i.e, the first knot and the last are the same) in the plane is just a polygon. A common spline is the natural cubic spline of degree 3 with continuity "C". 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 This forces the spline to be a straight line outside of the interval, while not disrupting its smoothness. Algorithm for computing natural cubic splines. Cubic splines are of the form formula_41. Given set of coordinates formula_42 we wish to find set of formula_43 splines formula_44 for formula_45 These must satisfy: Let us define one cubic spline formula_52 as a 5-tuple formula_53 where formula_54 and formula_55 correspond to coefficients in the form shown earlier and formula_56 is equal to formula_57 Algorithm for computing Natural Cubic Splines: Input: set of coordinates formula_58, with formula_59  Output: set splines which is composed of "n" 5-tuples. 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 "C" splines. The literature of splines is replete with names for special types of splines. These names have been associated with: Often a special name was chosen for a type of spline satisfying two or more of the  main items above. For example, the Hermite spline is a spline that is expressed using Hermite polynomials to represent each of the individual polynomial pieces. These are most often used with "n" = 3; that is, as Cubic Hermite splines. In this degree they may additionally be chosen to be only tangent-continuous ("C"); which implies that all interior knots are double. Several methods have been invented to fit such splines to given data points; that is, to make them into interpolating splines, and to do so by estimating plausible tangent values where each two polynomial pieces meet (giving us  Cardinal splines, Catmull-Rom splines, and Kochanek-Bartels splines, depending on the method used). For each of the representations, some means of evaluation must be found so that values of the spline can be produced on demand. For those representations that express each individual polynomial piece "P"("t") in terms of some basis for the degree "n" polynomials, this is conceptually straightforward: However, the evaluation and summation steps are often combined in clever ways. For example, Bernstein polynomials are a basis for polynomials that can be evaluated in linear combinations efficiently using special recurrence relations. This is the essence of De  Casteljau's algorithm, which features in Bézier curves and Bézier splines) For a representation that defines a spline as a linear combination of basis splines, however, something more sophisticated is needed. The de Boor algorithm is an efficient method for evaluating B-splines. History. Before computers were used, numerical calculations were done by hand. Although piecewise-defined functions like the sign function or step function were used, polynomials were generally preferred because they were easier to work with. Through the advent of computers splines have gained importance. They were first used as a replacement for polynomials in interpolation, then as  a tool to construct smooth and flexible shapes in computer graphics. It is commonly accepted that the first mathematical reference to splines is the 1946 paper by Schoenberg, which is probably the first place that the word "spline" is used in connection with smooth, piecewise polynomial approximation. However, the ideas have their roots in the aircraft and shipbuilding industries. In the foreword to (Bartels et al., 1987), Robin Forrest describes "lofting", a technique used in the British aircraft industry during World War II to construct templates for airplanes by passing thin wooden strips (called "splines") through points laid out on  the floor of a large design loft, a technique borrowed from ship-hull design. For years the practice of ship design had employed models to design in the small. The successful design was then plotted on graph paper and the key points of the plot were re-plotted on larger graph paper to full size. The thin wooden strips provided an interpolation of the key points into smooth curves. The strips would be held in place at discrete points (called "ducks" by Forrest; Schoenberg used "dogs" or "rats") and between these points would assume shapes of minimum strain energy. According  to Forrest, one possible impetus for a mathematical model for this process was the potential loss of the critical design components for an entire aircraft should the loft be hit by an enemy bomb. This 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 at Boeing and (somewhat later) by M.A. Sabin at British Aircraft Corporation. The word "spline" was originally an East Anglian dialect word. 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, 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 being done  at Pratt & Whitney Aircraft, where two of the authors of (Ahlberg et al., 1967) — 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) and (Young, 1997). Davis (1997) summarizes some of this material. External links. Theory Excel Function Online utilities Computer Code