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

Введение

Глава 1. Динамические системы и реконструкции по временному ряду

1.1 Введение.

1.2 Аппроксимация f и Df по точкам на аттракторе.

1.2.1 Локальная размерность

1.2.2 Восстановление уравнений движения в идеальном случае.

1.2.3 Зашумлённая реконструкция и проекционная регуляризация отображения Ф.

1.3 Методы обработки временных рядов нелинейной динамики как алгоритмы решения некорректных задач

1.4 Выводы.

Глава 2. Задача оценки ляпуновских показателей и фрактальных размерностей по временному ряду

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

2.1.1 Ляпуновские показатели и нормальный базис.

2.1.2 Подход Benettin и др. (алгоритм BGGS).

2.1.3 Оценка ляпуновских показателей по временному ряду: идеи и подходы

2.2 О возможности определить размерность dдг по временному ряду.

2.3 Матричный метод и его регуляризация.

2.4 Модификация метода оценки старшего показателя (метод фрейм-разложения)

2.5 Тестирование методов расчёта ляпуновских показателей.

2.6 Задача оценивания фрактальных размерностей странных аттракторов

2.7 Оценка масштаба фрактальности ер аттракторов динамических систем . 74 2.7.1 Алгоритм расчёта масштаба фрактальности для модельных систем

2.8 Оптимизация алгоритма расчёта корреляционного интеграла.

2.8.1 Выбор оценки корреляционного показателя (поиск участка, наиболее близкого к линейной зависимости).

2.9 Выводы.

Глава 3. Стационарный ляпуновский базис и методы аналога для расчёта ляпуновских показателей

3.1 Введение

3.2 Затухание возмущений ляпуновских векторов.

3.2.1 Оценки Я\]°\ векторы g(m;n°) и e(m;n°)

3.2.2 Бесконечно малые возмущения SV.

3.2.3 Конечные возмущения

3.2.4 Оценка возмущений для "мгновенных" ляпуновских показателей

3.3 Стационарный ляпуновский базис (СЛБ)

3.4 О непрерывности поля стационарных ляпуновских векторов.

3.4.1 Зачем нужна непрерывность. Бесконечно малые возмущения 8х.

3.4.2 Непрерывность и конечные возмущения.

3.5 Стационарный ляпуновский базис и расчёт ляпуновских показателей

3.5.1 Ляпуновские показатели как средние по мере.

3.5.2 Некоторые следствия существование СЛБ

3.5.3 Применение СЛБ для обоснования алгоритмов оценки ляпуновских показателей

4.2 Данные о продолжительности суток .120

4.3 Обработка данных численного эксперимента по конвекции в слое жидкости и исследования применимости реконструкций.133

4.3.1 Характерные масштабы и оценки длины выборки .134

4.3.2 Исследования аттрактора конвективного течения.137

4.3.3 Реконструкции при больших w .138

4.3.4 Реконструкция при малых w.143

4.3.5 Свойства реконструкций и Фурье-базис .145

4.3.6 Применимость реконструкций.146

4.3.7 Оценка К2 по зависимости ец-(w).147

4.4 Обработка экспериментальных данных в гидродинамике: сферическое течение Куэтта.150

4.5 Проблемы реконструкции для физиологических данных.164

4.5.1 Реконструкция аттрактора по ряду временных интервалов.165

4.5.2 Аппроксимация локальных уравнений движения.166

4.5.3 Корреляционный интеграл: сравнение с шумом.170

4.5.4 Обработка RR-интервалов: некоторые выводы.172

4.6 Заключение.173

Глава 5. Искажения реконструкций, выбор параметров и методов обработки 174

5.1 Линейный анализ искажений, вносимых реконструкцией.175

5.1.1 Усреднённые локальные искажения.176

5.1.2 Вариации вдоль траектории.181

5.1.3 Линейный анализ: критерии вариации скорости и кривизны.182

5.2 Выбор размерности реконструкции и упорядочение ближайших соседей . . . 184

5.3 Возможна ли коррекция линейных искажений? Нелинейные искажения . . 189 5.3.1 Нелинейные искажения и оценка временного порога соответствия для реконструкций wmax.194

5.4 Обрабатывать ли данные как детерминированные или как случайные? Корреляционный интеграл в роли критерия.202

5.4.1 Основная идея предлагаемого теста.203

5.4.2 Нормированный наклон для случайных IID данных и коррекция норм207

