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

РОССИЙСКАЯ АКАДЕМИЯ НАУК р^СТИф^Т ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ

') У НП'1

ь. ПУН На правах рукописи

УДК 519.6

ВАСИЛЕВСКИЙ Юрнй Викторович

Итерационные методы с разбиениями на большое число подобластей

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

АВТОРЕФЕРАТ

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

Москва 1993

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

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

Официальные оппоненты: доктор физико-математических наук ЗЛОТНИК А. А. кандидат физико-математических наук МАЗУРКЕВИЧ Г. Е.

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

Защита состоится " (^ё&И^Р^ 1993 г. в I ^ часов на заседании специализированного совета К 003.47.01 в Институте вычислительной математики РАН по адресу: 117334, Москва, Ленинский пр-т, 32а.

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

Автореферат разослан "_"_ 1993 г.

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

Общая характеристика работы

Актуальность темы. В последние десять-пятнадцать лет интенсивно развиваются численные методы, кЬторые сводят решение краевых задач в областях сложной формы для эллиптических уравнений второго порядка к решению аналогичных задач в простых областях и основаны на разбиении исходной области на более простые подобласти. Такие методы получили название "методы декомпозиции области" ("domain decomposition (DD)") или "методы разбиения области". Особую актуальность эти методы приобрели в связи с появлением многопроцессорных вычислительных систем. Методы декомпозиции области позволяют решать задачи в подобластях независимо друг от друга на разных процессорах, обмениваясь время от времени информацией между процессорами. DD-методы обладают тем преимуществом перед другими эффективными методами решения эллиптических уравнений, что они естественно параллелизуемы, то есть процесс распараллеливания в них очевиден и нагляден для исследователя. Часто DD-алгоритмы определяют через DD-переобуславливатели, для решения систем с которыми достаточно решать системы с матрицами жесткости в подобластях. Под переобуславливате-лем мы понимаем симметричную положительно определенную матрицу, эквивалентную по спектру матрице жесткости в исходной области. Среди критериев для сравнения различных DD-переобуславливателей можно выделить такие, как зависимость границ спектра переобусловленной матрицы жесткости от числа неизвестных, числа подобластей, структуры разбиения, возможного скачка коэффициента диффузии (для оператора диффузии), простота программной реализации и т. д. Исследование свойств известных DD-переобуславливателей и улучшение соответствующих спектральных характеристик представляют собой актуальную научную и прикладную задачу. В настоящей работе рассматриваются два базовых варианта метода декомпозиции области: DD-переобуславливатель типа Нейман-Дирихле и DD-переобуславливатель типа Нейман-Нейман.

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

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

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

1. Конструирование методов декомпозиции области с приближенным решением подзадач.

2. Построение ВВ-переобуславливателя, оптимального по арифметической сложности.

3. Исследование и развитие двух вариантов метода декомпозиции области: ВВ-переобуславливателя типа Нейман-Дирихле и ВВ-переоб-уславливателя типа Нейман-Нейман.

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

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

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

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

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

Апробация работы. Основные результаты диссертации докладывались на:

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

• 2-й Всесоюзной конференции по проблемам численного анализа (Тбилиси, 1989), 3-м Международном симпозиуме по численному анализу (Москва, 1992), 1-м Российско-финском симпозиуме по численному анализу (Юваскюла, Финляндия, 1992), DFG-симпозиуме по параллельным алгоритмам для параллельных вычислительных систем типа MIMD (Ганновер, Германия, 1993), 10-м Франко-итало-российском совместном симпозиуме по вычислительной математике и приложениям (Москва, 1993).

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

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

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

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

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

В параграфе 1.1 приведены теоремы продолжения функции в классе пространств Соболева, а также рассмотрены основные способы продолжения, применяемые в доказательстве теорем для пространства Соболева И^П). Кроме того, здесь вводится класс следов функций из И^П) на границе дП и формулируется теорема о следе в классе функций из И^П).

