Методы декомпозиции области и фиктивного пространства тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

На правах рукописи

4-0 (ЦЬ^ ^

Непомнящих Сергей Владимирович

Методы декомпозиции области и фиктивного пространства

01.01.07 - вычислительная математика

Автореферат

диссертации на соискание ученой степени доктора физико-математических наук

00346010В

Новосибирск, 2008

003460108

Работа выполнена в Новосибирском государственном университете.

Официальные оппоненты: доктор физико-математических

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

Чижонков Евгений Владимирович

Ведущая организация: Институт вычислительного

моделирования СО РАН (ИВМ СО РАН)

Защита состоится 13 февраля 2009 года в 14:00 часов на заседании Диссертационного совета Д 002.045.01 в Институте вычислительной математики РАН по адресу: 119991, г. Москва, ГСП-1, ул. Губкина, 8.

С диссертацией можно ознакомиться в библиотеке Института вычислительной математики РАН.

Автореферат разослан 24 декабря 2008 года.

Ученый секретарь диссертационного совета доктор физико-математических наук

Бочаров Г.А.

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

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

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

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

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

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

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

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

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

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

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

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 страницы.

Содержание работы

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

Первая глава диссертации посвящена сеточным аналогам теоремы о следах в пространствах Соболева, как для классических нормировок в пространстве Соболева Hl(Q), где П — заданная область

Ня1(П) = Мячп) + 1М1ь2(П) » п 1-1

1МЙ2(П) = У и2{х)йх, п

и, соответственно, в пространстве следов Н1/2(Г), где Г —граница области П

1М1#1/2(Г) = 1^1я»/2(Г) + 1М1ь2(Г),

-11

г г

М\ь2(Г) = 1<Р2Шх,

г

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

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

Пункт 1.2 посвящен сеточным теоремам о следах в пространстве Соболева Н1 (О,). Рассматривается как случай полной нормы в пространстве Н1(0.), так и случай полунормы.

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

В пункте 1.3 рассматриваются пространства Соболева Нр д(£1) с параметрами. Здесь

Ыщ,ч(П) = Р МяЧП) + 9 Ни11ь2(П)'

Ы12(П) = У

а

Мячп) = I и(х)\)2(1х. а

Такие пространства рассматривались М.С. Агроновичем и М.И. Вишиком и возникают, например, при использовании неявных разностных схем для решения параболических краевых задач. Определяются сеточные нормы в возникающих пространствах следов

2

МГ)' если 5 - Ь '

МИ

р\"рн\н1/2(г)+{ря)^ 1И|£2(г)>если к2<(р/я)<

рИя^(Г)+9|И1?,2(Г)> еСЛИ

и доказываются сеточные теоремы о следах с константами, которые не зависят как от параметров р и д, так и от триангуляции № области О,.

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

случай областей с анизотропной геометрией и анизотропными сетками (при замене переменных меняется как геометрия, так и характеристики триангуляций). Данный пункт состоит из четырёх частей. В первой части пункта (подпункт 1.4.1) рассматривается случай функций во всём пространстве Соболева Н1(О), то есть без конечно-элементных аппроксимаций, в областях с анизотропной геометрией (узкие полосы). Вводится нормировка следов функций, характеризующих область, и доказывается теорема о следах с константами, которые не зависят от геометрии области. Во втором подпункте 1.4.2 рассматривается случай областей с изотропной геометрией, но анизотропной триангуляцией. Определяются сеточные нормы в пространствах следов конечно-элементных функций и доказывается теорема о следах с оптимальными по порядку константами, то есть не зависящими от характеристик анизотропной сетки. В подпункте 1.4.3 доказывается аналогичная теорема для случая, когда диаметр области зависит от малого параметра е. В этом случае константы в теореме о следах не зависят от этого параметра е и анизотропии триангуляции (при соответствующем определении норм в пространствах следов конечно-элементных функций). Наконец, в последнем подпункте 1.4.4 полученные в 1.4.1-1.4.3 результаты объединяются, определяется соответствующая сеточная норма в пространстве следов и доказывается сеточная теорема о следах для случая анизотропных областей с анизотропной триангуляцией. Константы в сеточной теореме о следах не зависят ни от геометрии области, ни от триангуляций.

В последнем пункте 1.5 первой главы рассматриваются весовые пространства Соболева в определении которых участвуют сингулярные весовые функции, характеризующиеся параметром а. Соответствующие нормы в пространстве следов были введены С.М. Никольским:

'1|£2(п) = I и2(х)ёх, п

2 Г (\дгайи{х)\

йх.

При исследовании следов сеточных функций в весовых пространствах Н^(О), важную роль играют сеточные аналоги норм в пространствах и пространствах следов

Я1/2+а(Г)

Пусть

пЛ=( и -Л и Г и и -Л

\т,еМ1 / \ т.'бМг / \т,елг3 /

Мх

М2

М3

и

2 II ьИ2

)= к +

и

= 2 («Л(^))аЛа,

- Е

Ту ем

(Цд1-Цд2)2+(Цд2-Цдз)2 + (Ц^З-Цл)!

(р(ЗД)*«

т}ем2

{щ 1-Цд2)2 + (Цд2 - ЦД-3)2+(^3-ЦД'1)2 ^ (1—2а)/г2а

Т;бЛ/з

2,-ег

(1 — 2а)/г2а •

Для введённых сеточных норм доказан сеточный аналог теоремы о следах в этих пространствах с константами, не зависящими от параметра а и от триангуляции О}1 области О.

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

В пункте 2.1 второй главы в качестве введения в методы декомпозиции областей рассматривается простейший случай метода—так называемая, декомпозиция на полосы (без точек ветвления на объединении границ подобластей). Используя результаты главы 1, предлагаются оптимальные переобуславли-

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

В пункте 2.2 приводится формулировка аддитивного метода Шварца в произвольных гильбертовых пространствах (предложенная совместно с А.М.Мацокиным), которая основана на декомпозиции этого пространства в векторную сумму подпространств. Далее формулируются и доказываются дополнительные утверждения, которые могут быть полезны для решения конкретных задач с использованием абстрактной схемы аддитивного метода Шварца. В частности, предлагается способ определения подпространств с использованием оператора продолжения из более "бедного" пространства в более "богатое" исходное гильбертово пространство.

Теорема. Пусть Я = Я1 + Я2 + .. . + Ят и а(и,ь) = (Аи,ь).

Предположим, что существуют положительные константы а, р, сь с2:

а) а(а(и1,гп) +... + а(ит,ит)) < а(и,и) для щ +... + ит = щ

ас\{А 1и,и) < (В гг4,и) < Рс2(А~1и,и) Уи Е Щ, где Я"1 =В? + В+ + ... + В+.

т

в) В{:Н-> Ни Вг = В1

С1 {В{и, и) < (Аи,и) < С2{В^,и) \/и 6 Я,-

Тогда

Теорема. Пусть Ят и Л"-евклидовы вещественные пространства, а Е и 5—симметричные положительно-определенные матрицы порядка тип соответственно. Обозначим

(<Р,ФЬ =

{и,ь)з = {Би,у)

и пусть Т—линейный оператор, действующий из Дт в В!1 такой, что

а(<р,<р)ъ<{Т1р,Т<р)3</3(<р,<р)ъ

V (р Е Ят. Здесь а, /3—положительные константы. Положим

С = Т£-1Т*,

где Т—оператор, сопряженный к Т относительно евклидовых скалярных произведений в К"1 и Яп. Тогда

а(С+и,и) < (и,и)5 < /3(С+и, и)

V и Е Е, Е — 1тпТ— образ оператора Т, С+ —псевдо-обратный для С.

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

Пункт 2.3 посвящен методу декомпозиции области на непересекающиеся подобласти:

п 1=1

1=1

Положим

Бк = У 7Л =

г=1

На основе аддитивного метода Шварца строится переобуславливающий оператор, являющийся суммой двух переобу-славливателей, который соответствует разбиению (декомпозиции) исходного конечно-элементного пространства в векторную сумму двух подпространств

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

\у0 = [иь е Н(пн, г'1) ик (х) = о, х е 5'1},

И^г = {иН 6 ТУ0 (я) = 0, а^П?,}, ¿ = 1,2,..., п,

Оо = ^од Ф • • ■ ©

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

С1

ЯЧ«?)

< (В0^щ,щ) < с2

нцп*)

Ва =

0 .

о Вод

0 .

о .

о о

о

Во,п

о в0~1

о о

о о

В0,П- J

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

Ч>

я010/2(7")

-пи

1=1

í :Я(7Л) -+Я(П\ГЛ),

< с

V

"¿о'V) '

V?! = 6 Я(П\Гл)|ил = V/ 6 Я^)} ,

С1 (£</>,</>) < V5

Переобуславливающий оператор определяется как

в~1 = в$ + гтгЧ*.

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

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

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

Построению легко обратимого оператора, порождающего норму на объединении границ подобластей, которая эквивалентна норме в пространстве следов Я1/2 с константами, не зависящими от шага сетки, посвящен пункт 2.5. Данное построение основано на аддитивном методе Шварца. Для этого пространство сеточных функций на объединении границ подобластей (внутренних границах) разбивается на пересекающиеся подпространства, часть из которых соответствует окрестностям точек ветвления (точки, где пересекаются границы более двух подобластей), а остальные—криволинейным интервалам, соединяющим точки ветвления.

В пункте 2.6 рассматривается метод декомпозиции области на большое число непересекающихся подобластей. Предлагаемый переобуславливатель основан на аддитивном методе Шварца и имеет похожую структуру, что и переобуславливатель из пункта 2.3. Отличительной особенностью является введение дополнительного каркасного пространства на объединении границ подобластей. Константы спектральной эквивалентности предложенного переобуславливающего оператора и опе-

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

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

п

£2 = и, гфз,

п

р(х) =Рг — «Н^ >0, X е

Рассмотрим декомпозицию на два подпространства

Я(П\ГЛ) = ТЯо + И'ь

Здесь

\У0 = [ик € Я(ПЛ,Г&) ин (х) — 0, гс 6 5Л} ,

= {и11 е \¥о ик (х) = 0, ж ф П*,} , * = 1,2,..

'г >

«0 = «0,1 © • • • © «0,:

Пусть Во,*:

с\

НЦ п*) Положим

< < С2

Во =

О О

«V

О . ... О О р!В0>1 ... О

. . . О

• • • РпВо,п

К

о СрхВод)-1 . .

