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

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На пранах рукописи ЪШ С/СГ 7

Петренко

Ешнний Игоревич 003483870

Компьютерное исследование динамических систем на основе метода символического образа

05.13.11 Математическое. и программное; обеспечение нычнелитедьных машин, комплексов и компьютерных «тей

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических ня\к

1 о л С.-7

Сапкт-Петербур| 2009

003483870

Работа выполнена па Кафедре информатики математико-механического факультета Санкт-Петербургского государственного университета.

Н ау ч н ы й [ >у ко вод и 'га) 1 ь: Официальные оппоненты:

Ведущая организация:

кандидат физико-математических паук, доцент Ампмлова Наталья Борисовна.

доктор физико-математических паук. н}юфес:сор Флогонтон Александр Влади ми рови ч (Росси иск и й государство I н ы й педагогический университет им. А.И. Герцена),

доктор физико-математических наук, профессор Андрианов Сергей Николаевич (Санкт-Петербургский тсударст венный университет).

Санкт-Петербургский государственный политехнический университет.

Защита диссертации состоится " /14>да в час. на

заседании совета Д 212.232.51 по защите докторских и кандидатских диссертаций при Санкт-Петербургском государственном университете по адресу: 198504. Санкт-Петербург, Старый Петергоф, Университетский пр., д. 28. математико-мехаиический факультет Санкт-Петербургского государственного университета, ауд. 405.

С диссертацией можно ознакомиться в Научной библиотеке им. М.Горького Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб. 7/9.

Автореферат разослан "

2009 года.

Ученый секретарь диссертационного совета доктор физико-математических наук, профессор

И.К. Даугавет

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

При решении этой задачи используется идея разбиения фазового пространства на конечный набор ячеек (клеток) и моделирования поведения системы в соответствии с преобразованиями этих ячеек под действием системы. Уточнение фазового портрета происходит при последовательном подразбиении ячеек покрытия. Практическая реализация таких методов сталкивается с проблемой быстрого роста числа ячеек, что повышает сложность разработки и реализации применимых на практике методов. Для исследования и моделирования динамических систем Г. С. Осипенко предложил метод символического образа, представляющий собой развитие идеи о разбиении фазового пространства и кодировании траекторий [10]. Этот метод позволяет получать важные характеристики исходной динамической системы с помощью алгоритмов на ориентированном графе, вершинами которого являются элементы разбиения фазового пространства, а ребра определяются поведением системы на элементах разбиения.

Задача локализации цепио-рекуррептпых множеств решается с помощью выделения па графе символического образа компонент сильной связности (классов эквивалентности вершин, между которыми существует путь). Получаемый при помощи этого метода результат существенно зависит от способа построения символического образа. В литературе описан наиболее простой метод построения образа ячейки (далее будем называть его точечный метод), который исследует поведение системы через поведение системы ira фиксированном наборе точек [9,10]. Для некоторых систем применение такого метода может оказаться затруднительным (из-за необходимости рассмотрения очень большого числа точек), поэтому требуется разработать новые методы построения образа ячейки.

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

Второй важной характеристикой поведения системы является устойчивость ее цепно-рекуррентного множества при малом возмущении системы (правых частей). Она имеет большое значение для приложений, поскольку определение областей существования устойчивых режимов при изменении как параметров, так и правых частей, позволяет исследователю контролировать поведение системы. Непосредственная проверка такой устойчивости представляется затруднительной. Теоретически она может быть сведена к эквивалентной задаче оценке предельного множества показателей Ляпунова периодических гтсепдо-траекторий системы спектра Морса. Эта характеристика особенно важна, когда динамическая система имеет бесконечно много периодических траекторий большого периода. Г. С. Осипенко впервые предложил ■теоретический способ оценки спектра Морса динамической системы с помощью оснащенного символического образа [10], что позволило впервые получить компьютерный способ проверки устойчивости цепно-рекуррентного множества.

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

зоваиы методы построения оснащенного символического образа (образа ячейки для системы па проективном расширении), впервые реализован алгоритм оценки спектра Морса оснащенного символического образа, на основании которого получены численные результаты для систем, имеющих нетривиальные цепно-рекуррентные множества.

Третьей важной характеристикой динамических систем является инвариантная мера. Инвариантная мера динамической системы дает важное для приложений вероятностное описание поведения системы. Динамическая система может иметь много инвариантных мер, поэтому нужно выбирать те, которые интересны с точки зрения динамики. Аппроксимации инвариантной меры посвящено много работ, где в основном используется конечная аппроксимация оператора Перрона-Фробениуса [8], которая позволяет построить только одну специальную меру и только в случае, если известно, что такая мера существует для конкретной системы. Проверка этого свойства оказывается сложной теоретической задачей.

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

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

Цели И задачи диссертационной работы. Основными целями работы являются разработка и реализация программного комплекса компьютерного исследования дискретных и непрерывных динамических систем, основанного на методе символического образа, который впервые объединяет описанные выше методы исследования динамических систем: построение цепио-рекуррентного множества динамической системы при помощи различных методов построения символического образа (образа ячейки); вычисление оценки спектра Морса динамической системы через применение симплекс-

метода к ориентированному графу, построенному для динамической системы; построение приближения к инвариантной мере динамической системы, а также вычисление оценки энтропии по построенной инвариантной мере.

Для достижения обозначенных целей были поставлены следующие задачи:

• разработать и реализовать новые алгоритмы построения символического образа (образа ячейки), провести сравнение полученных алгоритмов, получить оценки скорости построения символического образа;

• исследовать и оценить возможность применения симплекс-метода к ориентированному графу оснащенного символического образа для получения оценки спектра Морса динамической системы;

• разработать и сравнить различные алгоритмы построения стационарного процесса на графе символического образа для получения приближения к инвариантной мере динамической системы;

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

Основные результаты.

1. Разработан и реализован программный комплекс компьютерного исследования динамических систем на основе метода символического образа, который впервые объединяет в себе: методы построения цепко-рекуррентных множеств дискретных и непрерывных динамических систем; метод построения оценки спектра Морса для непрерывных и дискретных динамических систем, применимый для компьютерной проверки устойчивости цепио-рекуррентпого множества; метод построения приближения к инвариантной мере динамической системы. В комплексе была успешно использована динамическая генерация кода. Реализованный программный комплекс может быть расширен новыми методами и алгоритмами исследования динамических систем. Компоненты данного программного комплекса могут быть использованы как части другой системы.

