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

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

РГБ ОЛ

2 т т

Гилева Лидия Викторовна

КАСКАДНЫЕ ИТЕРАЦИОННЫЕ АЛГОРИТМЫ В МЕТОЛЕ КОНЕЧНЫХ ЭЛЕМЕНТОВ ДЛЯ ЭЛЛИПТИЧЕСКИХ КРАЕВЫХ ЗАДАЧ

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

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

Работа выполнена в Институте вычислительного моделирования СО РАН.

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

Шайдуров Владимир Викторович

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

профессор Носков Михаил Валерьянович; кандидат физико-математических наук, профессор Распопов Виталий Евгеньевич

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

и математической геофизики СО РАН, г. Новосибирск

Защита состоится " ^^" СО2000 г. в ^ часов на заседании диссертационного совета К 064.61.01 в Красноярском государственном университете по адресу 660041, г. Красноярск, пр. Свободный, 79.

С диссертацией можно ознакомиться в библиотеке Красноярского государственного университета.

Автореферат разослан ЛЛС&Я/Ъ^ 2000 г.

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

р , - , . Красноярск 2000

А / О о /А У / — 2, Л 2

Е.К. Лейнартас

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы

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

' Цель работы

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

Методы исследования

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

оценками.

Научная новизна

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

Практическая значимость

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

Апробация работы

Материалы диссертации докладывались и обсуждались на следующих конференциях и семинарах:

1) на семинаре отдела вычислительной математики Института вычислительного моделирования СО РАН;

2) на 15 Межреспубликанской конференции по численным методам решения задач теории упругости и пластичности, Новосибирск, 1997;

3) на мегкдународной конференции "Математические модели и методы их исследования", Красноярск, 1997;

4) на Третьем сибирском конгрессе по прикладной и индустриальной математике, посвященном памяти C.J1. Соболева, Новосибирск, 1998.

Публикации

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

Структура и объем работы

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

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

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

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

В разделе 1.1 рассматривается задача Дирихле для слабонслинейного эллиптического уравнения

Лы = /(!,«) в П, (1)

и = 0 на Г, (2)

где Пей2- ограниченный выпуклый многоугольник с границей Г, правая часть (1) зависит только от решения, но не от его производных. Функция /{х,ь) принадлежит С(£2 х Л), и для нее выполняются следующие ограничения:

о < < с\ Ух е п. Уг е л,

ОУ

d2f( .

<с2 VxeQ, VvEfi.

Задача (1) - (2) имеет единственной решение в И'22(П).

Рассмотрим обобщенную формулировку задачи (1) - (2):

о

найти и € И^Л), такую что

C{u,v) — 0 VveWj(fi),

где C(u,v) = j(Vu • Vt; 4- j(x, u)v) dx. n

Эта задача также однозначно разрешима.

Для построения системы Бубнова-Галеркина на области О строится последовательность согласованных вложенных триангуляций 77, г = 0,1,... ,L В качестве новых узлов более мелкой триангуляции берутся середины сторон треугольников. Обозначим через Л,- .максимальную из длин сторон треугольников триангуляции 77, через П,- - множество вершин этой триангуляции, лежащих внутри Ü. а через щ число точек множества Каждому узлу у 6 Л; поставим в соответствие базисную функцию равную 1 в узле у, 0 во всех остальных узлах г той триангуляции и линейную на каждом треугольнике из 77- Их линейную оболочку обозначим через Нг.

Рассмотрим дискретную задачу:

найти, ¡i 6 Неудовлетворяющую равенству

£(:,-. г) = 0 Vre (3)

Эта задача имеет единственной решение, для которого справедлива оценка

IIй -¿illl.fi < с'ММко-

Мы используем обозначения норм ]| • (|0п, |) • Ц^д, || • [¡2,п, для соболевских пространств ¿г(^), И^'(П) и соответственно.

Задача (3) нелинейна. Для ее линеаризации используем метод Ньютона с "замороженной производной". Обозначим через щ приближенное решение системы (3) на нулевом уровне (с триангуляцией То) и будем считать, что оно удовлетворяет оценке

||"0 - ¿olli.fi < с3^||и||2,п- (4)

На г-том уровне получаем следующую задачу: найти 0; £ Н\ такую что

А(й,-,«) = (з(й,--1),и)п Уьен\ (5)

9/,

где С\ (£',,«) = / • Уи + -д~{х, йх:

{д{щ_г),у)п - I + йх,

и

й,-_1 приближенное решение, полученное на (г — 1)-ом уровне. Решение этой линейной задачи также определяется однозначно.

Задача (5) эквивалентна системе линейных алгебраических уравнений

Ьт = и (6)

размерности щ с симметричной положительно определенной матрицей

Обозначим через М{ векторное пространство размерности щ со скалярным произведением (•,•); и введем линейный оператор интерполяции /, : М-, —► М1+1. Введем также нормы

Р1П=А(0,5)1/2 V« 6ИЭД,

Нсль каскадного алгоритма состоит в решении задачи (6) при -I. для чего последовательно решаются вспомогательные задачи при г = 0.1,... ,1-1.

Каскадный алгоритм:

1. г/о определяется как приближенное решение задачи (3) при г = 0:

2. для / = 1.2____,I цикл

(<)

{ 2.1. ?/■, = /¡_]И,_1;

2.2. = «•,-,/,-);}.

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

Метод простых итераций [1щ итераций на уровне {); Процедура 5',(£;,и'г-, /,-);

3. у0 = «/¡;

4. для к — 1,... , т,- цикл 1 о тг(2к - 1)

2(ЬгТТ); (8)

Ук = Ук-1 - - /г)

5. полагаем 5,- = .

