Www.cs.utexas.edu



FITPACK

A Software Package for

Curve and Surface Fitting

Employing Splines Under Tension

by

Alan Kaylor Cline

Department of Computer Sciences

The University of Texas at Austin

Part A

I. Introduction to Curve and Surface Fitting Theory

I.1 Interpolation

Interpolation is a dangerous activity. It involves predicting the overall behavior of systems from a set of observations which is finite and occasionally very small. Consequently, many interpolation approaches are doomed to failure simply because (although they obey all the specified constraints) they do not conform with the mental expectations of the user.

A person seeking to interpolate data should incorporate as much knowledge of the behavior of the system as possible. Such properties as periodicity, smoothness, convexity, monotonicity, positivity, or exponential growth may be required of the interpolation because the model demands them. For example, if we were to fit rainfall activity we certainly would demand non-negative values of the fit. We might also desire annual periodicity in this case. One cannot expect a general purpose fitting method to reproduce these properties simply because the model possesses them or the modeler expects them. The modeler must assist the method in achieving the properties. Some methods allow for the automatic detection of certain properties such as monotonicity or convexity. Others allow the modeler to declare that certain properties are to be achieved. However, some methods cannot reproduce such properties in any circumstance. This package, FITPACK, allows the modeler to obtain a fit in which the function values maintain specified upper and lower bounds, in which the slopes also maintain specified upper and lower bounds, and in which regions of convexity and concavity can be specified.

Certain additional trends in the fitted function are achievable only after appropriate transformations on the part of the modeler. The following example shows how an exponential trend can be incorporated. Similar approaches may be used to incorporate other trends.

Example: n Suppose we are given a set of ordered pairs {(x ,y )} and it is our i i i=1 task to find a function f so that f(x ) = y for i = 1,...,n. The model for i i the system that produced the data suggests that an exponential trend is present, i.e.:

bx y ~ ae i i for some values of a and b. (Possibly the data are from the growth of some population or the decay of some radioactive substance.) If we logarithmically transform the data we have:

ln y ~ a + bx i i which is a linear trend of ln y with x . Suppose our general purpose i i interpolation method does an acceptable job of fitting data with linear trends (as most do) and so we employ it to produce a function g so that:

g(x ) = ln y for i = 1,...,n. i i The interpolation used for the original data is the composition of this g g(x) with exponentiation (i.e., f(x) = e ). Notice that our constraints are g(x ) ln y satisfied, since f(x ) = e i = e i = y , but also f has an exponential i i trend, since g has a linear trend.

I.2 Tension Splines

Henceforth, it will be assumed that whatever transformations are necessary have already been applied: we shall only deal with the problem in which the resulting trend can be suitably exhibited using the interpolation method. The methods employed in this package use tension splines as originally described in Schweikert [25]. Modifications and extensions are described in Cline [3-6], Lynch [10], Nielson [13], Pruess [16-18], and Spath [26].

The tension spline is a generalization of the cubic spline (see Ahlberg, Nilson, and Walsh [1] or deBoor [7]). A cubic spline is simply a single function of a single variable which everywhere has two continuous derivatives and is composed of segments of cubic polynomials. Thus if f is a cubic spline, its second derivative f", must be a set of linear polynomials in pieces. Yet since f" is continuous, it is actually a polygonal line. In the tension spline a factor sigma, the "tension factor," is introduced which generalizes the cubic spline. With the tension spline, as with the cubic spline, the second derivative is continuous. However, instead of specifying f" as a polygonal 2 line, now f"-sigma f is a polygonal line.

Obviously, for sigma = 0, the tension spline is a cubic spline. Since 2 2 f"-sigma f is a polygonal line, so is f-f"/sigma . Thus for large tension factors, f itself is nearly a polygonal line. Assymptotically then, f is a cubic spline as sigma tends to 0 and a polygonal line as sigma tends to 1. For intermediate values, the spline displays some of the characteristics of each.

In particular, since a polygonal line of interpolation is able to adopt certain characteristics of the data it interpolates, the tension spline, with sufficiently large tension factor, is able to do likewise. Consider a data set n {(x ,y )} in which all values of y are positive. This positivity may be i i i=1 i an important property and should be maintained by the function of interpolation. It is easy to see that a polygonal line interpolant does maintain the positivity. It is also true that the cubic spline interpolant may not be everywhere positive. However, with sufficient tension, the tension spline will be everywhere positive.

The above discussion is concerned with positivity but much more general properties are attainable with tension splines. Roughly stated, if the data being interpolated remains within certain bounds, then so can the tension spline of interpolation. A similar remark holds for the slopes in the original data and the slopes of the tension spline interpolation. Finally, properties of convexity and concavity can be preserved.

Formally, the capabilities could be stated as this: n Given {(x ,y )} with x < x < ... < x i i i=1 1 2 n 1. If alpha < min(y ,y ), then f(x) > alpha for x ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download