О О

Обозначим

О О

(РпВо,п) 1 .

у

НУ2(7")

¿=1

Я 1/2(эп£)

и определим

< :Я(7Л) ->Я(П\ГЛ),

< с

ч>

я^ V)'

и^ = е я(о/1,гЛ)|и'1 = ър* V/ е я(7Л)},

С1(Е¥>,¥>) <

ч>

нГ{ 7")

<с2(Е<^) У/бЯ(7/г).

Тогда

Рассмотрим

В'1 +

Т{ —

2 -1 -1 2 -1

-1

-1 2 -1 -1 2

, дан П гл = 0.

Тг =

2 -1 -1 2

-1

-1 2 -1 -1 2

, ап? п гл ^

Ъ = ТУ2, г = 1,2,... ,п, = Р1(Тг^ь + .. . +р„СГп£п,$т»), = + ... + РпрпФпМ,

с{я<р,ф) < (т<р,<р) < с{Еф,<р) е д^0, с = 28т(7г/2ттах), ттах = тахт,-, с = 2.

1<Кп

Для решения

Я(р = ф

рассмотрим итерационный процесс с Чебышевским набором параметров гк

Положим

Ч->° — о,

( п(е) \

ВФ= ^.-Ц^-^Г-^Е"1,

, /г. / \ ^ 1п(2/е) \fb-Jc

Тогда

= в-^р,

1/2(В1/2 <р, <р) < (Е(р, <р) < 3/2(В1/2р, у>) Е Н{Хн).

Положим

Б"1 = + Д+.

Теорема. 3 сх, с2 ^ с(Л,р):

сЦВи,«) < < С2(Вь,ь) УЬ е Ж

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

В пункте 3.1 формулируется и доказывается лемма, которая является основой метода фиктивного пространства.

Лемма. Пусть Но, Я —гильбертовы пространства со скалярными произведениями {щ,уо)н0, (и, и)# соответственно, А, В — самосопряженные положительно определенные непрерывные операторы в пространствах Щ, Я:

А:Н0-+ Н0, В : Я -> Я.

Пусть Я—линейный оператор такой, что

Я : Я -> Н0,

(АЯу,Яу)Но < сд(Яи,и)я

для любого элемента и £ Я. И пусть существует оператор Т такой, что

Т : Но Я, ЯТщ = щ,

ст(ВТио,Тщ)н < (Лщ,щ)е0,

для любого элемента щ € Щ. Здесь сд, сг — положительные константы. Тогда

сг(^_1и0,«о)яо < (ЯВ~хК*ио,ио)н0 < сл(А~1ио,щ)н0

для любого элемента щ € Щ. Здесь Я* — оператор, сопряженный к Я относительно скалярных произведений {ио,Уо)н0,

Я* : Я -> Н0, (Я*Щ,У)н = (щ,ЯУ)Н0■

В пункте 3.2 рассматривается применение леммы о фиктивном пространстве для построения переобуславливающих операторов для модельных эллиптических задач в ¿-образных об-

ластях с краевыми условиями Дирихле и смешанными краевыми условиями.

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

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

В четвертой главе предлагается построение переобуславливающих операторов для двух классов задач с особенностями: эллиптических краевых задач с разрывными коэффициентами в малых подобластях (на основе специального метода деком-

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

В пункте 4.1 рассматриваются эллиптические краевые задачи в случае, когда в подобластях, диаметр которых характеризуется параметрами Щ такими, что 0 < Н{ < 1, а коэффициенты задачи в этих подобластях характеризуются параметрами £г такими, что 0 < £{ < 1. В подпункте 4.1.2 предлагается построение переобуславливателя на основе декомпозиции области на непересекающиеся подобласти. Результаты, полученные в данном подпункте, имеют как самостоятельное значение, так и существенно используются в следующем подпункте. Наибольший интерес представляют результаты, полученные в подпункте 4.1.3, где переобуславливающий оператор строится на основе декомпозиции области на пересекающиеся подобласти. Примечательно, что для задачи с разрывными коэффициентами строится переобуславливающий оператор, использующий переобуславливающие операторы только для операторов Лапласа (например, из третьей главы) и не использует операторы продолжения сеточных функций. Константы спектральной эквивалентности предложенного переобуславливающего оператора и оператора исходной задачи не зависят от параметров

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

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

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

maxjl/fc2; (l/7i) max Pi{x) /р2{х)-, ч/ргИМИ}} ,

где х Eil, h—шаг сетки.

В заключении сформулированы основные результаты, совокупность которых выносится на защиту:

1. Сеточные теоремы о следах конечно-элементных функций:

а) Сеточные теоремы о следах в пространстве Соболева Н1(П), включая случай сгущающихся сеток.

б) Теорема о следах конечно-элементных функций для областей с малым диаметром.

в) Теорема о следах конечно-элементных функций в случае весового пространства Соболева Hp q(Q,).

г) Теорема о следах конечно-элементных функций для анизотропных (узких) областей.

д) Теорема о следах конечно-элементных функций в случае весового пространства Соболева

2. Разработана теория Аддитивного метода Шварца в абстрактных гильбертовых пространствах (совместно с A.M. Мацокиным). На основе этого метода предложены и обоснованы:

а) Новые формулировки методов декомпозиции области для непересекающихся подобластей.

б) Метод явного продолжения сеточных функций на иерархических сетках с сохранением нормы с оптимальной арифметической сложностью.

в) Аддитивный метод Шварца на границах подобластей в пространстве Соболева Я1/2.

г) Метод декомпозиции области для случая большого числа подобластей.

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

3. Разработана теория метода фиктивного пространства в абстрактных гильбертовых пространствах, который является обобщением известного метода фиктивных областей. На основе этого метода предложены и обоснованы:

а) Переобуславливающие операторы для эллиптических задач с кусочно-гладкими границами.

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

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

5. На основе предложенного метода декомпозиции области и сеточных теоремах о следах построены эффективные переобуславливающие операторы для анизотропных эллиптических задач.

Благодарности. Автор считает своим приятным долгом выразить глубокую благодарность своему учителю д.ф.-м.н. Александру Михайловичу Мацокину за постоянную научную поддержку при выполнении данной работы. Автор также признателен д.ф.-м.н. Юрию Алексеевичу Кузнецову за искреннее внимание и постоянное творческое взаимодействие, способствующие плодотворной работе над диссертацией.

Список основных публикаций

Список работ автора по теме диссертации, которые опубликованы в рецензируемых изданиях.

Статьи, опубликованные в журналах, рекомендуемых ВАК.

[1] Мацокин A.M., Непомнящих С.В. Метод альтернирования Шварца в подпространствах. // Изв. высш. учебных заведений. Математика, 1985, Т.29, №10, С.61-66.

[2] Мацокин A.M., Непомнящих С.В. Метод фиктивного пространства и операторы продолжения. // Ж. вычисл. мат. и мат. физ., 1993, Т.ЗЗ, №1, С.52-68.

[3] Мацокин A.M., Непомнящих С.В., Ткачев Ю.А., Юнг М. Методы многоуровневого переобусавливания на локально модифицированных сетках. // Сиб. журн. вычисл. матем., - Новосибирск: СО РАН, 2006, Т.9, №4, С.403-421.

[4] Непомнящих С.В. Метод разбиения пространства для эллиптических проблем со скачками коэффициентов в узких полосах. // Докл. РАН, 1992, Т.45, №2, С.488-491.

[5] Bank R.E., Jimack Р.К., Nadeem S.A., Nepomnyaschikh S.V. A weakly overlapping domain decomposition preconditioner for the finite element solution of elliptic partial differential equations. // SIAM J. Sci. Comput., 2001, V.23, №6, P.1818-1842.

[6] Beuchler S., Nepomnyashchikh S.V. Overlapping Additive Schwarz Preconditioners for Elliptic Problems with Degenerate Locally Anisotropic Coefficients. // SIAM J. on Numer. Anal., 2007, V.45, №6, P.2321-2344.

[7] Globisch G., Nepomnyaschikh S.V. The hierarchical preconditioning having unstructured grids. // Computing J., 1998, №61, P.307-330.

[8] Jung M., Nepomnyaschikh S.V. Variable additive preconditioning procedures. // Computing J., 1999, №62, P.109-128.

[9] Kwak D.Y., Nepomnyaschikh S.V., Pyo H.C. Domain decomposition for model heterogeneous anisotropic problems. // Numer. Lin. Alg. Appl., 2003, №10, P. 129-157.

[10] Matsokin A.M., Nepomnyashchikh S.V. Norms in the space of traces of mesh functions. // Soviet J. Numer. Anal, and Math. Modell., 1988, V.3, №3, P. 199-216.

[11] Matsokin A.M., Nepomnyaschikh S.V. On the convergence of the non-overlapping Schwarz subdomain alternating method. // Soviet J. Numer. Anal, and Math. Modell., 1989, V.4, №6, P.479-486.

[12] Matsokin A.M., Nepomnyaschikh S.V. On using the bordering method for solving systems of mesh equations. // Soviet J. Numer. Anal, and Math. Modell., 1989, V.4, № 6, P.487-492.

[13] Nepomnyaschikh S.V. On the application of the bordering method to the mixed boundary value problem for elliptic equations and on mesh norms in // Soviet J. Numer. Anal, and Math. Modell., 1989, V.4, №6, P.493-506.

[14] Nepomnyaschikh S.V. Schwarz alternating method for solving the singular Neumann problem. // Soviet J. Numer. Anal, and Math. Modell., 1990, V.5, №6, P.69-78.

[15] Nepomnyaschikh S.V. Method of splitting into subspaces for solving elliptic boundary-value problems in complex-form domains. // Soviet J. Numer. Anal, and Math. Modell., 1991, V.6, №2, P.151-168.

[16] Nepomnyaschikh S.V. Mesh theorems of traces, normalizations of function traces and their inversion. // Soviet J. Numer. Anal, and Math. Modell., 1991, V.6, №3, P.223-242.

Работы, опубликованные в рецензируемых изданиях.

