Методы декомпозиции области и фиктивного пространства 01. 01. 07 вычислительная математика
Скачать 191.6 Kb.
|
1 2
На правах рукописи Непомнящих Сергей ВладимировичМетоды декомпозиции области и фиктивного пространства 01.01.07 – вычислительная математика Автореферат диссертации на соискание ученой степени доктора физико-математических наук Новосибирск – 2008 Работа выполнена в Новосибирском государственном университете Официальные оппоненты: доктор физико-математических наук, профессор Агошков В.И. доктор физико-математических наук, профессор Лапин А.В. доктор физико-математических наук, доцент Чижонков Е.В. Ведущая организация: Институт вычислительного моделирования СО РАН (ИВМ СО РАН). Защита состоится 13 февраля 2009 года в 14:00 часов на заседании Диссертационного совета Д 002.045.01 в Институте вычислительной математики РАН по адресу: 119991, г. Москва, ГСП-1, ул. Губкина, 8. С диссертацией можно ознакомиться в библиотеке Института вычислительной математики РАН. Автореферат разослан “___” ___________ 2008 года. Ученый секретарь диссертационного совета доктор физико-математических наук Бочаров Г.А. Настоящая диссертация посвящена исследованию и разработке итерационных методов решения краевых задач для дифференциальных уравнений эллиптического типа второго порядка в областях сложной геометрической формы и их вариационно-разностных аналогов. Актуальность темы. Многие задачи естествознания и в частности математической физики приводят к краевым задачам эллиптического и параболического типа для дифференциальных уравнений в частных производных. Во многих случаях краевые задачи можно заменить на равносильные вариационные или проекционные задачи в соответствующих гильбертовых пространствах. Для приближенного решения краевых, вариационных или проекционных задач обычно используются разностные и вариационно-разностные методы, приводящие к системам линейных алгебраических (сеточных) уравнений. Современные задачи науки и техники, стремление создать детальную картину исследуемых явлений предъявляют все более высокие требования к точности их моделирования, следствием чего являются усложнение методов построения и повышения размера систем сеточных уравнений. Для решения систем сеточных уравнений высокого порядка обычные прямые методы, типа метода Гаусса, неприменимы даже для самых мощных ЭВМ. С другой стороны, стремительный прогресс в области вычислительной техники, создание мощных многопроцессорных вычислительных комплексов вызывает необходимость в разработке новых параллельных вычислительных алгоритмов, которые могли бы быть эффективно реализованы на этих многопроцессорных комплексах. Для эффективного решения систем разностных и вариационно-разностных уравнений целесообразно строить итерационные процессы, учитывающие специфику дискретных задач и использующие на каждом своем шаге быстрые прямые алгоритмы для решения вспомогательных задач, либо оптимальные многоуровневые переобуславливающие операторы на иерархических сетках. Изложенные обстоятельства позволяют сделать вывод об актуальности проблемы построения и исследования итерационных методов параллельного типа решения краевых задач и их дискретных аналогов. Цель работы состоит в разработке эффективных итерационных процессов решения систем сеточных уравнений, аппроксимирующих эллиптические краевые задачи, которые основаны на декомпозиции (разбиение) исходной задачи на конечное число подзадач и на упрощении этих подзадач с помощью введения вспомогательного (фиктивного) пространства. Научная новизна и практическая ценность. Наиболее эффективные методы решения краевых задач в областях сложной геометрической формы, как правило, связаны с методами упрощения геометрии области. Для решения этой задачи строятся два класса итерационных процессов. В основе первого класса лежит идея метода альтернирования Шварца по подобластям (методы декомпозиции области). Второй является аналогом метода фиктивных областей. В диссертационной работе предложено развитие идей этих подходов: аддитивный метод Шварца и метод фиктивного пространства.
Апробация работы. Основные результаты диссертации докладывались на ряде российских и международных конференций, в том числе и в качестве пленарных и приглашенных докладов: 1. International Conference on Parallel Algorithms (Обервольфах, Германия, 1992). 2. 6-th International Conference on Domain Decomposition Methods (Комо, Италия, 1992). 3. 7-th International Conference on Domain Decomposition Methods (Пенсильвания, США, 1993). 4. International GAMM-Workshop on Multilevel Methods (Мейсдорф, Германия, 1994). 5. 8-th International Conference on Domain Decomposition Methods (Пекин, Китай, 1995). 6. International GAMM-Workshop on Multilevel Methods (Стробль, Австрия, 1996). 7. 9th International Conference on Domain Decomposition Methods (Улленсванг, Норвегия, 1996). 8. European Conference on Numerical Mathematics and Advanced Applications (Париж, Франция, 1996). 9. Second European Conference on Numerical Mathematics and Advanced Applications (Хайдельберг, Германия, 1997). 10. 1-st Workshop on ``Large-Scale Scientific Computations'' (Варна, Болгария, 1997). 11. Domain Decomposition and Multifield Theories (Обервольфах, Германия, 1998). 12. 11-th International Conference on Domain Decomposition Methods (Лондон, Великобритания, 1998). 13. 3-rd European Conference on Numerical Mathematics and Advanced Applications (Юваскюла, Финляндия, 1999). 14. Special Radon Semester 2005 on Computational Mechanics (Линц, Австрия, 2005). 15. International Workshop on Direct and Inverse Field Computations in Mechanics (Линц, Австрия, 2005). Публикации. Всего по теме диссертации автором опубликовано около 70 научных работ, из них 24 работы [1-24] в рецензируемых изданиях. Структура диссертации. Диссертация состоит из введения, четырёх глав, заключения, списка литературы и списка основных публикаций автора. Общий объём диссертации 262 страницы. Содержание работы. Во введении дается краткий обзор литературы, посвященной методам решения краевых задач, связанных с геометрией рассматриваемой области, сеточным теоремам о следах в пространствах Соболева и приводится краткое содержание диссертации. Первая глава диссертации посвящена сеточным аналогам теоремы о следах в пространствах Соболева, как для классических нормировок в пространстве Соболева  , где  – заданная область и, соответственно, в пространстве следов  , где  – граница области  так и в пространствах Соболева, когда соответствующие нормировки функций зависят от различных параметров (дополнительные весовые коэффициенты в определении норм, параметры, характеризующие геометрию области и сеточные аппроксимации этих областей, весовые сингулярные функции). Данные результаты имеют как самостоятельное значение (например, при исследовании устойчивости по условиям Дирихле), так и являются важным аппаратом при конструировании и исследовании методов декомпозиции области и метода фиктивного пространства. В пункте 1.1 приводятся постановки эллиптических краевых задач, описывается их дискретизация и формулируется задача о построении переобуславливающих операторов для возникающих систем сеточных уравнений. Пункт 1.2 посвящен сеточным теоремам о следах в пространстве Соболева . Рассматривается как случай полной нормы в пространстве , так и случай полунормы. Диаметр области может зависеть от малого параметра  , а триангуляции  , аппроксимирующие область , могут иметь точки сгущения. Доказывается сеточный аналог теоремы о следах с константами, не зависящими от параметра и триангуляций .В пункте 1.3 рассматриваются пространства Соболева  с параметрами. Здесь  Такие пространства рассматривались М.С.Агроновичем и М.И.Вишиком и возникают, например, при использовании неявных разностных схем для решения параболических краевых задач. Определяются сеточные нормы в возникающих пространствах следов  и доказываются сеточные теоремы о следах с константами, которые не зависят как от параметров  и  , так и от триангуляции области .Наиболее технически сложным в главе 1 является пункт 1.4, в котором рассматриваются нормировки с анизотропными коэффициентами в областях с анизотропной геометрией и с анизотропными триангуляциями. Так как простой заменой переменных случай анизотропных коэффициентов в нормах сводится к случаю изотропных норм, то достаточно рассмотреть случай областей с анизотропной геометрией и анизотропными сетками (при замене переменных меняется как геометрия, так и характеристики триангуляций). Данный пункт состоит из четырёх частей. В первой части пункта (подпункт 1.4.1) рассматривается случай функций во всём пространстве Соболева , то есть без конечно-элементных аппроксимаций, в областях с анизотропной геометрией (узкие полосы). Вводится нормировка следов функций, характеризующих область, и доказывается теорема о следах с константами, которые не зависят от геометрии области. Во втором подпункте 1.4.2 рассматривается случай областей с изотропной геометрией, но анизотропной триангуляцией. Определяются сеточные нормы в пространствах следов конечно-элементных функций, и доказывается теорема о следах с оптимальными по порядку константами, то есть не зависящими от характеристик анизотропной сетки. В подпункте 1.4.3 доказывается аналогичная теорема для случая, когда диаметр области зависит от малого параметра . В этом случае константы в теореме о следах не зависят от этого параметра и анизотропии триангуляции (при соответствующем определении норм в пространствах следов конечно-элементных функций). Наконец, в последнем подпункте 1.4.4 полученные в 1.4.1-1.4.3 результаты объединяются, определяется соответствующая сеточная норма в пространстве следов и доказывается сеточная теорема о следах для случая анизотропных областей с анизотропной триангуляцией. Константы в сеточной теореме о следах не зависят ни от геометрии области, ни от триангуляций.В последнем пункте 1.5 первой главы рассматриваются весовые пространства Соболева  , в определении которых участвуют сингулярные весовые функции, характеризующиеся параметром  . Соответствующие нормы в пространстве следов были введены С.М.Никольским При исследовании следов сеточных функций в весовых пространствах , важную роль играют сеточные аналоги норм в пространствах и пространствах следов  .Пусть       Для введённых сеточных норм доказан сеточный аналог теоремы о следах в этих пространствах с константами, не зависящими от параметра и от триангуляции области . Во второй главе диссертации предлагаются и исследуются эффективные переобуславливающие операторы, которые основаны на методе декомпозиции. Методы декомпозиции рассматривается как применения аддитивного метода Шварца в гильбертовых пространствах со специальным выбором подпространств в этих пространствах. Выбор этих подпространств связан с декомпозицией исходной области на подобласти. Использование абстрактной формулировки аддитивного метода Шварца в произвольных гильбертовых пространствах позволяет предлагать широкий класс эффективных параллельных переобуславливающих операторов. В первом пункте 2.1 второй главы в качестве введения в методы декомпозиции областей рассматривается простейший случай метода – так называемая, декомпозиция на полосы (без точек ветвления на объединении границ подобластей). Используя результаты главы 1, предлагаются оптимальные переобуславливающие операторы, как по скорости сходимости соответствующих итерационных процессов, так и по арифметической сложности реализации предложенных переобуславливающих операторов. В пункте 2.2 приводится формулировка аддитивного метода Шварца в произвольных гильбертовых пространствах (предложенная совместно с А.М.Мацокиным), которая основана на декомпозиции этого пространства в векторную сумму подпространств. Далее формулируются и доказываются дополнительные утверждения, которые могут быть полезны для решения конкретных задач с использованием абстрактной схемы аддитивного метода Шварца. В частности, предлагается способ определения подпространств с использованием оператора продолжения из более “бедного” пространства в более “богатое” исходное гильбертово пространство. Теорема. Пусть  и  . Предположим, что существуют положительные константы  : а)  для  ;б)  ;в)  ,  :  .Тогда  ,где  .Теорема. Пусть  и  – евклидовы вещественные пространства, а  и  – симметричные положительно-определенные матрицы порядка m и n соответственно. Обозначим и пусть  – линейный оператор, действующий из в такой, что  . Здесь , – положительные константы. Положим где  – оператор, сопряженный к относительно евклидовых скалярных произведений в и . Тогда   ,  – образ оператора ,  – псевдо-обратный для  .Использование предложенного формализма демонстрируется на простых примерах декомпозиции области на пересекающиеся подобласти. Пункт 2.3 посвящен методу декомпозиции области на непересекающиеся подобласти.   Положим  На основе аддитивного метода Шварца строится переобуславливающий оператор, являющийся суммой двух переобуславливателей, который соответствует разбиению (декомпозиции) исходного конечно-элементного пространства в векторную сумму двух подпространств  .Первое подпространство соответствует функциям, обращающимся в ноль на границе подобластей и являющимся прямой суммой локальных подпространств, состоящих из функций, обращающихся в ноль вне подобласти.   Первое слагаемое в переобуславливателе состоит из локальных переобуславливателей для внутренности подобластей.   .Построение локальных переобуславливателей рассматривается в третьей главе. Второе подпространство является образом оператора продолжения сеточных функций с границ подобластей в их внутренность. Второе слагаемое в переобуславливателе состоит из явного оператора продолжения сеточных функций с сохранением нормы и оператора, определяющего норму на объединении границ подобластей  , , , , .Переобуславливающий оператор определяется как  .Приводятся оценки эквивалентности предложенного переобуславливающего оператора и оператора исходной задачи в зависимости от свойств локальных переобуславливателей, нормы оператора продолжения сеточных функций с границ подобластей в их внутренность, а также от констант эквивалентности оператора, определяющего норму на объединении границ подобластей и нормы в пространстве  , которая порождается оператором исходной задачи.В пункте 2.4 рассматривается построение явного оператора продолжения сеточных функций с границ области в её внутренность с сохранением нормы в классе конечно-элементных функций. В подпункте 2.4.1 предлагаются явные операторы продолжения интегрального типа, а в подпункте 2.4.2 явные операторы продолжения на иерархических сетках. В обоих случаях нормы предложенных операторов продолжения оцениваются константой, не зависящей от шага сетки, а арифметическая сложность реализации операторов продолжения пропорциональна числу степеней свободы области. Операторы продолжения интегрального типа могут применяться на произвольных неструктурированных сетка, однако их реализация логически сложнее, чем реализация на иерархических сетках. Построению легко обратимого оператора, порождающего норму на объединении границ подобластей, которая эквивалентна норме в пространстве следов с константами, не зависящими от шага сетки, посвящен пункт 2.5. Данное построение основано на аддитивном методе Шварца. Для этого пространство сеточных функций на объединении границ подобластей (внутренних границах) разбивается на пересекающиеся подпространства, часть из которых соответствует окрестностям точек ветвления (точки, где пересекаются границы более двух подобластей), а остальные – криволинейным интервалам, соединяющим точки ветвления.В пункте 2.6 рассматривается метод декомпозиции области на большое число непересекающихся подобластей. Предлагаемый переобуславливатель основан на аддитивном методе Шварца и имеет похожую структуру, что и переобуславливатель из пункта 2.3. Отличительной особенностью является введение дополнительного каркасного пространства на объединении границ подобластей. Константы спектральной эквивалентности предложенного переобуславливающего оператора и оператора исходной задачи не зависят ни от числа подобластей, ни от шага сетки, а арифметическая сложность реализации переобуславливателя пропорциональна числу степеней свободы исходной задачи. Наконец, в пункте 2.7 второй главы рассматривается метод декомпозиции области на непересекающиеся подобласти для эллиптических краевых задач с разрывом коэффициентов на границах подобластей.  ,   Рассмотрим декомпозицию на два подпространства .Здесь  Пусть  : Положим  .Обозначим  и определим , ,, .Тогда .Рассмотрим  . .  .  , .Для решения  рассмотрим итерационный процесс с Чебышевским набором параметров   Положим  Тогда  Положим  Теорема.  : Третья глава диссертации посвящена методу фиктивного пространства. Данный метод является развитием идеологии решения краевых задач, заложенной в методах фиктивных областей и фиктивных компонент. Основу метода фиктивного пространства составляет введение фиктивного более “богатого” гильбертова пространства, норма в котором определяется легко обратимым оператором, использование соответствующего оператора сужения из введённого гильбертово пространства в исходное. Используя этот метод, удаётся как “упростить” геометрию исходной области, так и “улучшить” структуру сетки. В пункте 3.1 формулируется и доказывается лемма, которая является основой метода фиктивного пространства. Лемма. Пусть  ,  - гильбертовы пространства со скалярными произведениями  ,  соответственно,  ,  – самосопряженные положительно определенные непрерывные операторы в пространствах , : Пусть  - линейный оператор такой, что для любого элемента  . И пусть существует оператор такой, что для любого элемента  . Здесь  ,  - положительные константы. Тогда для любого элемента . Здесь  - оператор, сопряженный к относительно скалярных произведений , : В пункте 3.2 рассматривается применение леммы о фиктивном пространстве для построения переобуславливающих операторов для модельных эллиптических задач в  - образных областях с краевыми условиями Дирихле и смешанными краевыми условиями.Метод фиктивного пространства для построения переобуславливающего оператора для сеточных эллиптических краевых задач в кусочно-гладких областях рассматривается в пункте 3.3. Метод фиктивного пространства применяется следующим образом. Сначала упрощается геометрия исходной области, а затем улучшается структура сетки. Основные арифметические затраты при реализации переобуславливающего оператора заключается в использовании переобуславливающего оператора на равномерной сетке в прямоугольной области. Константы спектральной эквивалентности предложенного переобуславливающего оператора и сеточного эллиптического оператора со смешанными краевыми условиями не зависят от шага сетки. В пункте 3.4 определяются переобуславливающие операторы на основе двух подходов: метода фиктивного пространства и многоуровневой декомпозиции на неструктурированных сетках. В отличие от пункта 3.3 последовательность применения метода фиктивного пространства меняется: на первом шаге улучшается структура сетки и осуществляется переход на фиктивную (вспомогательную) структурированную, но ещё не иерархическую, сетку, на втором шаге улучшается геометрия, то есть область заключается в фиктивную область простого вида (квадрат), в которой используется естественная иерархия сеток и соответствующих подпространств для построения многоуровневых переобуславливателей. Константы спектральной эквивалентности предложенного переобуславливающего оператора и исходного оператора задачи не зависят от шага сетки, а арифметическая сложность реализации переобуславливателя пропорциональна числу степеней свободы исходной задачи. В четвертой главе предлагается построение переобуславливающих операторов для двух классов задач с особенностями: эллиптических краевых задач с разрывными коэффициентами в малых подобластях (на основе специального метода декомпозиции) и для анизотропных эллиптических краевых задач (с использованием эквивалентных нормировок в соответствующем пространстве следов сеточных функций). В пункте 4.1 рассматриваются эллиптические краевые задачи в случае, когда в подобластях, диаметр которых характеризуется параметрами  такими, что  , а коэффициенты задачи в этих подобластях характеризуются параметрами  такими, что  . В подпункте 4.1.2 предлагается построение переобуславливателя на основе декомпозиции области на непересекающиеся подобласти. Результаты, полученные в данном подпункте, имеют как самостоятельное значение, так и существенно используются в следующем подпункте. Наибольший интерес представляют результаты, полученные в подпункте 4.1.3, где переобуславливающий оператор строится на основе декомпозиции области на пересекающиеся подобласти. Примечательно, что для задачи с разрывными коэффициентами строится переобуславливающий оператор, использующий переобуславливающие операторы только для операторов Лапласа (например, из третьей главы) и не использует операторы продолжения сеточных функций. Константы спектральной эквивалентности предложенного переобуславливающего оператора и оператора исходной задачи не зависят от параметров  и шага сетки, а арифметическая сложность реализации переобуславливателя пропорциональна числу степеней свободы исходной задачи.Пункт 4.2 посвящён методу декомпозиции области для эллиптических краевых задач с анизотропными кусочно-постоянными коэффициентами. Общая схема построения переобуславливателя основана на предлагаемом методе декомпозиции области для непересекающихся подобластей (пункт 2.3) и внутренних Чебышевских итераций (пункт 2.7). Принципиальным моментом в построении и исследовании переобуславливающего оператора является использование результатов, полученных в пункте 1.4. Константы спектральной эквивалентности предложенного переобуславливающего оператора и оператора исходной задачи не зависят от шага сетки  и коэффициентов  и  исходного анизотропного эллиптического оператора. Арифметическая сложность реализации переобуславливателя пропорциональна ,где  , – шаг сетки.В заключении сформулированы основные результаты, совокупность которых выносится на защиту: 1. Сеточные теоремы о следах конечно-элементных функций: а) Сеточные теоремы о следах в пространстве Соболева , включая случай сгущающихся сеток.б) Теорема о следах конечно-элементных функций для областей с малым диаметром. в) Терема о следах конечно-элементных функций в случае весового пространства Соболева .г) Терема о следах конечно-элементных функций для анизотропных (узких) областей. д) Теорема о следах конечно-элементных функций в случае весового пространства Соболева .2. Разработана теория Аддитивного метода Шварца в абстрактных гильбертовых пространствах (совместно с А.М. Мацокиным). На основе этого метода предложены и обоснованы: а) Новые формулировки методов декомпозиции области для непересекающихся подобластей. б) Метод явного продолжения сеточных функций на иерархических сетках с сохранением нормы с оптимальной арифметической сложностью. в) Аддитивный метод Шварца на границах подобластей в пространстве Соболева .г) Метод декомпозиции области для случая большого числа подобластей. д) Построены оптимальные переобуславливающие операторы для эллиптических задач с разрывными коэффициентами диффузии. 3. Разработана теория метода фиктивного пространства в абстрактных гильбертовых пространствах, который является обобщением известного метода фиктивных областей. На основе этого метода предложены и обоснованы: а) Переобуславливающие операторы для эллиптических задач с кусочно-гладкими границами. б) Используя комбинацию Аддитивного метода Шварца и метода фиктивного пространства, предложен оптимальный многоуровневый переобуславливатель для решения эллиптических задач на неструктурированных сетках. 4. Предложен новый оптимальный метод декомпозиции для решения эллиптических задач с разрывными коэффициентами без использования явных операторов продолжения сеточных функций и с использованием только переобуславливателей для оператора Лапласа. 5. На основе предложенного метода декомпозиции области и сеточных теоремах о следах предложены эффективные переобуславливающие операторы для анизотропных эллиптических задач. |
1 2
Добавить документ в свой блог или на сайт
Похожие:
 | Программа дисциплины ен. Ф. 01. 7 "Методы оптимизации" Рекомендуется... Дисциплина “Методы оптимизации” является математической основой решения различных проблем выбора одного из возможных образов действий,... | | Методы вычислений с контролем точности на квазиравномерных сетках... Р-52 Раджабова Н. Н., Умарова Б. Х хусанова Т. К. Методические разработки для самостоятельной работы по русскому языку для студентов... |
 | Обзор цифровых образовательных ресурсов, рекомендованных Министерством... Программа предназначена для проведения квалификационных испытаний в рамках процедуры аттестации педагогических работников по должности... | | Программа по формированию навыков безопасного поведения на дорогах... Наименование образовательной программы, профиль: дисциплина «Математический анализ», направление 010100 62-10-1-2362 «Математика»,... |
