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

российская академия наук

Сибирское отделение од

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

. ■ У'ПЛ

и математической геофизики

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

Гололобов Сергей Владимирович

МЕТОДЫ ДЕКОМПОЗИЦИИ ДЛЯ РЕШЕНИЯ НЕКОТОРЫХ ПАРАБОЛИЧЕСКИХ ЗАДАЧ

а

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

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

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

Работа выполнена в Институте вычислительной математики и математической геофизики СО РАН.

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

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

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

доктор физико-математических наук, профессор Воеводин А.Ф. доктор физико-математических наук, профессор Кузин В.й.

Ведущая организация:

Институт вычислительных технологий СО РАН, г. Новосибирск

Защита состоится " 14" июня 2000 г. в 15 часов на заседании специализированного совета К 002.10.01 в Институте вычислительной математики и математической геофизики СО РАН по адресу: Новосибирск, 630090, проспект академика Лаврентьева, 6, Институт вычислительной математики и математической геофизики.

С диссертацией можно ознакомиться в библиотеке Института вычислительной математики и математической геофизики СО

РАН.

Автореферат разослан "25_" апреля 2000 г.

Ученый секретарь диссертационного совета

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

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

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

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

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

1. Разработка и исследование явно-неявного метода декомпозиции области на непересекающиеся подобласти ( на несогласованных сетках ) на основе метода штрафа.

2. Разработка и исследование метода декомпозиции области на непересекающиеся подобласти ( на несогласованных сетках ) типа переменных направлений на основе метода штрафа.

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

Научная новизна. В основе исследования, проведенного в главах 1 н 2 лежит известная идея метода штрафа, которая используется для построения методов декомпозиции области на несогласованных сетках. В главе 1 рассматривается явно-неявный метод, для которого расширена область устойчивости за счет использования полиномов Ланцоша. В главе 2 предлагается метод декомпозиции области типа переменных направлений, имеющий повышенную скорость сходимости. В главе 3 рассматривается экстраполящшнная методика как эффективный способ распараллеливания вычислений. При этом экстраполяция проводится но по параметру дискретизации, а по некоторому весовому параметру, что является новой идеей. Однако идея получения оценок, основанных на односторонней константе Липшица, широко известна. Все изложенные результаты являются оригинальными, за исключением результатов пунктов 3.1-3.2, которые фактически были получены О.Акеельссоном, а в данной работе они приводятся в адаптированной для дальнейших исследовании форме. Результаты данной диссертации получены в соавторстве с Ю.М.Лаевским, а исследования, приведенные в главе 3, проводились также в соавторстве и с О.Акеельссоном.

Публикации ii аппробация работы. По томе диссертации опубликовано 5 работ. Основные результаты диссертации докладывались на третьем международном конгрессе по промышленной н прикладной математике ( ICIAM-95, г. Гамбург, Германия, 1995 г. ); на конференции молодых ученых ИВМиМГ СО РАН ( г. Новосибирск, 1998 г. ); на семинарах математического факультета Католического университета г. Неймегена ( Нидерланды. 1997-1999 гг. ); на научных семинарах ИВМиМГ СО РАН ( г. Новосибирск ).

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

Работа выполнена при поддержке гранта РФФИ-98-01-00709 и гранта INTAS-RFBR 95-0098.

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

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

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

Пусть П - ограниченный, открытый, связный многогранник в R'", т — 2,3, f]i и í?2 - подобласти в П такие, что

ñ = ñ, nñ2, Oí П Q'¿ = О,

и пусть 5 = íij П П2.

В пространстве Hl(Qp) х Hl(Qp) зададим две билинейные1 формы вида

г "' Ои Оь

где х = (.¡'|,.....гт) - точка п /<"". Дилос, в пространство Я'(9;,)

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

Я'(Пр), т.е. \pit\Vp) = (/р(/),V,,),,, р = 1,2, где (-,-),, - скалярное произведение в Ьъ(0.р), ^ € Здесь и далее через «(/)

обозначается значение функции и : —> Л', а - сильный

п])едсл в Л' ( если он существует ) элементов [м(£)]т ^ (и(( + т) — и(1))/т при т —V 0.