В параграфе 1.2 рассматриваются сеточные аналоги теорем из § 1.1: вводятся различные классы триангуляции, задается конечноэлементное пространство И^1 (,(П) и формулируются сеточные аналоги теоремы о продолжении функции, а также теоремы о следе функций из класса И^1 ДП).

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

. [ «1(х(), ц е п£иг\

I Л(

где Щ—квадрат со стороной и центром в точке х? 6 П^ являющейся образом узла Х{ триангуляции П^ при отражении относительно Г; Л; — характерный размер треугольников, имеющих в качестве вершины узел Х{. Отметим, что в обоих случаях арифметические затраты на реализацию этих вариантов продолжения сеточной функции пропорциональны числу узлов в триангуляции ПЛ.

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

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

В параграфе 2.1 исследуется возможность применения внутренних итерационных процедур с переобуславливатёлем для задач в подобластях при использовании ВБ-переобуславливателя типа Нейман-Дирихле. Пусть П — ограниченная область из Л", п — 2,3, с кусочно-линейной границей Определим билинейную форму

а(и, у) = ап(и, и) = J(a.Vu • Чь + иу) Лх, (2)

п

где а(х) — кусочно-постоянная функция, удовлетворяющая условию ¡п£а > 0. Пусть N — число вершин симплексов некоторой триангуляции Ол области П. Определим симметричную положительно определенную N х Л^-матрицу А через соотношение

(ЛЙ, V) = ап{и,ь) V«, ¿Т £ Я", (3)

где и, V — кусочно-линейные восполнения в И/21Л(П) векторов й,ь.

Разобьем множество треугольников из П* на два непересекающихся подмножества ПрП* и образуем из треугольников этих подмножеств области П] и Пг с фиксированной общей границей Г = Г![ П Пг, то есть построим разбиение О на две непересекающиеся подобласти и Пг- Разобьем множество вершин треугольников из П* на две группы. В первую группу отнесем вершины, принадлежащие П] и Г, во вторую — вершины, принадлежащие Пг, то есть все остальные вершины. Пусть число вершин в 1-й группе равно /V,-, £ = 1,2. Тогда матрицу жесткости А можно представить в блочном виде

л-{%£) «>

с м х ^—подматрицами Лу.

Зададим с помощью соотношения

= аП|(и,«>) Уи,« е ^2[А(П,), (5)

где и,ь € Ж^П)) обозначают восполнения векторов и,И £ Я^', симметричную положительно определенную N1 х Л^-матрицу Ащ. Определим матрицу В — Вт > 0 по формуле

д _ / + АцА^Ап АП \ ^

V М\ М-1 ) '

задающей метод декомпозиции области с альтернирующими краевыми условиями Нейман-Дирихле, поскольку для решения системы с матрицей В необходимо решить подсистему вида А\цг\ =51 и дважды подсистемы вида л22 ¿2 = 91-

Пусть В\ и £2 — симметричные, положительно определенные соответственно х и N2 х N4 -матрицы, удовлетворяющие условиям

>ч(в2У2, й) < (А22И2>И2) < А2(В2И2,а2) Чъ е (7)

О < А1 < Ль о < а2 < л2.

БВ-переобуславливатель типа Нейман-Дирихле с применением внутренних итерационных процедур имеет вид:

М А* .Щ»))' (8)

где

4 I 1

<Г'Ы = [11-11 (Ь - (9)

Я-1 (и) = \12 - П (Ь ~ Г^А22)}А^, (10)

1{— единичная матрица порядка Ni, г = 1,2; т^ — чебышевские параметры, соответствующие многочлену Чебышева первого рода, приведенному к отрезку [Д1; Л.х]; ту — параметры, обратные корням многочлена

т /да+>2-а.\

Ри(х) = —^

{л\1>.\\ ( Тр(х) —многочлен Чебышева первого рода, приведенный к отрезку [—1, 1]) и упорядоченные по схеме, гарантирующей устойчивость счета.

Теорема 2.1.1. Если триангуляция 0Л квазиравномерна с параметром /¡, а(х) = 1, х € П, то при

\og\h Р2

Зр(В~1А) С Ы1+7,)], (11)

