The evaluation of errors in computing by interpolation polynomials

EVALUATION OF CALCULATION ERRORS IN INTERPOLATION BY POLYNOMIALS

of

T. POPOVICIU

Member of the RPR Academy
(Cluj)

1.

Practical use of Lagrange's interpolation formula

f(x)\approx L\left(x_{1},x_{2},\ldots,x_{n+1};f\mid x\right),

(1)

where in the second term we have the Lagrange polynomial of degree $n$ which takes the values of the function $f(x)$ on the (distinct) interpolation nodes $x_{i}(i=1,2,\ldots$ , $n+1$ ), depends largely on the form in which this polynomial is put. This is especially important when it comes to the actual calculation of the values of the polynomial for different values of the variable $x$ Here we only deal with the case when the variable $x$ and the function $f(x)$ are real. In this case, to find the value of the polynomial, a finite number of elementary operations of addition, subtraction, multiplication and division must be performed on real numbers, usually limited decimal fractions, and in a determined order. The form in which the Lagrange polynomial is put is related precisely to this order of operations. As for the operations, they are executed, based on known procedures, directly or by machine, and which practically come down to the successive determination of the decimal digits of the result of each partial calculation, exact or approximate, in part.

The calculation procedure used involves inherent errors due to the fact that the successive calculations are made with approximation, for example due to the limitation to a certain number of decimal places of the partial results obtained. These errors are reflected in the final result, determining a correction which, in the interpolation problem considered, will have to be added to the corrections determined by the errors affecting the data of the problem.

We will first assume that the nodes are not necessarily equidistant and we will deal with the calculation of the second term of formula (1) for $x=x_{0}$ , using Newton's formula

L\left(x_{1},x_{2},\ldots,x_{n+1};f\mid x_{0}\right)=\sum_{i=0}^{n}\left(x_{0}-x_{1}\right)\left(x_{0}-x_{2}\right)\ldots\left(x_{0}-x_{i}\right)D_{1}^{i},*;

(2)

where the coefficients $D_{i}^{j},(i=0,1,\ldots,n)$ , are obtained from table 1 of divided differences in which we generally have

D_{i}^{j}=D_{i}^{j}[f]=\left[\begin{array}[]{cccc}x_{i},&x_{i+1},&\ldots,&x_{i+j};f\end{array}\right],D_{i}^{0}=f_{i}=f\left(x_{i}\right),

using the usual notations for divided differences of the function $f(x)$
The formation of table 1 of the divided differences is done by successively calculating the columns using the recurrence formula

	$\displaystyle D_{i}^{j}[f]=\frac{D_{i+1}^{j-1}[f]-D_{i}^{j-1}[f]}{x_{i+j}-x_{i}}\quad\left(D_{i}^{0}[f]=f_{i}\right)$		(4)
	$\displaystyle(i=1,2,\ldots,n+1-j;\quad j=1,2,\ldots,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 if the nodes and the function values at these nodes are given in this form.

Table 1: Table 1

$x$	$f(x)$	$D^{1}$	$D^{2}$	$D^{3}$	...	$D^{n}$
$x_{1}$	$f_{1}$
		$D_{1}^{1}$
$x_{2}$	$f_{2}$		$D_{1}^{2}$
$x_{3}$	$f_{3}$	$D_{2}^{1}$	$D_{2}^{2}$	$D_{1}^{3}$
$\vdots$	$\vdots$	$\vdots$			$D_{2}^{n-1}$	$D_{1}^{n}$
$x_{n-1}$	$f_{n-1}$		$D_{n-2}^{2}$
		$D_{n-1}^{1}$		$D_{*-2}^{3}$
$x_{n}$	$t_{n}$		$D_{n-1}^{2}$
$x_{n+1}$	$f_{n+1}$	$D_{n}^{1}$

⁰⁰footnotetext: *) For

i=0

the corresponding term of the amount is reduced to

D_{i}^{0}

An analogous convention

However, if the elements of array 1 are calculated approximately, the errors made are transposed onto the interpolation polynomial.

On the other hand, the multiplications involved in calculating the value of the interpolation polynomial are also made with errors. In what follows we propose to examine in turn the effect of these two types of errors, which overlap. For simplicity we will assume that the nodes and the point $x_{0}$ , where interpolated, are not affected by errors.
2. We deal first with the effect of errors that occur in the calculation of divided differences, assuming that the multiplications indicated in formula (2) are done exactly.

The columns of table 1 are calculated successively with certain approximations.
Let $\widetilde{f}_{i},(i=1,2,\ldots,n+1)$ , some approximate values of the function values on the nodes, $c_{i}^{(0)},(i=1,2,\ldots,n+1)$ , the respective corrections, so $f_{i}=\tilde{,}_{i}+c_{i}^{(0)},(i=1,2,\ldots,n+1)$ . Let then, in general, $\widetilde{D}_{i}^{j}=\widetilde{D}_{i}^{j}[f]$ , $(i=1,2,\ldots,n+1-j)$ , approximate values of the column elements $j$ , calculated using the already calculated elements of the column $j-1$ and $c_{i}^{(j)},(i=1,2,\ldots,n+1-j)$ , the respective corrections. We will then have

	$\displaystyle\widetilde{D}_{i}^{j}+c_{i}^{(j)}=$	$\displaystyle\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)$		(5)
		$\displaystyle(i=1,2,\ldots,n+1-j,\quad j=1,2,$		( $.,n)$ )

Table 1 of the divided differences is then replaced with table 2 of the calculated approximate values of the divided differences.

Table 2: Table 2

$x$	$\widetilde{f}(x)$	$\widetilde{D}^{1}$	$\widetilde{D}^{2}$	$\widetilde{D}^{3}$	$\widetilde{D}^{n-1}$	$\widetilde{D}^{n}$
$x_{1}$	$\widetilde{f}_{1}$	$\widetilde{D}_{1}^{1}$
$x_{2}$	$f_{2}$		$\widetilde{D}_{1}^{2}$
		$\widetilde{D}_{2}^{1}$		$\widetilde{D}_{1}^{3}$
$x_{3}$	$\widetilde{f_{3}}$		$\widetilde{D}_{2}^{2}$		$\widetilde{D}_{1}^{n-1}$
$\vdots$ $x_{n-1}$	$\vdots\begin{gathered}\vdots\\ \tilde{f}_{n-1}\end{gathered}$	$\vdots$	$\vdots$	$\vdots$	$\widetilde{D}_{2}^{n-1}$	$\widetilde{D}_{1}^{n}$
$x_{n-1}$	$\dot{\tilde{f}}_{n-1}$		$\widetilde{D}_{n-2}^{2}$
$x_{n}$	$\widetilde{f}_{n}$	$\widetilde{D}_{n-1}^{1}$	$\widetilde{D}_{n-1}^{2}$	$\widetilde{D}_{n-2}^{3}$
$x_{n+1}$	$\widetilde{f}_{n+1}$	$\widetilde{D}_{n}^{1}$

