Some aspects of the problem of accuracy in numerical computations

1 month ago

Tiberiu Popoviciu

accuracy/perturbations, Approximation Theory, Numerical Analysis

Abstract

Authors

T. Popoviciu
Institutul de Calcul

Keywords

?

Paper coordinates

T. Popoviciu, Unele aspecte ale problemei preciziei în calculele numerice, Bul. mat. al Soc. Şt. Mat. Fiz. din R.P.R., 1(49) (1957) no. 4, pp. 473-478 (in Romanian).

[English title: Some aspects of the problem of accuracy in numerical computations]

PDF

1957 b -Popoviciu- Bull. Math. – Unele aspecte ale problemei preciziei in calculele numerice

About this paper

Journal

Bull. Math. de la Soc. Sci, Math. Phys. de la R.P.R

Publisher Name

DOI

Print ISSN

Online ISSN

google scholar link

??

Paper (preprint) in HTML form

1957 b -Popoviciu- Bull. Math. - Some aspects of the problem of precision in numerical calculations

Original text

Rate this translation

Your feedback will be used to help improve Google Translate

SOME ASPECTS OF THE PRECISION PROBLEM IN NUMERICAL CALCULATIONS

OFTIBERIU POPOVICIU (Claj)

(Communication given at the Congress of Romanian Mathematicians, Bucharest, May-June 1956)

Driven by practical needs, numerical analysis has undergone great development in recent decades. The problems of numerical analysis are very varied, but all of them can be characterized by the fact that they aim to obtain results down to the last numerical calculations.

In what follows, we will review, very briefly, some very particular aspects of some numerical analysis problems, of great theoretical and practical importance, aspects that fall within the preoccupations of the Mathematics Section of the Cluj Branch of the Romanian Academy.
2. In many numerical analysis problems, it is required to obtain a number that depends on a function

f

, so the value of a functional is required

A [f]

of argument f. For the sake of clarity and simplification, we will assume for now that

f

is a real function of a real variable. The functional

A [f]

can have different structures. The simplest cases are encountered in calculating the value of the function

f

or its derivative of any order on a given point, as well as in the calculation of the integral of / in a given interval, etc. These latter particular cases are frequently encountered, for example in various methods of numerical integration of differential equations or other functional equations.

Due to too much complication or insufficient knowledge of the function

f

, in general, we cannot get the exact number

A [f]

. We must then be content with an approximation of this number. What makes such approximate calculation problems important is that in practice a convenient approximation of the number

A [f]

is always enough.

There are different procedures that allow us to obtain an approximate value for

A

[f]. A fairly general procedure can be schematized by the approximate equality

\begin{matrix} (1) & A [f] \approx B [f], \end{matrix}

so it can be taken as an approximation for

A [f]

value

B [f]

of another given functional, considered "simpler" than

A [f]

, meaning that effectively the calculation of the number

B [f]

it can be executed to the end and under certain conditions imposed in advance.

A general procedure for obtaining an approximation for the functional

A [f]

consists of replacing the function

f

through an approximation function

f

and

\begin{matrix} (2) & t \approx f . \end{matrix}

The number can then be taken

A [f]

as 0 approximation for

A [f]

, so

\begin{matrix} (3) & A [f] \approx A [f] . \end{matrix}

Moreover, equality (3) is of the form (1) if the approximation function

f

depends uniquely on the function

f

, so if

f

is the value of an operator

\begin{matrix} (4) & f (x) = F [f ∣ x] \end{matrix}

of argument

f

We can then take

\begin{matrix} (5) & B [f] = A [F [f ∣ x]] . \end{matrix}

In the following we will deal only with such approximation formulas.
3. In the practical use of an approximation of the form (1) it is particularly important to appreciate the error committed by this approximation. In search of such an appreciation a convenient delimitation of the remainder

\begin{matrix} (6) & R = R [f] = A [f] - B [f] \end{matrix}

of formula (1) is of great importance. Finally, to obtain such a delimitation a thorough study of the structure of the remainder

R [f]

it is very useful.

If, for example,

R [f]

is a linear functional (additive and homogeneous), under certain fairly general conditions it can be expressed as

R [f]

