MODERNIZATION ADAPTIVE PIECEWISE LINEAR APPROXIMATION OF DIFFICULT-TO-COMPUTE FUNCTIONS

Authors

G. A. Sheludko, A. Podgorny Institute of Mechanical Engineering Problems of NASU (2/10, Pozharsky str., Kharkiv, 61046, Ukraine)

S. V. Ugrimov, A. Podgorny Institute of Mechanical Engineering Problems of NASU (2/10, Pozharsky str., Kharkiv, 61046, Ukraine), e-mail: sugrimov@ipmach.kharkov.ua, ORCID: 0000-0002-0846-4067

Abstract

The solution of many theoretical and applied problems requires that some functional dependencies be substituted into others, which are more convenient for the implementation of a specific mathematical problem. At the same time, information about the character of the original function can be insufficient, and the function itself can be considered to be difficult to compute. The accuracy of such an approximation depends on the methods used, the character of the original function, as well as the number and choice of grid points. The easiest way of building such an approximation is doing it on a uniform grid of points, which does not always provide an acceptable result. The purpose of this paper is to develop effective adaptive methods of approximating functions for the problems aimed at searching for the lengths of curves and calculating integrals under conditions of limited information about the character of the original function and the presence of its derivatives. An adaptive approach to the approximation of a wide class of one-dimensional functions is proposed in the paper. For this approximation a piecewise linear approximation with a simple mechanism of exponential adaptive feedback step process control is used. The possibilities of this approach are considered, using the problems of calculating the lengths of curves and values of definite integrals. The specifics of the application of the suggested approach are detailed for each case. The approach does not require an initial allocation of grid points. The method ensures the required accuracy in automatic mode. The result is realized in a single pass without any preliminary transformations. The reliability of the obtained results is confirmed by solving the known test examples. The results of calculating a number of definite integrals with different nature of integrand are presented. The calculation results by the proposed method are compared with the data obtained by the usual trapezoid method. A high efficiency of the proposed approach is established. The proposed method opens the way for creating effective means for solving numerical integration and differentiation problems, as well as integral and differential equations and so on.

Keywords: approximation, interpolation, piecewise linear approximation, difficult-to-compute function, efficiency index

Full text: Download in PDF

References

