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

яизииэцъь =шърц1)Ь8пнэзиъ ^ЬБПИЭЗПЬЬЪЬРЬ иааизьъ ишпьиьизь ръаприизьцизь м ичэпиизизшъ ^РПРИзЦЪЬРЬ ььизьэш-з

зичпрзиъ зпгрр пш-рьър

=ШЪР1ПЦС4иМЦЪ риаиивиъвивьъ 4ЬР11Т1и31Ш1Ц4ЛПЬЭЪЬР ЦЬРЭСЫПР зиппизьь иизрьзъьрр яииир

РГб од

- 6 СЕН 2000

Ь.13,05 «Яш2||п1ш1)ш0 ^ йшрМшт^ш^шО

(ЗЬргщйЬр^1^ритпи5[1 с^илш1|шО ЬЬти^птп^гиООЬргшЗ » ДшиОшсфттиилЗр

ф^^илЗшрЬйилгф^ш^шО £}[ипгир)т.йОЬр|1

иьчиичьр

ьрьааь - 2000,

ИНСТИТУТ ПРОБЛЕМ ИНФОРМАТИКИ И АВТОМАТИЗАЦИИ НАЦИОНАЛЬНОЙ АКАДЕМИИ НАУК РЕСПУБЛИКИ АРМЕНИЯ

АКОПЯН ЮРИЙ РУБЕНОВИЧ

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

АВТОРЕФЕРАТ

диссертации на соискание ученой степени доктора

физико-математических наук по специальности

05.13.05 « Применение вычислительной техники и математических методов в научных исследованиях »

ЕРЕВАН - 2000

UmbGiufununi.pjujG pbüuiG huiumiumLlbl.t bpLuiGh щЬшшЦшО hiui5iii|UiupujGm.i5

'ПшгшпОш^шО [iGrytfiduJtwmGbp' 3>tiqh4u>-tiujpbi5iumfil|uiljLuG qfiLniupjruüübpl1 ryiljmnp,

щрпфЬипр Q.U.MnpbLljnil

qJimnLßjnLGGbpfi i^nljinnp, щрпфЬипр 3m..U.lTni|uhu)iuG

фЬчЬкш-ДшрЬйшш^ш^шО qfiuinLpjniGQäpfi ryitfmnp, щрпфЬипр U.O.ßniGfiU

Ипш2шшшр ЦшцйшЦЬрщгвдтО' ОФЛ UP ^шгфи^шЦшй U йшрЬйшиф-

ЦшЦшй qbn^fiqhljWjh tiGum|iinnun, ß.bmlnufiphpul)

Т1ш2ШИ)Шйп1йП1йо liuijuiGiuini1 2000р. иЬщшЬйсЬп|1 15-hG. д. 11°°

037 ItfipfanGbin^iu U рйфпрйшш^ш" öwuüwqtiuiwl^uiü [ипрЬрф

Gfiummü ИЬт^Ш! hiuugbnil' 375014 р. bpluuG, 'Л.иишЦ^ фпг\. 1 :

