On the accuracy of numerical computation in polynomial interpolation

Tiberiu Popoviciu
(original), approximation of univariate functions, Approximation Theory, interpolation, paper

Abstract

Authors

T. Popoviciu
Institutul de Calcul

Keywords

?

Paper coordinates

T. Popoviciu, Despre precizia calculului numeric în interpolare prin polinoame. Buletinul științific, Secția de științe matematice și fizice (Academia R.P.R.), 7 (1955) no. 4, pp. 953-961.

PDF

https://ictp.acad.ro/wp-content/uploads/2025/10/1955-c-Popoviciu-Bul.-St.-Sect.-St.-Mat.-Fiz.-Despre-precizia-calculului-numeric-in-interpolarea-prin-polinoame.pdf

About this paper

Journal

Buletinul Stiintific

Publisher Name

Academy of the Republic of S.R.

DOI
Print ISSN
Online ISSN

google scholar link

??

Paper (preprint) in HTML form

1955 c -Popoviciu- Bul. St. Sect. St. Mat. Fiz. - On the precision of numerical calculation in interpolation
Original text
Rate this translation
Your feedback will be used to help improve Google Translate
DEPARTMENT OF MATHEMATICAL AND PHYSICAL SCIENCES
'Volume VJI, no. 4, 1955

ON THE PRECISION OF NUMERICAL CALCULATION IN INTERPOLATION BY POLYNOMIALS

OF

TIBERIU POPOVICIUCORRESPONDING MEMBER OF THE RPR ACADEMY

Present communication at the meeting of June 30, 1955
  1. To calculate an approximate value of the function f ( x ) f ( x ) f(x)f(x)f(x), real and the real variable x x xxx, on the point x 0 x 0 x_(0)x_{0}x0, when the values ​​were known f ( x and ) , and = 1 , 2 , … , n + 1 f x and , and = 1 , 2 , … , n + 1 f(x_(i)),i=1,2,dots,n+1f\left(x_{i}\right), i=1,2, \ldots, n+1f(xand),and=1,2,…,n+1, of this function on n + 1 n + 1 n+1n+1n+1(distinct) data points x and , and = 1 , 2 , … , n + 1 x and , and = 1 , 2 , … , n + 1 x_(i),i=1,2,dots,n+1x_{i}, i=1,2, \ldots, n+1xand,and=1,2,…,n+1, the interpolation formula can be used
