Журнал вычислительной математики и математической физики, 2020, T. 60, № 6, стр. 963-974

1. ВВЕДЕНИЕ

В небольшой заметке [1] Л. Фейер сформулировал следующее определение поточечной близости точки к некоторому множеству.

Определение 1. Пусть $M$ – замкнутое множество из ${{\operatorname{R} }^{n}}$ (или гильбертова пространства). Если для точек $p$ и ${{p}_{1}}$ из ${{\operatorname{R} }^{n}}$ выполнено неравенство $\left\| {p - q} \right\| > \left\| {{{p}_{1}} - q} \right\|$ для любого $q \in M,$ то будем говорить, что ${{p}_{1}}$ поточечно ближе к $M,$ чем $p.$ Причем, если для $p$ не существует точек ${{p}_{1}},$ которые поточечно ближе, чем $p,$ тогда точку $p$ назовем ближайшей к множеству $M.$

Кроме того, им было отмечено, что множество ближайших к $M$ точек совпадает с замкнутой выпуклой оболочкой $\overline {{\text{conv}}(M)} $ множества $M.$ Из этого факта непосредственно вытекает, что если точка $p$ не принадлежит $\overline {{\text{conv}}(M)} ,$ то можно найти точку ${{p}_{1}},$ которая поточечно ближе к множеству $M,$ чем $p.$

На основе определения 1 поточечной близости точки к множеству и отмеченного геометрического факта Т. Моцкин и Дж. Шенберг [2] ввели определение монотонной фейеровской последовательности $\{ {{x}_{k}}\} ,$ для которой ${{x}_{k}} \ne {{x}_{{k + 1}}},$ $\left\| {{{x}_{{k + 1}}} - q} \right\| \leqslant \left\| {{{x}_{k}} - q} \right\|$ $\forall q \in M,$ и предложили релаксационный метод решения систем линейных неравенств. Дальнейшие исследования по методам построения фейеровских последовательностей для задач линейного и выпуклого программирования были продолжены в работах [3], [4]. И.И. Ереминым были введены более общие понятия, связанные с именем Л. Фейера: фейеровский оператор, фейеровский процесс, установлены их свойства и важные факты, которые определили широкий простор для построения итерационных фейеровских методов решения задач математического программирования в ${{\operatorname{R} }^{n}}$, в том числе, несобственных [5], [6] (см. также [7]).

В работе автора [8] было дано определение класса псевдосжимающих операторов, который в книге [8] в рамках единого подхода был переименован в класс сильно M-фейеровских операторов, поскольку эти операторы обладают более сильным свойством сжимаемости, чем фейеровские операторы, введенные И.И. Ереминым, и удовлетворяют тем же базовым условиям. Свойство сильной M-фейеровости оказалось весьма полезным при исследовании итерационных методов решения линейных и нелинейных обратных некорректных задач в бесконечномерных пространствах, что обусловлено уникальными свойствами процессов с фейеровскими операторами шага, а именно.

1. Неединственность решения задачи не является препятствием для применения (сильно) фейеровского процесса.

2. Классы фейеровских операторов замкнуты относительно операций произведения отображений и взятия выпуклой суммы.

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

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

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

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

2. ОСНОВНЫЕ КЛАССЫ ОПЕРАТОРОВ ФЕЙЕРОВСКОГО ТИПА И ИХ ВЗАИМОСВЯЗЬ

В приводимых ниже определениях классов нелинейных операторов используется двойная терминология. С одной стороны, в качестве основного понятия выступает свойство фейеровости, а с другой, в качестве сравнения привлекается терминология, которая встречается в несколько иной форме в различных разделах функционального анализа. Далее в статье мы будем использовать только ту терминологию, которая была введена в первых работах по фейеровским процессам и основана на идее поточечной аппроксимации множества, восходящей к работе [1]. Если не оговаривается особо, то в дальнейшем предполагается, что исследуемые операторы действуют в гильбертовом пространстве, для которого примем обозначение $H,$ а через ${\text{Fix}}(T)$ обозначим множество неподвижных точек оператора $T,$ т.е.

Определение 2. Оператор $T:H \to H$ называется слабо M-фейеровским (или M-квазинерастягивающим), если $M = {\text{Fix}}(T) \ne \emptyset $ и выполнено неравенство

обозначим класс таких операторов через ${{\mathcal{K}}_{M}}.$

Определение 3. Оператор $T:H \to H$ называется M-фейеровским (или строго M-квазинерастягивающим), если $M = {\text{Fix}}(T) \ne \emptyset $ и

обозначаем этот класс через ${{\mathcal{F}}_{M}}.$

Определение 4. Оператор $T:H \to H$ называется сильно M-фейеровским (или M-псевдосжимающим), если $M = {\text{Fix}}(T) \ne \emptyset $ и существут константа $\nu $ такая, что

обозначаем класс таких операторов через $\mathcal{P}_{M}^{\nu }$.

Определение 5. Оператор $T:H \to H$ называется нерастягивающим (нерасширяющим), если выполнено неравенство

