Эффективные вычислительные алгоритмы решения задач асимптотической стабилизации и управления тема диссертации и автореферата по ВАК РФ 01.01.07, кандидат физико-математических наук Озерицкий, Алексей Владимирович

• Озерицкий, Алексей Владимирович
• кандидат физико-математических наук
• 2007

Оглавление диссертации кандидат физико-математических наук Озерицкий, Алексей Владимирович

Введение

Глава 1. Математические основы методов стабилизации

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

1.1.1 Окрестность стационарной точки.

1.1.2 Окрестность нестационарной точки

1.1.3 Проектирование вдоль подпространства С

1.2 Вычислительная устойчивость алгоритмов.

1.2.1 Окрестность стационарной точки.

1.2.2 Окрестность нестационарной точки

1.3 Выводы по Главе 1.

Глава 2. Практическая реализация численных алгоритмов

2.1 Стационарный случай, проектирование вдоль Р+Н.

2.1.1 Базовый алгоритм.

2.1.2 Алгоритм со склейкой.

2.1.3 Параллельная модификация алгоритма.

2.2 Нестационарный случай.

2.2.1 Метод склейки.

2.2.2 Параллельная реализация.

2.3 Проектирование вдоль подпространства С

2.4 Решение задачи стабилизации в случае неизвестного оператора линейной части.

2.5 Вычисление инвариантных подпространств оператора L

2.6 Выводы по Главе 2.

Глава 3. Расчетные задачи

3.1 Модель Лоренца.

3.2 Задача Чафе-Инфанта.

3.3 Модель баротропного вихря на сфере.

3.4 Выводы по Главе 3.

Глава 4. Результаты расчета

4.1 Сравнение скорости работы различных алгоритмов.

4.2 Стабилизация с приближенно-вычисленными операторами проектирования.

4.3 Стабилизация на мелких сетках.

4.4 Модель баротропного вихря на сфере.

4.5 Выводы по Главе 4.

Введение диссертации (часть автореферата) на тему «Эффективные вычислительные алгоритмы решения задач асимптотической стабилизации и управления»

В задаче стабилизации и управления рассматривается некоторая физическая система. Её математическая интерпретация (модель) задается с помощью понятия полудинамической системы и описывается с помощью оператора эволюции S(t, •). Рассматривается по крайней мере два варианта поведения системы, называемых в дальнейшем траекториями, одно из которых является для нас идеальным, а второе - наблюдаемым. Необходимо как-то повлиять на систему извне, чтобы наблюдаемое поведение стало "похожим" на идеальное. Критерий и степень "похожести", а также временной промежуток, на котором эта "похожесть" достигается, могут определяться по-разному и в общем случае это зависит от конкретной формулировки задачи. В данной работе за основу брался размер отрезка времени на котором траектории сближаются, а также расстояние между траекториями в начальный и конечный моменты времени. Также могут различаться способы воздействия на систему, с помощью которых достигается требуемое поведение. Так как многие задачи стабилизации и управления для уравнений математической физики сводятся к задачам, в которых изменяют только начальные данные, то в качестве способа управления системой брался метод управления по начальным данным. В работе построены и обоснованы эффективные прикладные алгоритмы решения данной задачи, которые могут применяться для сложно-заданных полудинамических систем. С помощью построенных методов исследована возможность стабилизации решений для уравнения баротропного вихря на сфере.

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

