Best Chebyshev Approximation for Compression of Big Information Arrays

Abstract

The development of the theory of best uniform approximations was started by the work of Pafnuty L. Chebyshev (1821-1894) who for the first time has found the existence of the best polynomial approximation and detected its unique feature [1]. This theory later received his name. The scientific prove for the existence and uniqueness of such a polynomial as well as the basis for development of the classical analytical methods for its computing were given in the papers of P. Kirchberger, D. Jackson, S.-J. Valle-Poussin, E. Borel, S.N. Bernstein, N.I. Akhiezer and others. E.Y. Remez has proposed in 1933-1934 the method of successive Chebyshev interpolations and two based on it algorithms (I and II). They became the basis for numerical solution of the Best Chebyshev Approximation (BCA) problem. However because of the method computational complexity, implementation of the best approximants in practice became possible only in the late 1950s with the use of the computers developed then in Soviet Union. It should be noted that the first computer algorithms and programs of the polynomial BCA have been developed at V.M. Clushkov Institute of Cybernetics (GIC) of National Academy of Sciences of Ukraine (NASU) in the late 1950s with the direct assistance of E.Y. Remez. The results of specific problem solving were first reported by the authors in 1961 at the IV All-Union Mathematical Congress in Leningrad. The BCA technique development is traditionally held at GIC in the directions of the approximant class expansion and the BCA technique use to increase the accuracy of application problem solutions. Besides, it inspirits such important areas of the computer technology (CT) scientific foundations as the processing and compression of big numerical arrays, as the computational algorithm optimization for accuracy and speed by minimizing the total errors in their implementation. The related GIC results and some prospects for further development are described.

Keywords

• compression of data arrays
• existence
• uniqueness
• Best Chebyshev Approximation (BCA)
• information processing
• complicity
• accuracy
• performance
• total error

-

Improving the level and quality of information support for society is an increasingly important as a determining condition of its effective development. Information on the studied object states is usually represented by discrete form of functional dependencies which characterize the various nature processes in the form of information arrays of numerical data.

Working with such big arrays is associated with serious difficulties in their use in mathematical modeling and forecasting problems, in solving the problems of economically storing large amounts of data, in their high-speed transmission through communication channels, etc.

To overcome the above difficulties, mathematical processing of the arrays is applied using the interpolation, mean-square or uniform approximation methods to compress them by replacing the discrete representation with their analytical expression.

The compression ratio is characterized by a compression coefficient C, which is determined by the formula

C  b f  bF  , where b(f) and b(F) are accordingly the array size of the given discrete function f and the number of approximant parameters F.

The most efficient and general way to solve such problem is provided by the best uniform approximation method based on the P.L. Chebyshev’s results [1].

A fundamental feature of Best Chebyshev Approximation (BCA) is that the approximation accuracy limit obtained for a function discrete representation remains guaranteed for any points of the function continuous interval. The feature makes BCA preferable over both interpolation and RMS approximation methods. The specified BCA advantage allows one high accuracy solving both the problem of high compression ratio approximation of numerical data arrays (the direct approximation problem), and the problem of recovering the missed or absent values of the original data (the inverse approximation problem). The second problem usually arises when the experiment repeating is either difficult or impossible. Typical examples are analysis and synthesis of complex static or dynamic systems. The BCA feature is preserved when solving both direct and inverse approximation problems.

Known methods for the Chebyshev problem solving can be subdivided by the spread of E.Y. Remez’ methods [2, 3], the linear and convex programming methods [4, 5], the spline approximation methods [6], the methods of sequential differential linearization by parameter coefficients (mainly for fractional rational approximation) [7]. Among them, a special attention is paid to the second E.Y. Remez’ method which provides relatively fast convergence rate (quadratic in some cases) with the ability of computation unification. The last is important for the efficiency of computer implementations.