2. Разработаны и проанализированы линейный, точечный, улучшенный точечный, адаптивный и прямоугольный адаптивный методы построения символического образа (образа ячейки). Доказана теорема об оценках

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

3. Разработан алгоритм поиска контуров с минимальной и максимальной характеристикой на ориентированном графе, основанный на модификации симплекс-метода, перенесенной на ориентированный граф, что впервые позволило получить компьютерный метод оценки спектра Морса динамической системы и способ проверки устойчивости цепно-рекуррентного множества динамической системы. Доказана теорема о сходимости метода.

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

Научная новизна. Все полученные в работе результаты являются новыми. Научная новизна заключается в следующем:

• разработаны и проанализированы: линейный, точечный, улучшенный точечный, адаптивный и прямоугольный адаптивный методы построения символического образа (образа ячейки), при этом, линейный, точечный, адаптивный методы применимы для построения оснащенного символического образа. Для всех методов приведена сравнительная характеристика и оценки сложности работы;

• впервые реализован метод получения оценки спектра Морса динамической системы, основанный на применение симплекс-метода к ориентированному графу оснащенного символического образа;

• впервые разработаны и реализованы методы построения приближения к инвариантной мере динамической системы путем построения стационарного процесса па графе символического образа.

Практическая ценность. Разработанный программный комплекс

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

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

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

Апробация работы. Результаты работы докладывались:

• на конкурсе - конференции работ студентов, аспирантов и молодых ученых "Технологии Microsoft в теории и практике программирования" (Санкт-Петербург, 2004, 2005, 2007, 2008 — диплом первой степени)

• на конкурсе стипендий Intel (Санкт-Петербург, 2006, 2007)

• на VIII-й международной научно-технической конференции "Компьютерное моделирование" (Санкт-Петербург, 2007)

• на третьей международной научно-практической конференции "Современные информационные технологии" (Москва, 2008)

• па международной научной конференции "Космос, астрономия и программирование (Лавровские чтения)" (Санкт-Петербург, 2008)

• на шестой конференции "EUROMECH Nonlinear Dynamics Conference (EN О С 2008)" (Санкт-Петербург, 2008)