Изучение нелинейного нестационарного процесса или полудинамической системы сводится к исследованию оператора эволюции (или разрешающего оператора) S(t, •). По разрешающему оператору и начальным данным do строится траектория системы a* = S(t, ао) на требуемом отрезке времени [О, Т]. Будем считать, что траектория полностью определяется начальными условиями. При этом допущении можно влиять на динамику системы за счет изменения начального условия ао, то есть можно "заставить" траекторию двигаться в нужном направлении. Формально это означает, что траектория с некоторым начальным условием Zq € Н устраивает нас больше чем с начальным условием ао и требуется найти такой вектор I из конечномерного подпространства С С Н, что траектории с начальными условиями zq и ао + I сходятся на требуемом временном отрезке [0,Т]. Подпространство С называется подпространством допустимых смещений. Отметим, что наличие такого подпространства означает, что ао можно изменять только в некоторых пределах. Действительно, если бы пространства С не было и вектор поправки брался из Н, то задача не имела бы смысла, можно было бы сразу положить i = ао — zq. Если zq £ то I = ао — zo 6 С , поэтому будем считать, что zq не лежит в С. Однако, если zq лежит в С и норма разности ао — zq недопустимо велика, то можно добиться сходимости траекторий существенно меньшей по норме поправкой I. Действительно, неустойчивость оператора S обычно сосредоточена на некотором конечномерном подпространстве Н. Поэтому, можно проектировать разность ао — zq на подпространство Я, на котором оператор S устойчив. При этом убывание погрешности в устойчивом подпространстве будет гарантироваться разрешающим оператором S задачи. Отметим, что несмотря на то, что пространство С является конечномерным, в нем содержится бесконечное число элементов, поэтому решить данную задачу методом перебора не представляется возможным даже теоретически.

Рассмотрим, как может выбираться подпространство С в реальных задачах. Пусть ао, Zq являются функциями, заданными в некоторой области £1. Тогда можно рассмотреть некоторую подобласть К е ^ и в качестве подпространства С рассмотреть пространство финитных функций, отличных от нуля в области К. Это означает, что обеспечить требуемую динамику в системе можно, изменяя начальные условия ао в некоторой подобласти К.

Решение задачи строится на основании известных результатов /12, 13, 14, 16/ теории устойчивых многообразий, применимой в случае динамических систем гиперболического типа. Согласно обобщенной теореме Адамара-Перрона /2/, если выполнены условия частичной гиперболичности в окрестности Ozo, то существует устойчивое многообразие W~(zo,f). Это многообразие можно задать некоторой функцией /. Устойчивое многообразие характеризуется тем, что траектория каждой его точки сближается с траекторией точки zq, поэтому рассматриваемая задача сводится к приближенному проектированию на многообразие W~(zo, /). Время сближения траекторий для точек устойчивого многообразия является сколь угодно большим, поэтому критерием точности проектирования является величина Т гарантированного времени сближения траекторий.

Развитие методов стабилизации

Наиболее распространённый класс методов нахождения инвариантного многообразия использует следующую технику. Многообразие размерности к находится как последовательность топологических сфер Mi размерности к — 1 в Я. /10, 11/ При этом в качестве Mq берется сфера в неустойчивом инвариантном подпространстве (Eu(zq)) оператора L линеаризации S в стационарной точке zq. При этом Mi находится по найденной ранее Mi-1 тем или иным способом с помощью оператора S. Недостатком метода является неоднородное расстояние между Mi и Mi-1, в результате, даже если Mi найдены с высокой точностью, аппроксимация многообразия получается неточной. Отметим также вычислительную сложность данного подхода. Обычно Mj аппроксимируется с помощью N точек, поэтому сложность вычисления Mj+i будет пропорциональна N, при этом N зависит от требуемой точности аппроксимации.

В работе /10/ Дж. Гукенхеймер и А. Владимирский предложили идейно похожий метод нахождения устойчивого многообразия, лишенный этих недостатков. Метод сводит задачу проектирования на инвариантное многообразие размерности к к системе дифференциальных уравнений порядка к. При составлении дифференциальных уравнений рассматривается полудинамическая система, задаваемая системой дифференциальных уравнений у' = F{y). Используется факт, что векторное поле, задаваемое этой системой должно касаться графика функции /, задающей инвариантное многообразие. Начальный "граничный" набор точек задается с помощью дискретизации сферы в инвариантном подпространстве Eu(zq). Далее граница уточняется, и с помощью решения дифференциального уравнения порядка к к ней добавляются новые точки. Недостатком данного метода является невозможность его применимости к пространствам высокой размерности. Также остается открытым вопрос о строгом обосновании сходимости полученных алгоритмов.