The first GIC results in the area of BCA algorithm and program development addressed the polynomial approximation of univariate functions and the approximate solving systems of incompatible equations. Both were based on the second method of successive Chebyshev interpolations (SCI) proposed by E.Y. Remez. They have started a series of successive developments [8 - 11].

Farther development of the BCA thematic at GIC went in the next main directions. 1. Development of new BCA methods and algorithms for both analytically and discretely defined univariate functions by approximants of various nature (polynomial, fractional rational, etc.) as well as for the multivariate functions by generalized polynomial approximants. They apply the Remez’ SCI with reducing the problems to the linear programming problems. A branch of this direction is development of the best piecewise approximation algorithms and programs. They are applied to big arrays (of the order of 10 million values and more) breaking them by parts (a segment approximation).

2. Optimization of algorithms and programs for accuracy and speed by obtaining estimates of their total errors; development of methods, techniques and methods for modifying algorithms in order to further increase their computational efficiency; development of the techniques for solving classes of applied problems, including those related to compressing the large arrays of numerical information.

Increasing the information flows in society together with the raising acute problem of their compression when ensuring high accuracy and speed determine the growing demand and special relevance of BCA.

The ongoing BCA development at GIC addresses mainly its wider and systemic use for various classes of applied problems as well as the computer algorithm optimization.

Brief introduction to the BCA problems, algorithms and optimization methods is presented below. See [12 -15] for more detailed and specific information. 2

Problem Statement and Algorithms

The problem of best (uniform) Chebyshev’s approximation of a function f x on interval a, b in a general statement is based on the Chebyshev principle of minimizing the measure of uniform approximation

LH n   max f x  H n x; A .

xa,b It consists of finding such an approximate of degree n with the coefficients A  a0 , a1,, an  from the whole set of approximants Hn of degree  n which satisfies the minimax condition

LH n   min , where f x is a function continuous on a, b and min LH n  is the smallest Hn measure of uniform approximation.

As H n x; A consider the classes Pn of all polynomials of degree no bigger than and the classes rn of all fractional rational expressions of the degree n=l+m of type rn x  Pl x/ Qm x  rn x; A; B , coefficients A  ai , i  0, l and B  b j , j  0, m . where Pl(x) and Qm(x) are polynomials of the degrees l and m respectively with the

Then the statements of the problems of finding the best Chebyshev approximants are: max f x  Pn x; A  LPn   min , min LPn   L n x   , xa,b Pn Pn xmaax,b f x  rn x; A; B  Lrn   mrnin , mrnin Lrn   LRn x   , ( 1 ) ( 2 ) where Пn(x) and Rn(x) are target polynomial and fractional rational best Chebyshev approximants, when  and  are the values of their best approximations.

The existence, uniqueness and properties of these approximants follow respectively from the classical theorems of E. Borel and P.L. Chebyshev for the polynomial statement ( 1 ), and N.I. Akhiezer and P.L. Chebyshev for the fractional rational statement [16, 17]. Based on these theorems, the only solutions to problems ( 1 ) and ( 2 ) coincide, respectively, with the solutions to next “elementary” problems: max f x  Pn x; A   , xX1 max f x  rn x; A; B   , xX2 on (n+2) point subsets X 1 , X 2  a,b where the values  and  reach their max possible values  and  .

Each of the (n+2) point problems is a Chebyshev interpolation problem of the function f (x) on the set of (n+2) points, which are called Chebyshev alternance for the polynomial problem ( 1 ) and extremal basis for the rational fractional problem ( 2 ) respectively. This remarkable property of Chebyshev alternance is the basis for finding all the best Chebyshev approximations.

E.Y. Remez method of solving the problems ( 1 ) and ( 2 ) is based on the idea of sequential Chebyshev interpolations (SCI), whose r steps are reduced to finding a sequence of (n+2) point S-sets Sr  xr , v  0, n  1. This sequence converges to v the desired Chebyshev alternance or extreme basis if obtained by solving at each j-th step the next systems of algebraic equations for ( 1 ) and ( 2 ) respectively: f x j   Pn, j x j    1v  j ,

