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

РГ6 од

1 "1 г г ■ П 'о п ! » ¡.;.-.!

САНКТ-ПЕТЕРБУРГСКШ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

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

БЕЛЯКОВА Ольга Владиславовна

ЕОЕЙ ВАРИАНТУ ШОГОСЕТОЧКОГЭ МШДА ДНЯ НЕКОТОРЫХ ЗАДАЧ • МТЙШИЧЕСКОЙ <ЙВЙКЙ

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

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

Санкт-Петербург 1У93

Работа выпблнена ь Санкт-Петербургском государственном университета.

Научный руководитель - доктор физико-математических наук ДЕМЬЯНОВИЧ Юрий Казимирошч

Официальные оппонент: доктор физико-математических наук, профессор КОЩЕЕВ Вадим Глебович, кандидат физико-математических енук, доцент РЕПИН Сергей Игоревич

Ведущая организация - Петербургский институт инженеров транспорта

Защита состоится ", -'/с-- ¿саСуСс/ 1993 г. в часов

на заседании специализированного совета-Д 063.57.30 по защите диссертаций на соискание ученой степени доктора физико-математических наук в Санкт-Петербургском университете по адресу: 198504, Санкт-Петербург, Старый Петергоф, Библиотечная площадь, 2, Математлко-механичаский факультет.

С диссертацией можно ознакомиться в библиотеке им. Горького Санкт-Петербургского университета.

. Автореферат разослан --¿•'¿М 1993 г.

Ученый секретарь ■ специализированного совета Д 063.57.30

доцент Ю.А.СУ1КК0В

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

Актуальность терм. Как известно, в определенных условиях миогосеточный метод является оптимальным итерационным алгоритмом для решения эллиптических краевых задач. Он позволяет найти их прибляненноа решение за количество арифметических операций, пропорциональное числу неизвестных системы сеточных уравнений. Варианты ¿шогосеточного метода характеризуются цепочкой используемых конечномерных подпространств, которые в свои очередь могут быть вложенянмз и невложенными. Получение .оценок скорооти сходимости ¡.шогосеточного процесса для реальных задач представляет значительные трудности. Весьма нежно исслодовать упомянутый метод для задач с сильным внроящопяем и распространить результата на нестационарные задачи. Серьезные прея^ущоства имеют способа реализации многосеточного метода, при которых оценка оператора перехода ограничивается величиной, яэ зависящей от коэффициентов задачи'(робастные методы).

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

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

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

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

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

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

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

Апробация паббтн. Результаты доложены автором на Всесоюзной конференции в г. Пущино, 1988 г., на городском семинара "Математические вопроси метода конечных элементов" (Санкт-Петербург, 1992 г.), на кафедре вычислительной математики Кали-нишрадского госуниверситета и опубликованы в работах [б - 12]

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

сглакивезют итераций, а ткко текст програм па языке FORTRAI/ для рололгя олпоиерлоЗ заката о вароздэияеи я для рсзоннл двумерной задача со стационартм ураввопяом диффузии. Об."у:И обь015 диссертации 140 с.

СОДЕШЖВ РАБОТЫ

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

Au= | , feH, (I)

с шяияшгаяыго опрэдалэгшш, самосопрякеншм оператором А в гильбертовом пространства Ц . Исследованы такяе достаточные условия того, чтобы оценка скорости сходимости не зависела от числа вспскогаголышх подзадач. Получены некоторые оценки о длительности вычислительной работа и величине абсолютной по-грзиностя в многосогочнэм алгоритме (см. работы Г.П.Астрахал-цева [il , В.Г.Корнеева I2] , fTLaiUe 9.-F, /7?wiy ГДз] . Приведем исследуемую схему многосеточного процесса. В гильбертово;.! пространстве И со скалярным произведением (и, V ) и нормой Hull рассмотрим задачу (I). Пусть WA -соответствующее энергетическое пространство со скалярным произведением lu,v] z нормой \и(г= • Введем последовательность подпространств в Нд ,

I,cA'wcI)(i)cHAl K^i 2,... (2)

п определим в Хк оператор Ак тондеством

(Аки, V)= L-u.-zr], w,ireXK, A^^A. (3)

Через Рк и /J к обозначены ортопроекторн на пространство Хк в

Нд и в И соответственно.

К уравнению (I) приманим проекционный метод, при этом в качестве приближенного решения берется элемент и^сХ^ такой, что для всех £ Хт выполняется равенство

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