An approximate value $\widetilde{L}$ of expression (2) is then obtained using table 2 with the formula

\widetilde{L}=\sum_{i=0}^{n}\left(x_{0}-x_{1}\right)\left(x_{0}-x_{2}\right)\cdots\left(x_{0}-x_{i}\right)\widetilde{D}_{1}^{i}

(6)

and we will have

L\left(x_{1},x_{2},\ldots,x_{n+1};f\mid x_{0}\right)=\widetilde{L}+\lambda

(7)

$\lambda$ being the respective correction.
In order to delimit the correction $\lambda$ linear functionals are introduced $D_{i}^{j,k}[f]$ , defined as follows $(k<n)$ :

D_{i}^{j,k}[f]=\frac{D_{i+1}^{j-1,k}[f]-D_{i}^{j-1,k}[f]}{x_{i+j+k}-x_{i}},

(8)

for $j=1,2,\ldots,nk,i=1,2,\ldots,n+1-kj$ and

D_{i}^{0,k}[f]=f_{i},

(9)

for $i=1,2,\ldots,n+1-k$ In the paper [1] the formula is established

D_{i}^{j,k}[f]=D_{i}^{r,k+jr}\left[D_{i}^{j-1,k}[f]\right]\quad(0\leqslant r\leqslant j),

(10)

which is also written symbolically

D^{\alpha+\beta,k}=D^{\alpha,\beta+k}D^{\beta,k}

The notation used is based on the observation that any string of $n+1$ NUMBERS $\varphi_{1},\varphi_{2},\ldots,\varphi_{n+1}$ can be considered as formed by the values $\varphi_{i}=\varphi\left(x_{i}\right)$ ,
$=1,2,\ldots,n+1$ of a function $\varphi(x)$ , defined on the nodes $x_{1},x_{2},\ldots,x_{n+1}$
Taking into account formula (10), the following expression for the correction was obtained in the cited work : $\lambda$ :

\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_{1},ir}\left[c^{(ir)}\right]\right].

(11)

To delimit the correction $\lambda$ we need a convenient delimitation for $D_{i}^{j,k}[f]$ .

Divided difference $D_{1}^{n}=\left[x_{1},x_{2},\ldots,x_{n+1};f\right]$ is easily delimited taking into account the well-known formula

\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 $l(x)=\left(x-x_{1}\right)\left(x-x_{2}\right)\ldots\left(x-x_{n+1}\right)$ We have

\left|D_{1}^{n}\right|\leqslant N\left(x_{1},x_{2},\ldots,x_{n+1}\right)M,

where

N\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|}

(12)

and $M=\max_{i=1,2,\ldots,n+1}\left(\left|f_{i}\right|\right)$ An analogous delimitation
of $D_{1}^{n-k,h}[f]$ it can be written

\left|D_{1}^{n-k,k}[f]\right|\leqslant N_{k}\left(x_{1},x_{2},\ldots,x_{n+1}\right)M

(13)

where, by the way, $M$ can be replaced $\mathrm{cu}\underset{i=1,2,\ldots,n+1-k}{\max}\left(\left|f_{i}\right|\right)$
In formula (13) we have

N_{k}\left(x_{1},x_{2},\ldots,x_{n+1}\right)=\sup_{\begin{subarray}{c}i=1,2,\ldots,n+1-k\\ |fi|\leq 1\end{subarray}}\left|D_{1}^{n-k,k}\left[f_{i}\right]\right|.

and therefore

N_{k}\left(x_{1},x_{2},\ldots,x_{n+1}\right)=D_{1}^{n-k,k}[f]

provided we choose all the numbers $f_{i},i=1,2,\ldots,n+1-k$ , equal to 1 or -1 , conveniently.

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 (12). For $k>0$ , his expression $N_{k}\left(x_{1},x_{2},\ldots,x_{n+1}\right)$ but it is more complicated.

In his formation $D_{1}^{n-k,k}[t]$ only the nodes actually intervene $x_{i}$ for $i=1,2,\ldots,n-k,k+2,k+3,\ldots,n+1$ . So if $2k\leqslant n-1$ , all nodes will intervene. However, if $2k>n-1$ only the first ones will intervene $n-k$ and the last ones $n-k$ between the nodes $x_{1},x_{2},\ldots,x_{n+1}$ We deduce from this the following formula:

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)

(14)

if $2k>n-1$ It is enough to assume $k<n$ , because we obviously have

N_{n}\left(x_{1},x_{2},\ldots,x_{n+1}\right)=1

(15)

In the particular case

x_{1}<x_{2}<\ldots<x_{n+1}

(16)

it is shown that the formula holds