где

2р1 ,. У^-У^

, С2 некоторые положительные константы.

В параграфе 2.2 рассматривается обобщение ОВ-метода типа Нейман-Дирихле в форме аддитивного варианта метода Шварца.

Пусть а = 1 в = а в Пг, = = от, Л] = Лг = Д, х N-матрица Т — матричное представление оператора продолжения сеточной функции ТЛ, рассматриваемого в § 1.3. Зададим симметричную положительно определенную N X ЛГ-матрицу В через ее обратную:

В'1 = ГВ,-1ГГ + (12)

Теорема 2.2.2.

Бр(В~1А) С

2(1+С)

4(2 + аС)Р ' а

(13)

где

||ТА|| <С + \.

В частности, при а < 1 С [4(2+'с)£ > ^ТГ^] > то есть границы

спектра не зависят от скачка коэффициента диффузии.

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

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

В параграфе 3.1 БО-метод типа Нейман-Дирихле (6) применяется к случаю разбиения исходной области на полосы. При этом многосвязные области Г21 и Пг состоят из чередующихся полос шириной (1 (см. рис.1). Показывается, что число обусловленности переобусловленной матрицы жесткости не зависит от регулярной триангуляции и пропорционально <1~2, где <1 — минимальная ширина полос.

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

Введем новые обозначения fi^ = ííj, a^(u,v) — ai(u,v), Л^ = A\N и = Ni- Затем, аналогично изложенной выше процедуре, разобьем область Í)'1) на две непересекающиеся подобласти и По' с общей границей и на основе блочного разбиения матрицы А'1)

построим DD-переобуславливатель В'1) для матрицы Л1»:

,<•> _ ( 4V А® ) (1) _ I В<1> + ЛМГ^У А® ) (и) А ~ {4i> а® )' в 4? ) ■ (14)

Здесь A¡:' являются

лг!') X лг!'>

-подматрицами, i,j — 1,

2; 7V(0 х NP-

матрица 4^ задается с помощью соотношения (4^, w) = an<i)(v,w), которое предполагается выполненным для всех функций v,w G Wj обращающихся в ноль на 7W, а симметричная iv[1' х TV,''-матрица определена уравнением (Z?¡JV, w) = Vv,w 6 Wj

Результирующий двухуровневый DD-переобуславливатель Вц для матрицы А мы определим формулой

Предположим, что область П покрыта некоторой квадратной сеткой Gd с фиксированным шагом d, а пересечения квадратов этой сетки с областью Q задают способ ее разбиения на подобласти. Сетка G¿ строится таким образом, чтобы ее линии и граница дП всегда являлись объединением сторон треугольников из

Множество полученных подобластей разобьем на три подмножества, являющихся многосвязными подобластями Q2, П,1', íí^j как показано на рис.2. Такое разбиение автоматически порождает блочно-диагональные подматрицы А22,А^2 ,В\\\ поэтому при решении системы с матрицей Вц нам нужно решить 0(d~2) независимых подсистем на "элементарных" подобластях. Следовательно, процесс решения системы с матрицей Вц легко параллелизуем.

iii

П]

П<'> п<" п<" п<'> п >)

п<'> п. п<" П, (1 1)

п<" п<" П<'> 0<" п О п?> п<"

п<" П] п<" П, п >) П.

п<" п<'> п<" п<" 0 1) (!<■>

п<" п, П] п 1) п»

п<" п<" п<'> п ■) п<"

f ff n

f * ..... «r

ж & M 4'

: ;

n

n

n

tl

Рис.1. Рис.2. Рис.3.

Теорема 3.2.4- Если а(х) = 1, х G П, (см.(2)), то границы спектра матрицы BJilA в случае разбиения, изображенного на рис.2, принадлежат отрезку

[1, c.ce d-2], (16)

где cj, Cg не зависят от П , d .

Замечание 3.2.5. Пусть функция а(х) постоянна в каждой из элементарных подобластей множеств Пг, Г&2 ^ | ^ и удовлетворяет следующим требованиям:

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

