автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Алгоритмы, основанные на прикладной символической динамике

Введение

1 Символический образ

1.1 Псевдотраектория динамической системы.

1.2 Построение символического образа.

2 Энтропия динамической системы

2.1 Топологическая энтропия или мера недетерминированности системы.

2.2 Оценка топологической энтропии.

2.3 Символическая динамика.

2.4 Энтропия и символический образ.

2.5 Вычисление энтропии Я-пространства.

2.6 Энтропия гомеоморфизма, удовлетворяющего условию Липшица

2.7 Примеры вычислений оценок топологической энтропии

2.7.1 Энтропия отображения Хенона.

2.7.2 Энтропия логистического отображения.

2.7.3 Трехмерное логистическое отображение.

Изучение физических процессов приводит нас к построению математических моделей, описывающих данный процесс. Модели всегда рассматриваются при некоторых условиях, то есть разумных ограничениях на входящие в них величины и параметры и представляют собой уравнения, дифференциальные уравнения или их системы, описывающие изучаемый процесс в терминах математических объектов. Примеры таких моделей известны: модели движения маятника (х + ¡jx + sinх = О, /i « 0, здесь второе слагаемое представляет сопротивление среды), движения жидкости, движения тела с ускорением.

Практически важной задачей является исследование поведения решений систем. В основном математические модели какого-либо процесса или явления представляют собой нелинейные системы и как правило, не удается получить решение в виде формулы. А если даже такая формула и получена, то это еще не гарантирует знания поведения решения, так как изучение свойств известной функции может оказаться достаточно сложной задачей.

Нынешний период в развитии нелинейной динамики можно назвать периодом динамического хаоса. Оказалось, что существуют простые динамические системы, которые могут вести себя сложно. Другими словами, одним из ключевых моментов на этом этапе стала чувствительность к начальным данным - экспоненциальное разбегание двух бесконечно близких траекторий для класса хаотических аттракторов. Скорость этого разбега-ния определяется старшим ляпуновским показателем, а скорость "расползания" большого количества бесконечно близких траекторий - энтропией динамической системы.

Поведение хаотической динамической системы во времени оказывается довольно сложным. Примером может служить известное отображение С.Смейла, известное под названием подкова Смейла. Было показано, что временному поведению динамической системы может отвечать движение точки по бесконечно разорванному множеству (впоследствии такие множества получили название фрактальные). Хаотическая динамическая система объединяет в себе глобальную устойчивость (траектория не уходит из некоторой области фазового пространства) с локальной неустойчивостью - малые погрешности начальных данных нарастают, близкие траектории расходятся.

В начале 70-х годов качественная теория и концепция динамического хаоса позволили предложить новый подход к некоторым классическим задачам, например, к проблеме гидродинамической турбулентности — анализу сложной картины течения жидкости при больших скоростях. Предшествующие теории предполагали, что для описания турбулентности нужны модели с большим числом дифференциальных уравнений. Концепция динамического хаоса позволяет надеяться, что хотя бы в некоторых случаях за сложным временным поведением может скрываться сравнительно простая математическая модель. Например, работа американского метеоролога Э.Лоренца показала, что неувязки со среднесрочным прогнозом погоды связаны не с недостаточно подготовленными сотрудниками станции и не со слабой аппаратурой. Причина кроется в достаточно сложном поведении системы (хаотическом), которая описывается простой математической моделью.

Естественно, возникает вопрос об исследовании хаотических динамических систем, об их сравнении между собой. Какая система наиболее хаотична, предсказуема или наиболее вероятна для прогноза. Каковы же основные черты и закономерности хаотических режимов?

Во-первых, очень часто на асимптотической стадии траектория стремится к притягивающему множеству - фракталу (термин "фрактал"/от лат. й-асШэ - дробный/ был введен в 1975 г. Мандельбротом). Простейший и широко известный пример фрактала - это канторово множество (см. рис.0.1). О

1 Р-?

Н Н н н

2 7 8

I-Р I н н н н

Рис. 0.1: Первые пять шагов построения канторова множества.

Отличительной чертой, присущей многим (но не всем) фракталам, является то, что увеличенная часть такого множества оказывается подобна всему множеству. Возникает эффект самоподобия. ной аттрактора кенона. ПР» У—И