with the help of an integral (Stieltjes integral if we are under the conditions of F. Riesz's theorem). Such an expression of the remainder is not sufficient, because in the practical delimitations of the remainder there are properties such as those that refer to the degree of accuracy of the approximation formula (or of its remainder). The degree of accuracy (with respect to a polynomial) of a linear functional

R [f]

is defined as the largest whole number

n

(if any), so that

R [f] = 0

, for any polynomial

f

of the degree

n

In this case the remainder can be expressed by a linear functional of the derivative of

(n + 1)

-aa him

f

, if of course certain conditions for the existence of these expressions subsist. Various expressions of this type have been studied by many authors, especially for the rest of the derivation and numerical quadrature formulas.
4. In the case of a linear functional

R [f]

, the theory of higher-order convex functions allows us to find a remarkable form of

R [f]

If

R [f]

is the degree of accuracy

n

and if

f

is a continuous function on an interval, we have

\begin{matrix} (7) & R [f] = a [x_{1}, x_{2}, \dots x_{n + 2}; f] + b [x_{1}^{'}, x_{2}^{'}, \dots, x_{n + 2}; f] . \end{matrix}

In this relationship, valid under very general conditions, where

a, b

are constants independent of the function

f

, we used the well-known symbol of divided differences, and

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

and

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

there are groups of

n + 2

distinct points that generally depend on the function

t, [5]

.

It is particularly interesting when one of the numbers

a, b

can be taken equal to zero. This case occurs if and only if we have

R [f] \neq 0

for any (continuous and) convex function of order

n

.

The form (7) of the remainder specifies its structure a lot, linking it to the differential properties of the function

f

. The connection between divided differences and the
differential properties of a function is ensured by a series of properties, so-called averages, the simplest of which are already known from Cauchy [1] and others have been established more recently [7].
5. We do not insist further on the structure of the remainder

R [f]

; we will make only a few observations.
a) Structure (7) of the remainder

R [f]

, which we assume to be a linear functional, can be studied in a more general framework with the help of a convenient extension of the notion of degree of accuracy. This generalization consists in assuming that

R [f]

vanishes on the linear envelope of a system formed by a finite number of linearly independent functions. Of course, the corresponding generalization of the notion of divided difference is used. In addition to this condition, the remainder has already been obtained in integral form by J. Radon [10].
b) Up to now, nothing analogous is known for the case when

R [f]

is no longer a linear functional. Such functionals as residues seem to be important, however. For example, the Runge-Kutta method of numerical integration of differential equations reverts precisely to an approximation procedure of the general type indicated, in which, however,

R [f]

is not a linear functional. In this case

/

is a function of two or more independent variables. The fact that the remainder in the Rung eKutta method has been little studied so far is due to its complicated structure.

It seems that the problem of the structure of the rest

R [f]

, in case when

R [f]

is no longer a linear functional of

j

, is related to the generalizations of the notion of convexity with respect to an interpolating system of functions. In this latter direction we should mention the works of MI Morozov [4], L. Tornheim [11], E. Moldovan [3].
c) In the cited example of the Runge-Kutta method the remainder depends on a function of several variables. The remainder of the approximation formulas of the form (1) or (3), in which

f

is a function of several real variables, has been much less studied until now. Of course, numerous results were known regarding the rest of the derivation formulas and numerical quadrature (cubation). In our country, in this direction, we must remember the results of DV Ionescu [2]. But even in the case when

R [f]

is a linear functional, a formula analogous to (7) has not yet been studied in general. We, of course, abstract from the simple cases when the results are obtained starting from the case of a single variable and then proceeding by successive superposition of the variables.
6. To obtain an approximation of the number

A [f]

we need to actually calculate the number

B [f]

Let us assume that this number is given by formula (5) through the approximation function (4) of

f

For the actual calculation of

B [f]

a certain number of operations must be performed, which generally consist of a finite number of elementary arithmetic operations (addition, subtraction, multiplication and division).

To perform calculations, regardless of whether they are done directly, with the help of calculation tools, or by machine, a program is always followed which, in particular, specifies the order in which the various operations are performed.

