Abstract
Authors
T. Popoviciu (Institute of Numerical Analysis)
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.
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
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
'Volume VJI, no. 4, 1955
ON THE PRECISION OF NUMERICAL CALCULATION IN INTERPOLATION BY POLYNOMIALS
OF
Present communication at the meeting of June 30, 1955
- To calculate an approximate value of the functionf(x)f(x), real and the real variablexx, on the pointx_(0)x_{0}, when the values ​​were knownf(x_(i)),i=1,2,dots,n+1f\left(x_{i}\right), i=1,2, \ldots, n+1, of this function onn+1n+1(distinct) data pointsx_(i),i=1,2,dots,n+1x_{i}, i=1,2, \ldots, n+1, the interpolation formula can be used
{:(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*}
whereL(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)is the Lagrange polynomial of degreennand which takes the valuesf(x_(i))f\left(x_{i}\right)on interpolation points or nodesx_(i)x_{i}.
We will assume that the nodes are not necessarily equidistant and we will calculate the second term of formula (1) using Newton's formula,{: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))D, where the coefficientsD_(i)^(i),i=0,1,dots,nD_{i}^{i}, i=0,1, \ldots, n, are obtained from table no. 1 of divided differences in which we have, in general,
{:[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*}
using the usual notations for divided differences of the functionf(x)f(x).
The formation of table no. 1 of the divided differences is done by successively calculating the columns using the recurrence formula
The formation of table no. 1 of the divided differences is done by successively calculating the columns using the recurrence formula
{:[(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*}
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 pointx_(0)x_{0}, where interpolation is performed, are not affected by errors.
2. The columns of table no. 1. are calculated successively with certain approximations.
2. The columns of table no. 1. are calculated successively with certain approximations.
Whetherwidetilde(f)_(i),i=1,2,dots n+1\widetilde{f}_{i}, i=1,2, \ldots n+1, some approximate values ​​of the function values ​​on the nodes andc_(i)^((0)),i=1,2,dots,n+1c_{i}^{(0)}, i=1,2, \ldots, n+1, the respective corrections, sof_(i)= widetilde(f)_(i)+c_(i)^((0))f_{i}=\widetilde{f}_{i}+c_{i}^{(0)},i=1,2,dots,n+1i=1,2, \ldots, n+1. Let then, in general,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-j, approximate values ​​of the column elementsjj, calculated using the already calculated elements of the columnj-1j-1andc_(i)^((j)),i=1,2,dots,n+1-jc_{i}^{(j)}, i=1,2, \ldots, n+1-j, the respective corrections. We will then
{:(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*}
i=1,2,dots,n+1-j,j=1,2,dots,n.quadi=1,2, \ldots, n+1-j, j=1,2, \ldots, n . \quadThe
table m. 1 of the divided differences is then replaced by the table m. 2 of the calculated approximate values ​​of the divided differences.
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 valuetilde(L)\tilde{L}of expression (2) is then obtained using table no. 2 with the formula
{:(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*}
and we will have
{:(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*}
- fiiitd the respective correction.
In view of the correction delimitationlambda\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
3. Given the sequence of (distinct) nodes
{:(8)x_(1)","x_(2)","dots","x_(n+1):}\begin{equation*}
x_{1}, x_{2}, \ldots, x_{n+1} \tag{8}
\end{equation*}
any string ofn+1n+1numbers
{:(9)f_(1)","f_(2)","dots","f_(n+1):}\begin{equation*}
f_{1}, f_{2}, \ldots, f_{n+1} \tag{9}
\end{equation*}
can be considered to be formed by the valuesf_(i)=f(x_(i)),i=1,2,dots,n+1f_{i}=f\left(x_{i}\right), i=1,2, \ldots, n+1, of a functionf(a)f(a)defined on points (8). This simple observation clarifies various notations, which will follow.
Whetherkka non-negative integer< n<nand let's consider, forj=0,1,dots dots,n-kj=0,1, \ldots \ldots, n-k, the string
{:(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*}
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","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*}
whereD_(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-k. Thus, forj=0j=0the string (10) reduces to the string formed by the firstn+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 firstn+1-kn+1-kterms of the sequence (9) and, in general, the terms of the sequence (10), for ajjgiven, the terms of the series (10) for the immediately lower value of are expressed linearly and homogeneouslyjj.
Fork=0k=0, we haveD_(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-j, formulas (11) reduce to formulas (4), and the sequence (10) reduces to the set of column elements of orderjjfrom table no. 1 of the divided differences of the functionf(x)f(x)on the nodes (8).
The formula (11) that connects the strings (10) for successive values ​​ofjj, it can also be written
{:(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*}
More generally, we have the formula
{:(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*}
whererris an integer;0 <= r <= j0 \leqslant r \leqslant j.
9 - c. 1540
Indeed, it is observed that forr=0r=0andr=jr=j, formula (13) is obvious, and forr=1r=1it reduces to (12). To prove formula (13) it is therefore sufficient to show that, if it is true forr=s(s < j)r=s(s<j), it will also be true forr=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}\left[D^{j-s-1, k}[f]\right],
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}\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.
From this it immediately follows that formula (13) is true forr=s+1r=s+1Symbolically
, the property expressed by formula (13) can be written as
, the property expressed by formula (13) can be written as
D^(alpha+beta,k)=D^(alpha,beta+k)D^(beta,h).D^{\alpha+\beta, k}=D^{\alpha, \beta+k} D^{\beta, h} .
- In the following we will need a convenient delimitation of the elements of the string (9).
Divided differenceD_(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]is easily delimited, taking into account the well-known formula
[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)}
where_(i){ }_{i}
{:[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}
where
{:(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*}
andM=max_(i=1,2,dots,n+1)(|f_(i)|)M=\max _{i=1,2, \ldots, n+1}\left(\left|f_{i}\right|\right)An analogous delimitation
ofD_(1)^(n-k,k)[f]D_{1}^{n-k, k}[f]it can be written
ofD_(1)^(n-k,k)[f]D_{1}^{n-k, k}[f]it can be written
{:(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*}
where, by the way,MMcan be replaced withmax_(i=1,2,dots,n+1-k)(|//i|)\max _{i=1,2, \ldots, n+1-k}(|/ i|)In formula
(15) we have
(15) we have
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 } D
and therefore
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]
provided we choose all the numbersf_(i),i=1,2,dots,n+1-kf_{i}, i=1,2, \ldots, n+1-kequal to 1 or -1, conveniently.
we
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)
the second term being given by (1/4). Fork > 0k>0, his expressionN_(k)(x_(1),x_(2),dots,x_(n+1))N_{k}\left(x_{1}, x_{2}, \ldots, x_{n+1}\right)but it is more complicated.
In his formationL_(1)^(n-k,k)[f]L_{1}^{n-k, k}[f]only the nodes actually intervenex_(i)x_{i}fori=1,2,dots,n-k,k+2,k+3,dots,n+1i=1,2, \ldots, n-k, k+2, k+3, \ldots, n+1. So if2k <= n-12 k \leqq n-1,
all nodes will intervene. However, if2k > n-12 k>n-1only the first ones will intervenen-kn-kand the last onesn-kn-knodes (8). We deduce from this the following formula:
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)if2k > n-12 k>n-1It is enough to assumek < nk<n, because we obviously have
all nodes will intervene. However, if2k > n-12 k>n-1only the first ones will intervenen-kn-kand the last onesn-kn-knodes (8). We deduce from this the following formula:
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)if2k > n-12 k>n-1It is enough to assumek < nk<n, because we obviously have
{:(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*}
-5. In particular, suppose that
{:(18)x_(1) < x_(2) < dots < x_(n+1):}\begin{equation*}
x_{1}<x_{2}<\ldots<x_{n+1} \tag{18}
\end{equation*}
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]|]\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]
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]|]\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]
it follows that, in case (18), the numberN_(k)(x_(1),x_(2),dots,x_(n+1))N_{k}\left(x_{1}, x_{2}, \ldots, x_{n+1}\right)is given by the formula
{:(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*}
where the numbersalpha_(i)^(j,iℏ)\alpha_{i}^{j, i \hbar}can be calculated using the recurrence formulas
{:[(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*}
The recurrence formula (20) also shows us that, in case (18), we have
{:(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*}
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))]:}\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}
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)=
{:[=(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}
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),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
whereM=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)
6. Let's return to the delimitation of the corcetialambda\lambdafrom formula (7). Formula (5) can also be written
as
6. Let's return to the delimitation of the corcetialambda\lambdafrom formula (7). Formula (5) can also be written
as
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)}
from which we deduce and
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-1
From this it follows that
{:[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}
But, based on formula (13),
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]
and we have, therefore,
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 .
Adding these equalities member by member, we have
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] .
But we also have
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}
so we derive the formula
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]
Taking into account this formula, from (6), (7) we deduce
{:(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*}
In particular, if all corrections remain, in absolute value, at most equal toepsi\varepsilon, based on formula (15) we have
and we can write
where
and we can write
where
{:(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*}
When the function values ​​are exact, that is, whenc_(i)^((j))=0,i=1,2,dots,n+1c_{i}^{(j)}=0, i=1,2, \ldots, n+1, it can even be taken
{:(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*}
- We will conclude these considerations with a numerical example. Let the functionf(x)f(x)on the nodesx_(1)=14,x_(2)=17,x_(3)=31,x_(4)=35x_{1}=14, x_{2}=17, x_{3}=31, x_{4}=35, given with the exact values:
{:[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} .
We have heren=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))=1N_{1}\left(x_{1}, x_{2}\right)=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,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,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}\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)=
=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 .
We therefore have, interpolating at the pointx_(0)=27x_{0}=27,
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 .
If, in order to form table no. 2, we calculate the differences divided abbreviated tokkdecimals, we will have
|lambda| < (736)/(2*10^(k))=(368)/(10^(k))|\lambda|<\frac{736}{2 \cdot 10^{k}}=\frac{368}{10^{k}}
In order to obtain at least one exact decimal in the value of polynomial (2), we must have at least368*10^(-k) < 0,01368 \cdot 10^{-k}<0,01, so at leastk=5k=5.
TAKINGk=5k=5, with the data from table no. 2, the data from table no. 3 are obtained.
Painting No. 3
We then have
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,31089
and|lambda| < 0,00368|\lambda|<0,00368,
so
so
49,37021 < L(14,17,31,35;quad|quad|27) < 49,31457.49,37021<L(14,17,31,35 ; \quad|\quad| 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 functionf(x)f(x)at the pointx_(0)x_{0}using formula (1), in which the second term is an interpolation Newton polynomial of the form (2) for the case of knotsx_(i),i=1,2,dots,n+1x_{i}, i=1,2, \ldots, 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 bywidetilde(D)_(i)^(j)\widetilde{D}_{i}^{j}calculated approximations of elementsD_(i)^(j)D_{i}^{j}tables of separated differences, given by formula (3), and throughc_(i)^((j))c_{i}^{(j)}), corresponding amendments; correction of the calculated scaled value of Newton's polynomial (2) dan
To calculate the approximate value of the functionf(x)f(x)at the pointx_(0)x_{0}using formula (1), in which the second term is an interpolation Newton polynomial of the form (2) for the case of knotsx_(i),i=1,2,dots,n+1x_{i}, i=1,2, \ldots, 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 bywidetilde(D)_(i)^(j)\widetilde{D}_{i}^{j}calculated approximations of elementsD_(i)^(j)D_{i}^{j}tables of separated differences, given by formula (3), and throughc_(i)^((j))c_{i}^{(j)}), corresponding amendments; correction of the calculated scaled value of Newton's polynomial (2) dan
formula (22), in which expressionD_(i)^(i," le ")[//]D_{i}^{i, \text { le }}[/], referring to knots (8) and sequences (9) in accordance with these knots, given by formulas (11).
If we have|C_(i)^((j))| <= epsi\left|C_{i}^{(j)}\right| \leqq \varepsilonдля всех проровок десендных равностей, то из оценка (1.5) выводети оценка (23) дляlambda\lambda. At the same timeN_(k)(x_(1),x_(2),dots,x_(n+1))N_{k}\left(x_{1}, x_{2}, \ldots, x_{n+1}\right)размещение вечество выражениеми, depending only on nodes, а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 pointxx, from the function//(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 knotsx_(i),i=1,2,dots,n+1x_{i}, i=1,2, \ldots, 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 parwidetilde(D)_(i)^(j)\widetilde{D}_{i}^{j}les valeurs approximatives calculées des élémentsD_(i)^(j)D_{i}^{j}du tableau des différences divisees, donnés par les formules (3) et parc_(i)^((j))c_{i}^{(j)}les corrections respective, la correctionlambda\lambdafrom the approximate value calculated from the valeur du polynôme (2) de Newton est donnée par la formula (22), où les expressionsD_(i)^(j,k)[f]D_{i}^{j, 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))| <= epsi\left|c_{i}^{(j)}\right| \leqq \varepsilon, pour toutes les corrections des différences divisees, de la délimitation (15), on déduit la délimitation (23) delambda\lambda. leiN_(k)(x_(1),x_(2),dots,x_(n+1))N_{k}\left(x_{1}, x_{2}, \ldots, x_{n+1}\right)sont des expressions ne dépendent que des noeuds etV(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.
- *) Fori=0i=0the corresponding term for ham is reduced toL_(i)^(0)L_{i}^{0}. A similar convention applies to formulas (6), (22), (24).