Shampine, Allen, Pruess - Fundamentals of Numerical Computing (523185), страница 21
Текст из файла (страница 21)
The following table of the relative viscosity V of ethanol as functionof the percent of anhydrous solute weight w is taken from [12, p. D-236]:To see how good or bad P(w) is, some data points will be held in reserve. Specifically,we define P6(w) as the polynomial interpolating at {10, 20, 40, 60, 80, 100}. The errorof this interpolant is assessed by evaluating it at the remaining nodes where we know100CHAPTER 3INTERPOLATIONFigure 3.5 P16(v) from Example 3.6.the value of the function:This is probably sufficiently accurate for most purposes. Figure 3.4 shows that P6(x)provides a fit that looks reasonable.
However, if all 12 data points are interpolated, thenresulting P12(x) is not nearly so nice (see Exercise 3.6).Example 3.6. As a second example, we consider some data taken from [19, p. 84].Here v is the reciprocal of the wavelength of light and the function E(v) measuresthe relative extinction of light at this frequency due to observation and scattering byinterstellar materials.3.5 SPLINE INTERPOLATION101Figure 3.6 P16(v) from Example 3.6 over the interval [3.5,6].The data points marked (>) were interpolated by P16(v), which is graphed in Figure 3.5. This is not a good idea! Still, Figure 3.6 shows that the fit is acceptablein the middle of the span of data. As discussed earlier, we might have expected thisfrom the form of the error expression.
Several values of Pl6 at points held in reserveare P 1 6(0.29) = -108.8, Pl6 (1.11) = -28.3, P16 (5) = 5.01, P16 (8.5) = -5035, andP 1 6 (9.5)= 60,749.n3.5 SPLINE INTERPOLATIONThe error expression of Theorem 3.2 suggests that raising the degree of the interpolating polynomial will provide a more accurate approximation.
Unfortunately, otherfactors play a role and this tactic often does not succeed in practice. The expressionsuggests another tactic that will succeed. The error depends strongly on the length ofthe interval containing the nodes. If we can somehow reduce this length, the theoremsays that we will then get a better approximation. The basic idea of this section is toapproximate f(x) by a polynomial only on a piece of the interval. The approximationsover all the pieces form an interpolant called a spline. (In this book the word spline isa synonym for piecewise polynomial function.) More specifically, the function f(x) isto be approximated on [x1, xN].
The interval [x1, xN] is split into subintervals [xn, xn+1 ],where x1 < x2 < ··· < xN. A spline is a polynomial on each interval [xn, xn+l ]. In thiscontext the {xi } are called the breakpoints or knots. In the subsections that follow, aselection of splines that arise from interpolation with constraints are studied. A keyissue is how smoothly the polynomials connect at the knots, and this governs the orderin which they are taken up.102CHAPTER 3INTERPOLATIONDISCONTINUOUS AND CONTINUOUS SPLINESThe simplest splines are those arising from interpolation done independently on eachsubinterval [xn, xn+l ]. The bound (3.7) can be applied to each subinterval. For example, suppose that any four nodes are chosen in each subinterval [xn, xn+1 ]. Let thespline interpolant S(x) consist of the cubic polynomial interpolants on the subintervals.If h = max(xn+l - xn ) andthenAs h0, a good approximation is obtained over the whole interval.
Evidently thetactic of fixing the degree and approximating the function on pieces is more promisingfor practical interpolation than approximating the function over the whole interval bymeans of increasing the degree.Generally the polynomial on [x n ,x n+1 ] does not agree at xn with the polynomialon [x n-1 ,x n ], so this spline is generally discontinuous at the knots. When approximating a continuous function f(x) this may not be acceptable.
It is easy to modify thisconstruction to obtain a continuous spline. All we need do is include the ends of eachsubinterval among the points where f(x) is interpolated. The polynomial on [x n ,x n + 1 ]then has the value f(xn) at xn and so does the polynomial on [x n - 1 ,x n ] .Only data from [x n-1 ,x n ] are used in constructing the spline on this subinterval, sothe error depends only on the behavior of f(x) on this subinterval. This will not be thecase for splines taken up later.
In some contexts the spline is to be constructed beforeall the data are available and this property of the construction is essential.The simplest continuous spline is one that is piecewise linear, that is, S(x) is abroken-line function (see Figure 3.7). If S(x) is required to interpolate f(x) at theknots, then on [x n ,x n+1 ] for 1 < n < N - 1 the Lagrange form iswhich can be rewritten as(3.27)Example 3.7. Given the data (5, 1.226) (30, 2.662) (60, 2.542) (100, 1.201) takenfrom Example 3.5, (3.17) yields3.5 SPLINE INTERPOLATION103Figure 3.7 A typical linear spline function.The linearsubinterval hasfor finding thethe polynomialinterpolating spline (3.27) is very easy to evaluate once the properbeen located. All spline evaluation routines must contain an algorithmright subinterval.
Often this takes longer than the actual evaluation ofthere. For linear interpolation, an error bound is(3.28)whereConvergence is guaranteed asbounded. A similar argument using (3.16) yieldsis(3.29)Thus, S´(x) can be used as an estimate for f’(x) that gets better as h0.Continuous splines are used in the solution by finite elements of boundary valueproblems for second order differential equations. The simple program CODE1 in [l]allows the user to specify the degree of the interpolating polynomial on each elementthe subinterval [x n ,x n+1 ]—in the range 1 to 3.
The higher the degree, the more accuratethe approximation, but the greater the possibility of unwanted oscillations. This maynot matter when using the spline for finite elements, but it is to be avoided whenrepresenting data. For the latter purpose a good compromise seems to be the use ofcubic polynomials, so in the rest of this section we concentrate on them.The error of a continuous cubic spline constructed by interpolation independentlyon each subinterval can be analyzed using the error expressions developed for polynomial interpolation. On each subintervalfor k = 0, l, .
. . , 3 and suitable constants Ck. It is not so easy to prove and the powersof h differ, but similar results can be established for all the cubic splines we take up.104CHAPTER 3 INTERPOLATIONThe point, though, is that on each subintervalThis implies that for sufficiently small h, P´4(x) has the same sign as f´(x) as long as f´(x) 0. Put differently,except near the extrema of f(x), for small h the spline is monotonely increasing (decreasing) wherever f(x) is. The same argument applies to the second derivative andleads to the conclusion that except near inflection points of f(x), for small h the splineis concave (convex) wherever f(x) is.
We conclude that for small h, the spline will reproduce the shape of the function it interpolates. The same will be true of all the cubicsplines we take up. This is one reason why spline interpolation is much more satisfactory than interpolation by high degree polynomials. But what if h is not “small”?When the data are sparse, it is necessary to impose conditions on the spline to preservethe shape of the function, one of the matters we take up in the next subsection.CONTINUOUS FIRST DERIVATIVEIf we have derivative data available, it is easy to extend the approach of the precedingsubsection to obtain an interpolant with a continuous derivative.
For example, wecould interpolate f(xn ), f´(x,), f(xn+1 ), f´(xn+1 ) by the cubic Hermite interpolatingpolynomial on [x n ,x n+1 ]. Doing this on each subinterval produces a spline H(x) witha continuous first derivative. Each interval is treated independently, so the bounds(3.17)-(3.20) hold and show that a good approximation is obtained. In the chapter ondifferential equations, we produce, for successive n, approximations to a function y(x)and its derivative at the points xn, xn + h/2, and xn + h.
By forming the quintic (degree5) Hermite interpolant to these data, a spline with a continuous derivative is formedthat approximates y(x) and y´(x) for all x. It is especially important in this context thatthe interval [xn,xn + h] is handled independently because generally it is only the dataon this interval that are available when interpolation is done.Let us now consider the representation of data when only f(xi ) values are knownand there are not many of them. It has been found that a cubic spline H(x) yields a plotpleasing to the eye if it has a continuous derivative and if it preserves monotonicity. Bythe latter is meant that if fn < fn+1, then H(x) increases on (x n ,x n+1 ) and if fn > fn+1,then H(x) decreases.
The point is to avoid oscillations that do not appear in the data.A moment’s thought shows that linear splines preserve monotonicity. The problemwith them is that their graphs have “corners.” By going to cubits and a continuousfirst derivative, we avoid the corners. Such a “shape-preserving” interpolant can beconstructed along the lines of the cubic Hermite interpolant.
The cubits on [ x n - 1 ,x n]and [x n ,x n+l ] both interpolate to fn at xn. If the first derivative is to be continuous, thefirst derivatives of the two cubits must have the same value at xn, but now the value ofthis derivative is an unknown parameter that we choose to achieve monotonicity.As in (3.11) the cubic is written in the formfor xn < x < xn+1, 1 < n < N - 1. Note that the parameter bn is just the slope ofH(x) at the point xn.
Proceeding as in the derivation of (3.12)–(3.14) with the notationhn = xn+l - xn and= (fn+ 1 - fn ) /hn yieldsan = fn3.5 SPLINE INTERPOLATION105(3.30)These equations result from solving the three interpolation conditions H(xn) = fn,H(xn+l) = fn+1, and H´(xn+l) = bn+l for the three unknowns an, cn, and dn.The quantity A, is the slope of the line through (x n , f n ) and (xn+1, fn+1 ). If= 0,it seems reasonable to force H(x) to be constant on [x n ,x n + 1 ], that is, to make the slopesbn = bn+1 = 0. If0, let us define αn = bn/and β n = bn+1To preservemonotonicity it is necessary that the sign of the slope of H(x) at xn and xn+l be thesame as that ofMathematically this is α n > 0, β n > 0.A sufficient condition on α and β to preserve monotonicity was found by Fergusonand Miller [7].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
