Адаптивне обчислення довжин кривих, які задаються недиференційовними функціями
Ключові слова:
недиференційовна функція, кусково-лінійне наближення, адаптивний покроковий вибір вузлів, індекс ефективностіАнотація
Вимірювання довжин кривих є достатньо поширеним під час розв’язання різних задач. Якщо функція, що задає криву, є диференційовною, то обчислення довжини є досить простою математичною операцією. За відсутності початкової інформації про функцію доводиться застосовувати наближені методи. Який з цих методів за наявності конкретної функції доцільно використати, звичайно вирішує користувач, враховуючи клас функції та існуючий в його розпорядженні арсенал можливостей. Одним із важливих факторів, що впливають на вибір методу, є наявний ресурс часу на попередній аналіз функції та узгодження з початковими даними, які включають необхідну точність результату і загальні числові витрати. У статті пропонується метод, що ґрунтується на апостеріорному підході до проблеми, коли аналіз характеру поведінки функції здійснюється саме в процесі наближеного вимірювання довжини кривої в заданій області. Такий спосіб став можливим завдяки введенню покрокового адаптивного механізму, що реагує на відхилення кривої функції від її апроксимуючої ламаної. В кінцевому підсумку прийнятий локальний аналіз внаслідок адаптації дозволив проходити ділянки з великою крутістю кривої з малим кроком, а пологі – з великим. За особливо різкої зміни функції (наприклад, в підобластях з особливостями) основний адаптивний механізм наділений можливістю виходу за межі прийнятого набору констант без серйозних ускладнень алгоритму. Таким чином, відпала необхідність в попередньому дослідженні характеру поведінки функції, не обов’язково регулярній, та виявленні особливостей (зломи, екстремальні точки і т.п.), їх числа і місця. Для обчислення довжини кривої достатньо задати функцію на даній області і необхідну точність, обмежену мінімальним кроком, не піклуючись про використання якихось допоміжних таблиць та вагових коефіцієнтів. Проведений чисельний експеримент на тестовому наборі функцій різної складності показав перевагу запропонованого підходу над сітковими методами, особливо з рівновіддаленими вузлами.Посилання
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.
##submission.downloads##
Опубліковано
Номер
Розділ
Ліцензія
Авторське право (c) 2020 Serhii V. Ugrimov, Helii A. Sheludko
Ця робота ліцензується відповідно до Creative Commons Attribution-NoDerivatives 4.0 International License.
Автори, які публікуються в цьому журналі, погоджуються з наступними умовами:
- Автори залишають за собою право на авторство своєї роботи і передають журналу право першої публікації цієї роботи на умовах ліцензійного договору (угоди).
- Автори мають право самостійно укладати додаткові договори (угоди) з неексклюзивного поширення роботи в тому вигляді, в якому вона була опублікована цим журналом (наприклад, розміщувати роботу в електронному сховищі установи або публікувати в складі монографії), за умови збереження посилання на першу публікацію роботи в цьому журналі.
- Політика журналу дозволяє розміщення авторами в мережі Інтернет (наприклад, у сховищах установи або на персональних веб-сайтах) рукопису роботи як до подачі цього рукопису в редакцію, так і під час її редакційної обробки, оскільки це сприяє виникненню продуктивної наукової дискусії і позитивно позначається на оперативності та динаміці цитування опублікованої роботи (див. The Effect of Open Access).
