Файл: Курсовая работа Научный cт преп. A. Давыденко СанктПетербург 2016 Оглавление Введение 3.pdf

ВУЗ: Не указан

Категория: Курсовая работа

Дисциплина: Не указана

Добавлен: 09.12.2023

Просмотров: 55

Скачиваний: 2

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

Правительство Российской Федерации
Федеральное государственное бюджетное образовательное учреждение высшего образования
«Санкт-Петербургский государственный университет»
Кафедра системного программирования
Анкаренко Сергей Александрович
Вычисление старшего показателя
Ляпунова по временному ряду
Курсовая работа
Научный руководитель:
cт. преп. A. Давыденко
Санкт-Петербург
2016

Оглавление
Введение
3
Реализация
4
0.1. Метод взаимной информации . . . . . . . . . . . . . . . .
4 0.2. Метод ложных ближайших соседей . . . . . . . . . . . . .
5 0.3. Алгоритм Розенштайна . . . . . . . . . . . . . . . . . . . .
6
Доступные программные средства
8
Результаты
9
0.4. Системы с уже известным показателем Ляпунова . . . .
9 0.5. Реальные данные . . . . . . . . . . . . . . . . . . . . . . .
9
Заключение
11
Список литературы
12
2

Введение
Данная работа выполнялась в контексте проекта analyzeme, целью которого является разработка инструментов для анализа данных, по- иска зависимости между ними, прогнозирования.
Для анализа и прогнозирования данных требуется знать, какова их природа, устойчивы ли они или нет. Что понимать под устойчивостью?
Пусть у нас дана динамическое система, и есть решение с заданными на- чальными условиями. Если поведение решений с условиями близкими к начальным «не сильно отличается» от поведения исходного решения,
то поведение можно считать устойчивым. «Не сильно отличается» мож- но формализовать по разному, в этой работе используется определение устойчивости по Ляпунову. Критерием устойчивости является старший показатель Ляпунова, если он положителен, то данные можно считать неустойчивыми, а порождающую систему хаотической. Такие системы не поддаются прогнозированию на большой промежуток времени.
Вопрос устойчивости может возникнуть при прогнозировании курса валюты. Например, дан график зависимости курса валюты от времени,
следует сказать, устойчива ли валюта или нет. Проблема заключается в том, что нет математической модели системы, приведена лишь выборка,
то есть наблюдения через равные промежутки времени.
Целью данной работы является реализация модуля, который по данным, полученным путем наблюдения, определяет, являются ли они устойчивыми. Для реализации поставленной цели предстоит решить следущие задачи.
• Анализ предметной области
• Реализация подходящего алгоритма
• Тестирование на данных с уже известным показателем Ляпунова
• Тестирование на реальных данных
• Внедрение в проект analyzeme
3