[1] Beuchler S., Nepomnyashchikh S.V. Overlapping Additive Schwarz preconditioners for isotropic elliptic problems with degenerate coefficients. //J. Numer. Math., 2007, V.15, №4, P.245-276.

[2] Haase G., Langer U., Meyer A. and Nepomnyashchikh S.V. Hierarchical extension and local multigrid methods in domain decomposition preconditions. // East-West J. Numer. Math., 1994, V.2, №3, P. 173-193.

[3] Haase G., Nepomnyashchikh S.V. Explicit extension operators on hierarchical grids. // East-West J. Nuraer. Math., 1997, V.5, №4, P.231-348.

[4] Matsokin A.M., Nepomnyashchikh S.V. The fictitious component method using extension operators. // Siberian J. Comput. Math., 1992, V.l, №1, P.31-45.

[5] Nepomnyashchikh S.V. Domain decomposition method for the elliptic problem with jumps in the coefficients in thin strips. //Siberian J. Comput. Math., 1992, V.l, №2, P.23-34.

[6] Nepomnyaschikh S.V. Fictitious space method on unstructured meshes. // East-West J. Numer. Math., 1995, V.3, №1, P.71-79.

[7] Nepomnyaschikh, E.-J. Park. Preconditioning for Heterogeneous Problems. In Domain Decomposition Methods in Science and Engineering. // Lecture Notes in Comput. Sci. and Engin. (LNCSE), Springer, 2004, V.40, P.415-422.

[8] Nepomnyashchikh S.V. Domain decomposition methods. // Radon Series Comput. Appl. Math., 2007, V.l, P.89-159.

Непомнящих Сергей Владимирович

Методы декомпозиции области и фиктивного пространства

Автореферат

диссертации на соискание ученой степени доктора физико-математических наук

Подписано в печать 25.11.2008 г.

Формат бумаги 60 х 841/i6 Объем 2,0 п. л.

Тираж 100 экз.

1,9 уч.-изд. л.

Заказ № 454

Редакционно-издательский центр Новосибирского госуниверситета, 630090, г. Новосибирск, ул. Пирогова, 2

Введение.

1. Теоремы о следах для сеточных функций.

1.1. Переобуславливающие операторы для эллиптических краевых задач.

1.2. Сеточные теоремы о следах в пространствах Соболева Н1 (Q)

1.3. Конечно-элементные теоремы о следах для пространств

Соболева Hi, п.

1.4. Анизотропные области с анизотропными сетками.

1.4.1. Теорема о следах для тонких областей.

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

1.4.3. Теорема о следах для областей с малым диаметром в конечно-элементном случае.

1.4.4. Теорема о следах для анизотропных сеток в узких областях в случае конечных элементов.

1.5. Конечно-элементная теорема о следах для весовых пространств

Соболева

2. Декомпозиция области - Аддитивный метод Шварца.

2.1. Метод декомпозиции области: случай полос.

2.2. Аддитивный метод Шварца в гильбертовом пространстве.

2.3. Декомпозиция области для непересекающихся подобластей.

2.4. Явные операторы продолжения сеточных функций.

2.4.1. Явные операторы продолжения интегрального типа.

2.4.2. Явные операторы продолжения на иерархических сетках

2.5. Аддитивный метод Шварца на внутренних границах.

2.6. Метод декомпозиции для случая большого числа подобластей

2.7. Декомпозиция области для эллиптических краевых задач с разрывными коэффициентами.

3. Метод фиктивного пространства.

3.1. Лемма о фиктивном пространстве.

3.2. Метод фиктивного пространства для модельных задач.

3.3. Метод фиктивного пространства для кусочно-гладких областей

3.4. Метод фиктивного пространства и многоуровневой декомпозиции

3.4.1. Переход на структурированную сетку.

3.4.2. Многоуровневые переобуславливающие операторы.

4. Переобуславливающие операторы для задач с особенностями.

4.1. Эллиптические краевые задачи с разрывными коэффициентами в малых подобластях.

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

4.1.2. Декомпозиция области без пересечений.

4.1.3. Декомпозиция области с перекрытием.

4.2. Переобуславливающие операторы для анизотропных задач.

Многие задачи естествознания и в частности математической физики приводят к краевым задачам эллиптического и параболического типа для дифференциальных уравнений в частных производных. Во многих случаях краевые задачи можно заменить на равносильные вариационные или проекционные задачи в соответствующих гильбертовых пространствах (пространствах Соболева [113]). Для приближенного решения краевых, вариационных или проекционных задач обычно используются разностные и вариационно-разностные методы, приводящие к системам линейных алгебраических (сеточных) уравнений. Современные задачи науки и техники, стремление создать детальную картину исследуемых явлений предъявляют все более высокие требования к точности их моделирования, следствием чего являются усложнение методов построения и повышения размера систем сеточных уравнений.

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

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

Настоящая диссертация посвящена исследованию и разработке итерационных методов решения краевых задач для дифференциальных уравнений эллиптического типа второго порядка в областях сложной геометрической формы и их вариационно-разностных аналогов. Краевая задача формулируется как задача представления линейного функционала в гильбертовом пространстве. Наиболее эффективные методы решения краевых задач в областях сложной геометрической формы, как правило, связаны с методами упрощения геометрии области. Для решения этой задачи строятся два класса итерационных процессов. В основе первого класса лежит идея метода альтернирования Шварца по подобластям [186] (методы декомпозиции области). Второй является аналогом метода фиктивных областей [109]. В диссертационной работе предложено развитие идей этих подходов: аддитивный метод Шварца [78] и метод фиктивного пространства [88, 166]. Литература, посвященная методам построения и решения систем сеточных уравнений, чрезвычайно обширна. Достаточно полное и подробное изложение полученных к настоящему времени результатов в этой области содержится в монографиях, учебных пособиях и обзорах С.К.Годунова и В.С.Рябенысого [20], Е.Г.Дьяконова [26], В.Л.Ильина [27], А.Д.Ляшко и М.М.Карчевского [33], В.Г.Корнеева [39], Ю.А.Кузнецова [44], В.И.Лебедева [58], В.И.Лебедева и В.И.Агошкова [60], Г.И.Марчука [61], Г.И.Марчука и В.И.Лебедева [64], Г.И.Марчука и В.В.Шайдурова [65], С.Г.Михлина [82], Ж.-П.Обэна [92], Л.А.Оганесяна, В.Я.Ривкинда и Л.А.Руховца [93-94], Г.Н.Положего [98], В.С.Рябенького [103], А.А.Самарского [105], А.А.Самарского и Е.С.Николаева [107], А.А.Самарского, И.Е.Капорина, А.Б.Кучерова и Е.С.Николаева [106], Г.Стронга и Дж.Фикса [115], Ф.Сьярле [116], Р.П.Федоренко [120], В.Е.Шаманского [123] и многих других. Остановимся более подробно на результатах, относящихся к теме диссертационной работы. Первую группу составляют методы, основанные на предварительной декомпозиции исходной области, на подобласти более простого вида. Эти методы не только позволяет упрощать исходную задачу, но и является методом распараллеливания задачи. Первым методом такого типа является классический метод альтернирования Шварца [186, 19], в котором исходная область разбивается на пересекающиеся подобласти. Слабая формулировка этого метода исследовалась С.Л.Соболевым [112]. Целесообразность применения метода альтернирования Шварца для разностного уравнения Лапласа исследовалась М.А.Алексидзе в [2], в которой подчеркивается эффективность этого метода в случае, когда количество узлов сеточной области превышает объём оперативной памяти ЭВМ. Метод альтернирования Шварца на разностном уровне рассматривался также в работах [164, 25]. С.Е. Романовой [101] исследуется метод альтернирования Шварца для решения первой краевой задачи для разностных уравнений Лапласа и Пуассона на многогранниках, стороны которых параллельны координатным осям и биссектрисам координатных углов. Помимо метода альтернирования Шварца к этой группе методов относится другой класс итерационных методов, который связан с декомпозицией области на непересекающиеся подобласти. К данному классу относятся методы интегрирования по подобластям со специальными условиями сопряжения на линиях касания подобластей [66, 34, 122, 69, 70, 110, 111, 59]. На основе операторов Пуанкаре-Стеклова [180, 114] методы декомпозиции (композиции) в составных областях были предложены в [60, 58]. Целесообразность применения такого подхода для решения задачи Дирихле для разностного аналога уравнения Лапласа в случае области, состоящей из двух прямоугольников, отмечалась ещё в [185]. Однако, лишь блочно-релаксационный метод в подпространстве, предложенный Ю.А.Кузнецовым [40] и развитый в [41-44], позволил решит смешанные краевые задачи для эллиптических уравнений с кусочно-постоянными коэффициентами в областях, состоящих из прямоугольников, с точностью -2 — 1 — 1

8 > 0 за 0(h (lnh + In s )) арифметических действий, где h - шаг сетки. Эффективность метода [40-44] основано на использовании алгоритма частичного решения алгебраических систем уравнений, возникающих в ходе реализации метода [40, 128, 48, 118, 28, 15, 49]. В работе Е.Г.Дьяконова [25] блочно-релаксационный метод в пространстве трактуется с позиций метода окаймления. Как показано в работах [76, 23] матрица системы уравнений, которая получается после решения задач внутри каждой подобласти, порождает нормировку следов сеточных функций на границах подобластей в

1/2 пространстве Соболева Н . Скорость сходимости соответствующих итерационных процессов не зависит от шага сетки. Следует особо подчеркнуть, что в данных работах либо рассматривается случай двух подобластей, либо с методологической точки зрения ему эквивалентный случай, когда разрезы, делящие область на подобласти, не пересекаются. Непосредственное перенесение этих методов либо вообще не осуществимо, либо приводит к тому, что скорость сходимости итерационного процесса становится зависящей от шага сетки (в случае непрерывного замыкания алгоритмов отсутствует экспоненциальная сходимость). Построение оптимального алгоритма с точки зрения скорости сходимости и арифметической сложности его применения для переобуславливающихся разрезов требует применения дополнительных идей. Для этого чрезвычайно продуктивным оказался, так называемый, аддитивный метод Шварца. Впервые оптимальный алгоритм для случая пересекающихся разрезов был предложен в [84], где использовался аддитивный метод Шварца в пространстве следов. Как метод, аддитивный метод Шварца был предложен в

