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

Российская академия наук Сибирское отделение Вычислительный центр

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

Литвиненко Светлана Алексеевна

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

01.01-07 - Вычислительная математика

, 3 «да

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

Новосибирск 1997

Работа выполнена в Вычислительном Центре СО РАН.

Научный руководитель:

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

Официальные оппоненты:

доктор физико-математических наук, профессор Мацокин A.M. кандидат физико-математических наук, с.н.с. Ахмеров P.P.

Ведущая организация: ВЦ СО РАН, г.Красноярск.

t

Защита состоится " " X ^{',4/.', Zd 1997 г. в часов на заседании специализированного совета К 002.10.01 в Вычислительном Центре СО РАН по адресу: Новосибирск, 630090, проспект Лаврентьева, 6.

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

j'<) у/ • / ' if'

Автореферат разослан " -'W Ч*- "uCSti-A 1996 г.

Ученый секретарь Специализированного совета доктор физико-математических наук

Ю.И. Кузнецов

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

Данное исследование проводилось при поддержке РФФИ, грант 95-01-01530.

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

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

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

3. Разработка и исследование комбинации алгоритмов покомпонентного расщепления с явной схемой в подобласти с мелким шагом по времени.

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

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

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

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

Публикации и апробапия работы. По теме диссертации опубликовано пять работ. Основные результаты диссертации докладывались на 8-ой Всесибирской школе по методам вычислительной математики (Шушенское, 1993), конференции молодых ученых ВЦ СО РАН (Новосибирск, 1995), 9-ой Всесибирской школе по методам вычислительной математики (Шушенское, 1995), на научных семинарах ВЦ СО РАН.

Структура и объем работы. Диссертационная работа состоит из четырех глав, выводов и списка литературы. Объем работы - 85 машинописных страниц. Список литературы содержит 110 наименований.

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

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

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

fi - ограниченный, открытый, связный многогранник в Rm, m = 2,3, являющийся объединением системы непересекающихся многогранников т.е.

Ô = Uj=1fip, Пр П О, = 0, р ф q. (1)

В дальнейшем будем обозначать: Гр = дПр - граница подобласти Пр, Гм = ОрП П{, (р ф q). Далее, для каждого р = 1,..., s введем следующие множества индексов:

Jp,_ = 11 < q < р, measm_i(rM) ф 0},

Л.+ = i Р < Я < s, measffl_i(rp,?) # 0},

где measm_i(rP)î) - ¿ст-мера множества ГР), на многообразии размерности тп - 1, Jp = Jp>- U Jp>+. Сформулируем задачу Неймана с условиями идеального контакта следующим образом. При «о € ¿2 и / S X2((io.i»);-ff-1) требуется найти функцию и € Z2((io,/»);.flo), такую, что & € £2(^0, t.); Я-1) и для любого и € при почти всех t 6 (to,tt) выполняются равенства

(§(t),v) + a(t;»(i),v) = (f(t),v), (2)

(u(te),e) = (uo,e), (3)

где a(t; u(t), v) билинейная форма вида

л

p-i

a ap(t-,u(t),v) в свою очередь имеет вид

(5)

Здесь и далее Н1 - пространства вектор функций, задаваемых как произведение пространств Соболева для функций, определенных в подобластях.

Сформулируем задачу Неймана с условиями нендеального контакта в покомпонентном виде. Пусть «о £ ¿2 и / С ЬгЦ^о,и);Н~1). Требуется найти функцию ир £ £г((*0)**)> Н1)> такую, что ^ 6 Н~1) и V« е Я1 при почти всех ( £ (<о, ) вьшолняются

равенства

йи"

е /г («;(«) - = (/до,«л- (6)

(«'(*о),») = (ио,»>, (7)

где р > 0. Такой обобщенной постановке задачи соответствует следующая классическая постановка:

л« _

_ _

¿^Г + = 6 ^* ("рп п ^

— —

р4- и„ - и, = 0, г) 6 (£с, г.) X (Пр П П?) (Пр Г) П3 Ф 0),

мр(о,г) = и^(г), г б

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

Г« = {*ЕГР | С082(ПР13*)=1}. (8)

Кроме того, обозначим

Г(*> = и£=1г£*> П Г. (9)

Как нетрудно заметить, имеют место равенства

и« гГ№) _ Г) Г(4) р р(0 =

(10)

Введем множество номеров

| ГМСГ<*>}.

При этом, поскольку Пр - т-параллелепипед, то и^^ = Jp. И, наконец, пусть = ^ п Отметим, что если q е то граница Гм ортогональна вектору хк и и?€У(»)ГР1? = Г^'.

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

В п.2.1 приведена формулировка метода для задачи Неймана и выписано уравнение для ошибки. Сформулируем сеточную задачу Неймана в покомпонентном виде. Пусть N - некоторое натуральное число, г = {и - £0)/-М и г„ = ¿о + пт, п = 1,...,ЛГ. Требуется найти последовательность функций

такую, что иГ1+к!т б V/, и Vvk € V/, выполняются равенства

„я+Ь/га _ ,.п+(к-1)/т

«М-*-^-. »,*) + о^Чи+й и?к1тУр)

