T. Popoviciu,Consideraţii teoretice asupra utilizării practice a unor formule de interpolare, Bul. şt. Acad. R.P.R.,3(1951) no. 4, pp. 441-449 (in Romanian) .
of this formula.
These coefficients will be found on the upper (descending) side of the array of divided differences corresponding to the nodes taken in order (4). However, for the formation of this array, it will be advantageous for the nodes (4) to be in the ascending order of their numerical values, because then all the divisions that are made with the difference of nodes in order to form the array, are made with positive numbers based on the recurrence relation
In this way, errors that could arise from inattention to the signs of node differences are eliminated.
2. To simplify the notations, let us assume that the nodes, which we consider distinct, are taken in ascending order, so that
Then, based on the previous observation, table (3) is the most advantageous of all.n+1n+1analogous arrays obtained by permuting in all the waysn+1n+1knots.
We observe that not only the interpolation formula (2) enjoys the property that all its coefficients are contained in the table (3). Let us then find all the formulas (5) that have all their coefficients in the table (3). We will say that these formulas belong to the table (3). For this it is necessary and sufficient that for anyi=0,1,dots,ni=0,1, \ldots, npointsx_(nu_(1)),x_(nu_(2)),dots,x_(nu_(i+1))x_{\nu_{1}}, x_{\nu_{2}}, \ldots, x_{\nu_{i+1}}to bei+1i+1consecutive points (taken in a certain order) of the string (1), so as the permutation
of numbers1,2dots n+11,2 \ldots n+1to enjoy the property that any section
v_(1),v_(2),dots,v_(i+1),i=0,1,dots,nv_{1}, v_{2}, \ldots, v_{i+1}, i=0,1, \ldots, n
of the string (9) to be formed byi+1i+1consecutive natural numbers taken in a certain order.
If we agree to say about such a permutation (9) that it is a permutation consecutive to the initial permutation1,2,dots,n+11,2, \ldots, n+1, we see that:
the necessary and sufficient condition for the interpolation formula (5) to belong to the array (3) is that the permutation (9) is a permutation consecutive to the initial permutation1,2,dots,n+11,2, \ldots, n+1[the permutation with which the tableau (3) was formed].
Let us call neighboring elements of an element of the array (3) those elements that are found in the immediately preceding column and in the immediately following column, located immediately above and immediately below the element under consideration. The neighboring elements of the element[x_(i),x,dots,x_(i+j);f]\left[x_{i}, x, \ldots, x_{i+j} ; f\right]are then shown in the diagram
An element therefore generally has 4 neighboring elements. The only exceptions are the elements on the sides of the triangular array, namely: the elements[x_(1);f][x_(n+1);f]\left[x_{1} ; f\right]\left[x_{n+1} ; f\right]which have only one neighboring element,[x_(2);f],[x_(3);f],dots,[x_(n);f],[x_(1),x_(2),dots,x_(n+1);f]\left[x_{2} ; f\right],\left[x_{3} ; f\right], \ldots,\left[x_{n} ; f\right],\left[x_{1}, x_{2}, \ldots, x_{n+1} ; f\right]only two neighboring elements,iar[x_(1),x_(2);f],[x_(1),x_(2),x_(3);f],dots,[x_(1),x_(2),dots,x_(n);f][x_(n),x_(n+1);f],[x_(n-1),x_(n),x_(n+1);f],[x_(2),x_(3),dots,x_(n+1);f]\operatorname{iar}\left[x_{1}, x_{2} ; f\right],\left[x_{1}, x_{2}, x_{3} ; f\right], \ldots,\left[x_{1}, x_{2}, \ldots, x_{n} ; f\right] \left[x_{n}, x_{n+1} ; f\right],\left[x_{n-1}, x_{n}, x_{n+1} ; f\right],\left[x_{2}, x_{3}, \ldots, x_{n+1} ; f\right]only 3 neighboring elements. It is easy to see that ifn=1n=1there are only elements with one or two neighboring elements, and ifn=2n=2, only elements with one, two or three neighboring elements.
The coefficients (8) of the formulas (5) belonging to the table (3) are then characterized by the property that any two consecutive coefficients are neighboring elements in the table (3).
3. The number of interpolation formulas (5), belonging to the table (3) can be easily determined. A formula (5) is obtained by choosing the coefficients one from each column, two consecutive coefficients being neighbors. The numberN_(n)N_{n}of these formulas is therefore equal to the number of paths that can be described starting from the first column to the last, passing only through neighboring elements. All these paths end with the element[x_(1),x_(2)dots,x_(n+1);f]\left[x_{1}, x_{2} \ldots, x_{n+1} ; f\right]But the elements[x_(1),x_(2),dots,x_(n);f],[x_(2),x_(3),dots,x_(n+1);f]\left[x_{1}, x_{2}, \ldots, x_{n} ; f\right],\left[x_{2}, x_{3}, \ldots, x_{n+1} ; f\right]are neighbors with the element in the last column, and the number of roads passing through each of these elements is obviously equal toN_(n-1)N_{n-1}It therefore follows thatN_(n)=2N_(n-1)N_{n}=2 N_{n-1}. However,N_(1)=2N_{1}=2soN_(n)=2^(n)N_{n}=2^{n}.
We can also determine the number of formulas (5) belonging to the array (3) in which the first node isx_(i)x_{i}If we denote this number byC_(n)^(i-1)C_{n}^{i-1}, we obviously haveC_(n)^(o)=1,C_(n)^(n)=1C_{n}^{o}=1, C_{n}^{n}=1and based on the previous recurrence
It is easily deduced from this thatC_(n)^(i-1)=((n)/(i-l))C_{n}^{i-1}=\binom{n}{i-l}
More generally, the number of formulas (5) belonging to the table (3) in which the firstjjnodes arex_(i),x_(i+1),dots,x_(i+j-1)x_{i}, x_{i+1}, \ldots, x_{i+j-1}in some particular order, it is equal to2^(j-1)((n-j+1)/(i-1))2^{j-1}\binom{n-j+1}{i-1}.
4. Suppose that(n+1)(n+1)! is divided by2^(n)2^{n}and then(n+1)!=2^(n)p(n+1)!=2^{n} p. However, the question may be asked whether they cannot be foundppdivided difference tables, obtained by convenient permutations of the nodes (1), so that they contain all the(n-1)(n-1)! formulas (5). In this case, each of the(n+1)(n+1)! formulas (5), to belong to one and only one of the following tablesppconsidered paintings. We will show that this is impossible except in the trivial casen=1\mathrm{n}=1.
First of all, we must note that(n+1)(n+1)! is divided by2^(n)2^{n}if and only ifn+1n+1is a power of 2. Indeed, it is known from number theory that the prime factor 2 appears in (n+1n+1)! exactly to the power (n > 1n>1 )
n+1-sum_(i=0)^(k)a_(0)n+1-\sum_{i=0}^{k} a_{0}
wherea_(0)a_(1)dotsa_(k)a_{0} a_{1} \ldots a_{k}is the numbern+1n+1written in the dyadic system. So we must havesum_(i=0)^(k)a_(i)=1\sum_{i=0}^{k} a_{i}=1, from wherea_(0)=1,a_(1)=a_(2)=dots=a_(k)=0a_{0}=1, a_{1}=a_{2}=\ldots=a_{k}=0, that is
More precisely, it is seen that (n+1n+1)! is divided by2^(n)2^{n}only if we have (10) and then the quotientppis an odd number.
Let us now assume that we have (10) and thatn > 1n>1, sok > 1k>1. Be it thenppdivided difference tables. If all the (n+1n+1)! formulas (5) would belong to thesepppaintings, should in particular belong to these paintings exactlynn! formulas with the first nodex_(1)x_{1}However, to any tableau of divided differences there belongs at least one formula with the first nodex_(1)x_{1}and we saw that the number of formulas with the first nodex_(1)x_{1}which belongs to a painting can only be
1,((n)/(1)),((n)/(2)),dots,((n)/(n-1))" sau "((n)/(n))1,\binom{n}{1},\binom{n}{2}, \ldots,\binom{n}{n-1} \text { sau }\binom{n}{n}
Let then be the number of paintings, among thoseppconsidered, to which they belong((n)/(i))\binom{n}{i}formulas with the first nodex_(1)x_{1}We must have
which is impossible, because in hypothesis (10) it is proven that all numbers ((n)/(1))-1,i=1,2dots,n-1\binom{n}{1}-1, i=1,2 \ldots, n-1are even, and the numbern!-pn!-pis odd.
5. Suppose that the nodes (1) are in ascending order, so thatx_(1) < x_(2) < dots < x_(n+1)x_{1}<x_{2}<\ldots<x_{n+1}and bexxa fixed point of the real axis different from these nodes. We then propose to determine the permutation (4) such that the numbers
{:(12)|(x-x_(v_(1)))(x-x_(v_(2)))dots(x-x_(v_(i)))|","i=1","2","dots","n:}\begin{equation*}
\left|\left(x-x_{v_{1}}\right)\left(x-x_{v_{2}}\right) \ldots\left(x-x_{v_{i}}\right)\right|, i=1,2, \ldots, n \tag{12}
\end{equation*}
to be the smallest possible.
In using Newton's formula (5), this property applies when we want the multiplierl(x)l(x)of the remainder (6) to be the smallest possible in absolute value, when we stop this formula successively at1,2,dots,n+11,2, \ldots, n+1terms. Indeed, we have, based on formulas (5), (6), (7),
be nondecreasing.
By this property, the permutation (4) is not necessarily uniquely determined, but we will prove that:
x being a given point of the real axis, any permutation (4) for which the sequence (13) is nondecreasing is a permutation consecutive to the initial permutation1,2,dots,n+11,2, \ldots, \mathrm{n}+1.
This property exists regardless of the fact thatxxcoincide or not I have a knot.
To prove the property it will be enough to show that ifv_(1),v_(2),dots,v_(i)v_{1}, v_{2}, \ldots, v_{i}are consecutive natural numbers in a certain order and the natural numbersv_(1),v_(2),dots,v_(i),v_(i+1)v_{1}, v_{2}, \ldots, v_{i}, v_{i+1}enjoys this property.
( x <= (x_(1)+x_(2))/(2)x \leqq \frac{x_{1}+x_{2}}{2}forr=1r=1and(x_(n)+x_(n+1))/(2) <= x\frac{x_{n}+x_{n+1}}{2} \leqq xforr=n+1r=n+1)
Let us now suppose thatv_(i_(1)),v_(i_(2)),dots,v_(i)v_{i_{1}}, v_{i_{2}}, \ldots, v_{i}areiiconsecutive natural numbers and eithers,s+1,dots,s+i-1s, s+1, \ldots, s+i-1these numbers. We then have
(x_(s-1)+x_(s+i-1))/(2) <= x <= (x_(s)+x_(s+i))/(2)\frac{x_{s-1}+x_{s+i-1}}{2} \leqq x \leqq \frac{x_{s}+x_{s+i}}{2}
therefore all the more so
x_(s-1) < x < x_(s+i)x_{s-1}<x<x_{s+i}
and based on the above observation
min quad(|x-x_(j)|)=min(|x-x_(s-1)|,|x-x_(s+i)|)\min \quad\left(\left|x-x_{j}\right|\right)=\min \left(\left|x-x_{s-1}\right|,\left|x-x_{s+i}\right|\right)
j=1,2,dots,s-1,s+i,s+i+1,dots,n+1j=1,2, \ldots, s-1, s+i, s+i+1, \ldots, n+1
MEANv_(i+1)=s-1v_{i+1}=s-1ors+is+i, precisely what needed to be demonstrated.
In the case whens=1s=1, ors+i-1=n+1s+i-1=n+1, the demonstration changes slightly by simplifying and it is unnecessary to reproduce it again.
If the permutation (4) enjoys the property that it is possible to find axx, so that the sequence (13) is non-decreasing, we will say that this permutation or the corresponding formula (5) verifies the minimum property.
6. Interpolation formulas (5), for which the sequence (13) becomes non-decreasing for axxconveniently, they all belong to the array (3) formed with the nodes taken in ascending order.
Not all of them2^(n)2^{n}formulas (5) belonging to table (3) verify the minimum property studied.
It can be safely stated that at least2n2 nof these formulas verify the minimum property. Namely, if we successively take forxxthe means of the intervals(x_(i),x_(i+1)),i=1,2,dots,n\left(x_{i}, x_{i+1}\right), i=1,2, \ldots, n, we see that the permutations
1,2,dots,n+1quad;n+1,n dots,2,11,2, \ldots, n+1 \quad ; n+1, n \ldots, 2,1
as well as at least one of the permutations of the forms
i+1,i+2,dotsquad;quad i+1,i,dotsi+1, i+2, \ldots \quad ; \quad i+1, i, \ldots
verify the minimum property fori=1,2,dots,n-1i=1,2, \ldots, n-1For
n=1,2n=1,2HAVE2n=2^(n)2 n=2^{n}, so, in these cases, the 2nd and 4th formulas belonging to the table (3), respectively, verify the minimum property.
Ifn=3n=3HAVE2^(n)-2n=22^{n}-2 n=2Taking successively forxxthe means of the intervals(x_(1),x_(2)),(x_(1),x_(3)),(x_(2),x_(4)),(x_(3),x_(4))\left(x_{1}, x_{2}\right),\left(x_{1}, x_{3}\right),\left(x_{2}, x_{4}\right),\left(x_{3}, x_{4}\right), it is verified that 6 of the 8 consecutive permutations of the permutation1,2,3,41,2,3,4always checks the minimum property. The remaining permutations, which are2,3,4,12,3,4,1and3,2,1,43,2,1,4, check the minimum property if we have respectively
(x_(1)+x_(4))/(2) <= x <= (x_(2)+x_(3))/(2)" si "(x_(2)+x_(3))/(2) <= x <= (x_(1)+x_(4))/(2)\frac{x_{1}+x_{4}}{2} \leqq x \leqq \frac{x_{2}+x_{3}}{2} \text { si } \frac{x_{2}+x_{3}}{2} \leqq x \leqq \frac{x_{1}+x_{4}}{2}
It is seen that ifx_(1)+x_(4)!=x_(2)+x_(3),7x_{1}+x_{4} \neq x_{2}+x_{3}, 7of the 8 formulas belonging to the table (3) verify the minimum property, and ifx_(1)+x_(4)=x_(2)+x_(3)x_{1}+x_{4}=x_{2}+x_{3}, all 8 formulas verify the minimum property.
Ifn >= 4n \geqq 4, not all of them2^(4)2^{4}consecutive permutations of1,2,dots,n+11,2, \ldots, n+1checks the minimum property. Thus, it is impossible that the four permutations (in which it is sufficient to write the first 5 elements)
to verify the property. Indeed, for the opposite case we should havex_(1)+x_(4)=x_(2)+x_(3)x_{1}+x_{4}=x_{2}+x_{3}andx_(1)+x_(5)=x_(2)+x_(3)x_{1}+x_{5}=x_{2}+x_{3}sox_(4)=x_(5)x_{4}=x_{5}, which is in contradiction with the hypothesis that the nodes are distinct.
A more detailed analysis shows us that in the case ofn=4n=4, of the 16 formulas (5) belonging to the table (3), at least 11 and at most 14 verify the minimum property.
It would be interesting to see, fornnany, what is the minimum number( >= 2n)(\geq 2 n)and what is the maximum number (< 2^(n)<2^{n}ifn > 3n>3) of consecutive permutations to the initial permutation that can verify the minimum property.
For a given configuration of nodes the number of formulas that verify the minimum property can be easily determined. To determine this number we do not need to examine the monotonicity of the sequence (13) for all values ofxx, but for reasons of continuity, only those values ofxxfor which the sequence (13) is nondecreasing without being increasing. This comes down to examining the (finitely) values ofxx, for which we have
It is therefore sufficient to examine only the pointsxxwhich coincide with the means of the segments determined by two nodes.
In particular, if the nodes (1) are equidistant, the pointsxxthat intervene are the nodes themselves as well as the means of the segments determined by two consecutive nodes.
A detailed enumeration, which we will not reproduce, leads us to the result that if the nodes are equidistant, the number of formulas (5) belonging to the table (3) and verifying the minimum property is equal to
where[alpha][\alpha]is the whole contained inalpha\alpha.
7. To apply the interpolation formula, at pointxxwe will choose that formula (5) that verifies the property that the sequence (13) is non-decreasing.
Let us suppose, in particular, that the nodes are symmetrical about a point on the real axis. This point can be chosen as the origin 0. We must then distinguish two cases, according to whether the nodes are odd or even in number. If we assume that we interpolate in the vicinity of the origin, we must also distinguish two cases according to whether the pointxxis to the left or right of 0 .
Case I. Odd number of nodes. The nodes in ascending order can then be written (n=2kn=2 k )
asxxis to the left or right of 0 .
Ifxxis close enough to the origin, these are the only permutations that verify the minimum property.
The corresponding interpolation formulas are known generalizations of the arithmetic mean of these equations, when the nodes are known realizations of the interpolation formula, a gene is deduced, and we explicitly write these formulas here.
Case 11. Even number of nodes then write (n=2k-1n=2 k-1 )
asxxis to the left or to the right of 0. These permutations are the only ones that verify the minimum property ifxxis close enough to the origin.
The corresponding interpolation formulas are well-known generalizations of other Euler formulas, which also reduce if the nodes are equidistant. By taking the arithmetic mean of these two formulas, we obtain a well-known generalization of Bessel's interpolation formula. It is unnecessary to write these formulas explicitly.
The minimum property that we established constitutes a justification for using these formulas, when interpolating in the middle of the table of divided differences.
THEORETICAL CONSIDERATIONS REGARDING THE PRACTICAL APPLICATION OF SOME INTERPOLATION FORMULAS
(SUMMARY)
Each non-rearrangement of the given interpolation nodes (1) corresponds to a single Newton interpolation formula (5). The coefficients (8) of this formula are contained in the table of divided differences. The most advantageous is the table (3), composed of nodes arranged in order of increasing magnitude. It is shown that the interpolation formulas (5), for which the remainder is best bounded for all parts of these formulas, have their coefficients contained in tables (3) compiled in this manner.
These remarks justify the application of the classical formulas of Eyler, Stirling and Bessel.
THEORETICAL CONSIDERATIONS ON THE PRACTICAL USE OF SOME INTERPOLATION FORMULAE
(RÉSUMÉ)
For any permutation of given interpolation nodes (1), there corresponds a Newton interpolation formula (5). The coefficients (8) of this formula appear in the table of divided differences. The most advantageous table is table (3) constructed with the nodes taken in the order of increasing magnitude. It is shown that the interpolation formulas (5) for which the remainder is the best, for any section of these formulas, have their coefficients included in the table thus constructed.
These remarks constitute a justification for the use of the classical formulas of Euler, Stirling and Bessel.
^(1)){ }^{1)}The deadline fori=0i=0it reduces to[x_(1);f]=f(x_(3))\left[x_{1} ; f\right]=f\left(x_{3}\right)We use the notations{:x_(1),x_(2),dots,x_(i);f]\left.x_{1}, x_{2}, \ldots, x_{i} ; f\right]for the divided difference of the functionf(x)f(x)on the nodesx_(1),x_(2),dots,x^(i)x_{1}, x_{2}, \ldots, x^{i}.