78]. Здесь формализм аддитивного метода Шварца рассматривался для случая разложения абстрактного гильбертова пространства в векторную сумму подпространств. В специальном случае для оператора Лапласа и областей, состоящих из прямоугольников или параллелепипедов, аддитивный метод Шварца рассматривался в [108]. В дальнейшем аддитивный метод Шварца использовался в [85, 161, 88, 87, 143, 90, 200, 195, 80, 144, 149, 129, 157] и многих других работах. Отметим, что в ряде случаев абстрактная формулировка аддитивного метода Шварца связана с разбиением области или множества, состоящего из объединения разрезов, на пересекающиеся подструктуры. Важное приложение аддитивного метода Шварца было предложено А.М.Мацокиным в [74], где исходное пространство сеточных функций раскладывалось в векторную сумму двух подпространств, где одно из подпространств соответствует сеточным функциям на макроэлементах, определенных на исходной триангуляции области, а второе подпространство соответствует сеточным функциям в вершинах, не входящих во множество опорных узлов макроэлементов. Позже эта идея использовалась J. Хи [196].

Вторая группа методов тесно связана с классическим методом фиктивных областей, предложенным в [18], позднее развитым и исследованным В.К.Саульевым [109],В.И.Лебедевым [57],В.Я.Ривкиндом [99], Л.А.Руховцом [102], В.Д.Копчёновым [37], А.Н.Коноваловым [36] и другими. Данный метод использует расширение оператора из исходной области до некоторой фиктивной области простой формы, например, до прямоугольника в двухмерном случае или параллелепипеда в трёхмерном. Коэффициенты расширенного оператора в фиктивной области зависят от некоторого малого параметра. Расширение оператора без малого параметра известно как матричный аналог метода фиктивных областей и позднее это направление развивалось как метод фиктивных компонент. Основа этого направления была предложена в [5, 73] и исследована в работах [6, 7, 29-32, 47, 49-51, 6768, 70-71, 73, 81, 106, 117, 162]. К этой группе методов тесно примыкают алгоритмы, основанные на теории разностных потенциалов [8, 9, 55, 83, 103, 104] или использующие матрицы емкости [23, 137, 141, 178, 181-183, 193]. Скорость сходимости метода фиктивных компонент, построенного на основе расширения системы сеточных уравнений уравнениями с нулевыми коэффициентами и правой частью (симметричное расширение), существенным образом зависит от типа краевых условий. Случай естественных краевых условий был исследован Г.П. Астраханцевым в работе [5], где доказана независимость скорости сходимости метода от шага сетки. Случай главных краевых условий был исследован A.M. Мацокиным в [68], где исследована зависимость скорости сходимости метода от шага сетки. Детальный анализ спектра матрицы перехода (шага) метода фиктивных компонент привел к схеме построения несимметричного расширения системы вариационно-разностных уравнений [70], для которого скорость сходимости метода уже не зависит от параметра сеточной области и в случае главных краевых условий. Аналогичные результаты для систем разностных уравнений были получены И.Е. Капориным и Е.С. Николаевым в [29-32].

Дальнейшее развитие этой группы метод связано с методом фиктивного пространства, который был предложен автором в [88, 166]. Метод предлагает технологию построения переобуславливающих операторов в абстрактных гильбертовых пространствах. Основу метода фиктивного пространства составляет введение некоторого фиктивного гильбертова пространства (по аналогии с введением фиктивной области), норма в котором определяется легко обратимым оператором. Далее используется оператор сужения из введенного гильбертова пространства в исходное гильбертово пространство. Действие результирующего переобуславливающего оператора пространства на элементе из исходного гильбертова пространства состоит из трёх этапов. Сначала, с помощью оператора, сопряженного к оператору сужения, элемент исходного гильбертова пространства преобразуется в некоторый элемент фиктивного пространства, затем на этом элементе обращается легко обратимый оператор, действующий в фиктивном пространстве, и, наконец, с помощью оператора сужения полученный элемент преобразуется в элемент исходного гильбертова пространства. Применение метода фиктивного пространства для построения переобуславливающих операторов в конечно

1 1/2 элементных подпространствах пространств Соболева Н и Н на неструктурированных сетках позволяет определить оптимальные как по константам спектральной эквивалентности, так и по арифметической сложности реализации переобуславливающие операторы [88, 166, 80, 170]. В данном случае метод фиктивного пространства является эффективным для решения двух типов проблем: упрощения геометрии области и улучшения структуры сетки. В отличие от метода фиктивных компонент метод фиктивного пространства не требует точного решения задач в подобластях или организации двухступенчатого итерационного процесса, а достаточно использование переобуславливающего оператора для модельных задач в областях канонической формы с иерархическими сетками. Следует также отметить ряд работ, посвященных построению эффективных методов решения задач с сильно меняющимися коэффициентами, параболических задач, задач с вариационными неравенствами, а также построению многоуровневых (многосеточных) алгоритмов. [162, 35, 45, 52, 153, 127, 14, 195, 131, 53, 11, 132, 138, 179, 155, 140, 188, 154, 158, 145, 146, 133, 197, 184, 54, 13, 12, 160, 187, 147, 56, 159, 190-192].

Построение и исследование методов декомпозиции области и методов фиктивного пространства тесно связано с использованием теорем о следах функций из пространства Соболева [125, 10, 17] и их сеточных аналогов. Сеточные теоремы о следах сеточных функций на триангуляциях с хаотически расположенными узлами рассматривались [76, 142, 130, 86, 134]. Наиболее полное исследование пространства следов сеточных функций в пространстве Соболева было осуществлено автором в [88, 166], где рассматривался случай локально сгущающихся сеток, а также областей, диаметр которых характеризуется малым параметром. Построение эквивалентных нормировок в пространстве следов тесно связано с задачей о продолжении сеточных функций с сохранением нормы из подобласти в подобласть [7, 21, 22, 73, 194]. По-видимому, впервые определение легко обратимых норм в пространстве следов было осуществлено В.Б.Андреевым в [3] и далее конструктивное определение норм следов было дано в [4], где рассматривался случай прямоугольных сеток. Несколько более гибкая техника для определения легко обратимых норм, позволяющая рассматривать различные комбинации краевых условий, была предложена в [77]. Комбинация результатов из [77] и [88, 166] позволяет определять легко обратимые нормировки следов сеточных функций с хаотически расположенными узлами в области и различными краевыми условиями.

Пространства Соболева с параметрами Нр Ч(П) и соответствующая теорема о следах рассматривались М.С.Агроновичем и М.И.Вишиком [1]. Соответствующая норма в пространстве следов сеточных функций и теорема о следах рассматривались в [176]. Пространства Соболева Н1(Г2) в областях анизотропной формы (узкие области) рассматриваются автором в [90], где была определена норма в пространстве следов и доказана теорема о следах с константами, не зависящими от геометрии области. Сеточная норма в случае анизотропных областей и анизотропных сеток определена в [176, 157] и доказана соответствующая теорема о следах. Весовые пространства Соболева в определении которых участвуют сингулярные весовые функции, характеризующиеся параметром а, изучались С.М.Никольским [91], где была определена норма в пространстве следов и доказана теорема о следах с константами, не зависящими от параметра а. При исследовании следов сеточных функций в весовых пространствах Соболева важную роль играет корректное определение сеточных аналогов норм в пространстве и пространстве следов Н1/2+а(Г). Данные нормы и соответствующие теоремы о следах рассматривались в [168]. Изложим краткое содержание диссертационной работы.

Диссертация состоит из введения, четырёх глав, заключения и списка литературы.

Основные результаты диссертации опубликованы в работах, приведённых в Списке основных публикаций.

На защиту выносится совокупность следующих результатов:

1. Сеточные теоремы о следах конечно-элементных функций: а) Сеточные теоремы о следах в пространстве Соболева H^Q), включая случай сгущающихся сеток. б) Теорема о следах конечно-элементных функций для областей с малым диаметром. в) Терема о следах конечно-элементных функций в случае весового пространства Соболева Н^ (Q). г) Терема о следах конечно-элементных функций для анизотропных (узких) областей. д) Теорема о следах конечно-элементных функций в случае весового пространства Соболева Н^(П).

2. Разработана теория Аддитивного метода Шварца в абстрактных гильбертовых пространствах (совместно с A.M. Мацокиным). На основе этого метода предложены и обоснованы: а) Новые формулировки методов декомпозиции области для непересекающихся подобластей. б) Метод явного продолжения сеточных функций на иерархических сетках с сохранением нормы с оптимальной арифметической сложностью.

-230в) Аддитивный метод Шварца на границах подобластей в пространстве

Соболева Н1/2. г) Метод декомпозиции области для случая большого числа подобластей. д) Построены оптимальные переобуславливающие операторы для эллиптических задач с разрывными коэффициентами диффузии.

3. Разработана теория метода фиктивного пространства в абстрактных гильбертовых пространствах, который является обобщением известного метода фиктивных областей. На основе этого метода предложены и обоснованы: а) Переобуславливающие операторы для эллиптических задач с кусочно-гладкими границами. б) Используя комбинацию Аддитивного метода Шварца и метода фиктивного пространства, предложен оптимальный многоуровневый переобуславливатель для решения эллиптических задач на неструктурированных сетках.

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

5. На основе предложенного метода декомпозиции области и сеточных теоремах о следах предложены эффективные переобуславливающие операторы для анизотропных эллиптических задач.

Заключение

1. Агранович М.С., Вишик М.И. Эллиптические задачи с параметром и параболические задачи общего вида. Успехи математических наук, XIX, 1964,3 (117); 53-161.

2. Алексидзе М.А. О целесообразности применения альтернирующего метода Шварца на электронных цифровых машинах. Докл. АН СССР, 1958, Т. 120, №2; 231-234.

3. Андреев В.Б. Устойчивость разностных схем для эллиптических уравнений по граничным условиям Дирихле. Ж. Выч. Мат. и Мат. Физ., 1972, Т. 12, № 3; 598-611.

4. Андреев В.Б. Эквивалентная нормировка сеточных функций из1/2