N_{k}\left(x_{1},x_{2},\ldots,x_{j+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_{k+k+1}-x_{1}}

(17)

15 - Studies and research in mathematics (Cluj), annex/1961-1962

Formulas (14), (15), (17) completely determine $N_{k}\left(x_{1},x_{2},\ldots,x_{i}\right)$ and we have

\left|D_{i}^{j,k}[f]\right|\leqslant N_{k}\left(x_{i},x_{i+1},\ldots,x_{i+j+k}\right)M

where $M=\max_{r=i,i+1,\ldots,i+j}\left(\left|f_{r}\right|\right)$ In particular ,
if all corrections $c_{i}^{(j)}$ remain, in absolute value at most equal to $\varepsilon$ , based on formula (15) we have

\left|D_{1}^{r,i-r}\left[c^{(i-r)}\right]\right|\leqslant N_{i-r}\left(x_{1},x_{2},\ldots,x_{i+1}\right)\varepsilon

and we can write

|\lambda|\leqslant V\left(x_{0}\right)\varepsilon

((18)

where

	$\displaystyle V(x)$	$\displaystyle=\sum_{i=1}^{n}\left\|\left(x-x_{1}\right)\left(x-x_{2}\right)\ldots\left(x-x_{i}\right)\right\|\times$
		$\displaystyle\times\left[\sum_{r=0}^{i}N_{i-r}\left(x_{1},x_{2},\ldots,x_{i+1}\right)\right].$		(19)

When the values of the function are exact, that is, when $c_{i}^{0}=0,i=1,2,\ldots,n+1$ . can be taken even

	$\displaystyle V(x)$	$\displaystyle=\sum_{i=1}^{n}\left\|\left(x-x_{1}\right)\left(x-x_{2}\right)\ldots\left(x-x_{i}\right)\right\|\times$
		$\displaystyle\times\left[\sum_{r=0}^{i-1}N_{i-r}\left(x_{1},x_{2},\ldots,x_{i+1}\right)\right].$		(20)

3.

We will continue to deal with the effect of errors arising from the multiplications indicated in formula (2), assuming that the divided differences $D_{1}^{i}$ which intervene in this formula are calculated exactly. For this, certain theoretical considerations on the interpolation formula (1) are necessary.

At any permutation

x_{v_{1}},x_{v_{2}},\ldots,x_{v_{s+1}}

(21)

of the nodes

x_{1},x_{2},\ldots,x_{n+1}

(22)

an interpolation formula of the form will correspond

	$\displaystyle f(x)$	$\displaystyle=\sum_{i=0}^{n}\left(x-x_{v_{1}}\right)\left(x-x_{v_{1}}\right)\ldots\left(x-x_{v_{i}}\right)\times$
		$\displaystyle\times\left[x_{v_{1}},x_{v_{2}},\ldots,x_{v_{i+1}};f\right]+R(x)$		(23)

Of course the rest $R(x)$ does not depend on the permutation considered and can be written

R(x)=l(x)\left[x,x_{1},x_{2},\ldots,x_{n+1};f\right]

(24)

,where

l(x)=\left(x-x_{1}\right)\left(x-x_{2}\right)\ldots\left(x-x_{n+1}\right)

(25)

The practical use of the interpolation formula (23) will depend on the speed and accuracy of the calculation of the coefficients

\left[x_{v_{1}},x_{v_{2}},\ldots x_{v_{i+1}};f\right],i=0,1,\ldots,n

(26)

of this formula.
These coefficients will be found on the upper (descending) side of the table of divided differences corresponding to the nodes taken in the order (21). However, for the formation of this table, it will be advantageous for the nodes (21) to be placed in the ascending order of their numerical values, because then all the divisions that are made with node differences in order to form the table, are made with positive numbers. In this way, errors that could come from inattention to the signs of the node differences are eliminated.

To simplify the notations, let us assume that the nodes, which we consider distinct, are taken in ascending order, so that

x_{1}<x_{2}<\ldots<x_{n+1}

Then, based on the previous observation, table 1 is the most advantageous of all. $(n+1)$ ! analogous arrays obtained by permuting in all the ways $n+1$ knots.

We observe that not only formula (2) enjoys the property that all its coefficients are contained in table 1. Let us then find all formulas (23) that have all their coefficients in table 2. We will say that these formulas belong to table 1. For this it is necessary and sufficient that for any $i=0,1,\ldots,n$ points $x_{\nu_{1}},x_{\nu_{2}},\ldots,x_{\nu_{i+1}}$ to be $i+1$ consecutive points (taken in a certain order) of the string (22), so as the permutation

v_{1},v_{2},\ldots v_{n+1}

(27)

of numbers $1,2,\ldots,n+1$ to enjoy the property that any section

v_{1},v_{2},\ldots,v_{i+1},\quad i=0,1,\ldots,n

of the string (27) to be formed by $i+1$ consecutive natural numbers, taken in a certain order.

If we agree to say about such a permutation (27) that it is a permutation consecutive to the initial permutation $1,2,\ldots,n+1$ , we see that:
the necessary and sufficient condition for the interpolation formula (23) to belong to table 1 is that the permutation (27) is a permutation consecutive to the initial permutation $1,2,\ldots,n+1$ [the permutation with which tableau 1 was formed].

Let us call neighboring elements of an element of the array 1 those terms of the array, which 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 $\left[x_{i},x_{i+1},\ldots,x_{i+j};f\right]$ are then depicted in the diagram

The coefficients (26) of formulas (23) belonging to table 1 are then characterized by the property that any two consecutive coefficients are neighboring elements in table 1.

The number of interpolation formulas (23) belonging to table 1 can be easily determined. A formula (23) is obtained by choosing coefficients, one from each column, two consecutive coefficients being neighbors. The number $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.

Let's assume that $(n+1)!$ divides by $2^{n}$ and then $(n+1)!=2^{n}p$ . However, the question may be asked whether they cannot be found $p$ divided difference tables, obtained by convenient permutations of the nodes (1), so that they contain all the $(n+1)$ ! formulas (5). In this case, each of the $(n+1)$ ! formulas (5) belong to one and only one of the following tableaus $p$ considered paintings. In the paper [2] it is shown that this is impossible, except for the trivial case $n=1$ .

Also in the paper [2] it is shown that the number of formulas (23) belonging to table no. 1 in which the first $j$ nodes are $x_{i},x_{i+1},\ldots,x_{i+j-1}$ in any order, it is equal $\mathrm{cu}2^{j-1}\binom{n-j+1}{i-1}$ .

With these introductory considerations, we propose to determine the permutation (21) of the nodes, so that the effect of the errors coming from the multiplications (2) is the smallest, when these multiplications are done as usual according to the scheme

\left.\alpha_{0}\left(D_{1}^{0}+\alpha_{1}\right)\left(D_{1}^{1}+\ldots+\alpha_{n-1}\left(D_{1}^{n-1}+\alpha_{n}D_{1}^{n}\right)\ldots.\right)\right),

where was it noted $\alpha_{i}=x_{0}-x_{i},i=0,1,\ldots,n$ This comes down to determining the permutation (21) such that the string

\left|x-x_{v_{1}}\right|,\left|x-x_{v_{2}}\right|,\ldots,\left|x-x_{v_{n+1}}\right|

(28)

be non-decreasing.
By this property, the permutation (2) is not necessarily uniquely determined, but:
$x$ being a given point on the real axis, any permutation (21) for which the sequence (28) is nondecreasing is a permutation consecutive to the initial permutation $1,2,\ldots,n+1$ .

This property subsists regardless of the fact that $x$ coincides with a node or not.

If the permutation (21) enjoys the property that it is possible to find a $x$ , so that the sequence (28) is non-decreasing, we say that this permutation or the corresponding formula (23) verifies the minimum property.

The interpolation formulas (23), for which the sequence (28) becomes non-decreasing for a $x$ conveniently, they all belong to the array 1 formed with the nodes taken in ascending order.

Not all of them $2^{n}$ Formulas (23) belonging to table 1 verify the minimum property studied.

It is shown in the paper [2] that at least $2n$ of these formulas verify the minimum property.

For $n=1,2$ the 2 and 4 formulas belonging to table 1 respectively verify the minimum property.

If $n=3$ and $x_{1}+x_{4}\neq x_{2}+x_{3},7$ of the 8 formulas belonging to table 1 check the minimum probability, and if $x_{1}+x_{4}=x_{2}+x_{3}$ , all 8 formulas verify the minimum property.

In the case of $n=4$ , of the 16 formulas (23) belonging to table 1 , at least 11 and at most 14 verify the minimum property.

It would be interesting to see, for $n$ any, what is the minimum number $(\geqslant 2n)$ and what is the maximum number ( $<2^{n}$ if $n>3$ ) of consecutive permutations to the initial permutation, which 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 (28) for all values of 1ui $x$ for reasons of continuity, only those values of $x$ for the house of the maker. This comes back to the fact that we have to examine the values (in finite number) of $x$ , for which we have

\left|x-x_{r}\right|=\left|x-x_{s}\right|\quad(r\neq s),

equality that can only occur if

x=\frac{x_{r}+x_{s}}{2}

It is therefore sufficient to examine only the points $x$ which coincide with the means of the segments determined by two nodes.

In particular, if the nodes (22) are equidistant, the points $x$ What 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 (23) belonging to table 1, which verify the minimum property, is equal to

4.2^{\left[\frac{n}{2}\right]}+2.3^{\left[\frac{n+1}{2}\right]}-2n-6

where $[\alpha]$ is the whole contained in $\alpha$ .
To apply the interpolation formula, at point $x$ we will choose that formula (23) that verifies the property that the sequence (28) is non-decreasing.

Let us suppose, in particular, that the nodes are symmetrical about a point on the real axis. This point may be the origin 0. We must then distinguish two cases, according to whether the nodes are odd or even in number. If we suppose that we interpolate in the vicinity of the origin, we must also distinguish two cases according to whether the point $x$ is it to the left or to the right of him $O$ .

Case I. Odd number of nodes. The nodes in ascending order can then be written ( $n=2k$ )

-t_{k},-t_{k-1},\ldots,-t_{1},0,t_{1},t_{2},\ldots,t_{k},

and the permutations that verify the minimum property correspond to the following permutations of the nodes:

\begin{gathered}0,-t_{1},t_{1},-t_{2},t_{2},\ldots,-t_{k},t_{k},\\ 0,t_{1},-t_{1},t_{2},-t_{2},\ldots,t_{k},-t_{k},\end{gathered}

as $x$ is it to the left or to the right of him $O$ If
$x$ is sufficiently close to the origin, these are the only permutations that verify the minimum property.

The corresponding interpolation formulas are well-known generalizations of some of Euler's formulas, to which they reduce when the nodes are equidistant. By taking the arithmetic mean of these formulas, a well-known generalization of Stirling's interpolation formula is deduced (it is unnecessary to write these formulas explicitly here).

Case II. Even number of nodes. The nodes in ascending order can then be written ( $n=2k-1$ )

-t_{k},-t_{k-1},\ldots-t_{1},t_{1},t_{2},\ldots,t_{k},

and the permutations that verify the minimum property correspond to the following permutations of the nodes:

		$\displaystyle-t_{1},t_{1},-t_{2},t_{2},\ldots,-t_{k},t_{k}$
		$\displaystyle t_{1},-t_{1},t_{2},-t_{2},\ldots,t_{k},-t_{k}$

as $x$ is to the left or to the right of 0. These permutations are the only ones that verify the minimum property if $x$ is close enough to the origin.

The corresponding interpolation formulas are well-known generalizations of other Euler formulas, to which they reduce if the nodes are equidistant. 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).

