Итерационные методы решения эллиптическихзадач сложного вида с использаванием обращения лапласиана на простых сетках тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Механико-математический факультет р ' кафедра вычислительной математики

На правах рукописи УДК 519.6

РЯБИНИН ОлегВикторович_______;____

|

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

I

СПЕЦИАЛЬНОСТЬ 01.01.07 ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА

АВТОРЕФЕРАТ

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

•Лоскна, 1995

Работа выполнена- на кафедре вычислительной математики механико—математического факультета МГУ им. М.В.ЛомоносоВа.

Научный руководитель: Академик РАН Н.С.Бахвалов.

Официальные оппоненты: д.ф. —м.н. А.А.Злотник, к.ф.—м.н. Ю.В.Василевский.

Ведущая организация: Ярославский Государственный Университет.

Защита состоится "£ " {.¿Г,! заседании специализированного Сове; Институте Вычислительной Математики (119034, Москва, ул. Рылеева, 29)

95г. в часов на та К 003.47.01 в РАН.

С диссертацией можно ознакомиться в ИВМ РАН по адресу] Москва, ул. Рылеева, 29

Автореферат разослан " УЛ/^^А 1995г.

Ученый секретарь Специализированного Совета

к.ф. — м.н.

С.А.Финогенов.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ.; •:.: ; л

-■ Г ' ..(

актуальность темы: В последнее время при -численном ; .

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

I ' ■ ■ ■• -

формы для эллиптических уравнений второго"/ порядка [ -

применяются методы, которые требуют; ■ ^решать ¡ ,

аналогичные задачи в областях более простой формы.],

Новая структура вычислительных машин влечет за «обой

совершенствование математической базы для решения < |

сложных задач на параллельных ЭВМ. Например, .

осреднение процессов ^ периодических средам требует

решать задачи математической физики'-' с/ большим-разбросом коэффициентов. При численном решении

I

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

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

Конструирование' - итерационных эллиптических задач4'с большим

Цель работы. 1. методов для . решения

разбросом коэффициентов.

2. Конструирование лереобуславливателей (оптимальных по своим характеристикам) для сеточных задач со сгущениями.

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

1. Построение прямого метода решения сеточных задач со сгущениями.

5. Развитие математического аппарата исследования итерационных методов.

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

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

■;мфоп. Сформулирован метод возвращения к иодпрост ранетку на основе внутренних итераций и • • •••• ' ' чс ••••ость их числа от основных параметров .-.'.• методы решения некоторых задач с

оольшп: р--; Просом коэффициентов.

Апробация работы. Осног..... ,/л .тпты

диссертации докладывались на:

1. научно —исследовательском семинару г.ас] едры вычислительной математики механико —матсматиче :кого факультета МГУ им. М.В.Ломоносова.

2. научно—исследовательском семинаре инстлтута вычислительной математики РАН.

Публикации. По теме диссертации опубликована одна работа: Рябинин О.В. Итерационный метод решения вариационно —разностных аналогов эллиптических задач с большим разбросом коэффициентов//Доклады академии наук, 1994г. т. 339 № 4 с.

Структура диссертации. Диссертация состоит из введения, четырех глав и списка литературы из 93 наименований. Общий объем работы 94 страницы.

СОДЕРЖАНИЕ РАБОТЫ

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

Первая глава содержит необходимые элементы функционального анализа, теории разностных схем и матричного анализа. Здесь вводятся основные определения и понятия, требующиеся в диссертации. В параграфе 1.1. рассматриваются пространства Соболева, теоремы продолжения с сохранением класса, а также оснс способы продолжения. . ^ол« часто исиолы»у-т-:1 1г:к

практической реализации. Параграф 1.2. посвящен различным видам триангуляций и способам задания конечноэлементных пространств М^С) и основных

О I

подпространств \Л^(С,Го), ^^(С). Здесь определяются законы сгущения триангуляции к множеству. Будем говорить, что регулярная триангуляция (т.е. такая, что

отношение радиуса вписанной окружности к радиусу описанной для всех треугольников из Г^(С) принадлежит

отрезку 1], £=сопз1>0) сгущается к множеству Б с в по закону £(р), если существуют константы ср сз, <1 > 0 такие, что для всех треугольников е е Ть(С), содержащихся в