5. W2 (у). Исследования по теории разностных схем для эллиптическихи параболических уравнений, Москва: МГУ, 1973; 6-39.

6. Астраханцев Г.П. Итерационные методы решения вариационно-разностных схем для двумерных эллиптических уравнений второго порядка. Дис. к. физ.-мат. наук: 01.01.07., Ленинград, 1972.

7. Астраханцев Г.П. О численном решении задачи Дирихле в произвольной области. Новосибирск, 1977; 63-72.

8. Астраханцев Г.П. Метод фиктивных областей для эллиптического уравнения второго порядка с естественными краевыми условиями. Ж. Выч. Мат. и Мат. Физ., 1978 , Т.18, №1; 118-125.

9. Астраханцев Г.П. О численном решении задачи Дирихле с помощью разностного аналога потенциала двойного слоя. Москва, 1985; 18 е., (Препринт, ОВМ АН СССР; 102).

10. Астраханцев Г.П. О численном решении смешанных краевых задач для эллиптических уравнений второго порядка в произвольной области. Ж. Выч. Мат. и Мат. Физ., 1985, Т.25, №2; 200-209.

11. Бабич В.М., Слободецкий Л.Н. Об ограниченности интеграла Дирихле. Докл. АН СССР, 1956, 106; 604-606.

12. Бахвалов Н.С. Эффективный итерационный метод для решения уравнений Ламе для почти несжимаемой среды и уравнений Стокса. Докл. АН СССР, 1993, Т.44; 4-9.

13. Бахвалов Н.С. Эффективные методы решения жестких многомерных многопараметрических задач. Ж. Выч. Мат. и Мат. Физ., 1999, Т.39, №12; 2019-2049.

14. Бахвалов Н.С. Богачев К.Ю., Метр Ж.А., Эффективный алгоритм решения жестких эллиптических задач с приближениями к методу фиктивных областей. Ж. Выч. Мат. и Мат. Физ., 1999, Т.39, №6; 919931.

15. Бахвалов Н.С., Князев A.B. Эффективный итерационный метод для решения уравнений Ламе для почти несжигаемой среды и уравнений Стокса. Докл. АН СССР, 1992, 44; 4-9.

16. Бахвалов Н.С., Орехов М.Ю. О быстрых способах решения уравнения Пуассона. Ж. Выч. Мат. и Мат. Физ., 1982, Т.22, №6; 1386-1392.

17. Белинский П.П., Годунов С.К., Иванов Ю.Б., Яненко И.К. Применение одного класса квазиконформных отображений для построения разностных сеток в областях с криволинейными границами. Ж. Выч. Мат. и Мат. Физ., 1975, Т.15, №6; 1499-1511.

18. Бесов О.В., Ильин В.П., Никольский С.М. Интегральные представления функций и теоремы вложения. Москва: Наука, 1975; 480с.

19. Вишик В.И., Люстерник Л.А. Асимптотическое поведение решений линейных дифференциальных уравнений с большими или быстро меняющимися коэффициентами и граничными условиями. Успехи мат. наук, 1960, Т. XY, вып. 4(94); 29-95.

20. Годунов С.К. Уравнения матеметической физики. Москва: Наука, 1971; 416с.

21. Годунов С.К., Рябенький B.C. Разностные схемы. Введение в теорию. Москва: Наука, 1977; 439с.

22. Дмитриенко М.Е. О вариационно-разностном методе решения третьей краевой задачи в трехмерной области с входящим углом. Вариационно-разностные методы в мат. физике, Новосибирск, 1978; 81-92.

23. Дмитриенко М.Е., Оганесян Л.А. Вариант метода Шварца для прилегающих сеточных областей. Вычисления с разреженными матрицами, Новосибирск, 1981; 36-44.

24. Дрыя М. Алгоритм с матрицей ёмкости для вариационно-разностной задачи Дирихле. Вариационно-разностные методы в мат. физике, Новосибирск, 1981; 63-73.-23424. Дьяконов Е.Г. Разностные методы решения краевых задач. Москва:1. МГУ, 1971, Вып. 1.

25. Дьяконов Е.Г. О некоторых прямых и итерационных методах, основанных на окаймлении матрицы. В кн.: Численные методы в мат. физике, Новосибирск, 1979; 45-69.

26. Дьяконов Е.Г. Минимизация вычислительной работы. Москва: Наука, 1989; 272.

27. Ильин В.П. Разностные методы решения эллиптических уравнений. Новосибирск: НГУ, 1970; 264с.

28. Капорин И.Е. О задаче решения разностного уравнения Пуассона в неполно-разреженной постановке. В кн.: Разностные методы математической физике. Теория численных методов, Москва, 1981.

29. Капорин И.Е., Николаев Е.С. Метод фиктивных неизвестных для решения уравнений эллиптического типа в областях сложной формы. Докл. АН СССР, 1980, Т.251, №3; 544-548.

30. Капорин И.Е., Николаев Е.С. Метод фиктивных неизвестных для решения разностных эллиптического краевых задач в нерегулярных областях. Дифференц. Уравнения, 1980, Т. 16, №7; 1211-1225.

31. Капорин И.Е., Николаев Е.С. Развитие метода фиктивных неизвестных сопряженных направлений. Дифференц. Уравнения, 1981, Т. 17, №7; 1270-1279.

32. Капорин И.Е., Николаев Е.С. Метод фиктивных неизвестных для симметричных положительно определённых систем. Численные методы линейной алгебры, Москва, 1982; 33-42.

33. Карчевский М.М., Ляшко А.Д. Разностные схемы для нелинейных задач математической физики. Казань: КГУ, 1976; 155с.

34. Кацнельсон В.Э., Меньшиков В.В. Об одном аналоге альтернирующего метода Шварца. Теория функций, функциональный анализ и их приложения, Харьков: ХГУ, 1973, Вып.17; 206-215.

35. Кобельков Г.М. О решении эллиптических уравнений с сильно меняющимися коэффициентами. Москва, 1987; 26с. (Препринт, ОВМ АН СССР, 145).

36. Коновалов А.Н. Метод фиктивных областей в задачах фильтрации двухфазной несжигаемой жидкости с учётом капиллярных сил. Численные методы механики сплошной среды, 1972, Т.З, №5; 52-68.

37. Копчёнов В.Д. Приближенное решение задачи Дирихле методом фиктивных областей. Дифференц. Уравнения, 1968, Т.4, №1.

38. Корнеев В.Г. О построении вариационно-разностных схем высокого порядка точности. Вестн. Ленингр. ун-та. Сер. мат. мех. астрон., 1970, № 4; 28-40.

39. Кузнецов Ю.А. Блочно-релаксационные методы в подпространстве для двумерных эллиптических уравнений. В кн.: Численные методы в мат. физике, Новосибирск, 1979; 20-44.

40. Кузнецов Ю.А. Блочно-релаксационный метод в подпространстве решения двумерных и трехмерных уравнений диффузии в многозонных областях. В кн.: Методы решения систем вариационно-разностных уравнений, Новосибирск, 1979; 24-59.

41. Кузнецов Ю.А. Блочно-релаксационный метод решения задачи Дирихле. В кн.: Теория кубатурных формул и вычислительной математики, Новосибирск, 1980; 69-75.

42. Кузнецов Ю.А. Итерационные методы в подпространствах. Москва: ОВМ АН СССР, 1984; 133с.

43. Кузнецов Ю.А. Новые алгоритмы приближенной реализации неявных разностных схем. Москва, 1987. (Препринт, ОВМ АН СССР, 142). Sov. J. Numer. Anal, and Math. Modell., 1988, Vol.3, №2; 99-144.

44. Кузнецов Ю.А. Алгебраические многосеточные- методы декомпозиции области. Москва, 1989; 41с. (Препринт, АН СССР, ОВМ, 232).

45. Кузнецов Ю.А., Мацокин A.M., Шайдуров В.В. Быстрые итерационные методы решения систем сеточных уравнений. Актуальные проблемы вычислительной математики и мат. моделирования, Новосибирск: Наука, 1985; 207-228.

46. Кузнецов Ю.А., Финогенов С.А. Метод фиктивных компонент для решения трехмерных эллиптических уравнений. Архитектура ЭВМ и численные методы, Москва: ОВМ АН СССР, 1984; 73-94.

47. Кузнецов Ю.А., Финогенов С.А. Двухступенчатый метод фиктивных компонент для двух- и трехмерных задач электростатики. Численные методы и мат. моделирование, Москва: ОВМ АН СССР, 1987; 31-60.

48. Лаевский Ю.М. Методы разбиения области при решении двумерных параболических уравнений. Вариационно-разностные методы в задачах численного анализа, ВЦ СО АН СССР, Новосибирск, 1987; 112-128.

49. Лаевский Ю.М. Прямой метод декомпозиции области решения параболических уравнений. Новосибирск, 1992. (Препринт, ВЦ СО АН СССР, 946). On the domain decomposition method for parabolic problem. Bull. NCC, Numer. Anal., 1993, №1; 41-62.

50. Лаевский Ю.М., Мацокин A.M. Методы декомпозиции решения эллиптических и параболических краевых задач. Сиб. Ж. Выч. Мат., РАН, Сиб. отдел., Новосибирск, 1999, Т.2, №4; 361-372.

51. Лазаров Р.Д., Мокин Ю.И. О вычислении логарифмического потенциала. Докл. АН СССР, 1983, Т.272, №1; 27-30.

52. Лапин A.B., Декомпозиция области и параллельные решения задач со свободными границами. Тр. Матем. Центра им. Н.И. Лобачевского, Казань, 2001, Т.13; 90-126.

53. Лебедев В.И. Разностные аналоги ортогональных разложений основных дифференциальных операторов и некоторых краевых задач математической физики. I. Ж. Выч. Мат. и Мат. Физ., 1964, Т.4, №3; 449-465.

54. Лебедев В.И. Метод композиции. Москва: ОВМ АН СССР, 1986; 191с.

55. Лебедев В.И., Агошков В.И. Обобщенный алгоритм Шварца с переменными параметрами. Москва, 1981; 40с. (Препринт, ОВМ АН СССР, ВИНИТИ, 19).