UuibGuifununLpjuiGQ ЦшрЬцЬ t öiuGnpuuGiu[. hynh- [i qfiiniuliujG qpLurmipuiGm.i5:

Ubi\Ciujq.fipQ umujfii|iuä t 2000p. ognumnuh 3-hG

ишийшсфтшЦшй (unphprtfi с>|1шш11шО ршрштцшр, Ж __ fjjZtf' uiDin. ctfiin. р., uiiluiq qfm

U.b.UbLBnGjiuG

Тема диссертации утверждена в Ереванском государственном университете

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

профессор Г.М.Кобельков

доктор физико-математических наук, профессор Ю.М.Мовсисян

доктор физико-математических наук, профессор А.Д.Туниев

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

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

Защита состоится 15 сентября 2000г. в часов на заседании

специализированного совета 037 "Математическая кибернетика и информатика" в Институте проблем информатики и автоматизации HAH РА по адресу : 375014 г.Ереван, ул. П.Севака, 1

С диссертацией можно ознакомиться в научной библиотеке ИПИА HAH РА Автореферат разослан 3 августа 2000г.

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

специализированного совета, к.э.н., ст. н. с. А.Е. Мелконян

B/9J?

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

Актуальность темы. Многие задачи современного естествознания при-

одят к дифференциальным уравнениям с частными производными (уравне-1иям математической физики). Однако получить решение уравнения в явном

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

равнений, в частности, метод конечных разностей и метод конечных эле-гентов.

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

1. конечноразностная (или конечноэлементная) аппроксимация дифференциального уравнения;

2. решение полученной системы сеточных уравнений.

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

• система имеет высокий порядок, пропорциональный числу узлов сетки;

• матрица системы является разреженной;

• система, как правило, плохо обусловлена.

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

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

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

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

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

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

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

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

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

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

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

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

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

На защиту выносятся следующие основные положения:

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

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

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

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

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

Конференции:

IV международная конференция по дифференциальным уравнениям и их при-

гнению (г.Русе, Болгария, 1989); IV международный симпозиум по методам ^композиции области (г.Москва, Россия, 1990); III международная конферен-1Я по численному анализу (г.Москва, Россия, 1992); I финско-российская кон-еренция по вычислительной математике (г.Ювяскюля, Финляндия, 1992); европейская конференция по вычислительной математике и передовым при->жениям ENUMATH'95 (г.Париж, Франция, 1995); международная алгебраи-:ская конференция, посвященная памяти Д.К.Фаддеева (г.Санкт-Петербург, эссия, 1997); международная конференция по вычислительным наукам и ин-эрмационным технологиям CS1T-97 (г.Ереван, Армения, 1997); международ-m конференция по вычислительным наукам и информационным технологиям 5IT-99 (г.Ереван, Армения, 1999).

Семинары:

Семестр по численному анализу и математическому моделированию, Ме> дународный математический центр С.Банаха (г.Варшава, Польша, 1987,199! семинар по прикладной математике Университета Ювяскюля (г.Ювяскюл Финляндия, 1992); семинар по вычислительной линейной алгебре и ее пр ложениям, Католический университет Наймегена (г.Наймеген, Нидерланд! 1993,1995,1996,1997); семинар рабочей группы по проекту ИМТАБ 93-377 (г.П риж, Франция, 1995); семинар по прикладной математике Мичиганского ун верситета (г.Анн-Арбор, США, 1996); семинар рабочей группы по проек-ИМТАБ 93-377ех (г.Санкт-Петербург, Россия, 1997).

Публикации. Основные результаты диссертационной работы отражен в 18 научных статьях.

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

ра результатов по многосеточным методам переобуславливания, трех гла заключения, приложения, списка основных обозначений и списка литератур (100 наименований). Объем работы - 246 стр.

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

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

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

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

1. матрица М спектрально эквивалентна матрице А, то есть, существуют положительные постоянные Сх и Сг. не зависящие от порядка п матрицы А, такие, что

СщТМи < итАи < С2итМи УиеНп;

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

Завершается Обзор кратким изложением содержания диссертации.

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

В основе подхода лежит использование иерархической последовательности треугольных сеток. Каждая последующая сетка получается из предыдущей с помощью единообразной процедуры измельчения. Самая грубая сетка выбирается настолько "грубой", чтобы объем вычислительной работы, необходимый для решения редуцированной системы сеточных уравнений, был достаточно мал. В то же время самая мелкая сетка выбирается так, чтобы обеспечить требуемую точность численного решения. На каждом уровне измельчения осуществляется разбиение множества сторон ячеек сетки на подструктуры и на этой основе строятся многосеточные переобуславливатели с внутренними че-бышевскими итерациями. Предлагаемый метод построения многосеточных пе-реобуславливателей назван AM/S-методом (Algebraic multigrid/substructuring method). Аналогичный подход в случае прямоугольных сеток применялся ранее в статье Ю.А.Кузнецова. 1

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

В плоскости переменных х — {x\,xi) рассматривается многоугольная область Ü, являющаяся объединением некоторого числа I > 1 треугольников Am ,тп — 1,2,... ,1. Предполагается, что любые два треугольника либо не пересекаются, либо имеют только общую вершину, либо только общую сторону. Замкнутое подмножество Го границы díl состоит из сторон треугольников Дт (Гц может быть и пустым множеством).

Так как область S! составлена из треугольников, то тем самым имеется вполне определенная начальная триангуляция tq. Процесс построения иерархической последовательности сеток основан на следующей процедуре измельчения: каждый из треугольников, образующих триангуляцию, с помощью отрезков, соединяющих середины его сторон, разбивается на четыре треугольника. Руководствуясь этим правилом, исходя из tq строится последовательность триангуляции , к = 0,1,... ,р, области Í2. При этом говорится, что триангуляция 7х- соответствует к-му уровню измельчения сетки. Треугольники, образующие триангуляцию т¿, называются треугольными элементами к-го уровня. С каждой триангуляцией тк ассоциируется сетка , узлами которой являются вершины треугольных элементов.

Вводятся следующие обозначения:

Nk~ множество узлов сетки и^ , принадлежащих Í2 \ Го;

n/z - число узлов в множестве iV¿;

Vfc- пространство непрерывных в области Ü функций, линейных на каждом треугольном элементе из т^ и обращающихся в нуль на Го.

1 Yu.A.Kuznetsov. Algebraic multigrid domain decomposition methods.- Sov. J. Numer. Anal. Math. Modelling, v.4,No.5,1989, 351-379.

В параграфе 1,2 дается вариационная постановка эллиптической краево: задачи и определяется конечноэлементная система сеточных уравнений на ос нове кусочно-линейной аппроксимации. В предположении, что Г0 ф 0, фор мулируется приближенная конечноэлементная задача: для заданной функцш / £ ¿2(^0 найти функцию й € Ур такую, что

а Уй Уг) йх = ! / V йх Уу€Ур, (1

где коэффициент а - положительная, постоянная в каждом треугольна ке Дт функция.

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

Аи = д (2

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

В диссертации широко используется известное понятие спектрального чис ла обусловленности матрицы . Определяется оно следующим образом: дл. любых симметричных положительно определенных матриц А и В чере сопё(В~1 А) обозначается отношение наибольшего собственного числа мат рицы В"1 А к ее наименьшему собственному числу.

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

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

А = азвет {Ат : 1 < т < 1}.

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

УТЬти < иТАть < 5® уТЬть Уь, (3

где положительные постоянные и <5® не зависят от числа уровней из мельчения сетки, а определяются лишь геометрическими параметрами тре угольников Дт. Затем, используя операцию ансамблирования, строится мат рица

Ь = аБвет {ктЬт : 1 <т<1}, (4

где кт есть некоторые положительные параметры.

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

Исходя из требования минимизации числа обусловленности cond(L~lA), решается задача выбора параметров кт.

Теорема 1.2.1. 2 Пусть параметры кт в определении (4) матрицы L выбраны следующим образом:

кт = ysiïâffl , m =1,2,...,/. (5)

Тогда, независимо от значений коэффициента а в подобластях Ат,

cond (L А) < Xmin = max -rfr . (6)

Km< Âv ' - - Orn

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

Параграф 1.3 посвящен построению и исследованию двухсеточных перео-буславливателей.

Прежде всего, на последовательности сеток u)k строятся матрицы

L(k) = assem {ктЬ^ : 1 < m < 1} , k = 0,1,..., р , (7)

где есть матрицы конечноэлементного типа для треугольников Д„, (построенные с применением упоминавшегося выше отображения на единичный равносторонний треугольник), а к,„- некоторые положительные параметры. Для значений k > 1 матрица

m может быть представлена в блочном виде

LW

Т (к) г (к)

г (к) г (к) L/ ni iin-

. (8)

Заметим, что если параметры кгп в (7) выбраны согласно (5), то матрица Ь^ совпадает, по построению, с матрицей Ь, определенной в (4).

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

р>(к) т(к)

£>11 hl2

г (к) Ак) Ь21

}Nk\Nk-1

2Нумерзция теорем дается в соответствии с текстом диссертации.

от _ гт _ Т(к)г>(к) 1т(к) ¿>22 ~ ь22 -^21 ь12

где верхним левый блок В'11 есть диагональная матрица. Остальные блок! ¡пг , и 1^2 те же, что и в блочном представлении (8) матрицы .

Для дополнения Шура

¿(к) _ т (к)

матрицы доказано следующее важное утверждение.

Теорема 1.3.1. Для значений к — 1,2,... ,р справедливы равенства

Таким образом, в силу способа построения, дополнение Шура переобуслав ливателя В^ с точностью до числового множителя совпадает с конечноэле ментной матрицей на предыдущей, более грубой сетке. Основываясь на соот ношении (10), матрица

вю названа двухсеточным переобуславливателел

для матрицы

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

Б«

, не зависящие от общего числа уровней.

Теорема 1.3.2 . Независимо от выбора параметров кт в (7), а такж( независимо от значений коэффициента а в подобластях Дт, собствен ные числа матрицы

£(*) £(*); 1 < к <р, принадлежат отрезку [1,5].

В параграфе 1.4 описывается построение многосеточного переобуславли-вателя для матрицы А. Строится он путем замены дополнений Шура в блоч ных представлениях (9) двухсеточных переобуславливателей на задаваемьк неявно и рекурсивно определяемые матрицы. Эта рекурсия использует на каж дом уровне чебышевские итерации, где в качестве переобуславливающей матрицы берется многосеточный переобуславливатель с предыдущего, более грубого уровня. Таким образом, многосеточный переобуславливатель для исход ной матрицы жесткости строится рекурсивно, от одного уровня к другому вплоть до самой грубой сетки, где система сеточных уравнений решается < помощью некоторого прямого метода.

А именно, выбирается некоторое целое число V > 1 и для значений к -1,2,...,р последовательно определяются матрицы

т (к) ^21

г (к) -^12

г (к) 1>12

где

К(к-1) = £(*-!)

для для

(и:

к = 1 , 2 < к <р.

I

В качестве параметров ef~V', j = l,2,...,v, берутся величины, обратные к образам корней многочлена Чебышева первого рода степени и на отрезке

[ctk-i, ßk-i] . содержащем спектр матрицы Ai^-1' .

Матрица М = М^ называется многосеточным переобуслаеливателем для матрицы А конечноэлементной системы уравнений (3).

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

Теорема 1.4.2. Пусть v = 3 и параметры кт в (7) выбраны в соответствии с формулами (5). Тогда, независимо от значений коэффициента г в подобластях Ат, справедлива оценка

Cond (М-1 А) < (3 + 2\/5) Xmin , где величина Xmin определена в (6).

В итерационных методах с матрицей М = М^ в качестве многосеточно--о переообуславливателя необходимо решать системы уравнений с матрицами MW , где к — 1,2,... ,р. Дается процедура MG PREC/M(k)/1 решения системы с матрицей М® из (11). которая требует обращения матриц В$ и ß(t-i) Матрица В^ является диагональной. Решение же системы с матрицей , при к > 1, эквивалентно выполнению трех шагов чебышевского чтерационного метода с переобуславливающей матрицей На самой "рубой сетке, соответствующей нулевому уровню, система сеточных уравнений с матрицей L® решается с помощью некоторого прямого метода с затратой 0(1) арифметических операций.

В заключении параграфа дается оценка числа арифметических операций Aops, затрачиваемых на решение системы с матрицей М, то есть, на выпол-^ние одного шага переобуславливания:

A>ps — (64 + А^я) пр, ■де число арифметических операций, требуемых для решения системы

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

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

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

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

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

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

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

Вводятся следующие обозначения:

И- множество узлов сетки ш, принадлежащих ^ \ Го ;

п - число узлов в множестве N;

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

В предположении, что Го Ф 0, формулируется следующая конечноэлемент ная задача: для заданной функции / € ¿г(^) найти функцию й € V та кую, что

I аЧйЧьЛх =! /ьйх \fveV, (12

где коэффициент а - положительная, постоянная в каждом треугольни ке Дт функция.

Задача (12) приводит к системе сеточных уравнений

Ои = д (13

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

С} — аазелз {<3т : 1

где С)т есть матрицы жесткости для отдельных треугольников Ат.

Используя идеи и методы параграфа 1.2 (отображение на единичный равно сторонний треугольник), для матрицы С} системы (13) строится спектральж эквивалентная матрица

К — алеет {ктКт : 1 < т < 1} , (14

где кт~ некоторые положительные параметры.

Для каждого треугольника Ат , 1<т<1, имеет место отношение эквивалентности

иТКту < уТЯть < <5® уТКту Уи, где положительные постоянные и хе Жб1 что и в отношении эквивалентности (3).

Следующее утверждение аналогично Теореме 1.2.1, приведенной выше.

Теорема 1.5.1, Пусть параметры кт в определении (Ц) матрицы К выбраны в соответствии с формулами (5). Тогда, независимо от значений коэффициента а в подобластях Дт,

С0П(1 (/<"_1<2) < Хгт'п ,

где величина Хтт определена в (6).

Таким образом, построена матрица К, спектрально эквивалентная матрице С} конечноэлементной системы (13). В дальнейшем строится многосеточный переобуславливатель для матрицы К, который будет являться одновременно переобуславливателем и для матрицы <3.

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

Матрица К может быть представлена в блочной форме

К =

Кп Кп

к21 к2г

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

(м)

[К21 К,; \ }№„

где верхний левый блок Вц есть диагональная матрица, а блоки К\2, К21 и К-12 те же, что и в блочном представлении (15) матрицы К. Доказано следующее утверждение.

Теорема 1.6.1. Для дополнения Шура 5г2 = К22 - К21В11К12 справедливо равенство

где Ь^ есть конечноэлементная матрица, определенная в (7).

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

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

Теорема 1.6.2 . Независимо от выбора параметров кт в (14), а так же независимо от значений коэффициента а в подобластях Дт, собст венные числа матрицы В~ХК принадлежат отрезку [1,6].

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

Определенная в (14) матрица К представляется в блочной форме

К =

Кп К21 О

К12 О К22 к23 Кз2 Кзз

(17;

где Л^1)- множество узлов, расположенных в центрах тяжести кубических треугольных элементов, а -М2) - множество дополнительно введенных узлов, расположенных на сторонах кубических треугольных элементов. При этом блок К\\ является диагональной матрицей.

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

В =

Ки Ки _ О

К21 В22 + К21К11К1Т В2з О • В32 В33

}АГ(1)

(18)

где блоки К\\, К\2 и Кц те же, что и в блочном представлении (17) матрицы К. Здесь В22 есть блочно диагональная матрица с невырожденными диагональными блоками второго порядка.

Теорема 1.7.1. Для дополнения Шура 5зз = В33 — В^Щ^гз справедливо равенство

33 4600

где

№ есть конечноэлементная матрица, определенная в (7) . Матрица В названа двухуровневым линеаризирующим- переобуславлива-телем для матрицы К. Оценены границы спектра матрицы В~ХК.

Теорема 1.7.2 . Независимо от выбора параметров кт в (14), а также независимо от значений коэффициента а в подобластях Ат, собственные числа матрицы В~1К принадлежат отрезку [1,16.74] ■

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

Кусочно-квадратичная аппроксимация. Основываясь на блочном представлении (16) матрицы В и утверждении Теоремы 1.6.1, выбирается некоторое целое число V > I и определяется матрица

М

В и

К21

где

ДМ

Кп

■ К21В11К12

(19)

Матрицы Цр) и М^ определены в (7) и (11), соответственно. В качестве параметров в^ , ] = 1, 2,..., и, берутся величины, обратные к образам корней многочлена Чебышева первого рода степени V на отрезке (Зр], содержащем спектр матрицы М® I» . Предполагается, что набор положительных параметров кт, участвующих как в определении (7) матриц Ь^, так и в определении (14) матрицы К, один и тот же.

Матрица М. называется многосеточным переобуславливателем для матрицы К. С учетом Теоремы 1.5.1 доказано следующее утверждение.

Теорема 1.8.2. Пусть параметры кт в (7) и (14) выбраны в соответствии с формулами (5). Тогда, независимо от значений коэффициента а в подобластях Лт , справедлива оценка

сопд[М~10) < 6

Хтт :

где с, = 3 + 2\/Ъ, а Хтт ~ величина, определенная в (6) .

В параграфе приведена процедура МС РИЕС/А4/2 решения системы с матрицей М , требующая обращения матриц Вц и

ДМ . Матрица Вц является диагональной. В силу определения (19), решение системы с матрицей Д^

эквивалентно выполнению V шагов чебышевского итерационного метода с переобуславливающей матрицей М^ , построенной для случая кусочно-линейной аппроксимации.

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

4 + 201/ + ^С

Аг^» ОрЗ —

П .

Кусочно-кубическаяадпроксимация. Имея блочное представление (18) мат рицы В и основываясь на утверждении Теоремы 1.7.1, выбирается некоторое целое число и > 1 и строится матрица

М =

Ки К21 О

К12 _ В2 2 + КцКхуКхо

О

-Вгз

■Вз2

ЖЯ<»>+ £32^23

в которой матрица определена в (19).

Матрица М.- многосеточный переобуславливатель для матрицы К. Доказано следующее утверждение, аналогичное Теореме 1.8.2. Теорема 1.8.3. Пусть параметры кт в (7) и (14) выбраны в соответствии с формулами (5). Тогда, независимо от значений коэффициента а в подобластях Дт, справедлива оценка

сопй(М~1Я) < 16.74

Хтт I

где с„ — 3 + 2\/5, а, Хтт ~ величина, определенная в (6).

Дана процедура МС РКЕС/М/З решения системы с матрицей М., которая требует обращения матриц Кц , В^г и . Матрица Кц является диагональной; В22 - блочно диагональная матрица с диагональными блоками второго порядка. В силу определения (19), решение системы с матрицей Д^ эквивалентно выполнению и шагов чебышевского итерационного метода с переобуславливающей матрицей М^ .

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

т-орэ

18+ 121/+ £<4®

Для обоих типов аппроксимации рассмотрен вопрос о выборе и, числа че-бышевских итераций на самом верхнем уровне, - с точки зрения минимизации общих вычислительных затрат, требуемых для решения системы сеточных уравнений (13) с переобуславливателем М. (

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

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

п

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

В основе предлагаемого в главе подхода к построению многосеточных пе-реобуславливателей лежит идея использования на промежуточных уровнях так называемых возмущенных конечноэлементных матриц, которые не являются дискретными аналогами исходного дифференциального оператора. В случае сеточного оператора типа Гельмгольца — Ди + сги, где а = const > 0, конеч-ноэлементные матрицы для мелкой и грубой сеток соответствуют различным значениям коэффициента возмущения а . А именно, матрица для грубой сетки соответствует большему значению величины а. Тем самым обусловленность конечноэлементной матрицы, при переходе с мелкой сетки на грубую, улучшается не только за счет увеличения шага сетки, но также и благодаря росту коэффициента а. Таким образом достигается требуемая обусловленность конечноэлементной матрицы на грубой сетке за меньшее число уровней по сравнению с классическими многосеточными процедурами. При этом система сеточных уравнений на грубой сетке имеет достаточно большую размерность и может быть эффективно реализована на компьютерах с параллельной архитектурой.

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

Вначале дается конечноэлементная постановка самосопряженной эллиптической краевой задачи: для заданной функции / £ ¿г(^) найти функцию й (zVp такую, что

1а

2 Яц ЯЦ

£ ац + Vfi € . (20)

.¿,j=i oxj dxi J

Относительно коэффициентов a^ предполагается, что для каждого треугольника Д,и, 1 < т < I, существуют такие положительные постоянные и

q(2) чт0

i & < Е OiiWtti < £ $ е R (21)

для всех х £ Дт . Коэффициент а = const > 0.

Задача (20) сводится к системе сеточных уравнений

Аи = д (22)

с симметричной положительно определенной матрицей А порядка пр, которая может быть получена с помощью операции ансамблирования

А = азяет {Лт : 1 < т < /} конечноэлементных матриц Ат для отдельных треугольников Дт.

Построение матрицы Ь, спектрально эквивалентной матрице А, осуществляется так же, как и в параграфе 1.2. Используя отображение треугольников Дт на единичный равносторонний треугольник, для конечноэлементных матриц Ат строятся спектрально эквивалентные матрицы Ьт = Ат + аСт (Лт- матрица жесткости, Ст - матрица массы) такие, что справедливо отношение эквивалентности

ьТЬту < уТАту < уТЬть \/у ,

где положительные постоянные и определяются геометрическими параметрами треугольников Ат и зависят от постоянных и а^ из (21). Далее, используя операцию ансамблирования, строится матрица

Ь = азвет {ктЬт : 1 < т < 1}, (23)

где кт есть некоторые положительные параметры. Как и в Главе 1, решается вопрос об оптимальном выборе параметров, минимизирующих оценку числа обусловленности сопв (Ь~1А). Показано (Теорема 2.1.1), что если параметры кт в определении (23) матрицы Ь выбраны следующим образом:

кт = у/ИЖ,_ т = 1,2,... ,1, (24)

то

¿(2)

сопй [Ь М) < Хтгп = тах . (25)

1 <"!<!

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

Пусть 0 < к < р. Для всех треугольников Дт определяются матрицы жесткости Л£> и матрицы массы , построенные с применением упоминавшегося выше отображения на единичный равносторонний треугольник. Далее, выбрав некоторые положительные параметры кт, т = 1,2,... ,1, с помощью операции ансамблирования строятся матрицы

Л<*> = а^вет{ктА.$ : 1 <т<1},

С<*> = аззет{ктС$ :1<т<1}. ^

Наконец, определяется матрица

Ь(к) = д№ + акС(к) ^ (27)

которая рассматривается как возмущенная конечноэлементная матрица для дифференциального оператора задачи (20). Постоянная о* > 0 называется

коэффициентом возмущения. Для значений к > 1 матрица представима в блочном виде

=

Т% т{к)

г (к) г (к) ■"21 Ь22

' (28)

Если (7р ■= а и параметры кт выбраны согласно (24), то возмущенная

матрица Ь^ совпадает с матрицей Ь, определенной в (23).

Параграф 2.2 посвящен построению АМ/Б-версии двухсеточного переобу-славливателя для возмущенной конечноэлементной матрицы.

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

№ , где 1 < к < р, строится переобуславливающая матрица

д(*) г (к)

Т(к) т(к)

1 ' (9)

где блоки Ьу} , и Ьщ те же, что и в блочном представлении (28) матрицы Ь^ . Блок Вы1, в отличие от блока Ь^ матрицы Ь^ , является диагональной матрицей. Доказано следующее утверждение.

Теорема 2.2.1. Для дополнения Шура Б^) = — Ь^В^ ь\к2 матрицы из (29) справедливо равенство

а котором

ек = (8 + <гкЬ2к)/1б, а матрица определяется равенством

^ 8<тк(8(1 + 0) + Ы%)

<7к~1 (8 + акк\) (8 +(1+ЩакН1)-

Параметр д > 1, участвующий в определении переобуславливателя

В(к)

, называется параметром возмущения.

В параграфе 2.3, на основе полученного в предыдущем параграфе утверждения (Теорема 2.2.1), определяющего правило последовательного вычисления коэффициентов возмущения, строится последовательность возмущенных конечноэлементных матриц

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

о> = <г,

_ (8(1 + е) + в*М) fc_pp_1 L

Доказано утверждение (Теорема 2.3.1), устанавливающее нижнюю и верхнюю границы собственных чисел матрицы В^ iP^, 1 < к < р. Границы эти зависят от уровня разбиения сетки (в частности, от коэффициента возмущения <jfc) и параметра возмущения 0. Исследовано поведение, с изменением номера уровня к , границ спектра матрицы В® 1L№ .

Параграф 2.4 посвящен построению AM/S-версии многосеточного перео-буславливателя с внутренними чебышевскими итерациями.

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

диагональная матрица ., ,,

M(r) = lump (LW)

(операция lump строит диагональную матрицу, диагональные элементы которой равны сумме элементов соответствующих строк исходной матрицы). Далее, для значений к = г + 1,г + 2,... ,р последовательно определяются матрицы

М« -

У21 £кП-- ''-t 1^21 Щ\ М2

В{к) L{k)

где

7-1

R(k-1) _ L(k-1)

(30)

(31)

- п и-в^м^-1^-»)

В формуле (31), в качестве параметров

.7 = 1,2,..., , берутся величины, обратные к образам корней многочлена Чебышева первого рода степени Рк~ 1 на отрезке [а^-ь (Зк-1]. содержащем спектр матрицы М^-1' . Предполагается, что

(в, если к — г + 1 , , .

^^ = \3, если т + 2<к<р. (32)

Матрица М = М^ рассматривается в качестве многосеточного переобуславливателя для матрицы А системы сеточных уравнений (22).

Дается процедура МС РРЕС/РЕРТ/М(к)/(АМ/5) решения системы с матрицей М^ из (30), требующая обращения матриц и Матрица в[¥ является диагональной. Решение системы с матрицей , при к > г + 1, эквивалентно выполнению шагов чебышевского итерационного метода с переобуславливающей матрицей . Согласно (32), при реализации многосеточного переобуславливателя, на самой грубой из используемых сеток с номером г осуществляется 5 чебышевских итераций с диагональной переобуславливающей матрицей М^ , в то время как на остальных уровнях выполняются по три итерации.

В параграфе дается оценка числа арифметических операций, затрачиваемых на решение системы с матрицей М:

А ~

лорз -

64 + 6в(^Р "

В связи с выводом оценки числа обусловленности переобусловленной матрицы А системы сеточных уравнений (22), не зависящей от общего числа уровней измельчения сетки, рассматриваются вопросы выбора параметра возмущения в и числа итераций э на самом нижнем уровне с номером г. Показано, что параметр возмущения следует выбирать из диапазона 1 < в < 2.6. Приведена вычислительная процедура СА1.С (б) определения числа итераций 5 в зависимости от выбора параметра возмущения в и номера уровня г. Доказано следующее утверждение.

Теорема 2.4.2. Пусть выбран уровень г, где 0 < г < р, и определено число итераций 5 на этом уровне согласно процедуре СА1.С (в). Кроме того, параметры кт в (26) выбраны по формулам (24)- Тогда имеет место оценка

соп<1 (М ХА) < ^ ' — / 1 ■ _

(9 + 156)+ 8^10(1 +А) А

13 - 5в

где Хтт есть величины, определенная в (25).

В параграфе 2.5 обсуждается вопрос определения уровня г самой грубой сетки, до которого осуществляется спуск при реализации АМ/Б-версии многосеточного переобуславливателя. В основе решения лежит минимизация числа

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

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

находится асимптотическая формула

г = [/1р\,

где величина /2 зависит от параметра возмущения в. На основе проведенного анализа показано, что величина ¡1 растет с увеличением в из рассматриваемого диапазона 1 < в < 2.6, стремясь к своему предельному значению Д = 0.57.

Параграф 2.6 содержит построение AMLI-версии двухсеточных переобу-славливателей для возмущенных конечноэлементных матриц (аббревиатура AMLI происходит от названия метода- Algebraic multilevel iteration method, предложенного У.Аксельсоном и П.Вассилевским. 3)

Рассматриваются возмущенные конечноэлементные матрицы

Lw = AW + vkCW, к = 0,1,...,р,

где коэффициенты возмущения ак определяются посредством формулы

= А: = 0,1.....р. (33)

Величина а > 0 называется параметром возмущения; коэффициент а тот же, что и в (20).

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

Для значений к > 1, в качестве двухсеточного переобуславливателя для матрицы , представленной в (28), рассматривается матрица

В(к) =

¿й> ekL^ + ¿1 В^-'т

}Nk\Nk^ }Nk. г '

в которой Bii есть полиномиальная аппроксимация блока bfi (с использованием нормализованного многочлена Чебышева степени 7), ек- нормирующий коэффициент, зависящий, в частности, от параметра возмущения а и

^ fW ?№)

коэффициента возмущения ак, а Ь\2 и ¿21 - матрицы, выражающиеся через внедиагональные блоки представления матрицы в так называемом двухуровневом иерархическом базисе и матрицу

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

по отношению к двухсеточным переобуславливате-

лям 5«.

3O.Axelsson and P.Vassilevski. Algebraic multilevel preconditioning methods.! - Numer. Math., 56 (1989), 157-177.

Сформулировано и доказано утверждение (Теорема 2.7.2), устанавливающее границы спектра матрицы . Показано, что собственные числа матрицы принадлежат отрезку 1]. Получена формула для вычисления

5(а, 7)

положительной величины ак , зависящей от параметра возмущения а и 7-степени нормализованного многочлена Чебышева.

В параграфе 2.8 излагается построение АМН-версии многосеточного пе-реобуславливателя.

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

М{т) = вг1итр(1(г)) со специальным образом подобранным нормирующим коэффициентом вг. Далее, взяв за основу представление (34) двухсеточного переобуславливателя, для значений & = г + 1, г + 2,..., р последовательно определяются матрицы

М{к) =

-Рп

г(*) •^12

где

-^12

(35)

"к-1

(36)

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

многочлен Чебышева степени ¡/¡¡-1- Предполагается, что

а-, если к = г + 1 , , .

¡/, если г + 2<к<р.

Матрица М = М^ называется многосеточным переобуславливателем для матрицы А системы сеточных уравнений (22).

Дается процедура МС РЯЕС/РЕЯТ/М(к)/(АМН) решения системы с матрицей мю из (35), в которой происходит обращение матриц в}^ и ^ . Согласно определению, решение системы с матрицей эквивалентно выполнению 7 шагов итерационного метода, содержащего лишь обращение диагональной матрицы. Решение, системы с матрицей Я^-1) эквивалентно выполнению У'К-\ шагов чебышевского итерационного метода с переобуславливающей матрицей М^"1). Согласно (37), на самой грубой сетке осуществляется в чебышевских итераций с диагональной переобуславливающей матрицей М^ , в то время как на остальных уровнях выполняются по V итераций, где и = 2 или V — 3. Получено выражение для арифметической цены одного шага переобуславливания:

А ^ —

27 + 727 + 151/

4 — и

+ 45

а:

р—)—1

п.

■р I

= 2,3).

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

СОП(1(М~1А) < КгХтт, (38)

где величина А« зависит от параметра возмущения а и числа итераций 7 и V, а Хты~ величина, определенная в (25). В следующем параграфе выводится формула, по которой вычисляется величина Л*.

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

Сформулируем кратко полученные результаты:

- определено число итераций 7 = 4, требуемых для обращения матрицы ;

- установлены диапазоны параметра возмущения:

0.68 < а < 1.8 для V - 2 , 0.68 < а < 3 для и = 3 ;

- получена формула для вычисления величины А* из оценки (38);

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

г =

о + 4 — 2 log2 v

Р

а + 6 — 2 log2 v

в частности, в обоих случаях v = 2 и и — 3, достигается максимальный уровень г ~ [0.65 pj;

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

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

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

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

Сформулирована и доказана Теорема 2.11.2, в которой получена оценка числа обусловленности сond (М~1А) .

Приведена процедура MG PREC/PERT/M(k)/(AML!-HYBR!D) решения системы сеточных уравнений с матрицей М^ . Дается выражение для арифметической цены одного шага переобуславливания Аорз.

Параграф 2.12 посвящен определению параметров гибридного многосеточного переобуславливателя. Разработана процедура PARAM HYBRID PREC вычисления параметров. Сохраняя определенный баланс между оптимальностью по порядку арифметической цены одного шага переобуславливания и стабилизацией числа обусловленности, находится соотношение между параметрами ко и и в зависимости от параметра возмущения конечноэлементной матрицы. Решая задачу минимизации числа используемых уровней, находится предельная асимптотическая зависимость между номером уровня самой грубой сетки г и общим числом уровней измельчения сетки р: г = ¡_0.65pj.

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

Глава 3 посвящена построению алгебраических многосеточных переобуславливателей на квазииерархических треугольных сетках. Предлагается отказ от строгой иерархичности сеток, используемых в классических многосеточных алгоритмах. Сетки, которые здесь строятся, являются иерархическими внутри области и не являются таковыми вблизи ее границы. Такие сетки позволяют лучше аппроксимировать границу области сложной геометрической формы и вместе с тем использовать структуру иерархических сеток. В главе рассматриваются два подхода к построению квазииерархических сеток, в основе которых лежат регулярные сетки с равносторонними треугольными ячейками. Соответственно, строятся многосеточные переобуславливатели двух типов: квазииерархические многосеточные переобуславливатели (параграфы 3.1-3.5) и квазииерархические многосеточные переобуславливатели с

использованием метода фиктивных областей (параграфы 3.6-3.9).

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

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

О0 С üi С • • ■ С Пр и соответствующая последовательность регулярных треугольных сеток wк, к = 0,1,..., р, с шагом hk (по построению, hk = hk-1/2 для к > 1).

Для значений к = 0,1,... ,р вводятся следующие обозначения:

Nk - множество узлов сетки шк , принадлежащих \ сЮр;

пк - число узлов в множестве Nk;

V^-пространство кусочно-линейных в области Qk функций, обращающихся в нуль на dflk П дПр.

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

Формулируется конечноэлементная задача на сетке шр: для заданной функции f € ¿2(Ор) найти функцию ü G Vp такую, что

J^VüWvdx = Jafvdx Mv € Vp. (39)

Задача (39) сводится к системе сеточных уравнений

Аи = д ' (40)

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

Строится последовательность матриц конечноэлементного типа

Ле^,^-1'.....^''^'0' (41)

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

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

Для значений к>1 матрица А^ имеет блочную форму

А(к)

Ак) Лк)

Л11 л22

л(к) Ак)

Л01 Ло

}

*21 л22

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

где блок В^у , в отличие от соответствующего блока матрицы А^ , является диагональной матрицей.

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

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

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

Теорема 3.4.1. Для значений к = 1,2,... ,р собственные числа матрицы В^ А^ принадлежат отрезку [3/4,5].

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

Принимая за основу представление (42) двухсеточного переобуславливате ля, для значений к = 1,2,... ,р последовательно определяются матрицы

В® А®

4? Ш^ + А^В^А®

М(к) _

где

' Ri0) = А(0) f R(k-1) _ ¿(A-l)

для

для

к = 1 , 2 <к<р.

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

Матрица М = М^ называется многосеточным переобуславливателел для матрицы А. Доказано следующее утверждение.

Теорема 3.5.1. Справедлива оценка

cond (М'1 А) < (51 + 16л/15)/7.

Приведена процедура QUASI MG PREC/М^ решения системы уравнений с матрицей М^ , где 1 < к < р. Показано, что число арифметических операций Аор3, затрачиваемых на решение системы с матрицей М, пропорционально числу узлов пр самой мелкой сетки.

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

Здесь, в отличие от предыдущего подхода, процесс построения сеточны> областей начинается с многоугольной области (р > 1 есть некоторое цело« число), которая является объединением равносторонних треугольников, самы> мелких, с длиной стороны hp. Предполагается, что любые два треугольника либо не пересекаются, либо имеют только общую вершину, либо только общую сторону. Рассматривается случай, когда сеточная область Qp выпуклая Переход на более грубую сетку осуществляется путем иерархического укрупнения треугольников, то есть, путем объединения их в так называемые суперэлементы (четыре мелких треугольника объединяются в равносторонние треугольник с длиной стороны /ip_i = 2hp). При этом вблизи границы облаете появляются, как правило, "неполные" суперэлементы, которые дополняются до "полных" присоединением недостающих "мелких" треугольников. В результате, увеличивая шаг сетки в два раза, получаем новую, расширенную сеточную область; соответственно, суперэлементы превращаются в треугольные элементы расширенной области. Итак, взяв некоторую сеточную область Ц,,

где р > 1, в качестве исходной, и руководствуясь описанной выше процедурой, :троится последовательность расширяющихся областей

Пр С 1 С ... С По (43)

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

шр, a)p_i,...,w0 (44)

^соотношение шагов: hk-1 = 2hk). Построенные сетки называются FD-кбазм-иерархическими (аббревиатура FD (Fictitious Domain) указывает на метод фиктивных областей, который используется для построения многосеточных лереобуславливателей на этих сетках). Используемая версия метода фиктивных областей несколько отличается от классической версии этого метода. Каждый раз, укрупняя сетку, осуществляется расширение сеточной области з пределах узкой приграничной полоски, ширина которой соизмерима с шагом :етки.