When performing each (elementary) operation and especially when performing multiplication and division, errors are generally made because in practice we use only certain numbers, the so-called practical numbers which are usually expressed by limited decimal fractions or even limited to a certain number of decimal digits. In this way, during the calculation of

B [f]

more calculation errors accumulate which will
affect the final result sought. The approximation thus calculated of

B [f]

will ultimately be the effectively obtained approximation of the number

A [f]

.
7. In the practice of numerical calculation, the establishment, in each case, of a specific calculation program plays a great role. From a theoretical point of view, such programs can be studied, at least in the simplest concrete cases, with the help of various expressions that represent

B [f]

.
00, In order to see somewhat the variety of problems that arise from these considerations, we will present a simple concrete case.
Let us suppose that (4) is the interpolation polynomial of Lagrange.

f (x) = L (x_{1}, x_{2}, \dots, x_{n + 1}; f ∣ x)

,
relative to the function

f

and on the interpolation nodes (distinct)

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

, so it is the polynomial of degree

n

which coincides with the function

f

on the nodes

x_{i}

.

Let us then assume that we are dealing with the problem of interpolation using Lagrange's polynomial (8), therefore calculating the value

f (x_{0})

of the function

f

on the point

x_{0}

(assumed different from the nodes), knowing the values of the function on the interpolation nodes. We are therefore in the case when

A [t] = f (x_{0})

and

\begin{matrix} (9) & B [f] - L (x_{1}, x_{2}, \dots, x_{n + 1}; f ∣ x_{0}) . \end{matrix}

Stud Calculation of the value (9) on the point $x_{0}$ of the polynomial (8) can be done in different ways, according to the different calculation programs that can be indicated and studied by the explicit expressions of the Lagrange polynomial.
Bre 8. Let the formula

\begin{matrix} (10) & L (x_{1}, x_{2}, \dots x_{h + 1}; f ∣ x_{0}) = \sum_{i = 1}^{n + 1} \frac{\prod_{j = 1}^{n + 1} (x_{0} - x_{j})}{\prod_{j = 1}^{n + 1} (x_{i} - x_{j})} f (x_{i}), \end{matrix}

where the index

i

to the symbol

Π (^{(i)}

shows that the value

i

his/her

j

is excluded. Formula (10) can indicate, for example, that an amount of

n + 1

Each term of the sum is generally calculated by

2 n - 1

multiplications and a division. It is worth noting that by taking advantage of the partial results, the number of multiplications can be reduced. Thus, to obtain the products

\begin{matrix} (11) & \prod_{j = 1}^{n - 1} (x_{0} - x_{j}) (i = 1, 2, \dots, n + 1), \end{matrix}

there is no need for

(n + 1) (n - 1) = n^{2} - 1

multiplications, but, in general, only by

3 n = 3

Such a reduction in the number of operations to be performed is of great interest in practice, of course in connection with other conditions that, in general, a computing program must meet.

Another observation that can be made relative to the previous calculation is that in obtaining each term, the multiplication by

f (x_{i})

it may be subsequent or prior to the division operation, which must generally be performed to find this term.

The first way to proceed, which consists of calculating, in advance, the coefficients of

f (x_{i}), (i = 1, 2, \dots, n + 1)

from formula (10) it is advantageous if we need to apply formula (10) to many functions with the same nodes

x_{i}

and the same point

x_{0}

.

The second method, which consists in leaving the division of the terms (possibly only some of the terms) of the sum (10) to the end in the calculation, may present advantages in the case of simple particular data, allowing to take advantage of certain simplifications in the course of the calculation, such as simplifications of ordinary fractions, etc. and which are not advantageous in the case of the first way of organizing the calculations. We must emphasize, however, that such simplifications cannot be theoretically foreseen and do not generally fall within the theoretical concerns of the numerical calculation.
9. The advantages that Newton's formula presents in the problem of interpolation by polynomials are known

\begin{matrix} L (x_{1}, x_{2}, \dots, x_{n + 1}; f ∣ x_{0}) = \\ (12) & = \sum_{i = 0}^{n} (x_{0} - x_{1}) (x_{0} - x_{2}) \dots (x_{0} - x_{i}) [x_{1}, x_{2}, \dots, x_{i + 1}; f ∣ \end{matrix}

(the first term being

f (x_{1})

), where

[x_{1}, x_{2}, \dots, x_{i + 1}; f]

is the divided difference of the function

f

on the nodes

x_{1}, x_{2}, \dots, x_{i + 1}

The calculation program that usually uses formula (12) consists of successively obtaining the numbers

y_{1}, y_{2}, \dots, y_{n}

, where

\begin{matrix} (13) & \begin{array}{l} y_{i} = [x_{1}, x_{2}, \dots, x_{n - 1}; f] + (x_{0} - x_{n - i + 1}) y_{i - 1} (i = 1, 2, \dots, n), \\ y_{0} = [x_{1}, x_{2}, \dots, x_{n - i + 1}; f], y_{n} = L (x_{1}, x_{2}, \dots, x_{n + 1}; f; x_{0}), \end{array}} \end{matrix}

which generally behaves

n

multiplications, so fewer (for

n

sufficiently large) than the program indicated for formula (10). However, we must not forget that here the divided differences were previously calculated

[x_{1}, x_{2}, \dots, x_{i + 1}; f], (i = 1, 2, \dots, n)

. The calculation of these divided differences, for example by forming the table of divided differences, generally involves errors of the nature of those reported due to divisions with intervening node differences. It is then appropriate, as we did on another occasion [9], to examine the influence of the calculation errors, committed when forming the table of divided differences, on the calculation program indicated for formula (12).
10. In conclusion and relative to the calculation program indicated for formula (12) we can also make the following observations.
a) Seeking to minimize the computational burdens that accumulate through this program, we find a justification for the use of the various particular interpolation formulas, after the point of the