Рис 0 2: Иллюстрация фрактально» струк масштаба наблюдается эффект самоподобия.

I------.------.1------1.------л----------1------;-------]------¡-------;-------;---- ! I ! ! : : I I : 8 о------;------^------'г------.^----------о------1-------I-----—----

------;------\------1-------:-----------------1------1------н------1-------;------Н----

-2 -10 12 "2 -10 12

1 шаг. 1 4 шаг.

1------ о------ 1-.

-1------ —- 0------ Г----

-1------

5 шаг. 15 шаг.

1------;------------¡-------;------.•)!J!.!I

-1------1------\------I-------1------\------ -1------1------.!-------;.

-2-1012 -2 О 1 2

17 шаг.

11 шаг.

1------;------------1.------'.------]----- 1------;------\------¡-------;------1 о------;------р^ТГГргг^:-.!------.]— о.¡-----"Т^Г^^^^^.-! л—;—^------1------;—— -1—;-------!------\------1—!

-2 О 1 2 -2 -10 12

13 шаг. 18 шаг.

Рис. 0.3: Перемешивание малого фазового объема по аттрактору Хенона.

На рисунках 0.1 и 0.2 видно, что подобие действительно имеет место. Аттракторы, имеющие фрактальную структуру, называют странными.

Во-вторых, движение обычно оказывается локально неустойчивым, то есть, близкие траектории расходятся, не покидая при этом аттрактора.

В-третьих, если в качестве начальных данных взять не точку, а некоторый объем в фазовом пространстве, то с течением времени система начнет этот объем "размазывать" по всему аттрактору, и возникнет эффект перемешивания. На рисунке 0.3 показаны последовательные "размазывания" небольшого отрезка по аттрактору Хенона.

Таким образом, если в начальный момент времени мы знали состояние системы достаточно точно, то со временем ошибка начнет нарастать. Спустя некоторое время, зависящее от скорости перемешивания, можно будет лишь сказать, что оно " где-то на аттракторе". На больших временах характеризовать систему можно, только указав вероятность появления траектории в окрестности некоторой точки. Таким образом, мы приходим к вероятностному описанию динамического хаоса, к понятиям инвариантной меры и энтропии - степени хаотичности системы. Аттракторы, обладающие свойством перемешивания называют перемешивающими или стохастическими аттракторами. Оказывается [6], в большинстве случаев хаотичность системы влечет за собой и стохастичность аттрактора. Аттрактор Хенона, например, является одновременно странным (имеет фрактальную структуру), хаотическим (энтропия отлична от нуля) и стохастическим (см. рис. 0.3). Однако это не всегда так. В логистическом отображении х Е [0,1], при Л = 4 инвариантное множество равно всему отрезку [0,1] и у него нет фрактальной структуры. С другой стороны, при таком Л система имеет циклы, отличные от степени двойки, что равносильно ненулевой энтропии [10]. Получаем, что хаотичность не влечет странности.

При исследовании поведения динамических систем численными способами удобно применять методы символической динамики.

Прикладная символическая динамика - это набор методов и численных алгоритмов исследования глобальной структуры динамической системы. Применение этих методов не требует какой-либо предварительной информации о системе. Общая схема исследования следующая. Предположим фазовое пространство М покрыто конечным числом ячеек (М(г)} и в нашем распоряжении имеется "прибор", который показывает номер или индекс г ячейки, когда точка х лежит в ячейки М(г). Ячейки могут пересекаться; когда стрелка прибора стоит точно на границе М{г) и М^), тогда любое значение г или j считается правильным. Таким образом, траектория системы кодируется последовательностью индексов ^ е 7}. Индексами могут быть символы любой природы: номера, буквы, координаты и так далее. Часто говорят о буквах алфавита. В этом случае число букв совпадает с числом ячеек, и траектории кодируются последовательностью букв, которые называются допустимыми словами.

Название " символическая динамика" отражает основную идею — описание динамики системы при помощи допустимых последовательностей символов из конечного набора. Следует отметить, что по данной последовательности однозначно восстанавливается последовательность ячеек, через которые проходит траектория. Ясно, что такое описание динамики будет более точным, когда ячейки выбираются достаточно мелкими. Переход от фазового пространства к конечному набору символов можно рассматривать как дискретизацию фазового пространства.

