Масштабування даних для задачі побудови кривої в натуральній параметризації з кубічною кривиною
The article explores topic of coordinate scaling for linear inequality system in problem of building flat naturally parametrized curve passing through 2 points with given inclinations and curvatures at them. The non-smooth optimization problem presented is equivalent to a system of four...
Збережено в:
| Дата: | 2023 |
|---|---|
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України
2023
|
| Теми: | |
| Онлайн доступ: | https://www.fmmit.lviv.ua/index.php/fmmit/article/view/318 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Physico-mathematical modeling and informational technologies |
| Завантажити файл: |  |
Репозитарії
Physico-mathematical modeling and informational technologies| _version_ | 1867479691314593792 |
|---|---|
| author | Stetsyuk, Petro Khomiak, Olha Zhydkov, Volodymyr |
| author_facet | Stetsyuk, Petro Khomiak, Olha Zhydkov, Volodymyr |
| author_institution_txt_mv | [
{
"author": "Petro Stetsyuk",
"institution": "д. ф.-м. н., Інститут кібернетики імені В.М. Глушкова НАН України, Проспект Академіка Глушкова, 40, 03187, Київ"
},
{
"author": "Olha Khomiak",
"institution": "к. ф.-м.н., Інститут кібернетики імені В.М. Глушкова НАН України, Проспект Академіка Глушкова, 40, 03187, Київ"
},
{
"author": "Volodymyr Zhydkov",
"institution": "аспірант, Інститут кібернетики імені В.М. Глушкова НАН України, Проспект Академіка Глушкова, 40, 03187, Київ"
}
] |
| author_sort | Stetsyuk, Petro |
| baseUrl_str | http://www.fmmit.lviv.ua/index.php/fmmit/oai |
| collection | OJS |
| datestamp_date | 2025-02-21T17:31:10Z |
| description | The article explores topic of coordinate scaling for linear inequality system in problem of building flat naturally parametrized curve passing through 2 points with given inclinations and curvatures at them. The non-smooth optimization problem presented is equivalent to a system of four non-linear equations with four unknowns, which describes the problem of building curve with cubic curvature distribution and its solution method based on Shor’s r-algorithm modification. It is demonstrated, that for finding problem solution with given accuracy for less time it is really better to solve the problem with well scaled coordinates. Correct scaling plays essential role in choosing parameters for iterative modeling fragments of aerodynamic and technical profiles. |
| first_indexed | 2026-06-09T01:10:17Z |
| format | Article |
| fulltext |
123
doi.org/10.15407/fmmit2023.37.123
Масштабування даних для задачі побудови кривої в
натуральній параметризації з кубічною кривиною
Петро Стецюк1, Ольга Хом’як2, Володимир Жидков3
1 д. ф.-м. н., Інститут кібернетики імені В.М. Глушкова НАН України,
Проспект Академіка Глушкова, 40, 03187, Київ, e-mail: stetsyukp@gmail.com
2 к. ф.-м.н., Інститут кібернетики імені В.М. Глушкова НАН України,
Проспект Академіка Глушкова, 40, 03187, Київ, e-mail: khomiak.olha@gmail.com
3 аспірант, Інститут кібернетики імені В.М. Глушкова НАН України,
Проспект Академіка Глушкова, 40, 03187, Київ, e-mail: lynx233@yahoo.com
У статті досліджено питання масштабування для системи нелінійних рівнянь у задачі
побудови плоскої кривої у натуральній параметризації, яка проходить через дві задані
точки та забезпечує в них задані кути нахилу дотичних та задані значення кривин.
Представлена оптимізаційна негладка задача еквівалентна системі чотирьох нелінійних
рівнянь з чотирма невідомими, яка описує задачу побудови необхідної кривої з кубічним
розподілом кривини, та метод її розв’язання на основі модифікації r-алгоритму Шора.
Показано, що для того, щоб знайти розв'язок оптимізаційної задачі із заданою точністю
за менший час краще розв'язувати задачу з добре масштабованими даними. Правильне
масштабування даних відіграє суттєву роль для вибору параметрів при моделюванні
фрагментів аеродинамічних та технічних профілів в ітераційному режимі.
Ключові слова: плоска крива, натуральна параметризація, кубічна
кривина, негладка функція, r-алгоритм.
Вступ. Задачі побудови плоских кривих в натуральній параметризації [1-3]
зводяться до задач знаходження розв'язків систем нелінійних рівнянь, де частина
рівнянь залежать від невідомих параметрів підінтегральних функцій та невідомої
верхньої границі для визначеного інтегралу. Для задачі побудови кривої в
натуральній параметризації з кубічною кривиною в роботах [4, 5] сформульована
система нелінійних рівнянь, відповідна їй задача негладкої оптимізації та
алгоритм її розв'язання. У статті буде досліджено масштабування системи
нелінійних рівнянь, щоб забезпечити розв'язання погано обумовленої
оптимізаційної задачі, тобто коли відношення мінімального за модулем
коефіцієнта кубічного полінома до максимального може становити
12 910 10 .
1. Система нелінійних рівнянь та оптимізаційна задача.
Задача (див. рис. нижче) полягає у наступному. Потрібно так з'єднати точки
( , )A AA x y та ( , )B BB x y кривою лінією у натуральній параметризації, де кривина
3 2( ) =k s as bs cs d має кубічну залежність від довжини дуги, щоб
УДК 519.85
mailto:stetsyukp@gmail.com
mailto:khomiak.olha@gmail.com
Петро Стецюк, Ольга Хом’як, Володимир Жидков
Масштабування даних для задачі побудови кривої в натуральній параметризації …
124
забезпечити в точках A та B задані значення кутів нахилу дотичних
A та
B ,
та задані значення кривин
Ak ,
Bk . Кути вимірюються в радіанах.
Нехай S – довжина кривої від точки A до точки B . Знаходженню
параметрів кривини a , b , c , d та довжини S відповідає система з чотирьох
нелінійних рівнянь та одного лінійного рівняння [4]:
4 3 2
0
= cos
4 3 2
S
B A A
as bs cs
x x d s ds
, (1)
4 3 2
0
= sin
4 3 2
S
B A A
as bs cs
y y d s ds
, (2)
4 3 2
=
4 3 2
B A
aS bS cS
d S , (3)
3 2= , = .A Bk d k aS bS cS d (4)
З лінійного рівняння (4) отримуємо = Ad kе . Для пошуку a е
, bе
, cе , S е
в [5]
використано умовну задачу мінімізації суми модулів функцій нев’язок для
рівнянь (1)–(4), яка має вигляд: знайти
4 3 2
, , , 0
4 3 2
0
4 3 2
3 2
, , , arg min cos
4 3 2
sin
4 3 2
4 3 2
S
B A A A
a b c S
S
B A A A
B A A B A
as bs cs
a b c S x x k s ds
as bs cs
y y k s ds
aS bS cS
k S k aS bS cS k
е е е е
(5)
за обмежень
min maxS S S , (6)
4 4 3 3 2 2
4 3 2
, 1, ,
2 24 3 2
A A
i S i S i S iS
a b c k i N
NN N N
, (7)
де N – кількість рівних підінтервалів у інтервалі [0, ]S
для дискретизації функції
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2023, вип. 37, 123-127
125
4 3 2
( )
4 3 2
A A
as bs cs
s k s , [0, ]s S ;
2 2
min B A B AS x x y y ,
maxS – параметр для управління верхнею межею на S – загальну довжину кривої.
Цільова функція (5) є кусково-гладкою та забезпечує мінімізацію суми
модулів функцій нев'язок для рівнянь (1)–(4). Обмеження (6) гарантують додатні
значення довжини S , а обмеження (7) забезпечує існування єдиного глобального
мінімуму для задачі (5)–(7) незалежно від вибору величини
maxS .
Для розв’язання задачі (5)–(7) на основі модифікації r-алгоритму Шора
розроблено метод з управлінням параметрами (коефіцієнт розтягу простору),
0h (крок на першій ітерації) і 1q (коефіцієнт зменшення кроку на подальших
ітераціях) та критеріями зупинки x (зупинка за аргументом) та maxitn
(максимальна кількість ітерацій). Стартову точку вибрано рівною min0,0,0,
T
S .
2. Масштабування системи (1)–(4) та обчислювальний експеримент.
Нехай довжина кривої 100S е . Щоб у точці ( , )B Bx y гарантувати кут B
такий, що
2 2
B
, потрібно, щоб виконувалася нерівність
4 3 2100 100 100
100
2 4 3 2 2
a b с d
е е е е .
Якщо aе , bе , cе , d е є додатними, то дана нерівність означає, що їх значення
будуть величинами різних порядків: так aе буде мати порядок
810
, bе ‒
порядок
610
, cе ‒ порядок
410
, а d е
‒ порядок
210
. Це впливає на швидкість
збіжності методу розв'язання задачі (5)–(7), а при великих значеннях S е навіть
на неможливість її розв’язання. У цьому випадку може допомогти лема.
Лема ( 0 ). Якщо , , , , a b c d Sе е е е е є розв'язком системи (1)–(4), то
4a a е е е , 3b b ее е , 2c c е е е , S S ее е буде розв'язком наступної
системи рівнянь:
4 3 2
0
= cos
4 3 2
S
B A A
as bs cs
x x d s ds
, (8)
4 3 2
0
= sin
4 3 2
S
B A A
as bs cs
y y d s ds
, (9)
4 3 2
=
4 3 2
B A
aS bS cS
d S , (10)
3 2= , = .A Bk d k aS bS cS d (11)
Петро Стецюк, Ольга Хом’як, Володимир Жидков
Масштабування даних для задачі побудови кривої в натуральній параметризації …
126
Лема встановлює зв'язок розв'язків системи (1)–(4) та масштабованої
системи (8)–(11), в якій координати точок та значення кривин домножуються на
одну і ту ж величину 0 .
Для знаходження розв'язків погано масштабованих ( 10 ) та добре
масштабованих ( 1 ) задач проведено обчислювальний експеримент для двох
наборів даних. Для погано масштабованих задач були вибрані вихідні дані:
0, 20, , 0, 30, 40, , 0.
18 36
A A A A B B B Bx y k x y k
(12)
0, 20, , 0.1, 30, 40, , 0.05.
18 36
A A A A B B B Bx y k x y k
(13)
Для добре масштабованих задач їм відповідають такі вихідні дані:
0, 2, , 0, 3, 4, , 0.
18 36
A A A A B B B Bx y k x y k
(14)
0, 2, , 0.01, 3, 4, , 0.005.
18 36
A A A A B B B Bx y k x y k
(15)
У табл.1 наведено витрати r-алгоритму (за кількістю ітерацій – 1itn та 2itn ,
за кількістю обчислень узагальненого градієнта цільової функції – 1nfg та 2nfg )
для знаходження плоских кривих для даних (12) та (13) та краще масштабованих
даних (14) та (15) для трьох критеріїв зупинки за аргументом
6 8 1010 ,10 ,10x
. При цьому використовувались такі параметри 2.0 ,
0 1.0h , 1 1.0q , 1500maxitn . В табл. 1 також наведені відносні відхилення
між компонентами розв'язків, які визначаються за формулами
4
2 1 2/ /a a a a е е е е , 3
2 1 2/ /b b b b е е е е , 2
2 1 2/ /c c c c е е е е .
Таблиця 1
Витрати r-алгоритму на пошук розв'язків задач (12), (14) та (13), (15)
Задача( 10 )/
Задача( 1 )
Задачі (12), (14) Задачі (13), (15)
610x
810x
1010x
610x
810x
1010x
1 2/itn itn 163/103 211/133 242/154 254/102 278/131 314/151
1 2/nfg nfg 469/132 626/173 696/201 995/146 1039/183 1107/211
a е
5.5e-07 3.2e-09 8.9e-12 2.0e-05 1.3e-06 2.0e-09
b е
6.5e-07 2.5e-09 3.7e-12 2.8e-06 1.6e-07 2.6e-10
c е
6.6e-07 1.8e-09 1.3e-11 4.8e-07 2.4e-08 4.2e-11
S е
1.4e-07 1.3e-10 6.0e-12 2.6e-08 7.5e-10 3.1e-12
З таблиці видно, що для розв'язання задач з добре масштабованими даними
(задачі (14) та (15)) потрібно майже в два рази менше ітерацій та майже в чотири
рази менше обчислень узагальненого градієнта, ніж для розв'язання задач з
погано масштабованими даними (задачі (12) та (13)).
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2023, вип. 37, 123-127
127
Висновки. У статті досліджено питання масштабування для системи нелінійних
рівнянь у задачі побудови плоскої кривої у натуральній параметризації з
кубічним розподілом кривини, що проходить через дві задані точки та забезпечує
в них задані кути нахилу дотичних та задані значення кривин. Показано, що для
того, щоб знайти розв'язок із заданою точністю за менший час краще
розв'язувати задачу з добре масштабованими даними. Правильне масштабування
даних відіграє суттєву роль для вибору того чи іншого параметру при
моделюванні фрагментів аеродинамічних та технічних профілів в
ітераційному режимі, враховуючи, що масштаб достатньо встановити всього
один раз, а задачу (5)–(7) потрібно вирішувати дуже багато разів.
Робота підтримана Volkswagen Foundation (грант 97 775).
Література
[1] Борисенко В., Агарков О., Палько К., Палько М. Моделювання плоских кривих у
натуральній параметризації. Геометричне моделювання та інформаційні технології. 2016.
№ 1. С. 21-27.
[2] Борисенко В. Д., Устенко С. А., Устенко I. В. Геометричне моделювання s-подібних
скелетних ліній профілів лопаток осьових компресорів. Вісник двигунобудування. 2018.
№ 1. С. 45–52.
[3] Нестеренко А., Дученко O. Квазіньютонівські методи для моделювання плоских кривих.
Фізико-математичне моделювання та інформаційні технології. 2021. 33. С. 62-67.
[4] Stetsyuk P.I., Tkachenko O.V., Zhydkov V.O. Using Shor’s r-algorithm for building naturally
parametrized curve having cubic curvature. Proceedings of the 7-th International Conference on
Control and Optimization with Industrial Application, Baku, Azerbaijan, 26-28 August, 2020. Vol.
I. P. 389-391.
[5] Khomiak O., Stetsyuk P., Zhydkov V., Infante L. Using Optimization to Construct Naturally
Parametrized Curve with Cubic Curvature. In: Arsenyeva, O., Romanova, T., Sukhonos, M.,
Tsegelnyk, Y. (eds) Smart Technologies in Urban Engineering. STUE 2022. Lecture Notes in
Networks and Systems. 2023. Vol 536. Springer, Cham. P. 14–24.
Coordinate scaling for building naturally parametrized curve with
cubic curvature
Petro Stetsyuk, Olha Khomiak, Volodymyr Zhydkov
The article explores topic of coordinate scaling for linear inequality system in problem of building
flat naturally parametrized curve passing through 2 points with given inclinations and curvatures
at them. The non-smooth optimization problem presented is equivalent to a system of four non-
linear equations with four unknowns, which describes the problem of building curve with cubic
curvature distribution and its solution method based on Shor’s r-algorithm modification. It is
demonstrated, that for finding problem solution with given accuracy for less time it is really better
to solve the problem with well scaled coordinates. Correct scaling plays essential role in choosing
parameters for iterative modeling fragments of aerodynamic and technical profiles.
Отримано 13.03.23
http://www.coia-conf.org/upload/editor/files/COIA2020_V1.pdf
http://www.coia-conf.org/upload/editor/files/COIA2020_V1.pdf
http://www.coia-conf.org/upload/editor/files/COIA2020_V1.pdf
http://www.coia-conf.org/upload/editor/files/COIA2020_V1.pdf
|
| id | oai:ojs2.www.fmmit.lviv.ua:article-318 |
| institution | Physico-mathematical modeling and informational technologies |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2026-06-09T01:10:17Z |
| publishDate | 2023 |
| publisher | Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України |
| record_format | ojs |
| resource_txt_mv | wwwfmmitlvivua/d0/ca482e90ee7d171b081b57729e672ad0.pdf |
| spelling | oai:ojs2.www.fmmit.lviv.ua:article-3182025-02-21T17:31:10Z Coordinate scaling for building naturally parametrized curve with cubic curvature Масштабування даних для задачі побудови кривої в натуральній параметризації з кубічною кривиною Stetsyuk, Petro Khomiak, Olha Zhydkov, Volodymyr плоска крива, натуральна параметризація, кубічна кривина, негладка функція, r-алгоритм The article explores topic of coordinate scaling for linear inequality system in problem of building flat naturally parametrized curve passing through 2 points with given inclinations and curvatures at them. The non-smooth optimization problem presented is equivalent to a system of four non-linear equations with four unknowns, which describes the problem of building curve with cubic curvature distribution and its solution method based on Shor’s r-algorithm modification. It is demonstrated, that for finding problem solution with given accuracy for less time it is really better to solve the problem with well scaled coordinates. Correct scaling plays essential role in choosing parameters for iterative modeling fragments of aerodynamic and technical profiles. У статті досліджено питання масштабування для системи нелінійних рівнянь у задачі побудови плоскої кривої у натуральній параметризації, яка проходить через дві задані точки та забезпечує в них задані кути нахилу дотичних та задані значення кривин. Представлена оптимізаційна негладка задача еквівалентна системі чотирьох нелінійних рівнянь з чотирма невідомими, яка описує задачу побудови необхідної кривої з кубічним розподілом кривини, та метод її розв’язання на основі модифікації r-алгоритму Шора. Показано, що для того, щоб знайти розв'язок оптимізаційної задачі із заданою точністю за менший час краще розв'язувати задачу з добре масштабованими даними. Правильне масштабування даних відіграє суттєву роль для вибору параметрів при моделюванні фрагментів аеродинамічних та технічних профілів в ітераційному режимі. Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України 2023-06-29 Article Article application/pdf https://www.fmmit.lviv.ua/index.php/fmmit/article/view/318 PHYSICO-MATHEMATICAL MODELLING AND INFORMATIONAL TECHNOLOGIES; No. 37 (2023): ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; 123-127 ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; № 37 (2023): ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; 123-127 2617-5258 1816-1545 10.15407/fmmit2023.37 uk https://www.fmmit.lviv.ua/index.php/fmmit/article/view/318/286 Авторське право (c) 2023 Петро Стецюк, Ольга Хом’як, Володимир Жидков (Автор) |
| spellingShingle | плоска крива натуральна параметризація кубічна кривина негладка функція r-алгоритм Stetsyuk, Petro Khomiak, Olha Zhydkov, Volodymyr Масштабування даних для задачі побудови кривої в натуральній параметризації з кубічною кривиною |
| title | Масштабування даних для задачі побудови кривої в натуральній параметризації з кубічною кривиною |
| title_alt | Coordinate scaling for building naturally parametrized curve with cubic curvature |
| title_full | Масштабування даних для задачі побудови кривої в натуральній параметризації з кубічною кривиною |
| title_fullStr | Масштабування даних для задачі побудови кривої в натуральній параметризації з кубічною кривиною |
| title_full_unstemmed | Масштабування даних для задачі побудови кривої в натуральній параметризації з кубічною кривиною |
| title_short | Масштабування даних для задачі побудови кривої в натуральній параметризації з кубічною кривиною |
| title_sort | масштабування даних для задачі побудови кривої в натуральній параметризації з кубічною кривиною |
| topic | плоска крива натуральна параметризація кубічна кривина негладка функція r-алгоритм |
| topic_facet | плоска крива натуральна параметризація кубічна кривина негладка функція r-алгоритм |
| url | https://www.fmmit.lviv.ua/index.php/fmmit/article/view/318 |
| work_keys_str_mv | AT stetsyukpetro coordinatescalingforbuildingnaturallyparametrizedcurvewithcubiccurvature AT khomiakolha coordinatescalingforbuildingnaturallyparametrizedcurvewithcubiccurvature AT zhydkovvolodymyr coordinatescalingforbuildingnaturallyparametrizedcurvewithcubiccurvature AT stetsyukpetro masštabuvannâdanihdlâzadačípobudovikrivoívnaturalʹníjparametrizacíízkubíčnoûkrivinoû AT khomiakolha masštabuvannâdanihdlâzadačípobudovikrivoívnaturalʹníjparametrizacíízkubíčnoûkrivinoû AT zhydkovvolodymyr masštabuvannâdanihdlâzadačípobudovikrivoívnaturalʹníjparametrizacíízkubíčnoûkrivinoû |