Другой распространенной техникой нахождения инвариантных многообразий является метод функционально-аналитических рядов /31, 20/. Метод состоит в выписывании инвариантного многообразия аналитически в виде ряда. В качестве приближения к многообразию можно взять несколько членов ряда. Главным достоинством метода является эффективность при решении задач, требующих многочисленного проецирования на многообразие. Вычислив один раз необходимые коэффициенты можно использовать их для проецирования для любых начальных данных. Недостаток метода - быстрый рост числа вычислений с увеличением точности. Также данная техника применима к ограниченному классу полудинамических систем, задаваемых аналитически.

Отметим, что все использованные ранее методы применялись к полудинамическим системам частного вида, то есть использовались те или иные допущения о виде системы и её внутреннем устройстве. В данной работе никаких требований к полудинамической системе, кроме как удовлетворения условий гиперболичности в окрестности точки zo не требуется. Заметим также, что условие гиперболичности можно ослабить. Корнев А. А. в работе /18/ показал, что для существования устойчивого многообразия в окрестности точки Zq достаточно, существования разложения подпространства Н в этой точке в прямую сумму подпространств таких, что одно подпространство является слабо растягивающим, а другое не растягивающим.

Формулировка и теоретическое обоснование корректности задачи о проектировании на устойчивое многообразие в терминах подпространства С принадлежит А. В. Фурсикову /30, 32/. Алгоритм асимптотической стабилизации по краевым условиям на основании работ Фурсикова был впервые разработан и применен для уравнений Чафе-Инфанта Е. В. Чижон-ковым в работе /33/. Позже алгоритм был обобщен на случай уравнений Навье-Стокса в /34/. Метод, применяемый в работах /33, 34/, сводился к проецированию не на само устойчивое многообразие, а на его линейную часть, что фактически является частным случаем рассматриваемых в данной работе итерационных процессов с максимальным числом итераций равным единице.

В данной работе функция /, задающая устойчивое многообразие, строится с помощью метода сжимающих отображений /12, 13, 14, 16/. На основании инвариантных свойств W~(zo,f) выписывается итерационный процесс в пространстве функций, сходящихся к искомому многообразию. Данный метод был выбран благодаря своей универсальности, позволяющей использовать его для расчетов в случае банаховых пространств. Сходимость метода для стационарного и нестационарного случаев доказана Корневым А. А. в работах /12, 13, 14, 16/. Несмотря на универсальность метода, он имеет ряд проблем:

• количество арифметических операций на п итераций 0(2П);

• необходимо уметь выделять линейную часть L оператора 5;

• необходимо вычислять инвариантные подпространства оператора L.

Для сложных задач математической физики и моделирования климата вычислительная сложность алгоритма порядка 2П на п итераций является накладной. Линейную часть оператора L не всегда возможно найти точно (выделить аналитически). Целями данной работы являются:

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

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

• разработка и реализация параллельной версии алгоритма.

Структура и основные результаты работы

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

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