56. Лебедев В.И., Агошков В.И. Операторы Пуанкоре-Стеклова и их приложения в анализе. Москва: ОВМ АН СССР, 1983; 184с.

57. Марчук Г.И. Методы вычислительной математики. Наука, Москва, 1977; 455 с.

58. Марчук Г.И., Кузнецов Ю.А. Итерационные методы и квадратичные функционалы. Новосибирск, 1972; 205.

59. Марчук Г.И., Кузнецов Ю.А. Некоторые вопросы итерационных методов. Вычислительные методы линейной алгебры, Новосибирск, 1972; 4-20.-23964. Марчук Г.И., Лебедев В.И. Численные методы в теории переносанейтронов. Москва: Атомиздат, 1971; 496с.

60. Марчук Г.И., Шайдурав В.В. Повышение точности решений разностных схем. Москва: Наука, 1979; 318с.

61. Матеева Э.И., Пальцев Б.В. О разделении области при решении краевых задач для уравнения Пуассона в областях сложной формы. Ж. Выч. Мат. и Мат. Физ., 1973, Т.13, №6; 1441-1452.

62. Мацокин A.M. К развитию метода фиктивных компонент. Вычислительные методы линейной алгебры, Новосибирск, 1973; 48-56.

63. Мацокин A.M. О построении и методах решения систем вариационно-разностных уравнений. Дис. к.ф.-м.н.: 01.01.07, Новосибирск, 1975; 117с.

64. Мацокин A.M. Об одном методе решения систем сеточных уравнений. В кн.: Методы решения систем вариационно-разностных уравнений, Новосибирск, 1979; 136-138.

65. Мацокин A.M. Метод фиктивных компонент и модифицированный разностный аналог метода Шварца. Вычислительные методы линейной алгебры, Новосибирск, 1980; 66-77.

66. Мацокин A.M. Метод фиктивных компонент и альтернирования по подобластям. Вычислительные алгоритмы в задачах мат. физики, Новосибирск, 1985; 76-98.-24072. Мацокин A.M. Продолжение сеточных функций с сохранением нормы.

67. Вариационные методы в задачах численного анализа, Новосибирск,1986; 111-132.

68. Мацокин A.M. Связь метода окаймления с методом фиктивных компонент и методом альтернирования по подпространствам. Дифференциальные уравнения с частными производными, Новосибирск: Наука, 1986; 138-142.

69. Мацокин A.M. Решение сеточных уравнений на нерегулярных сетках. Новосибирск, 1987. (Препринт, ВЦ СО АН СССР, 738).

70. Мацокин A.M. Методы фиктивных компонент и альтернирования по подпространствам. Дис. д.ф.-м.н., Новосибирск, 1988; 272с.

71. Мацокин A.M., Непомнящих C.B. О сходимости метода альтернирования Шварца по ' подобластям без налегания. Методы аппроксимации и интерполяции, Новосибирск, 1981; 85-97.

72. Мацокин A.M., Непомнящих C.B. Применение окаймления при решении систем сеточных уравнений. Вычислительные алгоритмы в задачах мат. физики, Новосибирск, 1983; 99-109.

73. Мацокин A.M., Непомнящих C.B. Метод альтернирования Шварца в подпространствах. Изв. Высш. Учебных заведений. Математика, 1985, Т.29, №10; 61-66.

74. Мацокин A.M., Непомнящих C.B. Нормы в пространстве следов сеточных функций. Новосибирск, 1987; 33с. (Препринт, ВЦ СО АН СССР, 737).

75. Мацокин A.M., Непомнящих C.B. Метод фиктивного пространства и операторы продолжения. Ж. Выч. Мат. и Мат. Физ., 1993, Т.ЗЗ, №1; 5268.

76. Мацокин A.M., Скрипко И.Н. Метод фиктивных компонент и смешанные краевые условия. Вычислительные алгоритмы в задачах мат. физики, Новосибирск, 1983; 110-119.

77. Михлин С.Г. Вариационные методы в математической физике. Москва: Наука, 1970; 512с.

78. Мокин Ю.И. Численные методы для интегральных уравнений теории потенциала. Дифференц. уравнения, 1987, Т.23, №7; 1250-1262.

79. Непомнящих C.B. О применении метода окаймления к смешанной краевой задаче для эллиптических уравнений и о сеточных нормах в

80. W./2(S). Новосибирск, 1984; 24с. (Препринт, ВЦ СО АН СССР, № 106).

81. Непомнящих C.B. Метод разделения области для эллиптических задач с разрывными коэффициентами. Новосибирск, 1990; 20с. (Препринт, ВЦ СО АН СССР, №891).

82. Непомнящих C.B. Метод разложения на подпространства для решения эллиптических краевых задач в областях сложной формы. Численные методы и мат. моделирование, Новосибирск, 1990; 128-161.

83. Непомнящих C.B. Сеточные теоремы о следах, нормировка следов сеточных функций и их обращение. Новосибирск, 1991; 25с. (Препринт ВЦ СО АН СССР, 930).

84. Непомнящих C.B. Метод разбиения пространства для эллиптических проблем со скачками коэффициентов в узких полосах. Докл. РАН, Мат., 1992, Т.45, №2; 488-491.

85. Никольский С.М. Аппроксимация функций многих переменных и теоремы вложения. Москва: Наука, 1977.

86. Обен Ж.-П. Приближенное решение эллиптических краевых задач. Москва: Мир, 1977; 383с.

87. Оганесян Л.А., Ривкинд В.Я., Руховец Л.А. Вариационно-разностные методы решения эллиптических уравнений. Часть I. Дифференц. уравнения и их применение, Вып.5, Вильнюс, 1973; 385с.

88. Оганесян Л.А., Ривкинд В.Я., Руховец Л.А. Вариационно-разностные методы решения эллиптических уравнений. Часть II. Дифференц. уравнения и их применение, Вып.8, Вильнюс, 1974; 322с.

89. Оганесян Л.А., Руховец Л.А. Вариационно-разностные методы решения эллиптических уравнений. Ереван: Издат. Акад. Наук Арм. ССР, 1979; 335.

90. Ортега Д., Рейнболдт В. Итерационные методы решения нелинейных систем уравнений со многими неизвестными. Москва: Мир, 1975.

91. Погорелов A.B. Дифференциальная геометрия. Москва: Наука, 1969; 176с.

92. Положий Г.Н. Численное решение двумерных и трехмерных задач математической физики и функции дискретного аргумента. Киев: Киевский ун-т, 1962; 161с.

93. Ривкинд В.Я. Приближенный метод решения задачи Дирихле и об оценках сходимости решений разностных уравнений к решению эллиптических уравнений с разрывными коэффициентами. Вестник ЛГУ, Сер. Матем., 1964, 3.

94. Рисс Ф., Секефальви-Надь Б. Лекции по функциональному анализу. Москва: Мир, 1979.

95. Рябенький B.C. Метод разностных потенциалов для некоторых задач механики сплошных сред. Москва: Наука, 1987; 320с.

96. Рябенький B.C., Белянков А .Я. Разностные потенциалы и проекторы. Докл. АН СССР, 1980, Т.254, №5; 1080-1084.

97. Самарский A.A. Теория разностных схем. Москва: Наука, 1977; 656с.

98. Самарский A.A., Капорин И.Е., Кучеров А.Б., Николаев Е.С. Некоторые современные методы решения сеточных уравнений. Изв. высш. учебных заведений, Математика, 1983, №7; 3-12.

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

100. Сандер С.А. Модификация алгоритма Шварца для решения сеточных, краевых задач в областях, составленных из прямоугольников и прямоугольных параллелепипедов. Новосибирск, 1981; 21с. (Препринт, ВЦ СО АН СССР, № 83).

101. Саульев В.К. О решении некоторых краевых задач на быстродействующих вычислительных машинах методом фиктивных областей. Сиб. Мат. Ж., 1963, Т.4, № 4; 1488-1504.

102. Смелов В.В. Обоснование итерационного процесса по подобластям длязадач теории переноса в нечётном P2N+I приближении. Новосибирск, 1980; 27с. (Препринт, ВЦ СО АН СССР, 71).

103. Смелов B.B., Журавлева Т.Б. Принцип итерирования по подобластям в задачах с эллиптическим уравнением. Москва, 1981; 11с. (Препринт, 14).

104. Соболев C.JI. Алгоритм Шварца в теории упругости. Докл. АН СССР, 1936, T.4(XIII), №6; 235-238.

105. Соболев C.JI. Некоторые применения функционального анализа в математической физике. Ленинград: ЛГУ, 1950.

106. Стеклов В.А. Общие методы решения основных задач математической физики. Харьков: Издание Харьк. мат. общества, 1901.

107. Стренг Г., Фикс Дж. Теория метода конечных элементов. Москва: Мир, 1977; 349с.

108. Сьярле Ф. Метод конечных элементов для эллиптических задач. Москва: Мир, 1980; 512с.

109. Труфанов О.Д. Методы фиктивных компонент и разбиения области для решения волнового уравнения Гельмгольца. Дис. к.ф.-м.н.: 01.01.07, Москва, 1987; 109с.

110. Тыртышников Е.Е. Об алгоритмах дискретного преобразования Фурье. В кн.: Численные методы алгебры, Москва, 1981; 10-26.

111. Федоренко Р.П. О скорости сходимости одного итерационного процесса. Ж. Выч. Мат. и Мат. Физ., 1964, Т.4; 559-564.

112. Федоренко Р.П. Итерационные методы решения разностных эллиптических уравнений. Успехи мат. наук, 1973, T.XXYIII, вып.2; 121-181.

113. Харди Г.Г., Литтльвуд Д.Е., Полна Г. Неравенства. Москва: Иностр. лит., 1948.

114. Цвик Л.Б. Обобщение алгоритма Шварца на случай областей, сопряженных без налегания. Докл. АН СССР, 1975, Т.224, №2; 309-312.

115. Шаманский В.Е. Методы численного решения краевых задач на ЭЦВМ. Киев: Изд-во АН УССР, 1963, 4.1; 196с.

116. Яковлев Г.Н. О следах на кусочно-гладких поверхностях функций из пространства W\. Мат. Сборник , 1967, 74; 526-543.