v v wxv j  f xv j  Pl, j xv j / Qm, j xv j   1v j . ( 3 ) ( 4 ) The equations ( 3 ) are linear with respect to the coefficients ak , k  0, n of the polynomial Pn, j x and the value j when the equations ( 4 ) are non-linear with respect to the coefficients ai , i  0, l , the coefficients bi , i  0, m and the value j [2, 3, 8].

The main difficulty of all the numerical implementations of the Remez method is the choice of the (n+2) point sets at each step of. The subsets determine both the rate of convergence and the existence of the SCI convergence. 3 options are known for selection the (n+2) point sets: the optimal one, the semi-optimal one and the acceptable one. The optimal option provides the quadratic convergence rate, which in practice leads to a few iterations needed (even 1-2 iterations only: [3], p. 79).

The BCA algorithms for both the polynomial/fractional rational approximation of univariate functions and the generalized polynomial approximation of multivariate functions developed at GIC are based on the second method of E.Y. Remez’ SCI. The main advantage of the GIC algorithms in comparison with similar implementations known from other publications is their optimal method of the (n+2) point set replacement when moving to the next iteration [9 - 11]. 2.1

Polynomial and Fractional Rational Approximation

The initial function f(x) can be defined both analytically and discretely in the algorithms for solving the problems ( 1 ) and ( 2 ). However, discrete calculated values are used always when replacing the (n+2) point sets (at each iteration) [14, 15].

The replacement of current (n+2) point sets S j by the next S j1 is implemented according to the next rule. SCI selects the largest (n+2) deviations of the approximant from the initial function, taking into account the alternation (serial inversion) of the deviation value signs. Thus, the Chebyshev alternance for the problem ( 1 ) or the extremal basis for the problem ( 2 ) is approached, and the best approximants are computed together with their best approximation value. The solution of problem ( 1 ) at each j-th step is reduced to solving the system of linear algebraic equations ( 3 ) by the Kraut method optimized for accuracy and speed [14, 15].

Two algorithms (“A” and “B”) have been developed for the problem ( 1 ). Their difference is correspondent to the difference of the next BCA polynomial forms: n n  ai xi or  bi Ti x respectively. i 0 i 0

According to N.S. Bakhvalov, the algorithm “B” improves the algorithm “A” in the case of big variation of the polynomial coefficients, which can cause a big rounding error when calculating values by Horner scheme. The N.S. Bakhvalov’s algorithm for writing a polynomial in the form of a linear combination of Chebyshev polynomials significantly reduces the indicated numeric error [14, 18].

The total error analysis of algorithms “A” and “B” has shown that the advantage of the algorithm “B” becomes noticeable at the polynomial degrees n>10. For n≤10, both the algorithms are approximately equivalent in precision.

According to A. Ralston, convergence of the problem ( 2 ) is possible only for initial approximations in the near neighborhood of the best polynomials when convergence of the problem ( 1 ) is provided for any initial (n+2) point sets. However, A. Ralston of did not give any practical recommendations regarding the initial choice [19].

The drawback was eliminated in the Werner’s method able to converge from an arbitrary initial approximation. However, the algorithm complexity and its low (linear) convergence rate (according to the author himself) do not allow this method to be efficiently used in practice [20].

The combined algorithm (CA) developed at GIC has proposed a method of choosing the initial (n+2) point sets “close” enough to the target one. It ensures the SCI convergence for the problem ( 2 ). The CA uses Werner’s method at the first step to produce good initial (n+2) point set for SCI. It eliminates the theoretically possible cases of “degeneration” or “almost degeneration”. Then the SCI process continues until the desired is received. In contrast to the polynomial case ( 1 ), in the problem ( 2 ), the CA start is controlled by given accuracy, and the systems of algebraic equations ( 4 ) are nonlinear. The system ( 4 ) is linearised by eliminating unknowns using the iterative secant method [14].

