On the accuracy of numerical computation in interpolation by polynomials of two variables

1 month ago

(original), accuracy/perturbations, approximation of multivariate functions, Approximation Theory, interpolation, Numerical Analysis, paper

Abstract

Authors

T. Popoviciu
Institutul de Calcul

Keywords

?

Paper coordinates

T. Popoviciu, Asupra preciziei calculului numeric în interpolarea prin polinoame de două variabile, Stud. Cerc. Mat. (Cluj), 11 (1960) fasc. anexă, pp. 159-165 (in Romanian)

PDF

1960 g -Popoviciu- Stud. Cerc. Mat. (Cluj) – Asupra preciziei calculului numeric in interpolarea prin polinoame de doua variabile

About this paper

Journal

Studii si Cercetari Matematice

Publisher Name

Academy of the Republic of S.R.

DOI

https://ictp.acad.ro/scm/journal/article/view/93

Print ISSN

not available

Online ISSN

google scholar link

??

Paper (preprint) in HTML form

1960 g -Popoviciu- Stud. Cerc. Mat. (Cluj) - On the accuracy of numerical computation in interpolation by

Original text

Rate this translation

Your feedback will be used to help improve Google Translate

ON THE ACCURACY OF NUMERICAL COMPUTATION IN INTERPOLATION BY POLYNOMIALS OF TWO VARIABLES

OF

TIBERIU POPOVICIUCORRESPONDING MEMBER OF THE RPR ACADEMY,

(Cluj)

Paper presented at the Colloquium on the Theory of Partial Differential Equations in

21 - 26

sept. 1959

Let's consider $(m^{'} + 1) (n + 1)$ puncture $(x_{i}, {and}_{j}), i = 1, 2, \dots, m + 1$ , $j = 1, 2, \dots, 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} < \dots < x_{m + 1}$ , ${and}_{1} < {and}_{2} < \dots < {and}_{n + 1}$ . Permutation $P (r_{1}, r_{2}, \dots, r_{m + 1}; s_{1}, s_{2}, \dots, s_{n + 1})$ of the network of nodes is defined by a permutation $r_{1}, r_{2}, \dots, r_{m + 1}$ of indices $1, 2, \dots, m + 1$ , from o to exchange $s_{1}, s_{2}, \dots, s_{n + 1}$ of indices $1, 2, \dots \dots, n + 1$ and renumbering the coordinates of the network nodes so that we have $x_{i}^{'} = x_{r_{i}}, i = 1, 2, \dots, m + 1, {and}_{j}^{'} = {and}_{s_{j}}, j = 1, 2, \dots, n + 1$ .

Let's introduce the notations

\begin{matrix} (1) & D_{in, m}^{i, j} [f] = [\begin{array}{l} x_{in}^{'}, x_{in + 1}^{'}, \dots, x_{in + i}^{'} \\ {and}_{m}^{'}, {and}_{m + 1}^{'}, \dots, {and}_{m + j}^{'} \end{array}; f] \end{matrix}

for the differences divided by the points (

x_{in + a}, {and}_{m + b}

),

a = 0, 1, \dots, i

,

b = 0, 1, \dots, j

, relative to the function

f (x, and)

.
Dd ( = divided difference or divided differences)

\begin{matrix} (2) & \begin{array}{cl} D_{in, m}^{i, j} [f], in = 1, 2, \dots, & m + 1 - i, m = 1, 2, \dots, n + 1 - j, \\ i = 0, & 1, \dots, m, j = 0, 1, \dots, n \end{array} \end{matrix}

constitutes the dd array corresponding to the permutation

P (r_{1}, r_{2}, \dots, r_{m + 1}; s_{1}, s_{2}, \dots, s_{n + 1})

of the network of nodes.

The system

(m + 1) (n + 1)

d.d.

\begin{matrix} (3) & D_{1, 1}^{i, j} [f], i = 0, 1, \dots, m, j = 0, 1, \dots, n \end{matrix}

form 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 under consideration belongs to this array of dd In particular, the chained system (3) belongs to the array (2). Of course, however, the chained system (3) belongs at the same time to other arrays of dd

In particular, the tableau (2) corresponding to the initial permutation

P (1, 2, \dots \dots, m + 1; 1, 2, \dots, 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_{n, n}^{i}_{n}] = [\begin{array}{lll} x_{n}, & x_{n + 1}, \dots, & x_{n + i} \\ {and}_{m}, & {and}_{m + 1}, & \dots, \end{array}]

