Содержание к диссертации
Введение
Глава 1. Математические основы методов стабилизации 14
1.1 Постановка задачи 14
1.1.1 Окрестность стационарной точки 14
1.1.2 Окрестность нестационарной точки 17
1.1.3 Проектирование вдоль подпространства С 24
1.2 Вычислительная устойчивость алгоритмов 28
1.2.1 Окрестность стационарной точки 29
1.2.2 Окрестность нестационарной точки 34
1.3 Выводы по Главе 1 42
Глава 2. Практическая реализация численных алгоритмов 43
2.1 Стационарный случай, проектирование вдоль Р+Н 44
2.1.1 Базовый алгоритм 44
2.1.2 Алгоритм со склейкой 46
2.1.3 Параллельная модификация алгоритма 50
2.2 Нестационарный случай 63
2.2.1 Метод склейки 64
2.2.2 Параллельная реализация 65
2.3 Проектирование вдоль подпространства С 65
2.4 Решение задачи стабилизации в случае неизвестного оператора линейной части 68
2.5 Вычисление инвариантных подпространств оператора L . 71
2.6 Выводы по Главе 2 79
Глава 3. Расчетные задачи 80
3.1 Модель Лоренца 80
3.2 Задача Чафе-Инфанта 83
3.3 Модель баротропного вихря на сфере 89
3.4 Выводы по Главе 3 96
Глава 4. Результаты расчета 97
4.1 Сравнение скорости работы различных алгоритмов 97
4.2 Стабилизация с приближенно-вычисленными операторами проектирования 102
4.3 Стабилизация на мелких сетках 105
4.4 Модель баротропного вихря на сфере 106
4.5 Выводы по Главе 4 113
Заключение 114
Приложения 115
Программная архитектура 115
Библиотеки 118
Литература 119
- Вычислительная устойчивость алгоритмов
- Параллельная модификация алгоритма
- Решение задачи стабилизации в случае неизвестного оператора линейной части
- Стабилизация с приближенно-вычисленными операторами проектирования
Введение к работе
В задаче стабилизации и управления рассматривается некоторая физическая система. Её математическая интерпретация (модель) задается с помощью понятия полудинамической системы и описывается с помощью оператора эволюции S(t, ). Рассматривается по крайней мере два варианта поведения системы, называемых в дальнейшем траекториями, одно из которых является для нас идеальным, а второе - наблюдаемым. Необходимо как-то повлиять на систему извне, чтобы наблюдаемое поведение стало "похожим" на идеальное. Критерий и степень "похожести", а также временной промежуток, на котором эта "похожесть" достигается, могут определяться по-разному и в общем случае это зависит от конкретной формулировки задачи. В данной работе за основу брался размер отрезка времени на котором траектории сближаются, а также расстояние между траекториями в начальный и конечный моменты времени. Также могут различаться способы воздействия на систему, с помощью которых достигается требуемое поведение. Так как многие задачи стабилизации и управления для уравнений математической физики сводятся к задачам, в которых изменяют только начальные данные, то в качестве способа управления системой брался метод управления по начальным данным. В работе построены и обоснованы эффективные прикладные алгоритмы решения данной задачи, которые могут применяться для сложно-заданных полудинамических систем. С помощью построенных методов исследована возможность стаби-
лизации решений для уравнения баротропного вихря на сфере.
Постановка задачи
Изучение нелинейного нестационарного процесса или полудинамической системы сводится к исследованию оператора эволюции (или разрешающего оператора) S(t, ). По разрешающему оператору и начальным данным ао строится траектория системы at = S(t, ао) на требуемом отрезке времени [О, Г]. Будем считать, что траектория полностью определяется начальными условиями. При этом допущении можно влиять на динамику системы за счет изменения начального условия ао, то есть можно "заставить" траекторию двигаться в нужном направлении. Формально это означает, что траектория с некоторым начальным условием Zq Є Н устраивает нас больше чем с начальным условием ао и требуется найти такой вектор I из конечномерного подпространства С С Н, что траектории с начальными условиями zq и ао + I сходятся на требуемом временном отрезке [0,Т]. Подпространство С называется подпространством допустимых смещений. Отметим, что наличие такого подпространства означает, что ао можно изменять только в некоторых пределах. Действительно, если бы пространства С не было и вектор поправки брался из Н, то задача не имела бы смысла, можно было бы сразу положить / = ао — zq. Если zq Є , то I = ао — zq Є С , поэтому будем считать, что zq не лежит в С Однако, если zq лежит в С и норма разности ао — zq недопустимо велика, то можно добиться сходимости траекторий существенно меньшей по норме поправкой /. Действительно, неустойчивость оператора S обычно сосредоточена на некотором конечномерном подпространстве Н. Поэтому, можно проек-
тировать разность uq — zq на подпространство Я, на котором оператор S устойчив. При этом убывание погрешности в устойчивом подпространстве будет гарантироваться разрешающим оператором S задачи. Отметим, что несмотря на то, что пространство С является конечномерным, в нем содержится бесконечное число элементов, поэтому решить данную задачу методом перебора не представляется возможным даже теоретически.
Рассмотрим, как может выбираться подпространство С в реальных задачах. Пусть %, Zq являются функциями, заданными в некоторой области О,. Тогда можно рассмотреть некоторую подобласть К Є fi и в качестве подпространства С рассмотреть пространство финитных функций, отличных от нуля в области К. Это означает, что обеспечить требуемую динамику в системе можно, изменяя начальные условия uq в некоторой подобласти К.
Решение задачи строится на основании известных результатов /12, 13, 14, 16/ теории устойчивых многообразий, применимой в случае динамических систем гиперболического типа. Согласно обобщенной теореме Адамара-Перрона /2/, если выполнены условия частичной гиперболичности в окрестности Ozo, то существует устойчивое многообразие W~(zq,J). Это многообразие можно задать некоторой функцией /. Устойчивое многообразие характеризуется тем, что траектория каждой его точки сближается с траекторией точки zq, поэтому рассматриваемая задача сводится к приближенному проектированию на многообразие W~(zo, /). Время сближения траекторий для точек устойчивого многообразия является сколь угодно большим, поэтому критерием точности проектирования является величина Т гарантированного времени сближения траекторий.
Развитие методов стабилизации
Наиболее распространённый класс методов нахождения инвариантного многообразия использует следующую технику. Многообразие размерности к находится как последовательность топологических сфер М{ размерности к — 1 в Я. /10, 11/ При этом в качестве Mq берется сфера в неустойчивом инвариантном подпространстве (Eu(zq)) оператора L линеаризации S в стационарной точке zq. При этом Мі находится по найденной ранее Мі-\ тем или иным способом с помощью оператора S. Недостатком метода является неоднородное расстояние между Мі и Mj_i, в результате, даже если М{ найдены с высокой точностью, аппроксимация многообразия получается неточной. Отметим также вычислительную сложность данного подхода. Обычно Mj аппроксимируется с помощью N точек, поэтому сложность вычисления Mj+i будет пропорциональна N, при этом N зависит от требуемой точности аппроксимации.
В работе /10/ Дж. Гукенхеймер и А. Владимирский предложили идейно похожий метод нахождения устойчивого многообразия, лишенный этих недостатков. Метод сводит задачу проектирования на инвариантное многообразие размерности к к системе дифференциальных уравнений порядка к. При составлении дифференциальных уравнений рассматривается полудинамическая система, задаваемая системой дифференциальных уравнений у' — F{y). Используется факт, что векторное поле, задаваемое этой системой должно касаться графика функции /, задающей инвариантное многообразие. Начальный "граничный" набор точек задается с помощью дискретизации сферы в инвариантном подпространстве Eu(zq). Далее
граница уточняется, и с помощью решения дифференциального уравнения порядка к к ней добавляются новые точки. Недостатком данного метода является невозможность его применимости к пространствам высокой размерности. Также остается открытым вопрос о строгом обосновании сходимости полученных алгоритмов.
Другой распространенной техникой нахождения инвариантных многообразий является метод функционально-аналитических рядов /31, 20/. Метод состоит в выписывании инвариантного многообразия аналитически в виде ряда. В качестве приближения к многообразию можно взять несколько членов ряда. Главным достоинством метода является эффективность при решении задач, требующих многочисленного проецирования на многообразие. Вычислив один раз необходимые коэффициенты можно использовать их для проецирования для любых начальных данных. Недостаток метода - быстрый рост числа вычислений с увеличением точности. Также данная техника применима к ограниченному классу полудинамических систем, задаваемых аналитически.
Отметим, что все использованные ранее методы применялись к полудинамическим системам частного вида, то есть использовались те или иные допущения о виде системы и её внутреннем устройстве. В данной работе никаких требований к полудинамической системе, кроме как удовлетворения условий гиперболичности в окрестности точки zq не требуется. Заметим также, что условие гиперболичности можно ослабить. Корнев А. А. в работе /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/.
Вычислительная устойчивость алгоритмов
При этом МІ находится по найденной ранее МІ-\ тем или иным способом с помощью оператора S. Недостатком метода является неоднородное расстояние между МІ И MJ_I, В результате, даже если М{ найдены с высокой точностью, аппроксимация многообразия получается неточной. Отметим также вычислительную сложность данного подхода. Обычно Mj аппроксимируется с помощью N точек, поэтому сложность вычисления Mj+i будет пропорциональна N, при этом N зависит от требуемой точности аппроксимации. В работе /10/ Дж. Гукенхеймер и А. Владимирский предложили идейно похожий метод нахождения устойчивого многообразия, лишенный этих недостатков. Метод сводит задачу проектирования на инвариантное многообразие размерности к к системе дифференциальных уравнений порядка к. При составлении дифференциальных уравнений рассматривается полудинамическая система, задаваемая системой дифференциальных уравнений у — F{y). Используется факт, что векторное поле, задаваемое этой системой должно касаться графика функции /, задающей инвариантное многообразие. Начальный "граничный" набор точек задается с помощью дискретизации сферы в инвариантном подпространстве EU(ZQ). Далее граница уточняется, и с помощью решения дифференциального уравнения порядка к к ней добавляются новые точки. Недостатком данного метода является невозможность его применимости к пространствам высокой размерности. Также остается открытым вопрос о строгом обосновании сходимости полученных алгоритмов.
Другой распространенной техникой нахождения инвариантных многообразий является метод функционально-аналитических рядов /31, 20/. Метод состоит в выписывании инвариантного многообразия аналитически в виде ряда. В качестве приближения к многообразию можно взять несколько членов ряда. Главным достоинством метода является эффективность при решении задач, требующих многочисленного проецирования на многообразие. Вычислив один раз необходимые коэффициенты можно использовать их для проецирования для любых начальных данных. Недостаток метода - быстрый рост числа вычислений с увеличением точности. Также данная техника применима к ограниченному классу полудинамических систем, задаваемых аналитически. Отметим, что все использованные ранее методы применялись к полудинамическим системам частного вида, то есть использовались те или иные допущения о виде системы и её внутреннем устройстве. В данной работе никаких требований к полудинамической системе, кроме как удовлетворения условий гиперболичности в окрестности точки ZQ не требуется.
Заметим также, что условие гиперболичности можно ослабить. Корнев А. А. в работе /18/ показал, что для существования устойчивого многообразия в окрестности точки ZQ достаточно, существования разложения подпространства Н в этой точке в прямую сумму подпространств таких, что одно под- пространство является слабо растягивающим, а другое не растягивающим. Формулировка и теоретическое обоснование корректности задачи о проектировании на устойчивое многообразие в терминах подпространства С принадлежит А. В. Фурсикову /30, 32/. Алгоритм асимптотической стабилизации по краевым условиям на основании работ Фурсикова был впервые разработан и применен для уравнений Чафе-Инфанта Е. В. Чижон-ковым в работе /33/. Позже алгоритм был обобщен на случай уравнений Навье-Стокса в /34/. Метод, применяемый в работах /33, 34/, сводился к проецированию не на само устойчивое многообразие, а на его линейную часть, что фактически является частным случаем рассматриваемых в данной работе итерационных процессов с максимальным числом итераций равным единице. В данной работе функция /, задающая устойчивое многообразие, строится с помощью метода сжимающих отображений /12, 13, 14, 16/. На основании инвариантных свойств W (zo,f) выписывается итерационный процесс в пространстве функций, сходящихся к искомому многообразию. Данный метод был выбран благодаря своей универсальности, позволяющей использовать его для расчетов в случае банаховых пространств. Сходимость метода для стационарного и нестационарного случаев доказана Корневым А. А. в работах /12, 13, 14, 16/. Несмотря на универсальность метода, он имеет ряд проблем
Параллельная модификация алгоритма
Отметим, что данный результат имеет не только теоретическое значение, но также позволяет гарантировать, что в случае приближенного вычисления операторов проектирования алгоритм будет сходиться. Это особенно важно когда разрешающий оператор задачи S дан в виде "черного ящика" и понять его структуру для выделения линейной части L и операторов проектирования не представляется возможным посвящена практической реализации алгоритмов. Также здесь предложены и обоснованы модификации изложенных алгоритмов с вычислительной сложностью 0(п2) на п итераций. Данные усовершенствования алгоритма проектирования позволяют его использовать для сложно-заданных полудинамических систем. Также разработана версия алгоритма, которая может применяться для вычислений на слабосвязанных вычислительных машинах. Снижение числа итераций в исходном алгоритме было достигнуто путем внесения на некоторых шагах итерационного процесса погрешности в п е приближение к проекции на устойчивое многообразие. Метод преобразования алгоритма основан на представлении зависимости п го приближения от п — 1,...,0 приближений в виде дерева и склейки близких узлов дерева. Отметим, что так как исходный алгоритм имел сложность 0(2"), данное дерево не вырождается в цепочку. Преобразованный алгоритм был назван "методом склейки". Параллельная версия основана на рассмотрении некоторого множества в неустойчивом подпространстве Н. Множество делится на подобласти в каждой подобласти выбирается множество точек, которые будут проектироваться на устойчивое многообразие. Далее устойчивое многообразие строится целиком путем линейной интерполяции. Данный алгоритм может работать на слабосвязанной системе путем передачи каждой подобласти отдельному процессу. Отметим, что параллельный алгоритм никак не использует внутреннюю структуру оператора S, распараллеливается именно сам алгоритм проектирования, а не вычисление оператора S. Это важно для класса задач где реализовать параллельное вычисление оператора S не представляется возможным или это очень сложно, например, для задач с оператором S типа "черный ящик".
Строгие условия сходимости параллельного алгоритма и метода склейки не сформулированы, так как носят неконструктивный характер, однако, если найденная функция на каждой итерации не будет выходить из требуемого класса функций, то на основании доказательств, используемых в работах /12, 13, 14, 16/ разработанные алгоритмы будут сходиться. Вполне возможно, есть случаи, при которых внесенная погрешность будет слишком большой и метод склейки или параллельный алгоритм не сойдутся, однако, во всех проводимых расчетах алгоритмы сходились. При этом результаты усовершенствованных методов совпадали с результатом исходного алгоритма. В третьей главе подробно описаны используемые модели, для которых проводился расчет. Здесь содержится информация о применяемых разностных схемах, выписана линеаризация S и сопряженная задача. Четвертая глава содержит результаты расчета. Проведены расчеты для задаче Лоренца, Чафе-Инфанта, уравнения баротропного вихря на полусфере. Расчеты показали сходимость разработанных алгоритмов к тому же значению, что и базовый алгоритм проектирования.
Показана эффективность метода склейки и параллельного алгоритма. С помощью параллельного алгоритма удалось провести расчеты на мелких сетках (до 512 х 384) для баротропного вихря на сфере. Исследована возможность стабилизации для модели климата, описываемой уравнением баротропного вихря на сфере с физически разумными начальными данными. Установлены области на полусфере, изменения в которых начальной функции да- ет наиболее эффективные результаты по стабилизации. Отметим, что для уравнения баротропного вихря на полусфере, которое является математической моделью климата, возможность асимптотической стабилизации по начальным данным исследована впервые. Написана объектно-ориентированная библиотека с реализацией алгоритмов стабилизации. Библиотека написана таким образом, что к ней легко подключать новые модельные примеры, при этом поддерживаются максимально обобщенные модели, в которых оператор S задан в виде "черного ящика", однако пользователь библиотеки при желании может сам уточнить внутреннюю структуру задачи, задав оператор линеаризации L, сопряженный оператор линеаризации L и базисы устойчивого подпространства L и L . Соответствующие уточнения повышают скорость и расширяют область сходимости алгоритмов. Отметим, что недостающие данные будут вычислены приближенно, используя те или иные методы, изложенные в работе.
Решение задачи стабилизации в случае неизвестного оператора линейной части
Таким образом в построенной окрестности итерационный процесс (1.19) сходится со скоростью геометрической прогрессии к единственному решению 1+. Отметим, что скорость сходимости итерационого процесса (1.19) определяет параметр 7 а сходимость итерационного процесса (1.21) определяют не только параметр 7 но функция в \г ) и значения fr± (см. /14/). Поэтому метод (1.21) асимптотически по г имеет более вы сокую теоретическую скорость сходимости, чем метод (1.19), и сходится в несколько большей окрестности. И хотя требует больших вычислитель ных затрат, обычно оказывается предпочтительнее при практических рас четах. Начальное приближение щ = а + IQ разумно выбрать из условия и0 Є РІ0)ПО(0). Так как функция /(1) касается подпространства , сле- довательно, /() касается Р_ Н, и данное приближение имеет погрешность 0((г())2). Полученные результаты позволяют сформулировать решение задачи (1.1), (1.2) как решение уравнения относительно неизвестных коэффициентов Cj. Отметим, что данное уравнение соответствует решению задач (//) и (//) при f = 0. Предложенные итерационные методы решения отдельных задач составляют основу соответствующего численного алгоритма для уравнения (1.22). Следствием теорем 4, 7 является следующее утверждение: Теорема 8 Пусть для і — 0,..., п — 1 выполнены условия теоремы 2, система векторов {І+ ег}1 линейно независима и {Р\_ [еЦУі образует базис в Р\. Н. Тогда найдется такое г() 0, что для произвольного OQ Є Ozo решение I задачи (1.22) существует и единственно. Если же дополнительно для каждого і = 0,..., п — 1 выполнены условия теоремы 2, тогда OQ + / является решением задачи (1.1), (1-2). Еще раз отметим, что величина г определяется свойствами операторов Z/W, R и формально не зависит от параметра п. При этом решение нелинейного уравнения (1.22) можно пытаться построить стандартными методами, например, методом Ньютона. то предложенный метод принимает следующий вид: где функция f(w) Є В7(о)(Ого) аппроксимирует функцию f(w), задающую устойчивое многообразие W (ZQ,/) = {m = ZQ + w + f{w)}.
Приближение / может быть построено, например, методами работ /12, 15/, либо как решение задачи (//). В том числе можно положить / = 0. Рассмотрим вопрос об устойчивости итерационных процессов (1.7,1.15) относительно ошибок вычисления операторов Р± и PJ. . Во-первых, отметим, что вывод соотношений (1.6,1.12) существенно опирается на инвариантность подпространств Р±Н относительно оператора L и подпространств Р±Н относительно операторов lP\ Во-вторых, условия (а),(А) гарантируют обратимость и сжимаемость оператора L (LW) только на подпространствах Р+#, Р+ Н, что также принципиально при построении доказательства. На всем пространстве Я операторы L, L могут быть плохо обусловлен либо вырождены, поэтому формально даже малые ошибки в построении Р±Н, Р± не допустимы. При численной реализации итерационных процессов (1.7,1.15) операторы проектирования Р±, PJ/ вычисляются с некоторой погрешностью (например, с машинной точностью), влияние которой на окончательный результат f(w) (/ ) может оказаться катастрофическим. Сформулируем метод проектирования на многообразие W- в случае приближенно вычисленных векторов ef, і — 0,..., г о- Пусть оператор L не вырожден и известны такие операторы проектирования Р±, что выполнены следующие условия (а): Рассмотрим класс В1 (О) всех непрерывных отображений f(w) : Р-0 — Р+0 таких, что В пространстве Щ{0) зададим норму / = max /(iu). Имеет место следующая теорема /16/. Теорема 9 Пусть выполнены условия (а), (а). Тогда найдутся такие e,j,r 0, что в окрестности О — {и : Р_и г, \\Р+и\\ г} итерационный процесс (1.23) сходится в пространстве В7 (О) со скоростью геометрической прогрессии с любого начального приближения /о Є В7 (О). Предельная функция / является решением уравнения (1.6). Для каждого w Є О выполняется
Стабилизация с приближенно-вычисленными операторами проектирования
Вершины склеиваются слева направо, как показано на рисунке стрелкой. Отметим, что обратный порядок склейки, то есть, например, замена Р 2{у2) на /n_2(yi), невозможен. Действительно, при вычислении по исходному алгоритму дерево обходится слева направо и чтобы найти уі требуется знать fn 2(yi). Аналогично можно рассмотреть и склеить вершины /п_3(у4) и /n_3(2/i), /П 3Ы и /П 3Ы (см рисунок 2.1с). Склеиваем дальше вершины аналогичным образом. Несложно видеть, что эта склейка приводит к тому, что количество арифметических операций на п итераций сократилось с 0(2п) до 0(п2). Фактически склейка означает, вносится некоторая погрешность на каждом шаге исходного алгоритма: Так как исходный метод сходится для любой f(y) Є Ву(0), то если погрешность на каждом шаге такова, что функция не покидает множество -В7(0) метод будет продолжать сходиться (см. теорему 10). Вполне возможно, что для некоторых задач погрешность, вносимая методом склейки будет слишком большой и метод не будет сходиться, однако, для всех расчетных задач (задачи Лоренца, Чафе-Инфанта на отрезке, прямоугольнике, сфере, уравнение баротропного вихря на сфере) метод сходился к тому же самому числу, что и метод без склейки.
При этом оказалось, что склейка практически не влияет на скорость сходимости алгоритма, то есть если исходный алгоритм требовал порядка N итераций для сходимости с машинной точностью, то и метод склейки требовал столько же итераций. Рассмотрим практическую реализацию алгоритма метода склейки. Пусть N - максимальное число итераций, то есть мы хотим найти fN(y) по указанному алгоритму. За п обозначим номер текущей итерации. Рассмотрим дерево на рисунке (2.1с). С каждой вершиной fk{ym) дерева сопоставим пару чисел (I, к), где к - номер итерации, I - минимальное число ребер, соединяющее элемент fk{ym) с ветвью fn{y) — fn l{y) — ... — f{y)-Так, вершине fn(y) соответствует пара (0, п), вершине /n_1(yi) - (1, п — 1), вершине /п 3(уб) - (2,п — 3) и так далее. Назовем такую пару чисел (/, к) координатами элемента jk{ym). Для программной реализации данного алгоритма удобно завести два массива. Массив / размерности N х N, где I[l][n] = true, если элемент дерева с координатами (1,п) уже посчитан и I[l][n] = false в противном случае. Массив О размерности N х N. В элементе 0[([п] хранится значение вершины дерева с координатами (/, п). Подобным образом проводился расчет для задач Лоренца и Чафе-Инфанта на отрезке в работе /25/, однако при переходе на двумерные задачи и использование мелких сеток показало, что использовать память как 0(N х N) для расчета проблематично, также можно заметить, что алгоритм может сойтись за меньшее число итераций, чем заданное первоначально N и память окажется неиспользуемой.
Для решения этих проблем было принято решение ввести ассоциативный массив О, который каждой паре (I, п) ставит в соответствие указатель на точку, при этом если точка еще не посчитана, то указатель равен нулю. Данное решение избавило от проблем со сложным индексированием массива размерности NxN/2, а также избавило от выделения памяти порядка N х N/2 сразу. Пары (/, п) в ассоциативном массиве О упорядочены лексикографически. Заметим, что это увеличивает время доступа к элементам по сравнению с временем доступа к элементам обычного массива, однако, существенную часть работы алгоритма составляют операции нахождения значений операторов S, L, Р±, поэтому время доступа к элементам О никак не сказывается на общей производительности алгоритма. Вычисления будем проводить также как и в изначальном алгоритме, с естественными отличиями. Так, перед вычислением вершины fk(ym), с помощью массива О определим, посчитана ли она (проверим, равен ли соответствующий указатель нулю). После того, как вершина fk(ym) посчитана, кладем 0[l,k] = fk(ym)- Используя указанные термины, псевдокод первоначального алгоритма легко модифицировать в псевдокод алгоритма метода склейки. Рассмотрим множество точек {ук = Ьк(уо)},к — 0,...,п. Заметим, что у к будут сходиться к ZQ, так как ук лежат в устойчивом подпространстве оператора L. Будем последовательно искать значения приближения fm{yk) к функции f(y) в точках {ук}, то есть по найденным х 1 = fm l{yk) будем строить х = fm{yk)- При этом /(ук) = 0 для всех к = О, ...,п (см. рисунок 2.2). Основная проблема в алгоритмах, представленных выше, состоит в вычислении fm 1(P-S(fm"1(y) + у)). В данном случае точки х х — їт 1{Ук) известны на предыдущем шаге алгоритма. Значение fm l{PS{x1 l-\-yk)) можно получить с помощью линейной интерполяции, рассмотрев отрезки [(х ,Ук+і)Лхк Ук)}
Похожие диссертации на Эффективные вычислительные алгоритмы решения задач асимптотической стабилизации и управления