Numerous examples of solving problem ( 2 ) by the CA algorithm never caused “degeneracy” or “almost degeneracy” confirming the stable convergence of the Remez’ SCI for the problem ( 2 ) as well as for the problem ( 1 ). 2.2

Approximation of Functions of Many Variables

The problem of multivariate function approximation f X   f x1, x2 ,, xm  is ly independent basis functions 1X ,,n X  : n solved by the generalized polynomials Fn X    ai i X  on a system of lineari0 n max f X    z j j X   Lz1, z2 ,, zn   min , xE j1 where Z  z1,,z n  is found as a solution to a special case of a uniformly best approximation problem reduced to solving the next systems of incompatible linear equations:

n i Z    z j  j X i  f X i , i  1, N

j1

The problems (5) - (6) and (7) are equivalent to the next linear programming problem. n By attaching to each function i Z    aij z j  bi its “symmetrical copy” j1 n  N i Z   i Z    aij z j  bi the problem is reduced to the next problem j1 of algebraic minimax:

n i Z    aij z j  bi  0 , i  1,2N; aiN , j   a ; biN   bi , ij j1

 n  max i Z   im1,a2xN  j1 aij z j  bi   LZ   min    .

i1,2N  relative to such parameter values Z  z1,,z n  so that the value of the quantity max i Z  is the smallest possible, i.e. 1i 2N max i Z   LZ   min    . 1i2N Z

n   min,  i    i Z    aij z j  bi    0 , j1

The algorithm implements the direct and dual linear programming problems. The leading one is dual which is solved by the modified simplex method (MSM) given that in practice the number of equations N is much greater than the number of unknowns n, and table of “extended basis” of size n  2 n  4 for MSM is significantly less than the reference table of direct simplex method n  2 N . Some used techniques allow reducing more than half the simplex table and transforming just the modified (compressed) simplex table with the reference table being unchanged during the dual MSM problem solution. (See [3, 10, 14] for more details.)

The described MSM algorithm computes the desired parameters z1, z2 ,, zn of the problem (7) - (8). The found parameter values are then used to find the values i1 Z , i2 Z  , …,  in1 Z  . Their smallest and largest modulo values A (5) (6) (7) (8) and L are the lower and upper boundaries of the best approximation value  , i.e. A    L .

The criterion for the algorithm stop is fulfillment of the condition L    L  A .

The techniques used in the algorithm can significantly reduce the number of calculations and increase the accuracy [14]. 2.3

Algorithm Optimization

At GIC, the optimization of computational algorithms for accuracy and speed is traditionally based on the developed general theory of total error estimation.

The early results in this research direction have been obtained in Soviet Union in the 50-60s for estimating the approximation method errors and the fatal input data errors by S.M. Nikolsky, V.K. Dzyadyk, N.P. Korneychuk, S. B. Stechkin et al. The research was continued by A.N. Tikhonov, V.K. Ivanov, M.M. Lavrentiev. Since 1960s, interesting results on the rounding error estimates for numerical implementations of algorithms were obtained by N.S. Bakhvalov, J.H. Wilkinson, V.V. Voyevodin, V.A. Morozov, I. Babushka, S.L. Sobolev and others. With the development of approximate methods of computational mathematics, the need for a significant increase in the accuracy of their computer implementations has grown. An important progress for the problem solution was obtained in 1970th within the general scientific theory of analysis and estimates of total errors (TE), including all kinds of computational errors of algorithms, together with the first works on optimization of approximate methods and algorithms for various areas of numerical analysis.

GIC researchers were the first in Soviet Union who on the base of the theory estimated TE for the methods and algorithms of operator and singular integral equation solving, Fourier transforms, BCA. The research was continued in [12, 13, 21-30].

