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

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

Быченков Юрий Владимирович

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

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

Автореферат

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

Москва - 2003

Работа выполнена на кафедре Вычислительной математики механико-математического факультета Московского государственного университета имени М.В.Ломоносова.

Научный руководитель: доктор физ.-мат. наук, доцент Е.В.Чижонков

Официальные оппоненты: доктор физ.-мат. наук, профессор Е.Е.Тыртышников, кандидат физ.-мат. наук, с.н.с Т.К.Козубская.

Ведущая организация: Научно-исследовательский институт математики и механики имени Н.Г.Чеботарева Казанского государственного университета

ЛЛЯ00

Защита состоится '0_" О^СП 2003 г в

на заседании диссертационного совета Д 002.045.01

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

по адресу 119991, Москва, ГСП-1, ул. Губкина, дом 8.

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

Автореферат разослан

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

диссертационного совета,

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

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

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

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

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

ристиками сходимости, в большинстве случаев оставлены в тени или недостаточно разработаны. Это, несомненно, обусловлено большой теоретической и технической сложностью подобных исследований.

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

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

Научная новизна. В работе впервые подробно исследованы трех- и четырехпараметрические алгоритмы для решения, в общем случае нелинейных и нерегулярных, задач с седловой точкой. Эти алгоритмы являются обобщением известных алгоритмов Эрроу-Гурвица, Кобелькова, модифицированного метода верхней релаксации (МБОЯ) в случае незнакоопределенной симметричной матрицы.

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

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

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

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

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

Апробация работы. Результаты работы докладывались на Всероссийских молодежных школах-конференциях, г. Казань в 1999 и 2001 году, на Конференциях молодых ученых механико-математического факультета МГУ в 2000-2002 гг., на Ломоносовских чтениях 2002, на международной конференции "Workshop on Nonlinear Approximations in Numerical Analysis", г. Москва в 2003 году, а также на семинаре ИВМ РАН под руководством академика РАН Н.С.Бахвалова и профессора В.И.Лебедева.

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

Структура и объем диссертации. Диссертация состоит из введения, трех глав, приложения, заключения и списка литературы из 57 наименований. Общий объем работы - 125 страниц, включая 8 рисунков и 2 таблицы.

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

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

где п./ е и, р,д <Е Р, V и Р - конечномерные эрмитовы пространства над С размерностей ЛГу и соответственно, А = А* ^ 0 - линейный оператор в 17, В : Р и - линейный оператор максимального ранга. Задача (1) называется регулярной, если кег А = {0} и нерегулярной в противном случае.

Исследуемый итерационный алгоритм имеет следующий вид

Краткое содержание работы

(1)

+ (А + рВС~1В*)ик+ Врк = / + ¡ЗВС~1д

V

г

где Q : U ->■ U С : Р Ч- Р - линейные симметричные положительно определенные операторы, к G N U {0} - номер итерации, и0 е U, р° £ Р - заданные начальные приближения, а а > 0, т > 0, /3 R - итерационные параметры.

В §1.1 вводится определение класса оптимизации алгоритма (2) и связанные с ним понятия: классом оптимизации (или постановкой оптимизации) алгоритма (2) называется некоторое множество четверок (А, В, Q, С), где

А : U U, В - Р U, Q : U -> U, С : Р Р

являютйг линейными операторами, которые удовлетворяют следующим свойствам

А = А* ^ 0, Q = Q*> 0, С = С* > 0, (3)

ker В = {0}, ker А р| ker В* = {0}.

Последнее условие является необходимым и достаточным для существования и единственности решения (1) для любой правой части. Задачей асимптотической оптимизации алгоритма (2) на классе оптимизации К называется следующая вариационная задача

inf sup p(T(a,p,T-, A,B,Q,C)). (4)

%r0, (A,B,Q,C)eK

где Т(а,(3,т; A, B,Q, С) - оператор перехода в (2), р(-) - спектральный радиус оператора. Здесь же вводятся основные классы оптимизации:

• класс К(7, Г) состоит из всех четверок (А, В, Q, С), которые удовлетворяют условиям

Q = A> 0, 0<^С ^В*А~1В^ГС, (5)

где 0 < 7 < Г - фиксированные числа.

• класс А, 7, Г) состоит из всех четверок (А, В, С}, С), которые удовлетворяют неравенствам

0 < 7 С ^ В*А~1В ^ Г С, (6) где 0<5<Д,0<7^Г - фиксированные числа.

• класс Кг(5, А, 7, Г) состоит из всех четверок (А, В, ф, С), которые удовлетворяют неравенствам

0 < 7 С ^ В*С$~1В ^ Г С, (7) где 0 < 5 ^ А, 0<7^Г - фиксированные числа.

Следующий §1.2 посвящен оптимизации алгоритма (2) на классе К(7,Г), 7 < Г. Основной результат формулируется в виде теоремы

