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

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

Гладкие динамические системы с непрерывным временем являются основными моделями в классической механике со времен Ньютона. В 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].