The efforts lead to founding the All-Union School for the Optimization of Computing and to organizing the scientific international forum “Problems of Optimization of Computing” held by GIC since 1969 till now.

Such TE estimates were developed at GIC for BCA of the problems ( 1 ) and ( 2 ). They include both a priori and a posteriori deterministic majorant TE estimates. For some function classes of specific structural properties the obtained TE estimates are unimprovable by order with respect to some parameters. Inclusion of TE estimates into the computational schemes of algorithms can significantly increase their accuracy. In some cases, an order of magnitude improvement is achieved. Numerous procedures and techniques are used for additional optimization of the algorithm accuracy and speed. Among them, the input data preliminary processing is applied for eliminating random inaccuracies [12-14, 27].

Along with the basic BCA algorithms, using additional classes of approximants such as exponential, logarithmic and the root of the polynomial extends the classes of approximable functions.

In order to increase the compression efficiency of big data arrays, an analysis of the comparative BCA accuracy characteristics for different classes of approximants have been examined, and a class of generalized polynomials Qn x z11x   znn x for systems of basis functions 1x,,n x using a special case of reducing the problem (5) to the univariate version has been defined. A complex of BCA algorithms and programs for such polynomials has been developed.

A comparative analysis of the accuracy of approximations with different systems of basis functions is executed to determine the most suitable system in order to further improve the accuracy of solving the problem (5) in each specific case.

In order to further increase the efficiency of BCA use for compressing big and extra-big data arrays, a method of segment approximation has been developed. It is based on selection of the optimal number of nodes for dividing the array into subintervals with further applying BCA for each of them separately. Besides, the classes of approximants on the subintervals are selected taking into account the features of the interval dataset. This approach increases both the BCA accuracy at each subinterval and the total compression ratio. It should be noted that the segment approximation method for large arrays representing the functions with singularities commonly provides much better accuracy compared to the approximation on the whole interval [31, 32].

The developed techniques for comprehensive BCA optimization provide benefits of the developed tools in comparison with similar implementations such as [33, 34]. 3

Obtained Results

The developed BCA algorithms and programs for many years were used as a component of the built-in software of Soviet computers, including Macro Conveyor of MIR computer series where they implemented the system-level functions in the basic translator. In practice, their efficiency has been verified by many implementations in Ukraine, in other republics of Soviet Union, and abroad. The BCA toolkit was used for data array compression when solving various application problems in the fields of science and technology (including defense), when computing the complex systems characteristics in both static and dynamic mode of operations e.g. within the aircraft structural strength modeling for Soviet Tupolev Design Bureau, and Antonov Design Bureau (later Ukrainian Antonov Aeronautical Scientific-Technical Complex). The BCA toolkit was also used to calculate trajectories of planets and artificial satellites; transects and curves of transcontinental air pollution transport; profiles of highways and railways (including the famous Baikal–Amur Mainline); state analysis and forecasting for the Soviet Union energy system; the structural strength characteristics of beams and ceilings in earthquake-prone zones.

In the framework of the Chernobyl disaster consequences liquidation, the BCA toolkit was used as a component of the current state calculation software used for simulation of the Kiev water reservoir, the whole water system of the Dnieper reservoir cascade, of Black Sea and all the lemans of North-Western Black Sea region and of several other water objects [35].

The BCA algorithms have been implemented in FORTRAN, Algol, Pascal and then in C++. The last implementation is used by Ukrainian cluster supercomputers of SCIT family as a component of its Basic Parallel Application Software (BPAS). The SCIT BPAS includes the next BCA libraries: libроlу_арх.а (for the polynomial approximation of univariate functions), libratfraction.a (for the fractional rational approximation of univariate functions), libmany_var.a (for approximation of multivariate functions by the systems of basis functions), icybmath.a (for high precision computing the elementary and special mathematical functions), many_var_interp.a (for interpolation of multivariate functions).