(1) f ( x 0 ) = IT ( x 1 , x 2 , … , x n + 1 ; f ∣ x 0 ) , (1) f x 0 = IT x 1 , x 2 , … , x n + 1 ; f ∣ x 0 , {:(1)f(x_(0))=L(x_(1),x_(2),dots,x_(n+1);f∣x_(0))",":}\begin{equation*} f\left(x_{0}\right)=L\left(x_{1}, x_{2}, \ldots, x_{n+1} ; f \mid x_{0}\right), \tag{1} \end{equation*}(1)f(x0)=IT(x1,x2,…,xn+1;f∣x0),
where IT ( x 1 , x 2 , … , x n + 1 ; f ∣ x 0 ) IT x 1 , x 2 , … , x n + 1 ; f ∣ x 0 L(x_(1),x_(2),dots,x_(n+1);f∣x_(0))L\left(x_{1}, x_{2}, \ldots, x_{n+1} ; f \mid x_{0}\right)IT(x1,x2,…,xn+1;f∣x0)is the Lagrange polynomial of degree n n nnnand which takes the values f ( x and ) f x and f(x_(i))f\left(x_{i}\right)f(xand)on interpolation points or nodes x and x and x_(i)x_{i}xand.
We will assume that the nodes are not necessarily equidistant and we will calculate the second term of formula (1) using Newton's formula, IT ( x 1 , x 2 , … , x n + 1 ; f ∣ x 0 ) = ∑ and = 0 n ( x 0 − x 1 ) ( x 0 − x 2 ) … ( x 0 − x and ) D 1 j ) IT x 1 , x 2 , … , x n + 1 ; f ∣ x 0 = ∑ and = 0 n   x 0 − x 1 x 0 − x 2 … x 0 − x and D 1 j {:L(x_(1),x_(2),dots,x_(n+1);f∣x_(0))=sum_(i=0)^(n)(x_(0)-x_(1))(x_(0)-x_(2))dots(x_(0)-x_(i))D_(1)^(j))DIT(x1,x2,…,xn+1;f∣x0)=∑and=0n(x0−x1)(x0−x2)…(x0−xand)D1j), where the coefficients D and and , and = 0 , 1 , … , n D and and , and = 0 , 1 , … , n D_(i)^(i),i=0,1,dots,nD_{i}^{i}, i=0,1, \ldots, nDandand,and=0,1,…,n, are obtained from table no. 1 of divided differences in which we have, in general,
D and j = D and j [ f ] = [ x and , x and + 1 , … , x and + j ; f ] (3) D and 0 = f and = f ( x and ) D and j = D and j [ f ] = x and , x and + 1 , … , x and + j ; f (3) D and 0 = f and = f x and {:[D_(i)^(j)=D_(i)^(j)[f]=[x_(i),x_(i+1),dots,x_(i+j);f]],[(3)D_(i)^(0)=f_(i)=f(x_(i))]:}\begin{gather*} D_{i}^{j}=D_{i}^{j}[f]=\left[x_{i}, x_{i+1}, \ldots, x_{i+j} ; f\right] \\ D_{i}^{0}=f_{i}=f\left(x_{i}\right) \tag{3} \end{gather*}Dandj=Dandj[f]=[xand,xand+1,…,xand+j;f](3)Dand0=fand=f(xand)
using the usual notations for divided differences of the function f ( x ) f ( x ) f(x)f(x)f(x).
The formation of table no. 1 of the divided differences is done by successively calculating the columns using the recurrence formula
(4) D and j [ f ] = D and + 1 and − 1 [ f ] − D and j − 1 [ f ] x and + j − x and ( D and 0 [ f ] = f and ) and = 1 , 2 , … , n + 1 − j , j = 1 , 2 , … , n (4) D and j [ f ] = D and + 1 and − 1 [ f ] − D and j − 1 [ f ] x and + j − x and D and 0 [ f ] = f and and = 1 , 2 , … , n + 1 − j , j = 1 , 2 , … , n {:[(4)D_(i)^(j)[f]=(D_(i+1)^(i-1)[f]-D_(i)^(j-1)[f])/(x_(i+j)-x_(i))quadquadquad(D_(i)^(0)[f]=f_(i))],[i=1","2","dots","n+1-j","quad j=1","2","dots","n]:}\begin{align*} D_{i}^{j}[f] & =\frac{D_{i+1}^{i-1}[f]-D_{i}^{j-1}[f]}{x_{i+j}-x_{i}} \quad \quad \quad\left(D_{i}^{0}[f]=f_{i}\right) \tag{4}\\ i & =1,2, \ldots, n+1-j, \quad j=1,2 \ldots, n \end{align*}(4)Dandj[f]=Dand+1and−1[f]−Dandj−1[f]xand+j−xand(Dand0[f]=fand)and=1,2,…,n+1−j,j=1,2,…,n
It is seen that this calculation requires divisions (with node differences) due to which, in general, the divided differences cannot be calculated, for example, in the practical form of limited decimal fractions, except with a certain approximation, even
Tableau m. 1
if the nodes and the values ​​of the function on these nodes are given in this form. However, if the elements of the table no. I are calculated approximately, the errors committed are carried over to the interpolation polynomial. In the following we propose to examine the effect of these errors on the elective calculation of formula (2). For simplicity, we will assume that the nodes and the point x 0 x 0 x_(0)x_{0}x0, where interpolation is performed, are not affected by errors.
2. The columns of table no. 1. are calculated successively with certain approximations.
Whether f ~ i , i = 1 , 2 , … n + 1 f ~ i , i = 1 , 2 , … n + 1 widetilde(f)_(i),i=1,2,dots n+1\widetilde{f}_{i}, i=1,2, \ldots n+1f~and,and=1,2,…n+1, some approximate values ​​of the function values ​​on the nodes and c i ( 0 ) , i = 1 , 2 , … , n + 1 c i ( 0 ) , i = 1 , 2 , … , n + 1 c_(i)^((0)),i=1,2,dots,n+1c_{i}^{(0)}, i=1,2, \ldots, n+1cand(0),and=1,2,…,n+1, the respective corrections, so f i = f ~ i + c i ( 0 ) f i = f ~ i + c i ( 0 ) f_(i)= widetilde(f)_(i)+c_(i)^((0))f_{i}=\widetilde{f}_{i}+c_{i}^{(0)}fand=f~and+cand(0), i = 1 , 2 , … , n + 1 i = 1 , 2 , … , n + 1 i=1,2,dots,n+1i=1,2, \ldots, n+1and=1,2,…,n+1. Let then, in general, D ~ i j = D ~ i i [ t ] , i = 1 , 2 , … , n + 1 − j D ~ i j = D ~ i i [ t ] , i = 1 , 2 , … , n + 1 − j widetilde(D)_(i)^(j)= widetilde(D)_(i)^(i)[t],i=1,2,dots,n+1-j\widetilde{D}_{i}^{j}=\widetilde{D}_{i}^{i}[t], i=1,2, \ldots, n+1-jD~andj=D~andand[t],and=1,2,…,n+1−j, approximate values ​​of the column elements j j jjj, calculated using the already calculated elements of the column j − 1 j − 1 j-1j-1j−1and c i ( j ) , i = 1 , 2 , … , n + 1 − j c i ( j ) , i = 1 , 2 , … , n + 1 − j c_(i)^((j)),i=1,2,dots,n+1-jc_{i}^{(j)}, i=1,2, \ldots, n+1-jcand(j),and=1,2,…,n+1−j, the respective corrections. We will then
(5) D ~ i j + c i ( j ) == D ~ i + 1 j − 1 − D ~ i j − 1 x i + j − x i ( D ~ i 0 = f ~ i ) (5) D ~ i j + c i ( j ) == D ~ i + 1 j − 1 − D ~ i j − 1 x i + j − x i D ~ i 0 = f ~ i {:(5) widetilde(D)_(i)^(j)+c_(i)^((j))==( widetilde(D)_(i+1)^(j-1)- widetilde(D)_(i)^(j-1))/(x_(i+j)-x_(i))( widetilde(D)_(i)^(0)= widetilde(f)_(i)):}\begin{equation*} \widetilde{D}_{i}^{j}+c_{i}^{(j)}==\frac{\widetilde{D}_{i+1}^{j-1}-\widetilde{D}_{i}^{j-1}}{x_{i+j}-x_{i}}\left(\widetilde{D}_{i}^{0}=\widetilde{f}_{i}\right) \tag{5} \end{equation*}(5)D~andj+cand(j)==D~and+1j−1−D~andj−1xand+j−xand(D~and0=f~and)
i = 1 , 2 , … , n + 1 − j , j = 1 , 2 , … , n . i = 1 , 2 , … , n + 1 − j , j = 1 , 2 , … , n . i=1,2,dots,n+1-j,j=1,2,dots,n.quadi=1,2, \ldots, n+1-j, j=1,2, \ldots, n . \quadand=1,2,…,n+1−j,j=1,2,…,n.The
table m. 1 of the divided differences is then replaced by the table m. 2 of the calculated approximate values ​​of the divided differences.
Tableau m. 2
An approximate value L ~ L ~ tilde(L)\tilde{L}IT~of expression (2) is then obtained using table no. 2 with the formula
(6) L ~ = ∑ i = 0 n ( x 0 − x 1 ) ( x 0 − x 2 ) … ( x 0 − x i ) D ~ 1 j (6) L ~ = ∑ i = 0 n   x 0 − x 1 x 0 − x 2 … x 0 − x i D ~ 1 j {:(6) widetilde(L)=sum_(i=0)^(n)(x_(0)-x_(1))(x_(0)-x_(2))dots(x_(0)-x_(i)) widetilde(D)_(1)^(j):}\begin{equation*} \widetilde{L}=\sum_{i=0}^{n}\left(x_{0}-x_{1}\right)\left(x_{0}-x_{2}\right) \ldots\left(x_{0}-x_{i}\right) \widetilde{D}_{1}^{j} \tag{6} \end{equation*}(6)IT~=∑and=0n(x0−x1)(x0−x2)…(x0−xand)D~1j
and we will have
(7) L ( x 1 , x 2 , … , x n + 1 ; / ∣ x 0 ) = L ~ + λ , (7) L x 1 , x 2 , … , x n + 1 ; / ∣ x 0 = L ~ + λ , {:(7)L(x_(1),x_(2),dots,x_(n+1);//∣x_(0))= widetilde(L)+lambda",":}\begin{equation*} L\left(x_{1}, x_{2}, \ldots, x_{n+1} ; / \mid x_{0}\right)=\widetilde{L}+\lambda, \tag{7} \end{equation*}(7)IT(x1,x2,…,xn+1;/∣x0)=IT~+λ,
  1. fiiitd the respective correction.
In view of the correction delimitation λ λ lambda\lambdaλ, we will make some observations on the recurrence formula of divided differences and on the delimitation of divided differences, which will come in.
3. Given the sequence of (distinct) nodes
(8) x 1 , x 2 , … , x n + 1 (8) x 1 , x 2 , … , x n + 1 {:(8)x_(1)","x_(2)","dots","x_(n+1):}\begin{equation*} x_{1}, x_{2}, \ldots, x_{n+1} \tag{8} \end{equation*}(8)x1,x2,…,xn+1
any string of n + 1 n + 1 n+1n+1n+1numbers
(9) f 1 , f 2 , … , f n + 1 (9) f 1 , f 2 , … , f n + 1 {:(9)f_(1)","f_(2)","dots","f_(n+1):}\begin{equation*} f_{1}, f_{2}, \ldots, f_{n+1} \tag{9} \end{equation*}(9)f1,f2,…,fn+1
can be considered to be formed by the values f i = f ( x i ) , i = 1 , 2 , … , n + 1 f i = f x i , i = 1 , 2 , … , n + 1 f_(i)=f(x_(i)),i=1,2,dots,n+1f_{i}=f\left(x_{i}\right), i=1,2, \ldots, n+1fand=f(xand),and=1,2,…,n+1, of a function f ( a ) f ( a ) f(a)f(a)f(A)defined on points (8). This simple observation clarifies various notations, which will follow.
Whether k k kkka non-negative integer < n < n < n<n<nand let's consider, for j = 0 , 1 , … … , n − k j = 0 , 1 , … … , n − k j=0,1,dots dots,n-kj=0,1, \ldots \ldots, n-kj=0,1,……,n−k, the string
(10) D 1 j , k [ f ] , D 2 j , k [ f ] , … , D n + 1 − k − j j , k [ f ] (10) D 1 j , k [ f ] , D 2 j , k [ f ] , … , D n + 1 − k − j j , k [ f ] {:(10)D_(1)^(j,k)[f]","D_(2)^(j,k)[f]","dots","D_(n+1-k-j)^(j,k)[f]:}\begin{equation*} D_{1}^{j, k}[f], D_{2}^{j, k}[f], \ldots, D_{n+1-k-j}^{j, k}[f] \tag{10} \end{equation*}(10)D1j,k[f],D2j,k[f],…,Dn+1−k−jj,k[f]
formed by the help of the recurrence formula
D i i , h [ f ] = D i + 1 i − 1 , h [ f ] − D i j − 1 , h [ f ] x i + j + h − x i , (11) i = 1 , 2 , … , n + 1 − k − i D i i , h [ f ] = D i + 1 i − 1 , h [ f ] − D i j − 1 , h [ f ] x i + j + h − x i , (11) i = 1 , 2 , … , n + 1 − k − i {:[D_(i)^(i,h)[f]=(D_(i+1)^(i-1,h)[f]-D_(i)^(j-1,h)[f])/(x_(i+j+h)-x_(i))","],[(11)i=1","2","dots","n+1-k-i]:}\begin{gather*} D_{i}^{i, h}[f]=\frac{D_{i+1}^{i-1, h}[f]-D_{i}^{j-1, h}[f]}{x_{i+j+h}-x_{i}}, \\ i=1,2, \ldots, n+1-k-i \tag{11} \end{gather*}Dandand,h[f]=Dand+1and−1,h[f]−Dandj−1,h[f]xand+j+h−xand,(11)and=1,2,…,n+1−k−and
where D i 0 , k [ f ] = f i , i = 1 , 2 , … , n + 1 − k D i 0 , k [ f ] = f i , i = 1 , 2 , … , n + 1 − k D_(i)^(0,k)[f]=f_(i),i=1,2,dots,n+1-kD_{i}^{0, k}[f]=f_{i}, i=1,2, \ldots, n+1-kDand0,k[f]=fand,and=1,2,…,n+1−k. Thus, for j = 0 j = 0 j=0j=0j=0the string (10) reduces to the string formed by the first n + 1 − k n + 1 − k n+1-kn+1-kn+1−kterms of the sequence (9).
It is clear that the terms of the series (10) are expressed linearly and homogeneously with respect to the first n + 1 − k n + 1 − k n+1-kn+1-kn+1−kterms of the sequence (9) and, in general, the terms of the sequence (10), for a j j jjjgiven, the terms of the series (10) for the immediately lower value of are expressed linearly and homogeneously j j jjj.
For k = 0 k = 0 k=0k=0k=0, we have D i i , 0 [ f ] = D i i , i = 1 , 2 , … , n + 1 − j D i i , 0 [ f ] = D i i , i = 1 , 2 , … , n + 1 − j D_(i)^(i,0)[f]=D_(i)^(i),i=1,2,dots,n+1-jD_{i}^{i, 0}[f]=D_{i}^{i}, i=1,2, \ldots, n+1-jDandand,0[f]=Dandand,and=1,2,…,n+1−j, formulas (11) reduce to formulas (4), and the sequence (10) reduces to the set of column elements of order j j jjjfrom table no. 1 of the divided differences of the function f ( x ) f ( x ) f(x)f(x)f(x)on the nodes (8).
The formula (11) that connects the strings (10) for successive values ​​of j j jjj, it can also be written
(12) D i j , k [ f ] = D i 1 ^ , k + j − 1 [ D j − 1 , k [ f ] ] (12) D i j , k [ f ] = D i 1 ^ , k + j − 1 D j − 1 , k [ f ] {:(12)D_(i)^(j,k)[f]=D_(i)^( hat(1),k+j-1)[D^(j-1,k)[f]]:}\begin{equation*} D_{i}^{j, k}[f]=D_{i}^{\hat{1}, k+j-1}\left[D^{j-1, k}[f]\right] \tag{12} \end{equation*}(12)Dandj,k[f]=Dand1^,k+j−1[Dj−1,k[f]]
More generally, we have the formula
(13) D i j , k [ / ] = D i r , k + j − r [ D j − r , k [ / ] ] , (13) D i j , k [ / ] = D i r , k + j − r D j − r , k [ / ] , {:(13)D_(i)^(j,k)[//]=D_(i)^(r,k+j-r)[D^(j-r,k)[//]]",":}\begin{equation*} D_{i}^{j, k}[/]=D_{i}^{r, k+j-r}\left[D^{j-r, k}[/]\right], \tag{13} \end{equation*}(13)Dandj,k[/]=DandR,k+j−R[Dj−R,k[/]],
where r r rrRis an integer; 0 ⩽ r ⩽ j 0 ⩽ r ⩽ j 0 <= r <= j0 \leqslant r \leqslant j0⩽R⩽j.
9 - c. 1540
Indeed, it is observed that for r = 0 r = 0 r=0r=0R=0and r = j r = j r=jr=jR=j, formula (13) is obvious, and for r = 1 r = 1 r=1r=1R=1it reduces to (12). To prove formula (13) it is therefore sufficient to show that, if it is true for r = s ( s < j ) r = s ( s < j ) r=s(s < j)r=s(s<j)R=S(S<j), it will also be true for r = s + 1 r = s + 1 r=s+1r=s+1R=S+1. This is shown as follows. By hypothesis we have:
D i j − 1 , k [ f ] = D i s , k + j − s − 1 [ D j − s − 1 , k [ f ] ] , D i j − 1 , k [ f ] = D i s , k + j − s − 1 D j − s − 1 , k [ f ] , D_(i)^(j-1,k)[f]=D_(i)^(s,k+j-s-1)[D^(j-s-1,k)[f]],D_{i}^{j-1, k}[f]=D_{i}^{s, k+j-s-1}\left[D^{j-s-1, k}[f]\right],Dandj−1,k[f]=DandS,k+j−S−1[Dj−S−1,k[f]],
from which, if we take into account formula (12), we deduce
D i j , k [ f ] = D i 1 , k + j − 1 [ D s , k − j − s − 1 [ D j − s − 1 , k [ f ] ] = [ L i s + 1 , k + j − s − 1 [ D j − s − 1 , k [ f ] ] . D i j , k [ f ] = D i 1 , k + j − 1 D s , k − j − s − 1 D j − s − 1 , k [ f ] = L i s + 1 , k + j − s − 1 D j − s − 1 , k [ f ] . D_(i)^(j,k)[f]=D_(i)^(1,k+j-1)[D^(s,k-j-s-1)[D^(j-s-1,k)[f]]=[L_(i)^(s+1,k+j-s-1)[D^(j-s-1,k)[f]].:}D_{i}^{j, k}[f]=D_{i}^{1, k+j-1}\left[D^{s, k-j-s-1}\left[D^{j-s-1, k}[f]\right]=\left[L_{i}^{s+1, k+j-s-1}\left[D^{j-s-1, k}[f]\right] .\right.\right.Dandj,k[f]=Dand1,k+j−1[DS,k−j−S−1[Dj−S−1,k[f]]=[ITandS+1,k+j−S−1[Dj−S−1,k[f]].
From this it immediately follows that formula (13) is true for r = s + 1 r = s + 1 r=s+1r=s+1R=S+1Symbolically
, the property expressed by formula (13) can be written as
D α + β , k = D α , β + k D β , h . D α + β , k = D α , β + k D β , h . D^(alpha+beta,k)=D^(alpha,beta+k)D^(beta,h).D^{\alpha+\beta, k}=D^{\alpha, \beta+k} D^{\beta, h} .Dα+β,k=Dα,β+kDβ,h.
  1. In the following we will need a convenient delimitation of the elements of the string (9).
Divided difference D 1 n = [ x 1 , x 2 , … , x n + 1 ; f ] D 1 n = x 1 , x 2 , … , x n + 1 ; f D_(1)^(n)=[x_(1),x_(2),dots,x_(n+1);f]D_{1}^{n}=\left[x_{1}, x_{2}, \ldots, x_{n+1} ; f\right]D1n=[x1,x2,…,xn+1;f]is easily delimited, taking into account the well-known formula
[ x 1 , x 2 , … , x n + 1 ; f ] = ∑ i + 1 n + 1 f i l ′ ( x i ) x 1 , x 2 , … , x n + 1 ; f = ∑ i + 1 n + 1   f i l ′ x i [x_(1),x_(2),dots,x_(n+1);f]=sum_(i+1)^(n+1)(f_(i))/(l^(')(x_(i)))\left[x_{1}, x_{2}, \ldots, x_{n+1} ; f\right]=\sum_{i+1}^{n+1} \frac{f_{i}}{l^{\prime}\left(x_{i}\right)}[x1,x2,…,xn+1;f]=∑and+1n+1fandit′(xand)
where i i _(i){ }_{i}and
l ( x ) = ( x − x 1 ) ( x − x 2 ) … ( x − x n + 1 ) . Avem | D 1 n | ≦ N ( x 1 , x 2 , … , x n + 1 ) M , l ( x ) = x − x 1 x − x 2 … x − x n + 1 .  Avem  D 1 n ≦ N x 1 , x 2 , … , x n + 1 M , {:[l(x)=(x-x_(1))(x-x_(2))dots(x-x_(n+1))." Avem "],[|D_(1)^(n)| <= N(x_(1),x_(2),dots,x_(n+1))M","]:}\begin{array}{r} l(x)=\left(x-x_{1}\right)\left(x-x_{2}\right) \ldots\left(x-x_{n+1}\right) . \text { Avem } \\ \left|D_{1}^{n}\right| \leqq N\left(x_{1}, x_{2}, \ldots, x_{n+1}\right) M, \end{array}it(x)=(x−x1)(x−x2)…(x−xn+1). we |D1n|≦N(x1,x2,…,xn+1)M,
where
(14) N i ( x 1 , x 2 , … , x n + 1 ) = ∑ i = 1 n + 1 1 | l ′ ( x i ) | (14) N i x 1 , x 2 , … , x n + 1 = ∑ i = 1 n + 1   1 l ′ x i {:(14)N_(i)(x_(1),x_(2),dots,x_(n+1))=sum_(i=1)^(n+1)(1)/(|l^(')(x_(i))|):}\begin{equation*} N_{i}\left(x_{1}, x_{2}, \ldots, x_{n+1}\right)=\sum_{i=1}^{n+1} \frac{1}{\left|l^{\prime}\left(x_{i}\right)\right|} \tag{14} \end{equation*}(14)Nand(x1,x2,…,xn+1)=∑and=1n+11|it′(xand)|
and M = max i = 1 , 2 , … , n + 1 ( | f i | ) M = max i = 1 , 2 , … , n + 1   f i M=max_(i=1,2,dots,n+1)(|f_(i)|)M=\max _{i=1,2, \ldots, n+1}\left(\left|f_{i}\right|\right)M=MAXand=1,2,…,n+1(|fand|)An analogous delimitation
of D 1 n − k , k [ f ] D 1 n − k , k [ f ] D_(1)^(n-k,k)[f]D_{1}^{n-k, k}[f]D1n−k,k[f]it can be written
(15) | D 1 n − k , k [ f ] | ≦ N k ( x 1 , x 2 , … , x n + 1 ) M , (15) D 1 n − k , k [ f ] ≦ N k x 1 , x 2 , … , x n + 1 M , {:(15)|D_(1)^(n-k,k)[f]| <= N_(k)(x_(1),x_(2),dots,x_(n+1))M",":}\begin{equation*} \left|D_{1}^{n-k, k}[f]\right| \leqq N_{k}\left(x_{1}, x_{2}, \ldots, x_{n+1}\right) M, \tag{15} \end{equation*}(15)|D1n−k,k[f]|≦Nk(x1,x2,…,xn+1)M,
where, by the way, M M MMMcan be replaced with max i = 1 , 2 , … , n + 1 − k ( | / i | ) max i = 1 , 2 , … , n + 1 − k   ( | / i | ) max_(i=1,2,dots,n+1-k)(|//i|)\max _{i=1,2, \ldots, n+1-k}(|/ i|)MAXand=1,2,…,n+1−k(|/and|)In formula
(15) we have
N k ( x 1 , x 2 , … , x n + 1 ) = sup | f i | ≦ 1 i = 1 , 2 , … , n + 1 − k | D 1 n − k , k [ f ] | indice fic D N k x 1 , x 2 , … , x n + 1 = sup f i ≦ 1 i = 1 , 2 , … , n + 1 − k   D 1 n − k , k [ f ]  indice fic  D N_(k)(x_(1),x_(2),dots,x_(n+1))=s u p_({:[|f_(i)| <= 1],[i=1","2","dots","n+1-k]:})|D_(1)^(n-k,k)[f]|" indice fic "DN_{k}\left(x_{1}, x_{2}, \ldots, x_{n+1}\right)=\sup _{\substack{\left|f_{i}\right| \leqq 1 \\ i=1,2, \ldots, n+1-k}}\left|D_{1}^{n-k, k}[f]\right| \text { indice fic } DNk(x1,x2,…,xn+1)=soup|fand|≦1and=1,2,…,n+1−k|D1n−k,k[f]| index fic D
and therefore
N k ( x 1 , x 2 , … , x n + 1 ) = η 1 n − k , k [ f ] N k x 1 , x 2 , … , x n + 1 = η 1 n − k , k [ f ] N_(k)(x_(1),x_(2),dots,x_(n+1))=eta_(1)^(n-k,k)[f]N_{k}\left(x_{1}, x_{2}, \ldots, x_{n+1}\right)=\eta_{1}^{n-k, k}[f]Nk(x1,x2,…,xn+1)=η1n−k,k[f]
provided we choose all the numbers f i , i = 1 , 2 , … , n + 1 − k f i , i = 1 , 2 , … , n + 1 − k f_(i),i=1,2,dots,n+1-kf_{i}, i=1,2, \ldots, n+1-kfand,and=1,2,…,n+1−kequal to 1 or -1, conveniently.
we
N 0 ( x 1 , x 2 , … , x n + 1 ) = N ( x 1 , x 2 , … , x n + 1 ) N 0 x 1 , x 2 , … , x n + 1 = N x 1 , x 2 , … , x n + 1 N_(0)(x_(1),x_(2),dots,x_(n+1))=N(x_(1),x_(2),dots,x_(n+1))N_{0}\left(x_{1}, x_{2}, \ldots, x_{n+1}\right)=N\left(x_{1}, x_{2}, \ldots, x_{n+1}\right)N0(x1,x2,…,xn+1)=N(x1,x2,…,xn+1)
the second term being given by (1/4). For k > 0 k > 0 k > 0k>0k>0, his expression N k ( x 1 , x 2 , … , x n + 1 ) N k x 1 , x 2 , … , x n + 1 N_(k)(x_(1),x_(2),dots,x_(n+1))N_{k}\left(x_{1}, x_{2}, \ldots, x_{n+1}\right)Nk(x1,x2,…,xn+1)but it is more complicated.
In his formation L 1 n − k , k [ f ] L 1 n − k , k [ f ] L_(1)^(n-k,k)[f]L_{1}^{n-k, k}[f]IT1n−k,k[f]only the nodes actually intervene x i x i x_(i)x_{i}xandfor i = 1 , 2 , … , n − k , k + 2 , k + 3 , … , n + 1 i = 1 , 2 , … , n − k , k + 2 , k + 3 , … , n + 1 i=1,2,dots,n-k,k+2,k+3,dots,n+1i=1,2, \ldots, n-k, k+2, k+3, \ldots, n+1and=1,2,…,n−k,k+2,k+3,…,n+1. So if 2 k ≦ n − 1 2 k ≦ n − 1 2k <= n-12 k \leqq n-12k≦n−1,
all nodes will intervene. However, if 2 k > n − 1 2 k > n − 1 2k > n-12 k>n-12k>n−1only the first ones will intervene n − k n − k n-kn-kn−kand the last ones n − k n − k n-kn-kn−knodes (8). We deduce from this the following formula:
N k ( x 1 , x 2 , … , x n + 1 ) = N n − k − 1 ( x 1 , x 2 , … , x n − k , x k + 2 , x k + 3 , … , x n + 1 ) N k x 1 , x 2 , … , x n + 1 = N n − k − 1 x 1 , x 2 , … , x n − k , x k + 2 , x k + 3 , … , x n + 1 N_(k)(x_(1),x_(2),dots,x_(n+1))=N_(n-k-1)(x_(1),x_(2),dots,x_(n-k),x_(k+2),x_(k+3),dots,x_(n+1))N_{k}\left(x_{1}, x_{2}, \ldots, x_{n+1}\right)=N_{n-k-1}\left(x_{1}, x_{2}, \ldots, x_{n-k}, x_{k+2}, x_{k+3}, \ldots, x_{n+1}\right)Nk(x1,x2,…,xn+1)=Nn−k−1(x1,x2,…,xn−k,xk+2,xk+3,…,xn+1)if 2 k > n − 1 2 k > n − 1 2k > n-12 k>n-12k>n−1It is enough to assume k < n k < n k < nk<nk<n, because we obviously have
(17) N n ( x 1 , x 2 , … , x n − 1 ) = 1 (17) N n x 1 , x 2 , … , x n − 1 = 1 {:(17)N_(n)(x_(1),x_(2),dots,x_(n-1))=1:}\begin{equation*} N_{n}\left(x_{1}, x_{2}, \ldots, x_{n-1}\right)=1 \tag{17} \end{equation*}(17)Nn(x1,x2,…,xn−1)=1
-5. In particular, suppose that
(18) x 1 < x 2 < … < x n + 1 (18) x 1 < x 2 < … < x n + 1 {:(18)x_(1) < x_(2) < dots < x_(n+1):}\begin{equation*} x_{1}<x_{2}<\ldots<x_{n+1} \tag{18} \end{equation*}(18)x1<x2<…<xn+1
The recurrence formula ( 1 i. , no shows that if the terms of the sequence ( 9 ) are alternately positive and negative, the sequences (10) enjoy the same property. We have, on the one hand,
| D i i , k [ f ] | = 1 x i + j + k − x i [ | D i + 1 i − 1 , k [ f ] | + | D i i − 1 , k [ f ] | ] D i i , k [ f ] = 1 x i + j + k − x i D i + 1 i − 1 , k [ f ] + D i i − 1 , k [ f ] |D_(i)^(i,k)[f]|=(1)/(x_(i+j+k)-x_(i))[|D_(i+1)^(i-1,k)[f]|+|D_(i)^(i-1,k)[f]|]\left|D_{i}^{i, k}[f]\right|=\frac{1}{x_{i+j+k}-x_{i}}\left[\left|D_{i+1}^{i-1, k}[f]\right|+\left|D_{i}^{i-1, k}[f]\right|\right]|Dandand,k[f]|=1xand+j+k−xand[|Dand+1and−1,k[f]|+|Dandand−1,k[f]|]
Because, on the other hand, we always have
| D i j , k [ f ] | ≤ 1 | x i + j + k − x i | [ | D L l − k , k [ f ] | + | D i j − 1 , k [ f ] | ] D i j , k [ f ] ≤ 1 x i + j + k − x i D L l − k , k [ f ] + D i j − 1 , k [ f ] |D_(i)^(j,k)[f]| <= (1)/(|x_(i+j+k)-x_(i)|)[|D_(L)^(l-k,k)[f]|+|D_(i)^(j-1,k)[f]|]\left|D_{i}^{j, k}[f]\right| \leq \frac{1}{\left|x_{i+j+k}-x_{i}\right|}\left[\left|D_{L}^{l-k, k}[f]\right|+\left|D_{i}^{j-1, k}[f]\right|\right]|Dandj,k[f]|≤1|xand+j+k−xand|[|DITit−k,k[f]|+|Dandj−1,k[f]|]
it follows that, in case (18), the number N k ( x 1 , x 2 , … , x n + 1 ) N k x 1 , x 2 , … , x n + 1 N_(k)(x_(1),x_(2),dots,x_(n+1))N_{k}\left(x_{1}, x_{2}, \ldots, x_{n+1}\right)Nk(x1,x2,…,xn+1)is given by the formula
(19) N k ( x 1 , x 2 , … , x n + 1 ) = α 1 n − k , k (19) N k x 1 , x 2 , … , x n + 1 = α 1 n − k , k {:(19)N_(k)(x_(1),x_(2),dots,x_(n+1))=alpha_(1)^(n-k,k):}\begin{equation*} N_{k}\left(x_{1}, x_{2}, \ldots, x_{n+1}\right)=\alpha_{1}^{n-k, k} \tag{19} \end{equation*}(19)Nk(x1,x2,…,xn+1)=α1n−k,k
where the numbers α i j , i ℏ α i j , i ℏ alpha_(i)^(j,iℏ)\alpha_{i}^{j, i \hbar}αandj,andℏcan be calculated using the recurrence formulas
(20) α i j , k = α i + 1 j − 1 , k + α i j − 1 , k x i + j + k − x i , ( α i 0 , k = 1 ) i = 1 , 2 , … , n + 1 − k − j , j = 1 , 2 , … , n + 1 − k (20) α i j , k = α i + 1 j − 1 , k + α i j − 1 , k x i + j + k − x i , α i 0 , k = 1 i = 1 , 2 , … , n + 1 − k − j , j = 1 , 2 , … , n + 1 − k {:[(20)alpha_(i)^(j,k)=(alpha_(i+1)^(j-1,k)+alpha_(i)^(j-1,k))/(x_(i+j+k)-x_(i))","quad(alpha_(i)^(0,k)=1)],[i=1","2","dots","n+1-k-j","j=1","2","dots","n+1-k]:}\begin{gather*} \alpha_{i}^{j, k}=\frac{\alpha_{i+1}^{j-1, k}+\alpha_{i}^{j-1, k}}{x_{i+j+k}-x_{i}}, \quad\left(\alpha_{i}^{0, k}=1\right) \tag{20}\\ i=1,2, \ldots, n+1-k-j, j=1,2, \ldots, n+1-k \end{gather*}(20)αandj,k=αand+1j−1,k+αandj−1,kxand+j+k−xand,(αand0,k=1)and=1,2,…,n+1−k−j,j=1,2,…,n+1−k
The recurrence formula (20) also shows us that, in case (18), we have
(21) N k ( x 1 , x 2 , … , x i + k + 1 ) = N k ( x 1 , x 2 , … , x j + k ) + N k ( x 2 , x 3 , … , x j + k + 1 ) x j + k + 1 − x 1 (21) N k x 1 , x 2 , … , x i + k + 1 = N k x 1 , x 2 , … , x j + k + N k x 2 , x 3 , … , x j + k + 1 x j + k + 1 − x 1 {:(21)N_(k)(x_(1),x_(2),dots,x_(i+k+1))=(N_(k)(x_(1),x_(2),dots,x_(j+k))+N_(k)(x_(2),x_(3),dots,x_(j+k+1)))/(x_(j+k+1)-x_(1)):}\begin{equation*} N_{k}\left(x_{1}, x_{2}, \ldots, x_{i+k+1}\right)=\frac{N_{k}\left(x_{1}, x_{2}, \ldots, x_{j+k}\right)+N_{k}\left(x_{2}, x_{3}, \ldots, x_{j+k+1}\right)}{x_{j+k+1}-x_{1}} \tag{21} \end{equation*}(21)Nk(x1,x2,…,xand+k+1)=Nk(x1,x2,…,xj+k)+Nk(x2,x3,…,xj+k+1)xj+k+1−x1
Thus, using formulas (16), (17), (21) we deduce, in particular,
N 0 ( x 1 , x 2 ) = 2 x 2 − x 1 N 0 ( x 1 , x 2 , x 3 ) = 2 ( x 2 − x 1 ) ( x 3 − x 2 ) , N 1 ( x 1 , x 2 , x 3 ) = 2 x 3 − x 1 N 0 ( x 1 , x 2 , x 3 , x 4 ) = 2 ( x 4 + x 2 − x 1 − x 3 ) ( x 2 − x 1 ) ( x 3 − x 2 ) ( x 4 − x 3 ) ( x 4 − x 1 ) N 1 ( x 1 , x 2 , x 3 , x 4 ) = 2 ( x 4 + x 3 − x 1 − x 2 ) ( x 3 − x 1 ) ( x 4 − x 2 ) ( x 4 − x 1 ) , N 2 ( x 1 , x 2 , x 3 , x 4 ) = 2 x 4 − x 1 N 0 x 1 , x 2 = 2 x 2 − x 1 N 0 x 1 , x 2 , x 3 = 2 x 2 − x 1 x 3 − x 2 , N 1 x 1 , x 2 , x 3 = 2 x 3 − x 1 N 0 x 1 , x 2 , x 3 , x 4 = 2 x 4 + x 2 − x 1 − x 3 x 2 − x 1 x 3 − x 2 x 4 − x 3 x 4 − x 1 N 1 x 1 , x 2 , x 3 , x 4 = 2 x 4 + x 3 − x 1 − x 2 x 3 − x 1 x 4 − x 2 x 4 − x 1 , N 2 x 1 , x 2 , x 3 , x 4 = 2 x 4 − x 1 {:[N_(0)(x_(1),x_(2))=(2)/(x_(2)-x_(1))],[N_(0)(x_(1),x_(2),x_(3))=(2)/((x_(2)-x_(1))(x_(3)-x_(2)))","N_(1)(x_(1),x_(2),x_(3))=(2)/(x_(3)-x_(1))],[N_(0)(x_(1),x_(2),x_(3),x_(4))=(2(x_(4)+x_(2)-x_(1)-x_(3)))/((x_(2)-x_(1))(x_(3)-x_(2))(x_(4)-x_(3))(x_(4)-x_(1)))],[N_(1)(x_(1),x_(2),x_(3),x_(4))=(2(x_(4)+x_(3)-x_(1)-x_(2)))/((x_(3)-x_(1))(x_(4)-x_(2))(x_(4)-x_(1)))","N_(2)(x_(1),x_(2),x_(3),x_(4))=(2)/(x_(4)-x_(1))]:}\begin{gathered} N_{0}\left(x_{1}, x_{2}\right)=\frac{2}{x_{2}-x_{1}} \\ N_{0}\left(x_{1}, x_{2}, x_{3}\right)=\frac{2}{\left(x_{2}-x_{1}\right)\left(x_{3}-x_{2}\right)}, N_{1}\left(x_{1}, x_{2}, x_{3}\right)=\frac{2}{x_{3}-x_{1}} \\ N_{0}\left(x_{1}, x_{2}, x_{3}, x_{4}\right)=\frac{2\left(x_{4}+x_{2}-x_{1}-x_{3}\right)}{\left(x_{2}-x_{1}\right)\left(x_{3}-x_{2}\right)\left(x_{4}-x_{3}\right)\left(x_{4}-x_{1}\right)} \\ N_{1}\left(x_{1}, x_{2}, x_{3}, x_{4}\right)=\frac{2\left(x_{4}+x_{3}-x_{1}-x_{2}\right)}{\left(x_{3}-x_{1}\right)\left(x_{4}-x_{2}\right)\left(x_{4}-x_{1}\right)}, N_{2}\left(x_{1}, x_{2}, x_{3}, x_{4}\right)=\frac{2}{x_{4}-x_{1}} \end{gathered}N0(x1,x2)=2x2−x1N0(x1,x2,x3)=2(x2−x1)(x3−x2),N1(x1,x2,x3)=2x3−x1N0(x1,x2,x3,x4)=2(x4+x2−x1−x3)(x2−x1)(x3−x2)(x4−x3)(x4−x1)N1(x1,x2,x3,x4)=2(x4+x3−x1−x2)(x3−x1)(x4−x2)(x4−x1),N2(x1,x2,x3,x4)=2x4−x1
N 0 ( x 1 , x 2 , x 3 , x 4 , x 5 ) = N 0 x 1 , x 2 , x 3 , x 4 , x 5 = N_(0)(x_(1),x_(2),x_(3),x_(4),x_(5))=N_{0}\left(x_{1}, x_{2}, x_{3}, x_{4}, x_{5}\right)=N0(x1,x2,x3,x4,x5)=
= 2 [ ( x 2 − x 1 ) ( x 3 − x 2 ) + ( x 5 − x 4 ) ( x 4 − x 3 ) + ( x 2 − x 1 ) ( x 5 − x 4 ) ] ( x 2 − x 1 ) ( x 3 − x 2 ) ( x 4 − x 3 ) ( x 5 − x 4 ) ( x 4 − x 1 ) ( x 5 − x 2 ) = N 1 ( x 1 : x 2 , x 3 , x 4 , x 5 ) = 2 [ ( x 4 − x 1 ) ( x 5 − x 2 ) ( x 5 − x 1 ) + ( x 3 − x 1 ) ( x 4 − x 3 ) ( x 4 − x 4 ) + ( x 5 − x 2 ) ( x 3 − x 2 ) ( x 5 − x 3 ) ] ( x 2 − x 1 ) ( x 4 − x 2 ) ( x 5 − x 3 ) ( x 4 − x 1 ) ( x 5 − x 2 ) ( x 5 − x 1 ) N 2 ( x 1 , x 2 , x 3 , x 4 , x 5 ) = 2 ( x 5 + x 4 − x 1 − x 2 ) ( x 4 − x 1 ) ( x 5 − x 2 ) ( x 5 − x 1 ) N 3 ( x 1 , x 2 , x 3 , x 4 , x 5 ) = 2 x 5 − x 1 = 2 x 2 − x 1 x 3 − x 2 + x 5 − x 4 x 4 − x 3 + x 2 − x 1 x 5 − x 4 x 2 − x 1 x 3 − x 2 x 4 − x 3 x 5 − x 4 x 4 − x 1 x 5 − x 2 = N 1 x 1 : x 2 , x 3 , x 4 , x 5 = 2 x 4 − x 1 x 5 − x 2 x 5 − x 1 + x 3 − x 1 x 4 − x 3 x 4 − x 4 + x 5 − x 2 x 3 − x 2 x 5 − x 3 x 2 − x 1 x 4 − x 2 x 5 − x 3 x 4 − x 1 x 5 − x 2 x 5 − x 1 N 2 x 1 , x 2 , x 3 , x 4 , x 5 = 2 x 5 + x 4 − x 1 − x 2 x 4 − x 1 x 5 − x 2 x 5 − x 1 N 3 x 1 , x 2 , x 3 , x 4 , x 5 = 2 x 5 − x 1 {:[=(2[(x_(2)-x_(1))(x_(3)-x_(2))+(x_(5)-x_(4))(x_(4)-x_(3))+(x_(2)-x_(1))(x_(5)-x_(4))])/((x_(2)-x_(1))(x_(3)-x_(2))(x_(4)-x_(3))(x_(5)-x_(4))(x_(4)-x_(1))(x_(5)-x_(2)))],[=(N_(1)(x_(1):x_(2),x_(3),x_(4),x_(5))=)/(2[(x_(4)-x_(1))(x_(5)-x_(2))(x_(5)-x_(1))+(x_(3)-x_(1))(x_(4)-x_(3))(x_(4)-x_(4))+(x_(5)-x_(2))(x_(3)-x_(2))(x_(5)-x_(3))])],[(x_(2)-x_(1))(x_(4)-x_(2))(x_(5)-x_(3))(x_(4)-x_(1))(x_(5)-x_(2))(x_(5)-x_(1))],[N_(2)(x_(1),x_(2),x_(3),x_(4),x_(5))=(2(x_(5)+x_(4)-x_(1)-x_(2)))/((x_(4)-x_(1))(x_(5)-x_(2))(x_(5)-x_(1)))],[N_(3)(x_(1),x_(2),x_(3),x_(4),x_(5))=(2)/(x_(5)-x_(1))]:}\begin{gathered} =\frac{2\left[\left(x_{2}-x_{1}\right)\left(x_{3}-x_{2}\right)+\left(x_{5}-x_{4}\right)\left(x_{4}-x_{3}\right)+\left(x_{2}-x_{1}\right)\left(x_{5}-x_{4}\right)\right]}{\left(x_{2}-x_{1}\right)\left(x_{3}-x_{2}\right)\left(x_{4}-x_{3}\right)\left(x_{5}-x_{4}\right)\left(x_{4}-x_{1}\right)\left(x_{5}-x_{2}\right)} \\ =\frac{N_{1}\left(x_{1}: x_{2}, x_{3}, x_{4}, x_{5}\right)=}{2\left[\left(x_{4}-x_{1}\right)\left(x_{5}-x_{2}\right)\left(x_{5}-x_{1}\right)+\left(x_{3}-x_{1}\right)\left(x_{4}-x_{3}\right)\left(x_{4}-x_{4}\right)+\left(x_{5}-x_{2}\right)\left(x_{3}-x_{2}\right)\left(x_{5}-x_{3}\right)\right]} \\ \left(x_{2}-x_{1}\right)\left(x_{4}-x_{2}\right)\left(x_{5}-x_{3}\right)\left(x_{4}-x_{1}\right)\left(x_{5}-x_{2}\right)\left(x_{5}-x_{1}\right) \\ N_{2}\left(x_{1}, x_{2}, x_{3}, x_{4}, x_{5}\right)=\frac{2\left(x_{5}+x_{4}-x_{1}-x_{2}\right)}{\left(x_{4}-x_{1}\right)\left(x_{5}-x_{2}\right)\left(x_{5}-x_{1}\right)} \\ N_{3}\left(x_{1}, x_{2}, x_{3}, x_{4}, x_{5}\right)=\frac{2}{x_{5}-x_{1}} \end{gathered}=2[(x2−x1)(x3−x2)+(x5−x4)(x4−x3)+(x2−x1)(x5−x4)](x2−x1)(x3−x2)(x4−x3)(x5−x4)(x4−x1)(x5−x2)=N1(x1:x2,x3,x4,x5)=2[(x4−x1)(x5−x2)(x5−x1)+(x3−x1)(x4−x3)(x4−x4)+(x5−x2)(x3−x2)(x5−x3)](x2−x1)(x4−x2)(x5−x3)(x4−x1)(x5−x2)(x5−x1)N2(x1,x2,x3,x4,x5)=2(x5+x4−x1−x2)(x4−x1)(x5−x2)(x5−x1)N3(x1,x2,x3,x4,x5)=2x5−x1
It is now easy to see how one can delimit the terms of the series (10) with the help of the aforementioned results. We have
| D i j , k [ f ] | ≦ N k ( x i , x i + 1 , … , x i + j + k ) M D i j , k [ f ] ≦ N k x i , x i + 1 , … , x i + j + k M |D_(i)^(j,k)[f]| <= N_(k)(x_(i),x_(i+1),dots,x_(i+j+k))M\left|D_{i}^{j, k}[f]\right| \leqq N_{k}\left(x_{i}, x_{i+1}, \ldots, x_{i+j+k}\right) M|Dandj,k[f]|≦Nk(xand,xand+1,…,xand+j+k)M
where M = max r = i , i + 1 , … , i + j ( | f r | ) M = max r = i , i + 1 , … , i + j   f r M=max_(r=i,i+1,dots,i+j)(|f_(r)|)M=\max _{r=i, i+1, \ldots, i+j}\left(\left|f_{r}\right|\right)M=MAXR=and,and+1,…,and+j(|fR|)
6. Let's return to the delimitation of the corcetia λ λ lambda\lambdaλfrom formula (7). Formula (5) can also be written
as
D i 1 , j − 1 [ D ~ j − 1 ] = D ~ i j + c i ( j ) D i 1 , j − 1 D ~ j − 1 = D ~ i j + c i ( j ) D_(i)^(1,j-1)[ widetilde(D)^(j-1)]= widetilde(D)_(i)^(j)+c_(i)^((j))D_{i}^{1, j-1}\left[\widetilde{D}^{j-1}\right]=\widetilde{D}_{i}^{j}+c_{i}^{(j)}Dand1,j−1[D~j−1]=D~andj+cand(j)
from which we deduce and
D i 1 , j − r − 1 [ D ~ j − r − 1 ] = D ~ i j − r + c i ( j − r ) , 0 ≦ r ≦ j − 1 D i 1 , j − r − 1 D ~ j − r − 1 = D ~ i j − r + c i ( j − r ) , 0 ≦ r ≦ j − 1 D_(i)^(1,j-r-1)[ widetilde(D)^(j-r-1)]= widetilde(D)_(i)^(j-r)+c_(i)^((j-r)),0 <= r <= j-1D_{i}^{1, j-r-1}\left[\widetilde{D}^{j-r-1}\right]=\widetilde{D}_{i}^{j-r}+c_{i}^{(j-r)}, 0 \leqq r \leqq j-1Dand1,j−R−1[D~j−R−1]=D~andj−R+cand(j−R),0≦R≦j−1
From this it follows that
D i r , j − r [ D j , j − r − 1 [ D ~ j − r − 1 ] ] = D i r , j − r [ D ~ j − r + c ( j − r ) ] = D i r , j − r [ D ~ j − r ] + D i r , j − r [ c ( j − r ) ] . D i r , j − r D j , j − r − 1 D ~ j − r − 1 = D i r , j − r D ~ j − r + c ( j − r ) = D i r , j − r D ~ j − r + D i r , j − r c ( j − r ) . {:[D_(i)^(r,j-r)[D^(j,j-r-1)[ widetilde(D)^(j-r-1)]]=D_(i)^(r,j-r)[ widetilde(D)^(j-r)+c^((j-r))]=],[D_(i)^(r,j-r)[ widetilde(D)^(j-r)]+D_(i)^(r,j-r)[c^((j-r))].]:}\begin{gathered} D_{i}^{r, j-r}\left[D^{j, j-r-1}\left[\widetilde{D}^{j-r-1}\right]\right]=D_{i}^{r, j-r}\left[\widetilde{D}^{j-r}+c^{(j-r)}\right]= \\ D_{i}^{r, j-r}\left[\widetilde{D}^{j-r}\right]+D_{i}^{r, j-r}\left[c^{(j-r)}\right] . \end{gathered}DandR,j−R[Dj,j−R−1[D~j−R−1]]=DandR,j−R[D~j−R+c(j−R)]=DandR,j−R[D~j−R]+DandR,j−R[c(j−R)].
But, based on formula (13),
D i r , j − r [ D 1 , j − r − 1 [ D ~ j − r − 1 ] ] = D i r + 1 , j − r − 1 [ D ~ j − r − 1 ] D i r , j − r D 1 , j − r − 1 D ~ j − r − 1 = D i r + 1 , j − r − 1 D ~ j − r − 1 D_(i)^(r,j-r)[D^(1,j-r-1)[ widetilde(D)^(j-r-1)]]=D_(i)^(r+1,j-r-1)[ widetilde(D)^(j-r-1)]D_{i}^{r, j-r}\left[D^{1, j-r-1}\left[\widetilde{D}^{j-r-1}\right]\right]=D_{i}^{r+1, j-r-1}\left[\widetilde{D}^{j-r-1}\right]DandR,j−R[D1,j−R−1[D~j−R−1]]=DandR+1,j−R−1[D~j−R−1]
and we have, therefore,
D i r + 1 : j − r − 1 [ D ~ j − r − 1 ] = D i r , j − r [ D ~ j − r ] + D i r , j − r [ c ( j − r ) ] , r = 0 , 1 , … , j − 1 . D i r + 1 : j − r − 1 D ~ j − r − 1 = D i r , j − r D ~ j − r + D i r , j − r c ( j − r ) , r = 0 , 1 , … , j − 1 . D_(i)^(r+1:j-r-1)[ widetilde(D)^(j-r-1)]=D_(i)^(r,j-r)[ widetilde(D)^(j-r)]+D_(i)^(r,j-r)[c^((j-r))],r=0,1,dots,j-1.D_{i}^{r+1: j-r-1}\left[\widetilde{D}^{j-r-1}\right]=D_{i}^{r, j-r}\left[\widetilde{D}^{j-r}\right]+D_{i}^{r, j-r}\left[c^{(j-r)}\right], r=0,1, \ldots, j-1 .DandR+1:j−R−1[D~j−R−1]=DandR,j−R[D~j−R]+DandR,j−R[c(j−R)],R=0,1,…,j−1.
Adding these equalities member by member, we have
D i j , 0 [ D ~ 0 ] = D i 0 , j [ D ~ j ] + ∑ r = 0 i − 1 D i r , j − r [ c ( j − k ) ] . D i j , 0 D ~ 0 = D i 0 , j D ~ j + ∑ r = 0 i − 1   D i r , j − r c ( j − k ) . D_(i)^(j,0)[ widetilde(D)^(0)]=D_(i)^(0,j)[ widetilde(D)^(j)]+sum_(r=0)^(i-1)D_(i)^(r,j-r)[c^((j-k))].D_{i}^{j, 0}\left[\widetilde{D}^{0}\right]=D_{i}^{0, j}\left[\widetilde{D}^{j}\right]+\sum_{r=0}^{i-1} D_{i}^{r, j-r}\left[c^{(j-k)}\right] .Dandj,0[D~0]=Dand0,j[D~j]+∑R=0and−1DandR,j−R[c(j−k)].
But we also have
D i j , 0 [ D ~ 0 ] = D i j , 0 [ f ] − D i j , 0 [ c ( 0 ) ] = D i j [ f ] − D i j , 0 [ c ( 0 ) ] , D i 0 , j [ D ~ j ] = D ~ i i D i j , 0 D ~ 0 = D i j , 0 [ f ] − D i j , 0 c ( 0 ) = D i j [ f ] − D i j , 0 c ( 0 ) , D i 0 , j D ~ j = D ~ i i D_(i)^(j,0)[ widetilde(D)^(0)]=D_(i)^(j,0)[f]-D_(i)^(j,0)[c^((0))]=D_(i)^(j)[f]-D_(i)^(j,0)[c^((0))],D_(i)^(0,j)[ widetilde(D)^(j)]= widetilde(D)_(i)^(i)D_{i}^{j, 0}\left[\widetilde{D}^{0}\right]=D_{i}^{j, 0}[f]-D_{i}^{j, 0}\left[c^{(0)}\right]=D_{i}^{j}[f]-D_{i}^{j, 0}\left[c^{(0)}\right], D_{i}^{0, j}\left[\widetilde{D}^{j}\right]=\widetilde{D}_{i}^{i}Dandj,0[D~0]=Dandj,0[f]−Dandj,0[c(0)]=Dandj[f]−Dandj,0[c(0)],Dand0,j[D~j]=D~andand
so we derive the formula
D i j [ f ] = D i j = D ~ i j + ∑ r = 0 j D i r , i − r [ c ( j − r ) ] D i j [ f ] = D i j = D ~ i j + ∑ r = 0 j   D i r , i − r c ( j − r ) D_(i)^(j)[f]=D_(i)^(j)= widetilde(D)_(i)^(j)+sum_(r=0)^(j)D_(i)^(r,i-r)[c^((j-r))]D_{i}^{j}[f]=D_{i}^{j}=\widetilde{D}_{i}^{j}+\sum_{r=0}^{j} D_{i}^{r, i-r}\left[c^{(j-r)}\right]Dandj[f]=Dandj=D~andj+∑R=0jDandR,and−R[c(j−R)]
Taking into account this formula, from (6), (7) we deduce
(22) λ = ∑ i = 0 n ( x 0 − x 1 ) ( x 0 − x 2 ) … ( x 0 − x i ) [ ∑ r = 0 i D 1 r , i − r [ c ( i − r ) ] ] (22) λ = ∑ i = 0 n   x 0 − x 1 x 0 − x 2 … x 0 − x i ∑ r = 0 i   D 1 r , i − r c ( i − r ) {:(22)lambda=sum_(i=0)^(n)(x_(0)-x_(1))(x_(0)-x_(2))dots(x_(0)-x_(i))[sum_(r=0)^(i)D_(1)^(r,i-r)[c^((i-r))]]:}\begin{equation*} \lambda=\sum_{i=0}^{n}\left(x_{0}-x_{1}\right)\left(x_{0}-x_{2}\right) \ldots\left(x_{0}-x_{i}\right)\left[\sum_{r=0}^{i} D_{1}^{r, i-r}\left[c^{(i-r)}\right]\right] \tag{22} \end{equation*}(22)λ=∑and=0n(x0−x1)(x0−x2)…(x0−xand)[∑R=0andD1R,and−R[c(and−R)]]
In particular, if all corrections remain, in absolute value, at most equal to ε ε epsi\varepsilonε, based on formula (15) we have
and we can write
where
(23) V ( x ) = ∑ i = − 0 n | ( x − x 1 ) ( x − x 2 ) … ( x − x i ) | [ ∑ r = 0 i N i − r ( x 1 , x 2 , … , x i + 1 ) ] . (23) V ( x ) = ∑ i = − 0 n   x − x 1 x − x 2 … x − x i ∑ r = 0 i   N i − r x 1 , x 2 , … , x i + 1 . {:(23)V(x)=sum_(i=-0)^(n)|(x-x_(1))(x-x_(2))dots(x-x_(i))|[sum_(r=0)^(i)N_(i-r)(x_(1),x_(2),dots,x_(i+1))].:}\begin{equation*} V(x)=\sum_{i=-0}^{n}\left|\left(x-x_{1}\right)\left(x-x_{2}\right) \ldots\left(x-x_{i}\right)\right|\left[\sum_{r=0}^{i} N_{i-r}\left(x_{1}, x_{2}, \ldots, x_{i+1}\right)\right] . \tag{23} \end{equation*}(23)V(x)=∑and=−0n|(x−x1)(x−x2)…(x−xand)|[∑R=0andNand−R(x1,x2,…,xand+1)].
When the function values ​​are exact, that is, when c i ( j ) = 0 , i = 1 , 2 , … , n + 1 c i ( j ) = 0 , i = 1 , 2 , … , n + 1 c_(i)^((j))=0,i=1,2,dots,n+1c_{i}^{(j)}=0, i=1,2, \ldots, n+1cand(j)=0,and=1,2,…,n+1, it can even be taken
(25) V ( x ) = ∑ i = 1 n | ( x − x 1 ) ( x − x 2 ) … ( x − x i ) | [ ∑ r = 0 i − 1 N i − r ( x 1 , x 2 , … , x i + 1 ) ] (25) V ( x ) = ∑ i = 1 n   x − x 1 x − x 2 … x − x i ∑ r = 0 i − 1   N i − r x 1 , x 2 , … , x i + 1 {:(25)V(x)=sum_(i=1)^(n)|(x-x_(1))(x-x_(2))dots(x-x_(i))|[sum_(r=0)^(i-1)N_(i-r)(x_(1),x_(2),dots,x_(i+1))]:}\begin{equation*} V(x)=\sum_{i=1}^{n}\left|\left(x-x_{1}\right)\left(x-x_{2}\right) \ldots\left(x-x_{i}\right)\right|\left[\sum_{r=0}^{i-1} N_{i-r}\left(x_{1}, x_{2}, \ldots, x_{i+1}\right)\right] \tag{25} \end{equation*}(25)V(x)=∑and=1n|(x−x1)(x−x2)…(x−xand)|[∑R=0and−1Nand−R(x1,x2,…,xand+1)]
  1. We will conclude these considerations with a numerical example. Let the function f ( x ) f ( x ) f(x)f(x)f(x)on the nodes x 1 = 14 , x 2 = 17 , x 3 = 31 , x 4 = 35 x 1 = 14 , x 2 = 17 , x 3 = 31 , x 4 = 35 x_(1)=14,x_(2)=17,x_(3)=31,x_(4)=35x_{1}=14, x_{2}=17, x_{3}=31, x_{4}=35x1=14,x2=17,x3=31,x4=35, given with the exact values:
x 1 / 4 17 31 35 f ( x ) . 68 , 7 64 , 0 44 , 0 39 , 1 . . x 1 / 4 17 31 35 f ( x ) . 68 , 7 64 , 0 44 , 0 39 , 1 . . {:[x,1//4,17,31,35],[f(x).,68","7,64","0,44","0,39","1.]:}.\begin{array}{c|cccc} x & 1 / 4 & 17 & 31 & 35 \\ \hline f(x) . & 68,7 & 64,0 & 44,0 & 39,1 . \end{array} .x1/4173135f(x).68,764,044,039,1..
We have here n = 3 n = 3 n=3n=3n=3and we are in case (18) by the convenient choice of notations.
The previous formulas give us, in this case,
N 1 ( x 1 , x 2 ) = 1 N 1 x 1 , x 2 = 1 N_(1)(x_(1),x_(2))=1N_{1}\left(x_{1}, x_{2}\right)=1N1(x1,x2)=1
N 2 ( x 1 , x 2 , x 3 ) + N 1 ( x 1 , x 2 , x 3 ) = 1 + 2 x 3 − x 2 = 1 + 2 17 < 1 , 12 N 2 x 1 , x 2 , x 3 + N 1 x 1 , x 2 , x 3 = 1 + 2 x 3 − x 2 = 1 + 2 17 < 1 , 12 N_(2)(x_(1),x_(2),x_(3))+N_(1)(x_(1),x_(2),x_(3))=1+(2)/(x_(3)-x_(2))=1+(2)/(17) < 1,12N_{2}\left(x_{1}, x_{2}, x_{3}\right)+N_{1}\left(x_{1}, x_{2}, x_{3}\right)=1+\frac{2}{x_{3}-x_{2}}=1+\frac{2}{17}<1,12N2(x1,x2,x3)+N1(x1,x2,x3)=1+2x3−x2=1+217<1,12
N 3 ( x 1 , x 2 , x 3 , x 4 ) + N 2 ( x 1 , x 2 , x 3 , x 4 ) + N 1 ( x 1 , x 2 , x 3 , x 4 ) = N 3 x 1 , x 2 , x 3 , x 4 + N 2 x 1 , x 2 , x 3 , x 4 + N 1 x 1 , x 2 , x 3 , x 4 = N_(3)(x_(1),x_(2),x_(3),x_(4))+N_(2)(x_(1),x_(2),x_(3),x_(4))+N_(1)(x_(1),x_(2),x_(3),x_(4))=N_{3}\left(x_{1}, x_{2}, x_{3}, x_{4}\right)+N_{2}\left(x_{1}, x_{2}, x_{3}, x_{4}\right)+N_{1}\left(x_{1}, x_{2}, x_{3}, x_{4}\right)=N3(x1,x2,x3,x4)+N2(x1,x2,x3,x4)+N1(x1,x2,x3,x4)=
= 1 + 2 x 4 − x 1 + 2 ( x 4 + x 3 − x 1 − x 2 ) ( x 3 − x 1 ) ( x 4 − x 2 ) ( x 4 − x 1 ) = 1 + 2 21 + 5 459 < 1 , 11 . = 1 + 2 x 4 − x 1 + 2 x 4 + x 3 − x 1 − x 2 x 3 − x 1 x 4 − x 2 x 4 − x 1 = 1 + 2 21 + 5 459 < 1 , 11 . =1+(2)/(x_(4)-x_(1))+(2(x_(4)+x_(3)-x_(1)-x_(2)))/((x_(3)-x_(1))(x_(4)-x_(2))(x_(4)-x_(1)))=1+(2)/(21)+(5)/(459) < 1,11.=1+\frac{2}{x_{4}-x_{1}}+\frac{2\left(x_{4}+x_{3}-x_{1}-x_{2}\right)}{\left(x_{3}-x_{1}\right)\left(x_{4}-x_{2}\right)\left(x_{4}-x_{1}\right)}=1+\frac{2}{21}+\frac{5}{459}<1,11 .=1+2x4−x1+2(x4+x3−x1−x2)(x3−x1)(x4−x2)(x4−x1)=1+221+5459<1,11.
We therefore have, interpolating at the point x 0 = 27 x 0 = 27 x_(0)=27x_{0}=27x0=27,
V ( x 0 ) < 13 + 13 × 10 × 1 , 12 + 13 × 10 × 4 × 1 , 11 < 736 . V x 0 < 13 + 13 × 10 × 1 , 12 + 13 × 10 × 4 × 1 , 11 < 736 . V(x_(0)) < 13+13 xx10 xx1,12+13 xx10 xx4xx1,11 < 736.V\left(x_{0}\right)<13+13 \times 10 \times 1,12+13 \times 10 \times 4 \times 1,11<736 .V(x0)<13+13×10×1,12+13×10×4×1,11<736.
If, in order to form table no. 2, we calculate the differences divided abbreviated to k k kkkdecimals, we will have
| λ | < 736 2 ⋅ 10 k = 368 10 k | λ | < 736 2 ⋅ 10 k = 368 10 k |lambda| < (736)/(2*10^(k))=(368)/(10^(k))|\lambda|<\frac{736}{2 \cdot 10^{k}}=\frac{368}{10^{k}}|λ|<7362⋅10k=36810k
In order to obtain at least one exact decimal in the value of polynomial (2), we must have at least 368 ⋅ 10 − k < 0 , 01 368 ⋅ 10 − k < 0 , 01 368*10^(-k) < 0,01368 \cdot 10^{-k}<0,01368⋅10−k<0,01, so at least k = 5 k = 5 k=5k=5k=5.
TAKING k = 5 k = 5 k=5k=5k=5, with the data from table no. 2, the data from table no. 3 are obtained.
Painting No. 3
We then have
L ~ = 68 , 7 − 13 × 1 , 5667 + 130 × 0 , 00812 − 520 × 0 , 00015 = 49 , 31089 L ~ = 68 , 7 − 13 × 1 , 5667 + 130 × 0 , 00812 − 520 × 0 , 00015 = 49 , 31089 widetilde(L)=68,7-13 xx1,5667+130 xx0,00812-520 xx0,00015=49,31089\widetilde{L}=68,7-13 \times 1,5667+130 \times 0,00812-520 \times 0,00015=49,31089IT~=68,7−13×1,5667+130×0,00812−520×0,00015=49,31089
and | λ | < 0 , 00368 | λ | < 0 , 00368 |lambda| < 0,00368|\lambda|<0,00368|λ|<0,00368,
so
49 , 37021 < L ( 14 , 17 , 31 , 35 ; | | 27 ) < 49 , 31457 . 49 , 37021 < L ( 14 , 17 , 31 , 35 ; | | 27 ) < 49 , 31457 . 49,37021 < L(14,17,31,35;quad|quad|27) < 49,31457.49,37021<L(14,17,31,35 ; \quad|\quad| 27)<49,31457 .49,37021<IT(14,17,31,35;||27)<49,31457.
In this case, the polynomial (2) is obtained with three exact decimals, which is sufficient for the data of the problem.
Mathematics Section of the Cluj Branch of the RPR Academy

О ТОЧНОСТИ ЧИСЛЕННЫ РАСЧЕТОВ ПРИ ПОЛИНОЛЯЦИИ ПОЛИНОМАМИ

(BRIEF CONTENT)
To calculate the approximate value of the function f ( x ) f ( x ) f(x)f(x)f(x)at the point x 0 x 0 x_(0)x_{0}x0using formula (1), in which the second term is an interpolation Newton polynomial of the form (2) for the case of knots x i , i = 1 , 2 , … , n + 1 x i , i = 1 , 2 , … , n + 1 x_(i),i=1,2,dots,n+1x_{i}, i=1,2, \ldots, n+1xand,and=1,2,…,n+1, not necessarily equal, it is necessary to first compile a table of 1 separated differences. When compiling this table, it is necessary to sequentially calculate the values ​​of the columns, and the errors are introduced, affecting the calculation of the values ​​of Newton's polynomial. We denote by D ~ i j D ~ i j widetilde(D)_(i)^(j)\widetilde{D}_{i}^{j}D~andjcalculated approximations of elements D i j D i j D_(i)^(j)D_{i}^{j}Dandjtables of separated differences, given by formula (3), and through c i ( j ) c i ( j ) c_(i)^((j))c_{i}^{(j)}cand(j)), corresponding amendments; correction of the calculated scaled value of Newton's polynomial (2) dan
formula (22), in which expression D i i , le [ / ] D i i ,  le  [ / ] D_(i)^(i," le ")[//]D_{i}^{i, \text { le }}[/]Dandand, they [/], referring to knots (8) and sequences (9) in accordance with these knots, given by formulas (11).
If we have | C i ( j ) | ≦ ε C i ( j ) ≦ ε |C_(i)^((j))| <= epsi\left|C_{i}^{(j)}\right| \leqq \varepsilon|Cand(j)|≦εдля всех проровок десендных равностей, то из оценка (1.5) выводети оценка (23) для λ λ lambda\lambdaλ. At the same time N k ( x 1 , x 2 , … , x n + 1 ) N k x 1 , x 2 , … , x n + 1 N_(k)(x_(1),x_(2),dots,x_(n+1))N_{k}\left(x_{1}, x_{2}, \ldots, x_{n+1}\right)Nk(x1,x2,…,xn+1)размещение вечество выражениеми, depending only on nodes, а V ( x ) V ( x ) V(x)V(x)V(x)given by formula (24) or, if the function values ​​do not contain errors, by formula (25).
Finally, a numerical example is given.

SUR LA PRECISION DU CALCUL NUMÉRIQUE DANS L'INTERPOLATION PAR DES POLYNOMES

(SUMMARY)

Pour calculer une valeur approximative sur le point x x xxx, from the function / ( x ) / ( x ) //(x)/(x)/(x), à l'aide de la formulae (1), où le second member est le polynôme d'interpolation sous la forme (2) de Newton, il faut tout d'abord construire le tableau 1 des différences divisees. Les knots x i , i = 1 , 2 , … , n + 1 x i , i = 1 , 2 , … , n + 1 x_(i),i=1,2,dots,n+1x_{i}, i=1,2, \ldots, n+1xand,and=1,2,…,n+1ne sont pas nécessairement equidistants. Dans le calcul des éléments des colonnes successivees du tableau des différences divisees, on commet des erreurs qui se se transmettent au calcul des valeurs du polynôme de Newton. En désignant par D ~ i j D ~ i j widetilde(D)_(i)^(j)\widetilde{D}_{i}^{j}D~andjles valeurs approximatives calculées des éléments D i j D i j D_(i)^(j)D_{i}^{j}Dandjdu tableau des différences divisees, donnés par les formules (3) et par c i ( j ) c i ( j ) c_(i)^((j))c_{i}^{(j)}cand(j)les corrections respective, la correction λ λ lambda\lambdaλfrom the approximate value calculated from the valeur du polynôme (2) de Newton est donnée par la formula (22), où les expressions D i j , k [ f ] D i j , k [ f ] D_(i)^(j,k)[f]D_{i}^{j, k}[f]Dandj,k[f], relative to nodes (8) et à la suite (9) des valeurs sur ces noeuds, sont données par les formulas (11).
If we have | c i ( j ) | ≦ ε c i ( j ) ≦ ε |c_(i)^((j))| <= epsi\left|c_{i}^{(j)}\right| \leqq \varepsilon|cand(j)|≦ε, pour toutes les corrections des différences divisees, de la délimitation (15), on déduit la délimitation (23) de λ λ lambda\lambdaλ. lei N k ( x 1 , x 2 , … , x n + 1 ) N k x 1 , x 2 , … , x n + 1 N_(k)(x_(1),x_(2),dots,x_(n+1))N_{k}\left(x_{1}, x_{2}, \ldots, x_{n+1}\right)Nk(x1,x2,…,xn+1)sont des expressions ne dépendent que des noeuds et V ( x ) V ( x ) V(x)V(x)V(x)est donné par la formula (24) ou même par (25) lorsque les valeurs de la fonction ne sont pas affectés par des erreurs.
A la fin on donne une application numérique.
  1. *) For i = 0 i = 0 i=0i=0and=0the corresponding term for ham is reduced to L i 0 L i 0 L_(i)^(0)L_{i}^{0}ITand0. A similar convention applies to formulas (6), (22), (24).
1955

Related Posts