В параграфе 3.7, на последовательности сеток (44), строятся конечноэле-\лентные матрицы А^ с помощью соотношений

vTA{k]u = [ VüVvdx Vu,v ,

-де ü и v есть кусочно-линейные восполнения сеточных функций и и v, :оответственно, обращающиеся в нуль на границе области П*. Далее, для

матриц А^ , где 1 < к < р, строятся FD-квазииерархические двухсеточ-ные переобуславливатели F^ .

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

Теорема 3.8.1. Для значений к = 1,2,... ,р собственные числа матрицы Fk~l А^ принадлежат отрезку [1, (7+л/17)/2].

В параграфе 3.9 излагается построение FD-квазииерархического много-оеточного переобуславливателя для матрицы А = А^ с использованием знутренних чебышевских итераций. Многосеточный переобуславливатель М :троится рекурсивно, от одного уровня к другому, вплоть до самой грубой сет-<и, где система сеточных уравнений решается с помощью некоторого прямого

"етода: M«, ...,м^ = м.

Теорема 3.9.1. Справедлива оценка

cond (М'1 А) < 9.47.

Дана процедура FD/QUASI MG PREС/М^ решения системы уравнений с матрицей М^ , где 1 < к < р. Показано, что число арифметических операций Agps, затрачиваемых на решение системы с матрицей М, пропорционально ■|ислу узлов Пр самой мелкой сетки.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

2. Разработана техника построения оптимальных алгебраических многосеточных переобуславливателей с внутренними чебышевскими итерациями для иерархических треугольных сеток, основанная на разбиении сеток на подструктуры (АМ/Б-версия). Построены многосеточные переобуславли-ватели для

• кусочно-линейной аппроксимации;

• кусочно-полиномиальных аппроксимаций высокого порядка (второго и третьего).

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

• предложены три версии алгебраических многосеточных переобуславливателей с внутренними чебышевскими итерациями (АМ/Б-версия, АМН-версия и гибридный вариант АМН-версии);

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

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

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

• квазииерархические многосеточные переобуславливатели;

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

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

1. Ю.Р.Акопян. Вариационно-разностный метод решения первой краевой задачи для параболических уравнений на регулярной сетке.- Молодой научный работник, изд-во ЕГУ, Ереван, No.2(30), 1979, 57-69.

2. Ю.Р.Акопян. Оптимальная явная вариационно-разностная схема для параболических уравнений с правой частью из L2 - В сб. "Применение

методов теории функций и функционального анализа к задачам математической физики (доклады VII советско-чехословацкого семинара, Ереван, 1981), изд-во ЕГУ, Ереван, 1982, 23-27.

3. Ю.Р.Акопян. Явная вариационно-разностная схема для параболических уравнений с правой частью из L?.- В сб. "Прикладная математика , изд-во ЕГУ, Ереван, вып.2, 1983, 5-19.

4. Ю.Р.Акопян. Оценка скорости сходимости в L2 явной вариационно-разностной схемы для параболических уравнений .- В сб. "Вариационно-разностные методы в математической физике , часть 1 (под ред. Н.С.Бахвалова и Ю.А.Кузнецова), Москва, Отдел вычислительной математики АН СССР, 1984, 12-25.

5. Ю.Р.Акопян. Об одной неявной вариационно-разностной схеме на регулярной сетке для параболических уравнений,- В сб. "Прикладная математика', изд-во ЕГУ, Ереван, вып.4, 1986, 12-22.

6. Ю.Р.Акопян. Вариационно-разностные методы решения параболических уравнений - Numerical Analysis and Mathematica.l Modelling, Banach Center Pubhcations, v.24, PWIM- Polish Scientific Publishers, Warsaw, 1990, 465-472.

7. Ю.Р.Акопян, Ю.А.Кузнецов. Алгебраический многосеточный метод решения конечноэлементных сеточных уравнений на иерархических треугольных сетках- Препринт No.250 (1990), Отдел вычислительной математики АН СССР, Москва, 1-26.

8. Ю.Р.Акопян, Ю.А.Кузнецов. Алгебраический многосеточный метод для треугольных сеток,- В сб. "Архитектура ЭВМ и численные методы", (под ред. В.В.Воеводина), М., Отдел вычислительной математики АН СССР, 1991, 3-32.

9. O.Axelsson and Yu.R.Hakopian. Algebraic multilevel preconditioners for perturbed finite element matrices - East-West J. Numer. Math., vol.5, No.l (1997), 1-22.

10. O.Axelsson and Yu.R.Hakopian. Hybrid-type algebraic multilevel preconditioned for perturbed finite element matrices.- East-West J.Numer. Math., vol.6, No.3 (1998), 167-184.

11. O.Axelsson, Yu.R.Hakopian and Yu.A.Kuznetsov. Multilevel preconditioning for perturbed finite element matrices.- IMA J. Numer. Anal, 17 (1997), 125-149.

12. Yu.R.Hakopian. Algebraic multilevel/substructuring preconditioner for third order finite element approximation.- Report No.9538 (1995), Department of Mathematics, University of Nijmegen, The Netherlands, 1-18.

13. Yu.R.Hakopian. Algebraic multilevel/substructuring preconditioners for perturbed finite element matrices - Report No.9631 (1996), Department of Mathematics, University of Nijmegen, The Netherlands, 1-22 .

14. Yu.R.Hakopian. Algebraic Multilevel Preconditioning for Second Order Finite Element Approximation.- In:" Computer Science and Information Technologies" , Proceedings of CSIT Conference, Yerevan, Armenia, 1997, 261-263.

15. Yu.R.Hakopian. Algebraic Multilevel Preconditioning in Finite Element Method With Piecewise Cubic Approximation.- In:" Computer Science and Information Technologies", Proceedings of CSIT Conference, Yerevan, Armenia 1999, 107-109.

16. Yu.R.Hakopian and Yu.A.Kuznetsov. Algebraic multigrid/substruc-turing preconditioners on triangular grids.- Sou. J. Numer. Anal. Math. Modelling, v.6, No.6 (1991), 453-483.

17. Yu.R.Hakopian and Yu.A.Kuznetsov. Algebraic multigrid/substruc-turing preconditioners on quasihierarchical triangular grids - East-West J. Numer. Math., v.l, No.2 (1993), 87-110.

18. Yu.R.Hakopian and Yu.A.Kuznetsov. Algebraic multigrid/fictitious domain preconditioners on quasihierarchical triangular grids.- Russian J. Numer. Anal. Math. Modelling, v.9, No.3 (1994), 201-222.

ULTOnOUQhn

3riLflfl HrupbOll ^LUl^npjUjO

«=iiu0pujhw2ilujl)iuQ pujqdiugiuQgaijtiG i4bpujiLjUJji5ujOaiilnpti£Cihp L[bp2UJi[np inuuppiujhD i5iuiriptigQbp|i huiijuup»

Yuri R. Hakopian

"Algcbraic Multigrid Preconditioned for Finite Element Matrices"

UinbGiufununt.pjruGrud liiunrugqiud L hbuiLuqninilwc!» bG hmGpiuhuJ2-ijaiLjaiQ piuqi5aigmGgiuj(iD ilbpujiiiujjtfuiGiuilnptoQbp 4bpgui4np iniuppiuj^G Jpi5buip|ilj qpuiLiujG npn2JiuL Ciiuuip|igGbpp huutiwp, npnGp ujnujgujGnLti bQ jpL)^uji|iujQti qdujjpG tiJiLqLnwljujG hiuilujuuipruCiGbpti ptlwjfiG irn^wG iiui5iuGiul|: Pn[np LjiunnLgiluid i|tipujaiLujL5ai0Lut4npfi£0tipD u|iuml(LuGni.i5 bG OLyinfidiui (npn2iul|h fifiwumnil) ilbpuiuiuijCiiuQiuilnpti^Qbpfi quiufiG: Dpiqbu jbpfipG puibpiughnG DQpujguuLjujpqbp oqmiuqnp6ilrui] bG ^bp^UjuiG mpuqh linbpujgfiuiGbpp: <-lbpu)ujujji5ujGuji{npfi£Gbpfi bpljpuj^ujiJiwljwQ hfitip bG iwGqpuuiQnLti fiD^ajbu h[:bpujpfu|iwljwG, iDjQujbu t[ pLlujqhhhbpujplnliujLiajO giuQgbpp: UinujgijujA Onp L hfii3Quj(^LuQ wpqjruGpGbpQ hiutfiunniniubh ?aipujqpilnLd bQ uuinpla.

LT2luL)Uuj6 t htibpaipfupLuLjUjO bnujGL|jniG giuGgbpp huidujp GbpgpG >bph2bjujG (unbpiugfiiuQbpnil oujmpduj[ hiuGpujhiu24ujl)UJG piuqCimgujQgujjpG ^bpujinaiji]ujGiui|npp£Qbph l]uintugCiiuG inbfuGhl|iu: Ipai h|ii3iuG ijpuj Ljiunni.gLlw6 jG piuqtiujgujGguijfiG ilbpujLqujjJujOujilnpli^Ohp'

• L|innp-wn-4mnp qduijfiQ dnuiiupl|ni.i5Qbpp hwCiujp,

• piupdp liujpqp ( bpljpnpq U bppnpq) l)innp-iun-l|innp pwqi5iuGqiui5iuj|iG . i5ninuipl]rui]Gbpfi hmtiuip:

Ii2wb4w6 b mbuiubiuGnpbG hhi5Giuilnpiluj6 t ouim|idwL hiuQpwhiu24wL|wG 3iuqi5ujgujDgujjpG L|bpujujujji5Lu0ujitnp^Gbp|i bLunnL9l3uj0 Cnn Jbpnphb^. npf1 ihdfinlti qOLjlu6 t uLjqpGiul^ujG i|bp2wl|np iniuppwjpD tiujinpfigGbpfi

H

I gmftiiurjmn'lTi piuQmpmdmUuuin l]imi|(tmitoi|lufri ]iL(mmiJqhlo ijrjmümnlmpmij gmfimmqta ilorn^üq

OOl- .timgmcJrnhis 08 üqfiuim^

. rdpmpumÜLjh ijtjudqp i|UqgdfniUi|m |ii|inhi|<fc Jqg?i|du|imgmpfmlTimdq]i gi|fm6gmßmpbmd gmfirmjnjdmdqi|i(ijbm|itf • 'dqg?tjüu}imgmpfmhimUq|i gi|fmßgmßmpbmd gmlimi(ri|dmdqi|i|i|bm]i3 •

Jimüqddmm lulidq LjüqrjTilüutimompfmhnmUq'li i]hi|ui bím gq pmjidujimgpiln gqdugmtimnqm q çmjilimZfi :mh)i|ga|qm q mhijbudqp gmpßiuamh) Jdqg?iJüulimgmpfmhnmüq|i gi|fmßgm6mpbmd gmhmJiZmqmdgmq "Impijmfrio Jmpmq i|dqßgmß guiftigmuq gmh|mi|rl|dmdqi|ql|bmticî } çm]ihimZf|

: Umpmq

jmpçiul i|dqgpiudmnmfimn gmlimludmdmtn öpiuumdijti i|fmh|i|bu€!qp jmpßiuumh i|dqg?L|dutimgmprmhimdqJi gL|fmßgmßmpbmd dmpmij ]dqr)6i|üinmp gijímüdmin dujim3üq]i çm]ïlim]imbm } çm|iuiubminqi) •

'q3i]p ijfid ihugmi|bgü i|dqghmli dmtimp gmpqudin i|ßgmß q L|dmpmq ijtimiidmfimp ijßgmß duZuriJmgqpm rimh gmhminuinlmpi|nm } ¡pmjißminn q ödijliga| gmpßmbL|pijgiJp Jjid L|dqghmlidmhmp bufiçûubminbo gmpqudm ijßgmß } çmliçiul •

'fimdqddmm dqdq i|dqg?i|du]imgmprmhimdqji gijimß gmßmpbmd fiudqgmi|6mdqmi| gmfqZiJdq? gijídqg gq çmjitidmômum •

,piuilu ligo :Dpiußmbi|pi|gi]p ij]ié i|dqghmb dmf]mp gmpqudin i|ßgmß ;] gf|mmmlmg дтрЬггфтЬт tifp :üpiubm]imbm