Proprietatea de minimum pe care am stabilit-o constituie o justificare a utilizării acestor formule, în cazul cînd se interpolează în mijlocul tabloului diferentelor divizate.
4. Ne ocupăm în continuare cu cazul particular important al nodurilor echidistante, studiat în lucrarea [3]. Atunci printr-o transformare simplă, problema de interpolare se pune sub forma egalităţii aproximative.

f(a+xh)\approx\sum_{n=0}^{r}\frac{x(x-1)\ldots(x-v+1)}{v!}\Delta_{h}^{v}f(a),

(29)

unde coeficienţii $\Delta_{k}^{v}f(a)$ se calculează cu ajutorul tabloului de diferențe ale valorilor $f(a+vh),v=0,1,\ldots,n$ , ale functiei $f(x)$ pe noduri.

Calculul valorii polinomului

L(x)=\sum_{v=0}^{n}\frac{x(x-1)\ldots(x-v+1)}{v!}\Delta_{k}^{v}f(a),

(30)

pentru o valoare dată a lui $x$ , se face pe baza schemei

y_{v+1}=\Delta_{h}^{n-v}f(a)+\frac{x-n+v}{n-v+1}y_{v},\quad v=0,1,\ldots,n,\quad\left(y_{0}=0\right).

(31)

Atunci

y_{n+1}=L(x)

(32)

Într-o astfel de schemă de calcul însă, în mod practic, fiecare număr $y_{v+1}$ se calculează aproximativ, folosind valorile aproximative deja obţinute ale numerelor precedente $y_{1},\ldots,y_{v-1},y_{v}$ . Dacă notăm cu $\bar{y}_{v}$ valoarea aproximativă astfel calculată a lui $y_{v}$ și cu $c_{v}$ corecţia respectivă, succesiunea de calcule se va face, în loc de (4), pe baza schemei
$\bar{y}_{v+1}+c_{v+1}=\Delta_{h}^{n-v}f(a)+\frac{x-n+v}{n-v+1}\bar{y}_{v},\quad v=0,1,\ldots,n\quad\left(\bar{y}_{0}=0\right)$ .

Avem atunci

L(x)=\bar{y}_{n+1}+c

(34)

unde corectia $c$ este dată de formula

c=\sum_{\nu=0}^{n}\frac{x(x-1)\ldots(x-\nu+1)}{\nu!}c_{n-\nu+1}

(35)

Dacă eroarea absolută maximă în calculul valorilor aproximative ale numerelor $y_{\nu}$ este $\leqslant\varepsilon$ , deci dacă

\left|c_{v}\right|\leqslant\varepsilon,\quad v=1,2,\ldots,n+1

(36)

avem

|c|\leqslant\varepsilon K_{1}(x)

(37)

unde

K_{1}(x)=\sum_{v=0}^{n}\left|\frac{x(x-1)\ldots(x-v+1)}{v!}\right|

(38)

Formula de interpolare (29) este avantajoasă în special cînd $x$ este aproape de 0 . Această afirmatie este justificată, de ex., de cercetările noastre anterioare asupra utilizării practice a formulelor de interpolare [2]:

Este deci suficient să studiem aici cazul cînd $0<x<1$ . Avem atunci

K_{1}(x)=2-\frac{(1-x)(2-x)\ldots(n-x)}{n!},\quad x\in(0,1)

(39)

și se vede că $K_{1}(x)$ este crescător în intervalul $(0,1)$ . Rezultă că

1=K_{1}(0)<K_{1}(x)<K_{1}(1)=2,\quad x\in(0,1),

(40)

deci

|c|<2\varepsilon.

(41)

Un tablou al valorilor lui $K_{1}(x)$ poate fi utilizat în practică pentru obținerea unei delimitări mai bune.

Dăm mai jos tabloul valorilor lui $K_{1}(x)$ pentru $x=v\cdot 10^{-1}$ , $v=1,2,\ldots 9$ , şi $n=2,3,4,5,6$ .

Table 3: Tabloul 3

