yawiki.org entry for Spline (mathematics)

	Navigation Home Recent Most Active Popular Blog Credits RSS
	Interaction Register Statistics
	Help Suggestions Contact Us How to Edit Help

[Edit]

In the mathematical field of numerical analysis, 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 fields of computer-aided design and computer graphics, the term spline more frequently refers to a piecewise parametric polynomial curve. Splines are a popular representation of 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.

    Spline (mathematics)
        Introduction
        Definition
        Examples
        Notes
        Representations and names
        History

top

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. Splines may be used for interpolation and/or smoothing of
either one-dimensional or multi-dimensional data. 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.

top

Definition
A (univariate, polynomial) spline is a piecewise polynomial function.
In its most general form a polynomial spline

S: a,b o mathbb

consists of polynomial pieces

P_i: t_i, t_{i+1} o mathbb

, where

$a=t_0 < t_1 < cdots < t_ < t_ = b$ .

That is,

$S(t) = P_0 (t) mbox t_0 le t < t_1,$

$S(t) = P_1 (t) mbox t_1 le t < t_2,$

$cdots$

$S(t) = P_ (t) mbox t_ le t le t_.$

The given k values t_i are called knots. The vector

=(t_0, dots, t_)

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 on the subintervals

$t_i,t_{i+1} mbox i = 0,ldots k-2$

all have degree at most n, then the spline is said to be of degree

leq n

(or of
order n+1).

If

Sin C^

in a neighborhood of

t_i

, then the spline is said to be
of smoothness (at least)

C^

t_i

. That is,
the two pieces

P_

and

P_

share common
derivative values from the derivative of order 0 (the function value)
up through the derivative of order r_i.
Or stated differently, the two adjacent polynomial pieces
connect with loss of smoothness of (at most) j_i,
defined by

r_i=n-j_i

.
(Expressing the connectivity as a "loss of smoothness" is reasonable, since
if S were a simple polynomial throughout a neighborhood of
t_i, it would have smoothness Cⁿ
at t_i, and you would expect to lose smoothness
in order to break a polynomial apart into pieces.)
A vector

=(r_1, dots, r_)

such that the spline has smoothness

C^

t_i

for

0 is called a

smoothness vector for the spline.

Given a knot vector

, a degree n, and a smoothness vector

for

, one can consider the set of all splines of degree

leq n

having knot vector

and smoothness vector

. 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

S^_n()

.

In the mathematical study of polynomial splines the question of what happens when two knots,
say t_i and t_i+1,
are moved together has an easy answer. The polynomial piece
P_i(t)
disappears, and the pieces
P_i−1(t) and P_i+1(t)
join with the sum of the continuity losses for
t_i and t_i+1.
That is,

$S(t) in C^t_i = t_{i+1}$

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

a=t_0 < t_1 = cdots = t_1 < cdots < t_ = cdots = t_ < t_ = b

where

t_i

is repeated

j_i

times
for

i = 1, dots , k-2

.

A parametric curve on the interval ''a'',''b''

$G(t) = < X(t), Y(t) > mbox t in a , b$

is a spline curve if both X and Y are splines
of the same degree with the same extended knot vectors on that interval.

top

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
(at t=1)
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

$S(t) = P_0 (t) = -1+4t-t^2 mbox 0 le t < 1$

$S(t) = P_1 (t) = 2t mbox 1 le t < 2$

$S(t) = P_2 (t) = 2-t+t^2 mbox 2 le t le 3$

would be a member of that type, and also

$S(t) = P_0 (t) = -2-2t^2 mbox 0 le t < 1$

$S(t) = P_1 (t) = 1-6t+t^2 mbox 1 le t < 2$

$S(t) = P_2 (t) = -1+t-2t^2 mbox 2 le t le 3$

would be a member of that type.
(Note: the polynomial piece

2t

is quadratic, since it can be written

2t + 0t^2

. Any polynomial of one degree is trivially a polynomial of higher
degree simply by this trick of adding appropriate powers with zero coefficients.)
The extended knot vector for this type of spline would be