It should be noted that accuracy of elementary and special functions provided by the library is not less than 10-21 with the number of coefficients not more than 10. It is much better than the accuracy of conventional approximations (of not more than 8 exact decimal numbers).

All the libraries have copyright certificates.

The developed libraries can be used, inter alia, as reusable components for distributed solving problems in the EGI computational grid for high throughput computing. Despite the fact that the BCA algorithms and software libraries are not internally parallel, their use as an invariant BPAS component is supposed in a multitask mode when solving many sub-problems concurrently. The mode is common for parallel processing of big data arrays and this explains the libraries relevance for the High Performance Computing (HPC) domain.

The BPAS libraries implementation was funded by several projects including the project of approximation subsystem development for compressing big arrays of numeric data as a part of the Ukrainian Budget Committee Information and Analytical System, and the NASU scientific and technical project for development of software/hardware complexes [36].

BCA by generalized polynomials together with algebraic ones is widely used in solving many application problems for compressing big and extra-big onedimensional arrays-vectors (with up to 10 million number elements) with compression coefficients ranging from 100 to 500. For example, 1897 measurements of water salinity at different depths of the Black Sea compressed by polynomials of degrees from 9 to 14 with the compression ratios from 126 to 190 were reconstructed with the error from 1.2% to 2.1%.

Fig. 1 shows another example of BCA compression of a matrix by generalized polynomials. The matrix of size 17,339 KB (2 million 250 thousand numbers) have been compressed down to 52 KB providing the compression ratio C = 333.

BCA of multivariate functions by generalized polynomials and approximants of other classes was successfully applied for finding approximate solutions to systems of incompatible linear equations, for finding analytical approximate solutions of linear differential boundary value problems and initial boundary value problems of mathematical physics, for solving linear Fredholm integral equations by minimizing the maximum integral residual, and in other problems [37].

It was also used in solving problems of calculating the structural strength characteristics of reinforced concrete floors taking into account the conditions of precast slabs. The results of these works in 2017 were presented at two International scientific and practical conferences in Kharkov and Philadelphia (USA) and received positive assessments and certificates [38, 39].

Current work focuses on extending the BCA toolkit use for solving new classes of application problems. 4

Conclusion

Obtaining for a number of applications more accurate solutions in comparison with other known methods confirms the relevance and efficiency of BCA tools. Thus, BCA can be reasonably recommended for solving other classes of application problems.

BCA efficiency in compression of big and extra big arrays of numerical data with high accuracy and compression ratio provides several benefits such as storage resource saving, noise tolerance, high data delivery speed in communication networks, including the grid infrastructures of distributed computing, and guaranteed accuracy of data recovery.

Multiple applications of the BCA toolkit both confirmed its high efficiency and helped in its further improvement and development.

GIC work on solving complex optimization problems, computation accuracy and performance optimization for various classes of application problems including the algorithms and software of Best Chebyshev Approximation put important contribution to the computer technology progress. 5. Steifel, E.: Note on Jordan elimination, linear programming and Tchebycheff approximation. Numerische Mathematik 2( 1 ), 1–17 (1960). 6. Stechkin S.B., Subbotin Y.N.: Splines in Computational Mathematics [in Russian]. Nauka,

Moscow (1976). 7. Cody, W.J., Stoer, J.: Rational Chebyshev approximation using interpolation. Numerische

