42 DOC. NO.AFCRL-TR-73-400 OC 2673 NGR. & PHYS. SCI. LIB.-U.W.--MADISON AFCRL-TR-73-0400 AIR FORCE SURVEYS IN GEOPHYSICS, NO. 272 PN3 TIT 7 Q 272 Hermite Interpolation Algorithm for Constructing Reasonable Analytic Curves Through Discrete Data Points PAUL TSIPOURAS RENÉ V. CORMIER RECEIVED OCT 2 4 1973 UNIV. WISLY 6 July 1973 UNIVERSITY OF WISCONSIN Approved for public release; di stribution unlimited. COMPUTATION CENTER AERONOMY LABORATORY PROJECT 8624 AIR FORCE CAMBRIDGE RESEARCH LABORATORIES L. G. HANSCOM FIELD, BEDFORD, MASSACHUSETTS 01730 AIR FORCE SYSTEMS COMMAND, USAF AIR FORCE SIMS COMMAND UNIVERSITY OF MICHIGAN 3 9015 09512 6192 Qualified requestors may obtain additional copies from the Defense Documentation Center. All others should apply to the National Technical Information Service. Unclassified Security Classification DOCUMENT CONTROL DATA - R&D (Security classification of title, body of abstract and indexing annotaion must be entered when the overall report is classified) 1. ORIGINATING ACTIVITY (Corporale author) 20. REPORT SECURITY CLASSIFICATION Air Force Cambridge Research Laboratories (LKI) Unclassified L. G. Hans com Field 26 GROUP Bedford, Massachusetts 01730 3. REPORT TITLE HERMITE INTERPOLATION ALGORITHM FOR CONSTRUCTING REASONABLE ANALYTIC CURVES THROUGH DISCRETE DATA POINTS 4. DESCRIPTIVE NOTES (Type of report and inclusive dates) S. AUTHOR(S) (First name, middle initial, last name) Paul Tsipouras René v. Cormier 6. REPORT DATE 6 July 1973 84. CONTRACT OR GRANT NO. 70 TOTAL NO. OF PAGES 76 NO. OF REFS 32 1 90. ORIGINATOR'S REPORT NUMBERS) AFCRL-TR-73-0400 b. PROJECT, TASK, WORK UNIT NOS. 86 240201 62101F C. DOD ELEMENT 9b. OTHER REPORT NOIS) (Any other numbers that may be assigned this report) AFSG No, 272 d. DOD SUB ELEMENT 681000 10. DISTRIBUTION STATEMENT Approved for public release; distribution unlimited. 11. SUPPLEMENTARY NOTES 12 SPONSO RING MILITARY ACTIVITY Air Force Cambridge Research Laboratories (LKI) TECH, OTHER L, G. Hanscom Field Bedford, Massachusetts 01730 13. ABSTRACT Research was conducted using winds and temperatures measured on a 1500-ft tower at a few irregularly spaced levels. The research methodology required the construction of "reasonable" analytic curves of wind and temper- ature vs height. The curves were to be capable of integration and differentia- tion and were to be generated and plotted by computer without human interven- tion. "Reasonable" was subjectively defined as the curve that an individual would most probably draw by hand through the same data points. Of the sev- eral techniques tried, only an algorithm consisting of Hermite interpolation between every two successive points with artificial construction of required derivatives generated "reasonable" curves. Derivatives are artificially con- structed by a subroutine which duplicates the constraints that an individual subconsciously employs when drawing a curve through discrete data points. This report discusses the techniques investigated, graphically demon- strates the advantages and reasonableness of this algorithm, and describes it in detail. This algorithm should be applicable for fitting a continuous curve to discrete data of any sort. DD FORM 1 NOV 65 1.473 Unclassified Security Classification Unclassified Security Classification 14. LINK A LINK B LINK C KEY WORDS ROLE WT ROLE WT ROLE WT Curve fitting Lagrange interpolation Algorithm Hermite interpolation Least squares Unclassified Security Classification Preface The authors wish to thank Mr. T. Persakis for programming and documenting the algorithm and Mrs. F. Fernandes and Mrs. M. Borghetti for typing the manu- script. 3 | 1 Contents 1. INTRODUCTION 7 8 2. TECHNIQUES 2.1 Lagrange Interpolation 2.2 Least Squares 2.3 Hermite Interpolation Algorithm OO OO OO OO 8 8 8 3. CONCLUSIONS 9 APPENDIX A - A Detailed Description of the Hermite Interpolation Algorithm 23 Illustrations 10 1 11 1. Example 1, Curve Fitting Through 7 Discrete Data Points by: (a) straight line segments; (b) Lagrange interpolating polynomials; (c) Hermite interpolation algorithm 2. Example 2, Curve Fitting Through 7 Discrete Data Points by: (a) straight line segments; (b) Lagrange interpolating polynomials; (c) Hermite interpolation algorithm 3. Example 3, Curve Fitting Through 7 Discrete Data Points by: (a) straight line segments; (b) Lagrange interpolating polynomials; (c) Hermite interpolation algorithm 4. Example 4, Curve Fitting Through 7 Discrete Data Points by: (a) straight line segments; (b) Lagrange interpolating polynomials; (c) Hermite interpolation algorithm; (d) the Hermite interpolation algorithm modified to correct negative values 13 14 5 illustrations 16 5. Example 5, Curve Fitting Through 12 Discrete Data Points by: (a) straight line segments; (b) Lagrange interpolating polynomials; (c) Hermite interpolation algorithm 6. Example 6, Curve Fitting Through 12 Discrete Data Points by: (a) straight line segments; (b) Lagrange interpolating polynomials; (c) Hermite interpolation algorithm 7. Examples of Curve Fitting Data Given in Figure 1 (Example 1) by Least Squares with Different Degree Polynomials: (a) 2-degree; (b) 3-degree; (c) 4-degree; (d) 5-degree; (e) 6-degree 18 19 25 26 A1. Determing the Derivative of the Point A; A2. Determining the x-axis Tangent Point in Restricting the Polynomial to be > 0 A3. Example 4 Rotated 90°, Customary Dependent/Independent Variable Portrayal: (a) straight line segments; (b) the unmodified Hermite interpolation algorithm; (c) partial correction; (d) the modified Hermite interpolation algorithm 30 Tables 29 A1. Example n Data Points (A;) and Data Point Derivatives as a Function of Height A2. Example n + 1 Data Points (Aſ) and Data Point Derivatives as a Function of Height 32 6 Hermite Interpolation Algorithm for Constructing Reasonable Analytic Curves Through Discrete Data Points 1. INTRODUCTION Research* was conducted to investigate the characteristics of vertically inte- grated, boundary-layer winds. The methodology required construction of "reason- able" analytic curves of wind and temperature vs height from discrete data. These data were obtained at nonregularly spaced levels ranging in height from the surface to 1500 ft and in number from 7 to 12, depending on the tower. The curves had to be capable of integration and differentiation, and because of the num- ber involved (over 60, 000), had to be generated by computer without human inter- vention. "Reasonable", as used above, is subjectively defined as a curve that an individual knowledgeable of the physics involved, could draw by hand through the same data points. Connecting the data points with straight line segments creates physically un- natural derivative discontinuities and this method is therefore not acceptable. Figures la through 6a show examples of curves constructed by this procedure. (Received for publication 6 July 1973) *Conducted by R. V. Cormier in absentia and towards fulfilling the requirements for the degree of Doctor of Philosophy in Meteorology from St. Louis University, St. Louis, Mo. 7 2. TECHNIQUES 2.1 Lagrange Interpolation The first technique employed used a Lagrange interpolating polynomial of degree n-1 through the n data points. The details of this technique are available 1 in the most elementary textbooks on numerical analysis?. Figures 1b through 6b show sample curves plotted through 7 data points using the Lagrange technique. Inspection of these figures indicates that Lagrange interpolation can yield curves having unreasonable excursions and/or turns between data points. This is some- what evident between the top two data points in Figure 1b, and grossly evident in Figures 3b and 4b. In addition, Figure 4b shows that these excursions can lead to physically unreal negative wind speeds. For relatively simpler data distribu- tions, as shown in Figure 2b, the technique yields more reasonable curves. Figures 5b and 6b are examples of curves plotted through 12 discrete data points. 2.2 Least Squares In the search for a technique which would more consistently yield reasonable curves, least squares fitting with polynomials of varying degrees was tried. Again 1 this technique is described in most elementary numerical analysis texts texts?. Figure 7 shows the curves constructed by this technique for the same data points used in Figure 1 (Example 1) for 2- through 6-degree polynomials. Least squares fitting . generally produces curves having fewer and smaller excursions than Lagrange in- terpolation but, with one exception, these curves do not meet the basic criterion of going through the data points. The one exception is the least squares polynomial of degree one less than the number of data points (Figure 7e) which is equivalent to Lagrange interpolation. 2.3 Hermite Interpolation Algorithm 1 = Hermite interpolation was then suggested, but two problems were immediately evident. If Hermite interpolation were used over all n = 7 points, one could have as many as n-2 = 5 turns between points?; this would, as was the case with La- n grangian interpolation, produce unrealistic excursions between points. Further Hermite interpolation requires, in addition to the value of a function at specific points, the derivatives of the function. 1. Singer, J. (1964) Elements of Numerical Analysis, Academic Press, New York, N.Y. 8 The first problem was solved by using Hermite interpolation between every two successive points rather than over all points. The second problem was solved by artificially constructing derivatives at each of the points by a procedure that duplicates the constraints that an individual subconsciously employs when hand- drawing a curve through data points. This algorithm, consisting of two-point Hermite interpolation with derivatives artificially constructed, is described in de- tail in Appendix A. Figures 1c through 6c show the curves generated by the algorithm. These should be compared with curves a and b shown in Figures 1 through 6. With the exception of Figure 4c, notice how exceptionally reasonable the curves are. They are free of excursions and are quite similar to curves one would draw by hand through the same data points. Figure 4c displays an unreal negative wind speed. The algorithm was then further modified so that it would yield only positive values if data were physically limited to being equal to or greater than 0. Figure 4d shows the elimination of negative values as a result of this additional modification. Note that this has been achieved without a sacrifice in reasonableness; the curve is still as if it were drawn by hand. 3. CONCLUSIONS Research using data measured at a few points on a 1500-ft tower required the construction of "reasonable" analytic curves of the data as a function of height by electronic computer. Of the several techniques tried, only an algorithm consist- ing of Hermite interpolation between every two successive data points with artifi- cial construction of the required derivatives, generated "reasonable" curves. This algorithm should be applicable to discrete data of any sort. It is avail- able from AFCRL (SUYA) by referring to Problem Number 4026/6. 9 0.091 0001 120.0 HEIGHT (FT) IX101) 00.0 60.0 (a) 0:00 20.0 ... 00 1.00 2.00 300 7,00 8.00 9.00 10.00 4.00 5.00 6.00 WINO SPEEO (M/S) 160.0 140.0 120.0 100.0 HEIGHT (FT) (X101) 80.0 60.0 (b) 0:01 20.0 0.00 1.00 2.00 3.00 7.00 8.00 9.00 4.00 5.00 6.00 WINO SPEED (M/S) 10.00 Figure 1. Example 1, Curve Fitting Through 7 Discrete Data Points by: (a) straight line segments; (b) Lagrange interpolating polynomials 10 0.091 0.001 120.0 100.0 HEIGHT (FT) (X10') 80.0 80.0 (c) 0:00 20.0 0 °0.00 1.00 2.00 3.00 7.00 8.00 9.00 10.00 4.00 5.00 6.00 WIND SPEED (M/S) Figure 1. (cont) Example 1, Curve Fitting Through 7 Discrete Data Points by: (c) Hermite interpolation algorithm 160.0 0:01 120.0 (a) 100.0 HEIGHT IFT IIX101) 0.08 0:09 40.0 0.02 9.00 1.00 2.00 3.00 7.00 8.00 9.00 4.00 5.00 6.00 WIND SPEED (M/S) 10.00 Figure 2. Example 2, Curve Fitting Through 7 Discrete Data Points by: (a) straight line segments 11 0.091 140.0 120.0 0.001 HEIGHT (FT) IX101) 60.0 0:08 (b) 0.01 20.0 90.00 1.00 2.00 3.00 4.00 5.00 6.00 7.00 8.00 9.00 10.00 WIND SPEED (M/S) 0.097 0.011 120.0 100.0 HEIGHT FIX101) 80.0 (c) 0:09 1 001 20.0 0,00 1.00 2.00 3.00 7.00 8.00 9.00 10.00 4.00 5.00 6.00 WIND SPEED (M/S) Figure 2. (cont) Example 2, Curve Fitting Through 7 Discrete Data Points by: (b) Lagrange interpolating polynomials; (c) Hermite inter- polation algorithm 12 160.0 0.011 120.0 0.001 HEIGHT (FT MIX101 00.0 60.0 (a) 40.0 20.0 00.00 1.00 2.00 3.00 4.00 5.00 6.00 7.00 6.00 9.00 10.00 WIND SPEED (M/S) 160.0 140.0 120.0 0.001 (b) HEIGHT (FTITX10') 0.08 0.09 0001 20.0 0.00 1.00 2.00 3.00 7.00 8.00 9.00 4.00 5.00 6.00 WIND SPEED (M/S) 10.00 Figure 3. Example 3, Curve Fitting Through 7 Discrete Data Points by: (a) straight line segments; (b) Lagrange interpolating polynomials 13 0.091 0.001 120.0 100.0 HEIGHT (FTDIX10') 80.0 60.0 (c (c) 001 20.0 0 0.00 1.00 2.00 3.00 7.00 8.00 9.00 10.00 4.00 5.00 6.00 WIND SPEED (M/S) Figure 3. (cont) Example 3, Curve Fitting Through 7 Discrete Data Points by: (c) Hermite interpolation algorithm 160.0 139.9 119.8 99.8 HEIGHT (FT) TX101) 79.7 59.6 (a) 39.5 19.4 09.7 '0.00 1.00 2.00 3.00 7.00 0.00 9.00 10.00 4.00 5.00 6.00 WINO SPEED (M/S) Figure 4. Example 4, Curve Fitting Through 7 Discrete Data Points by: (a) straight line segments 14 1 160.0 8166T 6h 1 99.8 HEIGHT (FT)IX101) 797 99.6 (b) (b) 39.5 161 요 ​0 0.7 '0.00 1.00 2.00 3.00 7.00 0.00 9.00 10.00 4.00 5.00 6.00 WIND SPEED (M/S) 160.0 140.0 120.0 100.0 HELOHT (FT(X101) 80.0 (c) (c) 0.09 0001 20.0 +1.00 9.00 1.00 2.00 6.00 7.00 8.00 9.00 10.00 3.00 4.00 5.00 WIND SPEED (M/S) Figure 4. (cont) Example 4, Curve Fitting Through 7 Discrete Data Points by: (b) Lagrange interpolating polynomials; (c) Hermite Inter- polation algorithm 15 0.091 0.011 120.0 100.0 HEIGHT (FT) (X10') 8010 60.0 (d) Out 20.0 90.00 1.00 2.00 3.00 7.00 $.00 9.00 10.00 4.00 5.00 6.00 WIND SPEED (M/S) Figure 4. (cont) Example 4, Curve Fitting Through 7 Discrete Data Points by: (d) the Hermite interpolation algorithm modified to correct negative values 160.0 0.001 120.0 100.0 HEIGHT (FTI(X101) 80.0 (a) 60.0 40.0 20.0 * 9.00 1.00 2.00 + 3.00 7.00 8.00 9.00 10.00 11.00 4.00 5.00 6.00 WIND SPEED (M/H) Figure 5. Example 5, Curve Fitting Through 12 Discrete Data Points by: (a) straight line segments 16 160.0 140.0 120.0 100.0 HEIGHT (FD (X101) 80.0 (b) 0.09 0.01 20.0 9.00 1.00 2.00 3.00 7.00 8.00 9.00 7.00 5.00 6.00 WIND SPEED (M/H) 10.00 11.00 160.0 140.0 120.0 100.0 HEIGHT (FT) (X101) 80.0 (c) 009 40.0 20.0 9.00 1.00 2.00 3.00 7.00 8.00 9.00 4.00 5.00 6.00 WIND SPEED (M/H) 10.00 11.00 Figure 5. (cont) Example 5, Curve Fitting Through 12 Discrete Data Points by: (b) Lagrange interpolating polynomials; (c) Hermite inter- polation algorithm 17 160.0 0.001 120.0 100.0 HEIGHT (FD (X101) 80.0 60.0 (a) 40.0 20.0 * 00.00 1.00 2.00 3.00 7.00 8.00 9.00 10.00 11.00 4.00 5.00 6.00 WIND SPEED (M/H) 160.0 140.0 120.0 100.0 HEIGHT (FT) (X101) 80.0 60.0 (b) 40.0 20.0 9.00 1.00 2.00 3.00 7.00 8.00 9.00 + 10.00 11.00 4.00 5.00 6.00 WIND SPEED (M/H) Figure 6. Example 6, Curve Fitting Through 12 Discrete Data Points by: (a) straight line segments; (b) Lagrange interpolating polynomials 18 160.0 140.0 120.0 100.0 HEIGHT (FT (X101) 80.0 60.0 c) (c) 00 20.0 90.00 1.00 2.00 3.00 7.00 8.00 9.00 10.00 11.00 4.00 5.00 6.00 WIND SPEED (M/H) Figure 6. (cont) Example 6, Curve Fitting Through 12 Discrete Data Points by: (c) Hermite interpolation algorithm 160.0 0.011 POLYNOMIAL FIT DEGREE 2 120.0 100.0 HEIGHT (FT) (X101) 80.0 60.0 (a) X 0:01 20.0 00.00 1.00 2.00 3.00 7.00 8.00 9.00 10.00 4.00 5.00 6.00 WIND SPEED (M/S) Figure 7. Examples of Curve Fitting Data Given in Figure 1 (Example 1) by Least Squares with Different Degree Polynomials: (a) 2-degree 19 160.0 0.011 POLYNOMIAL FIT DEGREE 3 120.0 X 100.0 HEIGHT (FT)IX10') 80.0 60.0 (b) 0.01 20.0 90.00 1.00 2.00 3.00 1.00 8.00 9.00 10.00 4.00 S.00 6.00 WIND SPEED (M/S) 160.0 0.011 POLYNOMIAL FIT DEGREE 4 120.0 X * 100.0 HEIGHT (FT) IX10') 80.0 60.0 c (c) 0.07 20.0 °0.00 1.00 2.00 3.00 7.00 8.00 9.00 10.00 4.00 5.00 6.00 WIND SPEED (M/S) Figure 7. (cont) Examples of Curve Fitting Data Given in Figure 1 (Example 1) by Least Squares with Different Degree Polynomials: (b) 3-degree; (c) 4-degree 20 160.0 0.071 POLYNOMIAL FIT DEGREE 5 120.0 100.0 HEIGHT FIX10') 80.0 60.0 (d ) * 0:07 * 20.0 00.00 1.00 2.00 3.00 7.00 8.00 9.00 10.00 4.00 5.00 6.00 WIND SPEED (M/S) 160.0 0.001 POLYNOMIAL FIT DEGREE 6 120.0 100.0 HEIGHT (FT) (*10') 80.0 60.0 (e) 0.01 20.0 X 0.00 1.00 2.00 3.00 7.00 8.00 9.00 10.00 4.00 5.00 6.00 WINO SPEED (M/SI Figure 7. (cont) Examples of Curve Fitting Data Given in Figure 1 (Example 1) by Least Squares with Different Degree Polynomials: (d) 5-degree; (e) 6-degree 21 Appendix A A Detailed Description of the Hermite Interpolation Algorithm Al. MATHEMATICAL CONSIDERATIONS This algorithm is based upon Hermite's interpolation formula through n-data points. To briefly describe Hermite's formula, consider the simplest form of the formula using just two data points. Given the values f(x7), f(xz), and the deriva- tives f'(x7), f'(x2) of a function f(x) at two points xq and x2 of the x-axis, find a X1 polynomial P(x) of degree at most three, say ' 2 P(x) = 20 + a7x + ayx? + agx3, ao , (A1) such that f(x) and its derivatives are identical with those of the polynomial at the points x X1 and X2, that is f(x) P(x;) f'(x) = P(x) ; ' i = 1, 2, (A2) 3 20 + ayx1 + a2xiº + azaz a 21 a281 2381 Applying Eq. (A2) to Eq. (A1), the following linear system of equations is obtained: f(x1) a1 + 2a2X1 + 3az x1 f'(x1) (A3) ao f(x2) a1 + 2a2X2 + 3a382 f'(x2) 2 X a 2 3 + a x2 + a2x2 + az82 11 2 а 23 а 9 The solution of the above system determines the coefficients aj, aj, az, az, and so the polynomial is determined. The determinant. D of the matrix of coefficients is (x2 - x2) 114, and therefore, if x2 + xy and at least one of the numbers f(x;), f'(x;), i = 1, 2, is different from zero, a non-zero solution of the above system exists and is unique. Therefore the polynomial is obtained uniquely by solving the above system. Most texts on numerical analysis derive polynomial P(x) using a different, somewhat more sophisticated method than solving the above system. In such texts, the polynomial is given as: 2 ) = ) 1 + + X2 2 ( 2 P(x) = f(xx) (1 - 21", (xz) (x = x;)] 2 (x) f(x) [1 - 2Ľ, (x) (x - x2)) ?(x) ] L, x + f'(xy) (x - xz) L?, (x) + f'(x2) (x - x2) L?(x) (A4) 2 2 ' 2 where X - X2 L (x) X1 - X2 and (A5) x L2(x) - X1 *2 -*1 In the present study there is one constraint which restricts the use of the above method. The derivatives of the function are not known. This handicap is avoided by artificially creating derivatives of the given function at the given points as follows: The derivative of the function f(x) at the point [*;, f(x;)] is taken as the slope of the straight line joining the two points adjacent to this point. For example, the slope M; of the point A; (see Figure A1), is f(x1+ 1) - f(x-1) M. Yi+ 1 - Yi- -1 i i ?. 1 X 24 1 Y Ai A1-1 Aiti 1 1 1 1 1 Х Xi-1 Xi Xiti Figure A1. Determining the Derivative of the Point A; For the two end points of a given number of points, the derivative is taken as the slope of the straight line joining the point considered and the point adjacent to it. For instance, the derivatives of the points Ai-1 and A. Ai+1 are, respectively, the following: Mi-1 f(x) - f(x-1) X; - *-1 X and i M. i+ 1 f(x+1) - f(x) Yi+1- % After creating the derivatives of the function f(x) at the points x; = 1, 2, ..., n, using the above method, the function which represents the physical data is approxi- mated by a set of polynomials each having degree at most three. Every two con- secutive points define one such polynomial, as proven above, and is given by Eq. (A4). In this study, the function cannot be negative. Therefore the polynomial is restricted to P(x) ao + ax + ay x² + az x3 + ? 20, , (A5) where x in this study represents height above the earth and P(x) is the wind speed. To accommodate this restriction, consider a special case of the polynomial (the reason will become apparent below). Pick a point xm lying between xa and Xp (see Figure A2). а 25 Pm,b(x) (x) KA 가 ​fo fo Х Xo Xm хь Figure A2. Determining the x-axis Tangent Point in Restricting the Polynomial to be 20 For this point suppose that f(xm) = f'(xm) = 0, (A6) and also f(a) > 0. (A7) To simplify things denote f fa = f(a) and f' = f'(a). . a = X m ; If a polynomial having properties of Eq.(A6), namely, P(xm) = P'(xm) = 0, is created, then it would have a double root at the point x = this can be seen easily by constructing the polynomial which, for the points (xa, fa) and (xm; fm), becomes ) x 2 (x -x) f : X х m 1 P - (x xa Pa, m(x) - x) [(x - xm q' - 21 ] ) - fa m x а. X x) а х m a а a m + (xa x) f m a a}: а The third (real) root of Pa, m(x) is , IT - X3 (x x) f a m a (x x ) f '- 2f a m a a + X a 26 1 One now determines where this root is located or, to be more specific, what condition or conditions should the derivative fi' satisfy in order that this root be and x of the x-axis. outside of the interval defined by the points xa а. m Case a: If X3 0, (xa - Xm) fa' - 2f <0, а а a or 2f a f a (A8) x - X m a Case b: If xz > xm is desired, then (xa (x а x) f m a - x) ft m a Txa > X + X a *m 2f a 9 а a or а fa - xm) fa' > 1. (x a 2f a The above inequality holds if fa' satisfies the double inequality: а 3fa 2f a а 2 0, the polynomial P (x) is positive for every x in the interval (xa, Xm. xm One can incorporate Eq. (A8) and Eq. (A9) into the following inequality: a a, m ' 3f a 0. Hermite's polynomial passing through these two points is written as 2 X X m * 1 P (x xb - - (x) b - X Xb. - *mfy' - 2fy ] (xy - x m X m b m Pm, bre) - ( {-x} [14 - 21)6*- * ( fo} .{%ܟ݂ܐ ܀ - + (xp - Xm) f x This polynomial has a double root at x = x and its third root is m = хз (Xb - Xm) fo - 2fb + (хъ Xm) fb хь • As before, one concludes that Pm, b(x) is positive in the interval (xmxp), if either of the inequalities below is satisfied: 2fb fb' < (A10) Xb - %m X m 28 or 2fb fo' < 3fb. хъ - X (A11) m X m Incorporating Eq. (A10) and Eq. (A11) into one inequality: 3fb fb' < (b) Xp - *m if (b) holds, the polynomial Pm, b(x) has no root between Xm and xp , b A2. AN EXAMPLE The reasons for the mathematical considerations described in Appendix A are now explained in the following paragraphs. Constructing Hermite's polynomials for every two consecutive points has been mentioned previously, as well as the fact that the polynomials should be positive if the phenomenon is positive. In this case the phenomenon is the relationship be- tween wind speed and height above the ground. The data are given in Table A1, and graphed in Figure A3(a). This graph is composed of straight line segments passing through the given data points. The x-axis represents height above the earth and the y-axis represents wind speed. Table A1. Example n Data Points (Aſ) and Data Point Derivatives as a Function of Height 23 146 296 581 874 1166 1458 Height (x) Wind Speed (y) Derivatives 9.06 8.60 9. 68 0,09 1. 33 2.20 2.51 at A -.004 .002 -.020 -.014 .004 .002 .001 The derivative of each point using the method mentioned in A1. is constructed, and the Hermite cubic polynomial through each consecutive pair of points A;, i = 1, ..., 6 is determined. 6 is determined. The derivatives are also given in Table A1. The polynomials are plotted and can be seen in Figure A3(b). Ai+1' , i 29 10.00 6..67 (a) 3.33 0.00 50 150 100 (X101) 10.00 THE POLYNOMI AL Pao (XDEFINED IN 1XoXo WITH ABSOLUTE MINIMUM AT Xa= 648.62 6.53 ) (b) 3.07 Xm -0.40 хь 0 150 50 X 100 ( X 101 ) Figure A3. Example 4 Rotated 90°, Cus - tomary Dependent/Independent Variable Portrayal: (a) straight line segments; (b) the unmodified Hermite interpolation algorithm As previously mentioned, since the phenomenon is positive, the polynomials corresponding to each pair of points must be positive. The polynomials P ) i, i+ 1 +1(x) 30 = X *4' = a, b passing through the points A; and Ai+1 would be positive if they had no real roots in the interval (x;, Xi+1). Figure A3(b) shows that this occurs in the intervals (x1, x2), (x2, X3), (x3, x4), (X5, X6) and (xo, Xy). Inside the interval (xa *b = xg) the polynomial P (x) however has negative values. This behavior of the polynomial Pa, b(x) can be eliminated in the following way: Find the absolute minimum of P. (x) in the interval defined by xa and Xbº Suppose that this absolute minimum is x = x *m • (In the present example xm = 648. 62). In such a case, one more point is included in the set of the given experimental points; namely the point [xm, f(xm)) such that b a, b а f(x) xml f'(xm) = 0, x = *m i thereby making the assumption that the phenomenon is zero with zero derivative at If initially there were n = 7 points, there are now n + 1 = 8 points. Find the derivatives at the n + 1 = 8 points A; as described in Al. with the + constraint that f(xm) = f'(xm) = 0. Create, for the interval (xa, Xm', one Hermite's polynomial say P (x) a, and for the interval (xm, xy) another Hermite's polynomial say P ; , b(x), see Figure A3(c). = ' m 10.00 THE POLYNOMIAL POM (X1 DEFINED IN (XgXm! THE POL Pab IN (Xo XD! 6.67 c (c) 3.33 00:0 хь 0 + 50 *o *m 100 X 101) 150 Figure A3. (cont) Example 4 Rotated 90°, Customary Dependent/Independent Vari- able Portrayal; (c) partial correction 31 a * (x) and Pm, b(x) a, m In order that these two polynomials do not cross the x-axis, the derivatives fi' and fn' should satisfy the conditions (a) and (b) respectively. If these conditions are not satisifed, the derivatives fa' or ff' are changed in an orderly fashion until fo these conditions are satisfied. By so doing, the polynomials P. do not cross the x-axis and are both positive satisfying the requirement that our phenomenon is positive in the respective interval. Figures A3(b) through A3(d) clarify this discussion. In Figure A3(b) the poly- nomial Pa,b(x) passing 'a, b(x) passing through the points Aa (ta = x а = 581.0, f f 0.09), а a and Aъ - = , 874.0, fb (xop 1.33), 11 becomes negative in the interval (xa, Xy). The absolute minimum in this interval of P 648. 62. a, b(x) is x m The new set of the n + 1 = 8 points with their derivatives is given in Table A2, where there is one more point than in the previous set (Table A1), A 648.62, f 0), with zero derivative, fm' = 0. 0 - (x m m m Table A2. Example n + 1 Data Points (Aj) and Data Point Derivatives as a Function of Height 23 146 296 581 648* 874 1166 1458 Height (x) Wind Speed (y) Derivatives at A. i 9.068 8.60 9. 68 0.09 0.00 1.33 2.20 2.51 -.004 .002 -.020 -.027 0.000 004 .002 .001 * x = x m added data point In Figure A3(c) the polynomials corresponding to the new set of points are plotted. The role of conditions (a) and (b) now becomes apparent. Consider first condition (b). For the given data, 3f хь = 3 x 1.33 874, 0 - 648. 62 0.0177. - - X m 32 it But the new derivative of the point Ay is 0.004, and since 0.004 < 0.0177, follows that condition (b) is satisfied, and therefore the polynomial Pm, b(x) does not cross the x-axis and is positive in the interval (xm; xp). For the polynomial P (x) we check condition (a), a, m 3f a 11 - 0.004. X - X m a a а a, m The new derivative of the point A is fa' = -0.028 and condition (a) is not satis- fied. For this reason the polynomial P. (x) crosses the x-axis and is negative in the interval (x , Xm), see Figure A3(c). Accordingly, the derivative fa' is xm changed by the amount, say, of '= 0.001 and condition (a) is again checked; if it is not satisfied, fa' is again changed by o fa' and so on until a a а fa' > -0.004. The derivative fa' = -0.028 must be changed by 0.025 to satisfy condition (a). The new derivative of the point A. becomes а а f' a -0.028 + 0.025 -0.003. , a, m m, b m With this value of the derivative, the new polynomial Pa, m(x) does not cross the x-axis and is positive in the interval (xa: *m, see Figure A3(d). xm) The two polynomials P, (x) and P (x), which have replaced the polyno- mial P (x), are positive in their respective intervals and have a common double a, b zero for x = x *m • Using the above procedure, the phenomenon has thus been represented by a continuous positive and "reasonable" curve. One consideration should be taken into account. The change of the derivatives fa' and fp' will result in the change of the form of the polynomials being defined in fb the interval adjacent to the left of the point x, and adjacent to the right of the point Xp respectively. These two polynomials should be reconstructed to make certain that they are positive in their respective intervals. a 33 10.00 THE POLYNOMI AL Pagam (X) DEFINED IN 1Xq Xm? THE POLYNOMI AL PMD 1X1 DEFINED IN TXmXo 6.67 (d) 3.33 Xm 1 0.00 1 хь 0 150 50 X 100 ( X 101 ) Figure A3. (cont) Example 4 Rotated 90°, Customary Dependent/Independent Vari- able Portrayal: (d) the modified Hermite interpolation algorithm 34 Printed by United States Air Force L. G. Hanscom Field Bedford, Massachusetts