Adaptive Computation of Curve Lengths Given by Non-differentiable Functions
Keywords:
non-differentiable function, piecewise linear approximation, adaptive peace-wise selection of nodes, efficiency indexAbstract
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.References
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.
Demyanov, V. F., Vinogradova, T. K., & Nikulina, V. N. (1982). Nedifferentsiruyemaya optimizatsiya [Non-differentiable optimization].Leningrad: Izdatelstvo Leningradskogo universiteta, 324 p. (in Russian).
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).
Sheludko, H. A. & Ugrimov, S. V. (2011). Adaptivnaya gibridizatsiya [Adaptive hybridisation].Kharkov: Miskdruk, 308 p. (in Russian).
Forsythe, G. E., Malcolm, M. A., & Moler, C. B. (1977). Computer methods for mathematical computations.EnglewoodCliffs,New Jersey: Prentice-Hall, 259 p.
Krylov, A. N. (1954). Lektsii o priblizhennykh vychisleniyakh [Lectures on approximate calculations].Moscow: Gostekhizdat, 98 p. (in Russian).
Melentyev, P. V. (1962). Priblizhennyye vychisleniya [Approximate calculations].Moscow: Fizmatgiz, 388 p. (in Russian).
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).
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).
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).
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).
Bakhvalov, N. S., Zhidkov, N. P., & Kobelkov, G. M. (2018). Chislennyye metody [Numerical methods].Moscow: BINOM, Laboratoriya znaniy, 636 p. (in Russian).
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.
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).
Bellman, R. E. (2015). Adaptive control processes: A guided tour. Princeton:PrincetonUniversityPress, 274 p.
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.
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).
Sheludko, G. A. & Ugrimov, S. V. (1997). Adaptivnyie resheniya nekotorykh zadach vyichislitelnoy matematiki [Adaptive solutions to some problems of computational mathematics].Kharkov:Institute ofMechanical Engineering Problems of NASU, 37 p. (in Russian).
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.
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).
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.
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).
Ostrovskiy, A. M. (1966). Solutions of equations and systems of equations.New York: Academic Press, 338 p.
Downloads
Published
Issue
Section
License
Copyright (c) 2020 Serhii V. Ugrimov, Helii A. Sheludko
This work is licensed under a Creative Commons Attribution-NoDerivatives 4.0 International License.
All authors agree with the following conditions:
- The authors reserve the right to claim authorship of their work and transfer to the journal the right of first publication of the work under the license agreement (the agreement).
- Authors have a right to conclude independently additional agreement on non-exclusive spreading the work in the form in which it was published by the jpurnal (for example, to place the work in institution repository or to publish as a part of a monograph), providing a link to the first publication of the work in this journal.
- Journal policy allows authors to place the manuscript in the Internet (for example, in the institution repository or on a personal web sites) both before its submission to the editorial board and during its editorial processing, as this ensures the productive scientific discussion and impact positively on the efficiency and dynamics of citation of published work (see The Effect of Open Access).
