Art. LIV.—On the Use of the Standard Functions in In-terpolation.
[Read before the Wellington Philosophical Society, 16th December, 1902.]
There is a parallel between the expression of functions by Taylor's Series expansion formulæ, and of tables of numbers by interpolation formulæ, depending on finite differences. In both cases there is usually a “remainder” which is neglected as being immaterial. This parallel is seen to be very close if closely examined; but we need here only remark that, just as we have found it possible to reduce the degree of many Taylor's Series expansions by means of the standard functions,^{*} so also it is possible to reduce the number of differences required to interpolate in a normal table of figures. This, again, is a matter into which we need not go; defining the problem in hand as follows: Given a table of numbers, and having differenced them, what is the best formula—or, in other words, the formula of the least number of terms—that can be found to perform the interpolation by finite differences between two consecutive values of the numbers, the arguments being, of course, at equal intervals?
There are a number of ways of deducing formulæ of interpolation, the chief of which result in what are called^{†} Newton's, Lagrange's, and Bessel's methods, the latter being generally employed when more than two differences are significant. Each of these methods gives rise to a series of functions analogous to the standard functions, and in cases identical with them. Thus, in all cases the first function is the linear (L), and the second the standard parabola, x(1 —x). In Newton's and Lagrange's methods the other formulæ are not the same, but diverge widely from the standard form—less widely in Lagrange's method than in Newton's. Bessel's method, however, brings in the standard cubic and then diverges from the standard form.
[Footnote] * Trans. N.Z. Inst., 1901, p. 519 et seq.
[Footnote] † This nomenclature is drawn from that of F. G. Gauss (5-fig. Log. and Trig. Tables, larger edition, 1900, p. 150), who gives Lagrange's and Newton's methods for unequal increments, and then says, “Bei gleichen Intervallen gehen diese Formeln in die Formeln (1) und (2) uber,” i.e., into the methods referred to (Bessel's being, of course, a modification of Lagrange's method).
There is no doubt that Newton's method is in general inferior to either of the others. This arises from two facts: (1) the differences are so chosen as to depend on the values following the interval, instead of on those of both sides of it, and (2) the terms do not converge so rapidly as in the other forms. We shall therefore not develope Newton's method here, since in practical problems it is generally possible to give the values on each side of the interval.
Lagrange's and Bessel's methods employ the same differences— those indicated by the dotted line in the following table:—
In Newton's method the top row of Δ is used, and for the top interval. Bessel, however, instead of the even differences takes the mean of the difference indicated and the one below it—that is to say, he adds in half of the next following value of odd differences. What this comes to we shall presently see; but, meanwhile, it is evident that the two methods are identical in result, so we need only take Lagrange's method. Lagrange deduced the following functions as expressing a result of finite differences (to the first difference add):—
− x (1 − x) Δ _{2}/1·2
− x (1 − x) (1 + x) Δ _{3}/1·2·3
− x (1 − x) (1 + x) (2 − x) Δ _{4}/4!
− x (1 − x) (1 + x) (2 − x) (2 + x) Δ _{5}/5!
− x (1 − x) (1 + x) (2 − x) (2 + x) (3 + x)Δ _{6}/6!
and so on.
Converting these functions into standard form, we get the result given in the following table (to the first difference add):—
(The fractions are given as products to facilitate computation.) Thus a value of the Lagrange Δ^{4}_{0}, for instance, equal to n, gives rise in the interpolation formula to the terms—
[The section below cannot be correctly rendered as it contains complex formatting. See the image of the page for a more accurate rendering.]
n(3/52(P)−1/96(IV.)).
From this we see that, although it may be necessary to take the differences out to a high order, it does not follow that the formula necessary will be of high degree.
From this table we can at once see the improvement that Bessel made in Lagrange's formula, for it is evident that, taking half of the odd differences out in the term depending on the preceding even difference results in the elimination of the fractions which occupy the spaces in lines Δ^{3}, Δ^{5}, &c., column P, lines Δ^{5}, Δ^{7}, &c., in column IV., and so on. Thus Bessel's third difference function is the standard cubic, and the fifth a sum of cubic and quintic, which is an obvious improvement upon Lagrange's method.
It is not a complete improvement, for it does not alter to any appreciable extent Lagrange's even difference terms; and even with respect to the odd differences it includes a cubic term in the fifth difference function, instead of making it a pure standard quintic.^{*}
If we compute by means of the table given above, it is clear that we are able to effect completely what the Bessel method effected partially, in giving the terms of the formula nearly the best possible form—that of the standard functions.
A concrete example of a problem treated by Lagrange's and Bessel's methods and by that of the standard functions will serve to show the advantages of the latter method.
Loomis's “Practical Astronomy,” 1894, p. 207, gives a convenient example, that of getting the moon's R.A. from a twelve-hour table, for eight hours (i.e., x = ⅔). Two places of decimals are obviously enough, but we use three for the purposes of illustration.
[Footnote] * We here assume that the standard functions are the best practicable formulæ for convergence, concerning which vide the paper quoted.
Omitting the constant and the first-difference terms, which are the same in all methods, the data are:—
[The section below cannot be correctly rendered as it contains complex formatting. See the image of the page for a more accurate rendering.]
Δ^{2} | Δ^{3} | Δ^{4} | Δ^{5} | |
+ 25.68 s. | − 2.19 s. | |||
− 4.08 s. | − 0.06 s. | |||
+ 21.60 s. | − 2.25 s. | |||
Mean | + 23.64 | −2.22 |
Lagrange's method gives:—
Δ^{2} | − 2.853,3 s. |
Δ^{3} | + 0.251,8 |
Δ^{4} | − 0.045,7 |
Δ^{5} | − 0.000,7 |
− 2.647,2 s. |
The computation by Bessel's method gives:—
[The section below cannot be correctly rendered as it contains complex formatting. See the image of the page for a more accurate rendering.]
Δ^{2} | − 1/9 (23.64) | = − 2.626,7 s. |
Δ^{3} | (− 0.00617) (− 4.08) | = + 0.025,2 |
Δ^{4} | (+ 0.02057) (− 2.22) | = − 0.045,7 |
Δ^{5} | (+ 0.00069) (− 0.06) | = 0.000,0 |
Sum | − 2.647,2 s. |
The values of Bessel's coefficients can be got from tables.
Now, for the standard method, filling in the tables, we get:—
[The section below cannot be correctly rendered as it contains complex formatting. See the image of the page for a more accurate rendering.]
P. | C. | IV. | V. |
(+ 25.68)Δ^{2} gives − 12.84 | |||
(− 47.08)Δ^{3} " + 1.02 | − 0.34 | ||
(− 2.19)Δ^{4} " − 0.20,5 | 0.0 | + 0.02 | |
(− 0.06)Δ^{5} " − 0.00,3 | + 0.00 | + 0.00 | − 0.00 |
Sum − 12.028 (P) | − 0.34 (C) | + 0.02 (IV.) |
Taking the values of P, C, and IV. from tables, as in the case of Bessel coefficients, or computing thus—
[The section below cannot be correctly rendered as it contains complex formatting. See the image of the page for a more accurate rendering.]
for x = ⅔; P = ⅔ − (⅔)^{2} = + 2/9; C = + 2/9 (1 − 4/3) = 2/27; (IV.) = − 2/27 (1 − 4/3) = + 2/8
we compute the terms:—
[The section below cannot be correctly rendered as it contains complex formatting. See the image of the page for a more accurate rendering.]
(+ 2/9) (− 12.028) = − 2.672,9 s. |
(− 2/27) (− 0.34) = + 0.025,2 |
(+ 2/81) (+ 0.02) = + 0.000,5 |
Sum − 2.647,2 s. |
It is to be noticed that all the terms except the parabola have maximum ordinates of about 0.1, so that two places of decimals in their factors is ample. The quartic function, the term of which has here practically disappeared, has a maximum of 0.0625, so that the quantities it represents are never larger than 0·0013 in this interpolation, a quantity which is negligible with respect to the second place of decimals. This is against 0 052,0 in Bessel's method.
Comparing this with the Bessel's computation, we see that the fifth-degree term vanished in our table, while in the Bessel's its value was estimated, when it vanished; the fourth-degree term becomes negligible in our computation, while in Bessel's it is conspicuously large. The third-degree numbers are the same, 0·025,2. The Bessel's computation illustrates very clearly what was said about Bessel's method effecting an improvement only in the odd power terms.
It is hardly necessary to remark to those who may examine this method of using differences that there is no improvement on Newton's or Lagrange's methods for second differences, nor on Bessel's for third; but for fourth, and especially for higher differences still, the extra trouble of forming the table seems worth while, and certainly is worth while if a number of values have to be interpolated. The method of standard terms also possesses an obvious advantage where the problem is to find at what value of x, Y has a given value, since when fourth differences have to be used the approximation in three terms [Y = A + B^{x} + C(x — x^{2})] is more nearly accurate than the corresponding approximation of any of the other methods.
Note.
The standard functions referred to in this paper are:—
Parabola | (P) | = x (1-x) |
Cubic | (C) | = P (1-2x) |
Quartic | (IV.) | = C (1-2x) |
Quintic | (V.) | = C (1-4x)(3-4x) |
Hexic | (VI.) | = V. (1-2x) |
Heptic | (VII.) | = P (V.) |
Octic | (VIII.) | = P (VI.) |
and the list may be provisionally extended by P-multiplication. This list shows how the values of the functions for any value of x can be easily computed, or they may be taken from a table of values similar to those of the binomial coefficients (Newton's method) or of Bessel's coefficients. Such tables, it is confidently believed, will soon be included in many mathematical tables.
Postscript.
A more extended table of the standard terms, which are equivalent to the Lagrange interpolation, has now been computed, and is given herewith. The form differs slightly from that of the shorter table in the paper, the common factors in each line being separated. These common factors are connected by the ratio n−½n when n, the order of the factor sought, is even, n/2n or ½ when n is odd. Thus the table can be extended. Hence the common ratio is about ½. The coefficients of the standard functions are also best extended by a similar process, but it is too complicated, and, moreover, obvious, to be here given. It will be necessary to construct a similar table for the Newton differences if it is required to treat functions of which the values cannot be given on each side of any interval.
It is to be noticed that the results of these operations are simply identical with the results of the orthodox methods, and where the latter fail for want of convergence these operations fail also. The advantage which the reductions possess is merely the shortening of the formulæ.
The practical use of this reduction lies, I think, in the power it gives in stating the values of functions in tabular form, where space forbids the use of more than a 2- or 3-figure argument. An example will now be given of the power of the standard method in this respect. First, we may notice the fact, which is evident from the table, that the Lagrange terms are, all of them, nearly pure standard parabolæ. That is to say, their maxima are nearly the same as the value when x = ½. Consequently, the value or number represented by any of the Lagrange differences may amount to ½ times the common factor for that difference.
The example taken is that of the log. gamma function, which was tabulated by Legendre for the unit interval 1. 2 in a 3-figure argument, 12-figure table, the interpolation being indicated by third differences, which were tabulated thus (twelve decimals understood):—
x | Log. Gamma. | Δ^{1} | Δ^{2} | Δ^{3} | Δ^{4} |
(−) | (+) | (−) | (+) |
(1)·119
· 120 974 783 415 092 171 440 853 605 919 768 2M
· 121
[The section below cannot be correctly rendered as it contains complex formatting. See the image of the page for a more accurate rendering.]
The last difference does not seem to have been given, and it is not necessary for Lagrange's method, and twelve places, but would have been needed for thirteen places, since it reaches the value 6 or 3/32·6/4 = 0·14 units in the twelfth place.
De Morgan (Diff. Calc., p. 587) gives an abridgment of this table in a 2-figure argument, to use which it is necessary to reconstruct one decad of the original table before an interpolation can be made, which obviously is a tedious process.
On differencing out the first portion of the 2-figure table, which appears to be the least convergent portion, I find that Δ^{5} has a maximum of 1050 units, and Δ^{6} of 50 units.
[The section below cannot be correctly rendered as it contains complex formatting. See the image of the page for a more accurate rendering.]
Hence, on the Lagrange system, Δ^{5} represents 3/64 × 1050/4, or 12 units, and Δ^{6} 5/256 × 50/4, or 0·24 units.
[The section below cannot be correctly rendered as it contains complex formatting. See the image of the page for a more accurate rendering.]
Now, reducing to the standard system, Δ^{6} will be represented by 2/256 × 50/900 or 0·001 (VI.), with a maximum value of about 0·000,1 units, and Δ^{5} by 3/64·1050/80, or 0·3 (V.), with a maximum of 0·03 units, or 0·3 units in the thirteenth place.
Summing up, we need for a 12-figure table—3-figure argument, three differences; 2-figure argument, five differences, or four standard terms: and for a 13-figure table—3-figure argument, four differences; 2-figure argument, six differences, or four standard terms.
The following is a specimen line of a 2-figure table in terms of Lagrange differences and in standard terms:—
[The section below cannot be correctly rendered as it contains complex formatting. See the image of the page for a more accurate rendering.]
x Log. Gamma. | Δ^{1} | Δ^{2} | Δ^{3} | Δ^{4} | Δ^{5} | Δ^{6} |
(−) | (+) | (−) | (+) | (−) | (+) | |
(1) · 11 | ||||||
· 12 974783415092 | 1687233927 | 60670390 | 761542 | 18304 | 605 | 34 |
· 13 |
[The section below cannot be correctly rendered as it contains complex formatting. See the image of the page for a more accurate rendering.]
x Log. Gamma. | Δ^{1} | P | C | IV. |
(−) | (−) | (−) | (−) | |
(1) · 11 | ||||
· 12 974783415092 | 1687233927 | 30143123 | 63456 | 190 |
· 13 |
These are the actual numbers. If any one wishes to check them it should be noticed that the differences in the original table are Newton's or leading differences, so that the interpolation must be made with the binomial coefficients, and not with Lagrange's or Bessel's functions.
Finally, it may be noticed that if it is preferred not to use the standard functions their terms might be translated back into Lagrange or Bessel differences, so that existing tables may be used for interpolating without losing the advantage of the reduction.
[The section below cannot be correctly rendered as it contains complex formatting. See the image of the page for a more accurate rendering.]
Order of Différences. | Common Factor. | P | C | IV. | V. | VI. | VII. | VIII. | IX. | X. | XI. | XII. | XIII. |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Δ^{2} | ½ | −1 | |||||||||||
Δ^{3} | ¼ | −1 | +⅓ | ||||||||||
Δ^{4} | 3/32 | +1 | 0 | −1/9 | |||||||||
Δ^{5} | 3/64 | +1 | −7/36 | −1/9 | +1/180 | ||||||||
Δ^{6} | 5/256 | −1 | 0 | +3/20 | 0 | −1/900 | |||||||
Δ^{7} | 5/512 | −1 | +1⅛0 | +3/20 | −131/25200 | −1/900 | −4/6300 | ||||||
Δ^{8} | 35/8192 | +1 | 0 | −19/112 | 0 | +109/58800 | 0 | +1/11025 | |||||
Δ^{9} | 35/16384 | +1 | −143/1344 | −19/112 | +9539/2116800 | +109/58800 | +323/396900 | +1/11025 | +16/396900 | ||||
Δ^{10} | 63/65536 | −1 | 0 | +2195/12096 | 0 | −8971/3810240 | 0 | −647/3572100 | 0 | −16/3572100 | |||
Δ^{11} | 63/131072 | −1 | +4199/48384 | +2195/12096 | −655541/167650560 | −8971/3810240 | −131977/157172400 | −647/3572100 | −2572/39293100 | −16/3572100 | −64/39293100 | ||
Δ^{12} | 231/1048576 | +1 | 0 | −33593/177408 | 0 | +333167/122943744 | 0 | +5935/23051952 | 0 | +92/8820900 | 0 | +64/432224100 | |
Δ^{13} | 231/2097152 | +1 | −7429/101376 | −33593/177408 | +21947281/6393074688 | +333167/122943744 | +975761/1198701504 | +5935/23051952 | +440617/5618913300 | +92/8820900 | +17968/5618913300 | +64/432224100 | +256/5618913300 |
Note.—If it is preferred to arrange the differences in the Bessel fashion, the Lagrange table will apply, provided that all the numbers which are on the same diagonals as the zeros are also made zero. In other words, all the numbers which lie below the same number must be made zero,