Через Хр обозначим пространство функций из Л'(0(1), продолженных нулем за пределы йр до П. Тогда может быть введено пространство вектор-функций X — X) х с нормой || • ||ч-. При этом скалярное произведение в Ь% есть {и,у) = (щ, )4 (.'2)2. В пространстве Я1 х Я1 может быть введена билинейная форма

а,{и, у) = «1(14, 00 + г;2). (2)

Далее, в пространстве

Я1

введем подпространство Я1,0 = |г-' 6 Я^г^-г) = 1'2(:£),.г £ 5}.

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

выполняются равенства

(^(<).") + «(«(0,'') = (/(0,''), (3)

Как нетрудно заметить, задача (3). (4) эквивалентна обычной задаче Неймана в пространстве Я1 (12).

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

При тех же исходных данных, что п в задаче (3), (4), требуется найти функцию и? £ такую, что 6 , 1) п Ун 6 Н|,с| при почти всех ^ 6 выполняются равенства

(^(t),iO + aK(í),t.)+

+ - /К(') - «S(0)(fi - = (ДО- <■}, (5) l'í

(up(t0),v) = (u0,u),

где p > 0. В дальнейшем через А будем обозначать матрицу, соответствующую билинейной форме (2), а через В - матрицу, соответствующую интегралу по границе S в (5). Полагая сна-нала ¡'i = 0, а затем v2 = 0, получим покомпонентную запись уравнений (5)

dnp

+ -pjW ~ - vq)ds = (fp(t), »„),„

(í/(fo), v) = (lío, ")> p = 1,2, рфц, откуда незамедлительно следует, что

л _ ( 0 ^ п-( В!■>

I о .42,j' Б2,2

Приведенной обобщенной постановке соответствуют следующие условия неидеального контакта на границе S

chi? di& —- H--- = 0,

¿?T7. j dll'2

dug

+ ~ = ^ = 2' P ^

<4 \ à< / ï\ i

где ^ = E \jg^cos(np,xJ), 7ip и xJ - единичные орты внешнеи 1 hj—1 * к ü¡, нормали на S и j-й координатной оси.

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

1/,+Ц/,и(/))= 0, t. > О, «(О) = иа £ V, (6)

где 1" - рефлексивное банахово пространство, к, = ^ и L(t.-) : 1" ->■ 1 *'. Здесь V обозначает пространство двойственное по отношению к скалярному произведению (-,-) в некотором гильбертовом пространстве Н с нормой ||е|| = (v, г) 5.

В дальнейшем мы будем предполагать, что оператор L(■.•) удовлетворяет условию монотонности, т.е.

(L(t,u(t)) -L{t,v{t)),u[t)-v(t)) > >p{t)\\u(t)-Ht)\f, V«(f),y(f) 6 V, (7)

где p : (G, ос) -> R+, т.е. p{t) >0, t> 0.

Параболическое уравнение является стандартным примером, удовлетворяющем вышеприведенному условию

ut{t,x)+L{t,u(t,а)) = 0, t> 0, reQ,

со стандартными краевыми условиями и начальными данными ¡/(0,2) -- ч0(х). Здесь L{t,u{t,x)) = -V- (ЛУ«) + С-&'+/(/■ »)• где /(/,«) соответствует нелинейному члену реакции.

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

Далее, в п.1.2 формулируется в векторно-матричном метод, анализу которого посвящена данная глава. Пусть N - некоторое

натуральное число, г = t„ — iy -f vt. n = 1......Y.

Далее, пусть {тк}\.= 1 - последовательность чисел таких, что т = 7"! + ... + тя и т^ > 0. Метод запишется в виде

Xii ' - U\ , , 1 П ч »Ч-1^ 1 „

П Р Р

/7, А = (8)

¿i

),"+' и" 1 i