Mathematik 9( 3 ), 177–188 (1966). 8. Remez, E.Y.: Special topics of numerical construction of solutions to problems of the Chebyshev approximation [in Russian]. In Proc. IV All-Union Mathematical Congress in Leningrad 07/10/1961, vol. 2 (1964). 9. Alexandrenko, V.L., Kalenchuk-Porkhanova, A.A.: The program of polynomial approximation of functions is one of the variants of the E.Ya. Remez’ method [in Russian]. In Collection of standard routines for the Ural machine, pp. 9-41. KVIRTU, Kiev (1962). 10. Alexandrenko, V.L.: An algorithm for constructing an approximate uniformly-best solution to a system of incompatible linear equations [in Russian]. In Algorithms and Algorithmic Languages, 3, 57–74. CC AS USSR, Moscow (1968). 11. Porkhanova, A.A.: Chebyshev approximation by rational expressions [in Russian]. In Comput. mathematics in modern times of scientific-techn. progress, pp. 300–308. Znannia, Kiev (1974). 12. Kalenchuk-Porkhanova, A.A.: Algorithms and error analysis of the best Chebyshev approximation of a function of one variable [in Russian]. In Proc. Theory of approximation of functions, Kaluga, June 24–28, 1975, pp. 213–218. Moscow (1977). 13. Ivanov, V.V., Kalenchuk, A.A.: On the efficiency of algorithms for polynomial and fractional rational Chebyshev approximations [in Russian]. In Proc. Constructive theory of functions, pp. 72–77. Sofia (1983). 14. Kalenchuk-Porkhanova, A.A.: Approximation of functions of one and many variables [in Russian]. In Numerical methods for multiprocessor computing complex of the ES, pp. 366–395. Zhukovsky AFEA, Moscow (1987). 15. Kalenchuk-Porkhanova, A.A.: Approximation apparatus for the analysis and synthesis of complex systems [in Russian]. In Proc. 50 years of V.M. Glushkov Institute of Cybernetics of the National Academy of Sciences of Ukraine, pp. 354–361. GIC NASU, Kiev, 2008. 16. Nathanson, I.P.: Constructive theory of functions [in Russian], pp. 49, 50–56.

Gostekhizdat, Moscow-Leningrad (1949). 17. Akhiezer, N.M.: Lectures on the theory of approximation [in Russian], pp. 64–66. Nauka,

Moscow (1965). 18. Bakhvalov, N.S.: On stable computation of polynomials [in Russian]. Computational

Mathematics and Mathematical Physics, 2(6), 1568–1574 (1971). 19. Ralston, A.: Rational Chebyshev approximation by Remez algorithm. Numerische

Mathematik, 7( 4 ), 322–330 (1965). 20. Werner, H., Stoer, J., Bommas, W.: Rational Chebyshev approximation. Numerische

Mathematik, 10( 4 ), 289–306 (1967). 21. Babich, M.D., Ivanov, B.B.: Estimation of the total error in solving linear operator equations by simple iteration [in Russian]. Computational Mathematics and Mathematical Physics, 7(5), 988–1000 (1967). 22. Porkhanova, A.A.: On the study of the total error of the polynomial Chebyshev approximation [in Russian]. In Problems of accuracy and efficiency of computational algorithms, 5, 127–137, IC AS UkrSSR, Kiev (1969). 23. Kalenchuk-Porkhanova, A.A.: Analysis of error estimates for algorithms of the Chebyshev approximation. Problems of optimization and organization of calculations [in Russian].

RDNTP, Kiev (1974).

References

1. Chebyshev , P.L. : Full composition of writings [in Russian] . AS USSR , Moscow, vol. 2 , pp. 23 - 51 , vol. 2 , pp. 151 - 235 , vol. 3 , pp. 240 - 255 ( 1947 ).

2. Remez , E.Y.: On sequential interpolation method [in Russian] . Ukrains'kyi Matematychnyi Zhurnal , 12 ( 2 ), 170 - 179 ( 1960 ).

3. Remez , E.Y.: Fundamentals of numerical methods of the Chebyshev approximation [in Russian]. Naukova Dumka , Kiev ( 1969 ).

4. Zukhovitsky S.I. : Algorithm for solving the Chebyshev approximation problem in the case of a finite system of incompatible linear equations [in Russian] . Proceedings of the USSR Academy of Sciences , 79 ( 4 ), 561 - 564 ( 1951 ).