0, 1, 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.
The corresponding parametric curve having linear
spline components X(t) and Y(t)
just a polygon.

A common spline is the natural cubic spline of degree 3 with continuity

C^2

.
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

$S$ (a) , = S(b) = 0.

This forces the spline to be a straight line outside of the interval, while not disrupting its smoothness.

top

Notes
It might be asked what meaning more than

n

multiple knots in a knot vector have,
since this would lead to continuities like

$S(t) in C^ mbox m > 0$

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

t_i

appears more than

n+1

times in an extended knot vector, all instances of it in excess of the

n+1^

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.

The classical spline type of degree n used in numerical analysis has continuity

$S(t) in mathrm^a,b$ ,

which means that every two adjacent polynomial pieces meet
in their value and first n-1 derivatives at each knot.
The mathematical spline that most closely models the spline (device)
is a cubic (n=3), twice continuously differentiable (C²), natural
spline, which is a spline of this classical type with additional
conditions imposed at endpoints a and b.

Another type of spline that is much used in graphics,
for example in drawing
programs such as Adobe Illustrator from Adobe Systems,
has pieces that are cubic but has continuity only at most

$S(t) in mathrm^a,b$ .

This spline type is also used in PostScript
as well as in the definition of some computer typographic fonts.

Many computer-aided design systems that are designed for high-end
graphics and animation use extended knot vectors,
for example Maya from Alias.
Computer-aided design systems often use an extended
concept of a spline known as a Nonuniform rational B-spline (NURBS).

If sampled data from a function or a physical object is available,
spline interpolation is an approach to creating a spline that approximates
that data.

top

Representations and names
For a given interval

a,b

and
a given extended knot vector on that interval, the splines of degree n form a vector space.
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:

a = t_0 < underbrace_ < cdots < underbrace_ < t_ = b

j_i le n+1 ~,~~ i=1,ldots,k-2
The dimension is equal to the sum of the degree plus the multiplicities

$d = n + sum_^ j_i$

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^2

splines.

The literature of splines is replete with names for special types of splines.
These names have been associated with:

The choices made for representing the spline, for example:

using basis B-splines as basis functions for the entire spline (giving us the name B-splines)

using Bernstein polynomials as employed by Pierre Bézier to represent each polynomial piece (giving us the name Bézier splines)

The choices made in forming the extended knot vector, for example:

using single knots for

C^

continuity and spacing these knots evenly on ''a'',''b'' (giving us uniform splines)

using knots with no restriction on spacing (giving us nonuniform splines)

Any special conditions imposed on the spline, for example:

enforcing zero second derivatives at a and b (giving us natural splines)

requiring that given data values be on the spline (giving us interpolating splines)

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^1

); 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_i(t)

in terms of
some basis for the degree n polynomials, this is conceptually straightforward:

For a given value of the argument t, find the interval in which it lies

t in t_i,t_)

Look up the polynomial basis chosen for that interval

P_0, ldots, P_

Find the value of each basis polynomial at

, t

P_0(t), ldots, P_(t)

Look up the coefficients of the linear combination of those basis polynomials that give the spline on that interval

c_0, ldots, c_

Add up that linear combination of basis polynomial values to get the value of the spline at

, t

sum_^ c_j P_j(t)

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.

top

History
Before computers were used, numerical calculations were done by hand. Although piecewise-defined functions like the signum 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 ship-building 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 1960's 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 GM resulted in a number of papers being published in the early 60's, 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 GM is
detailed nicely in (Birkhoff, 1990) and (Young, 1997). Davis (1997) summarizes some of this material.

	Source Privacy License Download Contact Us Atlas Scientus.org Dictionary (Yet Another Wiki) RC : 1.39 This article is licensed under the GNU Free Documentation License [copyleft]. It uses material from the Wikipedia article "Spline (mathematics)". link