Методы прикладной символической динамики успешно применяются для решения следующих проблем:

• локализация периодических траекторий фиксированного периода,

• построение периодической траектории, в локализация множества цепно-рекуррентных траекторий,

• построение аттракторов и их областей притяжения,

• построение фильтраций,

• определение глобальной структуры динамической системы,

• оценка показателей Ляпунова периодических траекторий.

• оценка спектра Морса,

• построение изолирующих окрестностей,

• вычисление индекса Конли.

Целью данной работы является продолжение исследования динамических систем и разработка конструктивных методов вычисления топологической энтропии и структурной матрицы динамической системы.

Топологическая энтропия это характеристика динамической системы, которая может служить мерой хаотичности системы при соответствующем определении хаоса. Например, положительность энтропии отображения говорит о его хаотичности. Топологическую энтропию трудно численно оценить, так как она стандартно определяется через открытые покрытия. Большинство оценок было получено для одномерных отображений

14], [18]. Chen предложил метод оценки снизу топологической энтропии, используя последовательные прообразы отображения [17]. Авторы, предлагающие оценки энтропии для многомерных систем, используют подсчет числа периодических траектории фиксированного периода [15]. Но тогда на систему накладывается требование выполнения аксиомы А. Немецкие авторы [20] Gary Froyland, Oliver Yunge и Gunter Ochs предложили новый подсчет верхней оценки топологической энтропии, основанный на символической динамике. Но они накладывают так же дополнительные условия на используемое покрытие С. Полученная ими оценка имеет место при условии, что покрытие С является порождающим. Это ограничение является существенным недостатком метода, так как неизвестно как проверить, что данное покрытие является порождающим.

Предложенный в данной работе метод оценки топологической энтропии использует замкнутые покрытия без каких-либо специфических требований. Например, покрытие может состоять из кубов, пересекающихся на границе. Суть идеи следующая.

Пусть на компактном метрическом пространстве М действует дискретная динамическая система / : м —у М, где / - гомеоморфизм. Эта система строго детерминирована: задав точно начальное состояние xq, мы определим тем самым однозначно состояние хт в любой момент времени т: хт = fm(xо). Дело обстоит уже не совсем так, если мы находимся в условиях ограниченной точности. Предположим, мы пытаемся выяснить, случайной или детерминированной является изучаемая нами система, регистрируя положение фазовой точки в последовательные моменты времени при помощи некоторого прибора. Реальный прибор обладает ограниченной точностью и может показывать только конечный ряд значений.

Пусть С = {М{ 1),., М(п)} - конечное замкнутое покрытие фазового пространства, а ¿т - показание прибора при х € М(гт), 1 < im < п, т £ Z. Определим отображение ф, сопоставляющее точке ж последовательность —сю < т < +оо так, что ф(х) = {гт}^Г(х)еМ(гт). (0.1)

Соотношение (0.1) является ключом к исследованию систем методами символической динамики. Если в последовательности ф{х) обнаруживается простая закономерность, то мы не склонны считать изучаемую систему случайной. Если же эта последовательность достаточно сложна и "непредсказуема", то естественно приписать системе случайные свойства. Разумеется, в расчет должна приниматься не одна траектория /т(х) и отвечающая ей запись показаний прибора ф{х), а совокупность траекторий, отвечающих свойствам изучаемой системы.

Наша задача состоит в том, чтобы оценить сложность всей системы. Одна из возможностей связана с асимптотикой числа "допустимых слов" длины /V, то есть числа различных между собой отрезков записей показания прибора, соответствующих по правилу (0.1) при 0 < т < N — 1 всевозможным точкам х €Е М. Изучение асимптотики числа "допустимых слов" при N —^ оо дает возможность оценить топологическую энтропию изучаемого отображения.

Основным результатом второй главы явилась следующая теорема. Обозначим через /г(/) топологическую энтропию отображения / (то есть меру хаотичности системы).

Теорема Существует алгоритм, который дает двойную последовательность такую, что