24. Zadiraka , V.K. : Theory of computing Fourier transforms [in Russian]. Naukova Dumka , Kiev ( 1983 ).

25. Mikhalevich , V.S. , Sergienko , I.V. , Zadiraka , V.K. , Babich , M.D.: On the issue of computing optimization . Cybernetics and System Analysis , 30 ( 2 ), 65 - 94 ( 1994 ).

26. Khimich , A.N. , Nikolaevskaya , E.A. : Reliability analysis of computer solutions of systems of linear algebraic equations with approximate initial data . Cybernetics and Systems Analysis , 44 ( 6 ), 863 - 874 ( 2008 ).

27. Kalenchuk-Porkhanova , A.A. : Best Chebyshev approximation of functions of one and many variables . Cybernetics and systems analysis , 45 ( 6 ), 988, pp. 155 - 164 ( 2009 ).

28. Sergienko , I.V. , Khimich , A.N. , Yakovlev , M.F. : Methods for obtaining reliable solutions to systems of linear algebraic equations . Cybernetics and Systems Analysis , 47 ( 1 ), 62 - 73 ( 2011 ).

29. Kalenchuk-Porkhanova , A.A. : Ways to increase the efficiency of calculations using the apparatus of the best Chebyshev approximation [in Russian] . In Proc. High performance computing (HPC-UA) , Kiev, pp. 195 - 202 ( 2012 ).

30. Sergienko , I.V. , Shilo , V.P. : Modern approaches to solving complex discrete optimization problems . J. of Automation and Information Sciences , 48 ( 1 ), 15 - 24 ( 2016 ).

31. Vakal , L.P. : Seeking Optimal Knots for Segment Approximation . J. of Automation and Information Sciences , 48 ( 11 ), 68 - 75 ( 2016 ).

32. Vakal , L.P. , Kalenchuk-Porkhanova , A.A. , Vakal , E.S.: Increasing the efficiency of Chebyshev segment fractional rational approximation . Cybernetics and Systems Analysis , 53 ( 5 ), 759 - 765 ( 2017 ).

33. Demyanov , V.F. , Malozemov , V.N. : Introduction to minimax [in Russian] . Nauka , Moscow ( 1972 ).

34. Berdyshev , V.I. , Petrak , L.V. : Function approximation, numerical information compression, applications [in Russian]. UrD RAS , Yekaterinburg ( 1999 ).

35. Kalenchuk-Porkhanova , A.A. : Modeling Flow States in Water Bodies Cybernetics and Systems Analysis , 55 ( 4 ), 683 - 691 ( 2019 ).

36. Kalenchuk-Porkhanova , A.A. , Vakal L.P.: The approximation apparatus as part of supercomputer software with cluster architecture [in Russian] . Iskustvennyi Intellekt , 1 , 158 - 165 ( 2009 ).

37. Vakal , L.P. , Kalenchuk-Porkhanova , A.A. , Vakal , E.C. : The use of Chebyshev approximations in solving mixed problems for partial differential equations [in Russian] . Bulletin of KNTU , 42 ( 3 ), 119 - 123 ( 2011 ).

38. Azizov , Т., Melnyk , О., Orlova , О., Kalenchuk-Porkhanova , A. , Vakal , L. : According to the calculation of reinforced concrete ceilings taking into account the change in torsional stiffness of prеfabricated plates against the formation of normal cracks . Theoretical & Applied Science , 49 ( 5 ), 180 - 189 ( 2017 ).

39. Azizov , T. , Melnyk , O. , Orlova , O. , Kalenchuk-Porkhanova , A. , Vakal , L. : Calculation of reinforced concrete ceilings with normal cracks accounting of Chebyshev approximation . In Proc. 6th Int. Sc. Conf. Transbud , Kharkiv, Ukraine, 15 - 21 April, 2017 . МАТЕС Web of Conferences , vol. 116 , 02002 ( 2017 ).