117. Aronszajn N. Boundary values of functions with finite Dirichlet integral. Confer, partial diff. equat., Studies in eigenvalue problems, Univ. of Kansas, 1955.

118. Axelson O, Yassilevski P. Algebraic multilevel preconditioning methods. I. Numer. Math., 1989, 56; 157-177.

119. Banegas A. Fast Poisson solvers for problems with scarcity. Math. Comput., 1978, Vol.32; 441-446.

120. Bank R.E., Jimack P.K., Nadeem S.A., Nepomnyaschikh S.V. A weakly overlapping domain decomposition preconditioner for the finite elementsolution of elliptic partial differential equations. SIAM J. Sci. Comput., 23, 2001, N6; 1818-1842.

121. Bjorstad P.E., Widlund O.B. Iterative methods for the solution of elliptic problems on regions partitioned in to substructures. N.Y., 1984; 46p.

122. Bogachev K.Yu. Iterative methods of solving main boundary value problems for second-order quasilinear elliptic equations in complexly shaped domains. Rus. J. Numer. Analysis Math. Modell., 1992, Vol.7, №4; 281-298.

123. Bornemann F.A., Yserentant H. A basic norm equivalence for the theory of multilevel methods. Numer. Math., 1993, 64; 455-476.

124. Brambl J.H. Multigrid methods. Pitman Research Notes in Mathematics Series, Vol. 294, Longman Scientific: New York, 1993.

125. Brambl J.H., Pasciak J.E. and Schatz A.H. The construction of preconditioners for elliptic problems by substructuring. I-IV, Math. Comput.; 1986, 47: 103-134; 1987, 49: 1-16; 1988, 51: 415-430; 1989, 53: 1-24.

126. Brambl J.H., Pasciak J.E. and Xu J. Parallel multilevel preconditioners. Math. Comp., 55, 1990; 1-22.

127. Brambl J.H., Zhang X. Uniform convergence of the multigrid V-cycle for an anisotropic problem. Mathematics of Computation, 2000, 70(234): 453-470.

128. Buzbee B.L., Dorr F.W., George J.A., Golub G.H. The direct solution of the discrete Poisson equation oh irregular regions. SIAM J. Numer. Anal. 1971, Vol.8, №4; 722-736.-248138. Chan T., Mathew T. Domain decomposition algorithms. In A. Acta

129. Numerical 1994, Cambridge: Cambridge Univ. Press, 1994; 61-143.

130. Dahmen W., Kunoth A. Multilevel preconditioning. Numer. Math., 1992, 63; 315-344.

131. Dryja M. A finite element capacitance matrix method for the elliptic problem. SIAM J. Numer. Anal. 1983, Vol.20, № 4; 671-680.

132. Dryja M. A finite-element-capacitance method for elliptic problems on regions partitioned into substructures. Numer. Math., 1984, Vol.14; 153-168.

133. Dryja M., Widlund O.B. Domain decomposition algorithms with small overlap. SIAM, J. Sci. Comput., 1994, 15(3); 604-620.

134. Dyadechko V.G., Iliash Yu.I., Vassilevski Yu.V. Structuring preconditioners for unstructured meshes. Russ. J. Numer. Anal. Math. Modell., 1996, Vol. 11, №2; 139-154.

135. Gilyova L.V., Shaidurov V.V. A cascade algorithm for solving a discrete analogue of weak nonlinear elliptic equation. Rus. J. of Numer. Anal, and Math. Modell., 1999, Vol.4, №1; 59-69.

136. Globisch G., Nepomnyaschikh S.V. The hierarchical preconditioning having unstructured grids. Computing J., 61, 1998; 307-330.

137. Griebel M., Oswald P. On the abstract theory of additive and multiplicative Schwarz algorithms. Numer. Math., 1995, 70; 163-180.

138. Haase G., Langer U., Meyer A. and Nepomnyashchikh S.V. Hierarchical extension and local multigrid methods in domain decomposition preconditions. East-West J. Numer. Math., Vol.2, №3, 1994; 173-193.

139. Haase G., Nepomnyashchikh S.V. Explicit extension operators on hierarchical grids. East-West J. Numer. Math., 1997, Vol.5, N4; 231-348.

140. Jung M., Nepomnyaschikh S.V. Variable additive preconditioning procedures. Computing J., 62, 1999; 109-128.-250153. Kobel'kov G.M. Efficient methods for solving elasticity theory equations.

141. Soviet Journal of Numerical Analysis and Mathematical Modell., 1991, 6;361.375.

142. Kobel'kov G.M. On the solution the boundary value problem for the diffusion equation with highly varying coefficient. Rus. J. of Numer. Analysis and Math. Modell., 1996, 11; 487-495.

143. Kornhubert R. and Yserentant H. Multilevel methods for elliptic problems on domains not resolved by the coarse grid. Domain decomposition for PDEs, Keyes D.E. and Xu J. eds., Contemporary Mathematics, 180, 1994; 49-60.

144. Kuznetsov Y.A. Algebraic multigrid domain decomposition methods. Sov. J. of Numer. Analysis and Math. Modell., 1989, 4; 561-577.

145. Kwak D.Y., Nepomnyaschikh S.V., Pyo H.C. Domain decomposition for model heterogeneous anisotropic problems. Numer. Lin. Alg. Appl., 10, 2003; 129-157.

146. Laevsky Yu.M. On the domain decomposition method for grid parabolic problems. Rus. J. of Numer. Anal, and Math. Modell., 1998, Vol.13, №5, 389-403.

147. Laitinen E., Lapin A., Pieska J. Asynchronous domain decomposition methods for continuous casting problem. J. Comp. Appl. Math., 2003, 154; 393-413.

148. Lapin A. Iterative solution for two classes of mesh variational inequalities. ENUMATH-99 (Proceedings of 3-rd European Conf. on Numer. Math, and

149. Advanced Appl., Juvaskyla, Finland, 1999, ed. by P.Neittaanmaki, T.Tiihonen, P.Tarvainen), World scientific, Singapore, 2000; 617-625.

150. Lions P.L. On the Schwarz alternating method. I. First Int. Symposium on Domain Decomposition Methods for Partial Differential Equations, (R. Glavinski, G.H. Golub, G. Meurant and J. Periaux, eds.), SIAM, Philadelphia, 1988; 1-41.

151. Marchuk G.I., Kuznetsov Yu.A., Matsokin A.M. Fictitious domain and domain decomposition method. Sov. J. Numer. Anal. Math. Modell., 1986, Vol.1, №i; 3-35.

152. Matsokin A.M. and Nepomnyashchikh S.V. The fictitious component method using extension operators. Siberian J. Comput. Math., 1, 1992, N1; 31-45.

153. Miller K. Numerical analogs to the Schwarz alternating procedure. Numer. Math. 1965, B.7; 91-103.

154. Nepomnyashchikh S.V. Method of splitting into subspaces for solving elliptic boundary value problems in complex-form domains. Sov. J. Numer. Anal. > Math. Model. 1991, Vol.6, №2; 151-168.

155. Nepomnyashchikh S.V. Mesh theorems on traces, normalization of function traces and their inversion. Sov. J. Numer. Anal. Math. Model., 1991, Vol.6, №3; 223-242.

156. Nepomnyashchikh S.V. Decomposition and fictitious domain methods fortiielliptic boundary value problems. 5 Conference on Domain Decomposition

157. Methods for Partial Differential Equations, SIAM, Philadelphia, PA, 1992; 62-71.

158. Nepomnyaschikh S.V. Domain decomposition for elliptic problems with large condition numbers. Domain Decomposition for PDEs, D.E. Keyes and J. Xu, eds., Contemporary Mathematics, 180, 1994; 75-85

159. Nepomnyaschikh S.V. Domain decomposition and multilevel techniques for preconditioning operators. Technische Univ. Chemnitz-Zwickau, 1995. (Preprint SPC 95-30).

160. Nepomnyaschikh S.V. Fictitious space method on unstructured meshes. East-West J. Numer. Math., 1995, Vol.3, №1; 71-79.

161. Nepomnyaschikh S.V. Optimal multilevel extension operators. Technische Univ. Chemnitz-Zwickau, 1995. (Preprint SPC 95-3).

162. Nepomnyaschikh S.V. Preconditioning operators on unstructured grids. Seventh Copper Mountain Conference on Multigrid Methods, N.D. Melson et al., eds., N3339 in NASA Conference Publication, 1996; 607-621.

163. Nepomnyaschikh S.V. Preconditioning operators for elliptic problems with bad parameters. Domain Decomposition Methods for Sciences and Engineering, C.-H. Lai et al., eds., Published by Domain Decomposition Press, Bergen, 1999; 81-87.

164. Nepomnyashchikh S.V. Finite element trace theorems for parameter dependent Sobolev space. Numerical Mathematics and Advances Applications, World Scientific: Singapore, 2000; 31-41.

165. Nepomnyashchikh S.V. Domain decomposition methods. Radon Series Comput. Appl. Math., 2007, 1; 89-159.

166. O'Leary D.P., Widlund O. Capacitance matrix method for the Helmholtz equation on general three dimensional regions. Math. Comput., 1979, Vol. 33; 849-879.

167. Oswald P. Multilevel finite element approximation: theory and applications. Teubner Skripten zur Numerik, B.G. Teubner, Stuttgart, 1994.

168. Poincare H. La methode de Neuman et le probleme de Dirichlet. Acta Math., 1896, t. 20.

169. Proskurowski W. Numerical solution of Helmholtz's equation by implicit capacitance matrix methods. ACM Trans, on Math. Software., 1979, Vol.5, №i; 36-49.

170. Quarteroni A., Valli A. Domain decomposition methods for partial differential equations. Oxford: Oxford Univ. Press, 1999.

171. Saltzer Ch. An abridged block method for the solution of the Dirichlet problem for the Laplace difference equation. J. Math, and Phys., 1953, Vol. 32, №1; 63-67.

172. Schwarz H.A. Uber einige Abbildungsaufgaben. Ges. Math. Abh., 1869, 11; 65-83.

173. Shaidurov V.V., Tobiska L. The convergence of the cascadic conjugate gradient method applied to elliptic problems in domains with re-entrant corners. Math, of Comput., 1999, Vol.69, №230; 501-520.