$x\backslash n$	2	3	4	5	6
0,1	145	1735	1941625	21027925	2234412625
0,2	28	328	3616	387136	4075648
0,3	405	4645	5046625	53438375	5576636125
0,4	52	584	6256	655552	6785152
0,5	625	6975	7265625	75390625	7744140625
0,6	72	776	8096	832448	8492032
0,7	805	8505	8766625	89392975	9063046125
0,8	88	912	9296	940864	9487488
0,9	945	9615	9701625	97553325	9792032625

În acest tablou valorile sînt calculate exact și nu figurează decît partea lor zecimală. Partea întreagă este evident 1 peste tot. Pentru o valoare a lui $x$ care nu figurează în tablou, se delimitează superior $K_{1}(x)$ prin valoarea sa pentru valoarea imediat superioară a lui $x$ care figurează în tablou. Este clar că pentru $0,9<x<1$ nu putem obține pe această cale o delimitare mai buna decit (41). In practică este suficient să luăm niçte valori aproximative convenabile ale valorilor care figurează în tablou.

Formula (37) dă pentru $c$ delimitarea

-\varepsilon K_{1}(x)\leqslant c\leqslant\varepsilon K_{1}(x)

(42)

inferioară și superioară. Cînd natura calculului indică anumite condiții suplimentare verificate de corecţiile $c_{\nu}$ , o analiză mai amănunțită permite à precizăm aceste delimitări.

Să presupunem că sîntem în cazul în care $0<x<1$ și, ceea ce se întîmplă des în practică, că numerele $y_{v}$ sînt pozitive. Aceasta va avea loc aproape totdeauna cînd $\Delta_{h}^{v}f(a),\quad v=0,1,\ldots,n$ sînt numere pozitive. Pentru a calcula produsul

\frac{x-n+v}{n-v+1}y

(43)

se calculează totdeauna întîi o valoare aproximativă, de exemplu prin lipsă, a valorij sale absolute, care în cazul nostru este

\left|\frac{x-n+v}{n-v+1}\right|\bar{y}_{v}.

(44)

Acest caz are loc de exemplu dacă se calculează numerele (44) cu un număr oarecare de zecimale exacte.

Dacă presupunem că $c_{1}=0$ , ceea ce practic este acceptabil, deoarece presupunem aici că valorile funcției pe noduri nu sînt afectate de erori, vedem că în conditiile de mai sus corecțiile $c_{2},c_{3},\ldots,c_{n}$ sînt $\leqslant 0($ și $\geqslant-\varepsilon)$ iar $c_{n+1}\geqslant 0($ și $\leqslant\varepsilon)$ . Vom avea atunci

-\varepsilon\left[K_{1}(x)-K_{2}(x)\right]\leqslant c\leqslant\varepsilon K_{2}(x)

(45)

unde Pentru delimitarea lui $K_{2}(x)$ observăm că pentru $n=2$ avem $K_{2}(x)=1$ , iar pentru $n>2$ putem scrie

K_{2}(x)=1+xK_{3}(x),

(47)

unde

K_{3}(x)=\sum_{v=1}^{\left[\frac{n-1}{2}\right]}\frac{(1-x)(2-x)\ldots(2v-1-x)}{(2v)!}

(48)

Funcția $K_{3}(x)$ este descrescătoare în intervalu1 ( 0,1 ) şi vom putea utiliza un tablou de valori ale functiei $K_{3}(x)$ pentru delimitarea lui $K_{2}(x)$ cu ajutorul formulei (47).

Dacă formăm un tablou al valorilor lui $K_{3}(x)$ , pentru valorile $\xi_{v}$ , $v=0,1,\ldots,m-1(m>1)$ , ale variabilei, unde

0=\xi_{0}<\xi_{1}<\ldots<\xi_{m-1}<1,\quad\xi_{m}=1

(49)

și dacă $x$ nu figurează în acest tablou, formula (47) ne dă delimitarea

K_{2}(x)<1+xK_{3}\left(\xi_{i}\right),

(50)

presupunînd că $\xi_{i}<x<\xi_{i+1}$ .

Trebuie să observăm că din (13) și din faptul că $K_{1}(x)-K_{2}(x)>0$ rezultă că

K_{2}(x)<2,

(51)

aşa că pentru $\xi_{i}<x<\xi_{i+1}$ , delimitarea (50) nu ne va da o delimitare mai bună decit delimitarea imediata (51), decit daca $xK_{3}\left(\xi_{1}\right)<1$ . Deci price $0<x<1$ pună decît (51) pentru orice $0<x<1$ , este necesar şi suficient ca să avem

\xi_{i+1}K_{3}\left(\xi_{i}\right)<1,\quad i=0,1,\ldots,m-1.

(52)

În particular, prima condiţie (52) se scrie

\xi_{1}\sum_{v==1}^{\left[\frac{n-1}{2}\right]}\frac{1}{2v}<1,

(53)

care, din cauza divergenței seriei armonice, nu este verificată pentru $n$ destul de mare. Dacă deci numerele $\xi_{v},\nu=0,1,\ldots,m-1$ , sînt date, conditii sînt însă verifica, condițille (52) nu sînt toate verificate. Aceste intervalul $(0,1)$ în 10 če daca, de exemplu, $\xi_{v}$ sînt punctele care împart lui $\xi_{\text{v }}$ si $n$ avem următori ale lu $\xi_{v}$ și $n$ avem urmatorul tablou de valori ale funcţiei $K_{3}(x)$ .

Table 4: Tabloul 4

$x$	3,5	5,6	7,8
0,0	5	75	$91\overline{6}$
0,1	45	656625	788245125
0,2	4	568	670144
0,3	35	483875	561477875
0,4	3	404	461408
0,5	25	328125	369140625
0,6	2	256	$283925\overline{3}$
0,7	15	187375	205053375
0,8	1	122	131856
0,9	05	059625	$063702791\overline{6}$

În acest tablou valorile sînt calculate exact și nu figurează decît partea lor zecimală. Partea intreagă este peste tot egală cu 0 . Pentru a delimita pe $K_{2}(x)$ cu ajutorul formulei (47) pentru o valoare a lui $x$ care nu figurează în tablou, se ia din tablou valoarea lui $K_{3}(x)$ , pentru valoarea lui $x$ imediat inferioară și care figurează în tablou. Se verifică că condițiile (52) sînt satisfăcute în aceste cazuri. În practică se pot lua bineînțeles și aici niste valori aproximative prin adaos calorilor din tablou.

Pentru $n=3,4$ , în multe cazuri se poate obține destul de uşor direct, delimitarea lui $K_{2}(x)$ cu ajutorul formulei

K_{2}(x)=1+\frac{x(1-x)}{2}=\frac{(1+x)(2-x)}{2}.

(54)

Pentru delimitarea numărului $K_{1}(x)-K_{2}(x)$ observăm că el este egal cu $x$ pentru $n=2,3$ , iar pentru $n>3$ se poate scrie

K_{1}(x)-K_{2}(x)=xK_{4}(x),

