Содержание к диссертации
Введение
ГЛАВА I. Устойчивые итерационные методы для аппроксимации решений нерегулярных нелинейных уравнений 15
1. Об основных подходах к построению итерационных методов аппроксимации решений нерегулярных нелинейных уравнений с гладкими операторами 15
2. Класс устойчивых итерационных методов решения нелинейных некорректных операторных уравнений 25
3, Примеры построения итерационных процессов 32
4. Устойчивый метод градиентного типа для аппроксимации решений нерегулярных нелинейных уравнений 35
5. Построение итерационных методов решения.ннений с пониженными требованиями к гладкости оператора 42
6. Анализ условий основных теорем 48
7. О применении алгоритмов построения устойчивых итерационных методов к нелинейным интегральным уравнениям 51
8. Обсуждение результатов главы 1 55
ГЛАВА II. Устойчивые итерационные методы для нахождения квазирешений нерегулярных нелинейных уравнений 58
1. Класс устойчивых итерационных методов для отыскания квазирешений нерегулярных нелинейных уравнений 58
2. Градиентно-проекционный метод для нахождения квазирешений нерегулярных нелинейных уравнений на выпуклом замкнутом множестве 67
3. Вариант град иентно-проекцион ного метода для нахождения квазирешений нерегулярных нелинейных уравнений 77
4. Обсуждение результатов главы II 79
ГЛАВА III. Приложение устойчивых итерационных методов к обратным задачам гравиметрии и акустики 81
1. Обратные задачи гравиметрии 81
2. Применение устойчивых итерационных процессов к задачам гравиметрии 83
3. Численные эксперименты с обратными задачами гравиметрии 93
4. Постановка обратной задачи акустического рассеяния 99
5. Применение устойчивых итерационных методов в обратной задаче акустического рассеяния 101
6. Численные эксперименты с обратной задачей акустики 104
заключение 108
приложение 109
- Класс устойчивых итерационных методов решения нелинейных некорректных операторных уравнений
- Построение итерационных методов решения.ннений с пониженными требованиями к гладкости оператора
- Градиентно-проекционный метод для нахождения квазирешений нерегулярных нелинейных уравнений на выпуклом замкнутом множестве
- Численные эксперименты с обратными задачами гравиметрии
Введение к работе
В последние десятилетия активно развивается направление вычислительной математики, посвященное построению приближенных методов решения нерегулярных операторных уравнений в гильбертовых и банаховых пространствах. Интерес к изучению таких уравнений в бесконечномерных пространствах возник в связи с бурным развитием теории и практики обратных задач математической физики и определяется тем обстоятельством, что подобные задачи в большинстве случаев моделируются именно нерегулярными операторными уравнениями. Достаточно полный обзор современного состояния теории нелинейных обратных задач и методов их решения содержится в монографиях [1, 2, 16, 27-29, 47, 51, 52, 65, 67, 78, 81, S3]. Поскольку источником исходных данных в этих задачах на практике обычно служат измерения и эксперименты, операторы получаемых уравнений как правило бывают известны с той или иной погрешностью.
Объектом изучения в работе являются нелинейные операторные уравнения вида F(x)=0, x.Hl7 (1) где F: #1 —^ #2 - дифференцируемый по Фреше оператор, Я1( #2 ~ гильбертовы пространства. В тех случаях, когда разрешимость уравнения (1) не гарантируется, естественным обобщением (1) является задача отыскания квазирешения уравнения (1) на множестве Q, т. е. точки х* Є Q, являющейся решением задачи тшф), ^)-І||^)і|2. (2)
Квазирешения х* Є Q, для которых выполняется равенство F{x*) = О, совпадают с решениями уравнения (1). Здесь и далее в работе через \\х\\ обозначается норма элемента х Є X в пространстве X, вид которого обычно ясен из контекста.
В теории численных методов решения нелинейных уравнений задача (1) и соответствующая ей экстремальная задача (2) называются регулярными, если линеаризация оператора F(x) в окрестности решения (квазирешения) х* хорошо приближает F(x) в близких к х* точках [11, с. 16]. Всюду в работе регулярность (нерегулярность) задач (1), (2) и соответствующего оператора F(x) будем понимать в смысле следующего определения, конкретизирующего вышеприведенное условие.
Определение 1. Задана (1) (задача (2)) называется регулярной в окрест ности решения (квазирещения) ж*, если для всех точек х из окрестности х* оператор F'(x): Ні —> Ні имеет непрерывный обратный, определенный на всем пространстве Н<і, либо оператор F'*(x)F'(x): Hi -4- Н\ имеет непрерывный обратныщ определенный на всем пространстве Н\. В противном случае задача (1) (задача (2)) называется нерегулярной.
Пусть ставится задача приближенного решения уравнения (1). Аппроксимируя в окрестности точки о Н\ регулярное отображение F: Hi —У Hi в (1) его линейным приближением, приходим к уравнению F'(xq)(x-xo) + F(x0) = 0, -хе Ні. (3)
В тех случаях, когда уравнение (3) не имеет решения, может оказаться разрешимой задача mm~\\Ff(xQ)(x-xQ) + F(x0)\\2. (4)
Задача (4) эквивалентна уравнению Ґ*(х<і)У(хо)(х - хо) + F*(x0)F(x0) = 0, хе Нъ (5)
Для решения уравнений (3), (5) в случае непрерывно обратимых операторов F'(xq), F'*(xo)F'(xo) может быть использован широкий спектр численных методов решения регулярных (кппр.рктных) линейных операторных ураявшій (см., например, [48]). В случае нерегулярного отображения F(x) линейной аппроксимации (3) или (4) уже недостаточно для адекватного описания локальной структуры оператора F(x) в окрестности рассматриваемой точки xq. При этом задача отыскания решения (квазирешения) нерегулярного уравнения (1) оказывается как правило некорректно поставленной [11, с. 16; 20]. Поэтому построение эффективных методов решения указанных уравнений требует привлечения методов теории регуляризации некорректных задач. Кратко напомним основные понятия этой теории.
Пусть зафиксировано метрическое пространство (F, р), которому принадлежит точный оператор F(x) и все допускаемые к рассмотрению его аппроксимации.
Определение 2 ([73, 75]). Задача (1) (задача (2)) поставлена корректно по Лдамару в паре пространств {Hi^H^}, если выполняются следующие условия: задача (1) (задача (2)) имеет единственное решение; это решение непрерывно (в смысле метрики р на F и нормы пространства Hi) зависит от оператора F(x) при его вариациях в пределах пространства F.
Если нарушается хотя бы одно из условий 1), 2), то задача (1) (задача (2)) называется некорректно поставленной. '_,
Согласно определению 2, малые погрешности в задании оператора F(x), определяющего корректную задачу (1), мало влияют на решение (1) и в этом смысле с вычислительной точки зрения неопасны. Напротив, некорректно поставленные задачи чувствительны к погрешностям в исходных данных, так как малые вариации оператора F(x) могут привести к значительным изменениям решения или даже превратить исходное уравнение (1) в несовместное. Задача о нахождении квазирешения на множестве Q как вариационная задача также может оказаться некорректно поставленной. В частности, существование квазирешения на Q гарантировано в общем случае лишь при наличии у функционала ф(х) свойств типа коэрцитивности и слабой полунепрерывности снизу, а также для компактного множества Q. Центральным понятием теории некорректных задач является понятие регу-ляризующего алгоритма. Следуя [73, 75], приведем соответствующее определение в необходимой нам фирме. Пусть X* - множество решений (кьааи-решений) уравнения (1). Считаем, что вместо точного оператора Fix) в (1) известно его приближение F є F, p(F, F) < 5, где величина S > 0 характеризует погрешность аппроксимации F(x) и предполагается заданной.
Определение 3. Регуляризующим алгоритмом для задачи (1) (задачи (2)) называется оператор R: FxfO, сю) —V Н\, ставящий в соответствие паре (F,S) Є F х [0,оо) элемент Ял(ІГ)... _._#i таким образом^ v,wо для некоторого элемента х* X*, х* = x*{F), выполняется равенство Urn sup |[ifc(j?)-*'||=0. (6) d~*VFeF;p{FtF)<6
Из (6) следует, что элемент х$ = Rs(F) может быть выбран в качестве приближенного решения задачи (1), соответствующего приближенному one-ратору F(x) и уровню погрешности 5.
Впервые понятие регуляризующего алгоритма было сформулировано А. Н. Тихоновым в [71, 72], после чего теория приближенного решения некорректных задач оформилась как самостоятельная ветвь вычислительной математики. Современное состояние теории и методов решения некорректных задач подробно освещено в монографиях и статьях [10, 11, 19, 20, 22, 25, 31, 32, 51-53, 56-58, 68, 69, 73-75, 78, 83].
Проблема практического построения регуляризуадщих алгоритмов для того или иного класса некорректных уравнений имеет непосредственный прикладной интерес. Значительное место среди разрабатываемых численных методов решения уравнений (1) занимают регуляризирующие алгоритмы, построенные на базе итерационных процедур. Повышенный интерес к итерационным методам объясняется простотой алгоритмической и про- граммной реализации этих методов, а также свойством устойчивости к погрешностям вычислений, характерным для многих итерационных процессов. Существуют различные пути использования итерационных конструкций при решении некорректных задач. Краткий обзор известных подходов к построению итерационных методов решения нерегулярных нелинейных уравнений (1) приведен ниже (гл. I, 1).
В настоящее время наиболее завершенной можно считать теорию итерационных методов решения нерегулярных нелинейных уравнений с монотонными операторами. В ее основе лежит развитый в [10, 20] принцип итеративной регуляризации, позволяющий единообразно модифицировать классические итерационные методы решения нелинейных уравнений (градиентный метод, метод Ньютона и т. п.), делая их пригодными для решения и исследования нерегулярных уравнений (см. также [43]). В случае аффинных операторов F(x) — Ал, — /, где А: Н\ —> Нч - линейный непрерьшмый оператор, регуляризационные свойства градиентных методов вариационного типа и методов сопряженных градиентов подробно изучались в [25, 59, 60]. Для гладкого нелинейного оператора F(x) такое исследование удается провести лишь при наложении жестких структурных условий на характер нелинейности оператора в окрестности решения [83, 92, 95, 97-99], Упомянутые условия допускают эффективную проверку только в небольшом числе примеров, выполнение же их для сколь-нибудь широких классов реальных обратных задач является проблематичным (ем, [23, 90]). В основе изучаемых в [33] итерационных методов решения уравнения (1) лежит понятие 2-регулярности оператора F(x), обобщающее классическое определение регулярного оператора. Следует отметить, что свойство 2-регулярности не выполняется в случае интегрального вполне непрерывного отображения F(x), когда производная F'(x) оказывается вполне непрерывным линейным оператором.
Итеративные регуляризующие алгоритмы, пригодные для уравнений (1) с операторами, имеющими вполне непрерывную производную F'(x), строились и изучались в [3-6; 11, гл. 3, 4; 14; 45; 77; 79; 80]. В этих работах в качестве элемента R&(F) (см. определение 3) берется результат N(6) шагов соответствующего итерационного процесса {хп} — {x„(F)}, сходящегося к решению х* в случае точных данных F = F. При этом число итераций N(6) выбирается в зависимости от уровня погрешности 6 так, чтобы было limiV() = оо, а оператор Rs{F) = xN^(F) удовлетворял условию (6), За- метим, что при этом сама последовательность {xn(F)} (п —> оо) в случае F ^ F как правило расходится. Эффективная практическая реализация таких методов часто бывает затруднена тем обстоятельством, что крите- рий останова N{5) определяется с точностью до произвольной постоянной и зависит от неизвестных характеристик задачи.
Альтернативный подход к построению устойчивых итерационных методов, не требующих сопровождения в виде процедуры останова, намечен в [7; 8; И, гл. 5]. В этих работах изучались модификации стандартного градиентного процесса Xn+i = хп- jF'*(xn)F(xn), 7 > 0, (?) которые можно применять для решения нерегулярных уравнений без каких-либо дополнительных структурных условий на оператор F(x). Устойчивость итерационных процессов здесь и всюду далее понимается в том смысле, что вырабатываемые ими приближения {хп} — {xn(F)} обладают свойством ЇІ^ІІ-г. _ т*|| < П($+ А) ^ где величина Д определяется параметрами рассматриваемого процесса и при удачном выборе этих параметров может быть сделана сколь угодно малой. Свойство (8) существенно отличает данные процессы от методов итеративной регуляризации из [3-6, 11, 45], которые в применении к задачам с приближёнными данными вырабатывают расходящиеся при п —> со последовательности {xn(F)}. Из (8) следует, что для устойчивых методов нет - необходимости в построении критерия-останова. Качество получаемых приближений {хп} определяется лишь имеющимися вычислительными ресурсами и величинами 6, Д. В настоящее время для уравнений с операторами F(x) общего вида известно лишь несколько отдельных процессов типа (7), обладающих свойством (8) ([11, гл. 5]) и отсутствует сколь-нибудь общая теория построения и исследования таких процессов.
В основу конструкции устойчивых итерационных процессов решения (1) может быть положен подход, используемый в классическом методе Ритца (см., например, [18, 55]). В рамках этого подхода для аппроксимации решения уравнения (1) задается полная линейно независимая система векторов {en}Li С Hi, Затем строится последовательность конечномерных подпространств {М^}, где М^ - n-мерное пространство, натянутое на векторы єі, Є2,..., е„, и при помощи тех или иных (например, итерационных) методов решается последовательность задач ттф(х), ф(х) = ±\\Р(х)\\\ (9)
В случае, если функционал ф{х)} х Є Ні, является сильно выпуклым, задача (9) оказывается разрешимой при любом п и приближения Ритца х^п* Є М'"': ф(х^п>) = min ф(х) при п ~> оо сильно сходятся к единственной точке аб- солютного минимума ф(х) на Яі ([18, с. 177]). В отсутствии свойств оператора F{x), гарантирующих сильную выпуклость функционала ф(х) на Н\, вопрос о существовании и сходимости приближений Ритца остается открытым. Следует отметить, что для уравнений (1), моделирующих прикладные нелинейные обратные задачи, свойство выпуклости и тем более сильной выпуклости ф(х) на всем пространстве Н\ как правило не может быть гарантировано. Это обстоятельство делает актуальным проблему разработки модификаций метода Ритца, пригодных для устойчивого отыскания решений уравнений (1) с произвольными гладкими операторами F(x).
В диссертации для аппроксимации решения х* уравнения (1) с произвольным приближенно заданным гладким оператором F(x) применяется вариант метода Ритца с использованием вместо М^ фиксированного аффинного подпространства М$ = {х'Е Н\: х = у + ,у М}, Є #і- Таким образом, вместо (9) рассматривается задача
Й0. Й*) = 5ІІ^И3-"" (10)
Цель диссертации заключается в разработке и исследовании новых методов решения уравнения {If, основанных нагприменешш: к" аппроксимируй-ющей задаче (10) различных итерационных процессов минимизации с апро-1 бацией полученных методов на избранных обратных задачах гравиметрии и акустики.
Пусть оператор F{x) дифференцируем по Фреше, причем производная F'{x) удовлетворяет условию Липшица в некоторой окрестности точки х*. Основным элементом исследования аппроксимационных свойств решения задачи (10) по отношению к искомому решению х* уравнения (1) является введение условия на подпространство М, гарантирующего при подходящем выборе локальную сильную выпуклость функционала ф(х) на М% в шаре фиксированного радиуса. Это условие имеет вид: Ker(F'{x*))nM = {0}. (11)
Здесь Ker{F{x*)) - {у Є Hi: F\x*)y - 0} - ядро оператора F'{x*). В работе используются также и некоторые модификации условия (11). Пред-положим, что ||(/-Рл,)(**-Ш<Д, где Рм - оператор ортогонального проектирования из Н\ на подпространство М,1 - единичный оператор. Величина Д имеет смысл погрешности аппроксимации искомого решения х* подпространством М$. При выполнении ! 10 (11, достаточной малости погрешности 6 задания F(x) и малости величины Д устанавливается, что для решения задачи (10) могут успешно использоваться различные методы конечномерной минимизации, вырабатывающие релаксационные последовательности {хп} такие, что x„Aff,' ф{хп+1)<ф(хп), Ъж\\ф'(хп)\\=0. (12)
Именно, доказывается, что при выборе начального приближения хо М$ из окрестности $}г(Рм({х*)) П М фиксированного радиуса г > 0, приближения хп стабилизируются в окрестности решения х* с радиусом, пропорциональным 5 и Д, так что lim ||хп -х*\\ = \\х-х*\\ <С0(5 + А).
П-+00
Здесь Qr(x) = {і/ є Яі: \\у — rcjj < г}, х - точка локального минимума сильно выпуклого функционала ф(х) на указанной окрестности, постоянные r = r(F, М), Со = Cq(F7 М) не зависят от 8, Д, а определяются лишь данными задачи (1) и выбором подпространства М. Тем самым методы, получаемые в рамках рассматриваемой общей схемы, обладают свойством устойчивости к погрешностям rf> Д. Поэтому для таких процессов проблема "построения критерия останова итераций"естественным образом снимается. Устанавливаются достаточные условия, позволяющие гарантировать выполнение основного предположения (11) и его модификаций. Пусть, например, что оператор F'(x) является инъективным при х D С Н\. Это условие выполняется, в частности, для уравнений (1), моделирующих некоторые обратные задачи акустического рассеяния ([81, с. 129; 89]). В применении к этим задачам включение х Є D имеет смысл условия повышенный гладкости элемента х, совмещенного с требованием малости отклонения функции х(-) от постоянной. В подобных случаях условие (11) автоматически выполняется для любого подпространства М, если я* D. Условие (11) выполняется также в случае, если для некоторой точки х Є Н\, достаточно близкой к х*, выполняется tfer(F'(x))nitf = {0}. (13)
Вариация точки ж в (13) доставляет дополнительные возможности подбора подпространства М.
При построении методов решения уравнений (1) с операторами F(x), производная которых не удовлетворяет условию Липшица в открытой окрестности х*, рассматривается вариационная задача mWx); (р(х) == -||Ф(я)||2, х Є М, (14) где Ф(х) — F(x + — Рм)і х М. Дифференцируемость оператора Ф(х) = F(x + — Рм) в открытой окрестности х* здесь не предполагается. Будем считать, что выполняется включение М$ С D(F) П D(F) и операторы Ф(ж),Ф(х): -М -ч Яг обладают производными Фреше, которые удовлетворяют условию Липшица на М в шаре с центром в точке Рм%*- Основное условие на выбор подпространства М С Н\ и параметра Є if і, гарантирующее сильную выпуклость функционала <р(х), х М в шаре фиксированного радиуса в М} в этом случае имеет вид
Кег(Ф'(Рмх*)) = {0}. (15)
Если величины 6, А, ||Ф(Рд/г:*)|| достаточно малы, то для нахождения минимума в задаче (14) применимы различные методы конечномерной минимизации, вырабатывающие последовательности {хп} со свойством (12). При выборе начального приближения xq є М из малой окрестности Рм%*> для точек zn = хп + — Рм, аппроксимирующих х*, справедливо предельное соотношение lim'||*,-*ЇІ < 'сі(І + Д + ||Ф№*ОЦ).
В этом случае постоянная Ci = C\{F, М, ) в отличие от Co(F\M) зависит от обеих компонент пары (М, ). Обсуждаются модификации условия (15), позволяющие упростить выбор элементов этой пары. -
В качестве одной из модификаций схемы (7) изучается метод градиентного типа «о Є Hi, xn+i ~хп-ц {F'*(xn) F(xn) + a(xn - )). (16)
Здесь fi > 0 - шаговый множитель, a > 0 - параметр регуляризации, Є Яі -управляющий параметр, играющий роль начальной оценки х*. Ключевую роль в исследовании асимптотических свойств процесса (16) играет следующее условие приближенной истокопредставимости начальной невязки я* — : х* - = F'*(x*)v + w, ггЄ#2і we Hi, \\w\\ < Дь
При выборе начального приближения 2 согласно условию ||^о~ ж*|| ^ г\/<*> г — t*(F) и достаточно малых величинах а, ц, \\v\\, Ді устанавливается стабилизация итераций (16) в малой окрестности решения в соответствии с неравенством lim||a:n-x+||2
П-+0О
Здесь постоянная Сг = СгС^А*) не зависит от а, 6, Д, Ді. Последнее соотношение устанавливается без дополнительных структурных условий на оператор F{x). Вышеописанные результаты составляют основное содержание главы I.
Обоснование общей схемы построения итерационных методов для нахождения квазирешений уравнения 1) в случае Q = Н\ проводится в главе II. При малых величинах д, Д, |jF(:c*)||, процессы, получаемые в рамках этой схемы, оказываются устойчивыми в смысле соотношения (8). Для задачи отыскания квазирешения уравнения (1) на выпуклом замкнутом множестве Q С Н\ предлагаются и исследуются два варианта метода проекции градиента so Є Нь жп+і = Pg ( (Рмхп + - Рм) - -7PMF'*(PMXn + ? - Рм$ЦРм*п + І - РмО), 7 > 0; (17) хо t Hi, хп+1 = PQnM ((хп + ~ Рм) - -lF'*{xn + - РМ$РЫ + - Рм$), 7 > 0. (18)
Здесь Pq ~ оператор проектирования из Н\ n&Q.
Стабилизация итераций (17), (18) в окрестности квазирешения х* уста навливается при выполнении основного условия (11) и условия достаточной малости величин % о, А, Д4 = "jj (І"~^^Р^Х^урІх^Г'ШмШно, -цри вы- боре_начального приближения xq из окрестности квазирешения с радиусом г = r(F,M,5, Д), для итераций (17) и (18) выполняется предельное соотно шение Thn>„ - х*\\2 < С3(5 + Д + Д3 + 7).
Здесь постоянная Сз = Сз(Р,М, , Д) ограничена сверху, a r(F, М, S, А) отделена от нуля при 5, Д —> 0.
Класс устойчивых итерационных методов решения нелинейных некорректных операторных уравнений
Рассмотрим оператор PMF {X + — PM)F {X + - / )- J действующий из конечномерного пространства М в М. Очевидно, что он самосопряжен и имеет спектр, состоящий из конечного числа неотрицательных собственных значений. Тот же вывод справедлив и по отношению к оператору PMF {x )F {x )PMi который в силу условия 1 не содержит точку Л = 0 в своем спектре. Обозначим через р наименьшее собственное значение оператора РмР (х )Р (х )Рм. Для оценки первого слагаемого, стоящего в правой части неравенства (6), воспользуемся следующим утверждением. Лемма 1. ([15]) Пусть выполняются условие 1 и соотношения соотношения (7), (8) гарантируют выполнение обоих неравенств из условия леммы 1. Обратимся к оценке первого слагаемого из правой части неравенства в (6). Согласно лемме 1, для линейного самосопряженного оператора А Є L(M, М), Здесь {А} - семейство спектральных проекторов оператора Л, А = / 2#д (см. [66, с. 295]). Отсюда для всех точек х Є Пд/гС-Рд/я ) П М, удовлетворяющих условию (8), получаем Зафиксируем полученный вспомогательный результат. Теорема 1. Пусть выполняются условие 1 и соотношения (1.2), (1.22), (1), (4), (7), Тогда для точек х Є М, удовлетворяющих условию (11), справедлива оценка (12). Обратимся к исследованию локальных свойств функционала tp(x) на М в окрестности точки Рмх . Прежде всего определим условия, обеспечивающие локальную сильную выпуклость р(х) на М вблизи точки Рмх и оценим радиус той окрестности PA Yгде Функционал {ж) является сильно выпуклым. На основании леммы 1 имеем оценку Отсюда для всех точек х,у Є UTO(PMX ) П М получаем (PMF x + t-PMtWix + t-PM PMix-y x-y) \\х-у\\\ (13) Пусть в дополнение к (4), (7) выполняется следующее условие на Докажем существование точки ас, принадлежащей внутренности множества Qri (Рм% ) ГЇ М (рассматриваемого как подмножество М) и доставляющей безусловный локальный минимум функционалу р(х). Такая точка х должна удовлетворять условию р м(%) = 0. Воспользуемся следующей известной леммой. Лемма 2. ([49, с. 20]) Пусть f:D - G- непрерывное отображение, D замкнутое подмножество конечномерного евклидового пространства G со скалярным произведением (,) ?- Предположим, что а Є D \ 0D и выполняется условие Тогда уравнение f(x) = 0 имеет по крайней мере одно решение х Є D\dD. Здесь и далее через dD обозначает граница множества D С G. Пусть в обозначениях леммы считаем, что погрешности 6, Д достаточно малы, так что Используя неравенства (13), (16), для точек х Є д{р.Г1{Рмх ) П М) = {уєМ: \\у- Рмх \\ = п} оценим
Непосредственно из леммы 2 вытекает Теорема 3. Пусть выполняются условие 1 и соотношения (1.2), (1-22), (1), (4), (7), (16). Тогда существует точка х М такая, что Из теорем 2, 3 вытекает следующее Следствие. Пусть выполняются условие 1 и соотношения (1.2), (1.22), (1), (4), (7), (Ц), (16). Тогда существует единственная точка х Є М, \\х — Рмх \\ гі, для которой tpfM(х ) = 0, Для практического нахождения локального минимума функционала ф{х) могут использоваться различные методы безусловной минимизации на конечномерномпространстве М, Как правило, такие методы-вырабатывают релаксационные последовательности {хп} С М: р{хп+\) (р{хп). Укажем условия, гарантирующие принадлежность области сильной выпуклости гіОРма: ) П М всех точек произвольной релаксационной последовательности. Пусть XQ - начальная точка рассматриваемого итерационного процесса, XQ 6 іТі(Рмх ) ПМ. Необходимо гарантировать, чтобы наряду с хо множество уровня Тогда, согласно (17), для любой точки х є E(XQ) справедливо Следовательно, при выборе начального приближения XQ ЄМ согласно (19), все точки релаксационной последовательности {хп} начиная с XQ лежат в области сильной выпуклости функционала р{х). Хорошо известно, что для многих релаксационных методов минимизации сильно выпуклых функционалов в конечномерном пространстве характерна быстрая сходимость вырабатываемых последовательностей {хп} к изолированной точке локального минимума (см., например, [21, гл. 5]). В силу непрерывности р м(х), для таких последовательностей выполняется lira г(жп) = ф м{%) — 0- Непо п—юо средственно из оценки (12) вытекает Теорема 4. Пусть выполняются условие 1, соотношения (1.2), (1.22), (1), погрешности 6, А удовлетворяют условиям (4), (7), (Ц) (16), (18), а начальное приближение Хо М выбрано согласно (19). Тогда для произвольной релаксационной последовательности {хп} такой, что
Построение итерационных методов решения.ннений с пониженными требованиями к гладкости оператора
Конечно, проблема практического построения такой пары (М, ) не проще исходного уравнения. В отличие от 2, где величина р = р(М) в теоремах 2.1-2.4 определяется лишь подпространством М, величина р = р(М,) в теоремах 1, 2 зависит уже от обеих компонент пары (М,), и задача выбора (М, ) обеспечивающая как выполнение условий (9)-(12), так и малость правой части оценки (13), является более сложной. Дело в том, что стремление к минимизации величины А за счет вариации пары (М, ) даже при неизменной размерности М может привести к нежелательному уменьшению величины р, что в свою очередь повлечет ужесточение требований к погрешности S и начальному" приближению хо (см. теоремы 1, 2), Оптимальным является такой подбор (М, ), который уменьшает всю правую часть оценки (13) без существенного снижения р(М,). Покажем, что при наложении на оператор F{x) нежестких дополнительных—условийизадача выбора подобной-_пары (М,4)-может быть несколько _ упрощена. Введем подпространство и рассмотрим оператор Здесь аффинное подпространство Мх получено из М параллельным сдвигом в точку х , а Ф(а;) есть фактически сужение оператора F(x) на построенное таким образом подпространство. Дифференцируемость оператора Ф(х) в открытой окрестности решения х не предполагается, но будем считать, что существует производная Фреше У(х): М -У Щ.
Обозначим В дальнейшем вместо условия 1 будем считать выполненным следующую его модификацию. Условие 2. Подпространство Ы С Щ выбрано так, что оператор У{Рмх ): М - Яг является инъективным: Кег($ (Рмх )) = {0} Обозначим через р минимальное собственное значение оператора Подчеркнем, что определенная таким образом величина р = р(М) в отличие от р = р(М, ) зависит лишь от подпространства М, но не зависит от управляющего элемента . В силу условия 2, р 0. Лемма 2. Пусть выполняются условие 2 и соотношения Доказательство проводится почти дословным повторением доказательства леммы 2.1 (см. [15]) с заменой там величины р на р. Неравенства (17) являются аналогами соотношений (2.7), (2.8), гарантирующих выполнение всех условии леммы 2.1. Использование леммы 2 вместо леммы 1 позволяет при малом Д2 получить все результаты теорем 1, 2 с новой величиной р = р{М) вместо прежней р = р(Л4))- Сформулируем эти результаты. —-Теорема3. Пусть выполняющемуславиеJL, соотношения (4) .(5 -положим, что погрешности 5, Д, Дг и невязка Ф(Рд/;с ){ удовлетворяют условиям Тогда функционал р{х) является сильно выпуклым на множестве всех точек х Є М таких, что того выполняется соотношение то существует единственная точка х Є М такая, что \\х — Рмх \\ Г6; Теорема 4. Пусть выполняются условие 2, соотношения (4), (5), (18) и неравенство Тогда при выборе начального приближения XQ из условия для точек произвольной релаксационной последовательности {хп} такой, что ір м(хп+і) р м(хп), Ит $tf(#n)l! = 0, справедливо предельное соот п—кю Выполнение условия 2 и малость величины Дг можно обеспечить подходящим выбором подпространства М (см. 6). Малость величин Д, ]Ф{Рмъ в условиях (18)-(20) можно теперь добиваться вариацией элемента Є Н\ при фиксированном подпространстве М.
При выполнении условий теорем 3, 4, для решения задачи (6) применим общий алгоритм построения устойчивых итерационных методов, предло женный в 2. В частности, используя в качестве базового процесса метод градиентного спуска с постоянным шагом, приходим к итерационному про цессу _ _ аналогичному (3.1). Обратимся к анализу основного условия 2.1 и его модификации 5.2 и обсудим возможности практического подбора подпространства М, обеспечивающего их выполнение. В ряде случаев (см., например, [81, с. 129; 89]) удается доказать инъ-ективность оператора Р"{х) для точек х из некоторого подмножества пространства решений, т. е. для х Є D С Н\. В работах [81, 89], относящихся к обратным задачам акустического рассеяния, включение х Є D имеет смысл условия повышенной гладкости элемента а;, совмещенной с требованием малости отклонения функции х(-) от постоянной. В подобных случаях условие 2.1 автоматически выполняется для любого подпространства М, если х D. Проверка последнего соотношения должна опираться на имеющуюся априорную информацию о решении х . В общем случае подпространство М можно выбирать исходя из аналога условия 2.1, относящегося к точке ху не совпадающей в общем случае с х \ Из (1) следует, что величина Действительно, если .inf 1.Р (ж)М1 = 0. то найдется такая последова hM,\\h\\=l " v " тельность {hn} С М, \\hn\\ — 1, что jF (a:)/in —v 0. С другой стороны, в силу конечномерности пространства М, из последовательности {hn} можно выделить подпоследовательность {hnt}, сильно сходящуюся к некоторому элементу ho Є М. Очевидно, что )Ло = 1 и ( (ж)/1о = 0- Последнее соотношение противоречит условию (1). Тем самым неравенство (2) доказано. Следующая теорема показывает, что если точка х достаточно близка к аг , то (1) обеспечивает выполнение условия 2.1. Теорема 1. Пусть для некоторой точки х и конечномерного подпространства М С Ні выполняется условие (1), причем Теорема доказана. Таким образом, теорема 1 устанавливает возможность конструктивного подбора подпространства М, удовлетворяющего условию 2.1. Именно, следует выбирать М С #і так,, чтобы для точки х, достаточно близкой к х , выполнялось (1). При этом вариация пробной точки х доставляет дополнительные возможности построения М. Обсудим возможность проверки условия 5.2. По аналогии с (5.15) введем оператор Ф: М -» /?2,
Градиентно-проекционный метод для нахождения квазирешений нерегулярных нелинейных уравнений на выпуклом замкнутом множестве
В данном параграфе исследуется модификация итерационного процесса, предложенного в 2. В отличие от схемы (2.4), порождающей итерации хп Є Q, которые в общем случае не лежат в М, рассматриваемый здесь процесс вырабатывает приближения хп Є Q П М. Пусть Q С #і - выпуклое замкнутое ограниченное множество. Зафиксируем конечномерное подпространство М С Ні и будем считать выполненным следующее предположение, усиливающее условие 1.2.1. Условие 1. Подпространство М выбрано так, что Как и в 2, будем считать, что оператор F(x) дважды дифференцируем по Фреше, причем производная F"(x) удовлетворяет условию Липшица (1.4). Пусть вместо точного оператора F(x) доступно лишь его приближение F(x)} дифференцируемое по Фреше и удовлетворяющее условию (2.3). Для аппроксимации квазирешения Є Q предлагается итерационный процесс: XQ #i, Аналогично (2.5) представим (1) в виде Таким образом, процесс (1) является комбинацией метода проекции градиента с постоянным шагом ([20, с. 71]) для задачи и проектирования получаемых итераций на аффинное подпространство М%. В случае Q = #i цроцесс (1) совпадает с методом (1,3.1). Исследуем асимптотическое поведение точек Последовательности (1) при Заметим, что последние слагаемые неравенства (4) совпадают с заключительной частью оценки (2.7). Дословно повторяя следующие за (2.7) рассуждения, составляющие доказательство теоремы 2.2, приходим к основному результату настоящего параграфа с новой величиной Де = (Д2 + 2М1Д5 + Д!)1/2 вместо прежней Д. Теорема 1. Пусть выполняются условие 1, соотношения (1-4), (1-1$)t (2.3), начальное приближение XQ удовлетворяет условию константы qj, С, у выбраны согласно (2.37), (2.41), (2.40)j (2.42) с заменой А но Де-
Предположим, что погрешности AQ, Д4, 6 удовлетворяют (2.22), (2.28), (2.30), (2.32) и первому неравенству в (2.38) с заменой А на Де- Тогда для определяемой согласно (1) последовательности {хп} выполняются соотношения Соотношения (5), (6) гарантируют стабилизацию вырабатываемых методом (1) приближений в малой окрестности квазирешения х , если величины А, As, Аб, 6 достаточно малы. В заключение этой главы сопоставим ее результаты с результатами некоторых других работ в данной области. В [75] задача нахождения квазирешения изучается в рамках вариационного подхода к некорректным операторным уравнениям. Рассматривается уравнение где G(x) - в общем случае нелинейный оператор, действующий из Ні в Щ. Считается, что точные данные (G, у) задачи (1) неизвестны, а вместо них заданы приближенные (С?, у) такие, что В соответствии со схемой Тихонова уравнение (1) заменяется регуляризую-щей экстремальной задачей вида либо той или иной ее конечномерной аппроксимацией. При подходящем согласовании а — а{5) (6 — (Л, о-)), \ima($) = 0 устанавливается существо вание элементов х , на которых достигается глобальный минимум в задаче (2), и сильная сходимость # «\ — х при S —У 0. В случае нелинейного оператора F(x) = G(x) — у реализацию этой схемы затрудняет необходимость отыскания глобального минимума функционала Фа[х), сильная выпуклость которого на Q в общем случае имеется лишь в шаре с центром х6а радиуса г (а) а (см. [96]). То же относится и к возможным конечномерным аппроксимациям функционала Фа(з)- В 1 настоящей главы для отыскания квазирешения уравнения (1.1) предлагается схема, базирующаяся на идее минимизации сильно выпуклого функционала (1.5) на специально выбираемом конечномерном подпространстве М С Ні. В отличие от функционала Тихонова Фа(#), х & Hi, радиус сильной выпуклости которого стремится к нулю при S —» 0 (поскольку lima( ) = 0), сильная выпуклость функционала 6—ь0 ?(#), х Є М, имеет место на шаре фиксированного радиуса (см. (1.20)). Это позволяет не прибегая для минимизации tp(x) к процедурам глобального поиска, успешно использовать широкий спектр классических релаксационных методов конечномерной минимизации и переносить на случай уравнения (1.1) имеющиеся для них оценки скорости сходимости.
Отметим, что итерационные процессы (2.4), (3.1) применимы и в том случае, когда х является решением уравнения (1.1) и известно выпуклое замкнутое множество Q, содержащее х . Они могут быть успешно использованы и в частном случае аффинного оператора где А Є L(Hi #г). В этом случае задача (2.1) записывается в виде Очевидно, что второе неравенство в (1.4) выполняется автоматически, а условие 1.2.1 принимает вид Согласно теоремам 2.2 и 3.1, методы (2.4), (3.1) применительно к задаче (3) вырабатывает последовательность {#„}, стабилизирующуюся в окрестности квазирешения х при выборе начального приближения XQ В достаточной близости от х . Следует отметить, что за счет использования свойства выпуклости функционала (3) в [9] устанавливается глобальная сходимость методов итеративной регуляризации для решения (3). Однако, в отличие от итерационных методов, рассмотренных в [9], методы (2.4), (3.1) в случае приближенных данных не требуют сопровождения в виде критерия останова итерационного процесса. Результаты, представленные в настоящей главе, опубликованы в работах автора [38, 40], а также в совместных работах [12, 35, 44]. В [12, 35] автором проведено обоснование устойчивости градиентного метода (1.3.1) в применении к задаче (1.6). В [44J анонсирована полученная автором теорема 3.1.
Численные эксперименты с обратными задачами гравиметрии
В первой серии расчетов решалась модельная задача (1.1) с известным точным решением - негладкой контактной поверхностью при отсчетной границе z(x,y) — —6. Во всех случаях принималось Н = 1.5. В качестве области Dy на которой производятся измерения функции д(х,у), рассматривались квадраты D — [—4,4] х [—4,4],D = [-2,6] х _[ 4,4]. Предусматривалась возможностьзадания функции д(х,у) в (1.1) с погрешностью. Приближенная функция д(х,у) строилась в виде где 5 уровень погрешности, со(х,у) - реализация случайной величины, равномерно распределеннойла_отрезке [—1, 1] — ___ Интегралы по областям D 1). D во всех случаях вычислялись с использованием схемы Симпсона на сетке 20 х 20. Пример 1. Рассматривался градиентный процесс (2.22) при 7 = 0.25, М = LK, К = 4, = 0. Предполагалось, что в (1) величина 6 = 0. В качестве области измерений выбирался квадрат начальным прибли жением была функция ZQ(Х, у) = —6, первоначальная невязка составляла 11 — 1) (25(1)] = 24.9012. При реализации процесса с точной функцией д{Х)У) за 100 итераций эту невязку удалось уменьшить до 4.8799, на 500-й итерации невязка составила 3.0799. Устойчивость вырабатываемых приближений по отношению к номеру итерации характеризует таблица 1. Здесь и далее в таблицах 1-3 под невязкой на n-й итерации понимается величина ІІЗп- ІІад?)- На рис. 1 (см. приложение) показано сечение исследуемой области вертикальной плоскостью у — 0. Жирной линией выделено сечение аппроксимации границы раздела, полученной на 1000-Й итерации, тонкой - сечение точной границы; кривые 1- 3 на рис. 1-3 обозначают сечения графика функции д(х,у), земной поверхности и графика начального приближения ZQ (х, у) плоскостью у = 0. Сечение земной поверхности совпадает с осью абсцисс. Аналогичный результат, полученный при тех же значениях параметров, но для приближенной функции д(х, у) с максимальной абсолютной погрешностью 5 — 0.3, показан на рис. 2. В табл. 2 представлена зависимость невязки от номера итерации. Видно, что величина невязки по-прежнему монотонно убывает, но по сравнению с табл. 1 стабилизируется на несколько более высоком значении. Это можно объяснить введением в вычислительный процесс искусственной погрешности 6 = 0.3
На рис. 3 показан результат расчетов, проведенных с прежними значениями параметров, но при 5 = 0.6. Представлено сечение точной поверхности и ее аппроксимации, полученной на 1000-й итерации с выбором в качестве области измерений квадрата D , а в качестве начального приближения - функции ZQ(X, у) = —8. Стабильное уменьшение невязки по мере роста Сходный характер поведения невязки наблюдался и в аналогичных экспери-ментах с другими начальными данными. Как показывает совместный анализ таблиц 1-3, применяемый метод обладает устойчивостью по отношению к номеру итерации и к погрешности. Опишем результаты расчетов для уравнения (1.4) с известным точным решением Во всех случаях" принималосьЯ — 1.5. Отметим, что в датшомтшучае г Є М. В качестве начального приближения была выбрана сфера радиуса 0.5 с центром в точке (0,0, —1.5). В качестве области D, на которой производятся измерения функции д(х} у), рассматривался квадрат D = [—1,1] х [—1,1]. Приближенная функция д (х,у) строилась в виде (1). Все вычисления проводились с использованием равномерных сеток 16 х 16 на Q и 20 х 20 на D. При вычислении интеграла по д в (1.5) использовалась схема Симпсона с числом узлов, равным 5. Пример 2. Рассматривался итерационный процесс (2.24) при у = 0.1, = 0, М = Lg, К 2. Первоначальная невязка составляла Ц»"о —г ]) — 2.4836. Вычисления проводились при 6 = 0. При реализации процесса за 300 итераций эта невязка уменьшилась до 0.2857. Динамика изменения невязки представлена в табл. 4. Монотонное уменьшение невязки с ростом количества итераций говорит об устойчивости процесса (2.24). Под невязкой на іьй На рис. 4 (нижняя часть) показано сечение искомой поверхности (тонкая линия), начального приближения (малый овал) и поверхности, полученной на 1000-й итерации (жирная линия), плоскостью tp — 0. Здесь и далее на рис. 5-9 кривая 1 - сечение графика функции д(х, у) плоскостью ц = 0, 2 -земная поверхность. Сечение земной поверхности совпадает с осью абсцисс. Результаты счета с теми же параметрами, но с приближенной функцией д{х, у) при максимальном уровне абсолютной погрешности 5 — 0.1 приведены на рис. 5. В верхней "CLCTII рисунка точками показаны знатіс:::іп приближенной функции д{хуу), использовавшейся в процессе (2.24). При этом невязка как и в случае 6 = 0 монотонно уменьшалась при увеличении количества итераций. Соответствующие данные представлены в табл. 5.