174. Smith B.F., Bjorstad P.E., Gropp W.D. Domain decomposition. Parallel multilevel methods for elliptic methods partial differential equations. Cambridge Univ. Press, Cambridge, 1996.

175. Stevenson R. Robustness of multi-grid applied anisotropic equations on convex domains with re-entrant corners. Numer. Math., 1993, 68; 373-398.

176. Toselli A., Widlund O. Domain decomposition methods algorithms and theory. Spring Series in Comput. Math. Heidelberg: Springer, 2004, Vol.34.

177. Vassilevski Yu. A hybrid domain decomposition method based on aggregation. Numer. Linear Algebra Appl., 2004, Vol. 11; 327-341.

178. Vassilevski Yu. A parallel CG solver based on domain decomposition and non-smooth aggregation. Conjugate gradient algorithms and finite element methods (Proceedings of Int. Conf. 50 years of CG), Berlin-Heidelberg: Springer-Verlag, 2004; 93-102.

179. Widlund O. Capacitance matrix method for Helmholtz's equation on general bounded regions. Lect. Notes Math., 1978, №631; 209-219.

180. Widlund O.B. An extension theorem for finite element space with there applications. N.Y., 1986; 13p. (Techn. Rep., Comput. Sei. Dep., N.Y. Univ., 233)

181. Xu J. Iterative methods by space decomposition and subspace correction. SIAM Review 34, 1992, 4; 581-613.

182. Xu J. The auxiliary space method and optimal multigrid preconditioning techniques for unstructured grids. Computing, 1996, 56; 215-235.

183. Xu J., Zou J. Some nonoverlapping domain decomposition methods. SIAM Review 1998, 40; 857-914.

184. Yserentant H. On the multi-level splitting of finite element space. Numer. Math., 1986, 49; 379-412.

185. Yserentant H. Two preconditioners based on the multi-level splitting of finite element space. Numer. Math., 1990, 58; 163-184.

186. Zhang X. Multilevel Schwarz methods. Numer. Math., 1992, 63(4); 521-539.-256

187. Список основных публикаций

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

189. Центральные и рецензируемые издания

190. Мацокин A.M., Непомнящих C.B. Метод альтернирования Шварца в подпространствах. Изв. Высш. Учебных заведений. Математика, 1985, Т.29, №10; 61-66.

191. Мацокин A.M., Непомнящих C.B. Метод фиктивного пространства и операторы продолжения. Ж. Выч. Мат. и Мат. Физ., 1993, Т.ЗЗ, №1; 5268.

192. Мацокин A.M., Непомнящих C.B., Ткачев Ю.А., Юнг М. Методы многоуровневого переобусавливания на локально модифицированных сетках. Сиб. журн. вычисл. матем., Новосибирск: СО РАН., 2006, Т. 9, №4; 403-421.

193. Непомнящих C.B. Метод разбиения пространства для эллиптических проблем со скачками коэффициентов в узких полосах. Докл. РАН, Мат., 1992, Т.45, №2; 488-491.

194. Numer. Math, 2007, Vol.15, №4; 245-276.

195. Beuchler S, Nepomnyashchikh S.V. Overlapping Additive Schwarz Preconditioners for Elliptic Problems with Degenerate Locally Anisotropic Coefficients. SIAM J. on Numer. Anal, 2007, Vol.45, Is. 6; 2321-2344.

196. Globisch G, Nepomnyaschikh S.V. The hierarchical preconditioning having unstructured grids. Computing J, 1998, №61; 307-330.

197. Haase G, Langer U, Meyer A. and Nepomnyashchikh S.V. Hierarchical extension and local multigrid methods in domain decomposition preconditions. East-West J. Numer. Math, 1994, Vol.2, №3; 173-193.

198. Haase G, Nepomnyashchikh S.V. Explicit extension operators on hierarchical grids. East-West J. Numer. Math, 1997, Vol.5, №4; 231-348.

199. Jung M, Nepomnyaschikh S.V. Variable additive preconditioning procedures. Computing J, 1999, №62; 109-128.

200. Kwak D.Y, Nepomnyaschikh S.V., Pyo H.C. Domain decomposition for model heterogeneous anisotropic problems. Numer. Lin. Alg. Appl, 2003, №10; 129-157.

201. Matsokin A.M., Nepomnyaschikh S.V. On using the bordering method for solving systems of mesh equations. Soviet J. Numer. Anal, and Math. Modell., 1989, Vol. 4, № 6; 487-492.

202. Nepomnyaschikh S.V. On the application of the bordering method to the mixed boundary value problem for elliptic equations and on mesh norms in

203. W2/2(S). Soviet J. Numer. Anal, and Math. Modell., 1989, Vol. 4, №6; 493506.

204. Nepomnyaschikh S.V. Schwarz alternating method for solving the singular Neumann problem. Soviet J. Numer. Anal, and Math. Modell., 1990, Vol. 5, №6; 69-78.

205. Nepomnyaschikh S.V. Method of splitting into subspaces for solving elliptic boundary-value problems in complex-form domains. Soviet J. Numer. Anal, and Math. Modell., 1991, Vol. 6, №2; 151-168.

206. Nepomnyaschikh S.V. Mesh theorems of traces, normalizations of function traces and their inversion. Soviet J. Numer. Anal, and Math. Modell., 1991, Vol. 6, №3; 223-242.

207. Nepomnyaschikh S.V. Fictitious space method on unstructured meshes. East-West J. Numer. Math., 1995, Vol.3, №1; 71-79.-259221. Nepomnyaschikh, E.-J. Park. Preconditioning for Heterogeneous Problems. In

208. Domain Decomposition Methods in Science and Engineering, Lecture Notesin Comput. Sei. and Engin. (LNCSE), Springer, 2004, Vol.40; 415-422.

209. Nepomnyashchikh S.V. Domain decomposition methods. Radon Series Comput. Appl. Math., 2007, 1; 89-159.1. Другие научные издания

210. Мацокин A.M., Непомнящих C.B. О сходимости метода альтернирования Шварца по подобластям без налегания. Методы аппроксимации и интерполяции, Новосибирск, 1981; 85-97.

211. Мацокин A.M., Непомнящих C.B. Применение окаймления при решении систем сеточных уравнений. Вычислительные алгоритмы в задачах мат. физики, Новосибирск, 1983; 99-109.

212. Мацокин A.M., Непомнящих C.B. Нормы в пространстве следов сеточных функций. Новосибирск, 1987; 33с. (Препринт, ВЦ СО АН СССР, 737).

213. Непомнящих C.B. О применении метода окаймления к смешанной краевой задаче для эллиптических уравнений и о сеточных нормах в

214. WP(S). Новосибирск, 1984; 24с. (Препринт, ВЦ СО АН СССР, 106).

215. Непомнящих С.В. Метод разложения на подпространства для решенйя эллиптических краевых задач в областях сложной формы. Численные методы и мат. моделирование, Новосибирск, 1990; 128-161.

216. Непомнящих С.В. Сеточные теоремы о следах, нормировка следов сеточных функций и их обращение. Новосибирск, 1991; 25с. (Препринт ВЦ СО АН СССР, 930).

217. Matsokin A.M., Nepomnyashchikh S.V. The fictitious component method using extension operators. Siberian J. Comput. Math., 1, 1992, N1; 31-45.

218. Nepomnyashchikh S.V. Domain decomposition method for elliptic problems with discontinuous coefficients. Domain Decomposition for PDEs, R. Glowinski et al., eds., SIAM Publ., 1990; 242-252.

219. Nepomnyashchikh S.V. Decomposition and fictitious domain methods for elliptic boundary value problems. Domain Decomposition for PDEs, R. Glowinski et al., eds., SIAM Publ., 1992; 62-71.

220. Nepomnyashchikh S.V. Domain decomposition method for the elliptic problem with jumps in the coefficients in thin strips. Siberian J. Comput. Math, 1992, Vol.1, №2; 23-34.

221. Nepomnyashchikh S.Y. Domain decomposition methods for singular elliptic problems. Problems of Math. Physics, R. Jentsch at al., eds., Teubner Publ., 1994; 120-129.

222. Nepomnyaschikh S.V. Domain decomposition for elliptic problems with large condition numbers. Domain Decomposition for PDEs, D.E. Keyes and J. Xu, eds., Contemporary Math., 1994, Vol. 180; 75-85.

223. Nepomnyaschikh S.V. Domain decomposition and multilevel techniques for preconditioning operators. Technische Univ. Chemnitz-Zwickau, 1995. (Preprint, SPC 95-30).

224. Nepomnyaschikh S.V. Optimal multilevel extension operators. Technische Univ. Chemnitz-Zwickau, 1995. (Preprint, SPC 95-3).

225. Nepomnyaschikh S.V. Preconditioning operators on unstructured grids. Seventh Copper Mountain Conference on Multigrid Methods, N.D. Melson etal., eds., N3339 in NASA Conference Publication, 1996; 607-621.

226. Nepomnyaschikh S.V. Domain decomposition and multilevel techniques for preconditioning operators. Domain Decomposition Methods for Sciences and Engineering, R. Glowinski et al., eds., John Wiley & Sons, Ltd, 1997; 193203.

227. Nepomnyaschikh S.V. Domain decomposition for isotropic and anisotropic elliptic problems. Technische Univ. Chemnitz-Zwickau, 1999. (Preprint, SFB393/99-16).

228. Nepomnyaschikh S.V. Preconditioning operators for elliptic problems with bad parameters. Domain Decomposition Methods for Sciences and Engineering, C.-H. Lai et al., eds., Published by Domain Decomposition Press, Bergen, 1999; 81-87.

229. Nepomnyashchikh S.V. Finite element trace theorems for parameter dependent Sobolev space. Numer. Math, and Adv. Appl., World Scientific: Singapore, 2000; 31-41.

230. Nepomnyaschikh S.V., Park E.-J., Cho S. Domain Decomposition Preconditioning for Elliptic Problems with Jumps in Coefficients, Linz, Austria, 2005; 29 p. (RICAM-Report, 2005-22).

231. Nepomnyaschikh S.V., Scherer K. Multilevel preconditioners for bilinear finite elements approximations of diffusion problems. Bonn: Uni Bonn, 2008; 9 p. (Preprint, SFB611/08-384).