+- Е /г (РнХР+к/т - (И)

+1- Е I - = (/;•*,»*)„

«р = Па^«0,Р, (12)

где /;•* = 0, к <т-1 и = /Р(<„+1), и*/"-'1 = и°.

В п.2.2 проводится анализ сходимости предложенного метода. Справедлива

Теорема 2.2.2. Пусть для решения задачи (2), (3) используется метод (11), (12) при г < 1 и р — 0((Л+ г)!/2). Тогда имеет место оценка

||и" - и(<„)< с(М№2 + МУ'\ где М'н = ||и||(1) + (||и||(3) + |||¡|({оЛ))Л1/2, К = |М|(з) + ||£||((оЛ) +

Когда в области П задана согласованная сетка, оценка может быть усилена. При р = 0((А3'2 + г)1'2) оценка погрешности 0(Л3/4 + т1'2).

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

В п.2.4 рассматриваются вопросы распараллеливания алгоритма.

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

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

п+к/гп п+(4-1)/т

«М^--, + а«(*п+1; иГкЫ) +

-п УЛ^1+к/т - Рк^)РкА<1а = (/?'*, * = 1, ...,т, (13)

Р "и

<М~-+ а2(г„+1;и?+1,VI) + - / РК2^+1Рк^о

Т

= ^ Е иРк,хиТк'тРк^а + №п+1), v2)ъ (14)

Р к= 1 1.2

Ир = (15)

Для данного метода при р = 0((Л + т)1/2) оценка погрешности

В п.п.3.2-3.4 рассматривается комбинация метода расщепления с явной схемой в подобласти с мелким шагом по времени. Пусть -произвольный многогранник, П2 - т-параллелешшед. Сформулируем метод декомпозиции области решения задачи Неймана с использованием явной схемы в О1 и схемы расщепления в П2. Пусть N - некоторое натуральное число, т = (и — ta)/N нtn = + пт, п = Введем последовательность чисел {п}/=1 таких, что Т[ > 0 и £'=1 77 = т. В дальнейшем будем использовать обозначение Д; = Е'г=1 ту. Требуется найти функции 6 Улд и € такие, что

„"+'/» „»+(¡-1)/'

(Н!--, + а1(и + ¿1-1;«Г11-1)"М)

+ -/Р Рк,хи?(1-')1'РнА*°= (16)

р 1,»

" £ и Ры*$Г1+ЧтРкА*г + (/,«„ + Д_,), г'Оь / = 1.....з,

Р к=1л

п+к/т _ п+(к—1)/т

(М----а^\и+1;ип2+к,тМ)

т

^-ир^иТ^РнА^ (17)

Р 1 1.3

= ^¿7/г(Ч + (Як,**)„ к = 1,...,т,

/9 Т 1,1

= Р=1,2, (18)

где /£•* = 0, Л < т-1 и /г"'"1 = /2(<„-ц), «2/т-1 = и°2. Пусть выполнены условия устойчивости:

г < -"

1

Аао(1 + Ь)

(19)

.ч = 2АР о(1 + (20)

/» Л-'

где А^о/Л2 - наименьшая верхняя оценка спектра матричного аналога

билинейной формы оД/, и, V) т.ч. в - целое число.

Теорема 3.4.2. Пусть для решения задачи (2), (3) используется метод (16)-(18) при г < 1 и р — 0((Ь + г)1/2). Тогда, если выполняются условия устойчивости, имеет место оценка

тмс^и" - 4(^)11*, < с(М>^'2 + где Щ = ||«||{3) + (||и||(3) + |||М'Т = !М|(з) + ||£||(м.) +

И^Нькво.«.)*«)1"^2-

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

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

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

1. Доказаны теоремы аппроксимации для концентрирующих операторов размерности т — 1 на несогласованных сетках (п.1.4).

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

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

4. Предлагается и исследуется комбинация алгоритма покомпонентного расщепления с явной схемой в подобласти с мелким шагом по времени (пп.3.2-3.4).

5. Предложенные алгоритмы для решения двумерных задач реализованы в виде пакета программ БОМ-2 (глава 4).

По теме диссертации опубликованы следующие работы:

1. Лаевский Ю.М., Литвиненко С.А. О методе декомпозиции области с покомпонентным расщеплением решения двумерных параболических уравнений. Новосибирск, 1993. (Препринт / РАН, Сиб. отд-ние, ВЦ; 991)

2. Litvinenko S.A. On the explicit-implicit domain decomposition method without overlapping for parabolic problems // Bull. Novosibirsk Сотр. Center, Ser. Numer. Anal., 1994, Is.6, p.43-60.

3. Литвиненко С.А. Явно-неявные методы декомпозиции без налегания подобластей решения параболических задач // Труды конференции молодых ученых, Новосибирск, 1995, с.117-124.

4. Laevsky Yu.M., Litvinenko S.A. On the domain decomposition method with splitting in subdomains for solving parabolic problems // Rus. J. of Numer. Anal, and Math. Model., 1996, v.ll, №2, p.167-182.

5. Литвиненко С. А. Программа реализации методов декомпозиции // Вычислительные технологии в математической физике, Новосибирск, 1996.