Реализация
Определение старшего показателя Ляпунова можно условно разде- лить на две части:
• Реконструирование аттрактора исходной системы
• Непосредственное вычисление старшего показателя Ляпунова
Восстановление аттрактора
Пусть имеется некоторая динамическая система, но мы можем на- блюдать (измерять) только одну из фазовых координат этой системы.
Запишем равноотстоящие по времени измерения этой координаты в ви- де временного ряда:
x(1), x(2), ..., x(N )
(1)
где N — количество измерений.
Псевдофазовая реконструкция — это отображение, которое точке
x(t)
временного ряда ставит в соответствие точку [x(t), x(t + τ ), ..., x(t +
(m
−1)
∗ τ)] ∈ R
m
, где t — дискретное время (t = ((m−1)
∗ τ + 1), N),
τ
— временная задержка (в дискретах времени) и m — размерность пространства вложения.
Такенс показал [6], что используя только одну координату динамиче- ской системы, можно реконструировать исходный аттрактор в простран- стве точек с задержками x(t), x(t + τ ), ..., x(t + (m−1)
∗τ) таким образом,
что он будет сохранять важнейшие топологические свойства и динами- ку оригинального аттрактора. Размерность m определяется по формуле
(m > 2[d] + 1)
, где d — фрактальная размерность аттрактора
Таким образом, задача реконструирования аттрактора заключается в нахождении оптимальных τ и размерности.
0.1. Метод взаимной информации
Пусть (a, b)
∈ R
1
— минимальный интервал, содержащий все зна- чения временного ряда (1). Разобьем данный интервал на L равных
4
частей (количество интервалов разбиения обычно выбирают по фор- муле Старка L = ([log
2
N ] + 1)
[8]. Обозначим событие «значение x(t)
принадлежит i-му интервалу» через A
i
, а событие «значение x(t + τ )
принадлежит j-му интервалу» через B
j
. Тогда функция взаимной ин- формации определяется соотношением:
I(τ ) =
L

i=1
L

j=1
[P (A
i
B
j
)
− P (A
i
)
∗ P (B
j
)]
2
(2)
где P - вероятность
Оптимальная задержка выбирается в соответствии с первым ло- кальным минимумом функции I. Если функция монотонна, то выбира- ется τ , при котором
I(τ )
I(0)
1/e [3] где e - экспонента.
0.2. Метод ложных ближайших соседей
Метод ложных ближайших соседей основан на теореме Такенса о вложении [4], из которой следует, что при соответствующем выборе τ m
оригинальный и реконструированный аттракторы должны быть топо- логически эквивалентны (гомеоморфны). Поскольку траектории ори- гинального аттрактора не имеют самопересечений, то и в реконструи- рованном аттракторе траектории также не должны пересекаться. Са- мопересечение траекторий реконструированного аттрактора означает,
что размерность m пространства вложения меньше фрактальной раз- мерности аттрактора, то есть соответствующая псевдофазовая рекон- струкция не является биекцией. Условием того, что самопересечения будут отсутствовать, является то, что все соседние точки аттрактора восстанов- ленного в R
m
, будут также являться соседними в R
(
m + 1)
Метод ложных ближайших соседей позволяет определить наименьшее значение размерности m пространства вложения, так что при переходе к размерности (m + 1) количество ложных соседей (точек аттракто- ра, близких друг к другу в R
m
и отстоящих далеко в R
(
m + 1))
будет относительно мало. Полученное таким образом значение m определяет наименьшую размерность пространства вложения, где возможна рекон-
5

струкция аттрактора без самопересечений. Алгоритм метода ложных ближайших соседей состоит из следующих шагов:
1. Пусть m = 1. Находим для каждой точки x(i) временного ряда ближайшего «соседа» x(j) в m мерном пространстве.
2. Вычисляем расстояние
||x(i)−x(j)||.
3. Находим расстояние между данными точками на следующем шаге
||x(i + 1)−x(j + 1)|| и определяем
R
i
=
||x(i + 1)−x(j + 1)||
||x(i)−x(j)||
(3)
4. Если R
i
> R
t
, R
t
— подходящий порог, то точка x(j) является лож- ным ближним соседом по отношению к точке x(i). В результате подсчитывается количество таких ложных ближних соседей P для каждой точки x(i).
5. Вычисляется
P
N
и алгоритм повторяется для m = m + 1.
6. Алгоритм продолжается до тех пор, пока частное
P
N
не станет близким к нулю.
Рекомендуемое значение R
t
= 2
.[3]
Определение старшего показателя Ляпунова
По восстановленному аттрактору возможно найти старший пока- затель Ляпунова. Приведенный ниже подход основан на эргодической теореме В. И. Оселедца[7], которая утверждает, что экспоненциальное расхождение двух случайно выбранных точек на аттракторе с единич- ной вероятностью характеризует старший показатель Ляпунова.
0.3. Алгоритм Розенштайна
Розентшейн представил свой алгоритм [5] для нахождения наиболь- шего показателя Ляпунова, этот метод хорош тем, что вычисляет по-
6
казатель Ляпунова для данных небольшого размера, что делает его полезным с практической точки зрения.
1. Для каждой точки реконструированного аттрактора найти бли- жайшего соседа d
j
(0) = min
X
j
||X
i
− X
j
||, причем накладывается дополнительное условие
|i − j| > mean period
1 2. Далее рассчитывается
y(i) =
1
t
∗ < ln d
j
(i) >
(4)
где < ... > означает среднее по всем ln d
j
(i)
d
j
(i)
- расстояние j - ой пары после i дескретных шагов
3. Методом наименьших квадратов подбирается подходящая прямая к y(i), угловой коэффициент которой будет старшим показателем
Ляпунова
1
Под mean period подразумевается величина, обратная средней частоте мощностного спектра. Это нужно для того, чтобы быть уверенным в том, что соседняя точка расположена на другой траектории.
7


Доступные программные средства
Несмотря на то, что в проекте реализована возможность выполне- ния R скриптов, для реализации был выбран язык Java, так как важна скорость.
Для вычисления некоторых параметров использовались сторонние библиотеки:
• Быстрое преобразование Фурье и метод наименьших квадратов были реализованы с помощью библиотеки Commons Math: The
Apache Commons Mathematics Library
• Построение графиков производилось с использованием сторонней библиотеки JMathPlot
• Пакет deSolve на языке R для решения систем дифференциальных уравнений
8

Результаты
0.4. Системы с уже известным показателем Ляпу-
нова
Модуль был протестирован на системах с уже известным показате- лем Ляпунова, результаты приведены ниже, в таблице.
Система
Уравнение
Параметры
t
Логистическое
x
i+1
= ax
i
(1
− x
i
)
a = 4.0 1
Лоренц
˙x = a
(y − x)
˙
y =
−x ∗ z + c ∗ x − y
˙z = x
∗ y − b ∗ z
a = 16
c = 45.92
b = 4.0 0.01
Энон
x
i+1
= 1
− ax
2
i
+ y
i
y
i+1
= bx
i
a = 1.4
b = 0.3 1
Ожидаемое λ
Вычисленное λ
0.693[2]
0.6209514964441236 1.50[1]
1.4245536381712642 0.418[1]
0.4057422734887239
0.5. Реальные данные
С сайта Центрального Банка России были взяты данные о кур- сах доллара США а), немецкой марки б) на период с 02.08.1995 по
24.12.1997, отсчеты производились через каждые 2 дня
Результаты
Из графика видно, что данные на графике а) неустойчивы, слабо прогнозируемы, чего нельзя сказать о графике б).
Результаты алгоритма приведены ниже, синей линией обозначен рельный график < ln d
j
(t) >
2
, красной приближенная прямая методом наименьших квадратов, по алгоритму ее угловой коэффициент и есть
2
Напомню, что где < ... > означает среднее d
j
(i)
- расстояние по евклидовой норме между точками j-ой пары близлежащих траекторий на аттракторе после i дискретных шагов
9
а)
б)
Рис. 1: данные о курсе валюты старший показатель Ляпунова. В случае а) он положителен, что гово- рить об устойчивости, в случае б) отрицателен, здесь можно говорит о устойчивости.
а)
б)
Рис. 2: изменение < ln d
j
>
с течением времени
10


