Щодо питання обчислювальної складності при дослідженні динаміки систем із антисипацією
Статтю присвячено питанням дослідження систем із антисипацією. Розглядається динаміка таких антисипаційних систем, які зводяться до відображення минулих станів у майбутній у явному вигляді. Оператор еволюції таких відображень заданий оператором Хатчинсона. В метричному просторі з метрикою Хаусдорфа...
Gespeichert in:
| Datum: | 2019 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Ukrainian |
| Veröffentlicht: |
Інститут проблем математичних машин і систем НАН України
2019
|
| Schriftenreihe: | Математичні машини і системи |
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/151927 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Щодо питання обчислювальної складності при дослідженні динаміки систем із антисипацією / С.В. Лазаренко // Математичні машини і системи. — 2019. — № 1. — С. 28–35. — Бібліогр.: 7 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-151927 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-1519272025-02-09T15:36:05Z Щодо питання обчислювальної складності при дослідженні динаміки систем із антисипацією К вопросу вычислительной сложности при исследовании динамики систем с антисипацией To the issue of computational complexity under the study of systems dynamics with anticipatory Лазаренко, С.В. Обчислювальні системи Статтю присвячено питанням дослідження систем із антисипацією. Розглядається динаміка таких антисипаційних систем, які зводяться до відображення минулих станів у майбутній у явному вигляді. Оператор еволюції таких відображень заданий оператором Хатчинсона. В метричному просторі з метрикою Хаусдорфа проводиться моделювання динамічних систем із багатозначним оператором. У фокусі статті знаходиться проблематика розрахунку старшого показника Ляпунова як чисельної характеристики, на основі якої можна говорити про властиву системі чутливість до малих збурень, тим самим стверджуючи, що динаміка системи проявляє хаотичність чи регулярність. Статья посвящена вопросам исследования систем с антисипацией. Рассматривается динамика антисипационных систем, которые сводятся к отображению прошлых состояний в будущее в явном виде. Оператор эволюции таких отображений задан оператором Хатчинсона. В метрическом пространстве с метрикой Хаусдорфа проводится моделирование динамических систем с многозначным оператором. В фокусе статьи находится проблематика расчета старшего показателя Ляпунова как численной характеристики, на основе которой можно говорить о присущей системе чувствительности к малым возмущениям, тем самым утверждая, что динамика системы проявляет хаотичность или регулярность. The article is devoted to the study of the Anticipatory systems. The dynamics of the Anticipatory system is considered, which can be introduced by an explicit mapping of past states to future one in time. The evolution operator of such mappings is given by the Hutchinson operator. In a metric space with a Hausdorff metric, modeling of dynamical systems with a multi-valued operator is performed. The article focuses on the problem of calculating the Maximal Lyapunov exponent as a numerical characteristic, on the basis of which one can speak about the inherent sensitivity to small perturbations, thereby affirming that the system’s dynamics are random or regular. 2019 Article Щодо питання обчислювальної складності при дослідженні динаміки систем із антисипацією / С.В. Лазаренко // Математичні машини і системи. — 2019. — № 1. — С. 28–35. — Бібліогр.: 7 назв. — укр. 1028-9763 https://nasplib.isofts.kiev.ua/handle/123456789/151927 519.7 uk Математичні машини і системи application/pdf Інститут проблем математичних машин і систем НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Ukrainian |
| topic |
Обчислювальні системи Обчислювальні системи |
| spellingShingle |
Обчислювальні системи Обчислювальні системи Лазаренко, С.В. Щодо питання обчислювальної складності при дослідженні динаміки систем із антисипацією Математичні машини і системи |
| description |
Статтю присвячено питанням дослідження систем із антисипацією. Розглядається динаміка таких антисипаційних систем, які зводяться до відображення минулих станів у майбутній у явному вигляді. Оператор еволюції таких відображень заданий оператором Хатчинсона. В метричному просторі з метрикою Хаусдорфа проводиться моделювання динамічних систем із багатозначним оператором. У фокусі статті знаходиться проблематика розрахунку старшого показника Ляпунова як чисельної характеристики, на основі якої можна говорити про властиву системі чутливість до малих збурень, тим самим стверджуючи, що динаміка системи проявляє хаотичність чи регулярність. |
| format |
Article |
| author |
Лазаренко, С.В. |
| author_facet |
Лазаренко, С.В. |
| author_sort |
Лазаренко, С.В. |
| title |
Щодо питання обчислювальної складності при дослідженні динаміки систем із антисипацією |
| title_short |
Щодо питання обчислювальної складності при дослідженні динаміки систем із антисипацією |
| title_full |
Щодо питання обчислювальної складності при дослідженні динаміки систем із антисипацією |
| title_fullStr |
Щодо питання обчислювальної складності при дослідженні динаміки систем із антисипацією |
| title_full_unstemmed |
Щодо питання обчислювальної складності при дослідженні динаміки систем із антисипацією |
| title_sort |
щодо питання обчислювальної складності при дослідженні динаміки систем із антисипацією |
| publisher |
Інститут проблем математичних машин і систем НАН України |
| publishDate |
2019 |
| topic_facet |
Обчислювальні системи |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/151927 |
| citation_txt |
Щодо питання обчислювальної складності при дослідженні динаміки систем із антисипацією / С.В. Лазаренко // Математичні машини і системи. — 2019. — № 1. — С. 28–35. — Бібліогр.: 7 назв. — укр. |
| series |
Математичні машини і системи |
| work_keys_str_mv |
AT lazarenkosv ŝodopitannâobčislûvalʹnoískladnostípridoslídžennídinamíkisistemízantisipacíêû AT lazarenkosv kvoprosuvyčislitelʹnojsložnostipriissledovaniidinamikisistemsantisipaciej AT lazarenkosv totheissueofcomputationalcomplexityunderthestudyofsystemsdynamicswithanticipatory |
| first_indexed |
2025-11-27T11:38:18Z |
| last_indexed |
2025-11-27T11:38:18Z |
| _version_ |
1849943395462545408 |
| fulltext |
28 © Лазаренко С.В., 2019
ISSN 1028-9763. Математичні машини і системи, 2019, № 1
УДК 519.7
С.В. ЛАЗАРЕНКО
*
ЩОДО ПИТАННЯ ОБЧИСЛЮВАЛЬНОЇ СКЛАДНОСТІ ПРИ ДОСЛІДЖЕННІ
ДИНАМІКИ СИСТЕМ ІЗ АНТИСИПАЦІЄЮ
*
Навчально-науковий комплекс «Інститут прикладного системного аналізу» НТУУ «КПІ імені Ігоря
Сікорського», м. Київ, Україна
Анотація. Статтю присвячено питанням дослідження систем із антисипацією. Розглядається
динаміка таких антисипаційних систем, які зводяться до відображення минулих станів у майбу-
тній у явному вигляді. Оператор еволюції таких відображень заданий оператором Хатчинсона. В
метричному просторі з метрикою Хаусдорфа проводиться моделювання динамічних систем із
багатозначним оператором. У фокусі статті знаходиться проблематика розрахунку старшого
показника Ляпунова як чисельної характеристики, на основі якої можна говорити про властиву
системі чутливість до малих збурень, тим самим стверджуючи, що динаміка системи проявляє
хаотичність чи регулярність. У силу росту обчислень за показниковим законом у ході моделюван-
ня системи з антисипацією, обумовленою багатозначністю розв’язків, питання оцінки і мініміза-
ції цих обчислень стає першочерговою прикладною проблемою побудови системного підходу в ана-
лізі таких систем. Завдяки цій причині, прикладні дослідження систем цього класу залишаються
малочисельними, а актуальність їх обумовлена широким класом реальних процесів, що можуть
формально представлятися моделями із антисипацією. Останні, у свою чергу, можуть навіть
більш точно відображати природу процесу, який формалізують, порівняно з класичними моделями
з запізненням. Серед них варто відзначити такі, як моделювання транспортного потоку, вирішен-
ня конфліктних ситуацій тощо. У роботі запропоновано та детально описано процедуру розраху-
нку старшого показника Ляпунова, адаптовану до систем із багатозначними операторами еволю-
ції. Базова ідея процедури основана на алгоритмі Бенеттіна для чисельного розрахунку старшого
показника Ляпунова. Наведено оцінки часової та просторової обчислювальних складностей. Виді-
лено найбільш затратні з точки зору обчислень складові процедури – розрахунок відстані між ос-
новною траєкторією та збуреною.
Ключові слова: багатозначні відображення, показники Ляпунова, обчислювальна складність.
Аннотация. Статья посвящена вопросам исследования систем с антисипацией. Рассматривает-
ся динамика антисипационных систем, которые сводятся к отображению прошлых состояний в
будущее в явном виде. Оператор эволюции таких отображений задан оператором Хатчинсона. В
метрическом пространстве с метрикой Хаусдорфа проводится моделирование динамических си-
стем с многозначным оператором. В фокусе статьи находится проблематика расчета старшего
показателя Ляпунова как численной характеристики, на основе которой можно говорить о при-
сущей системе чувствительности к малым возмущениям, тем самым утверждая, что динамика
системы проявляет хаотичность или регулярность. В силу роста вычислений по показательному
закону в ходе моделирования системы с антисипацией, обусловленной многозначностью решений,
вопросы оценки и минимизации этих вычислений становятся первоочередной прикладной пробле-
мой построения системного подхода в анализе таких систем. По этой же причине прикладные
исследования систем этого типа остаются малочисленными, а актуальность их обусловлена ши-
роким классом реальных процессов, которые могут быть формально представлены моделями с
антисипацией. Последние же, в свою очередь, могут даже более точно отражать природу про-
цесса, который они формализуют, по сравнению с классическими моделями с запаздыванием. Сре-
ди них стоит отметить такие процессы, как моделирование транспортного потока, решение
конфликтных ситуаций и тому подобное. В работе предложена и подробно описана процедура
расчета старшего показателя Ляпунова, адаптированная к системам с многозначными операто-
рами эволюции. Базовая идея процедуры основана на алгоритме Бенеттина для численного расче-
та старшего показателя Ляпунова. Приведены оценки временной и пространственной вычисли-
тельных сложностей. Выделены наиболее затратные с точки зрения вычислений составные про-
цедуры – расчет расстояния между основной траекторией и возмущенной.
ISSN 1028-9763. Математичні машини і системи, 2019, № 1 29
Ключевые слова: многозначные отображения, показатели Ляпунова, вычислительные сложно-
сти.
Abstract. The article is devoted to the study of the Anticipatory systems. The dynamics of the Anticipatory
system is considered, which can be introduced by an explicit mapping of past states to future one in time.
The evolution operator of such mappings is given by the Hutchinson operator. In a metric space with a
Hausdorff metric, modeling of dynamical systems with a multi-valued operator is performed. The article
focuses on the problem of calculating the Maximal Lyapunov exponent as a numerical characteristic, on
the basis of which one can speak about the inherent sensitivity to small perturbations, thereby affirming
that the system’s dynamics are random or regular. Due to the exponential growth of computations during
modeling of the anticipatory system caused by the ambiguity of decisions, the questions of estimating and
minimizing these calculations become the primary applied problem of building a systems approach to the
analysis of such systems. For the same reason, the applied studies of these systems remain few in number,
and their relevance is due to a wide class of real processes that can be formally presented by models with
the anticipation. The lasts, in turn, may even more accurately reflect the nature of the process that they
formalize, compared with the classical models with a lag. Among them, it is worth noting such processes
as traffic flow modeling, conflict resolution, etc. The paper proposes and describes in detail the procedure
for calculating the Maximal Lyapunov exponent, adapted to systems with multi-valued evolution opera-
tors. The basic idea of the procedure is based on the Benettin algorithm for the numerical calculation of
the Maximal Lyapunov exponent. Estimates of time and spatial computational complexity are given. The
most costly parts of the procedure in terms of calculating are selected – the calculation of the distance
between the main trajectory and the perturbed one.
Keywords: multi-valued maps, Lyapunov characteristic exponents, calculation complexity.
1. Вступ
Дослідження динаміки систем, оператори еволюції яких передбачають багатозначність
розв’язків, на сьогоднішній день є відносно новим напрямом у теоретичній кібернетиці [1,
2]. Актуальність та значний прикладний потенціал полягає в побудові нових моделей, які в
деякій мірі більш точно можуть описувати ряд складних явищ та процесів. Так, якраз сис-
теми з антисипацією й належать до цієї новітньої гілки. Побудова та застосування таких
моделей не набула широкого розповсюдження в силу досить об’єктивних причин, серед
яких є значна ресурсоємність симуляції процесів за допомогою цих моделей; їх невизначе-
ність, обумовлена багатозначністю майбутніх сценаріїв еволюціонування; часто відсут-
ність відповідного програмного чи апаратного забезпечення. Безсумнівно, до числа таких
процесів можна віднести, наприклад, суспільну та індивідуальну свідомість, прийняття рі-
шень у конфліктних ситуаціях тощо.
Безумовно, важливим аспектом дослідження систем є аналіз їх динаміки. А зважа-
ючи на те, що системи з антисипацією визначаються через багатозначні операторами ево-
люції, то при дослідженні динаміки цих систем зіштовхуються з проблемами обсягів обчи-
слень та нелінійним ростом використання машинної пам’яті. Останніми й обумовлена мета
статті: побудова процедури розрахунку старшого показника Ляпунова (ПЛ) для систем із
антисипацією як важливого інструменту в дослідженні їх динаміки. У фокусі статті розг-
лядаються супутні питання оцінки часових та просторових обчислювальних складностей
для такої процедури.
2. Математична модель та базові поняття
Для початку введемо необхідні визначення та прийняті позначення. З детальною терміно-
логією антисипаційних систем можна ознайомитись у роботі [1] та за посиланнями в ній.
Розглянемо початкову систему, що описується законом сильної антисипації першого по-
рядку:
1 1( , , )i i ix f x x , , 0,1, 2,n
ix R i , (1)
30 ISSN 1028-9763. Математичні машини і системи, 2019, № 1
де управляючий параметр 2( ; ) R , оператор зв'язку nnn RRRRf 2: (часто –
однозначний), ix – стани неявної системи.
Нас цікавить випадок, коли f передбачає багатозначність розв’язків. Виходячи з
цих міркувань, вводимо таке. Нехай оператор f можна представити відображенням
n
n
n SRSF )dim(: у вигляді
1
1( , ) ( , )
i
i i k
x X k
X F X f x , (2)
тут
ni SX , nRx ,
nR
nS 2 є підмножиною множини всіх можливих підмножин із nR .
Для простоти вважатимемо, що Nk ,1 – скінченний набір. Із необхідними поняттями та
визначенням теорії багатозначних відображень можна ознайомитись у [3, 4].
Визначення. Станом динамічної системи (ДС) в явному вигляді в дискретний момент
,1,0i будемо називати таку множину:
n
k
i
ki SxX }{ .
Часто під станом антисипаційної ДС розуміють саме ix із (1), однак у контексті на-
шої задачі за розрахунком старшого ПЛ будемо притримуватись визначення вище. При
такому представленні нашої антисипаційної ДС, через явну залежність поточного її стану
від попередніх (за часом), оператор F називатимемо оператором еволюції ДС із антиси-
пацією.
Визначення. Траєкторію ДС, задану правилом зміни станів у (2) під дією оператора ( )F ,
починаючи зі стану в момент i , називатимемо послідовність kiiii XXXX ,,,, 21 . Якщо
k – скінченне, то мова, відповідно, йтиме про скінченну частину траєкторії.
Визначимо на nS метрику Хаусдорфа ),(infsup),,(infsupmax),( yxyxYXd
XxYyYyXx
H ,
де nSYX , , ( , ) – метрика Евклідова. Тобто, ми працюємо в метричному просторі всіх
не порожніх компактних підмножин.
Визначення. Збуреним станом ДС із антисипацією стану ni SX називатимемо такий стан
ni SX , що ( , )H i id X X x , де n
i Rx~ – збурення n
i Rx~ .
Таке визначення задає неоднозначність iX . Зрозуміло, що збурюючи iX у різний
спосіб за допомогою ix~ так, щоб ( , )H i id X X x , можна отримувати різні результати в хо-
ді ітерування (2). Для більшої визначеності будемо збурювати iX таким чином:
{ | }i i i i iX X x x x x X .
З необхідною термінологією в області обчислювальних складностей можна ознайо-
митись у [2]. Кардинальні числа iX , згідно з (2), в найгіршому випадку (наприклад, без
утворення циклів) будуть зростати за показниковим законом:
i
i NXX 0 , ,2,1i , (3)
де N – кількість селекторів в операторі Хатчинсона (2). Через цю особливість ДС із анти-
сипацією при їх моделюванні питання обчислювальних складностей постає особливо гост-
ро.
Дотримуватимемося таких необхідних позначень:
– під nc розумітимемо обчислювальні затрати на порівняння двох чисел у
nR (чи
еквівалентної їй операції);
ISSN 1028-9763. Математичні машини і системи, 2019, № 1 31
– nm – обчислювальні затрати на розрахунок функції, що діє в nR .
У цій же роботі [2] було показано, що складність розрахунку метрики Хаусдорфа
для двох станів iX та jX буде
2
1 0 1(2 ) i j
ijd c n N X c , (4)
а побудова траєкторії із i -го стану в pi -й:
2 2 2( 1) 1
0
02
( 1) ( 1)
( , ) .
2 1 2 1
i p i p
n n
n
c X cN N N N
M i i p m X
N N
(5)
3. Розрахунок показників Ляпунова
ПЛ є важливою характеристикою динамічних систем, кількісним описом збіжності чи роз-
біжності близьких траєкторій, на основі якої роблять висновок про її режим еволюції – ре-
гулярний, чи системі властива хаотичність як сильна чутливість до малих збурень [5, c.
143]. Тому для аналізу динаміки системи (в тому числі з антисипацією) доцільно мати не
лише процедуру їх розрахунку, а й максимально зосереджуватись на питанні її обчислюва-
льної оптимальності – мінімізації обчислювальних затрат при її проведенні.
Як добре відомо, за мультиплікативною ергодичною теоремою Оселедця кількість
таких показників буде рівною розмірності фазового простору ДС ( n ). Розглянемо дискре-
тну систему
1
1 ( ), ,n
t t tx f x x R f C ,
n – вимірну гіперсферу малого радіуса з центром у початковій точці 0x та ансамбль ДС
із початковими точками в цій гіперсфері радіусу :
000
~,~ xxx
при збуреннях 0
~x
різних напрямів. У ході еволюціонування цього ансамблю гіперсфера
деформується у n -вимірний еліпсоїд (поки ця множина зображуючих точок залишається
достатньо малою). Деформування (стиснення, розтягнення) цього гіпереліпсоїда відбува-
ється по n напрямам його головних півосей. Розмір цих півосей змінюється за експоненці-
альним законом exp( ), 1,it i n (при достатньо малих розмірах множини зображуючих то-
чок, щоб зберігалося лінійне наближення траєкторій). Нехай «основна» траєкторія
210 xxx та одна із ансамблю утворена збуренням початкового стану 0x :
0 0 0 0( )x x f x x , а – достатньо мале, щоб розглядати f лінійним наближенням,
то представивши f рядом Тейлора в околі 0x : 0 0 0( ) ( ) ( )( ) ( )f x f x f x x x o x , знайде-
мо відхилення між цими двома траєкторіями на першому кроці:
0 0 0 0 0( ) ( ) ( ) .f x f x x x f x
(6)
Добре відомо з тієї ж теореми Оселедця, що для кожного 0
~x існує показник (Ляпу-
нова):
0 0
1
( ) lim ln( )t
t
x x x
t
, (7)
32 ISSN 1028-9763. Математичні машини і системи, 2019, № 1
де tx~ – відхилення, дотичне до траєкторії в момент t .З (6) відхилення на першому кроці
буде 1 0 0( )x x f x . У залежності від обраного початкового збурення, приймає одне з
nii ,1 значень.
Існує ряд методів розрахунку ПЛ: Бенеттіна, Вольфа, Розенштайна, Кантца, Якобі
тощо [6]. Більшість із них використовують процедури ортонормування (наприклад, Грам-
ма-Шмідта) для розрахунку всього спектра показників. Для того, щоб дати відповідь на
питання, чи системі властива хаотичність, достатньо знати знак старшого ПЛ, який домі-
нує над рештою. Далі в роботі розглядатимемо процедуру розрахунку старшого ПЛ та її
адаптацію до систем із антисипацією. В основі запропонованої процедури для систем із
антисипацією, що розглядається далі, лежить ідея алгоритму Бенеттіна [7] для розрахунку
старшого ПЛ. З практичної точки зору, розрахунок по (7) представляє собою задачу із сер-
йозними обчислювальними проблемами, так як при надмалих збуреннях та великих t мо-
жна вийти за межі машинної сітки. Проте в контексті тематики даної роботи для систем, у
яких оператор еволюції заданий багатозначним відображенням, прямий розрахунок за (7)
стає просто неможливим у силу колосального обсягу обчислень. Тому Бенеттіном була за-
пропонована така обчислювальна процедура. Замість t розглядається велика серія
малих кроків однакової довжини, та на кожному кроці Tk ,1 розраховується показник
відхилення траєкторій 0ln( )k kx x , а тоді ПЛ розраховується як середнє за всіма кро-
ками:
1 1 0
1 1
ln .
T T
k
k
k k
x
T T x
Важливо, що Бенеттіном у тій же роботі були доведені існування границі при
T та її незалежність від 0
~x .
4. Адаптація процедури розрахунку старшого ПЛ для системи з антисипацією
Тепер застосуємо цей підхід до систем із антисипацією. Спочатку необхідно вибрати поча-
ткову точку. Оскільки ПЛ з фізичної точки зору представляють степінь розходження
(зближення) траєкторій, то зручно розглядати на кожному кроці алгоритму відстань між
двома траєкторіями, одна з яких лежить в атракторі (або максимально до нього наближе-
на). З міркувань мінімізації обчислень починати процедуру будемо зі станів потужності 1
системи (2). Для побудови цих станів вибираємо точку nRy , близькою до смислового
значення системи, для якої побудована відповідна антисипаційна модель, та будуємо дові-
льну послідовність номерів kiii ,,, 10 селекторів системи (2). При k образ 0x точки
y із композиції
0 1
( ) ( ) ( )
ki i if f f належатиме атрактору системи (2) [2] (звичайно, як-
що починати ітерування з басейну притяжіння). Цю точку 0 0{ }X x і візьмемо за початок
однієї із двох траєкторій, що розглядатимемо на вході алгоритму, адаптованого для розра-
хунку старшого ПЛ для систем із антисипацією. Початок другої траєкторії буде -
збуренням 000
~xXX , де 0
~x . Перші пару кроків запропонованої процедури зображе-
но на рис. 1.
ISSN 1028-9763. Математичні машини і системи, 2019, № 1 33
Рисунок 1 – Ілюстрація процедури розрахунку старшого ПЛ в моменти часу 2,0i для систем із
антисипацією. Суцільною лінією позначена траєкторія, що лежить в атракторі,
пунктирною – збурена
Будуємо першу ітерацію ( 1i ): 10 XX F , а точка 10 XX F . Відхилення
між образами складає 1 1( , )Hd X X . Тобто n -вимірна гіперсфера розтягнулась (стиснулась)
у відношенні 1
0
( , )Hd X X
x
, а тому перше наближення старшого ПЛ буде 1
0
( , )
ln Hd X X
x
. Про-
водимо другу ітерацію ( 2i ): траєкторію, що лежить в атракторі, ітеруємо далі по (2)
21 XX F , а другу траєкторію починаємо зі збуреного стану 1X , що переходить під
дією (2) у 2X . Аналогічно попередньому кроку розраховуємо друге випробування для ста-
ршого ПЛ: 2 2
0
( , )Hd X X
x
та друге його наближення – усереднення
1 2 2 2
0 0
( , ) ( , )( , )1
ln ln
2
H Hd X X d X X X X
x x
. Останнє усереднення варто розраховувати один
раз у кінці. Однак, на протязі всього T пам’ять, необхідна для збереження цих значень,
буде рости лінійно. Процедуру продовжуємо достатньо велику кількість разів, щоб отри-
мати максимально точне значення ПЛ. З обчислювальної точки зору варто зазначити, що
хоча 0
~x є постійним значенням, його включаємо в розрахунок випробувань ПЛ на кож-
ному кроці, щоб уникнути, знову ж таки, виходу обчислень ln( ( , ))Hd за межі машинної
сітки при надмалих ( , )Hd .
5. Обчислювальні складності процедури розрахунку старшого ПЛ
Розрахуємо просторові та часові обчислювальні витрати на проведення процедури, описа-
ної вище. Складність побудови «основної» траєкторії від стану 1X до TX буде (1, )M T .
Побудова збуреної траєкторії, з точки зору обчислювальних витрат, на кожному кроці не
переривалася, оскільки потужність її стану на кожному кроці співпадає із потужністю ос-
новної траєкторії. На кожному кроці, починаючи із 1i , розраховуємо відстань між обра-
зами основного iX та збуреного станів iX (що за (4) становить iid обчислювальних ви-
трат) і підраховуємо значення логарифму із витратою 1m . Після проведення останньої іте-
рації усереднюємо всі отримані наближення значень старшого ПЛ ціною 1( 1)T c . Таким
чином, загальні витрати на процедуру становитимуть
34 ISSN 1028-9763. Математичні машини і системи, 2019, № 1
1 1
1
2 (1, ) ( 1) .
T
ii
i
M T d Tm T c (8)
Згідно з (5), перший доданок в (8) буде
2 2
2
0 02
( 1) ( 1)
(2 )
1 1
T T
n n n
N N N N
c X m c X
N N
чи в O -нотації
2( ).T T
nO c N N
Тобто складність 2( )TO N , а у випадку мультимножини ( 0)nc буде ( )TO N (за де-
тальними роз’ясненнями про застосування мультимножин при цих розрахунках варто зве-
рнутися до [2]). Другий доданок в (8), беручи до уваги (4):
2 22 2 2 4 2( 1)
1 0 1 1 0
1
2
2 2
1 1 0 12
(( 2 ) ) ( 2 ) (1 )
1
(2 )
1
T
i T
n n
i
T
d c N X c d c N X N N N
N
Tc c n X N Tc
N
або в O -нотації 2( )TO N .
Тепер бачимо, що, незалежно від того, чи знаходимося ми у просторі мультимно-
жин чи ні, сумарна складність процедури по (8) складатиме 2( )TO N часових витрат. При-
чому, значна їх частина припадає саме на операції розрахунку відстані між станами основ-
ної траєкторії на атракторі та збуреної.
Оцінимо тепер просторову складність. На кожному кроці i процедури максимально
необхідно тримати в пам'яті два стани ДС (2) ( iX та iX ) й множину наближених значень
старшого ПЛ розміром i чисел із R . Тому, враховуючи (3), отримаємо просторову склад-
ність
n
i
NX i
02 чисел із nR або в O -нотації ( )iO N .
6. Висновки
У статті розглянута проблематика чисельного дослідження динаміки дискретно-часових
систем із антисипацією. Увагу зосереджено на проблемі розрахунку старшого показника
Ляпунова для систем такого типу. Запропоновано та детально описано процедуру, що є
адаптацією алгоритму Бенеттіна до цих систем. Проведено оцінки її часової та просторової
обчислювальних складностей.
Важливою складовою всебічного дослідження систем такого типу є розрахунок
всього спектра ПЛ. Враховуючи особливий ріст обчислювальних витрат при моделюванні
систем із антисипацією, наріжним питанням поставатиме оптимізація таких процедур роз-
рахунку спектра.
СПИСОК ДЖЕРЕЛ
1. Лазаренко С.В., Макаренко О.С. Аналіз логістичного антисипаційного рівняння із сильною ан-
тисипацією. Наукові вісті НТУУ “КПІ”. 2012. № 4. С. 91–96.
2. Лазаренко С.В. До обчислювальних проблем антисипаційних систем. Математика в сучасному
технічному університеті: сьома міжнар. наук.-практ. конференція (Київ, 27–28 грудня 2018 р.).
Київ, 2018. C. 92–95.
ISSN 1028-9763. Математичні машини і системи, 2019, № 1 35
3. Борисович Ю.Г., Гельман Б.Д., Мышкис А.Д., Обуховский В.В. Введение в теорию многознач-
ных отображений и дифференциальных включений. Москва, 2011. 224 c.
4. Половинкин Е.С. Многозначный анализ и дифференциальные включения. Москва, 2014. 522 с.
5. Кузнецов С.П. Динамический Хаос. Москва, 2006. 356 с.
6. Awrejcewicz J., Krysko A.V., Erofeev N.P., Dobriyan V., Barulina M.A., Krysko V.A. Quantifying
Chaos by Various Computational Methods. Part 1: Simple Systems. Entropy. 2018. Vol. 20 (3), N 175.
URL: https://doi.org/10.3390/e20030175.
7. Benettin G., Galgani L., Giorgilli A., Strelcyn J.-M. Lyapunov characteristic exponents for smooth dy-
namical systems and for Hamiltonian systems: A method for computing all of them. P.I: Theory. P. II:
Numerical application. Meccanica. 1980. Vol. 15. P. 9–30.
Стаття надійшла до редакції 16.01.2019
https://doi.org/10.3390/e20030175
|