Теорема 1.2.4. В классе Ж(7, Г) задача асимптотической оптимизации алгоритма (2) имеет единственное решение следующего вида

1 — Л/? V? 47

^гт^' Г0 = (ТТ71Г ао = (1Т7Г ^ '

где £ = 7/Г.

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

Далее, в §1.4 с использованием результатов предыдущего параграфа решена задача асимптотической оптимизации (2) в классе Ki(5, Д,7,Г), S < А, 7 < Г, о чем свидетельствует следующая теорема:

Теорема 1.4.6. Задача асимптотической оптимизации метода (2) в классе Ki(5, А,7,Г), где 0 < <5 < А, 0 < 7 < Г, имеет единственное решение

где £ = 7/Г, и = 5/А, a q^ является единственным на интервале (0,1) корнем уравнения

- (1 + u)q2 + - 1 )q + (1 - со) = 0.

1 + 5 1 + 5

Отметим, что формулы, полученные в теореме, могут быть выписаны в явном виде, так как величину q<j можно явно записать по формулам корней кубического уравнения. Качественные характеристики оптимального показателя сходимости выявлены в следствии:

Следствие 1.4.1. Пусть г/о = qo{ui, £) - величина определённая в теореме 1-4-6, тогда имеют место асимптотики

qo — 1 — ш + 0(ш2) при ш -» 0, £ = const,

/4м

о-С + 0(0 при £ о, ш — const.

z — UJ

Аналогичный результат получен в §1.5 для класса оптимизации К2(<5,Д,7,Г), 8< А, 7<Г:

Теорема 1.5.6. Задача асимптотической оптимизации метода (2) в классе К2(<5, А,7,Г), где 0 < 5 < А, 0 < 7 < Г, имеет

единственное решение

где £ = 7/Г; и = 5/Д, а <70 является единственным на интервале (0,1) корнем уравнения

У3 - (1 + ш)д2 +-1(2ш - 1)д + (1 - ш) = 0.

1-е

Следствие 1.5.1. Пусть до = - величина определённая

в теореме 1.5.6, тогда имеют место асимптотики

Отметим то, что указанные результаты не могут быть сведены к результатам предыдущего параграфа и наоборот.

В §1.6 проанализирована нерегулярная задача с седловой точкой, предложен следующий метод ее регуляризации: вместо исходной нерегулярной задачи (1) рассматривается задача с седло-вой точкой, эквивалентная исходной

где Ау = А+и В С~гВ*,/ = ¡+ь>ВС~1д, V > 0. Использование алгоритма (2) для решения (8) приводит к идее четырехпарамет-рического алгоритма для решения исходной нерегулярной задачи с параметрами а, [3, и > 0, /? £ К. В качестве класса оптимизации для нерегулярного случая предлагается рассмотреть класс

до — 1 - и + 0(ш2) при и -»■ 0, £ = сопв!;,

до = 1 - \ --£ + 0(£) при £ 0, и = соп^.

и

оптимизации K2s(5, А,7,Г) состоящий из четверок (A,B,Q,C), которые удовлетворяют неравенствам:

О < А < A Q, 5(Qu, и) sC (Аи, и) \/и 6 ker В*,

7 С <B*Q~lB <ГС. О

В этом случае указанный четырехпараметрический алгоритм эквивалентен исходному трехпараметрическому и в терминах последнего решение задачи оптимизации дает теорема Теорема 1.6.1. Задача асимптотической оптимизации метода (2) в классе А,7,Г), где 0 < 5 ^ А, 0 < 7 < Г, имеет единственное решение

^шУ1"^ ,>0.ft = g,4, = ^>0, (10)

2dA0 (2w0 ~ 1) + % 7 о

где £ = 7/Г, ^о = S/Aq, А0 = ¿(а;"1 + a qo является единственным на интервале (0,1) корнем уравнения

- (1 + u0)q2 + - 1)? + (1 - wo) = 0.

1 + £ 1 + £

Следствие 1.6.1. Пусть qo = <?o(w,£) - величина определённая в теореме 1.6.1 (ш = 5/А, £ = 7/Г), тогда имеют место асимптотики

qQ = 1 - из + о(ш) при и -» 0, £ — const, qo = 1 — £ + о(£) при £ —> 0, ш — const.

Вторая глава посвящена алгоритму для решения практически важных систем алгебраических уравнений с седловой точкой - системам типа Навье-Стокса:

Аи + Ки + Щи)и + Вр =/ , ,

В*и = д ' { }

{

где и, / € и, р,д € Р, V и Р - конечномерные евклидовы пространства размерностей Иу и Ир соответственно, А : и —> II - линейный симметричный положительно-определенный оператор, К : и —и - линейный кососимметричный оператор, а N .и х и —> и - билинейный оператор обладающий следующим свойством кососимметрии

у) = О V«, V е и. (12)

Исследуемый алгоритм носит вид