d — окресности множества S справедливо неравенство cif(p)<R(e)<C2Í(p), R(e) —радиус описанной окружности,

p = dist(S,e)— фзшкция евклидова расстояния между двумя множествами. Скалярные произведения на W^fG) ( . , . )o,h и ( • < • )l,h вводятся как дискретные аналоги скалярных произведений в L2 и W21 .

В параграфе 1.3. приводится способ задания вариационно — разностных аналогов эллиптических операторов. Всякий (линейный) оператор А : Wh(G,ro)->W¿(G,ro), задаваемый соотношением вида:

(Au,v)0,h = ^ajj Diu Djv dX + ^ buv dX

Gv

Vu,veWh(G,r0)

будем называть вариационно—разностным аналогом эллиптического оператора (ау = ауТ, ЬеЬ ^(С}))). Аналогично вводится понятие для операторов на торе. На ортогональной равномерной триангуляции прямоугольников

матрица А относительно естественного базиса соааада^т с матрицей разностного оператора Лапласа .>а сил.;: : топ триангуляции, и поэтому может быть обращена за 0(п 1п п) арифметических операций, п—число узлов сетки.

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

-I *

переобуславливателей в виде ШЗ Я , где В — вариационно—разностный аналог эллиптического оператора на некоторой "хорошей" триангуляции, II — оператор перехода с "хорошей" триангуляции на "плохую", И" — сопряженный оператор к Я относительно скалярных произведений, эквивалентных 1.2 .

Вторая глава посвящена исследованию методов итераций в подпространстве, внутренних итераций и методу возвращения к подпространству. Цель атой главы — постоение новых методов решения задач с большим разбросом коэффициентов. Далее везде £ > 0 — малый параметр. В параграфе 2.1. формулируется и доказывается основная теорема второй главы о методе возвращения к подпространству с помощью внутренних итерационных процедур.

Теорема 2.2.1. Пусть V — гильбертово пространство, ( . , . ) — скалярное произведение, Л( . , . ) — симметричная билинейная форма на V, )Л(х,х) 1 < а^хГ

х

1. Если и — подпространство V, и — а: о ортогональное дополнение относительна ■:.,.), и пр,. . \'еи/{0}

