Heath - Scientific Computing (523150), страница 64
Текст из файла (страница 64)
Requiring the first cubic to interpolate the data at the endpoints of the first interval gives the twoequationsα1 + α2 t1 + α3 t21 + α4 t31 = y1 , α1 + α2 t2 + α3 t22 + α4 t32 = y2 .Requiring the second cubic to interpolate the data at the endpoints of the second intervalgives the two equationsβ1 + β2 t2 + β3 t22 + β4 t32 = y2 ,β1 + β2 t3 + β3 t23 + β4 t33 = y3 .Requiring the first derivative of the interpolating function to be continuous at t2 gives theequationα2 + 2α3 t2 + 3α4 t22 = β2 + 2β3 t2 + 3β4 t22 .Requiring the second derivative of the interpolating function to be continuous at t2 givesthe equation2α3 + 6α4 t2 = 2β3 + 6β4 t2 .Finally, by definition a natural spline has second derivative equal to zero at the endpoints,which gives the two equations2α3 + 6α4 t1 = 0,2β3 + 6β4 t3 = 0.When particular data values are substituted for the ti and yi , this system of eight linearequations can be solved for the eight unknown parameters αi and βi .7.3.3Hermite Cubic versus Cubic Spline InterpolationThe choice between Hermite cubic and spline interpolation depends on the data to be fitand on the purpose for doing interpolation.
If smoothness is of paramount importance,then spline interpolation may be most appropriate. On the other hand, a Hermite cubicinterpolant may have a more pleasing visual appearance, and it allows the flexibility topreserve monotonicity if the original data are monotonic. These issues are illustrated inFigs.
7.8 and 7.9, where a monotone Hermite cubic and a cubic spline interpolate the samemonotonic data points (indicated by the bullets in the figures). We see that the additionaldegree of smoothness required of the cubic spline causes it to overshoot, and the resultinginterpolant is not monotonic. The cubic Hermite, on the other hand, is clearly less smooth,but visually it seems to reflect the behavior of the data better. In any case, it is advisable toplot the interpolant and the original data to help assess how well the interpolating functioncaptures the behavior of the data.7.3.
PIECEWISE POLYNOMIAL INTERPOLATION2358 •.......................................................................................................................................................................................................................................................................................................................................................................................•64200•2••46••8•10Figure 7.8: Monotone Hermite cubic interpolation of monotonic data.8 •......6420........................................................................................................................................................................................................................................................................................................................................................
............................•0•2••46••8Figure 7.9: Cubic spline interpolation of monotonic data.•10236CHAPTER 7. INTERPOLATION7.3.4B-splinesOne might wonder if an arbitrary spline can be represented as a linear combination of basisfunctions, which we have already seen can be done in various ways for polynomials. Anelegant answer to this question is provided by B-splines, which get their name from the factthat they form a basis for the family of spline functions of a given degree.B-splines can be defined in a number of different ways, including recursion, convolution,and divided differences. Here we will define them recursively. Although in practice we useonly the finite set of knots t1 , .
. . , tn , for notational convenience we will assume an infiniteset of knots· · · < t−2 < t−1 < t0 < t1 < t2 < · · ·The additional knots can be taken as arbitrarily defined points outside the interval [t1 , tn ].Again for notational convenience, we will also make use of the linear functionsvik (t) =t − ti.ti+k − tiTo start the recursion, we define B-splines of degree 0 by1 if ti ≤ t < ti+1Bi0 (t) =,0 otherwiseand then for k > 0 we define B-splines of degree k byk−1kBik (t) = vik (t)Bik−1 (t) + (1 − vi+1(t))Bi+1(t).Since Bi0 is piecewise constant and vik is linear, we see from the definition that Bi1 ispiecewise linear.
Similarly, Bi2 is in turn piecewise quadratic, and in general, Bik is apiecewise polynomial of degree k. The first few B-splines are pictured in Fig. 7.10. Anothermotivation for their name is their bell shape. For k = 1, they are often called “hat”functions.We note the following important properties of the B-spline functions Bik :1.2.3.4.5.•For t < ti or t > ti+k+1 , Bik (t) = 0.For ti < t P< ti+k+1 , Bik (t) > 0.∞kFor all t,i=−∞ Bi (t) = 1.kFor k ≥ 1, Bi is k − 1 times continuously differentiable.k , . . . , B k } is linearly independent on the interval [t , t ].The set of functions {B1−k1 nn−1k , .
. . , B k } spans the set of all splines of degree k havingThe set of functions {B1−kn−1knots ti .Properties 1 and 2 together say that the B-spline functions have local support. Property 3indicates how the functions are normalized, and property 4 says that they are indeed splines.Properties 5 and 6 together say that for a given k, these functions form a basis for the setof all splines of degree k having the same set of knots. Thus, if we use the B-spline basis,the linear system to be solved for the spline coefficients will be nonsingular and banded.The locality of the B-spline representation also means that if the data value at a given knot7.3.
PIECEWISE POLYNOMIAL INTERPOLATION2371.0 .....................................................................................Bi0....0.50.0ti1.00.5................................ti+1ti+2........... ..........................1 .....................i.......................................................................ti+3ti+4ti+3ti+4B0.0titi+1ti+21.00.5.......................................................................2.....................i................................................................................................................................................B0.0titi+1ti+2ti+3ti+41.00.5............................................................3............................................i..............................................................................................................................................................................................................0.0tiBti+1ti+2ti+3Figure 7.10: The first four B-splines.ti+4238CHAPTER 7.
INTERPOLATIONchanges, then the coefficients of only a few basis functions are affected, which is in markedcontrast to the standard polynomial representation, for which changing a single data pointchanges all of the coefficients of the spline interpolant.The use of the B-spline basis yields efficient and stable methods for determining andevaluating spline interpolants, and many library routines for spline interpolation are basedon this approach. B-splines are also useful in many other contexts, such as the numericalsolution of differential equations, as we will see later.7.4Software for InterpolationTable 7.2 is a list of some of the software available for polynomial interpolation and forcubic spline interpolation in one dimension.
Some of the spline packages offer the option ofHermite cubic interpolation as well. A spline toolbox is also available for MATLAB. Tensionsplines—a particularly flexible approach to spline curve fitting that conveniently allowssmoothing and shape preservation, if desired—are implemented in tspack(#716) from TOMS.We note that software is also available from many of these same sources for interpolation intwo or more dimensions, both for regularly placed and for irregularly scattered data.
Forgenerating orthogonal polynomials of various types, the software package orthpol(#726)is available from TOMS.Table 7.2: Software for polynomial and piecewise cubic interpolationPolynomialComputeEvaluateSourceinterpolationsplinesplineFITPACK [60]curfitcurev/splevFMMsplinesevalHSLtb02tb04tg01IMSLcsint/csdec/csher csvalKMNpchezpchevMATLABpolyfitsplineppvalNAGe01aefe01baf/e01befe02bbf/e01bffNRpolintsplinesplintNUMALnewtonPPPACK [53]cubsplppvaluSLATECpolintbint4/bintkbvalu/bspevSpäth [236]newdia/newsol cub1r5/cub2r7cubvalSoftware for interpolation often consists of two routines: one for computing an interpolant and another for evaluating it at any given point or set of points. The input to thefirst routine includes the number of data points and two one-dimensional arrays containingthe values of the independent variable and corresponding function values to be fit, andthe output includes one or more arrays containing the coefficients of the interpolant.
Theinput to the second routine includes one or more values at which the interpolant is to beevaluated, together with the arrays containing the coefficients previously determined, andthe output is the corresponding value(s) of the interpolant (and possibly its derivative) at7.5. HISTORICAL NOTES AND FURTHER READING239the desired point(s).7.4.1Software for Special FunctionsA number of functions that have proved useful in mathematics have become known as special functions.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