5.4.3 Нормированный наклон для данных от детерминированных маломо-довых динамических систем: обнаружение ложных соседей.211

5.4.4 Несколько примеров поведения tpo(e).214

5.4.5 Формулировка критерия: при каком значении <р0 данные не следует обрабатывать динамическими методами.216

5.4.6 Когда полезен предлагаемый тест.221

5.5 Выводы.222

Глава 6. Русла и джокеры: о новых методах прогноза поведения сложных систем 224

6.1 Введение. Проблема прогноза.224

6.2 Предикторы и трехслойные нейронные сети.228

6.3 Когда сложная динамика может быть предсказуема? Русла и джокеры . . . 229

6.4 Как могут возникать русла.230

6.5 Русла и прогноз временных рядов.230

6.6 Как искать русла?.232

6.7 Что находится в конце русла?.233

6.8 Модельный пример.234

6.9 Выводы и гипотезы.,.238

Заключение 240

Основные результаты диссертации . . . j.240

Краткая информация о программном комплексе.241

Литература 242 I

Введение

Актуальность темы. Проблема построения моделей по временным рядам является одной из классических. Соответствующие алгоритмы широко используются при решении задач управления, диагностики, классификации или идентификации объектов исследования, см. [171, 172] и др. В своей классической постановке она рассматривается в теории управления и математической статистике [171]-[176]. На сегодняшний день большая часть полученных результатов относится к линейным моделям. В то же время с развитием вычислительной техники постоянно расширяется интерес к построению и исследованию нелинейных моделей сложных процессов. Однако использование нелинейных моделей сталкивается с рядом трудностей, поскольку многие из апробированных подходов (принцип суперпозиции, Фурье-анализ, ^-преобразование) не могут быть эффективно использованы. Кроме того, очень остро встаёт проблема выбора адекватного класса моделей-кандидатов, среди которых может проводиться поиск оптимальных, т.е. в каком-либо смысле наиболее удачных. В последнее время наблюдается большой интерес к нейронным сетям как к достаточно универсальному классу моделей, пригодных для широкого спектра процессов, однако проблема выбора моделей-кандидатов не исчезает, а сводится к задаче выбора архитектуры и способа обучения нейронной сети.

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

Одна из основных идей синергетики [1], впоследствии получившая строгое обоснование в теории инерциальных многообразий [74], состоит в том, что асимптотическое поведение сложных систем зачастую требует для своего описания сравнительно немного переменных, которые Г.Хакен назвал "параметрами порядка". Его известный принцип подчинения мод заключается в том, что на асимптотической стадии большую часть переменных системы можно приближённо (в теории инерциальных многообразий — строго) считать алгебраическими функциями параметров порядка. Поэтому при исследовании сложных систем часто используют гипотезу о том, что её поведение может описываться динамической системой сравнительно небольшой размерности dдг ("инерциаль-ной формой"), несмотря на то, что строгие результаты и оценки размерности получены лишь для небольшого класса систем, например, для обобщенного уравнения Гинзбурга-Ландау.

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

Данная задача носит общий характер и возникает при анализе гидродинамических течений, солнечного и земного динамо, в задачах физики плазмы, физики твёрдого тела, химической технологии, физиологии и т.д. [1, 2, 11, 12], [20]—[24]. Причём знание этих параметров важно не только для моделирования, но и для организации и планирования экспериментов, с тем чтобы измерять наиболее информативные величины.

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

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