| С1ик+1 ~ ик + (л + К + рвС~1В*) ик + Щик)ик+ Врк = / \ -аС (ры - рк) 4- В*ик+1 = д

(13)

где Ц : 11 -¥ 11 С : Р Р - линейные симметричные положительно определенные операторы, / = / + рВС'гд, к Ми {0} -номер итерации, и0 £ II, р° £ Р - заданные начальные приближения, а а > 0, т>0, /3 € К - итерационные параметры.

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

0 < 5С} < дд, (14)

0 < 7С В*О-1 В ^ ГС, (15)

\(Ки, и)| < ск ЦпЦдЦиЦд, Чщуеи, (16)

|{Щи)ь, го)| ^ см ИиЦд |М|д \\т\\я , Ум, (17)

где 0 < <5<Д, 0 < 7^Г, сдг^О - известные фиксированные

величины.

В §2.2 вводится параметрическая норма в пространстве Z — И х Р Э г = (и,р)т:

1М1* = у/{{Я - т(х(А + (М(-)й}3) + ¡ЗВС-1В*)и, и) + ат(Ср,р),

где 0<х<1,0<т < (х(Д + сы ||й||д) + /5Г)-1, (•)* - симметричная составляющая линейного оператора, г = (й, р)т - решение задачи (11). Далее выводится оценка показателя скорости сходимости алгоритма в этой норме: Теорема 2.2.2. Пусть выполнены следующие условия:

см ||й||0 <6, 0 < х < 1, 1 2(1 - х)5{ 1 - т(хД + ¡ЗГ))3

Т < Ю1П

хД + /ЗГ 2((1 - х)(1 - г(хД + 0Г)))ЧЬ + Щ Р^О, к~5 + ф- сГ^Г > О, где г — (й,р)Т - решение задачи (11),

5= (^-СлгЦмЦд, д - Д + С]У \\uWq ,

»011

До= \ск + см I ||й||0 +-,|г

1(3 1 — т(хД + /ЗГ)^

а 2° = (и0, д°)т - вектор начальной ошибки приближения. Тогда алгоритм (13) сходится в норме \\-\\2 со скоростью геометрической прогрессии с показателем д таким, что

в 2а

+ \11-2тв + г2 (о-^)2} <1,

тах < |1 — тхй| , т

<е[7,Г]

где в = + <6

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

Следствие 2.2.2. (Асимптотика оценки). Пусть выполнены условия теоремы 2.2.2, тогда

шш ~ * ^ 1 - <и1 Уёб(0,1), Х>0- \\z-A\z

где С\ = С1(5,А,ск,см,и°,р°,/,д) и не зависит от £ = 7/Г. Если, кроме того, ск, = 0(8) при ¿Г —>■ 07 то

шш "У ~*}г < 1 - с^ё, а; е (0,1),

а,т> 0, г — Z

Z

где С2 = с2(ск,см,и°,р°,/,д) не зависит от £ и и, и = 8/А, Т(-) - оператор перехода в алгоритме.

В третьей главе исследуется задача с седловой точкой с сильно монотонной нелинейной частью и алгоритм для ее решения.

В §3.1 дается постановка задачи. Пусть и, Р - евклидовы пространства размерностей Ми, Мр соответственно Ми > Мр, ^ - некоторая область в £7, оператор А(и) : О, —и определен всюду в О, и удовлетворяет условию сильной монотонности:

^\\и1-и2\\1^{А(и1)-А(и2),и1-и2) (18)

а также условию Липшица:

р(«1) - А{и2)|| ^ Д ||«1 - и2\\я Уии и2 Е П, (19)

где 0 < <!) ^ Д, = > 0 - линейный оператор в С/. Исследуемая задача имеет вид

№+ <*>

где В .11 —> Р - линейный оператор. Для решения задачи (20) предлагается рассмотреть следующий алгоритм

(ик+1 _ ук

<2-+ А{ик)+/ЗВС~1В*ик+ Врк =1 + !ЗВС-1д

-аС (рк+г - рк) + В*ик+1 = д

(21)

где С : Р -> Р - линейный симметричный положительно определенный оператор, к € Ми{0} - номер итерации, и0 € О, р° € Р -заданные начальные приближения, аа>0, т>0, /3 € К - итерационные параметры. При исследовании (21) предполагаются известными величины 0 < 7 ^ Г из неравенств

0 < 7 С ^ В*С}~1В < Г С, (22)

а также существование решения задачи (20).

В §3.2 показывается, что для исследуемой задачи выполнена теорема единственности и существования при достаточно большой О. (например О. = II), что дает основание надеятся на достаточно большую область сходимости (по начальным приближениям) исследуемого алгоритма, что подтверждается основным результатом главы: введем норму в Z — и х Р следующим образом

Ы\г = \/ + ск-г(Ср, р), г = {и,р)тег,

тогда для некоторого Я € (0, А], зависящего только от А(-), справедлива