Здесь А| - верхняя оценка собственных значений А матрицы

На первом этапе каскадного алгоритма дискретная задача решается прямым или итерационным методом с довольно высокой точностью (см. (4)). Поскольку число уравнений дискретной системы невелико, решение «о может быть получено достаточно экономично.

Сходимость каскадного алгоритма характеризуется следующими теоремами.

Теорема 1. Пусть 1 < а < 2 и пусть реализован каскадный алгоритм с гп{ итерациями метода сопряженных градиентов или метода простых итераций (8) на каждом уровне г - 1,... ,где ггц - наименьшее целое число, удовлетворяющее неравенству

т( > то,2а{1-'].

Предположим, что

И20 < с4Л, < 1, с4> 1. Тогда для приближенного решения г/, справедлива оценка

III-/ - и/|||/ < с5Л/.

Теорема 2. При выполнении условий Теоремы 1 для кусочно-линейного восполнения и, 6 Н1 решения щ справедлива оценка

¡1« - "¡Цп < оЛ-

Число арифметических операций оценивается сверху величиной

5/ < (г7?п; + С8)П/ с константами, не зависящими от ш, и п

В разделе 1.2 рассматривается задача со знакопеременным спектром 2

- £ д^а^и) + аи = / в ГI, (9)

ы = 0 на Г, (10)

где коэффициенты и правая часть (9) удовлетворяю!' условиям д^£Ья(П), q> 2, г,; = 1,2; а 12 = а21 в А;

(И)

!=1 ¿=1 / 6 Lai«)-

Коэффициент а удовлетворяет условию

а е С(П) (12)

и может принимать отрицательные значения.

Будем считать, что оператор задачи (9)—(10) невырожден и она имеет единственное решение в W|(ii).

Перейдем к обобщенной формулировке задачи (9) - (10):

о

найти и EW\(fl), такую что C(u,v) = {f,v)a VveW\{il), где £(и, v) = / I У" ацд,ид{v + auv dx,

L W=1 I

(f,v)n = / Jvdx. n

Эта задача также имеет единственное решение.

о

На подпространстве Н' С W\(Sl) сформулируем дискретную задачу: найти Vj б Н', удовлетворяющую уравнению £(vi,v) = (f,v) a VveH\ (13)

Она эквивалентна системе линейных алгебраических уравнений

Ш = /г, (14)

матрица которой не является положительно определенной.

Введем положительную константу во, такую что а > -ад на Q. Тогда билинейная форма

£i(u,v) = £(u,v) + а0 ■ (и, v)q

о

положительно определена в IV^il).

Введем диагональную матрицу масс Д с элементами

А:{х) = Т ^ гпеая(Т), х £ О;. 7'е7;, гэг

Номера строки и столбца матрицы Д, содержащих элемент Д,(х'), согласованы с номером узла х в О,.

о

Определим следующие нормы для функций у из И7^^)

и векторов V из пространства Л/,- размерности тг,-

И, = (г^Д«)1'2,

и

где .4, = Ьг + Д.

Доказано, что при достаточно малом /г,- задача (13) имеет единственное решение, которое удовлетворяет оценке

1« - Ык < ^.Ц/Ио,!).

Для решения последовательности задач (14) при г = 0.... применим каскадный алгори тм. Каскадный алгоритм:

1. щ = Ьд1 /0;

2. для ¿ = 1,2,... ,1 цикл

{ 2.1. ии - и~уЩ-\]

Уо = щ; (15)

2.2. для к = 1,2,... ,тп; цикл

Ук = у к-1 - (¿¿2/А-1 - /<■);

2.3. и, = т/т,.;}.

На каждом уровне г итерационные параметры Тк~\ выбираются на основании соотношения между верхней и нижней оценками собственных чисел Л спектральной задачи

Ьг'-р = \Diip.

Для них справедлива оценка

- 1 < Л, < \-г < ... < Хщ < А* < едкг2. (16)

Введем параметр

и рассмотрим два случая.

1). Пусть 7,- > 1. Тогда положим

1 _2 тт(2к — 1)

^ = лгсм .....(18)

2). Пусть 7; < 1. Положим Ь* = тах{1, А-} и возьмем