обозначим этот класс операторов $\mathcal{K}$. Из определений 2–4 следует, что для введенных классов справедливы включения причем, как показывают примеры (см. [9]), эти включения строгие.В дальнейшем при упоминании о свойстве фейеровости оператора, как правило, будут опускаться слова “слабо” и “сильно”, если из текста ясно, о каком классе фейеровских операторов идет речь. Заметим, что сильную M-фейеровость, с одной стороны, можно рассматривать как некоторое обобщение свойства псевдосжимаемости Б. Мартине [10] для нерастягивающего оператора, а с другой, как усиление свойства M-фейеровости, введенное в [6].

Лемма 1. Если оператор $V:H \to H$ и $V \in {{\mathcal{K}}_{M}},$ тогда для $\lambda \in (0,1)$ оператор $T = \lambda V + (1 - \lambda )I$ принадлежит классу $\mathcal{P}_{M}^{\nu }$ для $\nu = (1 - \lambda ){\text{/}}\lambda .$ Обратно, если $T \in \mathcal{P}_{M}^{\nu },$ то $T = \tfrac{1}{{1 + \nu }}V + \tfrac{\nu }{{1 + \nu }}I,$ где $V \in {{\mathcal{K}}_{M}}.$

3. ОСНОВНЫЕ ПОСТАНОВКИ НЕЛИНЕЙНЫХ НЕКОРРЕКТНЫХ ЗАДАЧ

1. Минимизация выпуклого функционала

где $\phi {\kern 1pt} :\;H \to {{\operatorname{R} }^{1}}$ – полунепрерывный снизу выпуклый (в частности, квадратичный) функционал, $Q$ – выпуклое замкнутое подмножество гильбертова пространства $H$, которое называется допустимым множеством, $\phi {\text{*}}$ – оптимальное значение, множество $M$ решений задачи (3.1) называется оптимальным множеством. Если $\phi $ – сильно выпуклый функционал, то задача (3.1) корректно поставлена по Тихонову, однако выпуклость целевого функционала не гарантирует корректность задачи.

2. Решение вариационного неравенства

где $F$ – оператор, действующий в гильбертовом пространстве $H$, $Q - $ выпуклое замкнутое подмножество пространства $H$, $\left\langle {\,,\,} \right\rangle $ обозначает скалярное произведение в пространстве $H$.

3. Нахождение неподвижной точки нелинейного оператора $T:H \to H$, т.е. решение уравнения II рода

4. Нахождение решения нелинейного операторного уравнения I рода

где оператор $A$ действует на паре гильбертовых пространств, для которого обратный ${{A}^{{ - 1}}},$ в общем случае, разрывный.

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

Теорема 1. Для того чтобы точка $x{\text{*}}$ была решением задачи (3.1) минимизации выпуклого дифференцируемого по Гато функционала, необходимо и достаточно, чтобы точка $x{\text{*}}$ была решением вариационного неравенства

Теорема 2. Задача (3.2), в частности, (3.5) эквивалентна решению уравнения II рода

где $\gamma $ – произвольный положительный параметр, ${{P}_{Q}}$ – оператор метрического проектирования на множество $Q$. В частности, ввиду теоремы 1, задача минимизации (3.1) эквивалентна задаче (3.6) при $F(x) = \nabla \phi (x),$ а задача (3.4) эквивалентна (3.3) при $T(x) = x + A(x) - y$.

Таким образом, базовые постановки некорректно поставленных задач 1–4 можно рассматривать с единых позиций как задачу аппроксимации неподвижной точки нелинейного отображения, т.е. решения уравнения (3.3). Однако в приложениях выбор математической модели обычно диктуется типами входных данных, свойствами операторов и наличием для данной постановки сходящихся итерационных процессов.

4. СВОЙСТВА СИЛЬНО ФЕЙЕРОВСКИХ ОПЕРАТОРОВ

Во многих случаях задача допускает разбиение на подзадачи, для каждой из которых строится итерационный оператор, а затем с помощью некоторых операций сборки из имеющихся фрагментов конструируется оператор шага итерационного метода для решения задачи в целом. При этом удается построить разрешающий оператор из того же класса, что и порождающие его операторы, отвечающие за подзадачи. Возможность использования такого подхода для фейеровских операторов из класса $\mathcal{P}_{M}^{\nu }$ устанавливает следующая теорема (см. [7, теорема 1.8], [8]).

Теорема 3. Пусть операторы ${{T}_{i}}:H \to H,$ ${{T}_{i}} \in \mathcal{P}_{{{{M}_{i}}}}^{{{{\nu }_{i}}}}$ и $M = \bigcap\nolimits_{i = 1}^m \,{{M}_{i}} \ne \emptyset .$ Тогда верно следующее:

1) $T = {{T}_{m}}{{T}_{{m - 1}}}T...{{T}_{1}} \in \mathcal{P}_{M}^{\nu }$, $\nu = {{\min }_{{1 \leqslant i \leqslant m}}}\{ {{\nu }_{i}}\} {\text{/}}{{2}^{{m - 1}}}$,

