Применение символического образа для исследования непрерывных динамических систем.
Петренко Е. И. (СПбГУ, мат.-мех. ф-т, асп. каф. Информатики, 3 год)
Символический образ [1] представляет собой некую дискретизацию динамической системы и порождает символическую динамику, которая отражает поведение исходной системы. При помощи символического образа можно строить цепно-рекуррентные множества, инвариантные множества, находить неподвижные точки и периодические орбиты, оценивать энтропию, спектр Морса и многое другое. В работах [1,2] описаны различные способы реализации алгоритмов построения и анализа символического образа для дискретных динамических систем.
Целью нашей работы является применить описанные выше алгоритмы для непрерывных динамических систем. Приводится сравнение полученных результатов.
Пусть 
– некоторое компактное множество m-мерного пространства. Для начала мы приведем определения и способы построения символического образа для дискретных динамических систем, порожденных итерационными процессами вида 
. Диффеоморфизм 
задает дискретную динамическую систему на множестве . Фиксируем 
– конечное разбиение множества . Далее элементы разбиения 
будем называть ячейками. По множеству , набору ячеек 
и диффеоморфизму можно построить ориентированный граф следующим образом: ячейке будет соответствовать вершина графа; между двумя вершинами 
и 
есть ориентированное ребро, если образ ячейки, которая соответствует вершине , пересекается с вершиной , 
. Этот граф называется символическим образом [1].
Построение символического образа может быть очень трудоемкой задачей, если начинать его с мелкого разбиения. Поэтому мы используем технику подразбиений [2, 3]:
· для начала строится символический образ относительно крупного разбиения;
· потом выполняются алгоритмы анализа построенного символического образа, в результате которых, для определенного класса задач, некоторые ячейки можно исключить из рассмотрения;
· далее ячейки разбиваются на более мелкие, и процесс повторяется.
Цепно-рекуррентное множество системы – это множество таких точек, через которые проходит хотя бы одна траектория исходной системы. На символическом образе цепно-рекуррентному множеству соответствуют компоненты сильной связности. В [2] показано, что последовательность символических образов, построенных по технике последовательных подразбиений, сходится к цепно-рекуррентному множеству динамической системы.
Например, цепно-рекуррентное множество содержит все периодические траектории системы, и, в частности, все неподвижные [2].
Множеством неуходящих вершин будем называть такое множество вершин V символического образа, что для любой вершины v все достижимые из нее вершины лежат в V. В [2] было доказано, что множество неуходящих вершин символического образа при последовательном подразбиении сходится к положительному инвариантному множеству динамической системы. Аналогичным образом можно определить отрицательное инвариантное множество, если рассмотреть не входящие вершины.
В реализации алгоритма удобно рассматривать одинаковые ячейки. Каждая ячейка в таком случае представляется точкой её «верхнего левого угла». Разбиение области фазового пространства можно построить следующим способом: разобьем координатные оси на части одинаковой длины, так, чтобы по -ому направлению было 
частей. Всевозможные множества, состоящие по каждой координате из одного элемента разбиения, образуют искомое разбиение. Рассмотрим целочисленную систему координат, за единицу длины в которой принимается размер ячейки. В такой системе координат каждой ячейке соответствует единственная целочисленная координата. При вычислении образа ячейки проводится обратное преобразование координат (из целочисленной системы координат в исходную систему координат). Такой метод позволяет уменьшить объем памяти, требуемой для хранения ячейки.
Основные методы построения образа ячейки описаны в [2, 3, 4, 5]. От метода построения образа ячейки в большой степени зависит полученный результат и время, затраченное на его построение. Приведем некоторые из методов построения образа ячейки:
· Линейный метод: Строим образ ячейки в виде минимального прямоугольника, который содержит образы вершин.
· Точечный метод: Строим образ ячейки как набор ячеек, которые содержат образы равномерно выбранных точек исходной ячейки.
· Адаптивный метод: Строим образ ячейки по точкам в зависимости от поведения системы.
· Методы интервальной арифметики: Рассматриваем ячейку как интервальный вектор.
Для построения цепно-рекуррентного множества мы используем алгоритм Тарьяна [3], которые работает за линейное время.
Пусть на множестве задана система вида 
и ее решение 
с начальными данными 
. Фиксируем 
– сдвиг. Введем отображение сдвига по траектории следующим образом: 
.
Символическим образом непрерывной системы относительно сдвига 
будем называть символический образ, построенный относительно отображения сдвига 
.
Для построения символического образа мы используем методы, описанные в [2, 3, 4]. Также, для повышения производительности системы, и для экономии памяти, мы применяем генерацию кода «на лету» [6]. Для построения отображения сдвига относительно траектории применяется метод Рунге-Кутта четвертого порядка.
Рассмотрим систему Дуффинга:
Система имеет три состояния равновесия:
· 
– гиперболическая точка
· 
– фокус
· 
– фокус
Для построения символического образа этой системы выберем оператор сдвига на 0.1. Оператор сдвига будем реализовывать с помощью метода Рунге-Кутта четвертого порядка. Для вычисления значения оператора сдвига проведем 100 шагов метода интегрирования дифференциального уравнения с шагом 0.001 по времени.
Символический образ строится описанным выше способом. На каждом шаге будем выделять цепно-рекуррентное множество. Начальное разбиение области исследования 3х3. Начальную область следует выбирать так, чтобы она содержала в себе все состояния равновесия. Выберем область 
, проведем 9 шагов построения символического образа.
Полученный результат показывает цепно-рекуррентное множество, которое включает в себя состояния равновесия. Проведем построение цепно-рекуррентного множества на области 
. В данном случае это позволит исключить из рассмотрения некоторые пути из символического образа, построенного на области . Проведем 9 шагов построения.
Полученные результаты показывают, что на более мелкой области мы получаем меньшее цепно-рекуррентное множество системы. Снова уменьшим область исследования до 
, проведем 10 шагов построения символического образа.
В полученном результате мы можем увидеть три компоненты, которые соответствуют трем найденным аналитически состояниям равновесия системы.
Мы применили алгоритмы построения символического образа к непрерывным динамическим системам. При помощи полученной реализации были построены различные цепно-рекуррентные множества для отображения Дуффинга. Полученные результаты не противоречат аналитическим данным.
Описанные результаты были реализованы в рамках программного комплекса исследования динамических систем с помощью символического образа и используются для практического освоения курса «Компьютерное моделирование динамических систем» на математико-механическом факультете СПбГУ.
, «О символическом образе динамической системы», сб. Граничные задачи, Пермь, 1983 , «Введение в символический анализ динамических систем», Изд. СПбГУ, 2005 , «Разработка и реализация алгоритмов построения символического образа», Эл. ж. «Дифференциальные уравнения и процессы управления», 2006, 3, http://www. math. *****/diffjournal/j/ , «Разработка и реализация программного комплекса исследования динамических систем методами символической динамики», конф. «Технологии Microsoft в теории и практике программирования», Материалы межвузовского конкурса-конференции студентов, аспирантов и молодых ученых Северо-запада (1-2 марта 2005) , Санкт-Петербург, 2005 , , «Применение методов интервальной арифметики к задаче построения символического образа», Эл. ж. «Дифференциальные уравнения и процессы управления», 2006, 4, http://www. math. *****/diffjournal/j/ , «Применение динамической кодогенерации при исследовании динамических систем с помощью символического образа», готовится к печати