Заключение
На языке Java реализован модуль, вычисляющий старший показа- тель Ляпунова по набору данных. Результаты достаточно точны в слу- чае систем с уже известным показателем. На реальных данных алго- ритм работает вполне удовлетворительно.
11

Список литературы
[1] A. Wolf J.B. Swift H.L. Swinney, Vastano J.A. Determining Lyapunov exponents from a time series. –– 1985. –– P. 285.
[2] Eckmann J.-P., Ruelle D. Ergodic theory of chaos and strange attractors. –– 1985. –– P. 617.
[3] Klikova B., Raidl A. Reconstruction of Phase Space of Dynamical
Systems Using Method of Time Delay.
[4] Matthew B.Kennel Reggie Brown Henry D.I.Abarbanel. Determinating embedding dimension for phase-space reconstruction using a geometrical construction.
[5] Michael T. Rosenstein’ James J. Collins, Luca Carlo J. De. A practical method for calculating largest Lyapunov exponents from small data sets.
[6] Takens F. Detecting strange attractors in turbulence. –– 1980.
[7] Zeng X. Eykholt R. Pielke R.A. Estimating the Lyapunov-Exponent spectrum from short time series of low precision. –– 1991. –– P. 3229–
3232.
[8] Головко В.А. Лекции по нейроинформатике.
12