Снижение числа итераций в исходном алгоритме было достигнуто путем внесения на некоторых шагах итерационного процесса погрешности в п'е приближение к проекции на устойчивое многообразие. Метод преобразования алгоритма основан на представлении зависимости п'го приближения от п — 1,., 0 приближений в виде дерева и склейки близких узлов дерева. Отметим, что так как исходный алгоритм имел сложность 0(2"), данное дерево не вырождается в цепочку. Преобразованный алгоритм был назван "методом склейки".

Параллельная версия основана на рассмотрении некоторого множества в неустойчивом подпространстве Н. Множество делится на подобласти в каждой подобласти выбирается множество точек, которые будут проектироваться на устойчивое многообразие. Далее устойчивое многообразие строится целиком путем линейной интерполяции. Данный алгоритм может работать на слабосвязанной системе путем передачи каждой подобласти отдельному процессу. Отметим, что параллельный алгоритм никак не использует внутреннюю структуру оператора S, распараллеливается именно сам алгоритм проектирования, а не вычисление оператора S. Это важно для класса задач где реализовать параллельное вычисление оператора S не представляется возможным или это очень сложно, например, для задач с оператором S типа "черный ящик".

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

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

Четвертая глава содержит результаты расчета. Проведены расчеты для задаче Лоренца, Чафе-Инфанта, уравнения баротропного вихря на полусфере. Расчеты показали сходимость разработанных алгоритмов к тому же значению, что и базовый алгоритм проектирования. Показана эффективность метода склейки и параллельного алгоритма. С помощью параллельного алгоритма удалось провести расчеты на мелких сетках (до 512 х 384) для баротропного вихря на сфере. Исследована возможность стабилизации для модели климата, описываемой уравнением баротропного вихря на сфере с физически разумными начальными данными. Установлены области на полусфере, изменения в которых начальной функции дает наиболее эффективные результаты по стабилизации. Отметим, что для уравнения баротропного вихря на полусфере, которое является математической моделью климата, возможность асимптотической стабилизации по начальным данным исследована впервые.

Написана объектно-ориентированная библиотека с реализацией алгоритмов стабилизации. Библиотека написана таким образом, что к ней легко подключать новые модельные примеры, при этом поддерживаются максимально обобщенные модели, в которых оператор S задан в виде "черного ящика", однако пользователь библиотеки при желании может сам уточнить внутреннюю структуру задачи, задав оператор линеаризации L, сопряженный оператор линеаризации L* и базисы устойчивого подпространства L и L*. Соответствующие уточнения повышают скорость и расширяют область сходимости алгоритмов. Отметим, что недостающие данные будут вычислены приближенно, используя те или иные методы, изложенные в работе.

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

Основные результаты работы изложены в статьях /16, 17, 19, 25, 26/.

Заключение диссертации по теме «Вычислительная математика», Озерицкий, Алексей Владимирович

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

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

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

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

• Предложенные алгоритмы реализованы в виде пакета программ на языке Си/Си++. Реализована параллельная версии алгоритма.

Заключение

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

Список литературы диссертационного исследования кандидат физико-математических наук Озерицкий, Алексей Владимирович, 2007 год

1. Anderson Е., Bai Z., Bischof С., Demmel J., Dongarra J., Du Croz J,, greenbaum A., Hammaling S., McKenney A., Ostrouch S., Sorensen D., LAPACK users guide.// S1.M. Philadelphia. 1992.

2. Аносов Д. В., Геодезические потоки на замкнутых римановых многообразиях отрицательной кривизны.// Труды матем. ин-та им. В.А. Стеклова. Т. 90. 1967.

3. Бахвалов Н. С., Жидков Н. П., Кобельков Г. М., Численные методы, издание вте>рое//М.-Спб.:Физматлит Невский Диалект Лаборатория Базовых Знаний. 2001.

4. Богачев К. Ю., Практикум на ЭВМ. Методы приближения функций, 2-е изд// М.:Изд-во механико-математического факультета МГУ. 1999.

5. Годунов С. К., Современные аспекты линейной алгебры.// Новосибирск: Научная книга. 1997.

6. Годунов С. К., Лекции по современным аспектам линейной алгебры./ / Новосибирск: Научная книга. 2002.

7. Дымников В. П., Вычислительные методы в геофизической гидродинамике./ / М.: Отдел вычислительной математики АН СССР. 1984.

8. Дымников В. П., Филатов А.Н., Основы математической теории климата.// М.: ВИНИТИ. 1994.

9. Деммель Дж., Вычислительная линейная алгебра.// М.: Мир. 2001.

10. Guckenheimer J., Vladimirsky A., A fast method for approximating invariant manifolds// SIAM Journal on Applied Dynamical Systems. 2004. V. 3, N. 3. P. 232-260.

11. Johnson M. E., Jolly M. S.,Kevrekidis I. G., Two-dimensional invariant manifolds and global bifurcations: Some approximation and visualization studies// Numer. Algorithms. 14 (1997). P. 125-140.

12. Корпев А. А., Об итерационном методе построения "усов Адама-ра"// ЖВМиМФ. 2004. Т. 44, N. 8. С. 1346-1355.

13. Корнев А. А,, Об аппроксимации аттракторов полудинамических систем// Матем. сборник. 2001. Т. 192, N. 10. С. 19-32.

14. Корнев А. А., Методы ассимптотической стабилизации по начальным данным к заданной траектории// ЖВМиМФ. 2006. Т. 46, N.1. С. 37-51.

15. Корнев А. А., Классификация методов проектирования на устойчивое многообразие// Докл. РАН. 2005. Т. 400, N. 5, С. 736-738.

16. Корнев А. А., Озерицкий А. В., О приближенном проектировании на устойчивое многообразие// ЖВМиМФ, 2005. Т. 45, N. 9. С. 1580-1586.

17. Корнев А. А., Озерицкий А. В., О вычислительной устойчивости одного метода стабилизации, Вестник МГУ. 2007. N 1. С. 33-36.

18. Корнев А. А., К общей теории устойчивости полудинамических систем// Докл. РАН. 2002. Т. 387, N. 1. С. 13-15.

19. Kornev A. A., Ozeritsky А. V., On the problem of approximate projection onto the invariant manifolds of the Navier-Stokes equations//1.ternational Conference "Mathematical Hydrodynamics". Moscow. 2006. P. 47-48.

20. Калинина А. Б., Численная реализация метода функционально-аналитических рядов проецирования на устойчовое многообразие// Вычислительные методы и программирование. 2006. Т. 7, С. 61-68.

21. Ладыженская О. А., Солонников В. А., О принципе линеаризации и инвариантных многообразиях для задач магнитной гидродинамики// Зап.научн.сем.ЛОМИ. 1973. Т. 38. С. 46-93.

22. Lehoucq R. В., Sorensen D. С., Yang С., ARPACK Users' Guide: Solution of Large Scale Eigenvalue Problems with Implicitly Restarted Arnoldi Methods.// http://www.caam.rice.edu/software/ARPACK/. 1997. P. 4456.

23. Малышев A.H., Введение в вычислительную линейную алгебру// Но-восибирск:Наука, 1991.

24. Нечепуренко Ю. М., Спектральные разложения// Труды математического центра им. Н.И.Лобачевского. Том 26. Материалы Всероссийской молодежной научной школы-конференции. Издательство Казанского математического общества. Казань, июнь 2004, 44 стр.

25. Ozeritsky А. V., Efficient algorithms for stable manifolds// Russ. J. Numer. Anal. Math. Modelling. 2005. V. 20, N. 2. P. 209-224.

26. Ozeritsky A. V., Efficient Algorithms for Solutions of Asymptotic Stabilization on the Origin// International Conference "Tikhonov and Contemporary Mathematics". Moscow. 2006. P. 94-95.

27. Песин Я. M., Характеристические показатели Ляпунова и гладкаяэргодическая теория// Успехи матем. наук. 1977. Т. 32. Вып. 4(196). С. 55-112.

28. Самарский А. А., Николаев Е. С., Методы решения сеточных уравнений.// М.: Наука, 1978.

29. Самарский А. А., Теория разностных схем.// М.: Наука, 1989.

30. Фурсиков А. В., Стабилизируемость квазилинейного параболического уравнения с помощью граничного управления с обратной связью// Матем. сборник. 2001. 192, N. 4. С. 115-160.

31. Fursikov А. V., Stabilizability of Two-Dimensional Navier-Stokes equations with help of a boundary feedback control.// J. of Math. Fluid Mech. V. 3, (2001), pp. 259-301.

32. Chizhonkov E. V., Numerical aspects of one stabilization method// Russ. J. Numer. Anal. Math. Modelling. 2003. V. 18, N. 5. P. 363-376.

33. Chizhonkov E. V. Ivanchikov A. A., On numerical stabilization of solutions of Stokes and Navier-Stokes equations by the boundary conditions.// Russ. J. Numer. Anal. Math. Modelling, 2004, V. 19, N. 6, P. 477-494.

34. Шильников JI. П., Шильников А. Л., Тураев Д. В., Чуа Л. Методы качественной теории нелинейных систем. Ч. 1// М.-Ижевск: Ин-т Компьютерных иссл., 2004.