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

Одной из простейших математических моделей динамики жидкости является модель стационарного течения вязкой однородной несжимаемой жидкости в объеме (области) 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]). Тем не менее, даже при «хороших» значениях этой величины (например, ^½), реальный итерационный процесс может быть неустойчив и расходиться (см., например, [2]). Такое поведение в основном обусловлено внутренней структурой оператора перехода, а именно, наличием в жордановой форме оператора клеток достаточно больших размеров. Однако, известно, что при различных естественных ограничениях на исходный алгоритм (8), оператор перехода имеет жордановы клетки ограниченного порядка. Например [29], если пространство ker В* и его ортогональное дополнение инвариантны относительно оператора Q~lA, то оператор перехода в методе имеет жордановы клетки не более чем второго порядка.

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

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

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

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

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

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

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

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

Заключение

.