Адаптивне обчислення довжин кривих, які задаються недиференційовними функціями

image_print
DOI https://doi.org/10.15407/pmach2020.01.065
Журнал Проблеми машинобудування
Видавець Інститут проблем машинобудування ім. А. М. Підгорного Національної академії наук України
ISSN 0131-2928 (print), 2411-0779 (online)
Випуск Том 23, № 1, 2020 (березень)
Сторінки 65–72

 

Автори

Г. А. Шелудько, Інститут проблем машинобудування ім. А. М. Підгорного НАН України (61046, Україна, м. Харків, вул. Пожарського, 2/10)

С. В. Угрімов, Інститут проблем машинобудування ім. А. М. Підгорного НАН України (61046, Україна, м. Харків, вул. Пожарського, 2/10), e-mail: sugrimov@ipmach.kharkov.ua, ORCID: 0000-0002-0846-4067

 

Анотація

Вимірювання довжин кривих є достатньо поширеним під час розв’язання різних задач. Якщо функція, що задає криву, є диференційовною, то обчислення довжини є досить простою математичною операцією. За відсутності початкової інформації про функцію доводиться застосовувати наближені методи. Який з цих методів за наявності конкретної функції доцільно використати, звичайно вирішує користувач, враховуючи клас функції та існуючий в його розпорядженні арсенал можливостей. Одним із важливих факторів, що впливають на вибір методу,  є наявний ресурс часу на попередній аналіз функції та узгодження з початковими даними, які включають необхідну точність результату і загальні числові витрати. У статті пропонується метод, що ґрунтується на апостеріорному підході до проблеми, коли аналіз характеру поведінки функції здійснюється саме в процесі наближеного вимірювання довжини кривої в заданій області. Такий спосіб став можливим завдяки введенню покрокового адаптивного механізму, що реагує на відхилення кривої функції від її апроксимуючої ламаної. В кінцевому підсумку прийнятий локальний аналіз внаслідок адаптації дозволив проходити ділянки з великою крутістю кривої з малим кроком, а пологі – з великим. За особливо різкої зміни функції (наприклад, в підобластях з особливостями) основний адаптивний механізм наділений можливістю виходу за межі прийнятого набору констант без серйозних ускладнень алгоритму. Таким чином, відпала необхідність в попередньому дослідженні характеру поведінки функції, не обов’язково регулярній, та виявленні особливостей (зломи, екстремальні точки і т.п.), їх числа і місця. Для обчислення довжини кривої достатньо задати функцію на даній області і необхідну точність, обмежену мінімальним кроком, не піклуючись про використання якихось допоміжних таблиць та вагових коефіцієнтів. Проведений чисельний експеримент на тестовому наборі функцій різної складності показав перевагу запропонованого підходу над сітковими методами, особливо з рівновіддаленими вузлами.

 

Ключові слова: недиференційовна функція, кусково-лінійне наближення, адаптивний покроковий вибір вузлів, індекс ефективності.

 

Література

  1. Шор Н. З. Методы минимизации недифференцируемых функций и их приложения. Киев: Наук. думка, 1979. 200 с.
  2. Демьянов В. Ф., Виноградова Т. К., Никулина В. Н. Недифференцируемая оптимизация. Л.: Изд-во Ленингр. ун-та, 1982. 324 с.
  3. Гупал А. М. Минимизация недифференцируемых функций. Автоматика и телемеханика. 1974. № 4. С. 61–64.
  4. Шелудько Г. А., Угримов С. В. Адаптивная гибридизация. Х.: Міськдрук, 2011. 308 с.
  5. Форсайт Дж., Малькольм М., Моулер К. Mашинные методы математических вычислений. М.: Мир, 1980. 280 с.
  6. Крылов А. Н. Лекции о приближенных вычислениях. М.: Гостехиздат, 1954. 98 с.
  7. Мелентьев П. В. Приближенные вычисления. М.: Физматгиз, 1962. 388 с.
  8. Чебышев П. Л. О функциях, мало удаляющихся от нуля при некоторых величинах переменных: в 5 т. Т. 3: Математический анализ. 1948. 412 с.
  9. Бахвалов Н. С. Об алгоритмах выбора шага интегрирования. Вычисл. методы и программирование. 1966. Вып. 5. С. 33–38.
  10. Runge C. Über empirische funktionen und die interpolation zwischen äquidistanten en ordinaten . Zeitschriftfür Mathematik und Physik. 1901. Vol. 46. P. 224–243.
  11. Гинзбург Б. Л. Формулы численных квадратур, наиболее выгодные для применения. Уcп. мат. наук. 1954. Т. 9. Вып. 2 (60). С. 137–142.
  12. Бахвалов Н. С., Жидков Н. П., Кобельков Г. М. Численные методы. М.: БИНОМ. Лаборатория знаний, 2018. 636 с.
  13. Sheludko G. A., Ugrimov S. V. Modernization adaptive piecewise linear approximation of difficult-to-compute functions. J. Mech. Eng. 2018. Vol. 21. No. 2. P. 60–67.
  14. Пукк Р. А. Алгоритм интегрирования, учитывающий степень гладкости функций. Изв. АН ЭССР. Физика. Математика. 1970. Т. 19, № 3. С. 368–370.
  15. Беллман Р. Процессы регулирования с адаптацией. М: Мир, 1964. 360 с.
  16. Gander W., Gautschi W. Adaptive quadrature – revisited. BIT Numerical Math. 2000. Vol. 40. Iss. 1. P. 84–101. https://doi.org/10.1023/A:1022318402393.
  17. Шелудько Г. А. Адаптивное интегрирование. АН Украины. Ин-т проблем машиностроения. Харьков. 1973. 12 с. Деп. ВИНИТИ 26.07.73. № 7753.
  18. Шелудько Г. А., Угримов С. В. Адаптивные решения некоторых задач вычислительной математики. Харьков: Ин-т проблем машиностроения АН Украины, 1997. 37 с.
  19. McKeeman W. M. Algorithm 145: adaptive integration bi Simpson¢s rule. Communication of the Association for Computing Machinery. 1962. Vol. 5. Iss. 12. P. 604. https://doi.org/10.1145/355580.369102.
  20. Рабинович Е. В., Рубан А. А., Цапенко М. П., Шефель Г. С. Адаптивная кусочно-линейная аппроксимация. Автометрия. 1993. № 1. С. 26–29.
  21. Shekel J. Test functions for multi-modal search techniques. Proc. 5th Annu. Princeton Conf. Inform. Sci. and Syst. 1971. P. 354–359.
  22. Шелудько Г. А., Шупіков О. М., Сметанкіна Н. В., Угрімов С. В. Прикладний адаптивний пошук. Х.: Око, 2001. 191 с.
  23. Островский А. М. Решение уравнений и систем уравнений. М.: Изд-во иностр. лит., 1963. 219 с.

 

Надійшла до редакції 07 лютого 2020 р.

Прийнята до друку