| Литература А. С. Пушкин. В зеркале двух столетий. Мультимедиа энциклопедия.... Объем информации, входящей в энциклопедию, составляет 70 книжных томов. В состав бэкм 2002 вошли 5 словарей | | Рабочая программа учебной дисциплины дискретная математика Компьютерные системы и комплексы, укрупненной группы специальности 230000 Информатика и вычислительная техника, примерной программы,... |
| Программа дисциплины «Методы планирования производственных процессов»... Программа дисциплины «Методы планирования производственных процессов» для направления 230100 – «Информатика и вычислительная техника»... | | Пояснительная записка рабочая программа дисциплины «Иностранный язык... «Математика и компьютерные науки», 010500. 62 «Математическое обеспечение и администрирование информационных систем», 230100. 62... |
| Бюллетень экспериментальной биологии и медицины Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика | | Рабочая программа дисциплины дискретная математика (наименование)... |
| Рабочая программа для студентов очной формы обучения, направления... ... | | Программа дисциплины Современные методы принятия решений для направления... Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки 010400.... |
| Программа по формированию навыков безопасного поведения на дорогах... Электронное средство учебного назначения «Вычислительная математика и программирование» | | Литература Погрешности вычислений Программа предназначена для подготовки к вступительным испытаниям в аспирантуру по направлению 02. 06. 01 «Компьютерные и информационные... |
| Декомпозиция сигналов на основе вейвлетов Гаусса и Морле (dwsignal) Программа предназначена для декомпозиции сигналов и может применяться в научных исследованиях и при обучении студентов специализирующихся... | | Урок (математика и окружающий мир) Цель: формирование образовательных компетенций учащихся в рамках проекта «Тайны космического пространства» |
