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

ПО

1 О 'Российская академия наук

институт вычислительной математики

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

удк 519.6

ИЛЬЯШ Юрий Иванович

АЛГЕБРАИЧЕСКИЕ МНОГОСЕТОЧНЫЕ МЕТОДЫ И ИХ ПРИЛОЖЕНИЯ К МОДЕЛЬНЫМ ЗАДАЧАМ ВЫЧИСЛИТЕЛЬНОЙ ГИДРОДИНАМИКИ

Специальность 01.01.07 Вычислительная математика

автореферат

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

Москва 1996

Работа выполнена в Институте вычислительной математики РАН

Научный руководитель — доктор физико-математических наук КУЗНЕЦОВ Ю. А.

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

КОБЕЛЬКОВ Г. М. кандидат физико-математических наук КАПОРИН И. Е.

Ведущая организация — Вычислительный центр СО РАН, г. Красноярск.

Защита состоится " 6> гл. 1997 г. в часов на

заседании специализированного совета Д 003.47.01 в Институте вычи-. слительной математики РАН по адресу:

117333, Москва, ул. Губкина, 8.

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

Автореферат разослан " 1''I- " 199^" г.

Ученый секретарь

специализированного совета кандидат физико математических наук С. А. ФИНОГЕНОВ

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

Актуальность темы. Развитие высокоэффективных итерационных етодов решения систем линейных алгебраических уравнений, возникаю-;их в результате аппроксимации эллиптических уравнений конечно-злностными и конечно-элементными методами, остаётся одной из наибо-ее важных задач вычислительной математики. Особенно это относится к ».дачам в трёхмерных областях, при практическом решении которых воз-икают системы линейных алгебраических уравнений с сотнями тысяч и аже миллионами неизвестных. Среди множества проблем, возникающих ри построении итерационных методов, не последнюю роль играют такие, ак зависимость вычислительных затрат для получения решения с задан-ой точностью от числа неизвестных, от поведения коэффициентов диффе-энциальной задачи, от структуры области, граничных условий, от сети, на которой производилась аппроксимация задачи. Также, в связи с :ё более расширяющимся применением многопроцессорных компьютеров, ри построении итерационных методов необходимо учитывать эффектив-эсть их реализации на вычислительных системах с различными типами рхитектуры. С теоретической точки зрения одними из наиболее эффектных среди итерационных методов являются многосеточные методы. Од-эй из самых важных проблем в теории многосеточных методов является эказательство их сходимости и получение оценок скорости сходимости.

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

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

Построение алгебраических многосеточных методов, предназначенных пя решения эллиптических задач в трёхмерных областях, на параллель-ых ЭВМ.

Построение многосеточных методов для решения задач, аппроксимирован-

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

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

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

• на семинарах лаборатории вычислительной математики ИВМ РАН, семинарах в университете г. Юваскюла (Финляндия), в университете г. Аугс-бурга (Германия), в университете г. Штуттгарта (Германия) и на семинаре в GMD (г. Санкт-Августин, Германия);

• 3-м международном симпозиуме по численному анализу (г. Москва, 1992);

• 1-м Российско-Финском симпозиуме по численному анализу (г. Юваскюла. Финляндия, 1992);

• совместной Российско-Голландской рабочей встрече по прикладной математике (г. Москва, 1993);

• 10-м Франко-Российско-Итальянском совместном симпозиуме по вычислительной математике и приложениям (г. Москва, 1993);

• совместном Франко-Российском семинаре по вычислительной математике (г. Москва, 1994);

• 4-ой международной конференции по численному анализу (Москва, 1995):

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

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

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

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

В первой главе рассматривается алгебраический многосеточный мето;

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

Пусть Q — Ц'£>Р С R2; 4'°' Пи/]0' = 0, i ф j — единичные квадраты; , С дО., Г0 = Г0 ф 0, Г! = dfi \ Г0; V = {г; : v € Я^П), ®|Гв = 0}. Рассмо-жм задачу: для данного / € Ь2{р) найти и £ V:

JQa{x)VuVvdn = JQfvdn, W€V, (1)

1,есь а(х) = а; = const > 0, х е Vi. Построим в Q иерархическую эследовательность сеток I = 0, ..., L, с шагами hi = t~l. Определим эеугольные сетки Гразбивая все от; ячеек wf сетки на два треуголь-яка. Пусть Ул(0 пространство функций Куранта, ассоциированное с сеткой Обозначим через А[ матрицу, соответствующую конечно-элементной шроксимации (1) на сетке rj,''; А = Ai. Разобьём узлы сетки Г^ на 3 >уппы: 1) узлы в вершинах ячеек 2) узлы на рёбрах ячеек

I узлы внутри ячеек При этом А представляется в виде:

Мц Аи 0 ^ А = А21 А22 А2з

\ О Л32 А33