В основе большинства подходов, связанных с обработкой временных рядов лежит построение множества т.н. запаздывающих векторов z = {х{, жг-+1,. , xi+i} или, в терминах теории управления, векторов в пространстве состояний [172, 173, 174]. Новым результатом нелинейной динамики явилось установление того факта, что пространство состояний, а точнее, некоторое его подмножество, поверхность в нём, в определённом смысле эквивалентно фазовому пространству нелинейной динамической системы, породившей временной ряд (теорема Такенса и её обобщения [68, 69, 97]). Это позволило предложить новый класс методов, связанных с определением по временному ряду не только параметров статистических моделей [171], но и инвариантов динамической системы — фрактальных размерностей dp, энтропии К и ля-пуновских показателей Аг-. Фрактальная размерность может служить оценкой снизу для числа параметров порядка, остальные характеристики позволяют делать выводы о характере возникающих режимов и их предсказуемости.

Кроме того, данные инварианты динамических систем можно использовать при решении задач идентификации, в диагностических целях. Например, для некоторых физиологических систем (сердце, мозг) наличие хаоса отвечает норме, упрощение же режима или исчезновение хаотичности свидетельствует о серьёзных нарушениях в организме (внезапная сердечная смерть, эпилепсия, черепные травмы) [211]—[232].

Построение моделей авторегрессионного типа также приобрело иной характер, они стали восприниматься не просто как технический приём или модели, построенные по аналогии с линейными системами, а как аппроксимация уравнений движения изучаемого объекта в координатах специального вида. Исследования в области нелинейной динамики стимулировали интерес к задаче прогноза и построения моделей [178]-[189]. В ряде случаев удалось даже построить аналитические модели по данным эксперимента, см., например, [197, 218].

Таким образом, в начале 80-х годов фактически возникло новое направление в анализе временных рядов, связанное с использованием идей нелинейной динамики и синергетики [4]-[15]. С его помощью было получено несколько важных и интересных результатов — цикл исследований в радиофизике [8, 13], в том числе новая концепция связи с хаотической несущей (см. обзор [17]), новый подход к управлению и стабилизации хаотических систем (см. обзор [19]), новые принципы фильтрации шума [16], новые результаты в физике лазеров, химической кинетике [11]. Оно стимулировало новые исследования в гидродинамике [200, 202, 203, 207], физиологии [213]—[236]. Были разработаны некоторые базовые алгоритмы оценки инвариантов динамической системы по временному ряду, в основном, в 1982-1986гг (см. обзоры [14, 15]). В последующие годы они применялись к широкому спектру проблем, однако в большом числе случаев результаты их использования были неоднозначны.

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

Поэтому начиная с 1987г. стали появляться работы, в которых отмечались и возможные ограничения методик [135]—[138, 52]. В основном оценки касались требований на длину выборки N для анализа системы данной размерности d. Наиболее известна оценка Д.Рюэлля: d < 21giV [138]. В результате класс исследуемых моделей оказался ограничен только маломодовыми системами: реально чаще всего N < 105, откуда d < 10. Однако даже такие оценки не могли объяснить сложности в интерпретации некоторых результатов [52]. В связи с этим появились работы, где предлагались тесты, основанные на принципах нелинейной динамики, для проверки детерминированности данных, зависимости чисел ряда от предшествующих и нелинейности данных, т.е. можно ли считать, что данные порождены линейной авторегрессионной моделью или же модель должна быть нелинейна [237]—[248].

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

Дели работы.

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

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

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

Исследование возможностей применения идей нелинейной динамики для анализа сложных систем.

Научная новизна.

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

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

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

4. Предложены новые методы расчёта ляпуновских показателей и энтропии по временному ряду.

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

Практическая ценность.

1. Создан программный комплекс, реализующий наиболее быстрый алгоритм расчёта корреляционного интеграла, а также расчет ляпуновских показателей и энтропии по временному ряду. Программы использовались в ряде организаций (ИЗМИРАН, МГУ, ИВМ РАН, ИВНД РАН, Уфимском научном ^ центре РАН).

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

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

4. Предложены методики выбора параметров реконструкции на основе новых способов оценки её качества.

Апробация работы. Основные результаты диссертационной работы докладывались на Всесоюзной школе "Нелинейные колебания в радиофизике и электро-^ нике", Саратов, 1988; на международной конференции "Нелинейные явления", Москва, 1989; на Всесоюзной конференции "Нелинейные задачи математической физики и вычислительной математики", Звенигород, 1990; на международной конференции "Нелинейные задачи теории гидродинамической устойчивости", Москва, 1992; на международной конференции "Nonlinear Techniques in Physiological Time Series Analysis", Дрезден, ФРГ, 1995; на семинаре Рабочей группы по нелинейной динамике Потсдамского университета, ФРГ, рук. проф. Ю.Курте, 1995, 1996; на семинаре Группы нелинейной динамики Института комплексных исследований, Дрезден, ФРГ, рук. проф. Х.Канц, 1996; на международной конференции "Nonlinear Dynamics and Chaos", Саратов, 1996; на международной конференции "Nonlinear Dynamics of Electronic Systems", Москва, 1997; на международной школе "Хаотические колебания и образование структур", Саратов, 1998; на V Всероссийской конференции "Нейрокомпьютеры и их применение", Москва, 1999.

Структура и объём работы. Диссертация состоит из введения, шести глав, заключения и списка литературы. Объём диссертации — 255 страниц, она включает 80 рисунков и список литературы из 269 наименований.

Основные результаты диссертации

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

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

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

Краткая информация о программном комплексе

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

• Программы расчёта корреляционного интеграла по временному ряду в метриках L^c, Lie, Loo- Для обработки реконструкций реализован самый быстрый алгоритм, предложенный в диссертации.

• Программы для оценки количества сходящихся соседей.

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

• Программы, реализующие 4 алгоритма расчёта ляпуновских показателей по временному ряду. Для поиска ближайших соседей реализован один из самых быстрых алгоритм связанных списков, описанный в [111].

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

• Программу расчёта средней длины окна реконструкции для оценки масштаба нелинейных искажений и энтропии по временному ряду.

Большинство программ реализовано как отдельные модули, которые могут быть использованы как в комплексе с остальными, так и самостоятельно.

Общий объём исходных текстов составляет около 7000 строк на языке Фортран-77. При реализации программ на ЭВМ типа ЕС некоторые подпрограммы были написаны на языке ассемблера. Для ЭВМ типа IBM PC использование языка нижнего уровня практически не даёт выигрыша благодаря возможностям побитовых операций, высокому качеству компиляторов и особенностям системы команд для операций с плавающей точкой.

Предпочтительнее использовать 32-разрядные версии компиляторов, это дополнительно повышает скорость расчёта от 2-43 до 10 раз. »

Заключение Ь

1. Хакен Г. Синергетика, М.:Мир, 1980, 404с.

2. Николис Г., Пригожин И. Самоорганизация в неравновесных системах. М.:Мир, 1979, 512с.

3. Рабинович М.И., Трубецков Д.И. Введение в теорию колебаний и волн. М.:Наука,1984, 432с.

4. Шустер Г. Детерминированный хаос. Введение, М.:Мир, 1988, 240с.

5. Неймарк Ю.И., Ланда П.С. Стохастические и хаотические колебания. М.:Наука, 1987, 424с.

6. Ланда П.С. Нелинейные колебания и волны. М., Наука Физматлит, 1997, 495с.

7. Берже П., Помо И., Видаль С. Порядок в хаосе. М:Мир, 1991.

8. Анищенко B.C. Сложные колебания в простых системах, М: Наука, 1990, 312с.

9. Бабин А.В., Вишик М.И. Аттракторы эволюционных уравнений, М.:Наука, 1989, 296с.

10. Заславский Г.М., Сагдеев Р.З. Введение в нелинейную физику. От маятника до турбулентности и хаоса, М.: Наука, 1988, 368с.

11. Т.С. Ахромеева, С.П. Курдюмов, Г.Г. Малинецкий, А.А. Самарский. Нестационарные структуры и диффузионный хаос. М. Наука, 1992.

12. Лоскутов А.Ю., Михайлов А.С. Введение в синергетику. М., Наука, 1990.

13. Дмитриев А.С., Кислов В.Я. Стохастические колебания в радиофизике и электронике. М., Наука, 1989.

14. Eckmann J.P., Ruelle D. Ergodic theory of chaos and strange attractors. Rev. Mod. Phys.,1985, v.57, No3, p.617-656.

15. Abarbanel H.D.I., Brown R., Sidorowich J.J., Tsimring L.S., The analysis of observed chaotic data in physical systems. Rev. Mod. Phys., 65 (1993) 1331-1391.

16. Kostelich E.J., Schreiber T. Noise reduction in chaotic time-series data: a survey of common methods. Phys. Rev. E, 48 (1993) 1752-1763.

17. Дмитриев А.С., Панас А.И., Старков С.О. Динамический хаос как парадигма современных систем связи. Зарубежная радиоэлектроника. Успехи современной радиоэлектроники. 1997, №10, 4-26.

18. Дмитриев А.С., Старков С.О. Передача сообщений с использованием хаоса и классическая теория информации. Зарубежная радиоэлектроника. Успехи современной радиоэлектроники. 1998, №11, 4-32.

19. Лоскутов А.Ю. Хаотичность динамических систем и подавление хаоса: основные понятия. Физическая мысль России, 1997, №2-3, 6-35.

20. Васильев В.А., Романовский Ю.М., Яхно В.Г. Автоволновые процессы, М.: Наука, 1987, 240с.

21. Белолипецкий А.А., Тер-Крикоров A.M. О фундаментальных решениях нелинейного уравнения теплопроводности. Журн. Вычисл. Матем. и Матем. Физ., 24 (1984) №6, 850-863.24