Теорема 3.2.3. Пусть ц € (0,1) и

тогда для любого начального приближения ¿о = (и®,р°)Т £0,хР такого, что

М0 = {г € г : ||г - г\\2 ^ ||г0 - %} СО, х Р,

где г 6 ^ - решение задачи (20), алгоритм (21) корректно определен и сходится к г со скоростью геометрической прогрессии в норме ||-\\2 с показателем ц таким, что

Качественное представление о полученной оценке можно получить из

Следствие 3.2.1. (Асимптотика оценки). Пусть выполнены условия теоремы 8.2.3, тогда для некоторой константы с\ ^ 1/16

min —< 1 - ciw2f при £ -> +0, ш = const. e.r>0. \\z-z 7

Если же оператор А(и) симметричный, то имеет место оценка

min J—ä—äz < i _ CoUc npu £ +o, ш = const, a.'*». \\z-z\\7 ßeU 11 "Z

где 02 ^ 1/16 - некоторая константа.

Как и ранее, в следствии: £ = 7/Г, ш = ¿/А, а Т(-) - оператор перехода в алгоритме. Под симметричностью А(и) понимается симметричность всех существующих дифференциалов.

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

алгоритм существенно более эффективен при решении уравнений Навье-Стокса, чем алгоритмы того же класса (например, алгоритм Эрроу-Гурвица) при больших сопс^ф-1^)^ 1) и больших (по меркам рассматриваемых алгоритмов) характерных числах Не (« 1000).

Заключение содержит основные результаты диссертации.

Основные результаты работы

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

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

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

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

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

1. bychenkov Yu.V., Chizhonkov е.v. Optimization of one three-parameter method of solving an algebraic system of the Stokes type. // Russian Journal of Numerical Analysis and Mathematical Modeling, 1999, vol. 10, №1, p. 33 - 40.

2. БЫЧЕНКОВ Ю.В. Трехпараметрический метод для решения уравнения Навье-Стокса. // Четвертый сибирский конгресс по прикладной и индустриальной математике, посвященный памяти М.А.Лаврентьева (1900-1980): Тез.докл., ч.П.

- Новосибирск: Изд-во Ин-та математики, 2000, с. 77.

3. БЫЧЕНКОВ Ю.В. Асимптотическая оптимизация одного трехпараметрического алгоритма для решения задач с седло-вой точкой. // Труды мат. центра им. Н. И. Лобачевского.

- Казань: Издательство "ДАС", 2001, том 13: Численные методы решения линейных и нелинейных краевых задач, с. 155

- 161.

4. БЫЧЕНКОВ Ю.В. Об одном трехпараметрическом методе решения уравнений Навье-Стокса. // ЖВМ и МФ, 2002, том 42, №9, с. 1420 - 1427.

5. БЫЧЕНКОВ Ю.В. Оптимизация трехпараметрических алгоритмов для решения седловых задач. // Доклады Академии Наук, 2002, том 384, №4, с. 439 - 441.

6. Bychenkov Yu.V., Chizhonkov E.V. On optimization of one symmetric algorithm for saddle point problem.// Proceedings of the International Conference on Computational Mathematics. Edited by G.A.Mikhailov, V.P.Il'in, Y.M.Laevsky. - Novosibirsk: ICM&MG Publisher, 2002, p. 97 - 103.

7. Быченков Ю.В., Чижонков Е.В. Об одном подходе к регуляризации задач с седловой точкой. // Материалы Четвертого Всероссийского семинара "Сеточные методы для краевых задач и приложения". - Казань: Изд-во Казанского мат. общества, 2002, с. 40 - 42.

8. bychenkov Yu.V. Optimization of one class of nonsymmetri-zable algorithms for saddle point problems. // Russian Journal of Numerical Analysis and Mathematical Modeling, 2002, vol. 17, №6, p. 521 - 546.

Подписано в печать 21.08.2003 г. Формат 60x90, 1/16. Объем 1,25 п.л. Тираж 100 экз. Заказ №496

Отпечатано в ООО "Фирма Блок" 107140, г. Москва, ул. Русаковская, д. 1. т. 264-30-73 \vww.blok01 centre.narod.ru Изготовление брошюр, авторефератов, переплет диссертаций.

f

I lt I

I

i

I

! i

!

i

Введение

1 Линейные симметричные системы

§1.1 Постановки задач оптимизации

• §1.2 Оптимизация алгоритма в классе К.

§1.3 Свойства некоторых классов функций.

§1.4 Оптимизация алгоритма в классе Ki

§1.5 Оптимизация алгоритма в классе К

§1.6 Оптимизация алгоритма для нерегулярных задач

2 Системы типа Навье-Стокса

§2.1 Постановка задачи.

§2.2 Оценки скорости сходимости алгоритма.

3 Системы с сильно монотонной нелинейной частью

§3.1 Постановка задачи.

§3.2 Оценки скорости сходимости.