1. для любого I £ N последовательность невозрастающая при к —) +оо; и существует предел Нт^+оо '•= Ы > 0;

2. последовательность {/¿¿} неубывающая и /¿(/) < Нт^+00 /г/ < +оо;

3. если / - Липшицево отображение, то Л(/) < Нт^+00 Ы < +оо.

Еще одной из важных практических задач теории динамических систем является разработка конструктивных методов для исследования глобальной структуры траекторий системы.

Напомним, что бесконечная в обе стороны последовательность точек {х{, —оо < г < +оо} называется £-траекторией отображения /, если расстояние между образом /(а^) и х^+х меньше чем г: х) < £ для любого г. Если при этом последовательность {а^} является периодической, то она называется е-периодической траекторией, а точки ж, называются е-периодическими.

Следует подчеркнуть, что, как правило, точная траектория системы редко известна, а в действительности мы находим только £ — траекторию для достаточно мылых положительных е.

Точка х называется цепно-рекуррентной, если х есть е-периодическая для любого положительного £, то есть, существует периодическая £-траектория, проходящая через х. Цепно-рекуррентным множеством, называется множество всех цепно-рекуррентных точек. Известно, что цепно-рекуррентное множество инвариантное, замкнутое и содержит возвращающиеся траектории всех типов, таких как периодические, гомокли-нические и другие. Если через цепно-рекуррентную точку не проходит периодическая траектория, то существует сколь угодно малое возмущение в (7° топологии, для которой эта точка будет периодической [28, 30, 32]. Подмножество О, С называется компонентой цепно-рекуррентного множества, если любые две точки из могут быть соединены периодической е-траекторией для любого г > 0. Таким образом, цепно-рекуррентное множество может быть представлено в виде объединения непересекающихся инвариантных замкнутых компонент :

Q = \JQi г

Пусть {(¿1,(^21(^3, ■•} - компоненты цепно-рекуррентного множества динамической системы. Будем говорить, что между компонентами Qi и Qj есть связь €¿1 , если существует точка х такая, что а(х) С , и>(х) С .

Рассмотрим граф Г с множеством вершин {?}, соответствующих компонентам и с множеством ребер ¿-) ] в том и только в том случае, если существует связь Qi —>• Qj. Так построенный граф Г будем называть структурным графом динамической системы, а соответствующую матрицу переходов А = (а^) - структурной матрицей динамической системы /, а^ = 1, если существует ребро г —> ], иначе а^ = 0.

Структурный граф Г описывает глобальную динамику системы. В частности, структурный граф содержит информацию об аттракторах и их областях притяжения. Впервые структурная матрица динамической системы была определена в [27]. Авторы определяют здесь устойчивые связи между компонентами цепно-рекуррентного множества. А именно, пусть ~ компоненты цепно-рекуррентного множества, д : М М -непрерывное отображение, р - метрика на М. Рассмотрим расстояние р{1>9) = тахм р(/(х), д(х)) и обозначим носитель функции / — д через вирр(/ — д) = {х £ М : /(х) ф д{х)}- Связь С^^ —>• (¿^ называется устойчивой, если существует е > 0 такое, что любое возмущение д, р(/,д) < £, вирр{/ — д) С М имеет одинаковые связи —> Qj. В этой статье показано, что если динамическая система имеет конечное число компонент с устойчивыми связями, то существует конечный алгоритм построения структурной матрицы. Авторы приводят алгоритм построения структурной матрицы символического образа, которая, вообще говоря, не является структурной матрицей динамической системы. Основным недостатком предложенного метода является проверка того, что связи между компонентами устойчивые. Таким образом, возникает задача вычисления структурной матрицы без проверки устойчивости связей между компонентами. В диссертации построен алгоритм вычисления структурной матрицы динамической системы, причем требование устойчивости связей компонент цепно-рекуррентного множества снимается.

Основной результат третьей главы отражен в следующей теореме.

Теорема Существует алгоритм, который дает, двойную последовательность графов {Ст/й} такую, что

1. для любого I £ N последовательность графов {С^} сходится к графу Сг ;

2. если цепно-рекуррентное множество (3 имеет конечное число компонент, то последовательность графов {С;} за конечное число шагов совпадет со структурным графом Г динамической системы.

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

17 либо дополнительных или предварительных данных и представляют собой синтез теоретических результатов и компьютерно-ориентированных алгоритмов качественного исследования динамических систем.

1. Алексеев В.М. Символическая динамика, 11-ая математическая школа.- Киев. 1976. с. 128.

2. Боуэн Р. Методы символической динамики. Новое в зарубежной науке. Математика. Москва. 1979.

3. Динабург Е.И. Связь между различными энтропийными характеристиками динамических систем./ Изв. АН СССР. мат. 35. N 2. 1971. с. 324-366.

4. Каток А.Б. Гипотеза об энтропии. Математика. Гладкие динамические системы. Москва. 1977.

5. Макаренко Н.Г. Прикладные методы топологической динамики, препринт. Алма-Ата. 1991г.

6. Малинецкий Г.Г., Потапов А.Б. Современные проблемы нелинейной динамики. Москва. 2000г. 335 с.

7. Моисеев A.A. Символический образ динамической системы и алгоритмы его исследования// Тезисы докладов первой международной конференции "Дифференциальные уравнения и применения". 1996. с. 152.

8. Осипенко Г.С. О символическом образе динамической системы/ Сборник "Граничные задачи". Перьм. 1983. с. 101-105.

9. Писсанецки С. Технология разреженных матриц. Москва. 1988.

10. Шарковский А.Н., Майстренко Ю.Л., Романенко Е.Ю. Разностные уравнения и их приложения. Киев. 1986. 279 с.

11. Яглом A.M., Яглом И.М. Вероятность и информация. Москва. 1973. 511 с.

12. Anosov D.V. Geodesic flow on closed Riemannian manifold of negative curvature// Trudy Math. Steclov Institute. 1967. v. 90 (in Russian).

13. Bhatia N.P., Szego G.P. Stability theory of dynamical systems. N.Y. Springer. 1970.

14. Block L., Keesling J. Computing the topological entropy of maps of the interval with three monotone pieces// Journal of Statistical Physics. 1992. V.66. p.755-774.

15. Bowen R. Periodic points and measure for axiom A diffeomorphisms. Transactions of the American Mathematical Sociaty. 1971. p. 377-397.

16. Bronshtein I.U. Nonautonomous dynamical system. Kishinev. Shtinisa. 1984(in Russian).

17. Chen Qi, Edward Ott, Lyman P. Hard. Calculating the topological entropy of chaotic dynamical system// Physics Letters A. 1991. 156(48).

18. Collet P., Crutchfield J., Eckmann J. Computing the topological entropy of maps// Communications in mathematical physics. 1983. V.88. p.257-262.

19. Douglas L., Marcus B. An introduction to symbolic dynamics and coding.-New York. 1995.

20. Froyland Gary, Junge Oliver, Ochs Gunter. Rigorous computetion of topological entropy with respect to finite partition// Physica D. V. 154. 1-2. p. 68-84.

21. Gene H., Charles F., Loan V. Matrix computations.- Moscow. 1999.

22. Mizin D.A., Osipenko G.S., Kobyakov S. Yu. The estimates for the topological entropy of the dynamic system// Proceedings of the third international conference " Tools for mathematical modelling". 2001. p.85-105.

23. Nitecki Z., Shub M. Filtrations, decompositions, and explosions// Amer.J.of Math. 1975. v.97. .4. p.1029-1047.

24. Osipenko G., Komarchev I. Applied symbolic dynamics: Construction of periodic trajectories. World Scientific. WSSIAA. Singapore. 1995. N. 4. p. 573-587.

25. Osipenko G.S. Construction of Attractors and filtrations// Conley Index Theory, Banach Center Publications. 1999. V.47. p.173-197.

26. Osipenko G.S. The periodic points and symbolic dynamics// in Seminar on Dynamical Systems. Birkhauser Verlag. Basel. 1993. p.261-267.

27. Osipenko G.S., Salih Aytar, Kobyakov S. The structure matrix of dynamical system// Proceedings of the third international conference " Tools for mathematical modelling". 2001. p.85-105.

28. Pilugin S.Yu. The space of dynamical systems with C° topology. Lecture notes in math. Springer-Verlag. N.Y. 1994.