(55)

unde

K_{4}(x)=\sum_{v-1}^{\left[\frac{n-2}{2}\right]}\frac{(1-x)(2-x)\ldots(2v-x)}{(2v+1)!}

(56)

este o funcţie descrescătoare în intervalul ( 0,1 ). Se pot face observații analoage cu cele de mai sus, relativ la utilizarea unui tablou al valorilor lui $K_{4}(x)$ pentru delimitarea lui $K_{1}(x)-K_{2}(x)$ prin formula (55). Din formula (40) şi din $K_{2}(x)>1$ rezultă

K_{1}(x)-K_{2}(x)<1,\quad x\in(0,1)

(57)

şi condițiile pentru ca tabloul să dea o delimitare mai bună decît (57) pentru $\xi_{i}<x<\xi_{i+1}$ sînt ca $xK_{4}\left(\xi_{i}\right)<1$ . Aici $\xi_{v}$ sînt numerele (49). Dacă $i=m-1$ , această condiție cu siguranță nu este verificată pentru orice $x$ , deoarece $K_{4}\left(\xi_{m-1}\right)>1$ . In cazul acesta nu poate fi deci vorba decit ca tabloul să dea o delimitare mai bună decît (57) pentru orice $0<x\leqslant\xi_{m-1}$ şi orice $\xi_{m-1}\leqslant x\frac{1}{K_{4}\left(\xi_{m-1}\right)}$ The necessary and sufficient conditions for this to be the case are written as

\xi_{i+1}K_{4}\left(\xi_{i}\right)<1,\quad i=0,1,\ldots,m-2.

(58)

In Table 5 we give the values of $K_{4}(x)$ for his values $x$ which divide the interval $(0,1)$ into 10 equal parts and for $4\leqslant n\leqslant 9$ .

Table 5: Table 5

${}_{x}{}^{n}$	4.5	6.7	8.9
0.0	$\overline{3}$	$5\overline{3}$	$\overline{6761804}$
0.1	285	4461675	5571044625
0.2	24	38288	4675136
0.3	1983	$2974008\overline{3}$	$3605917458\overline{3}$
0.4	16	23488	2808064
0.5	125	1796875	2119140625
0.6	$09\overline{3}$	$13141\overline{3}$	15295573
0.7	065	0896675	$103052555357142\overline{8}$
0.8	04	05408	0614016
0.9	$018\overline{3}$	$0243008\overline{3}$	02727179583

This table shows the exact decimal parts of the function values. $K_{4}(x)$ . The integer part is everywhere equal to 1. The bound of $K_{1}(x)$ – $K_{2}(x)$ with the help of (55), using this table, it is done in the same way as it was done to delimit it $K_{2}(x)$ with the help of table 2.

Conditions (58) are fulfilled in these cases. As shown above, Table 5 gives a better delimitation than (57) for

\left\{\begin{array}[]{l}0<x<0,981996\ldots(n=4,5)\\ 0<x<0,976275\ldots(n=6,7)\\ 0<x<0,973452\ldots(n=8,9)\end{array}\right\}

respectively.
5. The previous results can be extended to the case of interpolation by polynomials of two variables [4].

Let's consider $(m+1)(n+1)$ puncture $\left(x_{i},y_{j}\right),i=1,2,\ldots,m+1$ , $j=1,2,\ldots,n+1$ , in the plane, forming a rectangular network of nodes'. For the purpose of fixing the notations we will assume that $x_{1}<x_{2}<\ldots<x_{m+1}$ , $y_{1}<y_{2}<\ldots<y_{n+1}$ Permutation $P\left(r_{1},r_{2},\ldots,r_{m+1};s_{1},s_{2},\ldots,s_{n+1}\right)$ of the network of nodes is defined by a permutation $r_{1},r_{2},\ldots,r_{m+1}$ of indices $1,2,\ldots,m+1$ , of a permutation $s_{1},s_{2},\ldots,s_{n+1}$ of indices $1,2,\ldots,n+1$ and renumbering the coordinates of the network nodes, so that we have $x_{i}^{\prime}=x_{r_{i}},i=1,2,\ldots,m+1,y^{\prime}=y_{sj},j=1,2,\ldots,n+1$ .

Let's introduce the notations

D_{v,\mu}^{i,j}[f]=\left[\begin{array}[]{llll}x_{v}^{\prime},&x_{v+1}^{\prime},&\ldots,&x_{v+i}^{\prime}\\ y_{\mu}^{\prime},&y_{\mu+1}^{\prime},&\ldots,&y_{\mu+j}^{\prime}\end{array};f\right]

for the differences divided by the points $\left(x_{v+\alpha}^{\prime},y_{\eta+\beta}^{\prime}\right),\alpha=0,1,\ldots,i$ , $\beta=0,1,\ldots,j$ , relative to the function $f(x,y)$ .D
$=$ (divided difference or divided differences).
$D_{v,\mu}^{i,j}[f],\quad v=1,2,\ldots,m+1-i,\mu=1,2,\ldots,n+1-j$ ,

i=0,1,\ldots,m,j=0,1,\ldots,n

(61)

constitutes the dd array corresponding to the permutation
of the network of nodes.

P\left(r_{1},r_{2},\ldots,r_{m+1};\quad s_{1},s_{2},\ldots,s_{n+1}\right)

The system $(m+1)(n+1)$ d.d.

D_{1,1}^{i,j}[f],i=0,1,\ldots,m;j=0,1,\ldots,n,

(62)

forms a chained system of dd
If each term of a chained system of dd belongs to the same array of dd we will say that the chained system considered belongs to this array of dd In particular, the chained system (€2) belongs to array 2. Of course, the chained system1 (62) belongs at the same time to other arrays of dd

In particular, tableau 2, corresponding to the initial permutation $P(1,2,\ldots,m+1;2,\ldots,n+1)$ of the network of nodes, will be called
the normal array of dd and any linked system of dd belonging to this array will be called a normal linked system of dd. In the case of the initial permutation we have

r_{i}=i,s_{j}=j,D_{v,\mu}^{i,j}[f]=\left[\begin{array}[]{c}x_{v},x_{v+1},\ldots,x_{v+i}\\ y_{\mu},y_{\mu+1},\ldots,y_{\mu+j}\end{array}\right]

for all possible values of $i,j,\nu,\mu$ .

Permutations $P\left(r_{1},r_{2},\ldots,r_{m+1};s_{1},s_{2},\ldots,s_{n+1}\right)$ of the network of nodes, corresponds to the interpolation polynomial of two variables, which in its general form is [2]

	$\displaystyle L(x,y)=$
	$\displaystyle=\sum_{i=0}^{m}\sum_{j=0}^{n_{i}}\left(x-x_{r_{1}}\right)\left(x-x_{r_{3}}\right)\ldots\left(x-x_{r_{i}}\right)\left(y-y_{s_{1}}\right)\left(y-y_{s_{2}}\right)\ldots\left(y-y_{s_{j}}\right)\quad D_{1,1}^{i,j}[f]$		(63)