• па XL международной конференции "Процессы управления и устойчивость" Control Processes and Stability (CPS'09) (Санкт-Петербург, 2009)

• на 5-й международной конференции "Dynamical Systems and Applications" (Constantza, Romania, 2009)

Публикации. Основные результаты представлены в 7 работах автора, перечисленных в прилагающемся списке работ автора. Работы [1,2] опубликованы в изданиях по перечню ВАК. В работах [1| и [6| автору принадлежит разработка и реализация методов построения инвариантных мер, а также реализации метода получения оценки энтропии. В работе [7] автору принадлежит

разработка и реализация методов построения образа ячейки в проективном пространстве, реализация метода вычисления оценки спектра Морса по динамической системе.

Структура И объем работы. Диссертационная работа объемом 197 машинописных страниц состоит из: введения, четырех глав, одного приложения и списка литературы, содержащего 85 наименований.

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

Символический образ представляет собой ориентированный граф, который строится по дискретной динамической системе хп+1 = /(хп), / : О С К'" —> К"', / диффеоморфизм, или по отображению сдвига для непрерывной динамической системы (х = д{х)), и разбиению множества £> па конечный набор ячеек {С,;}. Вершинам графа соответствуют ячейки, между вершинами г и з существует дуга { -> j, тогда и только тогда, когда /(С/) П С] Ф 0.

В реализации алгоритма рассматриваются одинаковые ячейки. Каждая ячейка в таком случае представляется точкой её "верхнего левого угла". Множество В берется в виде параллелепипеда, ориентированного по осям координат. Координатные оси пространства Ет разбиваются на части одинаковой длины, так, чтобы по ¿-ому направлению множество О разбивалось па р, частей. Рассматривается система координат, за единицу длины в которой принимается размер ячейки. Каждой ячейке сопоставляется набор из тп целых чисел.

Автором разработаны, реализованы и проанализированы пять методов построения образа ячейки:

Линейный метод. Образ ячейки оценивается через расширенный прямоугольник, ориентированный по осям координат, построенный по точкам образов (под действием системы) вершин исходной ячейки. Коэффициент расширения является параметром метода.

Точечный метод. Образ ячейки строится как объединение ячеек, которым принадлежат образы (под действием системы) равномерно выбранных точек внутри исходной ячейки. Количество точек является параметром данного метода.

Улучшенный точечный метод. Работает аналогично точечному методу, однако, если образ некоторый точки оказывается близко к границе ячейки, то к результату добавляются соседние ячейки.

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

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

Полученные оценки сложности построения одного шага символического образа сформулированы в виде следующей теоремы:

Теорема 1. Пусть N - количество ячеек (вершин в символическом образе), тогда сложность построения следующего шага: для точечного и улучшенного точечного методов — в среднем O(N); для линейного, адап-

тивного и прямоугольного адаптивного методов - в среднем, О(N2).

Разработанный автором комплекс компьютерного исследования динамических систем имеет меньшую оценку сложности построения символического образа точечным методом (в среднем), по сравнению с реализацией, приведенной в [9]. Полученные оценки сложности позволяют говорить о практической применимости приведенных реализаций, полученные компьютерные эксперименты подтверждают это.

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

Вторая глава содержит описание метода построения оценки спектра Морса динамической систем!.! с помощью оснащенного символического образа, построенного для специального расширения исходной системы, при этом каждой дуге присваивается некоторый вес. Пусть динамическая система задана в виде xn+i = f(xn). Рассматривается расширенная динамическая система:

_ Df{xn)vn

Xn+l — j{Xn), f„+l — . _ -г-г,

\Df(xn)vn\

где Xi G Rm, Vi € Pm~l, Pm~y проективное пространство (множество всех прямых в К"1, проходящих через начало координат). Автором реализованы три способа введения координат в проективном пространстве: для двумерного пространства координаты вводятся как угол наклона прямой и через отрезки, для трехмерного сферические координаты. На проективном пространстве были реализованы линейный, точечный и адаптивный методы.

Для оценки спектра Морса оснащенного символического образа нужно найти контуры с экстремальными характеристиками на каждой компоненте сильной связности символического образа. Объединение интервалов составленных из минимальных и максимальных значений этих характеристик па каждой компоненте сильной связности задает спектр Морса оснащенного символического образа. Вес контура определяется как среднее значение весов его ребер.

Для решения этой задачи был реализован метод, который сводит задачу поиска контура к задаче линейного программирования на ориентированном

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

Теорема 2. Предложенный метод поиска контцров с экстремальными характеристиками сходится к экстремальному решению за конечное число шагов (как симплекс-метод).

В заключение приводятся результаты компьютерных экспериментов. В третьей главе описано решение задачи построения приближения к инвариантной мере динамической системы. Путь G — {V, Е) — граф символического образа. Тогда функция R задает инвариантную меру (вес) на дугах,

если для всех е € Е ц(е) > 0, для каждой вершины сумма мер входящих дуг равна сумме мер исходящих дуг, и сумма мер на всех дугах равна 1. Меру можно расширить на множество V как сумму мер входящих или исходящих ребер.

Автором разработаны и реализованы два способа построения инвариантной меры на символическом образе. Первый способ основан на следующем свойстве: пусть и /¿2 инвариантные меры, тогда и их выпуклая линейная комбинация тоже является инвариантной мерой. Инвариантная мера строится как линейная комбинация мер, сосредоточенных ira простых циклах. Рассматриваются различш,ге алгоритмы поиска простых циклов па графе. Поскольку их количество может быть велико (экспоненциально от количества вершин), предложенные, алгоритмы позволяют находить лишь некоторые из простых циклов (полиномиальное количество от количества вершин), что не мешает получать приемлемые, с точки зрения исходной задачи, результаты. Доказана теорема:

Теорема 3. Алгоритм частичного перебора простых циклов завершается за 0(1УЦЕ1) шагов.

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

работе рассмотрены критерии остановки метода балансировки, приводится их сравнительный анализ. Доказана теорема:

Теорема 4. Последовательность балансировок, получаемая алгоритмом, сходится.

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

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

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

Разработанный комплекс реализован на языке С// 3.0, который входит в состав Microsoft .NET Framework 3.5. Для построения рисунков компьютерных экспериментов используется пакет GNUPLQT. Все использованные программные продукты распространяются бесплатно для академического использования-. На языке С// написано'около 92 тысяч строк кода, на языке С—-f-написано около 35 тысяч строк кода.

В начале главы приведено подробное описание подсистемы динамической генерации кода, которая позволяется снизить требования к оперативной памяти и повысить производительность системы. По заданной динамической системе программный комплекс генерирует код реализации некоторых алгоритмов и структур данных. Сгенерированный код компилируется при помощи встроенного в .NET Framework компилятора языка С#, после чего загру-

жается и используется. Динамическая генерация кода впервые применяется к реализации методов исследования динамических систем. В разработанном программном комплексе она используется для реализации методов целочисленной системы координат, методов построения образа ячеек и для создания структуры данных представления целочисленной координаты ячейки. Использование динамической генерации кода позволило снизить требования к оперативной памяти и снизить время, требуемое для построения символического образа. В диссертационной работе приведены результаты компьютерных экспериментов сравнения времени работы программного комплекса с использованием динамической генерации кода и без нее. По результатам экспериментов, экономия оперативной памяти соствляет от 30% (для 4-х мерных систем), до 60%(для двумерного случая), выигрыш по времени при построении цепно-рекуррентного множества составляет в среднем 15%.

Для организации взаимодействия объектов программного комплекса применяются компоненты и сервисы. Для этого используется концепция "обращение контроля". Такой подход широко применяется при разработке больших программных продуктов. Автором были проанализированы доступные реализации библиотек обращения контроля и была реализована собственная библиотека обращения контроля, которая обладает необходимыми для разрабатываемого программного комплекса свойствами и простотой использования.

Разработанный программный комплекс компьютерного исследования динамических систем па основе метода символического образа может быть применен для исследования непрерывных и дискретных динамических систем небольшой размерности. Он используется в курсе по компьютерному исследованию динамических систем па математическом факультете СПбГУ, а также может быть использован для исследования нетривиальных динамических систем, и в учебном процессе.

Заключение содержит список основных результатов, полученных в работе.

Публикации автора по теме диссертации Статьи в журналах, рекомендованных ВАК:

1. Ампилова Н. Б.. Петренко Е. И. Об оценке энтропии символического образа динамической системы //' Вестник СПбГУ, сер.10, вып.З. — 2008. — С. 3-11.

2. Петренко Е. И. Оптимизация алгоритмов построения инвариантного мно-

жества динамической системы с помощью генерации кода // Вестник СПб-ГУ. сер. 10. вып.З. 2009. Сентябрь. С. 1L2 118.

Другие публикации:

3. Петренко Е. И. Разработка и реализация алгоритмов построения символического образа /;' Эл. Ж. Дифф. уравнения и процессы управления 200G. № 3. С. 55 96. http://www.math.spbu.ru/<UfljoimmI;j.

4. Петренко Е. И. Применение символического образа для исследования непрерывных динамических систем // Труды III Международной научно-практической конф.: Современные! информационные технологии / Под ред. В. А. Сухомлин. М.: МГУ. 2008. С. 437 442.

5. Петренко Е. И. Об оценке энтропии символического образа ,'/ Процессы управления и устойчивость: Труды 40-й международной научной конференции аспирантов и студентов Под ред. Н. В. Смирнова, Г. Ш. Тамаеяна. СПб: Издат. СПбГУ, 2009. С. 497 502.

С. Романовский II. В., Ампилова Н. Б., Петренко Е. И. О .максимизации энтропии при линейных ограничениях . Труды Международной научной конференции "Космос, астрономия и программирование (Лавровские чтения)". СПб: СПбГУ, 2008. С. 181 185.

7. Computation of the Morse spectrum / G. S. Osipenko. .1. V. Romanovsky, E. I. Petreiiko, N. B. Anipilova /•/ ./. of Math. Sei: 2004. Vol. 120, no. 2. Pp. 1155 11GG. hUp:/ /www.mgeiilacomi(4 l.com (чл11(П11/к1и; jotli ■ 2()()4/11()0()()12()/(Ю()0(ЮП2/()018И93 ^

Цитированная литература:

8. Döllnitz M., Junge О. Set Oriented Methods for Dynamical Systems / Ed. by B. Fiedler. Berlin, Germany: Freie Universität. Berlin, Institut für Mathematik I. 2002. Feb. Vol. 2. P. 1098.

9. Fundinyer D. Investigating Dynamics by Multilevel Phase Space Discretization: Ph.D. thesis / Institut für Parallele und Verteilte Systeme. Abteilung Bildversteheu. 200G. http://Hib.uni-.s4uttgart.dc/opits/volltot<-i'2(KH5/2ßl4.

10. Osipenko G. Dynamical Systems, Graphs, and Algorithms. Springer, 2007. Vol. 1889 of Lecture Notes in Mathematics. P. 288. http.%^^www.springor.<toni/iiCTth/analysi4/l«x)k/978-3-i>4l)-35593-9.

Подписано к IIC'IHIII 30.09.2009г Форма! 00 х Si 1/16. Byxiaia (xjxenian. Fapmuvpa Timrs. Печап» цифровая. Псч. л 0.7. Тираж 100 íK i. Закат 4514 .

( )i печги ano li oí еле oiirpai imijotl но. un рафии химическою факу..1ы гга С^По] V 11)8501, Самкт-Пен'рГк рг, Старый Петергоф. Уиинергшегскнй пр. 20 Te.i.: (S12)Î2H-10KÏ, Г28-(Й19

1 Введение

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

2.1 Определения.

2.2 Символический образ динамической системы.

2.3 Построение символического образа для непрерывной системы

2.4 Анализ символического образа.

2.4.1 Локализация цепно-рекуррентных множеств

2.4.2 Локализация инвариантных множеств.

2.4.3 Алгоритм выделения компонент сильной связности

2.5 Представление ячейки.

2.6 Методы построения образа ячейки.

2.6.1 Линейный метод.

2.6.2 Точечный метод

2.6.3 Улучшенный точечный метод.

2.6.4 Адаптивный метод.

2.6.5 Прямоугольный адаптивный метод.

2.7 Реализация.

2.8 Структура данных символического образа.

2.9 Численный эксперимент.

2.9.1 Сжимающее отображение.

2.9.2 Отображение Хенона [54].

2.9.3 Трехмерная система [44,51].

2.9.4 Отображение Икеда [57].

2.9.5 Отображение с задержкой а = 2.27 [39].

2.9.6 Система Ван-дер-Поля [72].

2.9.7 Система Дуффинга [22].

3 Оценка спектра Морса динамической системы

3.1 Проективное пространство и показатели Ляпунова.

3.1.1 Характеристический показатель Ляпунова.

3.1.2 Определение проективного пространства.

3.1.3 Координаты в проективном пространстве.

3.1.4 Прямоугольные координаты в Р

3.1.5 Прямоугольные координаты в pm1.

3.2 Символический образ системы на проективном расслоении

3.3 Методы построения образа проективной части ячейки

3.3.1 Линейный метод.

3.3.2 Точечный и улучшенный точечный методы.

3.3.3 Адаптивный метод.

3.4 Спектр Морса динамической системы. Оценка спектра Морса.

3.4.1 Определение спектра Морса.

3.4.2 Оснащенный символический образ и его спектр

3.4.3 Локализация спектра Морса динамической системы

3.5 Алгоритм вычисления спектра Морса.

3.5.1 Определение контуров с экстремальными характеристиками

3.5.2 Алгоритм построения дерева и оптимального контура

3.5.3 Поиск начального контура

3.6 Численный эксперимент.

3.6.1 Линейная система на плоскости 3.6.2 Отображение Хенона [54].

3.6.3 Отображение с задержкой [19]

4 Методы приближенного построения инвариантных мер динамических систем

4.1 Инвариантная мера

4.1.1 Определение инвариантной меры.

4.1.2 Основные свойства инвариантной меры на графе

4.2 Построение инвариантных мер.

4.2.1 Метод поиска простых циклов

4.2.2 Метод балансировки.

4.2.3 Скорость сходимости.

4.3 Численный эксперимент. Построение инвариантной меры

4.3.1 Отображение Хенона.

4.3.2 Отображение Икеда.

4.4 Оценка энтропии символического образа.

4.5 Оценка топологической энтропии системы через итерации кривой.

4.6 Численный эксперимент. Вычисление энтропии.

4.6.1 Отображение Хенона.

4.6.2 Отображение Икеда.

5 Особенности реализации

5.1 Динамическая генерация кода.

5.1.1 Введение.

5.1.2 Применение генерации кода

5.1.3 Схема работы программного комплекса.'

5.1.4 Достоинства подхода.

5.1.5 Обобщения (generics) и генерация кода.

5.1.6 Неявные типовые параметры.

5.1.7 Ускорение работы линейного метода.

5.1.8 Ускорение работы улучшенного точечного метода

5.1.9 Ускорение работы адаптивного метода.

5.1.10 Реализация целочисленной системы координат

5.1.11 Анализ производительности программного комплекса в целом.

5.1.12 Результаты эксперимента.

5.1.13 Инверсия управления (1оС).

5.1.14 Генерация форм для пользовательского интерфейса

5.2 Архитектура подсистемы построения символического образа

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

Исторически гладкие динамические системы с непрерывным временем привлекли внимание после открытия Ньютоном того факта, что движение механических объектов может быть описано обыкновенными дифференциальными уравнениями второго порядка. Ньютон решил задачу двух тел. Однако решение задачи трех тел (Солнце, Земля, Луна) оказалось намного сложнее. После многочисленных попыток ученых того времени стало ясно, что эту задачу невозможно решить аналитически, получить решение в явном виде.

В начале 19-го века Пуанкаре задался вопросом, будет ли система планет задачи трех тел существовать вечно или планеты разлетятся на бесконечные расстояния. Разработанный им геометрический подход положил начало современной динамике, в которой изучается долгосрочное асимптотическое поведение системы при помощи методов, не основанных на знании ее решений в явном виде [10]. Пуанкаре указал на возможность существования хаоса в системе, т.е. такого поведения системы, при котором траектории апериодичны, а решения с близкими начальными данными оказываются существенно различными.

В 1963 году вышла работа Лоренца [63], в которой автор обсуждал чувствительную зависимость от начальных данных при исследовании гидродинамической модели для предсказания погоды. Рассмотренная им система была записана в виде системы дифференциальных уравнений. Он обнаружил, что траектории системы развиваются нерегулярно и апе-риодично. Две траектории с близкими начальными данными оказываются существенно различными, таким образом, система ведет себя непредсказуемо, в том смысле, что малейшие ошибки в измерении состояния атмосферы будут быстро расти, что сделает долгосрочный прогноз погоды неправильным. Однако Лоренц показал, что у хаоса есть структура (впоследствии, такого рода структуры стали называть странными аттракторами).

Понятие странного аттрактора (аттрактора с хаотичной структурой) было введено в 1971 году в работе Рюэля и Такенса [78]. Авторы описывали новую теорию турбулентности в жидкостях, основанную на предположениях о существовании странных аттракторов. Спустя несколько лет М. Смит [80] нашел примеры хаоса в разностных уравнениях, описывающих развитие популяции в биологии.

В последние годы широкое распространение получил метод интервального анализа. Компьютерные методы решения задач с помощью интервальной арифметики подробно описаны в работах [14,32,33,68,84]. В работе [3] представление ячейки покрытия в виде интервального вектора было использовано при реализации алгоритма локализации инвариантных множеств. Следует отметить работу У. Такера [82], в которой было доказано, что для "классических" значений параметров в системе Лоренца [63] имеется аттрактор. У. Такер разработал алгоритм, основанный на использовании интервальной арифметики с направленным округлением, позволяющий находить точные решения большого класса обыкновенных дифференциальных уравнений. Подход Такера при исследовании системы Лоренца был основан на комбинации аналитических и компьютерных методов: строгих вычислений и теории нормальных форм. В работе [65] авторы успешно применяют методы интервальной арифметики для доказательства существования хаоса в системе Лоренца.

Один из основных классов компьютерных методов исследования динамических систем представляют так называемые методы, основанные на множествах (set-oriented methods), которые используют конечное разбиение фазового пространства на клетки (ячейки) и отслеживают динамику системы по попаданию точек траекторий исследуемой системы в эти клетки. Для выбранной области фазового пространства К, строится последовательное подразбиение ячеек, удаляются те ячейки, образы которых заведомо не принадлежат К. При стремлении диаметра ячеек к нулю мы можем получать все более точный фазовый портрет. Реализация таких методов может использовать параллельные вычисления [31]. На этих методах основан алгоритм построения аттрактора динамической системы, описанный в работах [44-46,64]. Шу. [55] предлагает способ исследования динамической системы с помощью отображения ячейка-в-ячейку. Рассматриваются два подхода: простое отображение ячейка-в-ячейку и обобщенное отображение. Первый подход оказался эффективным при исследовании глобальной структуры динамических систем с хаотическим поведением траекторий. Отображение ячейка-в-ячейку рассматривается как приближение исходного отображения / отображением ячеек. Предполагается, что образ ячейки Mj есть Mj, если /(с) Е Mj, где с € Mi — центр ячейки. Во втором подходе предполагается, что образ ячейки Mi может состоять из нескольких ячеек Mjx,., Mjt, вероятности перехода из Mi в Mjk определяются пропорционально мерам множеств f(Mi)C\Mjk. Данный метод приводит к конечным марковским цепям и работе с матрицами большого порядка. Оба подхода являются компьютерно-ориентированными, хотя реализация второго метода представляет определенные трудности [55]. Основным недостатком методов Шу является их недостаточное теоретическое обоснование.

В 1983 году Г.С. Осипенко [16] предложил метод символического образа для исследования динамических систем. Этот метод можно рассматривать как обобщение идей, предложенных в [55]. Символический образ есть конечная аппроксимация динамической системы, представляющая собой ориентированный граф [6, 29]. Он строится по заданному покрытию фазового пространства ячейками С*, вершины графа соответствуют ячейкам, дуги — связям между ними, а именно: вершины г и j соединяются дугой, если образ ячейки С{ при?действии динамической системы пересекается с ячейкой Cj. В работах [15,16,19,21,43,72] приводятся доказательства сходимости метода при решении различных задач, например, построении инвариантных и цепно-рекуррентного множеств динамических систем.

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

• траекториям системы соответствуют допустимые пути на графе;

• символический образ отражает глобальную структуру динамической системы;

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

Полученная при последовательном подразбиении ячеек покрытия последовательность символических образов позволяет получить приближение к динамике системы, при этом точность построения оценивается через параметры символического образа. Многие задачи исследования динамических систем можно решать, используя алгоритмы на ориентированных графах [16,19,21,52,71,72]. Наиболее важная и часто решаемая задача — локализация цепно-рекуррентных множеств динамической системы. Символический образ широко используется при компьютерном исследовании динамических систем. Так, в работе [38] авторы строят цепь Маркова для системы на ячейках; сделан переход к ориентированному графу; далее в терминах неориентированных графов формулируется и решается задача построения разбиения множества ячеек на набор "почти инвариантных множеств". В работе [46] приводится метод построения цепно-рекуррентного множества динамической системы с помощью ориентированного графа. В [58] авторы используют символический образ для построения цепно-рекуррентных множеств динамических систем. Приведено подробное описание алгоритмов построения образа ячейки, описаны особенности реализации графа. В описании алгоритмов акцент сделан на экономию памяти и производительность. Дан способ построения символического образа для непрерывной динамической системы.

Нужно отметить, что быстрое развитие вычислительной техники позволяет применять компьютерные методы как неотъемлемую часть исследований динамических систем и потребность в их создании возрастает. Вопросам компьютерного исследования динамических систем посвящено достаточное количество работ. Они включают как исследования отдельных систем [1,34,36,37], так и разработку программных комплексов [4,5,11,12].

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

На данный момент не существует комплекса компьютерного исследования динамических систем, который реализует все описанные методы. Автором был разработан и реализован программный комплекс компьютерного исследования динамических систем на основе метода символического образа, который позволяет решать описанные задачи. В программном комплексе впервые применена динамическая генерация кода [24].

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

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

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

• построение приближения к инвариантной мере динамической системы; при этом, два последних класса задач решаются впервые.

Локализация цепно-рекуррентных множеств

Траекториям системы соответствуют пути на символическом образе, при этом периодическим траекториям соответствуют периодические пути. Как показано в [19, 72], при последовательном подразбиении ячеек покрытия и стремлении их диаметров к нулю мы получаем последовательность символических образов, которая позволяет локализовать траектории с точностью, не меньшей чем диаметр покрытия. Все вершины символического образа можно разбить на классы эквивалентности, такое разбиение соответствует разбиению на компоненты сильной связности ориентированного графа символического образа(классов эквивалентности вершин, между которыми существует путь). Таким образом, мы получаем возможность локализовать цепно-рекуррентные множества исходной системы. Цепно-рекуррентное множество содержит все периодические псевдо-траектории, оно приближает множество.периодических траекторий. Локализация цепно-рекуррентного множества является начальным шагом многих методов исследования динамических систем. Нужно отметить, что локализация цепно-рекуррентных множеств (кроме простейших — множеств неподвижных точек) является затруднительной при использовании классических методов численного анализа, поскольку они дают немного информации об асимптотике системы [1,19,72]. Алгоритмы локализации таких множеств сводятся к следующему: цепно-рекуррентное множество системы локализуется как объединение компонент сильной связности на ориентированном графе символического образа. Для выделения компонент сильной связности используется хорошо известный алгоритм Тарьяна [25], который имеет линейную по числу вершин и дуг сложность.

Символический образ и скорость работы алгоритмов его построения зависят от метода построения образа ячейки. В работе диссертанта [21] рассмотрены алгоритмы построения образа ячеек, приведены описание их реализации и сравнительная характеристика. Разработан и реализован способ представления ячейки в памяти, позволяющий избежать проблем с ошибками округления для чисел с плавающей точкой.

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

Оценка спектра Морса

Спектр Морса [15,19, 42, 43, 72] — это предельное множество показателей Ляпунова периодических псевдо-траекторий. Эта характеристика особенно важна, когда динамическая система имеет бесконечно много периодических траекторий большого периода. Оценка спектра Морса позволяет проверить [19] устойчивость цепно-рекуррентного множества при малом возмущении системы (правых частей). Устойчивость цепно-рекуррентного множества имеет большое значение для приложений, поскольку определение областей существования устойчивых режимов при изменении как параметров, так и правых частей, позволяет исследователю контролировать поведение системы. Показатель Ляпунова для траектории системы определяется, согласно [19]', одномерным подпространством, натянутым на единичный вектор в касательном пространстве. Такой вектор можно рассматривать как точку в проективном пространстве.

Рассматривается расширенная динамическая система, фазовое пространство которой состоит из пар вида (x,v), где х — точка исходного фазового пространства, a v — точка проективного пространства. Первая компонента расширенной системы действует аналогично исходной, вторая — "поворачивает" вектора действием дифференциала исходной системы в точке. Таким образом мы следим не только за траекторией системы, но и за изменением касательного вектора в точках траектории.

В [74] впервые был предложен и обоснован способ оценки спектра Морса динамической системы с помощью спектра Морса ее оснащенного символического образа, т.е. ориентированного графа, дугам которого присвоены некоторые числовые характеристики.

Символический образ расширенной динамической системы разбивается на компоненты сильной связности, на каждой компоненте выделяются контуры с максимальным и минимальным характеристиками. Спектр Морса оснащенного символического образа состоит из объединения интервалов [19], границы которых определяются экстремальными характеристиками, полученными на компонентах сильной связности.

Отметим, что при таком подходе вычисление спектра Морса связано с поиском простых замкнутых путей и выделением среди них контуров с нужными характеристиками. К сожалению, при итерационных построениях символического образа число таких путей резко возрастает, что приводит к колоссальным затратам памяти и времени. Использование метода непосредственного перебора всех циклов не привело к результату. И. В. Романовский предложил метод нахождения контуров с экстремальными характеристиками, основанный на симплекс-методе. Этот алгоритм был реализован автором и позволил впервые получить оценку спектра Морса для динамических систем, имеющих нетривиальные цепно-рекуррентные множества, первые результаты опубликованы в [15].

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

Построение инвариантной меры для динамической системы является нетривиальной задачей [18,26,45,46]. Инвариантная мера динамической системы дает важное для приложений вероятностное описание поведения системы. Динамическая система может иметь много инвариантных мер, поэтому нужно выбирать те, которые интересны с точки зрения динамики. Аппроксимации инвариантной меры посвящено много работ, где в основном используется конечная аппроксимация оператора Перрона-Фробениуса [46], которая позволяет построить только одну специальную меру и только в случае, если известно, что такая мера существует для конкретной системы. Проверка этого свойства оказывается сложной теоретической задачей.

Поскольку символический образ является конечной аппроксимацией системы, возникает задача о построении инвариантной меры на символическом образе, что в свою очередь приводит к построению стационарного процесса (замкнутого нормированного потока) на ориентированном графе.

Обоснованием для разработки и реализации алгоритмов построения приближения к инвариантной мере является следующий результат, доказанный Г. С. Осипенко в [18].

Для любой окрестности U (в слабой топологии) множества • инвариантных мер найдется положительное число do такое, что для всякого разбиения с максимальным диаметром d < do и любой инвариантной меры т на символическом образе, построенной относительно этого разбиения, мера, построенная определенным образом по т, лежит в окрестности U.

В работе [2] диссертантом реализован алгоритм построения инвариантной меры, основанный на построении мер простых циклов. На каждом простом цикле можно построить простой поток, в котором веса ребер одинаковы. Меру на символическом образе можно построить как линейную комбинацию мер простых циклов [26]. Такой подход, хотя и является достаточно простым, приводит к понятным трудностям в реализации: число простых циклов может быть очень велико. Рассматриваются алгоритмы, которые находят не все простые циклы. Вопрос о том, насколько "потерянные" циклы важны для динамики системы, проверяется только экспериментально.

И. В. Романовский предложил использовать теоретический метод построения нормированного замкнутого потока на графе, при котором всем дугам приписывается некоторая мера, так что поток является максимально "размазанным". Впервые этот алгоритм использовал Г. В. Ше-лейховский [7] при решении специальной транспортной задачи. Начальные значения выбираются произвольно, а затем улучшаются методом балансировки строк и столбцов матрицы распределения потоков. Сходимость метода в общем случае была доказана JI. М. Брэгманом [7,8,18]. В [18] реализованный диссертантом метод JI. М. Брэгмана впервые был успешно применен к задаче построения меры на символическом образе.

В работах [23,30,35] диссертантом реализованы алгоритмы построения инвариантной меры с помощью метода балансировки, рассмотрены различные критерии остановки алгоритма, приведена их сравнительная характеристика.

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

Структура работы

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

Заключение

В работе получены следующие результаты:

1. Разработан и реализован программный комплекс компьютерного исследования динамических систем на основе метода символического образа, который впервые объединяет в себе: методы построения цепно-рекуррентных множеств дискретных и непрерывных динамических систем; метод построения оценки спектра Морса для непрерывных и дискретных динамических систем, применимый для компьютерной проверки устойчивости цепно-рекуррентного множества; метод построения приближения к инвариантной мере динамической системы. В комплексе была успешно использована динамическая генерация кода. Реализованный программный комплекс может быть расширен новыми методами и алгоритмами ис

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

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

3. Разработан алгоритм поиска контуров с минимальной и максимальной характеристикой на ориентированном графе, основанный на модификации симплекс-метода, перенесенной на ориентированный граф, что впервые позволило получить компьютерный метод оценки спектра Морса динамической системы и способ проверки устойчивости цепно-рекуррентного множества динамической системы. Доказана теорема о сходимости метода.

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

Разработанный комплекс реализован на языке С# 3.0, который входит в состав Microsoft .NET Framework 3.5. Для построения рисунков компьютерных экспериментов используется пакет GNUPL0T. Все использованные программные продукты распространяются бесплатно для академического использования. На языке написано около 92 тысяч строк кода," на языке С++ написано около 35 тысяч строк кода.

Разработанный программный комплекс компьютерного исследования динамических систем на основе метода символического образа может быть применен для исследования непрерывных и дискретных динамических систем небольшой размерности. Он используется в курсе по компьютерному исследованию динамических систем на математическом факультете СПбГУ, а также может быть использован для исследования, нетривиальных динамических систем, й в учебном процессе.

1. Ампилова Н. Б., Ершов Е. К., Осипенко Г. С. Метод ньютона для приближенного построения периодических орбит // Труды 2 Межд.Конференции "Tools for matematical modelling". — СПб: 1999. — Pp. 108-117.

2. Ампилова H. Б., Петренко Е. И. Об оценке энтропии символического образа динамической системы // Вестник СПбГУ. сер. 10, вып.З. — 2008. — С. 3-11.

3. Ампилова Н. Б., Терентъев С. В. Применение методов интервальной арифметики к задаче построения символического образа // Эл. Ж. Дифф. уравнения и процессы управления — 2006. — № 4. — С. 50-64. http://www.math.spbu.ru/diffj ournal/j.

4. Андрианов С. H., Едаменко Н. С. Моделирование динамических систем (на примере задач физики пучков).— ИД СПбГУ, 2005. — Р. 169.

5. Андриевский Б. Р., Фрадков А. Л. Управление хаосом: Методы и приложения, ii. приложения // Автоматика и телемеханика.— 2004. по. 4. - Pp. 3-34.

6. Ахо А. В., Хопкрофт Д. Э., Ульман Д. Д. Структуры данных и алгоритмы, — М.: Вильяме, 2007,— С. 400.

7. Брэгман Л. М. Доказательство сходимости метода Г. В. Шлеховского для задачи с транспортными ограничениями // Журн. вычисл. мат. и мат. физики. — 1967.- Т. 7, № 1, — С. 147-156.

8. Брэгман Л. М. Релаксационный метод нахождения общей точки выпуклых множеств и его применение для задач выпуклого программирования // Журн. вычисл. мат. и мат. физики- — 1967. — Т. 3. — С. 629-641.

9. Буслов В. А., Яковлев С. JI. Численные методы II. Решение уравнений. Курс лекций. — СПб: СПбГУ, Физ. фак. Каф. Выч. Физ., 2001. — С. 44.

10. Каток А. Б., Хассельблат Б. Введение в современную теорию динамических систем. — М.: Факториал, 1999. — С. 768.

11. Колесов Ю. Б., Сениченков Ю. Б. Моделирование систем. Динамические и гибридные системы. — БХВ-Петербург, 2006. — С. 224.

12. Колесов Ю. Б., Сениченков Ю. Б. Моделирование систем. Практикум по компьютерному моделированию. — БХВ-Петербург, 2007. — С. 352.

13. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — М.: МЦНМО: Бином. Лаборатория знаний, 2004.— С. 955.

14. Меньшиков Г. Г. Интервальный анализ и методы вычислений. — НИ-ИХ СПбГУ, 1998-2001.— Т. Вып.1. Введение в интервальную организацию вычислений.

15. О вычислении спектра Морса / Г. С. Осипенко, И. В. Романовский, Е. И. Петренко, Н. Б. Ампилова // Проблемы математического анализа. 2004. — январь. — Т. 27. — С. 151-169.

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

17. Осипенко Г. С. Оценка характеристических показателей методами символической динамики // Дифференциальные уравнения — 2002,- Т. 38, № 4.- С. 1-11.

18. Осипенко Г. С. К вопросу об аппроксимации инвариантных мер динамических систем // Эл. Ж. Дифф. уравнения и процессы управления.— 2008.— № 2,— С. 58-79. http://www.math.spbu.ru/ diffjournal/j.

19. Осипенко Г. С., Ампилова Н. Б. Введение в символический анализ динамических систем. СПб: Изд. СПбГУ, 2005. - С. 237.

20. Петренко Е. И. Разработка и реализация алгоритмов построения символического образа // Эл. Ж. Дифф. уравнения и процессы управления. — 2006.— № 3.— С. 55-96. http://www.math.spbu.ru/ diff journal/j.

21. Петренко Е. И. Применение символического образа для исследования непрерывных динамических систем // Труды III Международной научно-практической конф.: Современные информационные технологии / Под ред. В. А. Сухомлпн. — М.: МГУ, 2008. — С. 437-442.

22. Петренко Е. И. Об оценке энтропии символического образа // Процессы управления и устойчивость: Труды 40-й международной научной конференции аспирантов и студентов / Под ред. Н. В. Смирнова, Г. Ш. Тамасяна. СПб: Издат. СПбГУ, 2009. - С. 497-502.

23. Петренко Е. И. Оптимизация алгоритмов построения инвариантного множества динамической системы с помощью генерации кода // Вестник СПбГУ, сер.10, вып.3. — 2009. — Сентябрь. — С. 112-118.

24. Писапецки С. Технология разреженных матриц. — Мир, 1988. — С. 410.

25. Построение инвариантных мер / Г. С. Осипенко, А. В. Крупин, Е. И. Петренко и др. // Эл. Ж. Дифф. уравнения и процессы управления. — 2007.— № 4.— С. 27-51. http://www.math.spbu.ru/ diffjournal/j.

26. Романовский И. В. Оптимизация стационарного управления дискретным детерминированным процессом // Кибернетика. — 1967. — Т. 2. С. 66-78.

27. Романовский И. В. Алгоритмы решения экстремальных задач. — М.: Наука, 1977.- С. 352.

28. Романовский И. В. Дискретный анализ (учебное пособие для студентов ВУЗов). СПб: BHV, 2003. - С. 336.

29. Романовский И. В., Ампилова Н. В., Петренко Е. И. О максимизации энтропии при линейных ограничениях // Труды Международной научной конференции "Космос, астрономия и программирование (Лавровские чтения)". СПб: СПбГУ, 2008. - С. 181-185.

30. Смирнов А., Флегонтов А. В. Анализ эффективности параллельных вычислений для динамических систем второго порядка // Материалы IX Санкт-Петербургской Международной конференции "Региональная информатика-2004". — Санкт-Петербург: 2004. — С. 60-61.

31. Шарый С. П. Конечномерный интервальный анализ. — XYZ, 2007. — С. 700.

32. Шокин Ю. И. Интервальный анализ. — Новосибирск: Сибирское отделение изд-ва "Наука", 1981. — С. 64-68.

33. Ampiloua N., Osipov A. Local bifurcations for gardini map // VINITI. — 1996. Pp. 1969-1969.

34. Ampilova N., Petrenko E. On the application of a linear programming method to the evaluation of the entropy of a symbolic image // 6th EUROMECH Nonlinear Dynamics Conference (ENOC 2008). 2008. -Pp. 1-4. http: //lib.physcon.ru/?item=1586.

35. Ampilova N. B. Numerical investigation of invariant curves behaviour in the vicinity of a fixed point of the Gardini map // Nonlinear dynamical systems. 1997. - Vol. 1. - Pp. 5-13.

36. Ampilova N. B. Numerical methods of the construction of periodic orbits near invariant curve for Hopf bifurcation // Nonlinear dynamical systems. 2000. — Vol. 2. - Pp. 71-80.

37. Analysis, Modeling and Simulation of Multiscale Problems / M.„ Dell-nitz, M. Molo, P. Metzner et al. — Springer Berlin Heidelberg, 2006.— Pp. 619-645.

38. Bifurcation from an invariant circle for two-parameter families of maps of the plane: a computer-assisted study / D. G. Aronson, M. A. Chory, G. R. Hall, R. P. McGehee // Commun.Math.Phys.- 1982,- Vol. 83, no. 3. Pp. 303-354.

39. The С# Language.— Microsoft Developers Network. http://msdn. microsoft.com/en-us/vcsharp/aa336809.aspx.

40. Castle project.— Домашняя страница проекта, http://www. castleproject.org/container/index.html.

41. Colonius F., Klieman W. The Morse spectrum of linear flows on vector bundles // Transactions of the American Mathematical Society.— 1996.- Vol. 348, no. 11.- Pp. 4355-4388.

42. Computation of the Morse spectrum / G. S. Osipenko, J. V. Romanovsky, E. I. Petrenko, N. B. Ampilova // J. of Math. Sci — 2004.- Vol. 120, no. 2.— Pp. 1155-1166. http://www.ingentaconnect.com/content/ klu/j oth/2004/00000120/00000002/00484193.

43. Dellnitz M., Hohmann A. A subdivision algorithm for the computation of unstable manifolds and global attractors // Numerische Mathematik. —1997. Vol. 75, no. 3. - Pp. 293-317.

44. Dellnitz M., Junge O. An adaptive subdivision technique for the approximation of attractors and invariant measures // Comput. Visual. Sci. —1998.- no. 1.- Pp. 63-68.

45. Dellnitz M., Junge O. Set Oriented Methods for Dynamical Systems / Ed. by B. Fiedler. — Berlin, Germany: Freie Universitat Berlin, Institut fur Mathematik I, 2002. Feb. - Vol. 2. - P. 1098.

46. Design Patterns: Elements of Reusable Object-Oriented Software / E. Gamma, R. Helm, R. Johnson, J. M. Vlissides. Addison-Wesley Professional Computing Series. — Reading, MA: Addison-Wesley Professional, 1994. P. 416.

47. Dollard K. Code Generation in Microsoft .NET.— Apress, 2004.— P. 760.

48. Eini O. Inversion of control and dependency injection: Working with Windsor container // Microsoft Developers Network — 2006. http:// msdn.microsoft.com/en-us/library/aa973811. aspx.

49. Fowler M. Inversion of control containers and the dependency injection pattern // Martin Fowler's Blog.— 2004.— Jan. http:// martinfowler.com/articles/injection.html.

50. Froyland G., Junge O., Ochs G. Rigorous computation of topological entropy with respect to a finite partition // Physica D.— 2001.— Vol. 154, no. 1-2. Pp. 68-84.

51. Fundinger D. Investigating Dynamics by Multilevel Phase Space Discretization: Ph.D. thesis / Institut fur Parallele und Verteilte Systeme. — Abteilung Bildverstehen, 2006. http://elib.uni-stuttgart. de/opus/volltexte/2006/2614.

52. Henon M. A two-dimensional mapping with a strange attractor // Comm. Math.Phys. 1976. - Vol. 4. - Pp. 69-77.

53. Hsu C. S. Cell-to-Cell mapping. A method of global analysis for nonlinear systems // Springer-Verlag. — 1987.— P. 352.

54. IEnumerable interface (System.Collections). — Microsoft Developers Network, http://msdn.microsoft.com/en-us/library/system. collections. ienumerable. aspx.

55. Ikeda K. Multiple-valued stationary state and its instability of the transmitted light by a ring cavity system // Optics Communications. — 1979. — Vol. 30, no. 2.—Pp. 257-261. http://cdsads.u-strasbg.fr/ abs/19790ptCo.30.2571.

56. Investigation of dynamical systems using symbolic images: Efficient implementation and applications / V. Avrutin, P. Levi, M. Schanz et al. // International Journal of Bifurcation and Chaos. — 2006. — Vol. 16, no. 12. Pp. 3451-3496.

57. Jones N. D., Gomard С. K., Sestoft P. Partial Evaluation and Automatic Program Generation. Prentice-Hall International Series in Computer Science. — Prentice Hall, 1993. P. 400.

58. Liberty J., Horovitz A. Programming .NET 3.5.- 0, 2008.- P. 476.

59. Lind D., Marcus B. An introduction to symbolic dynamics and coding. — Cambridge Univ. Press, 1995. — P. 478.

60. LINQ. — Microsoft Developers Network, http: //msdn. microsoft. com/ en-us/netf ramework/aa904594. aspx.

61. Lorenz E. N. Deterministic nonperiodic flow // Journal of the Atmospheric Sciences. — 1963. Vol. 20, no. 2. — Pp. 130-141.

62. Matiyasevich D. Y., Petrenko E. I. Algorithms for the construction of isolated invariant subsets of the symbolic image // Proceedimgs of XXXVI conference "Control- Processes and Stability". — St.Petersburg: 2005. — Pp. 341-347.

63. Mischaikow K., Mrozek M. Chaos in the lorenz equations: A computer assisted proof, part ii: Details // Mathematics of Computation. — 1998. — July. Vol. 67, no. 223. - Pp. 1023-1046.66