x_{0}

In this way and in this way, as I have shown elsewhere [6], the application in practice of Newton's formula with ascending or descending differences, of Euler's, Stirling's, Bessel's, etc. formulas, as the point

x_{0}

is near the extremities, near the center ete., of the table of differences (the nodes are assumed to be equidistant and arranged in ascending or descending order).
b) In the case of equidistant nodes, instead of divided differences, ordinary differences are used whose formation does not involve divisions. It can, however, be generally admitted that the table of differences does not involve calculation errors. I have shown in another paper [8] that for the program (13) modified in this sense, a delimitation of the accumulated calculation errors can be specified, and tables sufficient in practice can also be drawn up for the rapid finding of such delimitations.

BIBLIOGRAPHY

A. Cauch y, On interpolar functions, CR of the Acad. Sci. Paris 11 (1840), 775.
DV I one scu, Cubic formulae in which the integration domain is an equilateral triangle, Stud. și Cerc. Ştiinț., Cluj Branch, VI (1955), 7.
E. Moldovan, A generalization of the notion of convexity, Stud. si Cerc. Sciin}. Filiala Cituj VI (1955), 65.
M. I. Morozov, On some questions of uniform approximation of continuous functions by means of functions of interpolation classes, Izvestiya AN SSSR 16 (1952), 75
T. Popoviciu, On the form of the remainder in tunnels, approximation formulas of the analysis. Proceedings of the General Scientific Session of June 2-12, 1950, Ed. Acad. RPR, Bucharest 1951, p. 183.
- Theoretical considerations on the practical use of some interpolation formulas, Bul. Ştiţinţ. Acad. RPR, Secţ. Şt. Mat. l'iz, XIJ, 2 (1951), 441.
- On the existence of mean values of continuous functions, Hungarian Academy of Sciences, Division II, Public. IV (1954), 353.
- On the precision of numerical calculation in interpolation by Newlon's polynomial on equidistant nodes, Stud. si Cerc. Ştiint. Filiala Cluj VI (1956), 20.
- On the precision of numerical calculation in interpolation by polynomials, Bul. Stiinl.. Acad. RPR, Secț. Şt. Mat. Fiz., VII, 4 (1955), 953.
J. Radon, Residual expressions in interpolation and quadrature formulas using definite integrals, Monatshefte lür Math. u. Physik 42 (1935), 389.
L. Tornheim, On n-parameter Families of Functions and Associated Convex Frunctions, Trans. Amer. Math. Soc. 69 (1950), 457.

1957