2) $T = \sum\nolimits_{i = 1}^m \,{{\alpha }_{i}}{{T}_{i}} \in \mathcal{P}_{M}^{\nu }$, ${{\alpha }_{i}} > 0$, $\sum\nolimits_{i = 1}^m \,{{\alpha }_{i}} = 1$, $\nu = mi{{n}_{{1 \leqslant i \leqslant m}}}\{ {{\nu }_{i}}\} $.

Заметим, что порядок операторов в произведении из пункта 1 не имеет значение, т.е. соотношение справедливо для любой перестановки индексов.

Для аппроксимации неподвижных точек нелинейного оператора $T,$ т.е. решения уравнения

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

Введем обозначения “$ \rightharpoondown $” и “$ \to $” для слабой и сильной сходимости элементов гильбертова пространства. Сформулируем теорему сходимости для оператора шага $T$ из класса $\mathcal{P}_{M}^{\nu },$ которая была первоначально доказана для нерастягивающего оператора [10], а затем при более общих условиях [8].

Теорема 4. Пусть оператор $T:D(T) \subset H \to H$ из класса $\mathcal{P}_{M}^{\nu },$ удовлетворяет соотношению

Тогда при любом ${{x}^{0}}$ для итерационного процесса (4.2) справедливы следующие свойства:

1) ${{x}^{k}} \rightharpoondown \hat {x} \in {\text{Fix}}(T)$, т.е. сходится слабо к решению уравнения (4.1);

2) $\inf \{ {{\lim }_{{k \to \infty }}}{\text{||}}{{x}^{k}} - z{\text{||}}:z \in {\text{Fix}}(T)\} = {{\lim }_{{k \to \infty }}}{\text{||}}{{x}^{k}} - \hat {x}{\text{||}}$;

3) либо ${\text{||}}{{x}^{{k + 1}}} - \hat {x}{\text{||}} < {\text{||}}{{x}^{k}} - \hat {x}{\text{||}}$ для любого $k,$ либо ${{x}^{k}}$ стационарна, начиная с некоторого ${{k}_{0}} \geqslant 0,$ т.е. ${{x}^{{{{k}^{0}}}}} = {{x}^{{{{k}^{0}} + 1}}} = ... = \hat {x}$;

4) справедлива оценка

С учетом леммы 1 из теоремы 4 получаем

Следствие 1. Пусть в условиях теоремы вместо $T \in \mathcal{P}_{M}^{\nu }$ выполнено $T \in {{\mathcal{K}}_{M}}$. Тогда заключение теоремы справедливо для процесса

где $0 < \lambda < 1.$

Замечание 1. Если дополнительно в теореме 4 оператор $T$ является нерастягивающим (определение 5), тогда условие (4.3) выполнено. Таким образом, если множество $M = \bigcap\nolimits_{i = 1}^m \,{{M}_{i}} \ne \emptyset $ и известны операторы ${{T}_{i}} \in \mathcal{P}_{{{{M}_{i}}}}^{{{{\nu }_{i}}}},$ то, согласно теореме 3, для построения оператора $T \in \mathcal{P}_{M}^{\nu }$ достаточно положить

где ${{\alpha }_{i}} > 0$, $\sum\nolimits_{i = 1}^m \,{{\alpha }_{i}} = 1$. Объединяя этот факт с теоремой 4, получаем утверждение о сходимости МПП с оператором шага T из (4.4).

Теорема 5. Пусть $M = \bigcap\nolimits_{i = 1}^m \,{{M}_{i}} \ne \emptyset ,$ ${{T}_{i}} \in \mathcal{P}_{{{{M}_{i}}}}^{{{{\nu }_{i}}}}$ и для каждого выполнено условие (4.3). Тогда для МПП (4.2), где $T$ – любой из операторов (4.4), справедливо заключение теоремы 4.

Необходимо отметить, что, хотя сходимость итераций в теоремах 4, 5 только слабая, полученные результаты и развитые подходы можно применять при решении конечномерных задач, например, для систем линейных алгебраических уравнений (СЛАУ), в том числе, плохообусловленных

где матрица $A$ – произвольной структуры, а система, в общем случае, разрешима лишь в смысле наименьших квадратов. Во-первых, на примере СЛАУ легко продемонстрировать возможность разбиения на подзадачи (подсистемы), для каждой из которых строится фейеровский оператор, порождающий итерационный процесс, а затем из этих операторов генерируется фейеровский итерационный процесс для решения исходной СЛАУ (4.5) с помощью операций, указанных в теореме 3. В качестве подзадач здесь выступают подсистемы, на которые можно произвольным образом разрезать исходную СЛАУ. Во-вторых, покажем, как можно учитывать в алгоритме априорную информацию о решении СЛАУ с помощью фейеровских отображений.

Рассмотрим два итерационных метода решения СЛАУ – метод простой итерации и итерированный вариант метода Тихонова:

