Conte, de Boor - Elementary Numerical Analysis. An Algorithmic Approach (523140), страница 11
Текст из файла (страница 11)
. . , x n to the function f(x) = K(x - x 0 ) · · · (x - x n ), where K is an unknownconstant.] What does this imply about programs like the FUNCTION TABLE in Sec. 2.4 orAlgorithm 2.4?2.5-4 Use (2.18) to give a lower bound on the interpolation errorwhen2.6 INTERPOLATION IN A FUNCTION TABLE BASED ONEQUALLY SPACED POINTSMuch of engineering and scientific calculation uses functions such as sin x,ex, Jn (x), erf(x), etc., which are defined by an infinite series, or as thesolution of a certain differential equation, or by similar processes involvinglimits, and can therefore, in general, not be evaluated in a finite number ofsteps. Computer installations provide subroutines for the evaluation ofsuch functions which use approximations to these functions either bypolynomials or by ratios of polynomials.
But before the advent of highspeed computers, the only tool for the use of such functions in calculationswas the function table. Such a table contains function values f(xi ) forcertain points x0, . . . , xn, and the user has to interpolate (literally, “polishby filling in the cracks,” therefore also “falsify”) the given values wheneverthe value of f(x) at a point not already listed is desired. Polynomialinterpolation was initially developed to facilitate this process. Since in suchtables f(x) is given at a usually increasing sequence of equally spacedpoints, certain simplifications in the calculation of the interpolating polynomial can be made, which we discuss in this section.Throughout this section, we assume that f(x) is tabulated for x =a(h)b; that is, we have the numbers f(xi ), i = 0, .
. . , N, available, where(2.19)It is convenient to introduce a linear change of variables(2.20)and to abbreviate(2.21)This has the effect of standardizing the situation to one where f(x) isknown at the first N + 1 nonnegative integers, thus simplifying notation. It56INTERPOLATION BY POLYNOMIALSshould be noted that the linear change of variables (2.20) carries polynomials of degree n in x into polynomials of degree n in s.To calculate the polynomial of degree < n which interpolates f(x) atxk, . .
. , xk+n we need not calculate in this case a divided-difference table.Rather, it is sufficient to calculate a difference table. To make this precise,we introduce the forward difference(2.22)The forward difference is related to the divided difference in the followingway.Lemma 2.3 For all i > 0(2.23)Since both sides of (2.23) are defined by induction on i, the proof ofLemma 2.3 has to be by induction. For i = 0, (2.23) merely asserts thevalidity of the conventionsand is therefore true.
Assuming (2.23) to hold for i = n > 0, we haveshowing (2.23) to hold, then, for i = n + 1 too.With this, the polynomial of degree < n interpolating f(x) atxk, . . . , xk+n becomes(2.24)In terms of s, we haveHence2.6INTERPOLATION AT EQUALLY SPACED POINTS57A final definition shortens this expression still further. For real y and for ia nonnegative integer, we define the binomial function(2.25)The word “binomial” is justified, since (2.25) is just the binomialcoefficientwhenever y is an integer. With this, (2.24) takes the simpleform(2.26)which goes under the name of Newton forward-difference formula for thepolynomial of degree < n which interpolates f(x) at xk + ih, i = 0, . .
. , n.If in (2.26) we set k = 0, which is customary, the Newton forward-difference formula becomes(2.27)If s is an integer between zero and n, then this formula reads(2.28)The striking similarity with the binomial theoremis not accidental. If we introduce the forward-shift operatorthen we can writeThereforewhich is (2.28).i.e., then9INTERPOLATION BY POLYNOMIALSWe resist the temptation to delve now into the vast operationalcalculus for differences based on formulas likebut do deriveone formula of immediate use. Sincewe get from the binomialtheorem thator(2.29)The coefficientsfor (2.26) are conveniently read off a (forward-)difference table for f(x).
Such a table is shown in Fig. 2.4. According to(2.22), each entry is merely the difference between the entry to the leftbelow and the entry to the left above. The differences which appear in(2.27) lie along the diagonal markedin Fig. 2.4.Difference tables are used to check the smoothness of a tabulatedfunction, to detect isolated errors and to decide on the degree of theFigure 2.4 Forward-difference table.2.6INTERPOLATION AT EQUALLY SPACED POINTS59interpolating polynomial appropriate for the table.
We illustrate thesepoints in the following example.Example 2.8 From a book of interplanetary coordinates, we have copied (incorrectly, tomake a point) the x coordinate of Mars in a heliocentric coordinate system at the datesgiven. These coordinates are given at intervals of 10 days, and have been obtained byastronomers by various means. In Fig.
2.5, we have constructed a (forward-) differencetable for these data.The first three differences are of constant sign; hence, the first two are monotone.Third- and higher-order differences show a pronounced oscillatory behavior. If webelieve the tabulated function to be smooth, i.e., to be slowly varying, then this behaviorof the higher differences must be the effect of error.Suppose the error in the ith function value isall i. Then the table in Fig. 2.5contains the numbersand these differ from the supposedly slowly varyingcorrect numbersby the amountFrom (2.29) we have(2.30)withIf the tabulated values are accurately rounded values, then0.000005 and the errors in the fourth differences should therefore be no bigger than 8units in the last place. Yet the errors are much larger if we ascribe the oscillatorybehavior to error.Figure 2.5 Heliocentric, equatorial x coordinate of Mars (somewhat erroneous).60INTERPOLATION BY POLYNOMIALSA closer inspection of these fourth differences reveals systematic behavior in theoscillations.
If we subtract the average value 10 of the column of fourth differences fromeach entry in that column, then we get the sequence-1384-12182-26-6whose pattern suggests to the experienced that a mistake of about 20 units in the lastplace was committed in the table entry corresponding to the - 121 above, i.e., in theentry 1.24767, for t = 1,290.5. Indeed, a solitary change by - 20 units in the last place ofthat entry would change the column of fourth differences by-2080-12080-200according to (2.30), and thus account for essentially all the oscillations in that column.To summarize: Isolated errors in a function table are signaled bysystematic oscillations in the higher differences.
By comparing these oscillations around the (local) average with those generated by a single erroraccording to (2.30), an estimate of the error can be made and the tablecorrected.Figure 2.6 Heliocentric, equatorial x coordinate of Mars.In our example, correction of f(1,290.5) to 1.24787 produces the difference table inFig. 2.6.
Now even the fourth differences are of one sign. The fifth differences oscillate,but they are smaller in size than the maximum error of 16 = 25/2 units possible becauseof rounding in the function values. We conclude that the fifth differences consistessentially of noise due to the rounding in the function values and that interpolation bya fourth-degree polynomial should give satisfactory (and defensible) results.2.6INTERPOLATION AT EQUALLY SPACED POINTS61Because of the former importance of function tables, a rather largebody of material concerning interpolation in function tables has beendeveloped over the centuries. Difference operators other than the forwarddifference operator(such as the forward shift E) have been introducedto provide a compact notation for various forms for the interpolatingpolynomial, all of which differ only in the order in which interpolationpoints appear.
These forms have been associated with the names ofNewton, Gauss, Bessel, Stirling, Gregory, Everett, etc., often by traditionrather than by historical fact. A complete treatment of these forms can befound in Hildebrand [5].We choose not to discuss these forms. We feel that Algorithm 2.4 andthe FORTRAN subprogram TABLE discussed in Sec. 2.4 are sufficientequipment for the few occasions the student is likely to make use of tables.EXERCISES2.6-1 Prove that a solitary error in a function table leaves the average of the first fewdifference columns unchanged.2.6-2 The values of f(x) given below are those of a certain polynomial of degree 4.
Form adifference table, and from this table find f(5). (See Exercise 2.6-6.)2.6-3 Form a difference table for the following data, and estimate the degree of theinterpolating polynomial needed to produce interpolated values correct to the number ofsignificant figures given.2.6-4 Using the difference table in Fig. 2.6 find(b) f(1332.5)(a) f(1252.5)In each case estimate the error.2.6-5 Prove that if pn(x) is a polynomial of degree n with leading coefficient an, and x0 is anarbitrary point, then62INTERPOLATION BY POLYNOMIALSand[Hint: Use the definition (2.22) of the forward-difference operatorand (2.17).]. Else, use Lemma 2.12.6-6 Let xi = x0 + ih, i = 0, 1, 2, .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