A) если К = 0, го точно или приближенно решается задача

полученное решение обозначается и0 с Х0 ;

B) если К = т,,.., I, то

1) выполняются сглаживающие итерации в ^ :

2) находится поправка для- ик в . Для этого решается задача

К-«, =

р (р ?>£ ) итерациями алгоритма, начиная с нулевого начального приближения, получим Сд;

3) выполняется корректировка Ик :

4) выполняются сглаживающие итерации Г^ в Х.к :

«к — ' {«)■

Полученное значение принимается 8а новое приближенное

решение задачи (4).

В этом случае доказаны следующие результаты.

Леша I. Оператор перехода многосеточной итерации после

выполнения алгоритма А) - Б) в Хк описывается операторов

здэсь Гк , 6 - лилейные» чзста сглаяивалщах итераций Рк , 6ц соответственно.

Дамма 2. Пусть о(к, - вещественные пелояительныв параметры такла, что

КЕк-Р*„) &к гг/ « ^ Цг-К (-\РКЧ Скгк |2), ¡1 I! <{,

I Рк |2*д КСх-Р^ъ Ы \\ V , И? Ы,

Тогда выполнявшая оценка

•иII ^ таге {■

Из этих двух лемм следует теорема об оценке скорости сходимости многосеточного процесса для задачи (4).

Геопамд I. Пусть для выполнены условия лемма 2

с и задача в Х0 решена с точностью £„£(0. !)•

т.е.

IЧ - Ч 1

Тогда последовательность приближений , г<£ Л/ , полученных многосеточными итерациями по алгоритму А) - В), сходится

к решению и* задачи (4), причем о-

, т * ■ , 1 * I г Л I. \ 1 1 I ">-»

Эффективность мюгооеточного процесса существенно зависит от выбора в Хк сглаживающего процесса.

