Во многих областях науки исследователи все чаще и чаще используют математические модели для предсказания поведения объектов исследований. Провести ряд экспериментов с моделью оказывается намного проще, дешевле и даже реальнее. А полученные результаты таких исследований могут послужить для дальнейшего развития знания и, возможно, построения новых, более точных, моделей. Для создания математических моделей можно использовать различные подходы, такие как статистические модели, модели теории игр, дифференциальные уравнения, динамические системы. Модели многих реальных процессов могут быть представлены с помощью динамических систем. В таких моделях над точками фазового пространства — состояниями динамической системы — действует закон эволюции системы, при помощи которого по состоянию системы в некоторый момент времени можно определить состояние системы в следующий момент времени. Последовательность таких состояний образует траекторию динамической системы. Обычно состоя-, ния системы описываются набором вещественных чисел. Динамическая система может быть задана различными способами: дифференциальными уравнениями — в случае, если время в модели непрерывно, или разностными уравнениями, если время дискретно. В теории динамических систем в центре внимания стоит изучение асимптотического поведения, т. е. поведения системы при устремлении времени к бесконечности, особенно при наличии нетривиального возвращения. Ставится ряд вопросов об эволюции системы, например, может ли система прийти в одно из состояний, в которых она была раньшенасколько похожи процессы эволюции системы при близких начальных состояниях.
Исторически гладкие динамические системы с непрерывным временем привлекли внимание после открытия Ньютоном того факта, что движение механических объектов может быть описано обыкновенными дифференциальными уравнениями второго порядка. Ньютон решил задачу двух тел. Однако решение задачи трех тел (Солнце, Земля, Луна) оказалось намного сложнее. После многочисленных попыток ученых того времени стало ясно, что эту задачу невозможно решить аналитически, получить решение в явном виде.
В начале 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)CMjk. Данный метод приводит к конечным марковским цепям и работе с матрицами большого порядка. Оба подхода являются компьютерно-ориентированными, хотя реализация второго метода представляет определенные трудности [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 тысяч строк кода.
Разработанный программный комплекс компьютерного исследования динамических систем на основе метода символического образа может быть применен для исследования непрерывных и дискретных динамических систем небольшой размерности. Он используется в курсе по компьютерному исследованию динамических систем на математическом факультете СПбГУ, а также может быть использован для исследования, нетривиальных динамических систем, й в учебном процессе.