where $0=n_{i}\leqslant n,i=0,1,\ldots,m$ , and for $i=0$ respectively $j=0$ the product $\left(x-x_{r_{1}}\right)\left(x-x_{r_{2}}\right)\ldots\left(x-x_{r_{i}}\right)$ respectively $\left(y-y_{s_{1}}\right)\left(y-y_{s_{2}}\right)\ldots\left(y-y_{s_{j}}\right)$ is replaced by 1 .

On a given interpolation point ( $x,y$ ), determining an approximate value for $f(x,y)$ with the help of the polynomial (63) requires the calculation of the numerical value of this polynomial. This calculation is made by executing, exactly or approximately, a certain sequence of elementary operations: additions, subtractions, multiplications and divisions. Since the operations are generally executed approximately, a calculation error will result that depends on the precision with which the calculations were executed as well as, of course, on the order of performing these calculations, that is, on the program on the basis of which they were executed. We will not take into account the errors that may affect the data of the problem, so the coordinates of the nodes and the values of the function $f(x,y)$ on these nodes.

To calculate the numerical value of the polynomial (63), it may also be useful to modify its expression, putting

X_{0}=1,X_{i}=\frac{x-x_{r_{i}}}{k_{i}},Y_{0}=1,\quad Y=\frac{y-y_{s_{i}}}{l_{j}}

where $k_{0}(=1),k_{1},k_{2},\ldots,k_{m},l_{0}(=1),l_{1},l_{2},\ldots,l_{n}$ are some given numbers, different from 0. We then have

L(x,y)=\sum_{i=0}^{m}\sum_{j=0}^{n_{i}}X_{0}X_{1}\ldots X_{i}Y_{0}Y_{1}\ldots Y_{j}E_{i,j}

which is calculated, usually by adding up

\sum_{i=0}^{m}X_{0}X_{1}\ldots X_{i}A_{i}

(64)

having previously calculated the amounts

A_{i}=\sum_{j=0}^{n_{i}}Y_{0}Y_{1}\ldots Y_{i}E_{i,j},i=0,1,\ldots,m

(65)

Each of the sums (64), (65) is of the form

c_{0}C_{0}+c_{0}c_{1}C_{1}+\ldots+c_{0}c_{1}\ldots C_{\alpha}C_{\alpha}.

(66)

Let us assume that additions and subtractions are error-free (they are performed exactly, or, in any case, with some negligible errors). Then if we calculate the sum (66) based on the scheme

c_{0}\left(C_{0}+c_{1}\left(C_{1}+\ldots+c_{\alpha-1}\left(C_{\alpha-1}+c_{\alpha}C_{\alpha}\right)\ldots\right)\right)

(67)

as is usually done, the error comes only from performing the $\alpha+1$ successive multiplications $\mathrm{cu}c_{\alpha},c_{\alpha-1},\ldots,c_{0}$ respectively. It is easy to see that if these multiplications are performed with an absolute error at most equal to $\varepsilon$ , the approximate result obtained will have an absolute error smaller than

\varepsilon\left(1+\sum_{i=0}^{\alpha-1}\left|c_{0}c_{1}\ldots c_{i}\right|\right)\quad(=\varepsilon\text{ dacă }\alpha=0).

In the cases that we will consider effectively, multiplication by $c_{0}$ does not contain errors (we will always have $c_{0}=1$ ). In this case the absolute error of the result is smaller than

\varepsilon\sum_{i=0}^{\alpha-1}\left|c_{0},c_{1},\ldots,c_{i}\right|\quad(=0,\text{ dacă }\alpha=0).

Let us apply this calculation scheme to the sums (64) (65). The sum (65) is of the form (66), where we put

\alpha=n_{i},c_{v}=Y_{v},C_{v}=E_{i,v}\quad v=0,1,\ldots,n_{i}.

So, if we perform the calculations based on the scheme (67), the multiplications being performed with an absolute error $\leqslant\varepsilon$ , the result obtained $\widetilde{A}_{i}$ is with an absolute error $\leqslant\varepsilon\sum_{j=0}^{n_{i}-1}\left|Y_{0}Y_{1}\ldots Y_{j}\right|\quad\left(=0\right.$ , if $\left.n_{i}=0\right)$ It follows that the approximation of the sum (64),

\sum_{i=0}^{m}X_{0}X_{1}\ldots X_{i}\widetilde{A}_{i},

(68)

has an absolute error $\leqslant\varepsilon\sum_{i=0}^{m}\left|X_{0}X_{1}\ldots X_{i}\right|\left(\sum_{j=0}^{n_{i}-1}\left|Y_{0}Y_{1}\ldots Y_{j}\right|\right)$ .

The sum (68) is also of the form

\alpha=m,c_{v}=X_{v},C_{v}=\widetilde{A}_{v},\quad v=0,1,\ldots,m.

So, if here too we perform the calculations based on scheme (67), the multiplications being performed with an absolute error $\leqslant\varepsilon$ , the approximate value obtained for (68) will have an absolute error at most equal to $\varepsilon\sum_{i=0}^{n-1}\left|X_{0}X_{1}\ldots X_{i}\right|$ ( $=0$ , if $m=0$ ).

Ultimately, therefore, making the calculations based on the indicated scheme, we obtain for $L(x,y)$ an approximate value with an absolute error $\leqslant\varepsilon M$ , where

M=\sum_{i=0}^{m}\left|X_{0}X_{1}\ldots X_{i}\right|\left(\sum_{j=0}^{n_{i}-1}\left|Y_{0}\quad Y_{1}\ldots Y_{j}\right|\right)+\sum_{i=0}^{m-1}\left|X_{0}X_{1}\ldots X_{i}\right|.

(69)

We can ask ourselves the problem of finding, for the given interpolation point, $(x,y)$ , that permutation $P\left(r_{1},\dot{r}_{2},\ldots,r_{m+1};s_{1},s_{2},\ldots,s_{n+1}\right)$ of the network of nodes, for which the number $M$ given by formula (69) is the smallest possible. If this condition is met, we will consider that polynomial (63) is the most advantageous for numerical calculations (made based on the indicated scheme).

Both the amounts

B_{i}=\sum_{j=0}^{n_{i}-1}\left|Y_{0}Y_{1}\ldots Y_{j}\right|,

(70)

and the sum (69) are of the form

S_{0}+s_{v_{1}}S_{1}+s_{v_{1}}s_{v_{2}}S_{2}+\ldots+s_{v_{1}}s_{v_{2}}\ldots s_{v_{\alpha}}S_{\alpha},

(71)