1. Ostrovskiy, A. M. (1966). Solutions of equations and systems of equations, 2nd ed. New York: Academic Press.
2. Krylov, A. N. (1954). Lektsii o priblizhennykh vychisleniyakh [Lectures on approximate calculations]. Moscow: Gostekhizdat (in Russian).
3. Weiershtrass, K. (1885). Über die analytische Darstellbarkeit sogenannter willkürlicher Funktionen einer reelen Veränderlichn. Sitzungsberichte der Berliner Akademie der Wissenschaften, pp. 633–639.
4. Mhaskar, H. N. & Pai, D. V. (2000). Fundamentals of approximation theory. New Delhi: Narosa Publishing House.
5. Trefethen, L. N. (2013). Approximation theory and approximation practice. Oxford: Oxford University.
6. Richardson, L. F. (1911). The approximate arithmetical solution by finite differences of physical problems involving differential equations, with an application to the stresses in a masonry dam. Philosophical Transactions of the Royal Society of London, Ser. A, vol. 210, pp. 307–357. https://doi.org/10.1098/rsta.1911.0009
7. Runge, C. (1901). Über empirische funktionen und die interpolation zwischen äquidistanten en ordinaten. Zeitschrift für Mathematik und Physik, vol. 46, pp. 224–243.
8. Chebyshev, P. L. (1881). O funktsiyakh, malo uklonyayushchikhsya ot nulya pri nekotorykh velichinakh peremennykh. Sobranie sochineniy [On functions deviating least from zero at some values of variables. Col. works]. Vol. 3, pp. 108–127 (in Russian).
9. Faber, G. (1914) Über die interpolatiorische darstellung stetiger funktionen. Deutsche Mathematiker-Vereinigung Jahresbeucht, vol. 23, pp. 192–210.
10. Marcinkiewicz, J. (1939). Sur interpolation d`operations. Comptes rendus de l’Académie des Sciences, vol. 208, pp. 1272–1273.
11. Bernshteyn, S. N. (1937). O mnogochlenakh ortogonalnykh v konechnom intervale [On orthogonal polynomials in a finite interval]. Kharkov: Gos. nauch.-tekhn. izd-vo Ukrainy (in Russian).
12. Ahlberg, J. H., Nilson, E. N., & Walsh, J. L. (1967). The theory of splines and their applications. New York and London: Academic Press.
13. Popov, B. A. & Tesler, G. S. (1984). Priblizhenie funktsiy splaynami [Approximation of functions by splines] Kiev: Nauk. dumka (in Russian).
14. Rvachev, V. L. & Rvachev, V. A. (1975). Atomarnye funktsii v matematicheskoy fizike. Matematizatsiya znaniy i nauch.-tekhn. progress [Atomic Functions in Mathematical Physics. Knowledge Mathematization, and Scientific and Technical Progress]. Kiev: Nauk. dumka, pp. 188–199 (in Russian).
15. Ryabenkiy, V. S. (1974). Lokalnye formuly gladkogo vospolneniya i gladkoy interpolyatsii po ikh znacheniyam v uzlakh neravnomernoy pryamougolnoy setki [Local formulae for smooth replacement and interpolation by their values in non-uniform rectangular grid nodes]. Moscow: In-t problem matematiki Akademiyi nauk SSSR, 42 p. (Preprint. Akademiya nauk SSSR. In-t problem matematiki; 21) (in Russian).
16. Bos, L., De Marchi, S., Hormann, K., & Klein, G. (2012). On the Lebesgue constant of barycentric rational interpolation at equidistant nodes. Numerische Mathematik, vol. 121, iss. 3, pp. 461–471. https://doi.org/10.1007/s00211-011-0442-8
17. Bellman, R. E. (2016). Adaptive control processes. A guided tour. Princeton legacy library.
18. Bahvalov, N. S. (1966). Ob algoritmakh vybora shaga integrirovaniya [On algorithms for selecting integration steps]. Vychisl. metody i programmirovanie – Computational methods and programming, iss. 5, pp. 3–8 (in Russian).
19. Pukk, R. A. (1970). Algoritm integrirovaniya, uchityvayushchiy stepen gladkosti funktsiy [Integration algorithm taking into account degree of function smoothness]. Izv. AN ESSR. Fizika. Matematika – Proceedings of AS of ESSR. Physics. Mathematics, vol. 19, no. 3, pp. 368–370 (in Russian).
20. Sheludko, G. A. (1973). Adaptivnoe integrirovanie [Adaptive integration]. Kharkov: Academy of Science of USSR, In-t problem mashinostroeniya, 12 p. Dep. VINITI 26.07.73, no. 7753 (in Russian).
21. Sheludko, H. A. & Ugrimov, S. V. (1997). Adaptivnyie resheniya nekotorykh zadach vyichislitelnoy matematiki [Adaptive solutions to some problems of computational mathematics]. Kharkov: National Academy of Science of Ukraine, In-t problem mashinostroeniya, 37 p. (in Russian).
22. Gander, W. & Gautschi, W. (2000). Adaptive quadrature – revisited. BIT Numerical Mathematics, vol. 40, iss. 1, pp. 84–101. https://doi.org/10.1023/A:1022318402393
23. Forsythe, G. E., Malcolm, M. A., & Moler, C. B. (1977). Computer methods for mathematical computations. Englewood Cliffs, New Jersey: Prentice-Hall, 259 p.
24. Mathews, J. & Fink, K. (2004). Numerical methods using Matlab. 4nd ed. New Jersey: Prentice-Hall, 696 p.
25. Sheludko, H. A. & Ugrimov, S. V. (2011). Adaptivnaya gibridizatsiya [Adaptive hybridisation]. Kharkov: Miskdruk, 308 p. (in Russian).
26. Abramowitz, M. & Stegun, I. A. (Eds.) (1972). Handbook of mathematical functions with formulas, graphs, and mathematical tables. New York: Dover Publication.

Received 16 March 2018

Published 30 June 2018