(2)

1е Ац — диагональная, а А22 и А33 — блочно-диагональные матрицы с токами порядка (£ — 1) и (4 — I)2, соответственно. Определим матрицу Вц ри помощи соотношения:

<3)

1е и1* и ■и'1 — следы кусочно-линейных восполнений векторов и и V на рёбра

, a\L ^ = а(х), х £ Матрица Вц представима в виде:

, U.j —■ IX^tbJ, и, ^ и/J . 1VXCIX р*

А

о _ I "И "12 \

Б22 — блочно-диагональная матрица с блоками порядка (t — 1). Введём атрицы 5ц = Ац - Ai2B22A2i, В33 = А33 и В:

( Вп 0 0 \

В = F

О В22 О

О 0 £33

III 0 о \

В22 Ао 1 /22 о

) \ 0 #33 А32 /зз /

(4)

[емма 1.1.3 Собственные числа матрицы В 1А принадлежат отрезку > Атах], где Атах = 3 в случае ¡ = 2 « Атах = 3 + \/2 б случае £ = 3.

[емма 1.1.4 Матрица Вц' = Вц с точностью до множителя совпадает матрицей жёсткости Лх-1 для сетки

В[? = (1/4)А£_Ь

Лемма 1.1.4 открывает возможность для построения многосеточного пере-обуславливателя. Выберем в > 1, положим Б;-1 = Bf1 и для I — 2, ..., Ь определим матрицы

А = р'Г [

т=

в{'} © ви @ Я, (5)

-1

/1? - п -

(6)

где гр — чебышевские итерационные параметры.

Лемма 1.1.5 Справедлива оценка: сопс! В~[1Аь < VI, где г>1 определяется при помощи следующих рекуррентных соотношений:

Щ ~ КплХ1 Щ = Ап

1 = 2,

При некоторых значениях $ нЬ последовательность I оо ограничена сверху, при этом сопс! В^А ограниченно константой 1/5>4, не зависящей от Ь. Нетрудно получить:

1^2,2 = 3 + 2^3 и 6.5, 1/3,2 = 1 + « 3.3,

изл = ^ (4(3 + ^2)1/2(6 + л/2) + 12л/2 + 21) я 5.9. Итог содержанию § 1.1 подводит следующая теорема:

Теорема 1.1 В случае последовательности сеток с шагами, отличающимися в два раза (Ь = 2) при в = 2, 3, а в случае последовательности сеток с шагами, отличающимися в три раза (Ь — 3) при в = 3 число арифметических операций, требуемых для решения системы линейных уравнений с матрицей А при помощи метода сопряжённых градиентов с алгебраическим многосеточным переобуславливателем В с из (5) с точностък е, оценивается сверху величиной сЫ\пе~х, где с — некоторая константа, зависящая от числа квадратов, из которых составлена область, не не зависящая от размерности задачи N, значений коэффициента а в П ь граничных условий.

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

В § 1.2 многосеточный метод из § 1.1 используется при построение итерационного метода для решения системы уравнений Стокса. Пусть П С И2 — односвязная область с кусочно-гладкой границей дС1. Рассмотрим систему уравнений Стокса в области П

( -Дгй + Ур = 0 ,7)

I -сНу ш = 0 ^

' W А С •ш '

. р. — СТ 0 . . Р . . 9 .

це ь> = [и, у] — скорость, р — давление. На границе области ЭГЗ поставим словия Дирихле на скорость. Аппроксимация задачи (7) при помощи ме-ода конечных разностей на "разнесённых сетках" приводит к системе ли-ейных уравнений

(8)

це А = Ат > 0. Для решения системы (8) используется обобщённый ме-од минимальных итераций Ланцоша с блочно-диагональным переобусла-ливателем

В = В ® 5, (9)

це В ~ А, а 5 ~ СТА~1С. Тот факт, что В может быть эффективным ереобуславливателем для матрицы А обосновывается следующей леммой:

Гемма 1.2.3 Пусть А — А7 > 0, В = ВТ >0, 5 = 5Т > 0 и существуют оложительные, не зависящие от к константы ¿¿1, /¿2, и\, и^, такие, что ыполняются следующие два условия:

1/1(Вги,-ш)< (Лгу, ад) < ^(Бго, ш), (10)

(5р, р) <ЫЗр,р), УрбН"', р±кегС, (И)

де 5 = СТА~1С. Тогда спектр задачи на собственные значения

" V) ' = А В w '

. Р . . Р .

р JL кег С

ринадлежит следующему множеству:

{vi + \Jv\ + 4vifii)/2, (и2 + + 4i/2/ío)/2 (v2 - \¡vf+lv2fio)/2, (i/i - \jv\ + Av\[iy)/2 десь границы каждого из отрезков не зависят от h.

Ü

U И, Н.

[звестно, что аппроксимация задачи (7) на разнесённых сетках удовлетво-яет условию Ладыженской-Бабушки-Брецци. Из этого следует, что если зять S = I, то условие (11) будет выполненным. Матрица В строится при омощи алгебраического многосеточного метода. Для этого в fi строится ерархическая последовательность разнесённых сеток с шагами, отличающимся в три раза (i = 3). На такой последовательности сеток, алгебраи-еский многосеточный переобуславливатель В с 3 внутренними чебышев-кими итерациями (s = 3) будет удовлетворять условию (10).

'еорема 1.2 Обобщённый метод минимальных итераций Ланцоша с блоч-о-диагональным переобуславливателем (9), построенным с исполъзовани-м алгебраического многосеточного метода, является оптимальным в том мысле, что арифметические затраты для решения задачи (8) с точно-тью е есть 0(NIne-1), где N — размерность алгебраической задачи.

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

Вторая глава посвящена изучению усиленного алгебраического многосеточного метода. В § 2.1 рассматривается способ построения усиленного алгебраического многосеточного метода. Рассматривается задача: для данного f £ 1>2(П) найти и G V:

¿(VuVu + cuv) dfl = J f v dii, Vv e V, (12)

где с = с с = const > 0. Конечно-элементная аппроксимация (12) приводит к системе уравнений с матрицей Ас = А + ciM. Введём матрицу Ас = ACti, спектрально эквивалентную матрице Ас: Ас = А + ciD, где диагональная матрица D получается из матрицы М при помощи приёма "концентрации масс". Ас представляется в виде, аналогичном (2); вместо диагональных блоков Ац, в представление Ас входят блоки Д;,с = Ац + ciDu, г = 1,2,3. Определим диагональную матрицу:

Си = Dn ® <№г, (13)

где Si > 0 некоторый параметр. Положим Вц<с = Bn + ciCn, где 23ц из (3). Матрица Вц>с представима в 2 х 2 блочном виде:

6 _ ( АП,с А\2 \

где ¿?22,с — диагональная матрица (рассматриваем только случай t = 2). Введём матрицы Ви,с = Ап,с - А^В^сМь 5зз,с = А33,с и

Вс = [В1и ф В2и Ф Дгз.с] где матрица имеет вид, аналогичный (4).

Лемма 2.1.1 При значении параметра 61 = (с^ + б)/(с£ + 4) в (13), собственные числа матрицы В~1АС принадлежат отрезку [1; Атах], где Атах = ((2+с-£/2)2 —1)/((2+с/,/2)2 —3) < 3, независимо от значения коэффициента сь> 0.

Лемма 2.1.2 Матрица пропорциональна матрице АС1_\; соответствующей аппроксимации оператора Гелъмголъца с коэффициентом прь свободном члене равном С£_ 1 = с^/Ь?^: В[^с = А:,£-ь где

ACIL- 1 = AL-I + cL-iDL-i,

4 + cL 8 + 8C£+4'

^ ^ W, о , 2

h-l = о ,. o„_ ■ 2 ' = + Ci'

Заметим, что С£_1 более чем в два раза превышает коэффициент с/, в исходной задаче (12). Построим многосеточный переобуславливатель. Возьмём р, в > 1 и для I = к + 1, ..., Ь определим матрицы:

Д., = [¿Цс ® ^22,с ® Я,с, (14)

й(') _ £>11,с —

7/-1 А:,/-1

с,к

j=i

/Г'-п^Г'-гГ1»^) ;=i

-1

це rj'' — чебышевские итерационные параметры.

(15)

(16)

1емма 2.1.3 При оптимальном выборе итерационных параметров г]' в 15) и (16) справедлива оценка: сопс! В~\ АС^ < где VI определяется при омощи следующих рекуррентных соотношений:

щ= 3

им = 3

[(¿¿Hi+!)*-( JvUl-l у (у/^+1 )р+(у/щ- 1)р "

/ = к + 2, ..., L,

(17)

десь Vf. = fiklak есть число обусловленности матрицы Лс>ь

[ростую оценку для и^ = cond Acj можно получить, используя лемму Гер-1Горина. Оценивая арифметическую сложность решения системы уравне-ий с матрицей приходим к следующему результату:

Георема 2.1 Пусть номер самого грубого сеточного уровня к выбран в со-тветствии с условием к < 0.6 для s = 2 гыи к < 0.48 для s = 3. Тогда в боих случаях в формуле (16) можно подобрать число внутренних итера-ий р так, что будет выполняться условие Vk+\ S vmaxt где ^max — случае s = 2 и i/maK = 1 + |\/3 в случае s = 3. При этом имеет место ценка cond B~\Ac i < vmax, и число арифметических операций, требуемых ля решения системы с матрицей BCti из (Ц) есть O(N^).

1 конце § 2.1 приведены результаты численных экспериментов с усилен-ым многосеточным переобуславливателем. Эксперименты проводились на [ногопроцессорной вычислительной системе, построенной на базе 33 тран-пыотеров, и подтвердили эффективность использования рассматриваемого [етода на параллельных ЭВМ.

В § 2.2 усиленный многосеточный метод применяется для решения адач о потенциальном и полном потенциальном обтекании. В п.2.2.1 приво-ится постановка задач. Рассматривается стационарное, безвихревое, адиа-атическое течение невязкого идеального газа вокруг тела с границей Si, мегощего форму крыла, в области с внешней границей Г^. Область сделаем цносвязной, построив разрез Si, соединяя точку, соответствующую задней ромке крыла, с Гос. Потенциал поля скоростей у> удовлетворяет уравне-ию:

V(/>(|VH2)V^) = 0, (18)

це р = 1 для несжимаемого газа, и />(|Vy?|2) = (1 --^rlV^j2)^ для сжимае-:ого. Здесь ао и 7 — некоторые константы. На границе тела Si поставим

однородное условие Неймана, а на Гоо поставим неоднородное условие Неймана, обеспечивающее однородность потока на "бесконечности". На Sj потенциал ср может иметь конечный постоянный скачёк ß. Систему уравнений замкнём, добавив условие Кутты-Жуковского. Далее задача (18) формулируется в вариационном виде. Для аппроксимации воспользуемся методом конечных элементов. Для минимизации получившегося квадратичного функционала (линейная задача) используем метод сопряжённых градиентов; для решения нелинейной задачи используем алгоритм типа Полака-Рибьера. Для ускорения сходимости методов используем усиленный алгебраический многосеточный переобуславливатель.

Пусть в Ü имеется иерархическая последовательность треугольных сеток fif, I = 1, ..., L. Нашей целью является построение многосеточного пе-реобуславливателя для матрицы жёсткости Ао, соответствующей сетке Пусть матрица Ас есть конечно-элементный аналог на сетке оператора Гельмгольца — Д + Сх(х), где С = Ci = const > 0, 0 < х(х) < 1 — некоторая кусочно-постоянная функция, постоянная на каждом треугольнике сетки iij. Для матрицы Ас, пользуясь методикой, изложенной в § 2.1, можно построить усиленный многосеточный переобуславливатель. Основное содержание п.2.2.2 посвящено техническим деталям построения такого пере-обуславливателя Bc,s• Процедуру решения системы уравнений с матрицей Bc,s можно представить в виде 3-х кратного V-цикла, при этом сеточному уровню I соответствует матрица, являющаяся аппроксимацией оператора Гельмгольца с коэффициентом при свободном члене C'i ss Ct • 2L~l и для решения системы уравнений, соответствующей самой грубой сетке iij, используется s итераций чебышевского итерационного метода. Показано, что при достаточном числе итераций s (это число зависит от С, L и min,-Л,-, где hi — диаметр г-го треугольника из Q1}; показано, как оценить s) имеет место оценка

cond (Bc]sAc) < v = 3(3 + 2л/5) cot2 <£min, (19)

где фт\п — минимальный угол в триангуляции Qf. Матрица Be,s используется в качестве переобуславливателя для матрицы Aq. По мере возрастания С, спектральные свойства переобуславливателя Bq,s ухудшаются, но в то же время, число итераций s, необходимых для выполнения (19), уменьшается, т. е. цена решения системы уравнений с Bc,s падает.

Отметим следующий факт. Если граница области Q является криволинейной, использование сетки Cl'l для аппроксимации является неприемлемым, т. к. сетка аппроксимирует границу 8Q точно также, как сетка ßf. Для того, чтобы избавится от этого недостатка, определим в П квази-иерархическую последовательность триангуляций fif, I = 1, ..L: П, = Qi', fif строится при помощи обычной процедуры измельчения из Щ Щ строится путем сдвижки на ЗП приграничных узлов сетки iif. Сетка аппроксимирует 0V. со вторым порядком точности. Одним из основных преимуществ использования Bc,s в качестве переобуславливателя является то, что сетка fif может быть взята достаточно мелкой (в экспериментах ~ 100 узлов), при этом даже для небольших значений L (в экспериментах L = 3,4) число обусловленности матрицы, соответствующей fij невелико, следовательно, мало и необходимое для выполнения оценки (19) чи-

rio итераций s. Благодаря тому, что L может быть небольшим, матрица Четкости Â, соответствующая сетке Ûh = fi¿, близка к матрице А, со-гветствующей сетке П'1. Таким образом, для матрицы, полученной при ппроксимации задачи на квази-иерархической сетке, можно использовать ереобуславливатель, построенный на иерархической последовательности эток.

Целью проведения численных экспериментов, результаты которых приедены в п.2.2.3, являлось установление зависимости скорости сходимости ассматриваемых итерационных методов от размерности алгебраических эдач, и от сеток, на которых проводилась аппроксимация. Эксперименты ыли посвящены моделированию двумерного потенциального течения не-¡кимаемой и сжимаемой жидкости вокруг профиля NACA 0012.

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

Рассмотрим задачу о потенциальном обтекании (18) в области О = [\ Е, где П единичный куб, <ЗП = Г^, а Е — эллипсоид, дЕ = Sь На дй оставим условия Неймана: на S\ — однородное, на Гоо — неоднородное, [усть в fi имеется локально адаптированная к 90 сетка Q.h с шагом к = ~£/n, n > 1, L > 1. Конечно-элементный аналог задачи на этой сетке есть истема уравнений с матрицей А. Введём фиктивную область fin, такую то fi С fin и fin = U; £>,-, о/,- П u>j = 0, i ф j, где cu¡ — куб с ребром 21к. В fin остроим кубическую сетку fi^ с шагом h, число узлов которой обозначим ерез N. Рассмотрим NxN матрицу Ас, являющуюся конечно-разностным налогом оператора —Д+С в области fin с граничными условиями Неймана а Шп, а также N х N матрицу Ас — конечно-элементный аналог этого ператора в fi с граничными условиями Неймана на ôfi; Ло = А. Известно, то

Spectrum(P(h*Ác)-lPTAc) С {ci/\\T\\\ с2],

^е ||!Г|| — норма оператора продолжения, а с\, сг > 0 — некоторые констан-ы. Здесь Р — N х N матрица, осуществляющая соответствие между сетами 1]д и tf. Если В является такой матрицей, что Spectrum (B~1h3Ac) С *, (3], тогда Spectrum(РВ~1РтАс) С [сха/ЦГЦ2, со/З]. Далее строится такая атрица В, что а и /3 не зависят от к. Построим в fin иерархическую по-ледовательность кубических сеток fi^, I = 0, ..., L, hi = h, = 2h¡. ¡ведём матрицы Ac,,¡ = (Ai + CihfD¡). Здесь (1 /hf)AcLi конечно-разностный налог на сетке fif/ оператора Гельмгольца —Д + C¿ (C¡ >0 — некото-ый параметр) с граничными условиями Неймана. Разобьём узлы сетки ■il, I > 0, на 4 группы: 1) узлы сетки fin""1', 2) середины рёбер сетки fin"1; ) центры граней ячеек сетки fin"1; 4) центры ячеек сетки fin"1- При этом íq j, аналогично (2), имеет блочно-трёхдиагональный виде диагональными локами а\1-с = Л-j' + CikjDfi' порядка N-^ и внедиагональными блоками

Л*'-'. Введём матрицы

вй = (л&> + б^оЩ, в<<> = (аШ + <Ла?£>й) •

Здесь Л33 и Л22 — диагональные матрицы, определяемые при помощи соотношений

Л 3363 = Азз'ез + 41е4, ф2 = А$е.з + А$е3,

где е; = [1, ..., 1]т £ , а ¿3' и некоторые параметры. Введём матрицу

где ВЦ = А%1С, В $ — а['1с - А^ВЙ]-1 А^, а ^ определяется аналогично (4). Специальным образом подобирая и \ приходим к утверждениям:

Лемма 3.1.1 Собственные числа матрицы В;~1 Ас,; для любого I > 1 и С1 > 0 принадлежат отрезку [1; (7 + л/19)/2].

Лемма 3.1.2 Для любого I > 1 и С[ > 0 имеет место следующее равенство: = £1-1 (А;_ 1 + С(_1^/2_1А_1) = где

24 + \2Cihf + (С,/1?)2

С7|_1 = С,

48 + 80С1Щ + 18 (С, А,2)2 + (С/Л,2)3' 384 + 176С,Ь? + 24 (С; А?)2 + (С/А?)3

(20)

(21)

96 + 48С;А2 -+- 4(С;А2)2

Построим для матрицы Ас1,ь многосеточный переобуславливатель. Пусть р > 0. Для 1 = 1, ..., Ь определим матрицы

в1 = [в[1} © В.)!] © © вЩ я, р ■

= £0АСо,0

г(1) [11

= £1-\Ас1_и1-\

^-¿(^-^ВГДАс,.,,,-!)

-1

г = 2, ..., ь.

Здесь £1 и С; определяются из (20), (21), а — чебышевские итераци-

онные параметры. При этом сопё В;""1 Ас(,/ < где

щ = 1 + 12/(С0й§)

Щ -

+3

1-2

Ь,

где 6 = (7 + >/19)/2.

- и -

[емма 3.1.4 Пусть число итераций р выбрано таким образом, что вы-олняется неравенство < = ^шах- Тогда имеет место следующая

щенка

cond {BZ1Ac,l) < "шах, (22)

езависимо от числа сеточных уровней L + 1.

'з соотношения (21) следует, что величины С/ очень быстро возрастают по ере убывания I, а именно, С/_i ~ AC¡. Быстрое возрастание C¡ приводит тому, что число чебышевских итераций р, необходимое для удовлетво-ения условия леммы 3.1.4 достаточно мало, даже если число уровней в ногосеточном методе невелико (размерность задачи на самой грубой сете большая). Введём обозначение Bq^p = P(hBj)~lPT.

Гемма 3.1.5 Пусть р выбрано таким образом, что выполняется условие еммы 3.1.4 Тогда имеет место следующая оценка

cond (BclpAc) <

С1||Т||2 тах'

де константы С{, со, норма оператора продолжения ||Т|| и г/гаах из (22) не 2висят от шага сетки /г.

^алее в § 3.1 приведены результаты численных экспериментов, которые роводились на 16 процессорном параллельном компьютере СМ-5. Матрица 'с,р использовалась в качестве переобуславливателя для А. Эксперименты одтвердили эффективность использования метода на параллельном ком-ьютере.

В § 3.2 предлагается алгебраический многосеточный метод для ре-гения систем линейных уравнений, получающихся в результате конечно-цементной аппроксимации эллиптических задач в трёхмерных областях, вляющихся объединением тетраэдров. Пусть п = и,-$0) С И3, где = 0 — тетраэдры. Предположим, что

рТ/РТ < С, V*, (23)

де р°" и р]п радиусы описанной вокруг б-0' и вписанной в сфер, а = эnst > 0.

Гемма 3.2.1 Произвольный тетраэдр в^ может быть разбит на 4 ше-граэдра и 1 октаэдр причём таким образом, что

в('К

= 1, ..., 4. Октаэдр полученный из такого разбиения тетраэдра

в свою очередь может быть разбит на 6 октаэдров и 8 те-

храэдров причём таким образом, что ~ у = 1, ..., 6 и

[ользуясь леммой 3.2.1, построим в Г2 иерархическую последовательность эток Г),'', / = 0, ..., Ь. Поставим в соответствие каждому узлу д; сетки Г['', е принадлежащему подмножеству дИ, где поставлены условия Дирихле, усочно-линейнуюфункцию определённую в П итакую что: 1) ^¡'Н?») =

Jy> — узел сетки Г{,''; 2) линейна на каждом тетраэдре б]''; 3) vf непрерывна на каждом октаэдре wj'' и линейна на каждом из 8 тетраэдров, получающихся разбиением о;]'^ тремя плоскостями; 4) <р\'\с^Р) = 1/6, где cj'' — центр масс октаэдраhjf\Положим Hi = span H = Hi. Конечно-

элементная аппроксимация задачи (1) на сетке Г^' с использованием базисных функций пространства Я приводит к системе уравнений с Nl X Ni матрицей А = Ат > 0. Далее в параграфе строится матрица А^, имеющая блочное представление (2), такая что cond[A^]-1.A < (3tv)/2, где va зависит только от а из (23) (если все тетраэдры правильные, va = 1). Для матрицы строится, как и в § 1.1, двухсеточный переобуславливатель вт , имеющий вид (4). Доказывается утверждение:

Лемма 3.2.4 Собственные числа матрицы принадлежат от-

резку [1;

Далее аналогично (5), (6), на основе двухсеточного переобуславливателя строится многосеточный переобуславливатель использующий s вну-

тренних чебышевских итераций.

Лемма 3.2.6 Справедлива оценка сопсЦВ^']-1./!^ < i>l, где i'i определяется при помощи следующих рекуррентных соотношений:

v\ = Щ, П =

1 = 2,..., L, (24)

здесь 1/е = 8 и щи = 10^.

В случае в = 4, исследуя соотношение (24), для всех Ь получаем < иа

где

Лемма 3.2.7 В случае я = 4 справедлива оценка

атсЦВ^]-1!^ < (3^1/^/2 и 29.6^, независимо от числа сеточных уровней Ь.

Исследуя арифметическую сложность решения системы уравнений с

вм.

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

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

иале § 4.1 рассматривается построение сеток с локальным уточнением, бозначим множество квадратов w-0', г = 1, ..., то, из которых состоит , через G'0'. Зафиксируем некоторое L > 0. Предположим, что для недорого I, 0 < I < L построено множество G^K Множество строим тедующим образом: разобьём некоторые (возможно не все) квадраты wf, содящие в Gна 4 квадрата u}f+1\ j = 1, ..., 4. Все новые квадраты

а также квадраты к = 0, ..., /, которые не были разбиты, со-гавят множество С каждым из множеств I = 0, ..., L, ассоции-

^ем сетку Гд'. Треугольную сетку Г^, на которой производится аппрок-шация задачи (1), получаем из сетки Г^ разбиением всех квадратов из на 2 треугольника. Сетка f{,£', вообще говоря, содержит узлы, в ко->рых встречается ситуация "кирпичной кладки". Такие узлы мы назовём эдчинёнными узлами. Число остальных узлов, которые мы назовём ре-глярными, обозначим через Поставим в соответствие каждому из

згулярных узлов сетки Г^' базисную функцию <fii(x), i = 1, ..., хределённую в Q и обладающую следующими свойствами: 1) (fii(x) = О, € Го; 2) ipi(xj) = Sij, где xj — регулярный узел сетки Г^; 3) <р,(х) линей-1 на каждом треугольнике сетки Г)^; 4) <р-,{х) непрерывна в Q. Положим

£ = span {^i}jl<i>; Hi С V. Значение произвольной функции uh G Hi в здчинённом узле выражается через её значения в регулярных узлах. Предлагаем, что сетка такая, что соседями подчинённого узла являются згулярные узлы. Матрицу, соответствующую аппроксимации задачи (1) на :тке fj,£', обозначим через А. Построим при помощи операции ассембли-эвания "локальных" матриц жёсткости, соответствующих квадратам из ножества G^L\ матрицу А = Для построения матрицы, сиектраль-i эквивалентной матрице А, мы будем использовать лемму о фиктивном эостранстве (С. В. Непомнящих):

[емма 4.1.1 Пусть Н, Н — гильбертовы пространства, аАиА — само-тряжённые положительно определённые и непрерывные операторы в про-пранствах Н и Н, и пусть R : Н —> Я — линейный оператор, такой что

(ARv, Rv)Й < cr(Av, v)я, W € Я. (26)

усть также существует оператор Т : Я —> Н, такой что

RTu = й, Уй£ Я, (27)

сТ{АТй, Тй)н < (Ай, й)Й, Уй е Я. (28)

десь Сц и cj некоторые положительные константы. Тогда

сТ{А~1й, й)([ < (RA~lR*u, й)Й < ся(Л_1й, й)Й, Уй € Я.

Эесь R* — оператор, сопряжённый к R относительно скалярных произ-гдений в Н, Н.

В качестве пространства Н возьмём RA<M, а в качестве Н — R'v<i). Введём fj(L) х дг(х) матрицу R = 0] и определим Nх N^ матрицу Т:

(Tu)i = щ, если узел ж,- не является подчинённым (Тй){ = (ыр + йч)/2, если узел х; подчинён узлам хр и хч

Условия (26-28) выполняются, при этом су = 1, сд = 2. Пусть В такая матрица, что condB_1A < i/max. Тогда имеем

cond {RB~lRT)A < (сдг/тах)/сх = 2г/тах.

Далее для матрицы А, на основе результатов § 1.1, строится алгебраический многосеточный переобуславливатель В, для которого vmах = 3+2\/3- Таким образом, скорость сходимости обобщённого метода сопряжённых градиентов для решения системы уравнений с матрицей А с переобуславливателем В = (RB~XRT)~l не будет зависеть от коэффициента а задачи (1) и сетки Построенный метод, вообще говоря, не является оптимальным с точки зрения арифметической сложности, но тем не менее в практически важном случае, когда сетка уточняется к некоторой кривой, арифметическая сложность решения системы уравнений с переобуславливателем не превышает 0(iV<£> log iVW).

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

PT/Pi" <* = const, VTi € П\ (29)

где р°п и р\п — радиусы описанной вокруг Г; и вписанной в TJ окружностей. Обозначим N х N матрицу жёсткости, соответствующую сетке Пл через А. Для построения переобуславливателя В воспользуемся леммой 4.1.1. Построим в П вспомогательную составную сетку Qh, каждая ячейка которой содержит не более 1 узла сетки При помощи операции ассемблирования "локальных" матриц жёсткости, соответствующих всем ячейкам сетки Qh, определим матрицу А порядка N, N < 4N. В качестве пространства Н. возьмем

в качестве "фиктивного" пространства Н возьмём RiV. Существует взаимно-однозначное соответствие между узлами сетки П'1 и подмножеством ячеек сетки Qh, которые мы назовём базовыми ячейками; следовательно, можно построить взаимно-однозначное отображение г узлов ц сетки Пл на "базовые" узлы yi сетки Qh, которые являются, например, левыми нижними узлами базовых ячеек. Используя отображение г, определиу операторы й:Я->ЯиГ:НчН:

Ar~l(Vi)], если yi базовый узел,

з

| £ -и[х,-Jт иначе, х; - вершины Tj : yi G Tj

Лемма 4.2.1 Существуют константы сц > 0 и с? > 0, зависящие толъкс от а, такие что выполняются следующие два неравенства:

(ARv, Rv) < cr(Av, г/), Vv G R^, сТ{АТщТй) < (Ащ й), Vii € R'\

(Л«)Ы=«г(®,) , (Т«)Ы

1СЦИДН0, что условие (27) выполняется. Таким образом получаем, что nd (RA^E^A) ограничено величиной сд/сг, зависящей только от а. Од-iko, задача решения системы уравнений с матрицей А не менее сложна, :м с матрицей Л, но в § 4.1 для матрицы А построен алгебраический мно-сеточный переобуславливатель В. Обозначив В'1 = R,B~lRT, приходим утверждению:

емма 4.2.2 Пусть составная сетка Qh построена на основе регулярной риангуляции Пл. Тогда справедлива следующая оценка

cond В~ХА < —(3 + 2v^), сТ

'е константы сд, су зависят только от а из (29).

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

В Приложении изучается метод декомпозиции области на нестыкую-ихся сетках применительно к задаче о полном потенциальном обтекании, осмотренной в § 2.2. Отличительной чертой этого метода декомпозиции шяется возможность использования в подобластях, на которые разбивает-[ исходная область, независимых друг от друга сеток. В частности, следы ток на интерфейсах между подобластями могут не совпадать. Эта особен->сть открывает возможности для создания гибких параллельных методов (аптивного решения задач. Исходная дифференциальная задача, путём (едения множителей Лагранжа, переформулируется в форме задачи поис-i седловой точки, аппроксимация последней проводится с использованием эртарного (mortar) метода конечных элементов. Получающаяся при этом [стема линейных уравнений с незнакоопределённой матрицей решается >и помощи обобщённого метода минимальных итераций Ланцоша с поло-ительно определённым блочно-диагональным переобуславливателем (полным же образом решалась задача Стокса в § 1.2). Переобуславливатель слючает блоки, соответствующие задачам в подобластях и на интерфей-ix между подобластями. Для решения задач в подобластях и задач, соот-:тствующих интерфейсам, использовались, в частности, алгебраические зогосеточные методы, рассмотренные в диссертации. Рассматриваемый этод является существенно параллельным, поэтому особое внимание бы) придано результатам численных экспериментов, проведённых на парал-гльном компьютере SP2.

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

Для решения уравнения Пуассона, аппроксимированного на квази-иерар-1ческих регулярных сетках, построен усиленный алгебраический многоточный метод с оценкой скорости сходимости, не зависящей от степени ущения сетки. Проведено численное исследование параллельных свойств ;иленного алгебраического многосеточного метода на многопроцессорных .¡числительных системах.

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

-16 -

являющихся объединением тетраэдров.

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

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

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

1. Параллельный алгебраический многосеточный метод (совместно < Ю. А. Кузнецовым) - В сб.: Численные методы и математическое моделирование, Москва, ИВМ РАН, 1992.

2. Two iterative methods for solving the Stokes problem (совместно с Т. Ross: и J. Toivanen) - Reports on Applied Mathematics and Computing, No. 2 University of Jyväskulä, 35 p., 1993.

3. Алгебраический многосеточный метод для конечноэлементной аппроксимации трёхмерного уравнения диффузии - В сб.: Численные методы t приложения. Деп. в ВИНИТИ No. 394-В95 от 10.02.95, 1995, с. 68-80.

4. Алгебраический многосеточный метод для конечноэлементной аппроксимации эллиптическихуравнений на составных сетках - В сб.: Численньк методы и приложения. Деп. в ВИНИТИ No. 394-В95 от 10.02.95, 1995, с. 8191.

5. On the application of strengthened AMG for partially unstructured meshe; to unsteady fully potential flow problem with moving boundaries (совместно ( Ю. А. Кузнецовым и Ю. В. Василевским) - In: Proceedings of French-Russian-Uzbek Workshop on experiment, modelling and numerical methods in fluid dy namics, 1995.

6. On the application of fictitious domain and strengthened AMG method fo; locally fitted 3D cartesian meshes to the potential flow problem on a massivel] parallel computer (совместно с Ю. А. Кузнецовым и Ю. В. Василевским) -Report No. 9543, University of Nijmegen, The Netherlands, 1995.

7. Efficient parallel solving the potential flow problems on nonmatching grids (со вместно с Ю. А. Кузнецовым и Ю. В. Василевским) - In: Numerical Method: in Engineering. Proceedings of the Second ECCOMAS Conference on Numerica Methods in Engineering, John Wiley & Sons, pp. 469-475 (1996).

8. Efficient parallel solvers for two dimensional potential flow and convection diffusion problems on nonmatching grids (совместно с Ю. А. Кузнецовым i Ю. В. Василевским) - Report No. 357, Universität Augsburg, Germany, 1996

9. Structuring preconditioners for unstructured meshes (совместно с В. Дядеч ко и Ю. Василевским) - Russ. J. Numer. Anal. Math. Modelling, 11, No. 2 139-154 (1996).