Предположим, что известна дополнительная априорная информация о решении СЛАУ (4.5) в форме систем выпуклых (в частности, линейных) неравенств Определим операторы где ${{f}_{i}}$ – слабо полунепрерывный снизу функционал с ограниченным градиентом $\nabla {{f}_{i}}$, и образуем с помощью операций умножения и выпуклой суммы операторы Оказывается, что каждый из операторов шага $T,$ определяемый процессами (4.6), (4.7), принадлежат классу $\mathcal{P}_{M}^{1},$ где $M$ – множество решений СЛАУ (4.5) в смысле наименьших квадратов, оператор ${{U}_{i}},$ определяемый формулой (4.9), принадлежит $\mathcal{P}_{{{{Q}_{i}}}}^{\nu },$ где $\nu = (2 - \lambda ){\text{/}}\lambda ,$ (см. [7], лемма 3.14), а множество ${{Q}_{i}}$ определяется $i$-м неравенством в системе (4.8). Следовательно, оператор $U,$ определяемый каждой из формул (4.10), принадлежит классу $\mathcal{P}_{Q}^{\nu }$ при соответствующем $\nu $ (см. теорему 3). Поэтому из теоремы 5 получаем

Следствие 2. Для любого ${{x}^{0}}$ последовательность ${{x}^{k}},$ генерируемая фейеровским процессом

где $U$ – любой из операторов (4.10), сходится к решению СЛАУ (4.5) в смысле наименьших квадратов, удовлетворяющему априорным ограничениям (4.8).

Замечание 2. Если априорное множество $Q$ задано системой линейных неравенств, то при возмущенных входных данных СЛАУ и системы неравенств итерационный метод порождает регуляризующий алгоритм (РА). В [7], [9] можно найти доказательство приведенных здесь фактов и примеры использования априорных ограничений при решении прикладных задач.

5. МОДИФИКАЦИЯ МПП НА ОСНОВЕ КОРРЕКТИРУЮЩИХ МНОЖИТЕЛЕЙ

Цель этого раздела – исследование модифицированного варианта МПП, с помощью которого удается получить сильную сходимость итераций для нерастягивающего оператора и его приложений к некорректно поставленным задачам. Следующие две теоремы, полученные в работе Ф. Браудера [11], касаются существования неподвижных точек нерастягивающего оператора и их устойчивости относительно параметра.

Теорема 6. Пусть $D$ – выпуклое замкнутое ограниченное множество гильбертова пространства $H$ и $T$ – нерастягиващий оператор (определение 5), действующий из $D$ в $D.$ Тогда множество неподвижных точек ${\text{Fix}}(T)$ не пусто, выпукло и замкнуто.

Рассмотрим уравнение

с оператором $T \in \mathcal{K}$ и $0 < \gamma < 1,$ где ${{v}^{0}}$ – некоторый элемент из $D.$

Теорема 7. Пусть $T:H \to H$ – нерастягивающий оператор (определение 5), отображающий выпуклое замкнутое ограниченное подмножество $D$ из $H$ в $D.$ Тогда для любого ${{v}^{0}} \in D$ и параметра $0 < \gamma < 1$ существует единственное решение ${{x}_{\gamma }} \in D$ уравнения (5.1) и $li{{m}_{{\gamma \to 1}}}{\text{||}}{{x}_{\gamma }} - \hat {x}{\text{||}} = 0,$ где $\hat {x}$ – ближайшая к ${{v}^{0}}$ неподвижная точка оператора $T.$

Б. Гальперин в своей статье [12] предложил модифицированный вариант МПП в форме

и, используя результаты работы [11], установил сильную сходимость итераций к некоторой точке из ${\text{Fix}}(T).$ Для формулировки теоремы сходимости нам понадобится определение допустимой последовательности ${{\gamma }_{i}}.$

Определение 6. Числовая последовательность ${{\gamma }_{i}}$ называется допустимой, если следующие условия выполняются:

1) $0 < {{\gamma }_{i}} < 1,\;i = 1,2,...;$

2) ${{\gamma }_{i}} < {{\gamma }_{{i + 1}}},$ $i = 1,2,...,$ $li{{m}_{{i \to \infty }}}{{\gamma }_{i}} = 1$ и справедливы соотношения:

3) существует последовательность номеров $n(i)$ такая, что $n(i + 1) > n(i)$ и справедливы соотношения:

4) $li{{m}_{{i \to \infty }}}{{\varepsilon }_{{i + n(i)}}}\varepsilon _{i}^{{ - 1}} = 1,$ где ${{\varepsilon }_{i}} = 1 - {{\gamma }_{i}};$

5) $li{{m}_{{i \to \infty }}}n(i){{\varepsilon }_{i}} = \infty .$

Теорема 8. Пусть выполнены условия теоремы 7. Тогда для любого начального приближения ${{x}^{0}} \in D$ и для любой допустимой последовательности ${{\gamma }_{k}}$ последовательность ${{x}^{k}}$, порождаемая процессом (5.2), сходится сильно к $\hat {x} \in {\text{Fix}}(T),$ ближайшей к ${{v}_{0}}.$

Замечание 3. Если в теореме 8 наряду с условием $T \in \mathcal{K}$ оператор принадлежит классу $\mathcal{P}_{M}^{\nu }$ (или даже ${{\mathcal{K}}_{M}}$), то в качестве множества $D$ можно взять шар $S(z;r)$ произвольного радиуса $r$ с центром в неподвижной точке $z,$ содержащий ${{v}_{0}}.$ Это означает, что сходимость итерационного метода (5.2) будет гарантирована для любой начальной точки ${{x}^{0}}.$