where $S_{0},S_{1},\ldots,S_{\alpha}$ are positive numbers, $\operatorname{iar}s_{\nu_{1}},s_{\nu_{2}},\ldots,s_{\nu_{\alpha}}$ is a permutation of a string $s_{1},s_{2},\ldots,s_{\alpha}$ of positive numbers.

The string (70) is of the form (71), where
$\alpha=n_{i}-1,s_{j}=\left|y-y_{j}\right|,v_{i}=s_{j},S_{j}=\frac{1}{\left|l_{0}l_{1}\cdots l_{j}\right|},j=1,2,\ldots,n_{i}-1,S_{0}=1$ ,
and the sum (69) is of the form (71), where
$\alpha=m,s_{i}=\left|x-x_{i}\right|,v_{i}=r_{i},S_{i}=\frac{1}{\left|k_{0}k_{1}\ldots k_{i}\right|}\left(1+\sum_{j=0}^{n_{i}-1}\left|Y_{0}Y_{1}\ldots Y_{j}\right|\right);$

i=0,1,\ldots,m-1,S_{m}=\frac{1}{\left|k_{0}k_{1}\ldots k_{m}\right|}\left(\sum_{j=0}^{n_{m}-1}\left|Y_{2}Y_{1}\ldots Y_{j}\right|\right),v_{m}=r_{m}

We now have the following
Lemma. The sum (71) reaches its smallest value if the sequence $s_{v_{1}},s_{v_{2}},\ldots,s_{v_{\alpha}}$ is non-decreasing (in other words for a non-decreasing permutation of the string $s_{1},s_{2},\ldots,s_{\alpha}$ ).

The proof is immediate. It is easy to see that the minimum is reached only for non-decreasing permutations of the sequence $s_{1},s_{2},\ldots,s_{\alpha}$ .

From the previous lemma the following
Theorem then follows. If the permutation $P\left(r_{1},r_{2},\ldots,r_{m+1};s_{1},s_{2},\ldots,s_{n+1}\right)$ is such that the strings
$\left|x-x_{r_{1}}\right|,\left|x-x_{r_{2}}\right|,\ldots,\left|x-x_{r_{m}}\right|;\left|y-y_{s_{1}}\right|,\left|y-y_{s_{3}}\right|,\ldots,\left|y-y_{s_{n-1}}\right|$
to be non-decreasing, the number $M$ reaches its lowest value.

It follows from the preceding that if the strings

\left|x-x_{r_{1}}\right|,\left|x-x_{r_{2}}\right|,\ldots,\left|x-x_{r_{m+1}}\right|;\left|y-y_{s_{1}}\right|,\left|y-y_{s_{2}}\right|,\ldots,\left|y-y_{s_{n+1}}\right|

(72)

are non-decreasing, the polynomial (63) is the most advantageous for calculating an approximate value of $f(x,y)$ In this case, based on a previous result [2], the permutation $r_{1},r_{2},\ldots,r_{m+1}$ must be consecutive to the permutation $1,2,\ldots,m+1$ , and the permutation $s_{1},s_{2},\ldots,s_{n+1}$ consecutive to permutation $1,2,\ldots,n+1$ This means that for any $t(t=1,2$ , $\ldots,m+1$ , respectively $t=1,2,\ldots,n+1)$ strings $r_{1},r_{2},\ldots,r_{t}$ and $s_{1},s_{2}$ , … $s_{1}$ , are made up of $t$ consecutive natural numbers (in a certain order).

When the sequences (72) are non-decreasing and, in this case, the polynomial (63) is advantageous by calculations in the sense shown above, the corresponding chained system of dd is a normal chained system. It is therefore sufficient to use the normal tableau of dd to be able to construct all the advantageous polynomials (63), according to the different positions of the interpolation point.

We can, as in the case of a single variable [2], study various particular cases. If the interpolation point is in the vicinity of one of the extreme nodes $\left(x_{1},y_{1}\right),\left(x_{1},y_{n+1}\right),\left(x_{m+1},y_{1}\right),\left(x_{m+1},x_{n+1}\right)$ , we find that the most advantageous polynomials ordered by ascending and descending differences with respect to $x,y$ , so those for which the chained system (62) corresponds to the permutations $P(1,2,\ldots,m+1;1,2,\ldots,n+1)$ , $P1,2,\ldots,m+1;n+1,n,\ldots,1),P(m+1,m,\ldots,1;1,2,\ldots,n+1)$ , $P(m+1,m,\ldots,1;n+1,n,\ldots,1)$ If the points $x_{i}$ and $y_{j}$ are respectively equidistant, so if

	$\displaystyle x_{i}=x_{1}+(i-1)h,i=1,2,\ldots,m+1,y_{j}=y_{1}+(j-1)h^{\prime}$
	$\displaystyle j=1,2,\ldots,n+1\quad\left(h,h^{\prime}>0\right)$		(73)

and if the interpolation point is in the vicinity of the center of the network of nodes, we find that the most advantageous polynomials (63) are those ordered by the central differences with respect to $x$ and $y$ .

Finally, we note that instead of the normal array of dd, we can use the array formed with the numbers $k_{0}k_{1}\ldots k_{j}l_{0}l_{1}\ldots l_{j}D_{v,\mu}^{i,j}[f]$ , dd being related to the initial permutation of the network of nodes. If we take $k_{i}=ih,l_{j}=jh^{\prime}$ , for anything $i,j\geqslant 1$ , the numbers considered are reduced to the differences $\Delta_{h,h^{\prime}}^{i,i}f(x,y)$ of the function $f(x,y)$ The normal table of differences can then be replaced by the table of differences, the formation of which is particularly simple, since it only requires successive subtractions.

Finally, the previous considerations can be extended to the case of more than two independent variables.

BIBLIOGRAPHY

1.

Popoviciu T, On the precision of numerical calculation in interpolation by polynomials. Bull. scient. - Acad. RP R., Section of mathematical and physical sciences, VIII, 954-961 (1955).
2.
- •
  
  Theoretical considerations on the practical use of some interpolation formulas. Scientific Bulletin - Acad. RPR, Section of Mathematical and Physical Sciences, III, 441-449 (1951).
3.
- •
  
  Desfre precision of numerical calculation in interpolation by Newton's polynomial with equidistant nodes. Scientific Studies and Research, Ser. I, VI, 3-4, 27-35 (1955).
4.
- •
  
  On the precision of numerical calculation in interpolation by polynomials of two variables. Studies and research in mathematics (Cluj), XI, annex fasciculă anexă, 159-165 (1960).
5.

Steffensen JF, Interpolation, New York, 1950.

The evaluation of errors in computing by interpolation polynomials

Abstract

Authors

Keywords

Paper coordinates

PDF

About this paper

Journal

Publisher Name

DOI

Print ISSN

Online ISSN

References

Paper (preprint) in HTML form

EVALUATION OF CALCULATION ERRORS IN INTERPOLATION BY POLYNOMIALS

of

BIBLIOGRAPHY

Related Posts