Heath - Scientific Computing (523150), страница 63
Текст из файла (страница 63)
In addition to these undesirable computational properties, the use of high-degree polynomials for interpolation has some undesirabletheoretical consequences as well. Simply put, a high-degree polynomial necessarily has lotsof “wiggles,” which may bear no relation to the data to be fit. Although the polynomialgoes through the required data points, it may oscillate wildly between data points and thusbe useless for many of the purposes for which interpolation is done in the first place.One manifestation of this difficulty is the potential lack of uniform convergence of theinterpolating polynomial to an underlying continuous function as the number of equallyspaced points (and hence the polynomial degree) increases.
This phenomenon is illustratedby Runge’s function, shown graphically in Fig. 7.5, where we see that the interpolatingpolynomials of increasing degree converge nicely to the function in the middle of the interval,but diverge near the endpoints.2.01.51.00.50.0.............
.... .... ..... ..2........................................ ........ ....... ... ... .... ..... ...... .... .... .... ...... .... ...5... .... .. .... .... .................... .10.. ...... ................................................................................................................................................................................................................... .... .... .... ....
.... ........................................................... . ........ ...................... .... .. ....................................... ...................................... ......................................................... .. ... .... .... ................ ..................................... .......................................................................................................... ...................................................................................................................................... .............. .... .........
......................... .... ....... .... ................... ..... ...... ...............f (t) = 1/(1 + 25t )p (t)p (t)−1.0−0.50.00.51.0Figure 7.5: Interpolation of Runge’s function at equally spaced points.7.2.7Placement of Interpolation PointsAs we have just seen, equally spaced interpolation points may give unsatisfactory results,especially near the ends of the interval. If, instead of being equally spaced, the points arebunched near the ends of the interval, more satisfactory results are likely to be obtainedwith polynomial interpolation. One way to accomplish this is to use the Chebyshev points(2k − 1)π, k = 1, . .
. , n,tk = − cos2non the interval [−1, 1], or a suitable transformation of these points to an arbitrary interval.The Chebyshev points are the abscissas of n points in the plane that are equally spacedaround the unit circle but have abscissas appropriately bunched near the ends of the interval[−1, 1], as illustrated in Fig. 7.6. The name comes from the fact that the points tk are thezeros of the nth Chebyshev polynomial of the first kind.232CHAPTER 7. INTERPOLATION1••................................................................................................................. .................................................................
........ ......... ............ ......................................................... ......... ........ ...... .... .................... .............. ................ ............... .... ........ ..••••••0•• •−1•••0•••• ••1Figure 7.6: Chebyshev points for interpolation.Use of the Chebyshev points for polynomial interpolation distributes the error moreevenly and yields convergence throughout the interval for any sufficiently smooth underlyingfunction, as illustrated for Runge’s function in Fig. 7.7. Of course, one may have no choicein placing the interpolation points, either because of existing measured data or because aparticular distribution (such as equally spaced) is required for other reasons.2.0.........................................
.... .... .... ....1.51.00.50.0...............f (t) = 1/(1 + 25t2 )p5 (t)p10 (t)............................. ........................... ............. .... ..... .... ......... .... ...... ...... ... ......... ............ ............ . .... .... .... .... .... .... .... .... ... ............. .... ............. ................. ............................ .... ........
... ............ . ........ ............................ .......... .... ............... ................. ..... .......... ..................... .................... ..................................................... ........ .............................................................................................................................................................................................................................−1.0−0.50.00.51.0Figure 7.7: Interpolation of Runge’s function at the Chebyshev points.7.3Piecewise Polynomial InterpolationAn appropriate choice of basis functions and interpolation points can mitigate some ofthe difficulties associated with interpolation by a polynomial of high degree.
Nevertheless,fitting a single polynomial to a large number of data points is still likely to yield unsatisfactory oscillating behavior in the interpolant. Piecewise polynomial interpolation provides analternative to the practical and theoretical difficulties incurred by high-degree polynomialinterpolation. The main advantage of piecewise polynomial interpolation is that a largenumber of data points can be fit with low-degree polynomials.In piecewise polynomial interpolation of a given set of data points (ti , yi ), a differentpolynomial is used in each subinterval [ti , ti+1 ]. For this reason, the abscissas ti at whichthe interpolant changes from one polynomial to another are called knots, breakpoints, orcontrol points.
The simplest example is piecewise linear interpolation, in which successivedata points are connected by straight lines.7.3. PIECEWISE POLYNOMIAL INTERPOLATION233Although piecewise polynomial interpolation eliminates the problems of excessive oscillation and nonconvergence, it appears to sacrifice smoothness of the interpolating function.There are many degrees of freedom in choosing a piecewise polynomial interpolant, however, which can be exploited to obtain a smooth interpolating function despite its piecewisenature.7.3.1Hermite Cubic InterpolationIn Hermite, or osculatory, interpolation, the derivatives as well as the values of the interpolating function are specified at the data points.
Specifying derivative values simplyadds more equations to the linear system that determines the parameters of the interpolating function. To have a well-defined solution, the number of equations and the number ofparameters to be determined must be equal.To provide adequate flexibility while maintaining simplicity and computational efficiency, piecewise cubic polynomials are the most common choice of function for Hermiteinterpolation. A Hermite cubic interpolant is a piecewise cubic polynomial interpolant witha continuous first derivative.
A piecewise cubic polynomial with n knots has 4(n−1) parameters to be determined, since there are n − 1 different cubics and each has four parameters.Interpolating the given data gives 2(n − 1) equations, because each of the n − 1 cubicsmust match the two data points at either end of its subinterval.
Requiring the derivativeto be continuous gives n − 2 additional equations, for at each of the n − 2 interior datapoints the derivatives of the cubics on either side must match. We therefore have a total of3n − 4 equations, which still leaves n free parameters. Thus, a Hermite cubic interpolant isnot unique, and the remaining free parameters can be chosen so that the result is visuallypleasing or satisfies additional constraints, such as monotonicity or convexity.7.3.2Cubic Spline InterpolationIn general, a spline is a piecewise polynomial of degree k that is continuously differentiablek −1 times. For example, a linear spline is a piecewise linear polynomial that has degree oneand is continuous but not differentiable (it could be described as a “broken line”).
A cubicspline is a piecewise cubic polynomial that is twice continuously differentiable. As with aHermite cubic, interpolating the given data and requiring continuity of the first derivativeimposes 3n − 4 constraints on the cubic spline. Requiring a continuous second derivativeimposes n − 2 additional constraints, leaving two remaining free parameters.The final two parameters can be fixed in a number of ways, such as:• Specifying the first derivative at the endpoints t1 and tn , based either on desired boundaryconditions or on estimates of the derivative from the data• Forcing the second derivative to be zero at the endpoints, which gives the so-called naturalspline• Enforcing a “not-a-knot” condition, which effectively forces two consecutive cubic piecesto be the same, at t2 and at tn−1• Forcing the first derivatives as well as the second derivatives to match at the endpointst1 and tn (if the spline is to be periodic)234CHAPTER 7.
INTERPOLATIONExample 7.6 Cubic Spline Interpolation. To illustrate spline interpolation, we willdetermine the natural cubic spline interpolating three data points (ti , yi ), i = 1, 2, 3. Therequired interpolant is a piecewise cubic function defined by separate cubic polynomials ineach of the two intervals [t1 , t2 ] and [t2 , t3 ]. Denote these two polynomials byp1 (t) = α1 + α2 t + α3 t2 + α4 t3 ,p2 (t) = β1 + β2 t + β3 t2 + β4 t3 .Eight parameters are to be determined, and we will therefore need eight equations.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
