Thompson - Computing for Scientists and Engineers (523188), страница 33
Текст из файла (страница 33)
The next step is tomake the sums over the whole strips, each of which is of the same stepsize h, It istherefore most efficient (for both programmers and computers) first to combine coefficients of the powers of h, then to use the Homer polynomial algorithm to computethe integral contribution, called splint in SplineInt. Then the function addsthe contribution above j U (which is of length eU) and subtracts the contribution fromthe lower segment of length eL to obtain the complete integral.The function Horner4Poly is a customized version of the algorithm describedand programmed in Section 4.1.
It is adapted to express the integral of a polynomial in terms of its value at the start of the interval of integration (y) , the first throughthird spline derivatives (sl, s2, s3), and the interval e, according to (5.36). Thelast function needed for tests of integration is ywInt, the comparison analytical formula for the working-function indefinite integral, obtained from (4.4) andTable 4.1.Exercise 5.12Code the integration routines, following Program 5.1.
Then test the routines asfollows. First, use a constant input function of value equal to unity, and asmany knots as you wish. The integral should be equal to the length of the interval (even if this length is not a integer number of steps h) and it should be exactto within roundoff errors. If this test is successful, use any cubic polynomialand give the exact endpoint second derivatives.
Again results should agree withanalytical integrals to within roundoff. nWith coding and testing completed, it is time to use the spline-integration function.5.5INTEGRATION METHODS USING SPLINES177Integrating the working function and cosineWe investigate two examples of integrating by cubic splines, the pathological working function and the well-behaved cosine. Both of these functions are integrated bythe trapezoid and Simpson methods in Section 4.6, where the results are given inTables 4.9 — 4.11. Here we repeat some of these integrals so that we can comparethe accuracy and convenience of the algorithms.
On the basis of our discussion andexperience in Chapter 4 that numerical integration should be more accurate than numerical differentiation, we may expect agreeable results.In Table 5.4 we show the results of integrating the working and cosine functions using the nine-knot cubic-spline fits that are shown in Figures 5.3 and 5.5, respectively.TABLE 5.4 Nine-knot cubic-spline integrals for working function and cosine with indicated ende3point conditions.
The analytical value of the working-function integral is 9.9109 x 10 .Exercise 5.13Run Cubic Splines (Program 5.1) as a nine-point fit from -0.4 to 0.4 tocheck out the numerical results in Table 5.4 for the working function, yw, andfor the cosine function. Use both exact and natural-spline endpoint conditions.Choose the integration ranges as shown to allow comparison with results for thetrapezoidal and Simpson rules in Section 4.6.
nBy comparing the spline-integration errors for the working function in Table 5.4with those in Tables 4.9 and 4.10 for the trapezoid and Simpson methods (errors of0.2989 x 10-3 and 0.1669 x 10-3, respectively, for stepsize h = O.l), we seethat for either endpoint condition the spline method is a factor of 5 more accuratethan Simpson’s rule and a factor of nearly 10 better than the trapezoid rule. Admittedly there is much more arithmetic involved in the spline fitting, but it will also allow interpolating, estimating derivatives, as well as integrating.We have now learned how to fit curves through data using a method that produces fits that are locally very smooth, and that allows interpolation, estimation ofderivatives, and integration to be carried out reliably.
With all this power of splinefits, it is interesting to enquire why such methods have not been emphasized as partof the repertoire of numerical methods.178FITTING CURVES THROUGH DATA5.6 DIVERSION: COMPUTERS, SPLINES, AND GRAPHICSThe practical applications of curve fitting by splines have been closely related to thedevelopment of computers. To understand why, notice that the five steps involvedin spline fitting require a computing device with significant random-access memory,because for an n-point spline about 9n quantities are computed, and more than halfof these must be available after the fourth step, Further, unlike polynomial interpolation formulas, which have coefficients depending only upon the order of the polynomial assumed, in spline fitting the last four steps must be completely recomputedwhenever even a single function value, yj, is changed.
In hand calculations, usingpencil and paper, memory is at a premium and frequent re-recording of intermediatesteps is to be avoided.Before electronic computers, the large number of arithmetic operations requiredin spline fitting was a severe hindrance, since any error propagates through the calculation in a complicated way that is difficult to correct. Spline methods were therefore seldom used for practical work until computers were widely available and convenient to use.Historically, splines were given most attention in pure mathematics, until about1960 when using digital computers became practical and common. Thus, the formalmathematics of splines is very well developed, as exemplified in the monographs bySchultz and by Schumaker. The practical applications of splines are still under intensive development, as described in the influential book by De Boor, which contains extensive Fortran programs.
The near disjointness of the two sets of literatureon splines, in pure mathematics and in computing, makes their juxtaposition on library bookshelves confusing if not amusing. A history of the development of splinemethods is given in Schumaker’s book.Computer graphics and computer-aided design make extensive use of a varietyof splines in one or more variables. Splines for interpolating and smoothing curvesand surfaces are described in Chapter 11 of the treatise on computer graphics byFoley et al., in Farin’s practical guide to curves and surfaces for computer-aided geometric design, and in the extensive treatment by Bartels et al. Fast interpolationformulas for cubic splines with Bézier control points is described in the article byRasala.
A treatment of these topics that is more mathematically oriented is providedin the book by Lancaster and Salkauskas. For representing surfaces in three dimensions one requires so-called bicubic splines with two independent variables, orsplines with other properties than those we have developed. The design and description of type fonts for printing, a specialized application of two-dimensionalgraphics, also makes use of spline curves and their variants, as you can read inChapter 4 of Rubinstein’s book on digital typography.By contrast with splines, Fourier expansion techniques (such as we present inChapters 9 and 10) started in the early 1800s in applied mathematics and were onlylater developed in mathematical rigor and generality. From the two examples ofsplines and Fourier expansions we see that the three disciplines of mathematical analysis, computing, and applications form a research triangle, each contributing to thedevelopment of the others.REFERENCES ON SPLINE FITTING179A lesson to be learned from the history of splines is that, generally speaking, numerical methods developed in the days of laborious hand calculation will often notbe optimal for computer calculation.
Older numerical methods usually emphasizeminimum storage, easy error detection and correction, and minimal logical complexity. On the other hand, digital-computer methods may be relatively profligate ofstorage, they should be numerical robust because the intermediate results are seldominspected, and they may have quite involved logic — provided that it can be rigorously checked to ensure correctness.REFERENCES ON SPLINE FITTINGAbramowitz, M., and I. A. Stegun, Handbook of Mathematical Functions, Dover,New York, 1964.Bartels, R.
H., J. C. Beatty, and B. A. Barsky, An Introduction to Splines for Usein Computer Graphics and Geometric Modeling, Morgan Kaufmann, Los Altos,California, 1987.Davis, P. J., and P. Rabinowitz, Methods of Numerical Integration, AcademicPress, Orlando, Florida, second edition, 1984.De Boor, C., A Practical Guide to Splines, Springer-Verlag, New York, 1978.Farin, G., Curves and Surfaces for Computer Aided Geometric Design, AcademicPress, San Diego, California, 1988.Foley, J.
D., A. van Dam, S. K. Feiner, and J. F. Hughes, Computer Graphics,Addison-Wesley, Reading, Massachusetts, third edition, 1990.Lancaster, P., and K. Salkauskas, Curve and Surface Fitting, Academic Press, NewYork, 1986.Rasala, R., “Explicit Cubic Spline Interpolation Formulas,” in A. S. Glasner, Ed,,Graphics Gems, Academic, Boston, 1990, pp. 579 - 584.Rubinstein, R., Digital Typography, Addison-Wesley, Reading, Massachusetts,1988.Schultz, M. H., Spline Analysis, Prentice Hall, Englewood Cliffs, New Jersey,1973.Schumaker, L.
L., Spline Functions: Basic Theory, Wiley, New York, 1981.180Previous HomeChapter 6LEAST-SQUARES ANALYSIS OF DATAIn Chapters 4 and 5 we considered derivatives, integrals, and curve fitting of functions such that at each x = xj the fitted values are required to agree exactly with thegiven y (xj) = yj. By contrast, in applications the yj are usually data from measurements with associated uncertainties that should influence the fit made to them.Therefore, the most realistic fitted curve to the whole set of data may not necessarilypass through each yj. For example, if we expect that the data would lie on a straightline in the absence of any measurement uncertainty, then a fit that passes near thedata but not through them may be acceptable.The emphasis in this chapter is therefore on analyzing data in which we take intoaccount some sources of data uncertainty, namely random errors in measurement.We therefore discuss criteria for a best fit (Section 6.l), the use of orthogonal functions in least-squares fitting (Section 6.2) and we derive formulas for straight-lineleast squares when both variables have errors (Section 6.3).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
