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

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

804613454

РАЗРАБОТКА И РЕАЛИЗАЦИЯ ОСНОВАННЫХ НА ИНТЕРВАЛЬНОЙ АРИФМЕТИКЕ АЛГОРИТМОВ КОМПЬЮТЕРНОГО ИССЛЕДОВАНИЯ ДИНАМИЧЕСКИХ

СИСТЕМ

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Санкт-Петербург 2010

1 8 НОЯ 2010

004613454

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

Научный руководитель: кандидат физико-математических наук, доцент АМПИЛОВА Наталья Борисовна

Официальные оппоненты: доктор физико-математических наук,

профессор ФЛЕГОНТОВ Александр Владимирович (Российский государственный педагогический университет им. А.И. Герцена),

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

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

Защита состоится " 02 " 12 2010 года в /7 часов на заседании совета Д 212.232.51 по защите докторских и кандидатских диссертаций при Санкт-Петербургском государственном университете но адресу 198504, Санкт-Петербург, Петродворец, Университетский пр.,28, Математико-механический факультет.

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

Автореферат разослан " 3 ¡0 2010 г.

Ученый секретарь диссертационного совета

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

Общая характеристика работы

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

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

Развитие компьютерной техники привело к активному использованию компьютерного моделирования при изучении динамики систем со сложным поведением траектории. Один из основных классов компьютерных методов исследования динамических систем представляют так пазываемЕ>ге методы, основанные на множествах (set-oriented methods), которые используют конечное покрытие фазового пространства набором ячеек (клеток) и отслеживают динамику системы по попаданию точек траектории исследуемой системы в эти клетки. Для выбранной области фазового пространства К, строится последовательное подразбиение ячеек, удаляются те ячейки, образы которых заведомо не принадлежат К. При стремлении диаметра ячеек к пулю мы можем получат!, все более точный фазовым портрет. Поскольку образы ячеек могут вычисляться независимо, реализация таких методов может использовать параллельные вычисления |11|. На этих методах основано большинство алгоритмов локализации разных видов инвариантных множеств и, в частности, аттракторов динамических систем (|16, 17, 18, 19|).

Построение образов ячеек при реализации описанных методов приводит к необходимости обозначать факт пересечения образа с остальными ячейками покрытия. Весьма удачным оказался метод символического образа, предложенный в 1983 году Г.С. Осипенко |4|. Символический образ есть конечная аппроксимация динамической системы, представляющая собой ориентированный граф |3, 10|. Оп строится по заданному покрытию фазового пространства ячейками С;, вершины графа соответствуют ячейкам, дуги связям между ними, а именно: вершины i и j соединяются дугой, если образ ячейки Сj при действии динамической системы пересекается с

ячейкой СВ работах |1, 4, 5, С, 8, 22, 231 приводятся доказательства сходимости метода при решении различных задач, например, построении инвариантных, и частности, ценно-рекуррентных множеств динамических систем.

Полученная при последовательном подразбиении ячеек покрытия последовательность символических образов позволяет получить приближение к динамике системы, при этом точность построения оценивается через параметры символического образа. Применение метода символического образа к исследованию динамических систем описано и работах [1, 4, 5, 8, 15, 23, 24|.

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

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

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

Основные задачи.

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

1. Представление исходных данных. Используется целочисленная система координат, нее ячейки имеют одинаковый размер, каждая представлена пек-тором координат левого верхнего угла. Реализонаио 2 способа хранении информации о ячейке: а) сам координатный вектор, и б)помер ячейки, полученный с помощью преобразования многомерного индекса к одномерный. При первом способе храпения для оптимизации алгоритма локализации инвариантных множеств используется специальная структура храпения данных

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

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

3. Поиск ячейки в покрытии. Было разработано и реализовано 2 способа индексации ячеек покрытия: многомерный с использованием Л-деревьев и одномерный. В первом способе, при поиске ячейки, производится динамическое отсечение областей покрытия, в которых ячейки заведомо нет. В случае одномерной индексации, поиск ячейки сводится к обращению к элементу массива по адресу, однозначно определяемому по индексу ячейки.

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

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

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

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

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

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

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

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

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

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

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

• представление исходных данных;

• вычисление арифметических выражений;

• операция поиска ячейки.

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

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

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

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

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

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

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

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

• па научно технической конференции „Научное программное обечиечеиие в образовании и научных исследоваппях"(Санкт-Петербург, 2008);

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

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

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

Публикации. Основные результаты диссертации опубликованы в работах |1, 2, 3, 4, G, 8, 0|. Из них две публикации |1, 2| в журналах из перечня ВАК. Работы |1, 3, 4| написаны в соавторстве. В работах |1, 3, 4| Н.Б.Ампиловой принадлежат общие постановки задач, а С.В.Терентьеву реализация описываемых методов, создание демонстрационных примеров и программных средств. В |3| E.II. Петренко также является автором некоторых описываемых методов.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, списка литературы, включающего 70 источников, двух приложении. Текст занимает 143 страницы, содержит 32 рисунка и три таблицы.

