Adaptive Computation of Curve Lengths Given by Non-differentiable Functions

image_print
DOI https://doi.org/10.15407/pmach2020.01.065
Journal Journal of Mechanical Engineering – Problemy Mashynobuduvannia
Publisher A. Podgorny Institute for Mechanical Engineering Problems
National Academy of Science of Ukraine
ISSN 0131-2928 (Print), 2411-0779 (Online)
Issue Vol. 23, no. 1, 2020 (March)
Pages 65-72
Cited by J. of Mech. Eng., 2020, vol. 23, no. 1, pp. 65-72

 

Authors

Helii A. Sheludko, A. Podgorny Institute of Mechanical Engineering Problems of NASU (2/10, Pozharskyi St., Kharkiv, 61046, Ukraine)

Serhii V. Ugrimov, A. Podgorny 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

Measurement of the lengths of curves is quite common in solving various problems. If the function that defines the curve is differentiable, then computing the curve length is a relatively simple mathematical operation. In the absence of initial information about the function, it is necessary to apply approximate methods. Which of these methods should be used for a particular function is usually decided by the user. One of the important factors influencing the choice of the method is the available time resource for the preliminary analysis of the function and for the coordination with the initial data that include both the necessary accuracy of the result and the total numerical costs. The article proposes a method based on an a posteriori approach to the problem, where the analysis of the behavior of the function is carried out in the process of an approximate measurement of the length of the curve in a given area. This method became possible thanks to the introduction of an incremental adaptation mechanism that responds to the deviation of the function curve from the broken line approximating it. As a result, the local analysis accepted as a result of the adaptation made it possible to pass the large steepness segments of the curve in small increments and the flat segments, with large ones. With a particularly sharp change in the function (for example, in sub-domains with singularities), the main adaptation mechanism is able to go beyond the boundaries of the adopted set of constants without serious complications of the algorithm. Thus, there has disappeared the need both for a preliminary analysis of the behavior of the function, not necessarily regular, and the identification of singularities (kinks, extreme points, etc.), their numbers and locations. In order to compute the length of the curve, it is enough to set the function on this area and the required accuracy, limited by the minimum increment, without worrying about using some auxiliary tables and weight factors. The numerical experiment conducted on a test set of functions of varying complexity showed the advantage of the proposed approach over grid methods, especially with equally spaced nodes.

 

Keywords: non-differentiable function, piecewise linear approximation, adaptive peace-wise selection of nodes, efficiency index.

 

Full text: Download in PDF

 