Замечание 4. Последовательность ${{\gamma }_{i}} = 1 - {{i}^{{ - p}}}$ при $0 < p < 1$ и $n(i) = {{i}^{\nu }},$ $0 < p < \nu < 1$ является допустимой в смысле определения 6. Как было отмечено в разд. 3, основные постановки некорректных задач могут быть сведены к нахождению неподвижной точки некоторого отображения на основе МПП (4.2) или его модифицированного аналога (5.2). Следовательно, в случае возмущенных данных задачи с уровнем погрешности $\delta $ необходимо формулировать правило останова итераций, которое бы гарантировало сильную сходимость ${{x}^{{k(\delta )}}} \to \hat {x} \in {\text{Fix}}(T).$

Исследуем регуляризующие свойства итерационного процесса (5.2). Рассмотрим наряду с (5.2) ее аналог с возмущенным оператором $\tilde {T}$

и с той же стартовой точкой ${{x}^{0}}.$ Введем параметр $\delta ,$ который характеризует ошибку входных данных задачи так, что выполнено одно из двух соотношений где $\phi (\delta ) \to 0$ при $\delta \to 0.$

Теорема 9. Пусть выполнены условия теоремы 8 и имеет место либо соотношение (5.4), либо (5.5), причем в последнем случае дополнительно предполагается, что $\tilde {T} \in \mathcal{K}$. Тогда при связи параметров $k(\delta )\phi (\delta ) \to 0$, $\delta \to 0$, последовательность ${{\tilde {x}}^{{k(\delta )}}},$ сформированная процессом (5.3), сходится к $\hat {x} \in {\text{Fix}}(T),$ ближайшей к ${{v}_{0}}.$

6. ПРИЛОЖЕНИЯ МПП С КОРРЕКТИРУЮЩИМИ МНОЖИТЕЛЯМИ

Обратимся к уравнению (4.5) и рассмотрим процессы (4.6), (4.7), где теперь вместо матрицы линейный ограниченный оператор $A,$ действующий на паре гильбертовых пространств, обратный оператор ${{A}^{{ - 1}}}$ которого в общем случае разрывный. Нетрудно проверить, что оператор шага в каждом из этих процессов является нерастягивающим, поэтому из теоремы 8 получаем

Следствие 3. Итерационный процесс (5.2), где $T$ – оператор шага любого из процессов (4.6), (4.7), сходится сильно к решению, в общем случае, в смысле наименьших квадратов, ближайшему к ${{v}_{0}}$.

Пусть вместо точной пары $(A,y)$ известны приближенные данные ${{A}_{\delta }},\;{{y}_{\delta }}$ такие, что ${\text{||}}A - {{A}_{\delta }}{\text{||}} \leqslant \delta $, ${\text{||}}y - {{y}_{\delta }}{\text{||}} \leqslant \delta $. Несложная проверка показывает, что в этом случае выполнены соотношения (5.4), (5.5) с функцией $\phi (\delta ) = c\delta ,$ где $c$ – некоторая константа, следовательно, из теоремы 9 имеем

Следствие 4. При связи параметров $k(\delta )\delta \to 0,$ $\delta \to 0$ последовательность ${{\tilde {x}}^{{k(\delta )}}},$ построенная процессом (5.3) с возмущенными данными ${{A}_{\delta }},\;{{y}_{\delta }}$ сходится к решению операторного уравнения (4.5), ближайшему к ${{v}_{0}}$. Аналогичное утверждение справедливо для процесса

где $U \in \mathcal{P}_{Q}^{\nu } \cap \mathcal{K},$ $M \cap Q \ne \emptyset $ при наличии априорной информации о решении операторного уравнения в виде $x \in Q.$

В качестве примера множества априорных ограничений для операторного уравнения рассмотрим систему линейных неравенств

и оператор, отвечающий за i-е неравенство

Справедлива следующая [7]

Лемма 2. Оператор ${{U}_{i}}$ принадлежит классу $\mathcal{P}_{{{{Q}_{i}}}}^{\nu } \cap K,$ т.е. является сильно фейеровским и нерастягивающим; здесь ${{Q}_{i}} = \{ x \in H\,:\;\;\left\langle {x,{{a}_{i}}} \right\rangle - {{q}_{i}} \leqslant 0\} ,$ $\nu = (2 - \lambda ){\text{/}}\lambda .$

Это означает, что в качестве оператора $U$ в процессе (6.1) можно принять оператор, образованный произведением или выпуклой суммой операторов ${{U}_{i}}$. Заметим, что при $\lambda = 1$ оператор ${{U}_{i}}$ совпадает с метрической проекцией на гиперплоскость ${{l}_{i}}(x) = 0.$

В приложениях часто используется априорная информация о неотрицательности, монотонности или выпуклости решения в разных сочетаниях. Вместе с ограниченностью эти свойства порождают компактные множества, например, в ${{L}_{p}}.$ После дискретной аппроксимации априорные ограничения принимают вид выпуклых многогранников. В монографии [13] разработаны специальные методы, алгоритмы и программные средства построения регуляризованного семейства приближенных решений для линейных некорректных задач с учетом априорных ограничений такого типа.