Одной из простейших математических моделей динамики жидкости является модель стационарного течения вязкой однородной несжимаемой жидкости в объеме (области) Q С Кп (п = 2,3), которая описывается следующей системой уравнений в безразмерной форме где / : Q —W1 - заданное отображение (вектор постоянных внешних массовых сил). Долгое время эта система оставалась за рамками строгого математического изучения, что тем не менее, не мешало эффективно использовать её для исследования в приложениях. Однако, в 60-х годах прошлого века, благодаря выдающимся трудам О.А. Ладыженской, был найден подход к математическому исследованию этой крайне сложной с математической точки зрения проблемы. В работах О.А. Ладыженской была впервые указана и обоснована корректная постановка задачи (1) (см. [22] и цитированные в ней ссылки). Дальнейшее развитие теории и, в особенности, методов численного решения задач (1) и ей подобных выявило тот факт, что существенную роль для теорем существования и необходимым условием сходимости многих алгоритмов играет, так называемое, условие -v Ай + (и • V)u + Vp = /, xGQ, divu = 0, x 6 < й = 0, х едП,

1)

Ладыженской-Бабушки-Брецци (ЛББ-условие) и его дискретные аналоги, имеющее вид

7|ИК sup {P\.d™U) VpGL2(Q)/R, (2) 0^е(я01(О))тг INIi где Hq(Q) = Wj^) - пространство Соболева, || -1|2 - норма в этом пространстве, || || - норма в а константа 7 > 0 зависит только от области Q.

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

Uw + вР = /

В и = д где А(и) = —i/Aqu+N(u)u, В - дискретные аналоги операторов —ь>/\й+(й • V)it + - divit • й, grad, a U Э и, Р Эр - конечномерные аппроксимации пространств (Я(}(0))п и при этом {A(u)v,v) ^ 0, u,v е U.

Такие системы уравнений относятся к классу, так называемых, задач с седловыми операторами, наиболее общая форма которых где А(и) и С(р) - абстрактные локально монотонные операторы в соответствующих евклидовых пространствах. Системы вида Bp = f

- С(р) = 9

4)

4) довольно часто возникают в приложениях: кроме численного решения задач механики вязкой жидкости ещё и в теории зовании смешанных аппроксимаций эллиптических уравнений, в методах декомпозиции и др. ([14], [45], [37], [33], [27]) При этом главенствующую роль для теоретического анализа все таки играют системы вида (3), исследованию алгоритмов решения которых и посвящена данная работа.

К настоящему времени, предложено немалое количество эффективных алгоритмов для решения задач подобного вида (см., * например, [33], [14], [34], [15], [28] и цитированную в них литературу). Среди самых простых можно выделить обобщенный итерационный алгоритм Эрроу-Гурвица (оригинальный алгоритм (Q = I) впервые появился в [33]) где Q : U —>• U - положительно определенный самосопряженный оператор в U. Алгоритмы такого типа до сих пор не потеряли свою привлекательность, что связано с простотой их реализации и минимальными требованиями к объему памяти. Особенно стоит подчеркнуть, что в случае линейных симметричных сед-ловых задач, предельные характеристики эффективности этого алгоритма (Q = А, г - "оптимальные") по порядку не уступают многим другим, более сложным алгоритмам [28].

После своего появления, алгоритм (5) неоднократно подвергался различным модификациям и обобщениям. Так в работе [43] в алгоритм (5) (в контексте задачи Стокса), по-видимому впервые, было введено дополнительное слагаемое XBB*uk, А > упругости, в математическом программировании, при исполь

5)

О в следующем виде

7/^+1 qjk

Q- + А(ик) + \ВВ*ик + Врк =f + \Bg

-/3 (pk+1 - рк) + В* uk+1 = д

6) однако, судя по всему, этой модификации автором не придавалось большое значение (величина Л считалась фиксированной константой). В отечественной литературе подобное слагаемое было введено Г.М. Кобельковым в [16]. В этой работе (для решения задачи Навье-Стокса) был построен алгоритм следующего вида к+1 к

Q--— + А(ик) + f3'lBB*uk + В рк =f + /3~1Bg

-Р (;рк+1 - рк) + В* uk+1 = д

7) но, что самое главное, впервые была подчеркнута особая роль слагаемого j3~lBB*uk в ускорении сходимости алгоритма, что подтвердилось для нелинейных задач результатами численных экспериментов.

Дальнейшее обобщение этих идей приводит к следующему алгоритму, который является основным объектом исследования этой работы: к-\-1 к

QU ~U + (А(ик) + f3BC~lB*uk) + В рк = / + ($В С~1д -а С (рк+1 - рк) + В* ик+1 = д

8)