References

  1. Shor, N. Z. (1985). Minimization methods for non-differentiable functions. Berlin: Springer-Verlag, 178 p. https://doi.org/10.1007/978-3-642-82118-9.
  2. Demyanov, V. F., Vinogradova, T. K., & Nikulina, V. N. (1982). Nedifferentsiruyemaya optimizatsiya [Non-differentiable optimization]. Leningrad: Izdatelstvo Leningradskogo universiteta, 324 p. (in Russian).
  3. Gupal, A. M. (1974). Minimizatsiya nedifferentsiruyemykh funktsiy [Minimization of non-differentiable functions]. Avtomatika i telemekhanika – Automation and Telemechanics., no. 4, pp. 61–64 (in Russian).
  4. Sheludko, H. A. & Ugrimov, S. V. (2011). Adaptivnaya gibridizatsiya [Adaptive hybridisation]. Kharkov: Miskdruk, 308 p. (in Russian).
  5. Forsythe, G. E., Malcolm, M. A., & Moler, C. B. (1977). Computer methods for mathematical computations. Englewood Cliffs, New Jersey: Prentice-Hall, 259 p.
  6. Krylov, A. N. (1954). Lektsii o priblizhennykh vychisleniyakh [Lectures on approximate calculations]. Moscow: Gostekhizdat, 98 p. (in Russian).
  7. Melentyev, P. V. (1962). Priblizhennyye vychisleniya [Approximate calculations]. Moscow: Fizmatgiz, 388 p. (in Russian).
  8. Chebyshev, P. L. (1948). O funktsiyakh, malo uklonyayushchikhsya ot nulya pri nekotorykh velichinakh peremennykh [On functions that deviate little from zero for some variables]: in 5 vols. Vol. 3, pp. 110–127 (in Russian).
  9. Bakhvalov, N. S. (1966) Ob algoritmakh vybora shaga integrirovaniya [On algorithms for selecting the integration step]. Vychisl. metody i programmirovanie – Computational Methods and Programming, iss. 5, pp. 33–38 (in Russian).
  10. Runge, C. (1901). Über empirische funktionen und die interpolation zwischen äquidistanten en ordinaten [About empirical functions and the interpolation between equidistant ordinates]. Zeitschriftfür Mathematik und Physik – Journal of Mathematics and Physics,  vol. 46, pp. 224–243. (in German ).
  11. Ginzburg, B. L. (1954). Formuly chislennykh kvadratur, naiboleye vygodnyye dlya primeneniya [The most advantageous of numerical quadrature formulas]. Uspekhi matematicheskikh nauk – Advances in Mathematical Sciences, vol. 9, iss. 2 (60), pp. 137–142 (in Russian).
  12. Bakhvalov, N. S., Zhidkov, N. P., & Kobelkov, G. M. (2018). Chislennyye metody [Numerical methods]. Moscow: BINOM, Laboratoriya znaniy, 636 p. (in Russian).
  13. Sheludko, G. A. & Ugrimov, S. V. (2018). Modernization adaptive piecewise linear approximation of difficult-to-compute functions. J. Mech. Eng., vol. 21, no. 2, pp. 60–67. https://doi.org/10.15407/pmach2018.02.060.
  14. Pukk, R. A. (1970). Algoritm integrirovaniya, uchityvayushchiy stepen gladkosti funktsiy [Integration algorithm taking into account the degree of smoothness of functions]. Izv. AN ESSR. Fizika. Matematika – Proceedings of the AS ESSR. Physics. Mathematics, vol. 19, no. 3, pp. 368–370 (in Russian).
  15. Bellman, R. E. (2015). Adaptive control processes: A guided tour. Princeton: Princeton University Press, 274 p.
  16. Gander, W. & Gautschi, W. (2000). Adaptive quadrature – revisited. BIT Numerical Math., vol. 40, iss. 1, pp. 84–101. https://doi.org/10.1023/A:1022318402393.
  17. Sheludko, G. A. (1973). Adaptivnoe integrirovanie [Adaptive integration]. Kharkov: Institute of Mechanical Engineering Problems of USSR Academy of Science, 12 p. Dep. VINITI 26.07.73, no. 7753 (in Russian).
  18. Sheludko, G. A. & Ugrimov, S. V. (1997). Adaptivnyie resheniya nekotorykh zadach vyichislitelnoy matematiki [Adaptive solutions to some problems of computational mathematics]. Kharkov: Institute of Mechanical Engineering Problems of NASU, 37 p. (in Russian).
  19. McKeeman, W. M. (1962). Algorithm 145: Adaptive integration bi Simpson¢s rule. Communication of the Association for Computing Machinery, vol. 5, iss. 12, pp. 604. https://doi.org/10.1145/355580.369102.
  20. Rabinovich, Ye. V., Ruban, A. A., Tsapenko, M. P., & Shefel, G. S. (1993). Adaptivnaya kusochno-lineynaya approksimatsiya [Adaptive piecewise linear approximation]. Avtometriya – Autometry, no. 1, pp. 26–29 (in Russian).
  21. Shekel, J. (1971). Test functions for multi-modal search techniques. Proceedings of the 5th Annual Princeton Conference on Information Science and Systems, pp. 354–359.
  22. 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).
  23. Ostrovskiy, A. M. (1966). Solutions of equations and systems of equations. New York: Academic Press, 338 p.

 

Received 07 February 2020

Published 30 March 2020