1 , л(2к — 1) , , тк_х = - соз-1 ——(, к = 1,... , т,-/2, 19

Ь* 2(тп,- + 1)

1 . 7г(2к — т; — 1) , .

гц^-соб"1-^-к = тп{ 2 + 1,... , тп{, 20

Ц 2 (т,- + 1)

считая тгц четным.

Зафиксируем г и обозначим через ¿о = Щ ~ ич ошибку начального приближения для задачи (14), а через ¿1 =г;г —и; - ошибку аппроксимации итерационного процесса в (15). Рассмотрим линейный "итерационный" оператор (¿т. : 6о ~> ¿1- Он представляет собой матричный полином вида

т,-

¿=1

с коэффициентами Тк~\ из (18) либо (19)-(20).

Лемма 1. Пусть матрицы Ь{ и Д симметричны и матрица Д положительно определена. Тогда

< рМЬ Уше-Ц-.

где р = 1п_1(1 + у/2) < 1.14 . Кроме того, для параметров (18) справедливо неравенство

/ А, \ 1/2

а для параметров (19)-(20) неравенство

Ь' \1/2,

Число итераций в каскадном алгоритме выбирается по следующему правилу. Положим пц — т и выберем ш; как наименьшие целые, удовлетворяющие неравенствам

пц > трМ'^'-М, г = 1,2...../-1. (21)

после чего вычислим значения параметра 7,. г = 1.2____,1. Из (16), (17)

и (21) вытекает, что 7,- возрастает с ростом г. Поэтому при достаточно малом 1ц на мелких сетках 7; > 1, а неравенства 7,- < 1 имеют место

ю

на сетках с номерами от 1 до некоторого к < /. Тогда выберем ш,- как наименьшие целые, удовлетворяющие соотношениям

тщ=ТГц, г = 1,... 1, (22)

1Щ > /с2Ш.22('-!), 1 = 1,..., Л. (23)

Доказан следующий результат.

Теорема 3. Пусть

Л о < его/,™« 1«о- г;о|о < сцЛ/+7/^о, г<?е 7 = Р < 0.19. Пусть также число итераций ггц в каскадном алгоритме выбирается из условий (21)-(23). Тогда для решения щ, полученного каскадным алгоритмом, справедлива оценка

И«/ - М1/ < йгЧ/ 1|о,о-

Разность между кусочно-линейным восполнением и, € Н1 вектора и; и точным решением оценивается как

Щи - «|||!п < С13?1|||/||о,П-Число арифметических операций в каскадном алгоритме оценивается сверху величиной

< {слЛо&\пк + сх5)тпп{.

В разделе 1.3 рассматривается задача Дирихле для системы уравнений Ла.ме плоской теории упругости

- рДи - (А + р) gradd¡vu = / в Г2, (24)

и =0 на Г, (25)

где А,/л > 0 - коэффициенты Ламе, и — (щ,щ)Т - искомая вектор-функция перемещений, / = (/ь/2)г- вектор-функция массовых сил. Задача (24) - (25) имеет единственное решение в (^(П)) •

Обычным образом перейдем к обобщенной формулировке задачи (24)

- (25):

о

найти и £ (И^й))2, удовлетворяющую равенству

где билинейная форма С симметрична и положительно определена. Эта задача также однозначно разрешима. Сформулируем задачу Галеркина

найти г»,- £ (//')2, такую что

£(«,-.») = (/.«)п (26)

и

Она эквивалентна системе 2п,- линейных алгебраических уравнений

ЬМ = Я (27)

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

и векторов из пространства М1 размерности 2гс,

цкц,- = О^/)1'2, кед,

согласовав нумерацию элементов вектора и матрицы с номерами узлов х 6 П,-.

Задача (26) имеет единственное решение, для которого справедлива оценка

III" -«¡1п < С17Й,-||/||о,П-Лля решения последовательности задач (27) используется каскадный алгоритм вида (7) с методом сопряженных градиентов или методом простых итераций (8). Число итераций выбирается как наименьшее целое, удовлетворяющее неравенству

+ + (28)

Для приближенного решения [/;, полученного каскадным алгоритмом, доказана следующая теорема.

Теорема 4. Ошибка каскадного алгоритма для задачи (24)-(2о) оценивается как

Для кусочно-линейного восполнения щ € {Н1)2 вектора [7/ справедлива оценка

1К -и|1п< Л/ (с" + 2^тт)||/,кв-

Число арифметических операций оценивается сверху величиной

5; < (с18ш/ + С19)пг.

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

В разделе 2.1 рассматривается задача Дирихле на выпуклом ограниченном многограннике П С с границей Г з

- £ д^ъ&и) + <ш = / в П, (29)

•'¿=1

ы = 0 на Г. (30)

Коэффициенты и правая часть уравнении удовлетворяют условиям 3,-Оу-6 г,) = 1,2,3;

= на П, = 1,2,3;

/< ЕС,2 < Е чЫз < V Е "а П V*; € Л, и > > 0;

1=1 ¿,¿=1 1-1

а,/еь2(0), а > 0 на П.

При этих условиях задача (29) (30) однозначно разрешима в И^П).

Рассмотрим обобщенную формулировку задачи (29) - (30):

о

найти и Е И^П), такую что

£(и, «) = (/,«)п Уи (31)

где С(и,ъ) = / ^ а^д^идр + аии ¿а;. (32)

п /

Для построения дискретной системы осуществляется пространственная триангуляция многогранника Г2. С использованием традиционной процедуры дробления тетраэдров строится последовательность согласованных вложенных пространственных триангуляций 71, г = 0,1,... ,/. В качестве новых узлов более мелкой триангуляции берутся середины ребер тетраэдров. В итоге при дроблении тетраэдра исходной триангуляции 7о получается 3 вида тетраэдров с равными объемами, но разными длинами ребер. Обозначим через /г,- максимальную из длин ребер тетраэдров триангуляции 77- через Г2,- - множество всех вершин тетраэдров этой триангуляции, лежащих внутри П, а через щ - число точек множества П,-.

Аналогично двумерному случаю каждому узлу у 6 Яг поставим в соответствие кусочно -линейную базисную функцию а линейную оболочку этих функций обозначим через II1.

Дискретная задача эквивалентна системе линейных алгебраических уравнений

1,1), = /,- (33)

на векторном пространстве М,- размерности щ с симметричной положительно определенной матрицей.

Введем нормы

Р1Ь = £(*>, ¿)1/2, ¿е* 1И1, = ((..у'£,г.)1/2, V 6 М;.

Используя для решения последовательности задач (33) каскадный алгоритм с методом сопряженных градиентов или методом простых итераций (8) и выбирая число итераций из условия (28), получим приближенное решение (/¡. Для него доказан следующий результат.

Теорема 5. Ошибка каскадного алгоритма для задачи (29) - (31) оценивается как

Для кусочно-линейного восполнения щ € Н1 вектора щ справедлива оценка

Яй'-«Вп<Л/(с21 + 2~^) ИЯкп-

Число арифметических операций оценивается сверху величиной

S, < {С221П1 + с23)гг/.

В разделе 2.2 рассматривается алгоритм разбиения на тетраэдры трехмерной ограниченной области с гладкой криволинейной границей Г.

Предположим, что задана исходная грубая триангуляция %, удовлетворяющая следующим свойствам при i — 0.

1. Триангуляция 77 представляет собой множество замкнутых невырожденных тетраэдров, объединение которых является многогранником, имеющим только треугольные грани с вершинами на Г.

2. Триангуляция 77 является согласованной.

3. Максимальная длина ребер триангуляции 77, обозначаемая Л,, удовлетворяет неравенству

h < с2 2

с константой С22, зависящей от некоторых свойств области Q.

4. В каждом тетраэдре из 77 хотя бы одна вершина лежит внутри области fi.

Для дробления тетраэдров применяется процедура Div. Если тетраэдр имеет не более одной вершины на Г, то в качестве новых узлов более мелкой триангуляции выбираются середины его ребер. Тогда процедура Div на каждом уровне деления исходного тетраэдра дает тетраэдры только трех разных типов.

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

За показатель качества триангуляции 77 принимается критерий

х(77) = h\j min meas(T).

Доказан следующий результат.

Теорема 6. Пусть П С - ограниченная область с границей Г класса С2 и исходная согласованная триангуляция 7о обладает свойствами 1-4. Тогда из неравенства

< с'2з < 00

при достаточно малом /¡о в результате применения процедуры ко всем тетраэдрам из То получается согласованная триангуляция Т\, обладающая свойствами 1-4 и показателем качества

< с2з < сю, где с23 < 16^3■

В свою очередь, последнее неравенство при достаточно малом гарантирует свойства 1-4 согласованных триангуляции 77 уровня г = 2,... ,/, полученных применением процедуры для которых показатель качества удовлетворяет неравенству

77) < 0Т23, где у/2 < а < 2.

В разделе 2.3 рассматривается задача (29)-(31) на ограниченной выпуклой области П с границей Г класса С2. Предполагается, что Г является объединением нескольких кусков поверхностей Г,-, г = 1,... ,/с, заданных параметрически:

.7 = 1,2,3; и,г £ Я.

Для пространственной триангуляции области П применяется алгоритм, изложенный в разделе 2.2. В результате получается последовательность измельчающихся триангуляции 77, г = 0,1, — ,1. Объединение тетраэдров триангуляции 77 представляет собой вписанный в многогранник.

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

о

Для каждого узла у £ построим базисную функцию ^ бИ^КП), равную 1 в узле у, 0 во всех остальных узлах, линейную на каждом тетраэдре из 7/ и продолженную нулем на остальной части П. Базисные функции на уровне г строятся но следующему правилу. Возьмем произвольный узел у £ П,. Из него выходи I несколько ребер тетраэдров триангуляции 77,

Г)

в серединах которых лежат узлы </),... ,ут триангуляции 77+1- Положим

1 т 1 ;=1

На тетраэдрах из 77, имеющих не более одной вершины на Г, базисные функции линейны. В приграничной части множества й, которая не содержится в многограннике, образованном совокупностью всех тетраэдров из 7(, базисные функции равны нулю. На остальной части множества О базисные функции <р1 определены не на тетраэдрах из 71, а на многогранниках, которые образованы совокупностью тетраэдров из 71, полученных при дроблении тетраэдров из 77, и не совпадают с исходными тетраэдрами. Эти базисные функции склеены из кусочков функций, линейных только на каждом тетраэдре из 71.

На подпространстве 1Р, представляющем собой линейную оболочку функций р', сформулируем дискретную задачу:

найти г>1 Е Л\ такую что

С(щ)ь) = ({^ (34)

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

Лемма 2. Решение задачи (34) существует и единственно. Для него справедлива оценка

Дискретная задача эквивалентна системе п,- линейных алгебраических уравнений

= /; (35)

с симметричной положительно определенной матрицей.

Для приближенного решения щ задачи (35) при г = /, полученною каскадным алгоритмом (7) с методом сопряженных градиентов или методом простых итераций (8) и числом итераций из (28), доказана следующая теорема

Теорема 7. Ошибка каскадного алгоритма оценивается как Для восполнения й/ £ Н1 вектора гц справедлива оценка

II"; - "1п < Ь (с24 + ИЛЬ-

ш

Число арифметических операций оценивается сверху величиной

5/ < (с2йт/ + с-27)п1.

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

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

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

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

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

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

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

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

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

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

Работа поддержана грантом 98-01-00704 Российского Фонда Фундаментальных исследований и грантом 1/72342 Фонда Фольксвагена (УоП^-луадепзийип^).

ПУБЛИКАЦИИ 110 ТЕМЕ ДИССЕРТАЦИИ

1. Л.В.Гилева, В.В.Шайдуров. Каскадный многосеточный алгоритм в методе конечных элементов для плоской задачи теории упругости // Препринт No.15.BLl СО РАН. - Красноярск, - 1996. - 15 с.

2. Л.В.Гилева, В.В.Шайдуров. Каскадный многосеточный алгоритм в методе конечных элементов для плоской задачи теории упругости. // Деп. в ВИНИТИ, No. 3776-В96. - 1996. - 16 с.

3. L.V.Gilyova, V.V.Shaidurov. A cascadic multigrid algorithm in the finite element method for the plane elasticity problem // Preprint No.296 Weierstrass-Institut fur Angewandte Analysis und Stochastik. - Berlin, - 1996. - 13 p.

4. L.V.Gilyova, V.V.Shaidurov. A cascadic multigrid algorithm in the finite element method for the plane elasticity problem. // East-West J. Numer. Math. - 1997. - Vol.5, No.l. - P. 143-156.

5. Л.В.Гилева, В.В.Шайдуров. Каскадный многосеточный алгоритм в методе конечных элементов для задачи теории упругости // Мсж-дунар. конф. "Математические модели и методы их исследования", тез. докл. Красноярск: Крас. гос. ун-т. - 1997. - С.61-62.

6. Л.В.Гилева. Каскадный многосеточный алгоритм в методе конечных элементов для трехмерной задачи Дирихле // Сиб. журнал вычислительной математики. 1998. - T.I, No.3. - С.217-226.

7. Л.В.Гилева, В.В.Шайдуров. Каскадный многосеточный алгоритм в методе конечных элементов для эллиптической задачи со знакопеременным спектром // Третий сибирский конгресс по прикладной и индустриальной математике. Тез. докл., часть 2. - Новосибирск: Изд-во Института математики СО РАН. - 1998. - С.10.

8. L.V.Gilyova, V.V.Shaidurov. A cascadic multigrid algorithm in the finite element method for an indefinite-sign elliptic problem // 5-th European Multigrid Conference. Special Topics and Applications. - Stuttgart: Institut fur Computeranwendungen der Universität Stuttgart. 1998.

P. 74-89.

9. L.V.Gilyova, V.V.Shaidurov. A cascade algorithm for solving a discrete analogue of weakly nonlinear elliptic equation // Technical Report IOKOMOOl-98, Dresden: Technische Universität Dresden, Fakultaf. fur Mathematik und Naturwissenschaften."- 1998. - 12 p.

10. L.V.Gilyova, V.V.Shaidurov. A cascade algorithm for solving a discrete analogue of weakly nonlinear elliptic equation. // Russ. J. Numer. Anal. Math. Modelling.' 1999. - Vol.14, No.l. - P.59-69.

Введение

Глава 1. Решение двумерных задач

1.1. Решение слабонелинейной задачи

1.1.1. Формулировка дифференциальной задачи

1.1.2. Формулировка дискретной задачи

1.1.3. Формулировка каскадного алгоритма

1.1.4. Вспомогательные оценки

1.1.5. Доказательство сходимости каскадного алгоритма

1.2. Решение задачи со знакопеременным спектром

1.2.1. Формулировка дифференциальной задачи

1.2.2. Формулировка дискретной задачи

1.2.3. Формулировка каскадного алгоритма

1.2.4. Вспомогательный оператор

1.2.5. Доказательство сходимости каскадного алгоритма

1.2.6. Оптимизация числа итераций

1.3. Решение задачи плоской теории упругости

1.3.1. Формулировка дифференциальной задачи

1.3.2. Формулировка дискретной задачи

1.3.3. Формулировка каскадного алгоритма

1.3.4. Доказательство сходимости каскадного алгоритма

1.3.5. Оптимизация числа итераций

Глава 2. Решение трехмерной задачи

2.1. Каскадный алгоритм для задачи в многограннике

2.1.1. Формулировка дифференциальной задачи

2.1.2. Формулировка дискретной задачи

2.1.3. Формулировка каскадного алгоритма

2.1.4. Доказательство сходимости каскадного алгоритма

2.1.5. Оптимизация числа итераций

2.2. Обоснование асимптотической устойчивости алгоритма триангуляции трехмерной области

2.2.1. Алгоритм дробления триангуляции

2.2.2. Критерии качества триангуляции

2.2.3. Оценка изменения качества триангуляции в процессе дробления

2.3. Каскадный алгоритм для задачи в области с гладкой криволинейной границей

2.3.1. Формулировка дифференциальной задачи

2.3.2. Формулировка дискретной задачи

2.3.3. Вспомогательный результат

2.3.4. Сходимость решения системы Галеркина к точному решению

2.3.5. Оценка собственных чисел матрицы дискретной системы

2.3.6. Сходимость каскадного алгоритма

Глава 3. Вопросы реализации и численные эксперименты

3.1. Вопросы реализации каскадного алгоритма

3.1.1. Итерационные методы в каскадном алгоритме

3.1.2. Трехслойный полуитерационный метод

3.2. Численные эксперименты

3.2.1. Предварительные замечания

3.2.2. Уравнение Пуассона

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

Теория метода конечных элементов для краевых задач изложена в монографиях Ф.Сьярле [1], Л.А.Оганесяна и Л.А.Руховца [2], Г.И.Марчука и В.И.Агошкова [3], Г.Стренга и Дж.Фикса [4], Ж.П.Обэна [5], В.Г.Корнеева [6], В.В.Шайдурова [7] и других.

История метода конечных элементов восходит к работам В.Ритца и отечественных математиков И.Г.Бубнова и Б.Г.Галеркина. Основы метода конечных элементов были заложены в статье Р.Куранта [8], где впервые были использованы кусочно-линейные функции в вариационных методах. Современная теория метода конечных элементов базируется на теории обобщенных решений краевых задач, на теории аппроксимации функций и численных методах алгебры.

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

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

1) вариационная (обобщенная) формулировка задачи;

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

3) решение системы алгебраических уравнений.

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

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

Эффективность метода конечных элементов существенно зависит от метода решения системы алгебраических уравнений, которая обычно является разреженной и имеет большую размерность. Однако вопрос о выборе методов решения получаемых систем в литературе по конечным элементам в течение ряда лет практически не освещался. Это объясняется тем, что системы метода конечных элементов аналогичны по свойствам и структуре конечно-разностным системам, для которых имеется большой набор прямых и итерационных методов решения, достаточно полно представленных в книге А.А.Самарского и Е.С.Николаева [9].

В последнее время одним из эффективных итерационных методов решения систем алгебраических уравнений метода конечных элементов стал многосеточный метод. Впервые его идею предложил Р.П.Федоренко в работе [10], затем в [11] он обосновал сходимость многосеточного метода для конечно-разностного аналога уравнения Пуассона в квадрате. Н.С.Бахвалов в [12] доказал оптимальность метода по числу арифметических операций для достижения точности, согласованной с порядком сходимости. В итоге по асимптотическим оценкам эффективности метод опередил известные алгоритмы, но логическая сложность и громоздкое математическое обоснование на некоторое время завуалировали его достоинства.

На определенном этапе развития метода конечных элементов привлечение нового математического аппарата и программных реализаций существенно снизило трудоемкость алгоритма и упростило его обоснование. Поэтому в конце 70-х годов начинается рост числа публикаций по многосеточным методам. Отметим монографии В.Хакбуша [13] и В.В.Шайдурова [7], [31].

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

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

Впервые каскадный алгоритм с использованием метода сопряженных градиентов в качестве итерационного сглаживателя для решения эллиптических уравнений был представлен П.Дойфльхардом в статьях [14] и [15], где продемонстрирована высокая скорость сходимости этого алгоритма с вычислительной точки зрения. В работах В.В.Шайдурова [16], [17] была доказана оптимальная вычислительная сложность этого алгоритма для двумерной задачи Дирихле для эллиптического уравнения второго порядка с гладким решением. Затем в работах В.В.Шайдурова [18], Ф.А.Борнемана [19], Ф.А.Борнемана и П.Дойфльхарда [32], В.В.Шайдурова и Л.Тобиска [33] оптимальная сложность была установлена для эллиптического уравнения, решение которого является недостаточно гладким ввиду наличия у области углов больше п. В [33] в результате специального сгущения триангуляции получен такой же порядок аппроксимации, как и для задач с гладким решением.

Кроме того, в работах [19] и [32] установлены оценки скорости сходимости других итерационных сглаживателей в двух- и трехмерных краевых задачах для эллиптического уравнения второго порядка. В двумерном случае из проанализированных в этих работах сглаживателей только метод сопряженных градиентов дал оптимальную арифметическую сложность. Из работ В.В.Шайдурова [16] и [17] эта оптимальность следует также для метода простой итерации со специальными чебышевскими итерационными параметрами. В трехмерном случае помимо них еще несколько сглаживателей обеспечивают оптимальную сложность.

Сходимость каскадного алгоритма для некоторых нелинейных эллиптических уравнений доказана в работах Г.Тиммерман [34] и В.В.Шайду-рова и Г.Тиммерман [35].

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

При использовании алгоритмов на последовательности сеток важным вопросом является "вложенность" конечных элементов, т.е. возможность выражения базисных функций на редкой сетке в виде линейной комбинации небольшого числа базисных функций на более мелкой сетке. Такое свойство выполняется для многоугольных областей и дает простые правила интерполяции и проектирования функций с одной сетки на другую. В случае областей с криволинейной границей потребность аппроксимации границы при мельчении триангуляции приводит к тому, что обычные кусочно-линейные элементы вблизи границы не будут обладать свойством вложенности. В.В.Шайдуровым в [7, §5.3] предложен способ построения базисных функций в двумерной области с гладкой криволинейной границей, позволяющий сохранить это свойство, а в [20] доказано, что при использовании таких базисных функций каскадный алгоритм сохраняет свойство оптимальности. В диссертации этот подход обобщается для трехмерной области с гладкой криволинейной границей.

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

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

В разделе 1.1 рассматривается задача Дирихле для слабонелинейного эллиптического уравнения второго порядка

Аи = /(х,и) в П, (1) = 0 на Г, (2) где и С Я2 - ограниченный выпуклый многоугольник с границей Г, правая часть (1) зависит только от решения, но не от его производных. Функция принадлежит С(С1 х Я), и для нее выполняются следующие ограничения: дГ о < ~^-(х,у) < С1 Ухеп, Уг>еЯ, оь ж, и) с2 УяеП, Уьеп. дь2

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

В итоге на каждой из сеток с номерами г = 0,. ,/ получим систему линейных алгебраических уравнений

Ьм = ¡1 (3) с симметричной положительно определенной матрицей Ь{ размером щхщ, где щ - число внутренних узлов г-той сетки. Для их последовательного решения используется каскадный итерационный алгоритм.

Цель каскадного алгоритма состоит-в решении задачи (3) при i = I, для чего решаются вспомогательные задачи при i = 0,. ,1 — 1. После того, как получено решение на самой грубой сетке, задача (3) при г = 1,. решается итерационным методом (методом сопряженных градиентов или методом простых итераций) с использованием в качестве начального приближения интерполяции приближенного решения с предыдущей сетки.

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

В разделе 1.2 рассматривается задача Дирихле 2 Y1 di(aijdju) + аи = f в Q, (4) i¿= 1 и = 0 на Г, (5) где коэффициенты и правая часть (4) удовлетворяют условиям д{ац £ Lq(О), q > 2, i,j = 1,2; ап = «2i в Í);

2 2 2 мЕЙ < £ < »Ий в П Vfc G R, I/ > ц > 0; i=l i,j=1 г=1 е L2(Q).

Коэффициент а удовлетворяет условию а Е С (О) и может принимать отрицательные значения, т.е. оператор задачи (4)-(5) не является положительно определенным, при этом предполагается, что он невырожден.

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

LjVi = /¿, (б) г = 0,. ,/, матрицы которых не являются положительно определенными.

Доказано, что при достаточно мелком начальном разбиении кусочно-линейное восполнение решения задачи (6) аппроксимирует решение задачи (4)-(5) в энергетической норме с порядком где - максимальная из длин сторон треугольников г-той триангуляции, г = 0,. , /.

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

Ьг<р = ХБцр, где Д— диагональная матрица масс. Для собственных чисел имеет место оценка

- 1 < Л < с3АГ2- (?)

На нижних уровнях каскадного алгоритма с номерами от 1 до некоторого к < I реализуется неоптимальный с вычислительной точки зрения итерационный метод, требующий большего числа итераций для получения желаемой точности. На верхних уровнях, когда достаточно мало, на основании оценки (7) становится возможным использовать итерационный метод со специальными чебышевскими параметрами. В результате удается существенно понизить число итераций на самых мелких сетках.

Доказано, что погрешность каскадного алгоритма имеет порядок а число арифметических операций оценивается сверху величиной 0(щ( 1 +

В разделе 1.3 рассматривается задача Дирихле для системы уравнений

Ламе плоской теории упругости

Дм — (Л + ц) grad сНу и = / в П, и = О на Г, где Л, /х > 0 — коэффициенты Ламе, и = (и\,и2)т, / = (/ь/2)т.

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

Во второй главе рассматривается трехмерная задача Дирихле для эллиптического уравнения

В разделе 2.1 задача (8)-(9) рассматривается на ограниченном выпуклом многограннике. Для построения последовательности вложенных пространственных триангуляций используется алгоритм дробления тетраэдров, изложенный в [7]. Дискретная задача формируется с использованием кусочно-линейных базисных функций на тетраэдрах. Доказана оптимальная вычислительная сложность каскадного алгоритма с использованием метода сопряженных градиентов или метода простых итераций.

В разделе 2.2 рассматривается алгоритм разбиения на тетраэдры

8) (9) где коэффициенты и правая часть (8) удовлетворяют условиям е «»¿ = 1,2,3; о>{\ — о>]'г в Г2, — 1,2,3; а,/е12М, а > 0 в О. трехмерной ограниченной области с гладкой криволинейной границей. Он является трехмерным обобщением известного алгоритма дробления двумерных ограниченных областей с криволинейной границей [7]. Алгоритм начинается с некоторой исходной триангуляции с небольшим числом тетраэдров. Последующие триангуляции с уменьшающимся диаметром тетраэдров строятся рекуррентно путем дробления тетраэдров предыдущего уровня на 8 частей и корректировки расположения приграничных вершин для аппроксимации границы.

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

За показатель качества триангуляции 71 принимается критерий х(71) = к] / тттеаз(Т), где - максимальная из длин ребер тетраэдров триангуляции 7^, теав(Т) - объем тетраэдра Т.

Доказано, что если исходная триангуляция является достаточно мелкой и удовлетворяет условию х{Т\) < с4 < ОС, то для последующих триангуляций г = 2,3,. ,I справедливо неравенство 2с4.

В разделе 2.3 рассматривается задача (8)-(9) на ограниченной выпуклой области О с границей Г класса С2. Для построения последовательности измельчающихся пространственных триангуляций используется алгоритм, изложенный в разделе 2.2. В этом случае обычные кусочнолинейные элементы не будут обладать свойством вложенности. Поэтому для построения базисных функций используется способ, предложенный В.В.Шайдуровым в [7] для двумерного случая и позволяющий представлять базисные функции на редкой сетке в виде линейной комбинации небольшого числа базисных функций на более мелкой сетке. Такие базисные функции на тетраэдрах, не примыкающих к границе, совпадают с обычными кусочно-линейными, а вблизи границы склеены из кусочков функций, линейных только на каждом тетраэдре самого мелкого разбиения.

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

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

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

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

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

16 чие от последнего является устойчивым с вычислительной точки зрения.

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

Материалы диссертации докладывались и обсуждались на семинарах отдела вычислительной математики Института вычислительного моделирования СО РАН; на 15 Межреспубликанской конференции по численным методам решения задач теории упругости и пластичности, Новосибирск, 1997; на международной конференции "Математические модели и методы их исследования", Красноярск, 1997; на Третьем сибирском конгрессе по прикладной и индустриальной математике, посвященном памяти С.Л.Соболева, Новосибирск, 1998.

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

Работа поддержана грантом 98-01-00704 Российского Фонда Фундаментальных исследований и грантом 1/72342 Фонда Фольксвагена (УоНи-■яга^епвйЛиг^).

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

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

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

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

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

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

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

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

Другое направление для обобщения полученных результатов - исследование применения каскадных алгоритмов для решения задач с недостаточно гладким решением, когда и Е И^14^ а £ (0,1)

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

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

Автор выражает глубокую благодарность своему научному руководителю член-корр. РАН, профессору Владимиру Викторовичу Шайдурову.

Заключение

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

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

3. Г.И.Марчук, В.И.Агошков. Введение в проекционно-сеточные методы.- М.: Наука, 1981.

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

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

6. В.Г.Корнеев. Схемы метода конечных элементов высокого порядка точности. JL: Изд. ЛГУ, 1977.

7. В.В.Шайдуров. Многосеточные методы конечных элементов. М.: Наука, 1989.

8. R.Courant. Variational methods for the solutions of problems of equilibrium and vibrations. // Bull. Amer. Math. Soc., 49, 1943. P. 1 23.

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

10. Р.П.Федоренко. Релаксационный метод решения разностных эллиптических уравнений // ЖВМ и МФ, 1961. - T.I, No.5. - С.922-927. И] Р.П.Федоренко. О скорости сходимости одного итерационного процесса. // ЖВМ и МФ, - 1964. - Т.4, No.5. - С.559-564.

11. Н.С.Бахвалов. О сходимости одного релаксационного метода при естественных ограничениях на эллиптический оператор. // ЖВМ и МФ,- 1966. Т.6, No.5. - С.861-883.

12. W.Hackbush. Multi-Grid Methods and Applications. Berlin, N.Y.: Springer Verlag, 1985.

13. P.Deuflhard. Cascadic conjugate gradient methods for elliptic partial differential equations. I. Algorithm and numerical results. // Technical Report SC 93-23, Berlin: Konrad-Zuse-Zentrum, 1993.

14. P.Deuflhard. Cascadic conjugate gradient methods for elliptic partial differential equations. Algorithm and numerical results. In: Proceedings of 7th International Conference on Domain Decomposition Methods 1993, Providence: AMS, 1994.

15. V.V.Shaidurov. Some estimates of the rate of convergence for the cascadic conjugate-gradient method. // Preprint No.4, Magdeburg: Otto-von-Guericke-Universitat, 1994.

16. V.V.Shaidurov. Some estimates of the rate of convergence for the cascadic conjugate-gradient method. // Computers Math. Applic. 1996. - Vol.31,- No.4/5, P.161-17L

17. V.V.Shaidurov. The convergence of the cascadic conjugate-gradient method under a deficient regularity. // In: Problems and Methods in Mathematical Physics. Stuttgart: Teubner, 1994. P.185-194.

18. F.A.Bornemann. On the convergence of cascadic iterations for elliptic problems. // Preprint SC 94-8, Berlin: Konrad-Zuse-Zentrum, 1994.

19. V.V.Shaidurov. Cascadic algorithm with nested subspaces in domains with curvilinear boundary. // In: Advanced Mathematics: Computations and Applications. Eds.: A.S.Alekseev and N.S.Bakhvalov, Novosibirsk: NCC Publisher - 1995. - P.588-595.

20. В.В.Воеводин, Ю.А.Кузнецов. Матрицы и вычисления. М.: Наука, 1984.

21. Л.А.Оганесян, В.Я.Ривкинд, Л.А.Руховец. Вариационно-разностные методы решения эллиптических уравнений. Часть 2. // Труды семинара "Дифференциальные уравнения и их применение." Вильнюс: ИФН АН ЛитССР, 1974.

22. О.А.Ладыженская, Н.Н.Уральцева. Линейные и квазилинейные уравнения эллиптического типа. М.: Наука, 1973.

23. Г.Фикера. Теоремы существования в теории упругости. М.: Мир, 1974.

24. В.И.Лебедев, С.А.Финогенов. Решение проблемы упорядочения параметров в чебышевских итерационных методах. // ЖВМ и МФ. 1973.- Т.13, No.l. С. 18-33.

25. В.И.Лебедев. Функциональный анализ и вычислительная математика.- М.: Изд-во ОВМ АН СССР, 1987.

26. Х.Гаевский, Л.Грёгер, К.Захариас. Нелинейные операторные уравнения и операторные дифференциальные уравнения. М.: Мир, 1978.

27. Г.Корн, Т.Корн. Справочник по математике для научных работников и инженеров. Изд. 5-е. - М.: Наука, 1984.

28. А.Фокс, М.Пратт. Вычислительная геометрия. М.: Мир, 1982.

29. V.V.Shaidurov. Multigrid methods for finite elements. Dordrecht: Kluwer Academic Publishers, 1995.

30. F.A.Bornemann, P.Deuflhard. The cascadic multigrid method for elliptic problems. // Numer. Math. 75, No.2., 1996. - P.135-152.

31. V.V.Shaidurov, L.Tobiska. The convergence of the cascadic conjugate-gradient method applied to elliptic problems in domains with re-entrant corners. // Preprint No.37, Magdeburg: Otto-von-Guericke-Universität,1977.

32. G.Timmermann. A cascadic algorithm for the solution of a weakly nonlinear problem. // Technical Report IOKOMO-lO-97, Dresden: Technische Universität Dresden, Fakultät für Mathematik und Naturwissensch- 1997.

33. V.V.Shaidurov, G.Timmermann. A cascadic algorithm for the solution of nonlinear signindefinite problems. // Technical Report ЮКОМО-09-98, Dresden: Technische Universität Dresden, Fakultät für Mathematik und Naturwissenschaften. 1998.

34. Л.В.Гилева, В.В.Шайдуров. Каскадный многосеточный алг оритм в методе конечных элементов для плоской задачи теории упругости // Препринт No. 15 ВЦ СО РАН. Красноярск, - 1996. - 15 с.

35. Л.В.Гилева, В.В.Шайдуров. Каскадный многосеточный алгоритм в методе конечных элементов для плоской задачи теории упругости. // Деп. в ВИНИТИ, No. 3776-В96. 1996. - 16 с.

36. L.V.Gilyova, V.V.Shaidurov. A cascadic multigrid algorithm in the finite element method for the plane elasticity problem // Preprint No.296 Weierstrass-Institut für Angewandte Analysis und Stochastik. Berlin,- 1996. 13 p.

37. L.V.Gilyova, V.V.Shaidurov. A cascadic multigrid algorithm in the finite element method for the plane elasticity problem. // East-West J. Numer. Math. 1997. - Vol.5, No.l. - P.143-156.

38. Л.В.Гилева, В.В.Шайдуров. Каскадный многосеточный алгоритм в методе конечных элементов для задачи теории упругости // Меж-дунар. конф. "Математические модели и методы их исследования", тез. докл. Красноярск: Крас. гос. ун-т. - 1997. - С.61-62.

39. Каскадный многосеточный алгоритм в методе конечных элементов для трехмерной задачи Дирихле // Сиб. журнал вычислительной математики. 1998. - T.I, No.3. - С.217-226.

40. L.V.Gilyova, V.V.Shaidurov. A cascade algorithm for solving a discrete analogue of weakly nonlinear elliptic equation. // Russ. J. Numer. Anal. Math. Modelling. 1999. - Vol.14, No.l. - P.59-69.