for all possible values of

i, j, v, μ

2.
Permutations

P (r_{1}, r_{2}, \dots, r_{m + 1}; s_{1}, s_{2}, \dots, s_{n + 1})

of the network of nodes, corresponds to the interpolation polynomial of two variables, which in its general form is [2],

\begin{matrix} (4) & L (x, y) = \sum_{i = 0}^{m} \sum_{j = 0}^{n_{i}} (x - x_{r_{1}}) (x - x_{r_{9}}) \dots (x - x_{r_{i}}) (y - y_{s_{1}}) \times \\ \times (y - y_{s_{2}}) \dots (y - y_{s j}) D_{1, 1}^{i, j} [f] \end{matrix}

where

0 ≦ n_{i} ≦ n, i = 0, 1, \dots, m

and for

i = 0

respectively

j = 0

the product

(x - x_{r_{1}}) (x - x_{r_{2}}) \dots (x - x_{r_{i}})

respectively

(y - y_{s_{1}}) (y - y_{s_{2}}) \dots \times \times (y - y_{s j})

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 (4), 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.
3. To calculate the numerical value of the polynomial (4), 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, Y_{j} = \frac{y - y_{s_{j}}}{l_{j}},

E_{i, j} = k_{0} k_{1} \dots k_{i} l_{0} l_{1} \dots l_{j} D_{1, 1}^{i_{1}, j} [f], i = 0, 1, \dots, m, j = 0, 1, \dots, n

, where

k_{0} (= 1), k_{1}, k_{2}, \dots, k_{m}, l_{0} (= 1), l_{1}, l_{2}, \dots, 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} \dots X_{i} Y_{0} Y_{1} \dots, Y_{j} E_{i, j}

which is usually calculated by adding

\begin{matrix} (5) & \sum_{i = 0}^{m} X_{0} X_{1} \dots X_{i} A_{i}, \end{matrix}

having previously calculated the amounts

\begin{matrix} (6) & A_{i} = \sum_{j = 0}^{n_{i}} Y_{0} \cdot Y_{1} \dots Y_{j} E_{i, j} i = 0, 1, \dots, m . \end{matrix}

Each of the sums (5), (6) is of the form

\begin{matrix} (7) & c_{0} C_{0} + c_{0} c_{1} C_{1} + \dots + c_{0} c_{1} \dots c_{α} C_{α} . \end{matrix}

Let us assume that additions and subtractions do not involve errors (they are performed exactly or, in any case, with some errors that can be neglected). Then if we calculate the sum (7) based on the scheme

\begin{matrix} (8) & c_{0} (C_{0} + c_{1} (C_{1} + \dots + c_{α - 1} (C_{α - 1} + c_{α} C_{α}) \dots)), \end{matrix}

as is usually done, the profit comes only from the performance of the

α + 1

inmulțiri successive

cu c_{α}, c_{α - 1}, \dots, c_{0}

respectively. It is easy to see that if these multiplications are performed with an absolute error, at most equal to

ε

, the approximate result obtained will have an absolute error

≦ ε (1 + \sum_{i = 0}^{α - 1} | c_{0} c_{1} \dots c_{i} |), (= ε

if

α = 0)

In the cases that we will actually consider, 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

≦ ε \sum_{i = 0}^{α - 1} | c_{0} c_{1} \dots c_{i} |, (0

if

α = 0)

.

Let us apply this calculation scheme to the sums (5), (6). The sum (6) is of the form (7), where we put

α = n_{i}, c_{v} = Y_{v}, C_{v} = E_{i, v}, v = 0, 1, \dots, n_{i} .

So if we perform the calculations based on scheme (8), the multiplications being performed with an absolute error

≦ ε

, the result obtained

{\tilde{A}}_{i}

is with an absolute error

≦ ε \sum_{j = 0}^{i^{-} - 1} | Y_{0} Y_{1} \dots Y_{j} |, (= 0

, if

n_{i} = 0)

It follows that the approximation of the sum (б),

\begin{matrix} (9) & \sum_{i = 0}^{m} X_{0} X_{1} \dots X_{i} {\tilde{A}}_{i} \end{matrix}

has an absolute error

≦ ε \sum_{i = 0}^{m} | X_{0} X_{1} \dots X_{i} | (\sum_{j = 0}^{n_{i} - 1} | Y_{0} Y_{1} \dots Y_{j} |)