О < ао <Л(у,у) ||у|| < а(,'! Д ааи •и-нстна:

(у,у) = (Х,у) 2(ар+аОЛ(х,у) V

следуют оценки:., Иуой <(а1гдр)(ао+а1)'||хо11 +2а1(а0+а1)"[|Х11| |{у1(1<(14-2а1(ао+;а1)'')(1!хо!{ 4- Ы ), уо , У1 — ортопроекции у на и и и . 2. Пусть Р :: V -* V обладает свойством:' УхеУ (Рх)в =хо и Ц(Рх)1|(й |и.е[0,1) . Тогда существует целый параметр т,

что последовательность {х }, определяемая соотношениями

1. х* = х°, „

2. (у"» = (х"» - 2(а1 + а0) Л(х» , У V е V,

_ П«1 _.ж к

3. х = Р у ; ч .

-I

сходится к нулю со скоростью q геометрической-прогрессии, д е['(а1 —ао)(а1 + ао)~\ 1 ), т = т(^а).

При ^ = 0 Р—ортопроектор, т = 0, q = (al —ао)(а1 + ао), и приведенный итерационный процесс — процесс с возвращением в подпространство.

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

Пусть , \

л.

л,.

-й,

Требуется найти

Л

£ -> О — малый параметр.

Для решения поставленной задачи предлагается итерационный процесс с использованием внутренней процедуры:

Л

' ;'/' ' ' Л

4 ^ ^лх, ^ й'са),

Л

4. и}*А = <и} гЪ^'Т

, р — параметры итерационного процесса. Для погрешности г'=и—и* справедлива оценка ( при оптимальных Г, и

если области Ло , Л, и -/2^ таковы, что выполняется предположение 2.2.1. На каждом шаге итерационного процесса требуется решать задачу вида

!»<«" ъж* - км

Во второй части параграфа рассматривается метод фиктивных областей для первой краевой задачи на дискретном случае. - | С

Актуальность данного вопроса связана с "выходом" из подпространства Б случае произвольной квазиравномерной , триангуляции. Пусть Л = Лс ОЛ^ . На

определяется«?рператор А£ :

Ал

В —некоторый оператор, спектрально — эквивалентный А

---...--------; 1

Справедливо следующее следствие к теореме 2.2.1:

Лемма 2.2.3. Существуют параметры т е итерационный процесс 1.- Хв»0.

2.

3.

V

N. Ъ, такие, что

......--------;

4. = ^

сходится к решению задачи А£и = Г со скоростью сходимости, не зависящей от Ь и £ ; т=^т(е ,Ь), О —оператор продолжения из Л0 в -0-л с сохранением нормы. Пункт 3 итерационного процесса является реализацией оператора Р из теоремы 2.1 Л.и

Для задачи А. и = ( справедлива также лемма 2.2.4,

£ • 1 основанная на методе разложения на подпространства:

Лемма 2.2.4. Существуют константы ^ , ^ > 0 такие, что при

О

любой функции уеШ}^)

(Справедливость Лемм 2.2.3 и 2.2.1 , ом .и я-.. ,.р;. численным экспериментом в одномерном случае). В третьей главе исследуется структура матриц жесть ;саи вариационно—разностных аналогов эллиптических зад; а на триангуляциях со сгущениями и развивается л . разложения на подпространства для пострс .... эффективных переобуславливателей для таких задач. В параграфе 3.1. рдссматривается случай триангуляции со сгущением к точке по некоторому закону сгушения Г( (з ). Переобуславливатель О для матрицы А жесткости исходной задачи представляется в виде

Б"'= 010г( 21 ^ 0^1^)020?. где Оь 02 - операторы

I «ч

пере/одА с одной триангуляции на другую, Кооператоры разложения на подпространства, — разностные операторы Лапласа на ортогональных равномерных трианга.\ацн:е прял, и о " ; ',><а

формулируется алгоритм построения от-рспора < и

)/ -] у

доказывается оценка спектра оператора А г 13 Д^п зависимости от закона сгущения. Основная идея разложения на подпространства заключается и следуй, а Сначала разбиваете;! обл.е.ть на неаог! • < подоо\астей (кольч фориы), в каждой на .а;

три." ' "тция т • .лправномерноп и р«чулнрпо1

Затем . разложение функции и устраивается по числу подобластей на конечно —элементные функции и так, что каждая из них отражает общее поведение функции и в i — ой подобласти,( в * дополнении к исходной области и цостоянна (в каждой компоненте связности). Операторы QlQ2Ri как раз и обеспечивают данное разложение.

Основным результатом настоящего параграфа является

-' ' ' ■ I' Я 1

доказательство трго, что обусловленность оператора ADA (отношение верхней границы спектра к нижней) не превосходит

i.^ (4 ед

V*.

<x - tons

где величины,'стоящие; в фигурных скобках зависят только

от закона ; сгущения: р —число подобластей, Hj, —

• • ' . I

характерный размер триангуляции в i -4 ой подобласти,

^И(Пг) — площадь минимального прямоугольника, содержащего

I—ую подобласть/; V^' — характерна^ ширина I —ой

подобласти как-'кольца. Для простейшего варианта

л,

закона сгущения f(f)=h g+h d = const (пример 3.3.1.); поэтому и для всех более медленных; законов сгущения

d = const; ч.кромел этого, арифметическая сложность

" vi ■ " ' | -г а

вычисления оператора Р на функции есть 0(h In h ), h —

i • I

параметр триангуляции. Если параллельные операции счи —

! | -i

тать за одну, то.арифметическая1 сложность будет 0(h In h).

Параграф 3.2. посвящен одному быстрому прямому методу обращения вариационно — разностного аналога А оператора

Лапласа первой краевой задачи на триангуляции со'

сгущенйем к части границы. . ;

1 а' " ' ''1''

Покроем квадрат П=(0,1) ортогональной равномерной!

| -п. . * ,

сеткой с шагом Ь= 1/Ы=2 по обеим осям координат и зададимся натуральным т—параметром сгущения к левой стороне квадрата. При' 1=0,..'.,т—1 каждой квадрат исходной сетки, находящийся между прямым'й х=2 "и. ■ х~2 разделим на 4 равных квадрата; квадраты исходной сетки, находящиеся слева от прямой х=2 разделим па .4 равных квадрата. Ъ • =2 Ь. Через Т ^(П)" обозначим . триангуляцию П, полученную делением. . каждого

элементарного квадрата конечной сетки на два равных треугольника диагональю с положительным тангенсом угла наклона к оси Ох. (ТЬ(П) является ..регулярной несогласованной триангуляцией). Результатом данного параграфа является описание метода обращения матрицы оператора А, построенного по _ ТЬ(П); матрица рассматривается относительно естественного базиса.

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

"77"' ■

представить следующим образом. После (быстрого) дискретного преобразования Фурье вдоль вертикального направления система Аи = 1 распадается на N + т — 1 независимых подсистем с матрицами, графы которых являются деревьями. | Вершины графа соответствуют неизвестным, а ребро графа, соединяющее 1 и j вершины — (!,]) — му ненулевому элементу (симметричной) матрицы. При определенной нумерации неизвестных в каждой строке матрицы слева от диагонального элемента находится

ровно один ненулевой элемент, а функция целого расстояния от диагонального до ненулевого левого — монотонная, В результате такой нумерации матрица . обращается методом Гаусса; прямой ход следует начинать снизу вверх, поскольку в этом случае не происходит заполнения элементов матрицы. На каждом шаге метода используется не более шести операций арифметики. После обратного преобразования Фурье получается точное решение уравнения Au=f.

Предложенный метод позволяет конструировать 'ффективпые перообуславливатели для (монотонных) законов сгушения к части границы. При наличии в графе нескольких циклов предлагается в начале использовать метод декомпозиции для исключения "циклических" переменных, после чего граф матрицы_становится деревом. В параграфе 3.3. обобщаются результаты пораграфов 3 1! и 3.2. на другие типы сгущений триангуляции, отличные от рассмотренных в параграфах 3.1. и 3.2: — сгущение к линиям в двумерном случае;

— сгущение к линиям в общем случае dim > 2;

— сгущение к множеству ненулевой меры dim=2. Методы решения таких задач основаны на композиции методов параграфов 3.1. и 3.2, а также на методе наложения на подпространства для случая конечных (11 = 2,3) разбиений области.

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

В_параграфе АЛ. рассматривается метод переобус —

v:вливания для эллиптических задач на квазиравномерных чиангу/пииях прямоугольника. Здесь приводится отличное

•>пксг ■••.!■: н .мн'-рачурс доказательство следующей: i * юрома Пусть "1 v. (П), Т^(П) — две квазиравномерные триангуляции прямоугольника П Rf W^jll), W^fn) — соответствующие конечно —элементные пространства со скалярными произведениями (.,.)0и (.,.)„, эквивалентными Ц, , A: WMn) Wh(n), В: \К(П) -» \^'(П) - вариационно -разностные аналоги оператора Лапласа по соответствующим тпиапгуляциям. Тогда существует оператор перехода

О: й^(П) такой, что операторы А* и ЬйЕ + ОВ О*

спектрально эквивалентны с константами эквивалентности, не зависящими от п- тасла узлов Т^П); при этом число ненулевых элементов матрицы оператора О относительно естественного базиса есть О(п).

Доказательство этой теоремы построено на двух фактах:

1. Если Та. (П), Т^ (П) —ортогональные равномерные триангуляции П, а каждый треугольник из Ть(П) является объединением нескольких треугольников из Т ^ (П), то справедливость теоремы следует из теории многосеточных методов или проверяется непосредственным гармоническим анализом. При этом О — оператор линейной интерполяции с Тц(П) на ВД.

- . 2. Если в условиях теоремы дополнительно в каждый элементарный треугольник из Т^(П) попадает не более одного узла триангуляции Тк(П), то (Лемма 4.1.1) существует оператор перехода О такой, что операторы Л" и С'В О спектрально эквивалентны с константами эквивалентности,

V-

не зависящими от 1т и, кроме того, СЮ = Е — тождественный оператор на Ш (П).

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

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

2. Предложен метод построения переобуславливателей для эллиптических задач на триангуляциях со сгущениями.

3. Построен прямой метод обращения вариационно — разностного аналога оператора Лапласа на триангуляции со сгущением к части границы.

4. Предложен .-ггод -. - • •• графами - Д'Т"