Даииа.3. пусть _р((ек- &*к ё ^ («-Д \ М,

б -6* , где - спектральный радиус. Тогда при любом рё//

Теорема 2. Пусть в алгоритма К) - В) сглааивавщие итерации такие, что ёк = Ек~<?к А* , Ж Ак)€ {О, Д Р^э Бк • То-

{ -//a, kW1-

гда для последовательности приближенных решений (4),

полученных по указанному алгоритму, при любых р^е U выполняется оценка

i » i , г * i

"«J,

где

, п0 nKA т.ц

^--ГПШ (б ^ ! }, n^f, , 1 ém

<*« = W«)/(pK- ¿(G«)), 4¿K)¿?((£■«-РКЖ ¿Л V{f),

ф/р^/г, o<f<{.

L тая {fa t f(/-f Пусть . Введем определение

Определение у. Последовательность называется регулярной для оператора А , если

][ aJ ¡I Slip lu-P^UQ , С4 = const, с{ >0. net

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

Теорема 3. Пусть последовательность - регулярная для оператора А и выполняются условия вложенности (2), существует такое £e(Q, I), что Е (<Гд Ак) и

Г t hTu У S (4 сг, сг COnsi, сй>0 • Тогда

f (( Ек- АкТ'У * , b^const, с, >0,

для всех i,..., m, (!с не зависит от размерности Хп, и мно-госеточшй процесс по алгоритму А) - 3) оптимален.

Пусть в качестве сглаживающих итераций рассматриваются итерации

Введем отображение Ч' : ХК~*ХК , где Х^ - пространство

векторов , Л^ = &тХк. Каяднй из векторов можно

считать набором коэффициентов разложения функции г(к^Хк по базису } с Хя .

Теорема 4. Пусть - регулярная для А последовательность подпространств и выполняются условия: I) существует с£(0, I) такое, что Ей'^^Сх А^г-Е, ^ = 2) существуют полокитэльныэ постоянкне 'С,, Съ так1!е, что сг\\Л\\ ~<

^ Ч^^й^/РеХ". Тогда в реальном вычислитель-

ном процесса итерации (6) козко заменить итерациям

при этом многосзточный процесс оптимален, /¿>т <; р , м-йяс!^, «(■ = (р+1>), ^-сопН, ¿>0, рем.

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

Другой подход см. в работе

Вапк ПЛ., Ог<роп1 Т.Г. [4]). Дифференцируя по временной переменной (7), придем к задаче

(<?"'£ + = (8) где =-(х ух)ре ' ^ ~ параметр дискретизации. Введем

Г "> ^К

еще сетку по пространственной переменной } х.^ }.

о—о

Тзопема 5. Если величины 01К\

01к = я* (- х^)2/ , р ? ограничены в совокупности, £ 01(Ы) , то для решения зада-

чи (8) найдется такая кусочно-линейная функция а , что справедливо неравенство jVlg'-itffdc £0.Ш сЩ,

Теорема 6. Если {ХД строится с помощью сеток cr.^i24*/^ 1-0,..., , то - регулярная последо-

вательность для А. .

Решая задачу (8) численно и вводя норму \и i ,

Lv, -wlj.- iu\2+T~ivf, получим следующий результат.

Лемма 4. Для любого 0 многосеточшй процесс, примененный к решению (8) со оглаююаюдиш итерациями (6), оптимален и-выполняется оценка

' Щ um 'г с 1 "/»V 'т '

%£ № t £6(0, I), начальное приближение для многосе-

точного процесса.

Теорема 7. Для обобщенного решения задачи (7) на каждом временном шаге ■£ выполняется оценка

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

malte У-Р., П?и!0з1 , bctnk Я,£., DoucjfosC. [51 ).

Итак, рассмотрим задачу

О)

где Вп - некоторый положительно определенный, самосопряженный оператор в гильбертовом пространство И со скалярным произведением {V, V), ti.VeU. Для решения этой задачи шогосеточ-

иым методом вводится последовательность конечномерных подпространств {X«} таких, что

(ктХв < <ЖтХп, Х^Н-, ¿-О,...,/п.

и оператор суженая ' . 1« ^: ХК~*,ХК./ , оператор продолжения , : . причем 1Г, -гс)" (V, 'гс), г(.еХк,г'-£Х1(_1.0йозначпы, как правде,

итерационные процессы в Хк • Цусть известно некоторое приближенное решение Тогда рассмотрим сле-

дующий алгоритм многосеточной итерации для решения (Э):

С) если к =0, то точно или приближенно решается задача

V = &, <

полученное решение обозначаем ие ;

1>) если к = , то

1) йк*~ Гк (ик, {Д ик, {ке Хк (сглаживание);

2) вахо.дится поправка для гсм в . Для этого ре- . шается задача

]а итерациями ) алгоритма, начиная с. нулевого- началь-

ного приближения, получим ил ;

3) кк -«-гс^ + ин.{ (коррекция);

4) йк -¿-6-ц (сглаживание).

Вычисленное значение принимается за новое приближен-

ное решение задачи (9). Операторы 3^ считаются положительно определенные, самосопряженном в Хк. Следовательно, с &1 можно связать энергетическую ворму Ни , 11гс!1ь. = (В^и, гс)(

к^Хг. V ,

Леугма 5. Для оператора .¿ь , = В- выпол-

няются следующие свойства: I) Ъ- - самосопряженный по энергия

Воператор; 2) Ъ- неотрицательный оператор; 3) ЛЗХН =

Пусть Т; г? Е;~ Б,-Л - 8---оператор перехода после шагов 2), 3) алгоритма С) -1>)! - некоторый положительный параметр; тогда справедливо следующее утверлщение. Дйэтла в. Если выполнены условия: I) "^¿И^. ¿1,

Теорема 8. Пусть для любых 1с.*_{ £ верны со-

отношения

* «аг-, 1 Ч И

В ^ »V; ё -Ъ+р-Ъ^гт.! -Ч)в. (

здесь Р^ , - линейные части сглаяиващих итераций алгоритма, ^, ^ - некоторые полонитэлыма вещественные парамег-рц. Тогда .

Теорема 9. Пусть выполнеш условия теорема 8 для всех •/,,..(да. Тогда в результате применения шогосеточной итерации по алгоритму С) -3)) к некоторому прибликзнному решении, ге^ , ££// , задачи 9 получим такое, что

*

- Но ^ Ч ,