Здесь Q : U —> U, С : Р —»• Р - положительно определенные самосопряженные операторы, a>0,r>0,/3eR - итерационные параметры, и0 £ Q, р° £ Р - начальные приближения. Основной особенностью этого алгоритма является наличие трех независимых итерационных параметров. Еще раз отметим, что частным случаем этого алгоритма являются алгоритмы Эрроу-Гурвица (/3 = О, С = I) и Кобелькова (/3 = а-1, С = /), a таьсже модифицированный метод верхней релаксации (MSOR) в случае незнакоопределенной симметричной матрицы [55].

Расширение класса решаемых задач приводит к дальнейшему обобщению алгоритма. Так для решения линейных задач с вырожденным оператором А в работе рассматривается четы-рехпараметрическая модификация алгоритма Q иМ~ +(Avuk + /3BC-1B*uk) + В pk = f (9) -аС (рш - pk) + В* uk+1 = д где Av = А + vBC~xB\ f = f + ((3 + и)В C~lg. Особенность этого алгоритма заключается в том, что четвертый параметр ь> > О входит в постановку задачи оптимизации, поэтому не может быть явно исключен из алгоритма.

Исследованию алгоритмов из класса (8) (в основном алгоритму Эрроу-Гурвица (/3 = 0)) посвящено немалое количество работ. Кроме исследования свойств сходимости алгоритма в таких работах как [33], [27], [43], [16], существует множество работ связанных с оптимизацией скорости сходимости, большинство которых относится к случаю линейных симметричных задач. Рассмотрим подробнее этот класс задач. Во многих случаях в качестве дополнительной информации к постановке задачи оптимизации авторы предполагают, что выполнены неравенства

7С < В*А~гВ ^ ГС, SQ^A^AQ, (10) первое из которых является аналогом ЛББ-условия (2) для задачи Навье-Стокса, а последние связаны с задачей построения эффективных предобуславливателей для оператора А (оператор Лапласа в задаче Стокса), кроме того, иногда используется альтернативная постановка

5Q^A^AQ. (11)

Отметим, что в случае S = А обе постановки эквивалентны. По видимому, пионерской работой в области оптимизации (8) является работа [51], в которой для специальной нормы ошибки приближения на к-ой итерации алгоритма получена специальная оценка вида ^ ot)eо и найдено оптимальное значение go = min а), которое удовлетворяет неравенству а,т> О

Яо К \J 1 - Coptic2 < 1 - ^ 1/8 < Copt < 1, где а; = <$/Д, £ = 7/Г.