• в любой элементарной подобласти fijj) из множества П^ функция а(г) меньше, чем а(х) в соседних с П^! элементарных подобластях из

ni1'.

Тогда теорема 3.2.4 остается верной и в этом случае, причек константы Ci, cg (см.(16)) не зависят от скачка функции а(х) на границе между элементарными подобластями .

В параграфе 3.3 двухуровневый метод распространяется на случай разбиения исходной области П на подобласти fi; — треугольники некоторой квазиравномерной триангуляции П^ с параметром d. Подобное обобщение стало возможным благодаря использованию идеи многоуровневости и результатов параграфа 2.2. Однако число обусловленности в этом случае хотя и не зависит от Я\ но пропорционально d~4. Выйти из этой ситуации можно, примененив внутренние итерационные процедуры из § 2.1. Это приведет к тому, что число обусловленности переобусловленной системы не будет зависеть от ЯЛ и будет пропорционально d~2 .

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

драты (п. 3.4.1). Цель применения каркасного пространства — избавиться от зависимости числа обусловленности от — достигается благодаря решению краевой задачи на каркасной сетке. В пункте 3.4.1 каркасное пространство Ус вводится как подпространство функций из

Ц = {V 6 Щ',л(П(1), Г0): V = г, на I € ии г, е Л1; (17)

« = г/;Лагт(иП(.))}.

Здесь щ — множество индексов элементарных подобластей П^1] из множества Туьаггп — оператор дискретно-гармонического продолжения функций из И'гДП^) до функций из И^ДП*1)) :

-Л

^1,)>агти1 —

(18)

К Э (Рнщ)(х) =

Определим проектор Рл на подпространство Ус следующим образом: пусть щ € И'аДО'1)), тогда

£ I х е 0$, . в ии

<-> (19)

х е

Пусть А^1' X ЛГ^-матрица Р — матричное представление проектора Р/,.