Содержание работы

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

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

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

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

В четвертой главе приведено описание особенностей реализации созданного программного комплекса.

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

Символический образ представляет собой ориентированный граф, который стро-

ится но дискретной динамической системе жп+1 = /(.г„), / : О С Ит —> В!п, / диффеоморфизм, или по отображению сдвига для непрерывной динамической системы (л == д(х)), и разбиению множества О па конечный набор ячеек {С^. Вершинам графа соответствуют ячейки, между вершинами г и ] существует дуга г —> тогда и только тогда, когда /(СП С^ ф 0.

В реализации алгоритма граф не строится, рассматривается его множество-представление. Пусть = |а/1, ..., Л7„| начальное покрытие компакта М ячейками А/; С /Дт; г = 1,..., п. Для каждой ячейки Л/^ вычислим множества Щ = А/,-, где С{ множество индексов з тех ячеек, для которых /(Л/;) (~) /(Л/,) = 0. Построим множество-представление графа (¡1, соответствующее символическому образу С] отображения / относительно покрытия а именно бд, = Это множество содержит все ячейки покрытия, которые участвуют в построении графа На следующем шаге разбиение применяется к элементам множества <?в,, в результате повторении описанной процедуры получается множество-представление Св-2 Для графа бг-

На А'-м шаге рассматриваем разбиение вида = | А/^,... , | М^ С Ог^ , | , строится множество-представление Погрешность аппроксимации инвариантного множества может быть оценена через параметр!,I символического образа. Ниже представлено краткое описание алгоритма построения множества (Зс^

1. Пусть (?~ текущее множество-представление графа С, а множество Оок уточпее

2. Пусть (?£,, = 0.

3. Для каждой ячейки из (?£>(._,

• вычислить ее образ: 1тд\

• вычислить пересечение 1тд с /п4/„,9;

• Если Ш1тд ф 0 тогда 00к = 0Ок[^1пЬ1тд.

4. Вернуть в качестве результата множество б^,.

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

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

Доказано следующее

Утверждение.

Время работы алгоритма локализации инвариантных множеств равно 0(п*Т), где. п число ячеек в покрытии D*, Т - время поиска ячейки в ■покрытии.

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

Во второй главе описано применение интервальных методов для решении задачи о существовании е-траекторни дискретной пли непрерывной динамической системы ( с заданным или вычисленным е ), проходящей через 2 заданные точки. В случае, если такая траектория существует, можно также получить последовательность интервалов (Л), так что любая последовательность точек, выбираемых произвольно в каждом из них, является е-траекторией. Для получения такой последовательности были разработаны и реализованы два алгоритма: алгоритм построения ¿-траекторий с S = е и с <5 6 [е,£ + </], где q — максимальный из диаметров образов ячеек.

Доказано следующее Утверждение.

Время работы алгоритмов построения множества приближенных траекторий равно O(N), где N = \А\. С помощью опиаиаюго метода можно численно определить параметры, при которых приближенная траектория возмущенной системы является точной траекторией исходной.

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

В третьей главе описан способ реализации смешанных вычислений [14]. Этот термин был введен для обозначения техники оптимизации компьютерных программ. Мы используем эту технику при реализации модуля динамической генерации кода, так как при реализации алгоритмов исследования динамических систем возникает необходимость в эффективной многократной однообразной обработке параметров и функции, описывающих конкретную систему. Для решения этой задачи был разработан язык DYNAMIC SYSTEM DEFINITION LANGUAGE (

DSDL ), а также реализован компилятор для него.

Доказана следующая

Теорема.

Порождающая грамматика (G^i) языка DSDL является коитекстио-спобоЛюй LL-грамматикой.

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

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

• для Microsoft .Net платформы;

• с поддержкой POSIX стандартов.

Так как реализация для POSIX стандартов является наиболее трудоъемкой (для .Net платформы существует встроенная высокоуровневая модель компилятора и компоновщика — .Net Code Document Object Model), в этой главе подробно обсуждаются особенности организации процесса компиляции в промежуточны» код с использованием набора инструментов MinG\V\2\\{ приведены примеры использования библиотек).

Алгоритм локализации инвариантных множеств реализован па языке С++. При реализации алгоритма была использована библиотека BOOST интервальной арифметики [12|. Визуализация инвариантных множеств осуществляется с помощью технологии GNUPLOT [7|. Распределенный алгоритм локализации инвариантных множеств ДС реализован с помощью библиотеки Boosl.Threads, которая входит в состав Boost — собрание библиотек, расширяющих С I 4 . Текущая реализация этой библиотеки работает на платформах POSIX, Win32 и Macintosh Carbon. Для непрерывных систем был использован интервальный метод Рупге Кутта 4-го порядка, разработанный Ю. И. Шокипым |13|.

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

сравнение интервального метода локализации с методами работ (|15|,|8|).

Алгоритм поиска е-траекторнн реализован на языке С//. Визуализация результата реализована с помощью графического компонента для .Net платформы |9|. Пользовательский интерфейс создан с помощью технологии .Net Windows Forms |20|. Используется компилятор языка DSDL для платформы Microsoft .Net.

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

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

Работы автора по теме диссертации

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

|1| Алтшюва Н. Б., Терттьеа С. В. О Применении интервальной арифметики при численном исследовании динамических систем. // Журнал Вестник СПбГУ, серия 10, помер 4, 2009.

|2| Тере.тпьев С. В. Об оптимизации реализации алгоритма локализации инвариантных множеств динамических систем. // Журнал Вестник СПбГУ, серия 10, помер 2, 2010.

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

|3| Алтилова II. Б., Петренко Е. И., Терентию С. D. Разработка и реализация компьютерно ориентированных методов исследования динамических систем с использованием символического образа. // Труды научной международной конференции „Космос, астрономия и программирование". СПб.: СПбГУ, 2008. С. 127 134.

|4| Ампилова Н. Б. Терстпъев С. Б. Применение методов интервальной арифметики к задаче построения символического образа. // Электронный журнал „Дифференциальные уравнения и процессы управления", помер 4, 200G. http://www.neva.ru/jouraal/j/index.litinl.

[5| Теркнтьев С. В. Применение методов интервальной арифметики к задаче построения псевдотраектрий. // Труды III Международной научно практической копф.: Современные информационные технологии / Под ред. В. А. Сухомлин. М.: МГУ, 2008.-С. 362 368.

|б] Те.рентьг.в С. В. Разработка и реализация программного комплекса дли компьютерного моделирования динамических систем. // Журнал „Новые технологии" Воронеж ВГПУ, 2008, номер 3. С. 12.

|7] Терслтьав С. В. Разработка и реализация программного комплекса для компьютерного моделирования и исследования динамических систем. // Труды научно-технической конференции „Научное программное обечпеченне в образовании и научных исследованиях". СПб..'Изд. Сапкт-Петерб. Политехи. Ун-та. 2008, январь. С. 300 30G.

|8| Тере.нтьев С. В. О применении интервальной арифметики при построении псевдотраекторий // Процессы управления и устойчивость: Труды 41-й международной научной конференции аспирантов и студентов / Под ред. Н. В. Смирнова, Г. Ш. Тамасяна,- СПб: Издат. СПбГУ, 2009.4 С. 506 512.

(9] Tereiityev S. Invariant Sets of Dynamical Systems -- the Computation by Methods of Interval Arithmetic//„OVIDIUS" UNIVERSITY ANNALS CONSTANTZA. Series: CIVIL ENGINEERING. SPECIAL ISSUE DEDICATED TO THE 5 TH CONFERENCE n„DYNAMICAL SYSTEMS AND APPLICATIONS". 2009. P. 219.

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

[1| Ампилова Н. В., Петренко Е. И., Терептьев С. В. Разработка и реализация компьютерно-ориентированных методов исследования динамических систем с использованием символического образа. // Тр.уды научной международной конференции „Космос, астрономия и программирование". СПб.: СПбГУ, 2008. С. 127 134.

[2| Ахо А., Сети Р., Ульман Дж. Компиляторы: принципы, технологии, инструменты. М.: Изд. дом „Вильяме", 2003. 768 с.

|3] Ахо А. В., Хопкрофт Д. Э. и Ульман Д. Д. Структуры данных п алгоритмы. // М. Вильяме, 2007. с.400.

(4| Осипенко Г. С. О символическом образе динамической системы. //Граничные задачи. Под ред. В. А. Алексеева, Пермь. 1983. С. 101-105.

|5| Осипенко Г. С., Амнилова Н. Б. Введение н символический анализ дииамиче-ских систем. СПб.: Изд-во С.- Петербургского ун-та, 2005. 230 с.

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

|7| Графический инструмент GNUPLOT. - htlp://gnuplol.sourceforge.net/.

|8| Петренко E.II. Разработка и реализация алгоритмов построения символического образа. // Электронный журнал „Дифференциальные .уравнения и процессы управления,,, номер 3, 2006. hUp://www.iieva.ru/journal/j/index.litnil.

|9| Раба Н.О. Графические компоненты для платформы .NET. // Труды 3-й Международной научно-практической конференции „Современные информационные технологии и IT- образование", http://2008.it-edu.ru/pages/Coiiference-works.

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

|11| Смирнов А. и Флегопгов А. В. Анализ эффективности параллельных вычислений для динамических систем второго порядка. // Материалы IX Санкт-Петербургской Международной конференции „Региональная ниформатика-2004,,. Санкт-Петербург, 2004. с. 00 01.

|12| Собрание библиотек BOOST. http://www.boost.org.

|13| Шокин Ю. И. Интервальный анализ. Новосибирск: Наука, 1981. 111 с.

|14| Ershov A. Mixed calculation // Jourimkln scientific world. 14.02.1984. http://ershov.iis.iisk.su/archive/eaindex.asp?<lid 2590.

|15| D. Fundinger. Investigating Dynamics by Symbolic Analysis: Tunings for an Efficient Compulation of the Symbolic Image. // Электронный журнал „Дифференциальные уравнения п процессы управления", помер 3, 2005. http://ww\v.neva.ru/jounial/j/index.lilml.

|16| Delliiitz М. Set Oriented Methods for Dynamical Systems. // Berlin, Germany, Freie Universität Berlin, Institut für Mathematik I. 2002, Feb. vol. 2. p. 1098.

[17| Dellnilz M. and Holtmann A. A Subdivision Algorithm for the Computation of Unstable Manifolds and Global At tractors. // Numerische Mathematik, 1997. vol. 75, no. 3. p. 293 317.

|18| Delliiitz M. and Junge О. An adaptive subdivision technique for the approximation of at tractors and invariant measures / / Comput. Visual. Sei., 1998. no 1. p. 03 G8.

[19| Matiyasevich D. Yu. and Petrenko B. I. Algorithms for the construction of isolated invariant subsets of the symbolic image // Proceedings of XXXVI conference „Control Processes and Stability,,, St.Petersburg, 2005. p. 341-347.

[201 Microsoft Developers Network. — http://msdn.microsoft.com/library/.

|21| Minimalist GNU for Windows. http://www.nniig-w.org/.

|22| Osipenko G. S. and Romanovsky J. V. and Petrenko E. I. and Ampilova N. B. Computation of the Morse Spectrum. // J. of Math. Sci., 2004. vol. 120, no. 2. p. 1155 1 ICG. http://www.ingentaconnect.com/coiitent/ klu/joth/2004/00000120/00000002/00484193.

|23| Osipenko G. S. Dynamical Systems, Graphs, and Algorithms

Springer, 2007 Vol. 1889 of Lecture Notes in Mathematics, p. 288. http://www.spnnger.com/math/analysis/book/978-3-540-35593-9.

|24| Osipenko G. S. Numerical Explorations of the Ikeda mapping dynamics. // Electronic Journal of Differentional Equations and Control Processes, 2004, no. 2. p. 43-67, http://www.math.spbu.ru/diffjournal/j.

Лицензия ЛР № 020593 от 07.08.97

Подписано в печать 14.10.2010. Формат 60x84/16. Печать цифровая. Усл. печ. л. 1,0. Уч.-изд. л. 1,0. Тираж 100. Заказ 6546Ь.

Отпечатано с готового оригинал-макета, предоставленного автором, в Цифровом типографском центре Издательства Политехнического университета. 195251, Санкт-Петербург, Политехническая ул., 29. Тел.: (812) 550-40-14 Тел./факс: (812) 297-57-76

Введение

Глава 1 Локализация инвариантных множеств динамических систем

1.1 Основные определения

1.2 Основные понятия интервальной арифметики.

1.2.1 Интервальные расширения вещественных функции

1.2.2 Вычисление арифметических выражений в компьютерной арифметике.

1.2.3 Интервальный метод б-го порядка типа Рунге-Кутта

1.3 Алгоритм локализации инвариантных множеств.

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

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

1.4.2 Система О. Юнге.

1.4.3 Уравнение Дуффинга.

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

1.4.5 Отображение с задержкой.

1.4.6 Система Ван-дер-Поля.

Глава 2 Построение псевдотраекторий, проходящих через заданные точки

2.1 Постановка задачи.

2.2 Алгоритм построения 6-траекторий с 5 = е.

2.3 Алгоритм построения ¿^траекторий с 6 € [е, е + я]

2.4 Применение константы Липшица.

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

2.5.1 Нелинейная система на плоскости.

2.5.2 Отображение с задержкой.

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

2.5.4 Уравнение Дуффинга.

2.5.5 Система О. Юнге.

Глава 3 Использование метода смешанных вычислений

3.1 Постановка задачи.

3.2 Основные определения

3.3 Язык описания динамических систем( £>51)1/).

3.4 Компилятор языка БвВЬ.

Глава 4 Особенности реализации

4.1 Модули смешанных вычислений.

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

Теория динамических систем является фундаментальной математической дисциплиной, тесно связанной с большинством областей математики. Ее методы стимулировали исследования во многих других отраслях знания, что в свою очередь привело к появлению новой науки, называемой прикладной динамикой (нелинейной динамикой или теорией хаоса). Динамические системы все чаще используются во многих областях как модели реальных процессов. Они делятся на два основных класса: непрерывные и дискретные. Непрерывные динамические системы задаются автономными системами дифференциальных уравнений, а дискретные — рекуррентными соотношениями (разностными уравнениями).

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

В 1963 году Е. Лоренц [49] рассмотрел гидродинамическую модель для предсказания погоды. Рассмотренная им система дифференциальных уравнений 3 порядка ведет себя непредсказуемо (хаотично в том смысле, что малейшие ошибки в измерении состояния атмосферы быстро растут, что делает долгосрочный прогноз погоды неправильным. Однако Лоренц показал, что у хаоса есть определенная структура. Системы с хаотическим поведением траекторией были обнаружены во многих прикладных задачах.Так, в работе М.Смит [67] был приведен пример возникновения хаоса в разностных уравнениях, описывающих развитие популяции в биологии. Примеры чувствительной зависимости от начальных данных и появления хаотических режимов при определенных значениях параметров были найдены и в хорошо известных уравнениях Дуффинга. В 1971 году Д. Рюэль и Ф. Такенс в работе, посвященной турбулентным потокам в жидкости, ввели понятие странного аттрактора,т.е. такого инвариантного асимптотически устойчивого множества системы, которое обладает весьма сложной структурой и возникает при появлении хаотических режимов.

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

Развитие компьютерной техники привело к активному использованию компьютерного моделирования при изучении динамики систем со сложным поведением траекторий. Один из основных классов компьютерных методов исследования динамических систем представляют так называемые методы, основанные на множествах (set-oriented methods), которые используют конечное разбиение фазового пространства на клетки (ячейки) и отслеживают динамику системы по попаданию точек траекторий исследуемой системы в эти клетки. Для выбранной области фазового пространства К строится последовательное подразбиение ячеек, удаляются те ячейки, образы которых заведомо не принадлежат К. При стремлении диаметра ячеек к нулю мы можем получать все более точный фазовый портрет. Поскольку образы ячеек могут вычисляться независимо, реализация таких методов может использовать параллельные вычисления [20]. На этих методах основано большинство алгоритмов локализации разных видов инвариантных множеств и, в частности, аттракторов динамических систем ([38, 36, 37, 50]).

Одним из видов инвариантных множеств, довольно часто интересующим исследователей, являются периодические траектории. Решению задачи нахождения периодических орбит посвящено достаточное количество работ, причем они используют как методы обычной, так и интервальной арифметики. Так, в [43] используется интервальный метод Ньютона, который позволяет найти все периодические орбиты небольшого периода отображения Икеда в заданной области.

Построение образов ячеек при реализации описанных методов приводит к необходимости как-то обозначать факт пересечения образа с остальными ячейками покрытия. Весьма удачным оказался метод символического образа, предложенный в 1983 году Г.С. Осипенко [12]. Символический образ есть конечная аппроксимация динамической системы, представляющая собой ориентированный граф [5, 19]. Он строится по заданному покрытию фазового пространства ячейками С{, вершины графа соответствуют ячейкам, дуги — связям между ними, а именно: вершины i и э соединяются дугой, если образ ячейки Сг при действии динамической системы пересекается с ячейкой Cj. В работах [1, 12, 13, 14, 16, 60, 61] приводятся доказательства сходимости метода при решении различных задач, например, построении инвариантных, в частности, цеино-рекурреитных множеств динамических систем.

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

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

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

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

Полученная при последовательном подразбиении ячеек покрытия последовательность символических образов позволяет получить приближение к динамике системы, при этом точность построения оценивается через параметры символического образа. Применение метода символического образа к исследованию динамических систем описано в работах [1,12,13,16, 42, 61, 62].

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

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

Первыми работами в этом направлении можно считать работу Р. Янга[76] ( 1931г.,арифметика для вычислений с множествами чисел) и П. Двайера[40] (1951г., использование числовых диапазонов для учёта погрешностей в численном анализе). В 1956-58-м годах появились работы М. Вармуса [73] и Т. Сунага [69], в которых излагались идеи классической интервальной арифметики. Термины <интервал>, <интервальный> впервые были использованы в [69]. Работа Т.Сунага заслуживает внимания еще и потому, что он стал основателем алгебраического формализма интервальных вычислений, а также привел примеры применений новой техники в численном решении алгебраических уравнений и задачи Коши для обыкновенных дифференциальных уравнений.

В 1959г. появляется первая работа Р. Мура [55], а в 1966г. его монография по интервальному анализу [56], где впёрвые были последовательно изложены основы нового направления в вычислительной математике. В нашей стране история развития интервальных методов связана с именем видного русского советского математика и педагога В.М.Брадиса, который с середины 20-х годов прошлого века развивал так называемый метод границ — способ организации вычислений, приводящий к достоверным двусторонним границам точного значения вычисляемого результата, фактически аналогичный интервальной арифметике. В 1962г. в работе [8] Л. ,В. Канторович писал, что эта тематика является приоритетной для вычислительной науки, поскольку может быть использована для повышении точности и надёжности численных алгоритмов. С созданием настоящей школы исследователей по интервальным вычислениям в нашей стране связаны имена Н. Н. Яненко и его ученика Ю. И. Шокина, написавшего первую на русском языке книгу [28] по интервальному анализу. Методы численного решения задач с помощью интервальной арифметики подробно описаны в работах [11, 27, 28]. В работе [29] с целью обеспечения доказательных вычислений на ЭВМ был разработан и реализован алгоритм аппроксимации вещественных функций линейными сплайнами, на основании которого был создан пакет функционально-интервальной арифметики, позволивший решить ряд вычислительных задач.

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

Именно благодаря возможности получить строгие оценки на интервалы существования решения, метод интервального анализа в применении к исследованию поведения динамических систем со сложным поведением траекторий в последние годы стал активным инструментом исследования. Компьютерные методы решения различных задач с помощью интервальной арифметики подробно описаны в работах [28, 11, 27, 58, 74]. Следует отметить работу У. Такера [72], в которой было доказано, что для классических значений параметров в системе Лоренца [49] имеется аттрактор. У. Такер разработал алгоритм, основанный на использовании интервальной арифметики с направленным округлением, позволяющий находить точные решения большого класса обыкновенных дифференциальных уравнений. Подход Такера при исследовании системы Лоренца был основан на комбинации аналитических и компьютерных методов: строгих вычислений и теории нормальных форм. Авторы работы [54] успешно применяют методы интервальной арифметики для компьютерного доказательства существования хаоса в системе Лоренца. Статья [43] посвящена подробному исследованию отображения Икеда, оценке верхней границы инвариантного множества, локализации неблуждающего множества и периодических орбит небольшого периода. Последнее выполняется с использованием интервального оператора Кравчука.

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

Основные задачи.

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

1. Представление исходных данных. Используется целочисленная система координат, все ячейки имеют одинаковый размер, каждая представлена вектором координат левого верхнего угла. Реализовано 2 способа хранения информации о ячейке: а) сам координатный вектор, и б)номер ячейки, полученный с помощью преобразования многомерного индекса в одномерный. При первом способе хранения для оптимизации алгоритма локализации инвариантных множеств используется специальная структура хранения данных — -деревья. Во втором случае каждая ячейка представлена одним битом, означающим ее присутствие в получаемом приближении к инвариантному множеству. (В начале работы все ячейки получают признак 1.) При таком способе хранения существенно уменьшается объем используемой оперативной памяти.

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

3. Поиск ячейки в покрытии. Было разработано и реализовано 2 способа индексации ячеек покрытия: многомерный с использованием .й-деревьев и одномерный. В первом способе, при поиске ячейки, производится динамическое отсечение областей покрытия, в которых ячейки заведомо нет. В случае одномерной индексации, поиск ячейки сводится к обращению к элементу массива по адресу, однозначно определяемому по индексу ячейки.

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

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

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

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

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

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

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

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

Заключение

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

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

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

• представление исходных данных;

• вычисление арифметических выражений;

• операция поиска ячейки.

3. При решении задачи о существовании псевдотраекторий, проходящих через две заданные точки, разработаны и реализованы два метода построения £-траекторий. Доказаны теоремы об их сложности. Для эффективной работы была внедрена динамическая генерация кода. При вычислении константы Липшица для вычисления нормы интервала разработан и реализован распределенный алгоритм.

Для повышения быстродействия обработки входных параметров системы разработан язык описания динамических систем — ИвБЬ, а также реализован его компилятор. Показано, что грамматика языка описания является ЬЬ-грамматикой. Это значит, что существует класс ЬЬ-анализаторов, способных разобрать входную цепочку, порожденную с помощью Оа8в.1 • На практике большим преимуществом ЬЬ-разбора является простота реализации, так как левосторонний анализ можно представить в виде работы детерминированного конечного автомата. Компилятор языка ОвБЬ реализован с помощью набора технологии А1^ТЫ1 [31]. В качестве промежуточных языков на этапе генерации кода используются языки С + +, 3.0 [71, 57]. В процессе компиляции используются библиотеки .Net Code Document Object Model[46], .Net reflection[30], набор инструментов MinGW [53]. Данная компонента комплекса является кросс-платформенной.

Все реализации алгоритма локализации инвариантных множеств выполнены на языке С++. При реализации алгоритма была использована библиотека BOOST интервальной арифметики [21]. Текущая реализация этой библиотеки работает на платформах POSIX, Win32 и Macintosh Carbon. Визуализация осуществляется с помощью технологии GNUPLOT [7].

Алгоритм поиска е-траекторий реализован на языке С# 3.0 [71, 57], который входит в состав Microsoft .NET Framework 3.5 [48]. Визуализация результата реализована с помощью графического компонента для .Net платформы [17]. Пользовательский интерфейс создан с помощью технологии .Net Windows Forms [52, 63, 75].

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

1. Реализация локализации инвариантных множеств дискретных и непрерывных систем размерности больше трех.

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

3. Для повышения быстродействия локализации инвариантных множеств непрерывных динамических систем необходимо реализовать возможность запуска программы на CUDA( Compute Unified Device Architecture) — програмно-аппаратной архитектуре, позволяющей производить вычисления с использованием графических процессоров NVIDIA Технология CUDA даёт разработчику возможность по своему усмотрению организовывать доступ к набору инструкций графического ускорителя и управлять его памятью, организовывать на нем сложные параллельные вычисления[35].

1. Ампилова Н.Б. Терентьев C.B. Применение методов интервальной арифметики к задаче построения символического образа. // Электронный журнал „Дифференциальные уравнения и процессы управления", номер 4, 2006. http://www.neva.ru/journal/j/index.html.

2. Ампилова Н.Б. Терентьев C.B. О Применении интервальной арифметики при численном исследовании динамических систем. // Журнал Вестник СПбГУ, серия 10, номер 4, 2009.

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

4. Ахо А., Сети Р., Ульман Дж. Компиляторы: принципы, технологии, инструменты. М.: Изд. дом Вильяме, 2003. 768 с.

5. Графический инструмент С1ЧиРЬОТ. — http://gnuplot.sourceforge.net/.

6. Канторович Л.В. О некоторых новых подходах к вычислительным методам и обработке наблюдений. // Сибирский Математический Журнал. 1962. - Т. 3, N0. 5. - С. 701-709.

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

8. Мартыненко Б.К. Языки и трансляции. Учеб. пособие. СПб.: Изд.С.-Петербургского университета, 2003.

9. Меньшиков Г. Г. Интервальный анализ и методы вычислений. // СПб.: Науч.-исслед. ин-т химии С.-Петерб. ун-та, 1998-2001. Вып. 1. Введение в интервальную организацию вычислений. www.apmath.spbu.ru/ru/education/courses/elective/menshikov.html.

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

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

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

13. Петренко Е.И. Компьютерное исследование динамических систем на основе метода символического образа. Диссертация на соискание ученой степени кандидата физико-математических наук. Санкт-Петербург, 2009.

14. Петренко Е.И. Разработка и реализация алгоритмов построения символического образа. / / Электронный журнал „Дифференциальные уравнения и процессы управления,,, номер 3, 2006. http://www.neva.ru/journal/j/index.html.

15. Раба Н.О. Графические компоненты для платформы .NET. // Труды 3-й Международной научно-практической конференции „Современные информационные технологии и IT- образование", http://2008.it-edu.ru/pages/Conference-works.

16. Романенко С. А., Турчин В. Ф. Рефал-компилятор. // Труды 2-й Всесоюзной Конференции по программированию. Заседание Б. Новосибирск, 1970, 3-6 февраля. http://www.refal.org/origins/RfcVkp2/index.htm.

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

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

19. Собрание библиотек BOOST. — http://www.boost.org.

20. Терентьев C.B. Об оптимизации реализации алгоритма локализации инвариантных множеств динамических систем. // Журнал Вестник СПб-ГУ, серия 10, номер 2, 2010.

21. Терентьев С. В. Разработка и реализация программного комплекса для компьютерного моделирования динамических систем. // Журнал „Новые технологии" Воронеж ВГПУ, 2008, номер 3. С. 12.

22. Шарый С. П. Конечномерный интервальный анализ. Новосибирск: XYZ, 2009. 572 с.

23. Шокин Ю. И. Интервальный анализ. Новосибирск: Наука, 1981. 111 с.

24. Another Tool For Language Recognition. — http://www.antlr.org/.

25. Aronson D.G.,Chory M.A., Hall G.R. et.all. Bifurcation from an invariant circle for two-parameter families of maps of the plane: A computer-assisted study. Commun.Math.Phys.83,3(1982), p.303-354.

26. Beckmann N. Kriegel H.P. Schneider R. B. Seeger B. The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. // SIGMOD Conference 1990: 322-331. http://dbs.mathematik.uni-marburg.de/publications/myPapers/1990/BKSS90.pdf.

27. Технология CUDA. — http://www.ru.wikipedia.org/wiki/CUDA.

28. Dellnitz M. and Hohmann A. A Subdivision Algorithm for the Computation of Unstable Manifolds and Global Attractors. // Numerische Mathematik, 1997. vol. 75, no. 3. p. 293-317.

29. Dellnitz M. and Junge 0. An adaptive subdivision technique for the approximation of attractors and invariant measures // Comput. Visual. Sei., 1998. no 1. p. 63-68.

30. Dellnitz M. Set Oriented Methods for Dynamical Systems. // Berlin, Germany, Freie Universität Berlin, Institut für Mathematik I. 2002, Feb. vol. 2. p. 1098.

31. Dellnitz M., Junge О. Set oriented numerical methods for dynamical systems. // Handbook of dynamical systems, Ed. B. Fiedler. 2002.Vol.2. 270 p.

32. Dwyer P. Linear Computations. // New York: John Wiley & Sons, 1951.

33. Ershov A. Mixed calculation // Journal:In scientific world. 14.02.1984. http://ershov.iis. nsk.su/archive/eaindex. asp?did=2596.

34. D. Fundinger. Investigating Dynamics by Symbolic Analysis: Tunings for an Efficient Computation of the Symbolic Image. // Электронный журнал „Дифференциальные уравнения и процессы управления", номер 3, 2005. http://www.neva.ru/journal/j/index.html.

35. Galias Z. Rigorous investigation of the Ikeda map by means of interval arithmetic. // Nonlinearity 15(2002), p. 1759-1779.

36. Guttman A. R-Trees: A Dynamic Index Structure for Spatial Searching. // Proc. 1984 ACM SIGMOD International Conference on Management of Data, pp. 47-57. ISBN 0-89791-128-8. http://www.sai.msu.su/ megera/postgres/gist/papers/gutman-rtree.pdf.

37. Ikeda K. Multiple-valued stationary state and its instability of the transmitted light by a ring cavity system // Opt. Commun. 1979, Vol. 30. P.257-261.

38. Kathleen Dollard. Code Generation in Microsoft .NET. // Apress, 2004. p. 760.

39. L. Jaulin, M. Kieffer, 0. Didrit, E. Walter Applied interval analysis. Berlin: Springer, 2001.

40. Liberty J. and Horovitz A. Programming .NET 3.5. // O'Reilly, 2008. p. 476.

41. Lorenz E. N. Deterministic Nonperiodic Flow. // Journal of the Atmospheric Sciences, 1963. vol. 20, no. 2. p. 130-141.

42. Matiyasevich D. Yu. and Petrenko E. I. Algorithms for the construction of isolated invariant subsets of the symbolic image // Proceedings of XXXVI conference Control Processes and Stability, St.Petersburg, 2005. p. 341-347.

43. Mischaikow, K. (2002). Topological techniques for efficient rigorous computations in dynamics. Acta Numerica.

44. Microsoft Developers Network. — http://msdn.microsoft.com/library/.

45. Minimalist GNU for Windows. — http://www.mingw.org/.

46. Mischaikow K. and Mrozek M. Chaos in the Lorenz equations: A computer assisted proof. Part II: Details // Mathematics of Computation, 1998, July, vol. 67, no. 223. p. 1023-1046.

47. Moore R.E. Automatic error analysis in digital computation. // Technical report LMSD84821 of Lockheed Missiles and Space Division. Sunnyvale: Lockheed Corp., 1959.

48. Moore R.E. Interval analysis. // Englewood Cliffs: Prentice Hall, 1966.

49. Nagel C. and Evjen B. and Glynn J. and Skinner M. and Watson K. Professional C# 2008 // Wrox, 2008. p. 1848.

50. Neumaier A. Interval Methods for systems of equations. // Cambridge: Cambridge University Press, 1990. 245 p.

51. O. Junge (1999). Mengenorientierte Methoden zur numerischen Analyse dynamischer Systeme. Phd thesis, University of Paderbonn.

52. Osipenko G. S. and Romanovsky J. V. and Petrenko E. I. and Ampilova N. B. Computation of the Morse Spectrum. // J. of Math. Sei., 2004. vol. 120, no. 2. p. 1155-1166. http://www.ingentaconnect.com/content/ klu/joth/2004/00000120/00000002/00484193.

53. Osipenko G. S. Dynamical Systems, Graphs, and Algorithms — Springer, 2007 Vol. 1889 of Lecture Notes in Mathematics, p. 288. http://www.springer.com/math/analysis/book/978-3-540-35593-9.

54. Osipenko G. S. Numerical Explorations of the Ikeda mapping dynamics. // Electronic Journal of Differentional Equations and Control Processes, 2004, no. 2. p. 43-67, http://www.math.spbu.ru/diffjournal/j.

55. Petzold C. Programming Microsoft(R) Windows(R) Forms Pro Developer. // Microsoft Press, 2005. p. 384.

56. Pilarczyk, P. (1999). Computer assisted method for proving existence of periodic orbits. TMNA, 13(2), 365-377.

57. Ruelle D. F. and Takens F. On the Nature of Turbulence. // Communs Math. Phys., 1971. vol. 20, no. 3. p. 167-192.

58. Smith M. Stability and Complexity in Model Ecosystems 2nd ed. //J. Mathematical ideas in biology. 1971.

59. Standard Template Library. — http://msdn2.microsoft.com/en-us/library/cl91tb28(VS.80).aspx.

60. Sunaga T. Theory of an interval algebra and its application to numerical analysis. // RAAG Memoirs. 1958. - Vol. 2, Misc. II. - P. 547-564.

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

62. Tucker W. A rigorous ODE solver and Smale's 14th problem. // Found. Comput. Math. 2002. Vol.2. P. 53-117.

63. Warmus M. Calculus of approximations. // Bull. Acad. Polon. Sci. 1956. -CI. Ill, vol. IV, No. 5. - P. 253-259.

64. Wikipedia: Interval arithmetic. — http://en.wikipedia.org/wiki/ Interval arithmetic.

65. Windows Forms. — Домашняя страница документации no Windows Forms .NET. http://ru.wikipedia.org/wiki/WindowsForms.

66. Young R. Algebra of many-valued quantities. // Mathematische Annalen. -1931. Bd. 104. - S. 260-290.