An Adaptive Method for Numerical Differentiation of Difficult-to-Compute Functions

Authors

Helii A. Sheludko, A. Pidhornyi Institute of Mechanical Engineering Problems of NASU (2/10, Pozharskyi St., Kharkiv, 61046, Ukraine), ORCID: 0000-0003-4171-9591

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

Abstract

An adaptive approach to the numerical differentiation of difficult-to-compute functions is considered. Complex dependencies, which are the result of multiple superpositions of functions or the product of various algorithmic processes, are knowingly difficult to study directly. To establish the nature of the behavior of such dependencies, one has to resort to numerical analysis. One of the important characteristics of functions is a derivative, which indicates the direction and rate of change of a dependence. However, with difficult-to-compute functions, the available a priori information is not always sufficient to achieve the appropriate accuracy of the solution by known means. The loss of accuracy occurs due to the accumulation of round-off errors that grow in proportion to the number of calculated values of a function. In this case, it is necessary to pass on to the posterior approach in order to determine the behavior of the function and move away from the scheme of equidistant nodes, relying on an adaptive way of studying the local situation in the domain of the function. This paper implements an adaptive method for finding derivatives of a function with a minimum of restrictive requirements for the class of functions and the form of their assignment. Due to this, the costs of calculating the function have been significantly reduced with the result that their number has been brought to almost the optimal level. At the same time, the amount of RAM used has sharply decreased. There is no need for a preliminary analysis of the problem of establishing the class of the function under study, in the involvement of special functions or transformation of initial conditions for using standard tables of weight coefficients, etc. For research, it is enough to assign a continuous and bounded function on a fixed segment and a minimum step, which is indirectly responsible for ensuring the required accuracy of differentiation. The effectiveness of the proposed method is demonstrated on a number of test examples. The developed method can be used in more complex problems, for example, in solving some types of differential and integral equations, as well as for a wide range of optimization problems in a wide variety of areas of applied analysis and synthesis.

Keywords: non-differentiable function, piecewise linear approximation, adaptive step-by-step selection of nodes.

Full text: Download in PDF

References

1. Mhaskar, H. N., Naumova, V., & Pereverzyev, S. V. (2013). Filtered Legendre expansion method for numerical differentiation at the boundary point with application to blood glucose predictions. Applied Mathematics and Computation, vol. 224, pp. 835–847. https://doi.org/10.1016/j.amc.2013.09.015.
2. Sheludko, H. A., Shupikov, O. M., Smetankina, N. V., & Ugrimov, S. V. (2001). Prykladnyy adaptyvnyy poshuk [Applied Adaptive Search]. Kharkiv: Vydavnytstvo ″Oko″, 191 p. (in Ukrainian).
3. Grakovski, A. & Alexandrov A. (2005). Spectral method for numerical calculation of derivatives in digital processing of subsurface radar sounding signals. Mathematical Modelling and Analysis, vol. 10, no. 1, pp. 31–40. https://doi.org/10.1080/13926292.2005.9637268.
4. Zhao, Z. (2021). A Hermite extension method for numerical differentiation. Applied Numerical Mathematics, vol. 159, pp. 46–60. https://doi.org/10.1016/j.apnum.2020.08.016.
5. Il’in, V. P. & Zadorin, A. I. (2019). Adaptive formulas of numerical differentiation of functions with large gradients. Journal of Physics: Conference Series, vol. 1260, iss. 4, pp. 042003-1–042003-7. https://doi.org/10.1088/1742-6596/1260/4/042003.
6. Lu, S. & Pereverzev, S. V. (2006) Numerical differentiation from a viewpoint of regularization theory. Mathematics of Computation, vol. 75, no. 256, pp. 1853–1870. https://doi.org/10.1090/S0025-5718-06-01857-6.
7. Zhao, Z. & You, L. (2021). A numerical differentiation method based on Legendre expansion with super order Tikhonov regularization. Applied Mathematics and Computation, vol. 393. https://doi.org/10.1016/j.amc.2020.125811.
8. Krylov, A. N. (1954). Lektsii o priblizhennykh vychisleniyakh [Lectures on approximate calculations]. Moscow: Gostekhizdat, 98 p. (in Russian).
9. Goncharov, V. L. (1954). Teoriya interpolirovaniya i priblizheniya funktsiy [Theory of interpolation and approximation of functions]. Moscow: Gostekhizdat, 386 p. (in Russian).
10. Melentyev, P. V. (1966). Priblizhennyye vychisleniya [Approximate calculations]. Moscow: Fizmatgiz, 388 p. (in Russian).
11. Chebyshev, P. L. (1948). O funktsiyakh, malo uklonyayushchikhsya ot nulya pri nekotorykh velichinakh peremennykh [On functions that deviate little from zero for some variables]. Complete works: In 5 vols. Vol. 3: Mathematical analysis. Moscow, Leningrad: Izd-vo AN SSSR, pp. 110–127 (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, 284 p.
13. Bellman, R. E., Dreyfus S. E. (2015). Applied Dynamic Programming. Princeton University Press, 390 p.
14. Sheludko, G. A., Strelnikova, Ye. A., & Kantor, B. Ya. (2008). Gibridnyye metody v zadachakh optimalnogo proyektirovaniya. Poiskovyye metody [Hybrid methods in optimal design problems. Search methods]. Kharkov: Novoye slovo, 188 p. (in Russian).
15. Sheludko, H. A. & Ugrimov, S. V. (2011). Adaptivnaya gibridizatsiya [Adaptive hybridisation]. Kharkov: Miskdruk, 308 p. (in Russian).
16. Sheludko, G. A. & Ugrimov, S. V. (2018). Modernization adaptive piecewise linear approximation of difficult-to-compute functions. Journal of Mechanical Engineering – Problemy mashynobuduvannia, vol. 21, no. 2, pp. 60–67. https://doi.org/10.15407/pmach2018.02.060.
17. Bakhvalov, N. S. (1975). Chislennyye metody [Numerical methods]. Moscow: Nauka, 632 p. (in Russian).
18. Ramm, A. G. (1968). O chislennom differentsirovanii [On numerical differentiation]. Izvestiya vuzov. Matematika – News of Universities. Mathematics, no. 11, pp. 131–134 (in Russian).
19. Gill, P. E., Murray, W., & Wright, M. H. (1981). Practical Optimization. London: Academic Press, 401 p.
20. Tikhomirov, V. M. (1986). Rasskazy o maksimumakh i minimumakh [Narratives about maximums and minimums]. Moscow: Nauka, 192 p. (in Russian).
21. Forsythe, G. E., Malcolm, M. A., & Moler, C. B. (1977). Computer methods for mathematical computations. Englewood Cliffs, New Jersey: Prentice-Hall, 259 p.
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. Mathews, J. & Fink, K. (2004). Numerical methods using Matlab. New Jersey: Prentice-Hall, 696 p.
24. Dolgopolova, T. F. & Ivanov, V. K. (1966). O chislennom differentsirovanii [About numerical differentiation]. Zhurnal vychislitelnoy matematiki i matematicheskoy fiziki – Journal of Computational Mathematics and Mathematical Physics, vol. 6, no. 3, pp. 57–71 (in Russian). https://doi.org/10.1016/0041-5553(66)90145-5.
25. Ostrovskiy, A. M. (1966). Solutions of equations and systems of equations. New York: Academic Press, 338 p.

Received 29 March 2021

Published 30 June 2021