Введем векторный аналог пространства Ус —подпространство Нч пространства й'''1', состоящее из векторов, компоненты которых равны значениям функций из Ус в узлах триангуляции П^ПЙ'1^. Пусть Мц — число элементарных подобластей в множестве Ми х /УС'-матрица Рс осуществляет тождественное отображение пространства Д^" в пространство Яг, а х Л/^-матрица Ас — матрица жесткости, соответствующая конечноэлементному пространству, заданному на равномерной триангуляции сетки (¡¡и, линии которой параллельны осям координат и проходят через центры элементарных подобластей

П[1} (рис.3).

Определим симметричную положительно определенную М1' х ./V'1'-матрицу

№ через ее обратную

[¿0)]-1 = (/ _ р)[в(1))-1(/ _ Р^) + РсА:хР?, (20)

где I — ЛГО х ТУ^-единичная матрица; матрицы Р, Ас, Рс определены выше. Тогда БР-переобуславливатель с применением каркасного пространства будет иметь вид

Ь^ЯЬ + Л^А» А^у (21)

Теорема 3-4.1. Если а(г) = 1, I € П, (см.(2)), то границы спектра матрицы Вц1А принадлежат отрезку [ с9,сю ], где константы с9,сю не зависят ни от П'1, ни от ^ .

Отметим, что если функция а(х) удовлетворяет условиям из § 3.2, то теорема 3.4.1 остается в силе, причем константы сд,сю не зависят от скачка функции а(х) на границе между элементарными подобластями.

В пункте 3.4.2 изложенная в § 3.4.1 методика применяется для устранения зависимости от числа подобластей в простейшем методе декомпозиции с разбиением на полосы (§ 3.1). Пусть многосвязные области Пх, Г2г состоят из чередующихся полос ширины ¿(см. рис.1). Покроем область Г2 квадратной сеткой С л с фиксированным шагом (I, пересечения квадратов этой сетки с областью П задают способ ее разбиения на подобласти, причем каждая подобласть принадлежит одной из полос П^ГЬ- Множество полученных подобластей разобьем на три подмножества, являющихся многосвязными подобластями Пг, Пг > как показано на рис.2.

Блочное представление матрицы Л, соответствующее разбиению на полосы П1, П2, и соответствующий ВВ-переобуславливатель будем обозначать через

А = ( 1 В = ( ВП + ^

и« АП Ап Л22 ) '

где Л у, *,У = 1,2, — х Л^-подматрицы; N1—число узлов в области 1; N2 — число узлов в области Пг.

Блочное представление матрицы А, соответствующее разбиению на подобласти > , будем обозначать простыми заглавными буква-

ми, как в § 3.2, и п. 3.4.1.

Вместо каркасного пространства Ус — подпространства 1У2'/Х^'1') (17) — рассмотрим каркасное пространство \¥с — подпространство И^1 Л(Я):

\¥с = {у £ И^ДП) : V = п на 0$, 6 Щ, г,- 6 Я1; (22)

V - линейна наП^ П П^ V = Т£агт(и\й1)},

Тнагт— оператор дискретно-гармонического продолжения функций из И72 д(01) до функций из И^'^П).

Определим проектор на подпространство \УС следующим образом: пусть и] 6 И^'^О), тогда

РнЩ, х е П^,

,.т&'™„,ПЛ(РЛи,)|п(,), ж.еП^ПЙ,, (23) т£гт(<?ли.) к, ' I е Й2.

ЪУС Э (дЛ«,)(х) =

Пусть TV X TV-матрица Q — матричное представление проектора Q/,, а N2^ X TV-матрица Qc осуществляет тождественное отображение пространства RNu в векторный аналог пространства Wc.

Определим симметричную положительно определенную TV X TV-матрицу В через ее обратную

В-1 = (/ - Q)B-\I - QT) + QcA;lQl (24)

Теорема 3-4.9. Если а(х) = 1, i 6 П, (см.(2)), то границы спектра матрицы В-1 А принадлежат отрезку { сд,сю ], где константы сд,сю не зависят ни от Slh, ни от d .

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

Наряду с разбиением Q на полосы ill, Q2, определим еще одно разбиение П на полосы с шириной d, согласующееся с сеткой Gj, но в направлении, перпендикулярном полосам ПьПг- Блочное представление матрицы А и переобуславливатель 2?х типа (6), соответствующие разбиению на iiifUjiимеют вид:

А = f А И ^12 \ в _ i Ai + AuAnhi Ли \ 1^21 ^22/' Х \ Ац А22)'

где А^ — Nj х TVj-подматрицы, i,j = 1,2; N\ — число узлов в П £lh] TV2 — число узлов вЙ2П Slh.

Для М G N и любой области fl^l'i * 6 "ь определим область П(|,М) следующим образом: Q(i,M) = {1 £ | dist(x, П^') < Md}, где — полоса из такая, что Qj}' С В частности,П(»,0) = ft])'. Определим проектор Qh,M на подпространство Wc по формуле (23), где для х Е П^ оператор осреднения по области заменен на оператор осреднения по области fl(t, М).

Пусть N х TV-матрица Qm — матричное представление проектора Qh,M■ Модифицированный переобуславливатель Вм определим через обратную TV X.TV-матрицу

ВТ} = (/ - Qm)B~\I - Qh) + QuBllQTM. (25)

Как следует из экспериментальных данных, число обусловленности матрицы BjjA не зависит от и пропорционально d~l при оптимальном

М = ^"д41) что доказать теоретически не удалось. Таким образом, модифицированный метод каркасного пространства имеет много общего с методом расщепления по направлениям, однако имеет то преимущество, что переобуславливающая матрица является симметричной и положительно определенной, что позволяет использовать обобщенный метод сопряженных градиентов.

В параграфе 3.5 анализируется ББ-метод типа Нейман-Нейман. В п. 3.5.1 исходная задача сводится к задаче на разрезе •— границе между подобластями и исследуются свойства полученной этим сведением матрицы Шура. Пусть П — полигональная область, Го -— замкнутое подмножество д(1, состоящее из конечного числа отрезков прямых, Г1 = 9П \ Го, ПЛ— квазиравномерная триангуляция области П, причем множество Го Л Г1 принадлежит множеству вершин треугольников , п — размерность пространства И^Д(П, Го). Определим билинейную форму

а(и, V)" = а%(и, V) = |(Уи ■ VV + аиг;)ЛП (26)

11

и симметричную положительно определенную ( а > 0 или Го Ф 0 ) или полуопределенную (а = 0, Го = 0 ) п х гг-матрицу Ла через соотношение

(Аай, ь) = а(и, V)" ЧИ,Ие1Г, (27)

где и, V — кусочно-линейные восполнения в И^Го) векторов и, V £ Л".

Разобьем область П на М не' налегающих друг на друга подобластей П; диаметра таких, чтобы минимальный радиус круга, вписанного в каждую подобласть был порядка <1 и граница ОП,-, I = 1 ,...,М, проходила по сторонам треугольников из ПА. Пусть п,- — число узлов триангуляции ПА, принадлежащих П,-, а щ € Яп' —• вектор значений функций из Го), I = 1 ,...,М. Обозначим через ТУ,- прямоуголь-

ную n¿ X п-матрицу, состоящую из нулей и единиц, которая отображает вектор и; £ Е"1 в вектор и € Д", устанавливая соответствие между узлами П? и узлами

Определим п,- х «¡-матрицы А" через соотношения

«.•) = (Л?*. *<) ^ы,-, щ е Лп\

где и,-,«,-—восполнения в И^ДП.-.Го) векторов щ,% £ Я."', 1 = 1,...,Л/.

Пусть 7 = I) <ЭП,- \ Го — граница между подобластями, л = ЗП; П -у. Разбив узлы П*1 на две группы — принадлежащие внутренностям П(, I =

-141,... ,М ( r»i узлов), и лежащие на 7 (п7 узлов), — перепишем матрицы A", Af в блочном виде

A° = (f Л1°)> * = Л?) W

\ ЛТ1 7 / V A71,¡ Л7,< /

с n,-i7 х rij 7-подматрицей A°h где п, 7—число узлов ПА, лежащих на 8ÍIДГо-Матрицу N¡ также представим в блочной форме: N¡ = (Na, Ni-,). Определим n7 х п7-матрицу S" :

(29)

Глобальные матрицы A", Sa могут быть получены ассемблированием локальных матриц A", S":

Aa = Z NA?NT, 5° = Е NiyS?NT, (30)

1=1 i=i

ГДе а а а а -1 о

S? — ~ Aj¡,i[All,¡) Aly.i- (31)

Далее в п. 3.5.1 отмечается, что число обусловленности Sa пропорционально Л-1 при фиксированном разбиении на подобласти, и показывается его пропорциональность d-2 при фиксированном числе узлов внутри каждой подобласти.

В пункте 3.5.2 вводится DD-переобуславливатель типа Нейман-Нейман по формуле:

Ha = Y.NhHfNjv Щ = AIS?]"1 Д, «>0. (32)

i

Матрицы Д = diag{d\, di,..., dn¡i} являются локальными матрицами взвешивания и удовлетворяют условию: Е NyDiN^ = /, где I — единичная

¡=1

матрица порядка п7.

Анализ спектра матрицы HaS° при а = 1 проводится в рамках аддитивного варианта метода Шварца.

Теорема 3.5.1. Sp(HlSl) С [1, с(1 + log£)max{^;log jj}J. В пункте 3.5.3 описывается метод балансировки, введенный Я. Ман-делом для оператора Лапласа.

Для простоты рассмотрим случай а = 0, Го / 0. Пусть ia={1, ..., М„}

— множество индексов подобластей П;, для которых 9Г2;ПГо = 0; z¡ £ R"'1

— вектор, компоненты которого равны единице,

Обозначим через Р ^-ортогональный проектор на W и зададим пу х пу-матрицу м

= (33)

¡=1

Определим пу х п7-матрицу Н% = Нйи > 0 :

H°M = ((I-P)T0S0(I-P) + P)S°~l. (34)

Теорема 3.5.2 (Я. Мандел). Sp (Я^5°) С [1, С],

ГЖЕ^ВЩ d

С= sup -тр-- < const ■ (1 + log2 -). (35)

Vvi—0i£i, $t£Rl j=j » '"5?

Далее метод балансировки распространяется на оператор Гельмголь-ца. Пусть а = 1, Го = 0. Разложим пространство Я"7 на два подпространства:

= : («?,ё)=0, е = (1,..., 1)т },

H2 = {ve R^ : i1=9-е, в G Я1 } и определим проекторы Fj на Я(, » = 1,2, следующим образом:

P2ii=ip^-e Р1=1-Р7. (36)

(е,е)

Зададим п7 X пт-матрицу Нм по формуле

Н1, = РХН*МРТ+±Р21Р1. (37)

Теорема 3.5-i. Sp (H^S1) С [ф, СС), где /?,с,С— некоторые положительные константы, не зависящие от Л, d, С из (35).

При умножении вектора г £ Я"7 на Н% необходимо решать системы с матрицей, соответствующей каркасной сетке. При достаточно большом числе подобластей (d —* 0) может возникнуть необходимость выбора пере-обуславливателя для этой матрицы, поэтому в пункте 3.5.3 исследуются ее спектральные свойства и предлагаются переобуславливатели для нее.

В четвертой главе изложен опыт реализации описанных в главе 3 методов декомпозиции на параллельной вычислительной системе. В § 4.1 приводятся основные характеристики транспьютерной системы, использовавшейся в экспериментах. Методы из §§ 3.1 и п. 3.4.2, перенесенные на случай параллелепипеда, разбитого на слои, применялись для решения линейной (§ 4.2) и нелинейной (§ 4.3) задачи. Число используемых процессоров равнялось 1, 2, 4.

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

1. Предложен метод вычисления нормы оператора дискретно-гармонического продолжения сеточной функции.

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

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

4. Устранена зависимость от числа подобластей в одноуровневом (при разбиении на полосы) и двухуровневом (при разбиении на квадраты) DD-методе типа Нейман-Дирихле благодаря применению каркасного пространства для DD-переобуславливателя.

5. На основе аддитивного варианта метода Шварца построены оценки спектра для DD-метода типа Нейман-Нейман для оператора Гельм-гольца. Метод балансировки, введенный Я. Манде лом, распространен на случай оператора Гельмгольца.

6. Проведены эксперименты по применению DD-методов из § 3.4 для решения на параллельной вычислительной системе нелинейной задачи об околозвуковом потенциальном обтекании препятствия в трехмерном канале.

Публикации по теме диссертации

1. Теорема о продолжении сеточных функций // Численный анализ и математическое моделирование,—М: ОВМ АН СССР.1989.-С.20-29.

2. Метод декомпозиции области с приближенным решением подзадач, // Численные методы и программное обеспечение.— М.: ОВМ АН СССР,1990. — С.23-29.

3. Теоремы о продолжении сеточных функций: обзор некоторых результатов (совместно с Непомнящим С. В.) / Научный отчет N1 по государственной научно-технической фирме "Математика и технологии". — М., 1991. — 25 с.

4. Методы декомпозиции области с приближенным решением подзадач // Численные методы и математическое моделирование.— М.: ИВМ РАН,1992.—С.21-34.

5. On numerical experiments with Neumann-Neumann and Neumann-Dirichlet domain decomposition preconditioned (jointly with Kuznetsov Yu. A., Manninen P.)/ Reports on Applied Mathematics and Computing N 3.—University of Jyvaskula, 1993. — 27 p.

6. On the implementation of DD techniques on the transputers for a 3D transonic potential flow problem in a channel / Technical Report N.93-3. — Mathematical Institute A, Stuttgart University, 1993. — 11 p.

7. On application of global coarse space for two-level domain decomposition method in the case of a large number of subdomains// Russ. J. Numer. Anal. Math. Modelling. 1993. Vol.8, N.l, p. 59-82.