Рассмотрим сначала частный случай задачи (3.1), когда целевой функционал – квадратичный

где $A$ – линейный ограниченный оператор, действующий на паре гильбертовых пространств ${{H}_{1}},\;{{H}_{2}}$, а $Q$ – выпуклое замкнутое необязательно компактное подмножество из ${{H}_{1}}.$ Поскольку компактность множества не предполагается и допускается неограниченность обратного оператора ${{A}^{{ - 1}}},$ то задача некорректна по Тихонову. Предполагается, что задача (6.4) имеет непустое множество решений $M$. Согласно теоремам 1, 2 задача (6.4) эквивалентна решению операторного уравнения где ${{P}_{Q}}$ – оператор метрического проектирования. Сформируем МПП с оператором шага $T$который называют обычно методом проекций градиента. При принятых условиях нельзя гарантировать сходимость итераций к решению задачи, однако его модификация с помощью корректирующих множителей позволяет решить эту проблему, поскольку оператор шага обладает свойством фейеровости и принадлежит классу $\mathcal{K}$ нерастягивающих операторов [14] (см. также лемму 2.14 из [10]).

Лемма 3. При $0 < \beta < 2{\text{||}}A{\text{|}}{{{\text{|}}}^{{ - 1}}}$ оператор шага $T$ итерационного метода (6.5) принадлежит классу $\mathcal{P}_{{{{Q}_{i}}}}^{\nu } \cap K,$ где параметр $\nu = (1{\text{/}}\beta {\text{||}}A{\text{|}}{{{\text{|}}}^{2}} - 1{\text{/}}2)$.

Из теоремы 8, леммы 3 и замечания 3 выводим

Следствие 5. Если последовательность ${{\gamma }_{k}}$ является допустимой, то для любого начального приближения ${{x}^{0}}$ процесс

сходится к решению $\hat {x}$ задачи (6.4), ближайшему к ${{{v}}_{0}}.$

Замечание 5. Если пара $(A,y)$ задана своим $\delta $-приближением $({{A}_{\delta }},{{y}_{\delta }}),$ то для процесса (6.6) справедливо заключение следствия 4 о сходимости итераций к решению $\hat {x}$ при выборе числа итераций $k(\delta )$ таким образом, чтобы $k(\delta )\delta \to 0$ при $\delta \to 0.$

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

где $F(x) = \nabla \phi (x)$, $Q$ – выпуклое замкнутое ограниченное подмножество из $H$, ${{P}_{Q}}$ – оператор метрического проектирования. Справедливо следующее утверждение (см. [15, лемма 4.1]).