The sum (9) is also of the form

α = m, c_{v} = X_{v}, C_{v} = {\tilde{A}}_{v}, v = 0, 1, \dots, m .

So if we perform the calculations here based on scheme (8), the multiplications being performed with an absolute error

≦ ε

, the approximate value obtained by pentium (9) will have an absolute error at most equal to

ε \sum_{i = 0}^{m - 1} | X_{0} X_{1} \dots X_{i} | (= 0, dacă 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

≦ ε M

, where

M = \sum_{i = 0}^{m} | X_{0} X_{1} \dots X_{i} | (\sum_{j = 0}^{n_{i} - 1} | Y_{0} Y_{1} \dots Y_{j} |) + \sum_{i = 0}^{m - 1} | X_{0} X_{1} \dots X_{i} |

.
4. We can set ourselves the problem of finding, for the given interpolation point

(x, y)

, exchange that

P (r_{1}, r_{2}, \dots, r_{m + 1}; s_{1}, s_{2}, \dots, s_{n + 1})

of the network of nodes for which the number given by formula (10) is the smallest possible. If this condition is met, we will consider that polynomial (4) is the most advantageous for numerical calculations (made based on the indicated scheme).

Both the amounts

\begin{matrix} (11) & B_{ı} = \sum_{j = 0}^{n_{i} - 1} | Y_{0} Y_{1} \dots Y_{j} |, i = 0, 1, \dots m \end{matrix}

and the sum (10) are of the form

\begin{matrix} (12) & S_{0} + s_{ν_{1}} S_{1} + s_{ν_{1}} s_{ν_{2}} S_{2} + \dots + s_{ν_{1}} s_{ν_{2}} \dots s_{ν_{α}} S_{α}, \end{matrix}

where

S_{0}, S_{1}, \dots, S_{α}

are positive numbers, and

S_{v_{1}}, S_{v_{2}}, \dots, S_{v_{α}}

is a permutation of a string

s_{1}, s_{2}, \dots, s_{α}

of positive numbers.

The string (11) is of the form (12), where

\begin{matrix} α = n_{i} - 1, s_{j} = | y - y_{j} |, v_{j} = s_{j}, S_{j} = \frac{1}{| l_{0} l_{1} \dots l_{i} |} \\ j = 1, 2, \dots, n_{i} - 1, S_{0} = 1 \end{matrix}

and the sum (10) is of the form (12), where

α = m, s_{i} = | x - x_{i} |, v_{i} = r_{i}, S_{i} = \frac{1}{| k_{0} k_{1} \dots k_{i} |} (1 + \sum_{i = 0}^{π_{i} - 1} | Y_{0} Y_{1} \dots Y_{j} |),

i = 0, 1, \dots, m - 1, S_{m} = \frac{1}{| k_{0} k_{1} \dots k_{m} |} (\sum_{j = 0}^{n_{m} - 1} | Y_{0} Y_{1} \dots Y_{j} |), ν_{m} = r_{m}

.

We now have the following

Lemma. The sum (12) reaches its smallest value if the sequence

s_{v_{1}}, s_{v_{2}}, \dots, s_{v_{α}}

is non-decreasing (in other words, for a non-decreasing permutation of the string

s_{1}, s_{2}, \dots, s_{α}

).

The proof is straightforward. It is easy to see that the minimum is reached only for non-decreasing permutations of the sequence

s_{1}, s_{2}, \dots, s_{α}

. From the previous lemma then follows the following
THEOREM. If the permutation

P (r_{1}, r_{2}, \dots, r_{m + 1}; s_{1}, s_{2}, \dots, s_{n + 1})

it is so that the strings

| x - x_{r_{1}} |, | x - x_{r_{2}} |, \dots, | x - x_{r_{m}} |; | y - y_{ε_{1}} |, | y - y_{s_{2}} |, \dots, | y - y_{s_{n - 1}} |

to be non-decreasing, the number M reaches its smallest value.
5. It follows from the preceding that if the sequences

\begin{matrix} (13) & | x - x_{r_{1}} |, | x - x_{r_{2}} |, \dots, | x - x_{r_{m + 1}} |; | y - y_{s_{1}} | \\ | y - y_{s_{2}} |, \dots, | y - y_{s_{n + 1}} | \end{matrix}

non-decreasing int, polynomial (4) is the most advantageous for calculating an approximate value of

f (x, y)

In this case, based on a previous result [1], the permutation

r_{1}, r_{2}, \dots, r_{m + 1}

must be consecutive to the permutation

1, 2, \dots, m + 1

and the permutation

s_{1}, s_{2}, \dots, s_{n + 1}

consecutive permutations

1, 2, \dots, n + 1

This means that for any

t

,

(t = 1, 2, \dots, m + 1

, respectively

t = 1, 2, \dots, n + 1)

, the strings

r_{1}, r_{2}, \dots, r_{t}

and

s_{1}, s_{2}, \dots, s_{t}

are made up of how many

t

consecutive natural numbers (in a certain order).

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

We can, as in the case of a single variable [1], study particular cases differently. If the interpolation point is in the vicinity of one of the extreme nodes

(x_{1}, y_{1}), (x_{1}, y_{n + 1}), (x_{n + 1}, y_{1}), (x_{n + 1}, y_{n + 1})

, we find that the most advantageous polynomials ordered by ascending and descending differences in relation to

x, y

, so those for which the chained system (3) corresponds to the permutations

P (1, 2, \dots, m + 1; 1, 2, \dots, n + 1 P (1, 2, \dots, m + 1; n + 1, n, \dots, 1), P (m + 1, m, \dots, 1; 1, 2, \dots, n + 1 P (m + 1, m, \dots, 1; n + 1, n, \dots, 1)

If the points

x_{4}

and

y_{j}

are respectively equidistant, so if

x_{i} = x_{1} + (i - 1) h, i = 1, 2

,

\dots, m + 1, y_{j} = y_{1} + (j - 1) h^{'}, j = 1, 2, \dots, n + 1, (h, h^{'} > 0)

and if the interpolation point is in the vicinity of the center of the node network, the central differences in relation 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} \dots k_{j} l_{0} l_{1} \dots l_{j} D_{v, μ}^{i, j} [f]

, dd being related to the initial permutation of the network of nodes. If we take

k_{i} = i h, l_{j} = j h^{'}

, for anything

i, j \geq 1

, the numbers considered are reduced to the differences

Δ_{h, h^{'}}^{i, j} 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 very simple because it only requires successive subtractions.

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

ON THE ACCURACY OF NUMERICAL CALCULATION IN INTERPOLATION BY POLYNOMIALS OF TWO VARIABLES

PEBIOME

Calculation of the value of the interpolation polynomial (4) for given

x, y

is carried out by calculating the sum (5), where the numbers

A_{i}

are given by relation (6). Here the numbers

X_{i}, Y_{j}, E_{i, j}

are given in the work and are related to the function

f (x, y)

through divided differences ( 3 ), corresponding to the permutation (

x_{r_{i}}, y_{s_{j}}

) interpolation nodes. Sums (5), (6) have the form (7). The calculation of such a sum is carried out using the scheme (8), where only multiplications by

c_{α}, c_{α - 1}, \dots, c_{0}

are associated with errors smaller than the number є in absolute value. Then the most convenient polynomials for calculation (4) are those for which the sequences (13) are non-decreasing. Thus, we arrive at a theoretical justification for the practical use of the most well-known interpolation formulas, such as those of Newton, Stirling, Bessel, etc.

L'TISRECISION DREAMS

summary

The calculation of the value of the interpolation polynomial (4), in the case of

x, y

given, is done by calculating the sum (5) where the numbers

A_{i}

are given by the relation (6). The numbers

X_{i}, Y_{j}, E_{i .;}

are given liff the text and are linked to the function

f (x, y)

through the intervised nodes (3) corresponding to a permutation (

x_{r_{i}}, y_{s_{i}}

) of such a sum. The sums (5), (6) are of the form (7). The calculation is carried out using scheme (8) or only absolute multi-value sums to the number

^{2}

in this case the polynomials (4) which are advantageous for calculations are those for which the sequences (13) are decrossing. We thus arrive at a theoretical justification for the use and practice of well-known interpolation formulas, such as those of Newton, Stirling, Bessel, etc.

BIBLIOGRAPHY

Popovicus T., Theoretical considerations on the practical use of some interpolation formulas. Scientific Bulletin. Acad. RPR, Section of Mathematical and Physical Sciences, III,

441 - 449 (1951)

STEFFENSEN J. F., Interpolation. New York, 1950.

Received on 3.XII.1959

1960