В дальнейшем этот результат был улучшен в работе [35] и получен показатель скорости сходимости q = I ((1 - Qu + " О2"2 + 4(1 - ы)) < 1 - ^ а*.

Позднее эта оценка была уточнена в [56], но без качественного улучшения показателя.

Существенно иной подход был предложен в работе [1] и получена следующая асимптотика оптимального показателя

Я opt ~ 1 - 2апри £ —>• О, си у 1.

И, наконец, в работе [29] при специальных дополнительных условиях на алгоритм были получены точные формулы для оптимального показателя сходимости со следующей асимптотикой qopt ~ 1 ~ \ VC, ПРИ f 0, cj = const. у ^ — LJ

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

Теорема 1. Пусть оператор А — линейный самосопряженный положительно определенный и выполнены следующие неравенства В* А'1 В < Г С, SQ ^ А < A Q, где 0 < £ ^ Д, 0 < 7 ^ Г - фиксированные величины. Тогда задача асимптотической оптимизации алгоритма (8) имеет единственное решение

Г + 7 (l-g02)2 1-9о2

25 (2u,-l) + gg >0' А = 0, = —>0' где £ = 7/Г, и = 5/A, a qo является единственным на интервале (0,1) корнем уравнения q3 - (1 + + " 1)д + (1 - ш) = 0.

Указанная теорема дает окончательный ответ о пределах сходимости алгоритма в терминах спектрального радиуса оператора перехода. Как известно из общей теории итерационных методов, спектральный радиус оператора перехода итерационного алгоритма дает точную нижнюю и асимптотическую оценки скорости сходимости метода в терминах любой фиксированной нормы (см. [26]). Тем не менее, даже при "хороших" значениях этой величины (например, ^1/2), реальный итерационный процесс может быть неустойчив и расходиться (см., например, [2]). Такое поведение в основном обусловлено внутренней структурой оператора перехода, а именно, наличием в жордановой форме оператора клеток достаточно больших размеров. Однако, известно, что при различных естественных ограничениях на исходный алгоритм (8), оператор перехода имеет жордановы клетки ограниченного порядка. Например [29], если пространство ker В* и его ортогональное дополнение инвариантны относительно оператора Q~lA, то оператор перехода в методе имеет жордановы клетки не более чем второго порядка.

Оптимизация такого класса алгоритмов как (8) носит сложный технический и теоретический характер. Это связано с тем, что обычно получаемые в результате оценок спектра оператора перехода минимаксные задачи носят неаналитический (или очень сложный аналитический) и недифференцируемый характер, что крайне затрудняет, а часто просто делает невозможным, применение стандартных методов теории минимаксных задач. Для преодоления этих трудностей при доказательстве теоремы 1 были разработаны и исследованы специальные классы функций на прямой, а также особый аппарат доказательства. Использование этого аппарата позволило в дальнейшем получить аналогичные результаты для других задач и алгоритмов. В частности, в этой работе доказан результат аналогичный теореме 1, но для другой постановки задачи - (11), а также для задач с вырожденным А в случае алгоритма (9).

Кроме линейного алгоритма в данной работе был также исследован трехпараметрический алгоритм (8) для нелинейных задач с квадратичной нелинейностью типа Навье-Стокса и задач с сильно монотонной нелинейностью.

Диссертация состоит из введения, трех глав, приложения и заключения.

Основные результаты работы состоят в следующем:

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

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

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

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

Заключение

1. Астраханцев Г.П. Анализ алгоритмов типа Эрроу-Гурвица. ПЖВМиМФ, 2001, том 41, № 1, с. 17 - 28.

2. Бахвалов Н.С. Численные методы М.: Наука, 1975, 632 с.

3. Бахвалов Н.С., Кобельков Г.М., Чижонков Е.В. Эффективные методы решения уравнений Навье-Стокса. Численное моделирование в аэрогидродинамике. М.: Наука, 1998, с. 37^5.

4. Борисович Ю.Г., Близняков Н.М., Израилевич Я.А., Фоменко Т.Н. Введение в топологию. М.: Наука, 1995, 416 с.

5. Быченков Ю.В. Об одном трехпараметрическом методе решения уравнений Навье-Стокса. // ЖВМ и МФ, 2002, том 42, №9, с. 1420- 1427.

6. Быченков Ю.В. Оптимизация трехпараметрических алгоритмов для решения седловых задач. // Доклады Академии Наук, 2002, том 384, №4, с. 439 441.

7. Быченков Ю.В., Чижонков Е.В. Об одном подходе к регуляризации задач с седловой точкой. // Материалы Четвертого Всероссийского семинара "Сеточные методы для краевых задач и приложения". — Казань: Изд-во Казанского мат. общества, 2002, с. 40-42.

8. Валединский В.Д., Кобельков Г.М. О разностном аналоге неравенства ||р||ь2 ^ C||grad р \\w-i. II Матер, сем. ОБМАН СССР, Препринт, Москва, 1983, №67.

9. Воеводин В.В., Кузнецов Ю.Ф. Матрицы и вычисления. М.: Наука, 1984, 320 с.

10. Годунов С.К. Современные аспекты линейной алгебры. Новосибирск: Научная книга, 1997, 390 + xxvi с.

11. Демьянов В.Ф., Малозёмов В.Н. Введение в мини-макс. М.: Наука, 1972, 368 с.

12. Дьяконов Е.Г. Минимизация вычислительной работы. Асимптотически оптимальные алгоритмы для эллиптических задач. М.: Наука, 1989.

13. Кобельков Г.М. О численных методах решения уравнений Навье-Стокса в переменных скорость давление. Вычислительные процессы и системы, вып. 8. М.: Наука, 1991, с. 204-236.

14. Кобельков Г.М. О методах решения уравнений Навье-Стокса. II Докл. АН СССР, 1978, том 243, №4, с. 843 -846.

15. Кобельков Г.М. Об эквивалентных нормировках подпространств Ь2. П Analysis Mathematica, 1977, том 3, №3, с. 177- 186.

16. Кобельков Г.М. Решение задачи о стационарной свободной конвекции. П Докл. АН СССР, 1980, том 255, №2, с. 277 282.

17. Красносельский М. А. Топологические методы в теории нелинейных интегральных уравнений. M.-JL: Госте-хиздат, 1956, 392 с.

18. Красносельский М. А., Забрейко П.П. Геометрические методы нелинейного анализа. М.: Наука, 1975, 512 с.

19. Кураев Г.Н. Задача о стационарной свободной конвекции при нелинейных граничных условиях. Л ЖВМ и МФ, 1978, том 18, №3, с. 784-789.

20. Ладыженская О.А. Математические вопросы динамики вязкой несжимаемой жидкости. М.: Наука, 1970, 288 с.

21. Ладыженская О.А., Солонников В.А. О некоторых задачах векторного анализа и обобщенных постановках краевых задач для уравнений Навье-Стокса. // Зап. науч. сем. ЛОМИ АН СССР, 1976, №59, с. 81 118.

22. Лебедев В.И. Метод сеток для уравнений типа Соболева. И Докл. АН СССР, 1956, том 114, №6, с. 1166 1169.

23. Пасконов В.М., Полежаев В.И., Чудов JI.A. Численное моделирование процессов тепло и массообмена. М.: Наука, 1984, 285 с.

24. Самарский А.А., Николаев Е.С. Методы решения сеточных уравнений. М.: Наука, 1978, 592 с.

25. Темам Р. Уравнения Навье-Стокса. М.: Мир, 1981, 408 с.

26. Чижонков Е. В. Релаксационные методы решения сед-ловых задач. М.: ИВМ РАН, 2002, 239 с.

27. Чижонков Е.В. Об одном обобщенном релаксационном методе решения линейных задач с седловым оператором. // Машем, моделирование, 2001, том 13, № 12, с. 107 114.

28. Чижонков Е.В. О сходимости алгоритма Эрроу -Гурвица для алгебраической системы типа Стокса. // Доклады Академии Наук, 1998, том 361, №5, с. 1 3.

29. Чижонков Е.В. О сходимости одного алгоритма для решения задачи Стокса. // Вестник Моск. Ун-та. Сер. 15: Вычисл. матем. и киберн., 1995, №2, с. 12-17.

30. Чижонков Е.В. К сходимости метода искусственной сжимаемости. // Вестник Моск. Ун-та. Сер. 1: Математика, механика., 1996, №2, с. 13 — 19.

31. Arrow К., Hurwicz L., Uzawa Н. Studies in Nonlinear Programming. Stanford, CA: Stanford University Press, 1958, 334 p.

32. Bramble J.H., Pasciak J.E. A preconditioning technique for indefinite systems resulting from mixed approximations of elliptic problems. // Mathematics of Computation, 1988, vol. 50, №181, p. 1 17.

33. Bramble J.H., Pasciak J.E., Vassilev A.T. Analysis of the inexact Uzawa algorithm for saddle point problems. // SIAMJ. Numer. Analys., 1997, №3, p. 1072 1092.

34. Bramble J.H., Pasciak J.E., Vassilev A.T. Inexact Uzawa algorithms for nonsymmetric saddle point problems. // Math. Сотр., 2000, vol. 69, №230, p. 667 689.

35. Brezzi F., Fortin M. Mixed and Hybrid Finite Element Methods. New York: Springer Verlag, 1991, 350 p.

36. Bychenkov Yu.V. Optimization of one class of nonsymmetrizable algorithms for saddle point problems // Russian Journal of Numerical Analysis and Mathematical Modeling, 2002, vol. 17, №6, p. 521 546.

37. Bychenkov Yu.V., Chizhonkov E.V. Optimization of one three-parameter method of solving an algebraic system of the Stokes type. // Russian Journal of Numerical Analysis and Mathematical Modeling, 1999, vol. 10, № 1, p. 33 40.

38. Chizhonkov E.V. On Solving an Algebraic System of Stokes Type under Block Diagonal Preconditioning. // Сотр. Math, and Math. Physics., 2001, vol. 41, №4, p. 514 521.

39. Clarke F.H. Optimization and Nonsmooth Analysis. New York: Wiley, 1983, 308 p.

40. Crouzeix M. Etude d'une methode de linearisation. Resolution numberique des equations de Stokes stationnaires. Application aux equations de Navier-Stokes stationnaires. // IRIA, 1974, № 12, p. 141 244.

41. Crouzeix M., Ravi art P. A. Conforming and nonconforming finite element methods for solving the stationary Stokes equations. // R.A.I.R.O., 1973, №R-3, p. 77 104.

42. D'yakonov E. G. Optimization in solving elliptic problems. New York: CRC Press, 1996, 562 p.

43. Elman H., Silvester D. Fast nonsymmetric iterations and preconditioning for Navier-Stokes equations. // SIAM J. Sci. Copmut., 1996, vol. 17, p. 33 46.

44. Golub G.H., Wathen A.J. An iteration for indefinite systems and its application to the Navier-Stokes equations. // SIAM J. Sci. Comput., 1998, vol. 19, №2, p. 530 539.

45. Hackbusch W. Multi-Grid Methods and Applications. Berlin-Heidelberg: Springer-Verlag, 1985, 377 + xiv p.

46. Queck W. The convergence factor of preconditioned algorithms of the Arrow-Hurwicz type. // SI AM J. Sci. Copmut., 1989, №4, p. 1016 1030.

47. Rannacher R., Turek S. A simple nonconforming quadrilateral Stokes element. // Numer. Meth. Part. Diff. Equ., 1992, №8, p. 97-111.

48. Turek S. Efficient Solvers for Incompressible Flow Problems: An Algorithmic and Computational Approach. Springer Verlag, 1999, 310 p.

49. Xiaojun Chen. On preconditioned Uzawa methods and SOR methods for saddle-point problems. // J. of Сотр. and Appl. Math., 1998, № 100, p. 207 224.

50. Young d.m. Iterative Solution of Large Linear Systems. New York: Academic Press, 1971.

51. Zulehner W. Analysis of iterative methods for saddle point problems: a unified approach. // Math. Сотр., 2002, vol. 71, №238, p. 479-505.

52. Finite Element Analysis Tool (FEATFLOW).http://www.feat/low. de.