Лемма 4. Если ${\text{||}}F{\kern 1pt} {\text{'}}(x){\text{||}} \leqslant N,$ $x \in Q,$ то при $0 < \gamma \leqslant 2{\text{/}}N$ оператор $T,$ определяемый формулой (6.7), является нерастягивающим.

Из теоремы 8 и леммы 4 получаем

Следствие 6. Пусть выполнены условия леммы 4 и задача (3.1) имеет непустое множество решений. Тогда для любого ${{v}_{0}}$ и для любой допустимой последовательности ${{\gamma }_{k}}$ процесс

сильно сходится к решению задачи (3.1), ближайшему к ${{v}_{0}}$.

Заметим, что при ${{\gamma }_{k}} = \tfrac{1}{{1 + {{{(1 + k)}}^{p}}}},$ $0 < p < 1,$ ${{v}_{0}} = 0$ утверждение о сильной сходимости (6.8) содержится в работе [14] (см. теорему 4.1).

Установим регуляризующие свойства построенного итерационного процесса.

Теорема 10. Пусть целевой функционал $\phi $ в задаче (3.1) задан приближенно функционалом ${{\phi }_{\delta }}$ и выполнены условия аппроксимации

Пусть последовательность $\{ {{\tilde {x}}^{{k(\delta )}}}\} $ построена процессом (6.8), в котором функционал $\phi $ заменен на ${{\phi }_{\delta }}.$ Тогда при выборе числа итераций $k(\delta ),$ удовлетворяющему соотношению $k(\delta )\delta \to 0$ при $\delta \to 0$, последовательность $\{ {{\tilde {x}}^{{k(\delta )}}}\} $ сходится к решению $\hat {x}$ задачи (3.1), ближайшему к ${{v}_{0}}$.

Действительно, по теореме 9 для сходимости итераций в условиях возмущенных данных достаточно проверить для оператора $T(x) = {{P}_{Q}}(x - \gamma F(x))$ выполнение условия (5.4), которое в нашем случае, с учетом (6.9), принимает вид

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

Определение 7. Отображение $S_{Q}^{\phi }\,:\;\;H \to Q \subset H,$ определяемое соотношением

введенное Дж. Моро [16], называется prox-отображением, а итерационный процесс называется prox-методом; здесь $Q$ – выпуклое замкнутое подмножество гильбертова пространства $H.$

Теорема 11. Prox-отображение $S_{Q}^{\phi }$ принадлежит классу $\mathcal{P}_{M}^{1} \cap \mathcal{K},$ т.е. является сильно M-фейеровским и нерастягивающим оператором, где $M$ – множество решений задачи (3.1).

Теорема 8 вместе с теоремой 11 влекут (см. [9, лемма 2.7])

Следствие 7. Пусть задача (3.1) разрешима и $\hat {x}$ – ее решение, ближайшее к ${{v}_{0}}.$ Тогда для ${{x}^{0}} \in Q$ и допустимой последовательности ${{\gamma }_{k}}$ процесс

сходится сильно к $\hat {x}.$

Необходимо отметить, что при реализации процесса (6.10) требуется вычислять $w = S_{Q}^{\phi }(v)$ в каждой итерационной точке $v = {{x}^{k}},$ где prox-отображение задано неявно и элемент $w$ находится как решение задачи на минимум для равномерно выпуклого функционала. Это означает, что для приближенного вычисления $w = S_{Q}^{\phi }(v)$ можно привлечь МПП со сжимающим оператором. Действительно, согласно теоремам 1, 2 вычисление $w$ сводится к нахождению неподвижной точки оператора $T = {{P}_{Q}}(x - \gamma F(x)),$ т.е. к решению уравнения

где $F(x) = \nabla \phi (x) + (x - v).$

Лемма 5. Пусть ${\text{||}}F(x) - F(u){\text{||}} \leqslant C{\text{||}}x - u{\text{||}},$ тогда при $\gamma < 2{\text{/}}{{C}^{2}},$ ${\text{||}}T(x) - T(u){\text{||}} < {\text{||}}x - v{\text{||}},$ а при $\gamma = 1{\text{/}}{{C}^{2}},$ $C > 1$, справедлива оценка

Таким образом, для приближенного вычисления $S_{Q}^{\phi }({{x}^{k}})$ в процессе (6.10) можно применить МПП со сжимающим оператором $T$. Если структура множества допускает экономичный алгоритм вычисления метрической проекции ${{P}_{Q}},$ то в целом процесс (6.10) может оказаться вполне эффективным.

7. ДВУХЭТАПНЫЕ МЕТОДЫ РЕШЕНИЯ НЕЛИНЕЙНЫХ УРАВНЕНИЙ С МОНОТОННЫМ ОПЕРАТОРОМ

Регуляризованное семейство приближенных решений для вариационного неравенства (3.2) может быть сформировано на основе принципа итеративной регуляризации А.Б. Бакушинского с помощью итерационной схемы [15]

где $F(x)$ – монотонный оператор, $G$ – равномерно (сильно) монотонный оператор, ${{P}_{Q}}$ – оператор метрического проектирования, ${{\gamma }_{k}},\;{{\varepsilon }_{k}}$ – последовательности положительных параметров. Таким образом, идея итеративной регуляризации основана на предварительной регуляризации (первый этап) исходной задачи (в данном случае вариационного неравенства) и на втором этапе на применении к ней той или иной итерационной схемы (в данном случае МПП).

Теорема 12. Пусть $F(x) = A(x) - y,$ $A$ – монотонный оператор, для которого $\sup \{ {\text{||}}A{\text{'}}(x){\text{||}}{\kern 1pt} :\;x \in Q\} \leqslant C,$ $y$ задан приближенно элементом ${{y}_{\delta }},$ ${\text{||}}y - {{y}_{\delta }}{\text{||}} \leqslant \delta .$ Пусть параметры ${{\gamma }_{k}},{{\varepsilon }_{k}}$ выбраны в соответствии с соотношениями

Если число итераций $k(\delta )$ выбрано так, что выполнены соотношения $li{{m}_{{\delta \to 0}}}k(\delta ) = \infty ,$ $li{{m}_{{\delta \to 0}}}\delta {\text{/}}{{\varepsilon }_{{k(\delta )}}} = 0,$ тогде $x_{\delta }^{k}$ определяется процессом (7.1), в котором $y$ заменен на ${{y}_{\delta }},$ а $\hat {x}$ – решение вариационного неравенства $\left\langle {G(x),x - v} \right\rangle \leqslant 0$ $\forall v \in M,$ M – множество решений вариационного неравенства (3.2).

Выше уже исследовалась некорректная задача с монотонным оператором в форме вариационного неравенства и итеративно регуляризованный метод последовательных приближений, который порождает регуляризованное семейство приближенных решений. Ниже рассмотрим некорректную задачу в форме операторного уравнения (3.4), где $A:H \to H,$ – монотонный оператор с разрывным обратным ${{A}^{{ - 1}}},$ правая часть задана приближенно ${{y}_{\delta }},{\text{||}}y - {{y}_{\delta }}{\text{||}} \leqslant \delta .$ Для построения устойчивого приближенного решения на первом этапе к операторному уравнению применяется схема Лаврентьева

а на втором для аппроксимации регуляризованного решения ${{x}_{\alpha }}$ используются $\kappa {\text{ - }}$процессы где $\beta > 0,$ $ - 1 \leqslant \kappa < \infty $. Класс итерационных методов (7.3) как для корректно, так и некорректно поставленной задачи (3.4) в случае нелинейных уравнений ранее не исследовались. Эти методы, по-видимому, впервые были анонсированы автором в работе [17]. Для линейного оператора $A$ итерационные схемы вида (7.3) (естественно, при замене оператора $A{\text{'}}$ на $A$) и при $\beta = 1,$ исследовались в книге [15], где при некотором выборе ${{\alpha }_{{k(\delta )}}}$ доказана сходимость итераций к нормальному решению уравнения (3.4). Очевидно, что для положительно-oпределенного оператора $A$ при $\alpha = 0,$ $\beta = 1,$ $\kappa = \alpha $ схемы сводятся к классическим $\alpha $-процессам, изложенным в монографии [18]. Обычно в линейном случае вместо $\kappa $ используется параметр $\alpha ,$ что дало основание назвать схемы $\alpha $-процессами. Но поскольку в нашем нелинейном регуляризованном случае через $\alpha $ обозначен параметр регуляризации, было принято использовать в схемах (7.3) вместо привычного $\alpha $ параметр $\kappa $ и назвать их $\kappa $-процессами.

Теорема 13. Пусть $A$ – монотонный оператор, $A{\text{'}}({{x}^{0}})$ – самосопряженный (неотрицательно определенный) оператор и выполнены условия

где ${{S}_{{{{r}_{0}}}}}({{u}^{0}})$ содержит ${{x}_{\alpha }}.$ Тогда для любого начального приближения ${{x}^{0}} \in {{S}_{{{{r}_{0}}}}}({{u}^{0}})$ припоследовательность $\{ {{x}^{k}}\} ,$ порождаемая процессом (7.3), сходится к решению ${{x}_{\alpha }}$ уравнения (7.2), а присправедлива оценка

Для получения оценки погрешности двухэтапного метода зададим класс корректности (равномерной регуляризации) в форме истокообразной представимости решения

Введем переобозначение для решения регуляризованного уравнения (7.2), теперь $x_{\alpha }^{\delta }$ обозначаем решение с приближенной правой частью ${{y}_{\delta }},$ а ${{x}_{\alpha }}$ в случае точно заданной $y.$ Согласно результату из работы [19] для регуляризованного решения справедливы оценки из которой при $\alpha = \sqrt {\delta {\text{/}}{{k}_{0}}} $ имеем Объединяя (7.5) с оценкой для $\kappa $-процесса (7.4) и выбирая число итераций по формуле получаем окончательную оценку для двухэтапного метода которая является оптимальной по порядку $\delta $ (см. подробности в [20], [21]).

Рассмотрим двухэтапный метод решения нелинейного уравнения (3.4) с монотонным непрерывно дифференцируемым оператором $A:H \to H,$ для которого выполнены условия

в шаре ${{S}_{{{{r}_{0}}}}}({{u}^{0}}),$ содержащем ${{v}_{0}}$ – нормальное решение уравнения (3.4) и решение ${{x}_{\alpha }}$ уравнения (7.2). Как и в предыдущем пункте, применяется схема регуляризации Лаврентьева, а на втором для аппроксимации ${{x}_{\alpha }}$ регуляризованный модифицированный метод Ньютона [20]

Теорема 14. Пусть производная $A{\text{'}}({{x}^{0}})$ является самосопряженным (неотрицательно определенным) оператором и выполнены условия (7.7). Пусть параметры $\alpha ,\bar {\alpha }$ и начальное приближение ${{x}^{0}}$ удовлетворяют соотношениям:

Тогда при $\beta < \alpha \bar {\alpha }{\text{/}}{{(\alpha + {{N}_{1}})}^{2}}$ процесс (7.8) сходится к ${{x}_{\alpha }}$ и оператор шага $T$ является сильно $\{ {{x}_{\alpha }}\} $-фейеровским, а при $\beta = \alpha \bar {\alpha }{\text{/}}2{{(\alpha + {{N}_{1}})}^{2}}$ справедлива оценка погрешностигде ${{x}_{\alpha }}$ – единственное решение уравнения (7.2).

Из изложенного в теореме 13 следует, что на том же классе корректности истокообразно представимых решений и при условиях теоремы 14 для двухэтапного метода Ньютона–Лаврентьева (7.2), (7.8) также справедлива оптимальная по порядку оценка (7.6) с той лишь разницей, что теперь параметр $q$ определяется формулой (7.9).

Замечание 6. Ввиду известного факта, что градиент выпуклого функционала является монотонным оператором (см. [22, лемма 4.10, § 4, гл. III]) $\kappa $-процессы и регуляризованный метод Ньютона могут применяться при аппроксимации регуляризованного решения с выпуклым функционалом Тихонова

в частности, для квадратичного функционала $\phi (x) = {\text{||}}Ax - y{\text{|}}{{{\text{|}}}^{2}}$ и стабилизатора $\Omega (x) = \int_D \,\sqrt {{\text{|}}\nabla x(s){{{\text{|}}}^{2}} + \beta } ds.$