Обозначим Л - прямоугольник вида {(осуу): Обходе, Теорема 10. Для указанного в §4 алгоритма многосеточного

процесса при рьыении задачи аи.^ {эО/щ, и,/л -^0, выполняется оценка

И^илояение разделяется на две части. В первой части содержатся интегральные оценки производных решения задачи (7) и дзумерной нестационарной задачи с сильным вырождением по одной пространственной порайонной (§ 1-4). Зги оценки используются при доказательствах теорем аппроксимаций во второй глава. В § 5-7 указан способ получения оценок аппроксимации решений нестационарных задач в областях, отличных от прямоугольника.

Вторая часть приложения содер:гат текст программа для решения одномерной задачи с вырогданием вида -(гс^ид^^«^ ,

^а^и'Мх—о, о1е (I, 2) и текст программы, реа-0

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

Коротйо укажем распределение материала по главам и параграфам.

В § I первой главы изложена схема исследуемого многосеточного алгоритма. Во втором параграфе получена теорема об оценко скорости сходимости алгоритма (теорема I). В § 3 исследованы способы оценки параметров с!«. , ^ из теоремы I (теорема 2). В параграфе 4 рассмотрены достаточные условия оптимальности многосеточного процесса, когда в качестве сгланиваюдих используются простые итерации (теорема 3). Вопрос о практике- •

ской роализапм сглаживающих итераций в ¿зяздиональяом пространстве X* исследован в § 5. Используя метод введения специального функционала,в параграфах § 6, 7 подучены общие оценки длительности вычислений в Многосеючном методе и погрешности округления в зависимости от параметров многосэточного алгоритма^ , Аит Х„, /Дил^к. К других).

В § 1-2 второй главы указан способ получения оценок аппроксимация последовательность® подпространств для решения начально-краевой задачи с сильным выровдением по пространственной переменной. В § 3 рассмотрена аппроксимация дискретизиро-ванной по времени нестационарной задачи с помощью кусочно-линейных функций (теорема 5). Аппроксимгционные свойства функций зависят от способа построения сеток; ото показано в § 4. В 5 5 на основании определения регулярности семейства подпространств X«. , теорем аппроксимации из § 4 и оценки нормы оператора К* доказана оптимальность многосеточного процесса для модельной задачи с сильным вырождением. В § 6 указан способ получения оценки точности приближенного решгния нестационарной задачи, полученной указанным многосэточным методом.

. В § I третьей главы описывав.ся алгоритм рассматриваемого многосеточного процесоа. В § 2, 3 даны теорема об оценке скорости сходимости указанного алгоритма и теоремы об оценке некоторых параметров этого алгоритма (в частности, с}* , ^ ). В § 4 подробно описаны все операторы, входящие в алгоритм, и затем е § 5 перчены матричные представления этих операторов л вычислена оценка нормы оператора перехода этого алгоритма. В § 6 приведены сравнительные результаты машинных расчетов по алгоритму из § 4.

Литература

1.Астраханцев Г. П. Об одном итерационном методе решения сеточных эллиптических задач//ЖШ'и Ш>, т. II, К 2, 1971.

2. К о р н е е в В. Г."Конечно-элементная аппроксимация высокой точности. - Л., 1972. - 250 с.

3. Ш^йи. З.-Р. ШЙз^ил ЛгхииксДл: ^оя. "а^ыпДм.

\JasuoWji5l О. Оли^.

\jjrvalxA ^Л-Иадя! ^лсоЦКм . /.КПиЖ .0*1 С**^.,

4. Рч.Е., Т.1?-.' Си с^сияа! ^Аии ^илглл

сыиля^йпла. ип№- амА. сил^чяАшп.. /ъъ\\\

6. Б е л я к о в а 0. В. Вариационно-разностная аппроксимация начально-краевой задачи с сильным вырождением в случав одной пространственной переменной. Деп. в ВИШОТ, Я 7369-В85-от 22.10.85. • .

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

. нения с вырождением. Деп. в ВИНИТИ, й 3514-В86 от 14.05.86.

8. Белякова 0. В. О дифференциальных овойствах решения одной краевой задачи с сильным вырождением. Деп. в ВИНИТИ, К 4932-В86 от 07.07.86.

9. Демьянович Ю. К. .Белякова 0. В. О гладкости решения некоторнх задач с вырождением. Деп. в ВИНИТИ, П 4932-В86 от 27.08.86.

10. Белякова О.'В. Об аппроксимации задач с вырождением эллиптичности//Вестш1к ЛГУ, Серия мат., мзх., астр. 1886, й 4.

11. Б у а д и я А." А.' , Б е л я к о в а 0. В. О сходимости многое о точных процессов. Деп. в ВИНИТИ, В 8328-188 от 16.12.88.

12. Б е л я к о в а 0. В. , Б у з д и п А. А. Тоората-ческие и практические оценки скорости сходимости одного варианта мяогосаточного процесоа. Доп. в ВИНИТИ, В 39-В93 от 10.01.93.