ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2007, том 47, < 2, с. 197-205
УДК 519.642.8
О СПЕКТРАЛЬНЫХ СВОЙСТВАХ ОДНОГО ПУЧКА ОПЕРАТОРОВ1*
© 2007 г. Ю. В. Быченков
(119922 Москва, Ленинские горы, МГУ, мехмат) e-mail: bychenkov@yahoo .com Поступила в редакцию 10.04.2006 г.
Переработанный вариант 07.07.2006 г.
Изучение сходимости и оптимальных свойств широкого класса итерационных алгоритмов для решения седловых задач сводится к анализу собственных значений операторных пучков специального вида. Предложен новый подход к исследованию спектральных свойств таких пучков, позволяющий во многих случаях получать точные оценки скорости сходимости алгоритмов. Библ. 7.
Ключевые слова: седловой оператор, пучок операторов, спектральные свойства, оценка скорости сходимости.
1. ВВЕДЕНИЕ
Построение эффективных алгоритмов решения задач с седловыми операторами является одной из актуальных задач современной вычислительной математики, что обусловлено широким использованием таких задач в приложениях (см. обзор [1]). Преобладающую роль при построении алгоритмов играет класс разреженных седловых задач больших размерностей, для решения которых применяются в основном итерационные алгоритмы.
Как показывает практика, анализ сходимости и тем более оптимизация итерационных алгоритмов решения седловых задач является сложной задачей, требующей применения индивидуальных подходов в каждом конкретном случае. Однако общий шаг в исследовании многих алгоритмов состоит в сведении проблемы к изучению свойств некоторого полиномиального операторного пучка %(X) = P(X, L, G), где X е С, L, G - линейные эрмитовы операторы в конечномерном эрмитовом пространстве U.
Анализ существующих алгоритмов показывает (в данной работе на этом анализе не заостряется внимание), что для обширного класса задач исследование сходимости может быть сведено к изучению спектра
°(%) = {X е С | ker%(X) Ф {0}}
пучка %(X) вида
X(X) = f(X, L)g(X, G) + h(X)G, f е С[X, *], g е С[Х, t], h е С[X], (1.1)
в предположениях
L = L*, o(L)c[6j,62], 6j,62 е U, 5j < 82, (1.2)
G = G* > 0, o( G) с {0 }u[Yl,Y2 ], Yi,Y2 е U, 0 <Yl <У2- (1.3)
Здесь и далее приняты следующие обозначения: C[zb ..., zk] - кольцо многочленов от переменных zx, ..., zk,kе N, с коэффициентами в С, c(A) - спектр линейного оператора A (т.е. спектр пучка A - XI).
Универсальные подходы к исследованию спектральных свойств пучка (1.1) позволяют значительно облегчить изучение сходимости алгоритмов для решения задач с седловыми операторами. Один из таких подходов для частного случая пучка (1.1) предложен в [2]. Подход базируется на использовании операторных неравенств и позволяет получать хорошие оценки сходимости некоторых алгоритмов (алгоритмы типа Эрроу-Гурвица и алгоритмы с симметричными предо-
Работа выполнена при финансовой поддержке РФФИ (код проекта 05-01-00511).
бусловливателями), недостаток подхода состоит в сужении класса алгоритмов и недостаточной точности оценок (даже по порядку величин). Другой, более общий подход, фактически представлен в работах Е.В. Чижонкова (см., например, [3]) и основан на дополнительном предположении, сужающем класс рассматриваемых задач: ядро оператора G инвариантно относительно Ь. Этот подход позволил получить, как оказалось, точные оценки сходимости многих алгоритмов для седловых задач.
Ниже предлагается новый универсальный подход к исследованию спектральных свойств пучка (1.1), в частности позволяющий получать простые и точные оценки скорости сходимости многих итерационных алгоритмов для решения седловых задач.
2. ОЦЕНКИ СПЕКТРА ПУЧКА ОПЕРАТОРОВ Всюду далее будем считать, что %(X) - операторный пучок вида (1.1).
Теорема 1 (нижняя оценка). Пусть Mс С - конечное непустое множество, cardM < dim U, причем для любого X е Mнайдутся s0 е [5j, 52], t0 е [у^ у2] такие, что f(X0, s0) = 0 или fX0, s0)g(X0, t0) + + h(X0)t0 = 0; тогда существуют линейные операторы L и G в U, удовлетворяющие (1.2), (1.3), такие, что M с с(%).
NU
Доказательство. Пусть [в,}i = 1 - произвольный ортонормированный базис в U, NU = dim U.
NM
Пусть M = [Хг-} = 1, где NM = cardM > 0, NM < NU. По условию, существуют s. е [5Ь 52], ti е {0} и и [Ух, У2] такие, что f(Xt, s,)g(k,, t) + h(k,)t, = 0, i = 1, 2, ..., Nm.
Зададим операторы L и G следующими соотношениями при i = 1, 2, ..., NU:
Гsiei, если i< NM, Гtiei, если i< NM,
Let = \ Gei = \
[sNMet, если i > Nm, [ tNuet, если i > Nm.
Несложно убедиться, что определенные таким образом операторы L и G удовлетворяют предположениям (1.2), (1.3), причем при i = 1, 2, ..., NM имеем
%(Хг)вг = (fa, s;)ga, tt) + h(Хг)tt)вг = 0,
т.е. X. е c(%). Теорема доказана.
Основное следствие этого результата состоит в том, что любая верхняя оценка с(%) на классе операторов (1.2), (1.3) содержит множество решений X(s, t), удовлетворяющих одному из уравнений
f(X, s) = 0, f(X, s)g(X, t) + h(X)t = 0
при различных s е [51, 52], t е [y1, у2]. В дальнейшем будут указаны условия, при которых эта оценка является точной.
Отметим, что при анализе свойств алгоритмов для решения седловых задач собственные значения пучка x(X), удовлетворяющие условию g(X, 0) = 0, чаще всего исключаются из рассмотрения. В связи с этим все последующие утверждения построены таким образом, чтобы отбросить эти значения еще на этапе формулировки условий. Тем не менее это не ограничивает общности оценок, которые в случае необходимости могут быть свободно расширены за счет добавления решений уравнения g(X, 0) = 0.
Теорема 2 (верхняя оценка). Пусть выполнены предположения (1.2), (1.3), X0 е с(%) и g(X0, 0) Ф 0, тогда или найдется s0 е [51, 52] такое, что
f(Xo, so) = 0,
или, если такого s0 не существует,
conv{Г1 g(X), t) I t е [уi, y2]} + conv{ДХ0, s)_1h(X0) | s е [61,62]} э 0,
где conv обозначает замкнутую выпуклую оболочку множества в С.
Доказательство. Пусть выполнены условия теоремы, тогда существует вектор u е U\{0} такой, что x(X0)u = 0. Обозначим линейный операторf(X0, L) символом S. Еслиf(X0, s0) = 0 для некоторого s0 е [61, 62], то теорема доказана.
Предположим, что/(À0, s) Ф 0 для любого s е [ô1, ô2], тогда
о(S) = {/(Ào, s) | s е с(L)}ç{/(Ào, s) | s е [Si, S2]} (2.1)
и, следовательно, 0 g o(S), т.е. оператор S обратим. Из указанного предположения также следует, что Gu Ф 0: действительно, если Gu = 0, то
0 = X(^o)u = /(Ào, L)g(Ào, G)u = Sg(Ào, 0)u,
а так как по условию g(À0, 0) Ф 0, то u е kerS, что приводит к противоречию.
Представим вектор u в виде u0 + u1, где u0 е H = ker G, u1 е K = (ker G)1 = im G, а спектральную задачу - в виде
g(Ào, G)u + ST1 h(Ào)Gu = o.
Умножим справа скалярно обе части уравнения на Gu, затем разделим на (Gu, Gu) Ф 0, при этом воспользуемся равенствами Gu = Gu1, (u, Gu) = (u1, Gu1), тогда получим
(g ( Ào , G ) u i , Gu i ) + ( У1 h ( Ào ) Gu i , Gu i ) = o (22)
( Gui, Gu1 ) ( Gui, Gu1 )
Оператор F = G|K : K —- K самосопряжен в K и c(F) ç fy, y2], следовательно, оператор F_1g(Ào, F) нормальный и a(g(À0, F)) = g(À0, c(F)); таким образом, имеем
( g(Ào, G ) ui, Gui ) ( F'1 g(Ào. F) Fub Fui) {.-i (À [Y Y ]}
( G ui, Gui ) = -Fi"FÛ)-Ç COnv{ t g(Ào' 0 I tе ^]}. (2.3)
Так как оператор L самосопряженный, то оператор S = f(À0, L) нормальный, следовательно, оператор S-1 также нормальный, поэтому
( ^ h GÀ° Gu )Gui ) Ç conv{ /(Ào, s )-i h (Ào ) I s е [Si,S2 ]}. (2.4)
Из соотношений (2.2), (2.3), (2.4) немедленно следует утверждение теоремы. Во многих задачах априорно известно (см., например, [2], [4], [5]), что спектр операторного пучка (1.1) является вещественным; в этом случае полезно следующее следствие теоремы 2.
Следствие 1. Пусть выполнены условия теоремы 2 и многочленыf(À, s) и g(À, t) имеют вещественные коэффициенты. Если À0 е [, тогда существуют s0 е [S1, S2], t0 е [Y1, y2] такие, что
f(À0, s0) = 0 илиf(À0, s0)g(À0, t0) + h(À0)t0 = 0.
Доказательство. Предположим, что для любого s е [S1, S2] выполнено неравенство f(À0, s) Ф 0, тогда, по теореме 2, имеет место включение
conv{t -g(Ào, t) I t е [yi, Y2]} + conv{/(Ào, s)-ih(Ào) | s е [Si, S2]} э o.
Из условия следует, что многочлен P(s) = /(À0, s) обладает вещественными коэффициентами, а значит, образ отрезка [S1, S2] под действием P является отрезком в [\{0}. Так как h(À0) не зависит от s, то множество
{/(Ào, s)-ih(Ào) I s е [Si, S2]} = {P(s)-ih(Ào) I s е [Si, S2]}
является отрезком в С, а значит, выпуклым, замкнутым множеством. Аналогичным образом доказывается, что {t_1g(À0, t) | t е [y1, у2]} также является выпуклым замкнутым множеством. Следовательно, имеет место включение
{t'1 g(Ào, t) | t е [yi, Y2]} + {/(Ào, s)-ih(Ào) | s е [S^]} э o, поэтому найдутся t0 е [y1, y2], s0 е [S1, S2] такие, что
t-ig(Ào, to) + /(Ào, so)-ih(Ào) = o,
что эквивалентно равенству
/(Ào, so ) g (Ào, to ) + h (Ào )to = o.
Следствие доказано.
Отметим, что полученная в следствии оценка совпадает с нижней оценкой, полученной в теореме 1, следовательно, является точной.
3. ОЦЕНКИ СПЕКТРАЛЬНОГО РАДИУСА
Минимизация спектрального радиуса оператора перехода является основой асимптотической оптимизации стационарных алгоритмов. Величина спектрального радиуса оператора перехода алгоритмов такого типа непосредственно связана с величиной
р(Х) = sup IX. (3.1)
Хе с(%)
g(X, 0) Ф 0
Оценки р(х) можно вывести как следствие оценок спектра, полученных в теореме 2, однако целесообразно получение более компактных и удобных оценок при дополнительных ограничениях на вид операторного пучка (1.1).
Пусть Pе С[г1, ..., zn],nе N, тогда обозначим через degz Pстепень многочлена PI 0 е C[z]
1 lzi = i ф j
при фиксированных zi = z0, i Ф j.
Теорема 3. Пусть выполнены предположения (1.2), (1.3). Дополнительно предположим, что degf < 1, degtg < 1 и величина
degx(f (X, si)f (X, s2)g(X, t) + f(X, s3)h(X)t) > 0
не зависит от s1, s2, s3 е [61, 62], t е [y1, y2]; тогда имеем
p(X)< max {|X(s, t)|},
s е [81,82] t е [Y1, Y2]
где максимум берется по всем X(s, t), удовлетворяющим одному из уравнений
f(X, s) = 0,
f(X, s)g(X, t) + h(X)t = 0, (3.2)
f(X, 81)f(X, 82)g(X, t) + f(X, s)h(X)t = 0.
Доказательство. Для начала отметим, что из усло
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.