——^ + (Л2.а + ~B2:¿h!J+> - И',»'Г = f.v (Я)

Т (I />

где ü", {> = 1,2 - заданные векторы начальных данных, п ti¡'* =

£ * • Уравнение (8) - это явная схема с переменным

шагом в подобласти П].

В п.1.3 приводится анализ свойств полиномов Ланцоша. Полиномом Ланцоша степени s называется функция вида

где Г,+1(у) = cos[(s + 1) arceos у] - полином Чебышева 1-го рода степени $ + 1, у £ [—1,1]. Некоторые свойства полиномов Ланцоша применяются для доказательства устойчивости ( п.1.4 ) и сходимости ( п. 1.5 ) метода. В частности, целый параметр л задается по формуле

s=(3TAp+1)*-1 = 0(-^), (Ю)

где А,, - подходящая оценка сверху для спектра матрицы Л[ | +

\ви и

1=1.....'' (И)

Теорема 1.4. Пусть для решения задачи (3), (4) используется метод (8)-(9) при к < т < го, /> = е(/*2 + тр с выбором, параметра я и последовательности {т<..};.= 1 о соответствии с равенствам,и (10), (11). Тогда им,пет место оценка

шах |К - «(МИ^ = 0(1, + Л),

где 'числа, 1ц, 7ц и с не зависят от параметров Н, т, я и вектор-функции

Сформулированные теоремы подтверждаются численными экспериментами В П.1.6.

13 п. 1.7 приводится анализ сходимости и устойчивости явно-неявного метода с расщеплением. Этот метод является модификацией метода из п. 1.2, в которой решается вопрос об обращении оператора на неявном полушаге. Предположим дополнительно, что П - выпуклый многогранник, - параллелепипед ( параллелограмм ), в 0-2 коэффициенты ](■£.) = 0 при / ф ] н граница 5 ортогональна т-ой координатной оси. Тогда из (1) следует очевидное представление билинейной формы е-})

т Ч)

02(«2,"2) = Ц 4 («2,^2), (=1

где = / Хц(х)^Нх.

Далее, сформулируем метод декомпозиции области с расщеплением во второй подобласти в векторно-матрнчном виде. Пусть Лг - некоторое натуральное число, г — t„ = ¿о + пт.

и = 1,. .../V. Пусть {т1;}'1=1 - последовательность чисел таких, что т — п + ... + т$ и Тк > 0. Запишем метод в следующем виде

+ (Ли + Ч.кГ^ - =

п Р Р

= 14, к = 1,...,в, (1-2)

—2 - ИЗ

,п+1 —^

+ 4',2У2+"' = 2. /=1,...,т-1, (13)

+ (АИ + 1В22)зЙ+1 _ 1Вт и'Г = (Ы)

г р р

где и", р — 1,2 - заданные векторы начальных данных.

Теорема 1.6. Пусть для решения задачи. (3). (4) используется метод (1'2)-(Ц) при Ь. < /го, т < т0, р = с(/)Д ■+ с выбором, параметра -ч и последовательности в соответствии с

равенствами (10), (11). Тогда им.ест место оценка

т

,'()/■ числа 1¡и и Ту не зависят от параметров Ь, т, и нектор-фупкции и(/).

Эксперименты из п.1.8 подтверждают полученные теоретические результаты.

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

Ар — А + -В.

Р

Пусть Л" натуральное число, т = (£, — ¿о)/^ и ¿„ = ta + пт. п = 1.....N. Запишем метод в векторно-матрнчном виде

+ Ли" +(15)

г/2 ' " - /, „" + 1 _ //"+£ 1

-—~ + Л«"+1 + = ГЧ (10)

т/2 р

где = ±(/" + /,,+ 1) и и", = 1,2 - заданные векторы

начальных данных.

Для вышеупомянутого метода доказывается сходимость и устойчивость ( п.2.2 ).

Теорема 2,2. Пусть для решения задачи (3^, (4) используется метод (15)-(16). Тогда при т = Л", = + /г2""1)! г/. Л < 1,и имеет место оценка

И » /f \и / а < |

числа Лц и с не зависят от к и аектор-функци у.

Приведенные в п.2.2 оценки удается улучшить в одномерном случае ( п.2.3 ).

Теорема 2.4. Пусть для -решения одномерной задачи (У)-(4) используется метод (15)-(16). Тогда для р = с\/т'г + К2 п 7 ти- ¡> < ^и нмеет .место следующая оценка

1 + ¥

шах II«" - w(í„)|]r = О

гс7е числа с. Tq и ho не зависят от. т, h и вектор-функции и.

Полученные теоретические результаты проверяются численными экспериментами в п.2.4.

В главе 3 речь пойдет об экстраполяционных неявных методах с параметром. В пп..3.1-3.3 проводится исследование устойчивости и сходимости неявного метода с параметром. Известно, что неявная форма метода с параметром может быть записана в виде 2-х шагов: неявный шаг ( t —> Г = t + вт )

v{t)+TÍ)L{t,v(t)) = v(t),

за которым следует явный шаг ( t —> t + т )

u(t + т) + т(1 - Ô)L{t,v(t}) = v(t),

где t = 9{t + r) + (1 -0)t — f 4- От и v(t) = v(t) = Ov{t + T) + (l -

0)r{t), O<0<1.

Теорема 3.3. Ошибка аппроксимации неявного метода с параметром. при 9k = 1 - щ^п > во-. Ç > 0.- > 0, к — 1,2..... где

> i. ( - некоторые параметры, удовлетворяет следующему равенству

||Я(ЫН = 0(г1+"),

где 0 < ц < 1, Tk < т, если тк9к{ 1 - 0к) - - =

0(т1+/'), к = 1,2,..., для любого решения u(t) задачи с сильно монотонным оператором (6) ( т.е. p[t) > p¡¡ > 0, W 6 (О.ос) J.

для которой u\*\t) £ L x ((). оо; II). Оценка оптимальна, т.с ||ВД| = |«(г2)|. г:сли ,,= !.'

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

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

Vi{t;) + TBiLiti^ViiU)) = Vi(t),

v,(t + г) + т(1 - dt)L(ti, «¡(Г;)) - nit)),

m

i'(> + т) = EM(f+ r), Vi( 0) = 1-0,

а метод с динамической экстраполяцией имеет следующий вид

гч(Fi) + r0iL(ti, «¿(Fi)) = v{t). r,(t + т) + t(1 - (h)L(ti, v,(ti)) = v,-{ti),

m

v{t + r) = E PMt + Г), (17) ¿=1

"¿(0) = i'o,

где Fi = t f 0,-r, Vi[ti) = T-i(t) = впф +- т) + (1 - Gi)vi(t), ф, £ R. i — 1,.... m.

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

Теорема 3.4. Независимо от выбора параметров / = 1 и ■целого m > 0 ne существует нелепый метод с па-

раметром. выше второго порядка аппроксимации ни со с.тпатн-нсской. ни с динамнчггког] экстраполяцией.

Свойствам устойчивости и сходимости неявного метода с параметром со статической экстраполяцией посвящен п.3.4.'2.

Теорема 3.5. Для зи,дпч диффузионного типа с оператором Ь(1,и), удовлетворяющем неравенству (7) при ¡>> рц > 0 существует устойчивый неявный метод с параметром со статической экстраполяцией не выше второго порядка аппроксимации в любой момент времени 1.

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

Лемма 3.5. а). Если \ < + в2 < | + 20102, > 0, 02 > 0. тогда метод (17) А-устойчив.

Ь). Если кроме того $1 + 02 > 1 и 0] 4- в? < | -Ь в\в-2: тогда оператор перехода метода положителен на неотрицательной полуоси.

-—в

Лемма 3.6. а). Если — ^г^, >0, в2> 0, тогда, .метод (17) Ь-усгпойчив.

Ь). Если кроме того в\ + в-1 > 1, тогда оператор перехода метода положителен на неоуприцателъной полуоси.

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

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

1. В пространстве кусочно-линейных функций для явно-неявного метода декомпозиции области на непересекающиеся подобласти ( на несогласованных сетках ) на основе метода штрафа в ¿2-норме по пространственным переменным и в сеточном аналоге С-нормы по времени получена оценка 0(\/т + /¡) при оптимальном значении штрафного параметра. Для схемы с расщеплением выведена оценка О (г5 + /и). Для доказательства устойчивости методов рассмотрены свойства полиномов Ланцоша.

2. В пространстве кусочно-линейных функций для метода декомпозиции области на непересекающиеся подобласти ( на несогласованных сетках ) типа переменных направлении на основе метода ш графа в ¿¿-норме пространственным переменным п в сеточном аналоге С-нормы но времени получена оценка 0(h) при г = 0(//л) и оптимальном значении штрафного параметра. Эта оценка улучшена для одномерного случая до ()(h) при т — 0(h).

■5. Для нелинейных уравнений с сильно монотонным опера тором пролучена оценка 0(т'1) для оптимального значения весового параметра. Доказана теорема о максимальном порядке аппроксимации 0(т2) для экстраполяцнонных неявных методов с параметром. Устанавлена асимптотическая устойчивость для неявного метода с параметром со статической -экстраполяцией. Для неявного метода с параметром с динамической -экстраполяцией доказана А- ( L- ) устойчивость. Предложенные методы протестированы на попудя-ционной задаче с использованием автоматически генерируемых сеток.

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

1. Лаевскнй Ю.М., Гололобов С.В. Явно-неявные методы декомпозиции области решения параболических уравнений // Снб.мат.журн., (1995). Т.Зб, №3. С. 590 601.'

2. Axelsson О., Gololobov S.V. Stability and error estimates for the 0-method for strongly monotone and infinitely stiff evolution equations // Dept. of Math.. Catholic University of Nijmcgen. The Netherlands. Report. No. 9908, (1999).

3. Axelsson O., Gololobov S.V., Laevskv Yu.M. Extrapolated ^-methods for nonlinear reaction-diffusion problems // East-West Journ. Numer. Anal., (1999). V.7, No.4. pp. 45-52.

4. Gololobov S.V. Explicit-implicit domain decomposition methods based on splitting for solving parabolic equations // Bull. Novosibirsk Сотр. Center, Sim-. Numer. Anal., (199G). Is.7. pp. 19-3G.

5. Gololobov S.V., Laevsky Yu.M. On one domain decomposition method with nonmatching grids for solving parabolic: equations // Bull. Novosibirsk Corrip. Center, Ser. Ntirner. Anal., (1996). Is.7. pp. 37-50.

Введение

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

0.2. Параболические начально-краевые задачи.

0.3. Нелинейные задачи

0.4. Дискретизация и вспомогательные неравенства

1. Явно-неявный метод декомпозиции области

1.1. Некоторые вспомогательные неравенства

1.2. Формулировка метода.

1.3. Свойства полиномов Ланцоша.

1.4. Устойчивость

1.5. Теоремы сходимости

1.6. Численные эксперименты ( одномерная задача )

1.7. Явно-неявный метод дбкймпозиции с расщеплением

1.8. Численные эксперименты ( дв^ерная задача )

2. Метод декомпозиции области типа переменных направлений

2.1. Формулировка метода

2.2. Теоремы сходимости.

2.3. Теоремы сходимости для одномерной задачи.

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

3. Неявные методы с параметром для нелинейных задач

3.1. Устойчивость неявного метода с параметром

3.2. Теоремы сходимости.

3.2.1. Произвольные шаги по времени.

3.2.2. Почти постоянные шаги по времени.

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

3.4. Экстраполяционные неявные методы с параметром . 95 3.4.1. Экстраполяционные неявные методы с параметром для модельной задачи.

3.4.2. Неявный метод с параметром со статической экстраполяцией для задач реакции-диффузии

3.4.3. Неявный метод с параметром с динамической экстраполяцией для монотонных операторов

3.5. Адаптивные сетки.

3.5.1. Построение адаптивной сетки по пространству

3.5.2. Построение адаптивной сетки по времени

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

Заключительные замечания

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

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

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

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

Теперь кратко остановимся на научной новизне полученных в диссертации результатов. В основе исследования, проведенного в главах 1 и 2 лежит известная идея метода штрафа, которая используется для построения методов декомпозиции области на несогласованных сетках. В главе 1 рассматривается явно-неявный метод, для которого расширена область устойчивости за счет использования полиномов Ланцоша. В главе 2 предлагается метод декомпозиции области типа переменных направлений, имеющий повышенную скорость сходимости. В главе 3 рассматривается экстраполяционная методика как эффективный способ распараллеливания вычислений. При этом экстраполяция проводится не по параметру дискретизации, а по некоторому весовому параметру, что является новой идеей. Однако идея получения оценок, основанных на односторонней константе Липшица, широко известна. Все изложенные результаты являются оригинальными, за исключением результатов пунктов 3.1-3.2, которые фактически были получены О.Аксельссоном, а в данной работе они приводятся в адаптированной для дальнейших исследований форме. Результаты данной диссертации получены в соавторстве с Ю.М.Лаевским, а исследования, приведенные в главе 3, проводились также в соавторстве и с О.Аксельссоном.

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

1. Бесов О.В., Ильин В.П., Никольский С.М. Интегральные представления функций и теоремы вложения // М., Наука, (1975).

2. Вабищевич П.Н. Разностные схемы декомпозиции расчетной области при решении нестационарных задач // Журн.вычислит, математики и мат.физики, (1989). Т.29, №12. С. 1822-1829.

3. Ладыженская O.A. Краевые задачи математической физики // М., Наука, (1973).

4. Лаевский Ю.М. Методы разбиения области при решении двумерных параболических уравнений // Вариационно-разностные методы в задачах численного анализа. Новосибирск: ВЦ СО АН СССР, (1987). С. 112-128.

5. Лаевский Ю.М. Об одном алгоритме декомпозиции области без налегания подобластей решения параболических уравнений // Журн.вычислит, математики и мат.физики, (1992). Т.32, №11. С. 1744-1755.

6. Лаевский Ю.М. Метод конечных элементов решения многомерных параболических уравнений // Новосибирск, НГУ, (1993).

7. Лаевский Ю.М. О декомпозиции области для параболических задач с разрывными решениями и методе штрафа // Журн.вычислит.математики и мат.физики, (1994). Т.34, №5. С. 702-718.

8. Лаевский Ю.М., Гололобов С.В. Явно-неявные методы декомпозиции области решения параболических уравнений // Сиб.мат.журн., (1995). Т.36, №3, С. 590-601.

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

10. Лаевский Ю.М., Мацокин A.M. Методы декопозиции решения эллиптических и параболических краевых задач // Сиб.журн.выч.математики, (1999). Т. 2, № 4, С. 361-372.

11. Лебедев В.И. Явные разностные схемы с переменными шагами по времени для решения жестких систем уравнений // М., Препринт/АН СССР. ОВМ, (1987). №177.

12. Лебедев В.И. Как решать явными методами жесткие системы дифференциальных уравнений // Вычислительные процессы и системы. М., Вып. 8, (1991). С. 237-291.

13. Лебедев В.И., Финогенов С.А. О порядке выбора итерационных параметров в чебышевском циклическом итерационном методе // Журн.вычислит. математики и мат.физики, (1971). Т.11, №2. С. 425-438.

14. Лионе Ж.-Л., Мадженес Э. Неоднородные граничные задачи и их приложения // М., Мир, (1971).

15. Локуциевский В.О., Локуциевский О.В. Применение чебышевских параметров для численного решения некоторых эволюционных задач // М., Препринт/АН СССР. ИПМ, (1984). №98.

16. Марчук Г.И., Шайдуров В.В. Повышение точности решений разностных схем // М., Наука, (1979).

17. Михлин С.Г. Вариационные методы в математической физике // М., Наука, (1970).

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

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

20. Самарский A.A. Введение в теорию разностных схем // М., Наука, (1971).

21. Самарский A.A., Николаев Е.С. Методы решения сеточных уравнений // М., Наука, (1978).

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

23. Фаддеев Д.К., Фаддеева В.Н. Вычислительные методы линейной алгебры // М.-Л., Гос. изд-во физ.-мат. лит-ры, (1963).

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

25. Яковлев Г.Н. О следах функций из пространства W^ на кусочно-гладких поверхностях // Матем.сб., (1967). Т. 74, № 4, С. 526-543.

26. Axelsson О. Error estimates for Galerkin methods for quasilinear parabolic and elliptic differential equations in divergence form // Numer. Math., (1977). V. 28. pp. 1-14.

27. Axelsson O. Error estimates over infinite intervals of some discretizations of evolution equations // BIT, (1984). V. 24, pp. 413-424.

28. Axelsson 0. Stability and error estimates valid for infinite time, for strongly monotone and infinitely stiff evolution equations // Equadiff 6 ( edited by J.Vosmansky and M.Zlamal ), J.E.Purkyne University, Brno, Czechoslovakia, (1985). pp. 274-284.

29. Axelsson O. A priori bounds and discretization error estimates for parabolic problems // Proceedings of ISNA, Prague (1987), Teubner, Band 107, Leipzig, (1988). pp. 8-18.

30. Axelsson O., Gololobov S.V. Stability and error estimates for the 0-method for strongly monotone and infinitely stiff evolution equations // Dept. of Math., Catholic University of Nijmegen, The Netherlands, Report No. 9908, (1999).

31. Axelsson O., Gololobov S.V., Laevsky Yu.M. Extrapolated 0-methods for nonlinear reaction-diffusion problems // East-West Journ. Numer. Anal., (1999). V.7, No.4. pp. 45-52.

32. Axelsson O., Steihaug T. Some computational aspects in the numerical solution of parabolic equations // J. Comp. App. Math., (1978). V.4. pp. 129-142.

33. Babuska I. The finite element method with penalty // Math, of Comput., (1973). V.27, N. 122. pp. 221-228.

34. Dahlquist G., Error analysis for a class of methods for stiff nonlinear initial value problems // Numerical Analysis ( G.A.Watson, ed. ), Dundee 1975, Springer-Verlag, LNM 506, (1976).

35. Dawson C.N., Du O. A domain decomposition method for parabolic equations based on finite elements // Domain Decomposition Methods for Partial Differential Equations. Philadelphia: SIAM, (1991). pp. 255-263.

36. Dawson C.N., Dupont T.F. Noniterative domain decomposition for second order hyperbolic problems // Domain Decomposition Methods in Science and Engineering, Abstr. Villa Olmo, Como (Italy), (1992). p. 11.

37. Dryja M. Substructuring methods for parabolic problems // Technical Report 529, N.Y.University, Computer Sci. Dept., (1990).

38. Dupont T. Mesh modification for evolution equations // Math. Comp., (1982). V. 39. pp. 85-107.

39. Eriksson K., Johnson C. Error estimates and automatic step control for nonlinear parabolic problems, I // SIAM J. Numer. Anal., (1987). V. 24. pp. 12-23.

40. Eriksson K., Johnson C. Adaptive finite element methods for parabolic problems IV: nonlinear problems // SIAM J. Numer. Anal., (1995). V. 32. pp. 1729-1749.

41. Eriksson K., Johnson C. Adaptive finite element methods for parabolic problems V: long-time integration // SIAM J. Numer. Anal., (1995). V. 32. pp. 1750-1763.

42. Ewing R.E., LazarovR.D., Vassilev A.T. Adaptive techniques for time-dependent problems // Comp. Meth. Appl. Mech. Engrg., (1992). V. 101. pp. 113-126.

43. Ewing R.E., LazarovR.D., Vassilev A.T. Finite difference scheme for parabolic problems on composite grids with refinement in time and space // SIAM J. Numer. Anal., (1994). V. 31. pp. 1605-1622.

44. Prank R., Schneid J., Ueberhuber C.W. The concept of B-convergence // SIAM J. Numer. Anal., (1981). V. 18. pp. 753-780.

45. Gololobov S.V. Explicit-implicit domain decomposition methods based on splitting for solving parabolic equations // Bull. Novosibirsk Comp. Center, Ser. Numer. Anal., (1996). Is.7. pp. 19-36.

46. Gololobov S.V., Laevsky Yu.M. On one domain decomposition method with nonmatching grids for solving parabolic equations // Bull. Novosibirsk Comp. Center, Ser. Numer. Anal., (1996). Is.7. pp. 37-50.

47. Johnson C., Nie Y., Thomee V. An a posteriori error estimate and adaptive time step control for a backward Euler discretization of a parabolic problem // SIAM J. Numer. Anal., (1990). V. 27. pp. 277-291.

48. Kraaijevanger J.F.B.M. B-convergence of the implicit midpoint rule and the trapezoidal rule // BIT, (1985). V. 25. pp. 652-666.

49. Kraaijevanger J.F.B.M. Contractivity of Runge-Kutta methods // BIT, (1991). V. 31. pp. 482-528.

50. Laevsky Yu.M. The use of the Lanczos polynomials for solving parabolic equations // Numerical Methods and Applications. Sofia: Publishing House of the Bulg. Acad, of Sci., (1989). pp. 244-249.

51. Laevsky Yu.M. On the domain decomposition method for parabolic problems // Bull, of the Novosibirsk Computing Center, Ser. Numer. Anal., (1993). Is. 1. pp. 41-62.

52. Laevsky Yu.M. On the explicit-implicit domain decomposition method for parabolic problems // Bull, of the Novosibirsk Computing Center, Ser. Numer. Anal., (1993). Is. 2. pp. 79-90.

53. Laevsky Yu.M. Preconditioning operators for grid parabolic problems // Rus. J. of Numer. Anal, and Math. Modell., (1996). V. 11, No. 6. pp. 497-515.

54. Laevsky Yu.M., Litvinenko S.A. On the domain decomposition method with the splitting in subdomains for solving parabolic problems // Rus. J. of Numer. Anal, and Math. Modell., (1996). V. 11, No. 2. pp. 167-182.

55. Lang J., Walter A. A finite element method adaptive in space and time for nonlinear reaction-diffusion systems // IMPACT Comput. Sci. Eng., (1992). V. 4. pp. 269-314.

56. Litvinenko S.A. On the explicit-implicit domain decomposition method without overlapping for parabolic problems // Bull, of the Novosibirsk Computing Center, Ser. Numer. Anal., (1994). Is. 6. pp. 43-60.

57. Mathew T., Russo G., Wang J. A domain decomposition based splitting method for solving parabolic problems // Domain Decomposition Methods in Science and Engineering, Abstr. Penn. St. Univ., Pennsylvania, (1993).

58. Ortega J.M., Rheinboldt W.C. Iterative solution of nonlinear equations in several variables // Academic Press, New York, (1970).

59. Prothero A., Robinson A. The stability and accuracy of one-step methods // Math. Comp., (1974). V. 28. pp. 145-162.

60. Rannacher R. A domain decomposition algorithm for parabolic problems // The Summer Conference on Domain Decomposition in Lambrecht (Germany), Abstr. Das Zentrum fur Practische Mathematik wird gefordert von der Volkswagen-Stiftung, (1991).

61. Rektorys K. The method of discretization in time and partial differential equations // D. Reidel Publ. Co., Dordrecht-Holland, Boston-USA, (1982).

62. Wheeler M.F. A priori X2 estimates for Galerkin approximations to parabolic partial differential equations // SIAM J. Numer. Anal., (1973). V. 10, No. 4. pp. 723-759.