авторефераты диссертаций БЕСПЛАТНАЯ  БИБЛИОТЕКА

АВТОРЕФЕРАТЫ КАНДИДАТСКИХ, ДОКТОРСКИХ ДИССЕРТАЦИЙ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ

Ньютоновские методы поиска особых решений нелинейных уравнений

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

Ерина Мария Юрьевна Ньютоновские методы поиска особых решений нелинейных уравнений 01.01.09 дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

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

Москва – 2007

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

Научный консультант: доктор физико-математических наук Измаилов Алексей Феридович.

Официальные оппоненты: доктор физико-математических наук, профессор Жадан Виталий Григорьевич;

кандидат физико-математических наук, доцент Денисов Дмитрий Витальевич.

Ведущая организация: Институт прикладной математики им. М. В. Келдыша Российской академии наук.

Защита состоится 15 февраля 2008 года в 11 часов на заседании диссертационного совета Д 501.001.44 в Московском государственном университете им. М. В. Ломоносова по адресу: 119991, Москва, ГСП-1, Ленинские горы, МГУ, 2-й учебный корпус, факультет ВМиК, аудитория 685.

С диссертацией можно ознакомиться в библиотеке факультета ВМиК Московского го сударственного университета им. М. В. Ломоносова по адресу: 119991, Москва, ГСП-1, Ленинские горы, МГУ, 2-й учебный корпус.

С текстом автореферата можно ознакомиться на официальном сайте факультета ВМиК Московского государственного университета им. М. В. Ломоносова http://www.cs.msu.su в разделе Наука – Работа диссертационных советов – Д 501.001.44.

Автореферат разослан 11 января 2008 г.

Ученый секретарь диссертационного совета Н. П. Трифонов профессор

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Еще в 70–е годы XIX–го века было установлено (E. Schrder), o что метод Ньютона обладает лишь линейной скоростью сходимости к кратному корню одного скалярного уравнения с одной неизвестной. Квадратичная скорость сходимости может быть восстановлена путем домножения стандартного шага метода на кратность корня. Первая попытка обощить эти результаты на многомерный случай была сделана в 60–е годы XX–го века (L.B. Rall). В свою очередь, эта работа инициировала целый ряд публикаций (D.W. Decker, A.O. Griewank, C.T. Kelley, H.B. Keller, G.W. Reddien). Итогом этих исследований стало следующее утверждение: в лучшем случае удается гарантиро вать линейную скорость сходимости метода Ньютона к особому решению, и, кроме того, начальное приближение недостаточно выбирать просто близким к исходному решению (множество подходящих начальных приближений может не содержать окрестности точ ного решения, хотя это множество, как правило, в определенном смысле плотно ).

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

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

В настоящее время доминирующим в области численного отыскания особых решений представляется другой подход, связанный с построением так называемых расширенных (еще говорят определяющих) систем. Этот подход был предложен в 70–е годы XX–го века (R. Seydel, H. Weber, W. Werner, G. Moore, A. Spence), однако, идея настолько есте ственна, что, возможно, она появлялась независимо и в других работах. Идея состоит в том, чтобы включить исходное уравнение в семейство уравнений, зависящее от некоторых дополнительных переменных (параметров) таким образом, чтобы оператор новой систе мы имел сюръективную производную в соответствующем решении. Этот первый этап называется раскладыванием ( unfolding ) особенности. Второй этап, называемый иногда сечением ( cut ), состоит в нахождении дополнительных уравнений, делающих расширен ную систему квадратной, причем так, чтобы искомому особому решению соответствовало регулярное (в определенном выше смысле) решение получаемой расширенной системы.

Тогда это решение можно искать любым традиционным численным методом (например, методами ньютоновского типа).

Среди недавних исследований по численным методам поиска особых решений отме тим разработки как зарубежных (E.L. Allgower, K. Bhmer, W. Govaerts,, M. Hermann, o A. Hoy, V. Janovsk, P. Kunkel, W. Middelman), так и отечественных (О.А. Брежнева, y А.Ф. Измаилов, А.А. Третьяков, А. Хмура) авторов.

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



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

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

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

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

2. Исследована устойчивость предложенного подхода по отношению к возмущениям оператора уравнения.

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

нелинейных операторных уравнений с фредгольмовыми производ ными;

систем нелинейных уравнений с ограниченной гладкостью и комплементар ных задач.

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

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

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

Апробация работы. Результаты работы были представлены в виде докладов на се минаре кафедры Исследования операций факультета ВМиК МГУ им. М.В. Ломоносова (рук. А. Ф. Измаилов, Д. В. Денисов), а также на следующих конференциях:





1) научная конференция Тихоновские чтения, Москва, МГУ, октябрь 2005 г.;

2) CERMCS international conference of young scientists, Chisinau, Moldova State University, сентябрь, 2006 г.;

3) XIV международная научная конференция студентов, аспирантов и молодых ученых Ломоносов, Москва, МГУ, апрель 2007 г.;

4) V московская международная конференция по исследованию операций (ORM2007), Москва, ВЦ РАН, апрель 2007 г.

Публикации. По теме диссертации опубликовано 9 работ.

Структура и объем диссертации. Диссертация состоит из введения, трех глав, приложения, заключения и библиографии. Общий объем диссертации 103 страницы. Биб лиография содержит 68 наименований.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

Рассматривается уравнение F (x) = 0, (1) где F : O IRm дважды непрерывно дифференцируемое отображение, O IRn открытое множество, n m. Решение x O уравнения (1) называется особым, если rank F () m.

x или, другими словами, r = corank F () 0.

x В противном случае решение x называется регулярным.

Структуру особенности F в точке x, а точнее, структуру образа F (), можно описать x матричным уравнением P F (x) = 0, (2) где P IRmm проектор на некоторое прямое дополнение Y2 подпространства Y1 = m im F () в IR параллельно Y1. Точка x удовлетворяет (2), но, во-первых, P в общем случае x не может быть известно точно (без знания искомого x), а во-вторых, система (2) содержит в (2) следует заменить некоторой его слишком много уравнений. Поэтому, во-первых, P аппроксимацией P : O IRmm (подразумевается, что P () = P ), а во-вторых следует x оставить в системе F (x) = 0, P (x)F (x) = 0 (3) лишь существенную часть второго уравнения.

Все известные на сегодня способы выбора проектора P (·) предполагают знание коран га особенности r. Иногда r может быть известно из анализа, являющегося внешним по отношению к описываемому подходу. С другой стороны, r может рассматриваться как параметр с конечным числом возможных значений. Наконец, известны регулярные про цедуры для определения r, предполагающие, что известна точка в IRn достаточно близкая к x (такая точка нужна в любом случае, поскольку речь идет о локальных методах нью тоновского типа).

Раздел 1.1.1 посвящен описанию двух способов реализации отображения P (·), на ос нове которых конструируется определяющая система вида (x) = 0, (4) где : O IRm IRr(nm+r) гладкое отображение.

Один из способов выбора P (·) заключается в следующем. Зафиксируем матрицы A n(nm+r) и B IRmr такие, что IR IRn = ker F () ker AT, IRm = im F () im B.

x x (5) Эти условия подразумевают, в частности, что rank A = n m + r, rank B = r.

Тогда существует единственная пара матриц K IRn(nm+r) и C IRmr такая, что x AT K = Enm+r, F ()K = 0, (F ())T C = 0, B T C = Er.

x Столбцы K и C образуют базисы ker F () и (im F ()) соответственно. Проектор на Y x x m параллельно Y1 в IR задается формулой P = BC T.

Чтобы аппроксимировать K и C, рассмотрим следующую пару матричных линейных систем:

F (x)K BT = 0, AT K = Enm+r, (6) (F (x))T C AT T = 0, B T C = Er (7) n(nm+r) mr r(nm+r) относительно неизвестных (K, C, T ) IR IR IR ;

x O играет здесь роль параметра. Используя теорему о малом возмущении обратимого оператора, получаем, что в сделанных предположениях существуют непрерывно дифференцируемые отображения K(·) : O IRn(nm+r), C(·) : O IRmr и T (·) : O IRr(nm+r) такие, что K() = K, x C() = C, x T () = 0.

x Аппроксимация P (·) выбирается следующим образом: для x O P (x) = B(C(x))T.

Тогда согласно (7) P (x)F (x) = B(C(x))T F (x) = BT (x)AT x O.

Введем отображение : O IRm IRr(nm+r), (x) = (F (x), T (x)) = (F (x), T1 (x),..., Tr (x)), (8) где через Ti (x) обозначена i-я строка матрицы T (x), i = 1,..., r. Пусть ej векторы n стандартного базиса в IR, j = 1,..., n. Введенное отображение непрерывно дифферен цируемо на O, причем для вычисления производной этого отображения можно использо вать следующую формулу: для всякого x O Ti (x)ej = ((C(x))T (F (x)[ej ])K(x))i, i = 1,..., r, j = 1,..., n. (9) Отметим также, что для вычисления производной T можно воспользоваться явной формулой Tij (x) = (F (x)[K j ])T C i, где K j и C i – столбцы матриц K(x) и C(x) соответственно, i = 1,..., r, j = 1,..., n.

Следующее предложение дает необходимое и достаточное условие того, что ker () = {0} x (10) (что равносильно невырожденности матрицы ( ())T ()) и, в частности, x является x x изолированным решением уравнения (4).

Предложение 1. Пусть отображение определено согласно (8).

Тогда (10) равносильно равенству { ker F () | F ()[, x] im F () x ker F ()} = {0}.

x x x x (11) Условие (11) известно как условие невырожденности второго дифференциала.

Система (4) при r 0, по-прежнему, является переопределенной. Общий оператор выбора это отображение R(·) : IRm L(IRm IRr(nm+r), IRn ). Задав это отображение, от системы (4) переходим к системе R(x)(x) = 0. (12) В разделе 1.1.2 описываются две конкретные реализации оператора выбора, которые пред ставляются наиболее естественными:

1) R(·) R, где R L(IRm IRr(nm+r), IRn ) фиксированный (постоянный) опера тор;

2) R(·) = ( (·))T.

К системе (12) с постоянным оператором выбора могут применяться стандартные чис ленные методы, например, метод Ньютона:

R (xk )(xk+1 xk ) = Rxk. (13) В слабых предположениях на первые две производные F в искомом решении x можно показать, что при почти любом R такой процесс будет обладать локальной сверхлинейной сходимостью. В частности, R можно выбирать, скажем, случайным образом.

Для второго способа задания R(·) итерация метода Ньютона для уравнения (12) имеет вид ( (xk )[xk+1 xk ])T (xk ) + ( (xk ))T (xk )(xk+1 xk ) = ( (xk ))T (xk ), и может быть заменена своей неточной версией без ущерба для скорости сходимости:

( (xk ))T (xk )(xk+1 xk ) = ( (xk ))T (xk ), что соответствует методу Гаусса Ньютона для уравнения (4). Данная модификация поз воляет избежать необходимости вычислять вторые производные. Для введенного в (8) отображения эта формула принимает вид r (F (xk ))T F (xk ) + (Ti (xk ))T Ti (xk ) (xk+1 xk ) = i= r k T k (Ti (xk ))T Ti (xk ).

= (F (x )) F (x ) + (14) i= Из предложения 1 и стандартного результата о локальной сверхлинейной сходимости метода Гаусса–Ньютона вытекает Теорема 1. Пусть в решении x уравнения (1) выполнено условие (11) невырожден ности второго дифференциала.

Тогда если матрицы A и B удовлетворяют условию (5), а начальное приближение x IRn достаточно близк к x, то итерационный процесс (14) корректно определяет о траекторию {xk }, которая сходится к x со сверхлинейной скоростью.

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

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

В разделе 1.2 предлагаются конструктивные способы идентификации коранга особен ности r и выбора матриц A и B, необходимых для реализации описанного подхода, по имеющемуся начальному приближению x0 IRn. Эти способы основаны на оценке рассто яния до решения при выполнении условия 2-регулярности.

Для всякого x O определим сингулярное разложение матрицы F (x):

F (x) = U (x)(x)(V (x))T, где (x) IRmn – диагональная матрица, на диагонали которой стоят сингулярные числа i (x), i = 1,..., m, 1 (x) 2 (x)... m (x) 0, U (x) IRmm и V (x) IRnn ортогональные матрицы.

Положим r(x0 ) = m max{i = 1,..., m | i (x0 ) F (x0 ) /2 }. (15) Далее, считая коранг r определенным, столбцы aj матрицы A и bi матрицы B зададим следующим образом:

aj = v j (x0 ), j = m r + 1,..., n, bi = ui (x0 ), i = m r + 1,..., m, (16) где для всякого x O через ui (x), i = 1,..., m, и v j (x), j = 1,..., n, обозначены столбцы матриц U и V соответственно.

Предложение 2. Пусть в решении x уравнения (1) выполнено { ker F () | F ()[, ] im F ()} = {0}.

x x x (17) Тогда если начальное приближение x0 IRn достаточно близк к x, то число r = о r(x0 ), определяемое согласно (15), совпадает с corank F (), а матрицы A и B, столбцы x которых определяются согласно (16), удовлетворяют условию (5).

Итоговый, полностью реализуемый алгоритм NDS (Newton for Dening System) выгля дит следующим образом:

Алгоритм NDS 1. Выбираем вариант А или Б алгоритма. В случае варианта А, выбираем R L(IRm IRr(nm+r), IRn ).

2. Фиксируем (0, 1). Полагаем k = 0 и выбираем x0 IRn.

3. Вычисляем сингулярное разложение F (x0 ) и определяем число r = r(x0 ) согласно (15). Задаем матрицы A IRn(nm+r) и B IRmr со столбцами определяемыми согласно (16).

4. Решая матричные линейные системы (6), (7), вычисляем матрицы K(xk ), C(xk ) и T (xk ).

5. Вычисляем матрицы Ti (x), i = 1,..., r, по формулам (9).

6. Определяем точку xk+1 согласно (13) для варианта алгоритма A и согласно (14) для варианта Б. Увеличиваем номер шага k на единицу и переходим к п. 4.

Теорема 2. Пусть в решении x уравнения (1) выполнено условие (17).

Тогда если начальное приближение x0 IRn достаточно близк к x, то вариант Б о алгоритма NDS корректно определяет траекторию {xk }, которая сходится к x со сверх линейной скоростью.

Аналогичное утверждение имеет место и для варианта А алгоритма NDS, с той только разницей, что оно будет верно для почти любого R L(IRm IRr(nm+r), IRn ).

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

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

В разделе 2.1 рассматривается краевая задача x = f (t, x), t [0, 1], (18) g(x(0), x(1)) = 0, (19) n n n n n где f : IR IR IR и g : IR IR IR заданные отображения. Пусть G открытое множество в IR IRn. Введем множества G[0, 1] = G ([0, 1] IRn ), G0 = {x IRn | (0, x) G}, G1 = {x IRn | (1, x) G}.

Отображение f непрерывно и дважды непрерывно дифференцируемо по второй перемен ной на G[0, 1], а g дважды непрерывно дифференцируемо на G0 G1. Пусть, наконец, x(·) Cn [0, 1] решение задачи (18), (19), график которого graph x = {(t, x(t)) | t [0, 1]} содержится в G.

Решение x(·) задачи (18), (19) естественно назвать особым, если вырождена матрица g g F 1 IRnn, F1 = ((0), x(1)) + 1 ((0), x(1))1 (1), x x x x где 1 (·) : [0, 1] IRnn решение начальной задачи:

f 1 = (t, x(t))1, (20) x 1 (0) = En. (21) В разделе 2.1.1 речь идет о редукции краевых задач для обыкновенных дифференци альных уравнений к конечномерным системам уравнений. Применяя к уравнению (18) теорему о дифференцируемой зависимости решения от начальных условий и теорему единственности, получаем следущее: найдется окрестность O точки x(0) в IRn и гладкое : [0, 1] O IRn :

= f (t, ), (22) (0) = x. (23) Тогда t [0, 1] (t, x(0)) = x(t), причем x O, IRn (t, x) = 1 (t, x), (t, x) = 2 (t, x, ), x x где 1 (·, x) : [0, 1] IRnn фундаментальная матрица линеаризованного на функции (·, x) уравнения (18), т.е. решение матричной начальной задачи (20), (21), а 2 (·, x, ) :

[0, 1] IRnn решение матричной начальной задачи 2f f 2 = (t, (t, x))2 + 2 (t, (t, x))[1 (t, x)]1 (t, x), t [0, 1], (24) x x 2 (0) = 0. (25) Введем отображение F : O IRn, F (x) = g(x, (1, x)).

Краевая задача (18), (19) сводится к конечномерной системе (1) с таким оператором F.

Предложение 3. В сделанных предположениях отображение F удовлетворяет в точке x условию невырожденности второго дифференциала (11) тогда и только тогда, когда ker F 1 g (, (1))[(, 1 (1)), (x, 1 (1)x)] + x g (, (1))2 (1, )x im F 1 x ker F + x = {0}, x где (·) = (·, x), 2 (·, ) = 2 (·, x, ). Кроме того, отображение F удовлетворяет в точке x условию (17) тогда и только тогда, когда ker F 1 g (, (1))[(, 1 (1)), (, 1 (1))] + x g (, (1))2 (1, ) im F + x = {0}.

x Раздел 2.1.2 посвящен применению к краевым задачам алгоритмов, описанных в гла ве 1. Реализация данных алгоритмов требует решения на каждой итерации вспомога тельных матричных начальных задач (22), (23);

(20), (21) и (24), (25). Последнее же, разумеется, делается приближенно, что приводит к необходимости принимать во вни мание неизбежную неточность вычисления значений и производных отображения F. Рас сматривается случай, когда для решения вспомогательных начальных задач используется простейшая разностная схема, а именно схема Эйлера, и показывается, что возникающие при этом погрешности можно интерпретировать как гладкое возмущение отображения F, удовлетворяющее всем условиям теорем об устойчивости из раздела 1.3.

Раздел 2.2 посвящен уравнениям с фредгольмовыми производными и, в частности, интегральным уравнениям.

К важнейшим типам особенностей отображений бесконечномерных пространств отно сится так называемая фредгольмова вырожденность. Пусть X банахово простран ство, O окрестность точки x в X, отображение F : O X дважды непрерывно диф ференцируемо на O, причем его производная F () является фредгольмовым оператором, x т.е. подпространство im F () замкнуто и x dim ker F () = dim ker(F ()) = r x x при некотором (конечном) r.

Простейший (но при этом крайне важный) пример отображений с фредгольмовыми производными доставляют конечномерные отображения, что соответствует случаю X = IRn, и в этом смысле излагаемые ниже результаты обобщают построения из раздела 1.1.

Важнейший бесконечномерный пример отображений с фредгольмовыми производными это интегральные операторы вида F (x) = x(·) f (·,, x( )) d, x(·) X, где f : IR IR IRm IRm гладкое отображение;

в качестве пространста X в данном случае можно взять Cm [0, 1] или L2, m [0, 1]. В случае фредгольмова F (), решение x x уравнения F (x) = является особым, если r 0.

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

В разделе 2.2.1 приводятся некоторые сведения о фредгольмовых линейных операто рах.

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

Структуру особенности F в точке x, а точнее, структуру образа F () можно описать x уравнением P F (x) = 0, где P : X X (непрерывный) проектор на (r-мерное) прямое дополнение подпро странства im F () в X параллельно im F (). Заменяя P некоторой его аппроксимацией x x ), получаем систему уравнений P : O L(X, X) (подразумевается, что P () = P x F (x) = 0, P (x)F (x) = 0.

Считая r известным, зафиксируем линейно независимые наборы a1,..., ar X и a,..., a X такие, что 1 r im F () lin{a1,..., ar } = {0}, x im(F ()) lin{a,..., a } = {0}.

x 1 r Чтобы аппроксимировать x1,..., xr и x,..., x рассмотрим следующие линейные си 1 r стемы: r F (x)i Tji aj = 0, i = 1,..., r, j= a, i = ij, i, j = 1,..., r, j r (x)) Tij a = 0, (F i = 1,..., r, i j j=, aj = ij, i, j = 1,..., r.

i относительно неизвестных 1,..., r X,,..., X и T IRrr, где x O играет 1 r роль параметра.

Определяющая система имеет вид (x) = 0, (26) где : O X IRrr, (x) = (F (x), T (x)). (27) Явная формула для производной T :

Tij (x) = (F (x)[j (x)]) (x), i, j = 1,..., r.

i Следующее предложение является естественным обобщением предложения 1 для ко нечномерного случая, описанного в разделе 1.1.1, и дает необходимое и достаточное усло вие того, что ker () = {0} x (28) и, в частности, что x является изолированным решением уравнения (26).

Предложение 4. Пусть отображение определено согласно (27).

Тогда (28) равносильно равенству { ker F () | F ()[, x] im F () x ker F ()} = {0}.

x x x x Если использовать базисы x1,..., xr в ker F () и x,..., x в ker(F ()), то это усло x x 1 r вие можно записать в виде r r k x, F ()[xj, xk ] = 0 i, j = 1,..., r IR x = {0}.

i k= Иными словами, это условие линейной независимости матриц k = ( x, F ()[xj, xk ] )i, j=1,..., r, x k = 1,..., r.

i Далее, распространяя описанный в главе 1 подход с использованием оператора выбора, получаем следующее: если оператор выбора имеет вид R L(X IRrr, X), r IRn, T IRrr, (QT )i ai, R(, T ) = + (29) i= где Q L(IRrr, IRr ), то тогда итерация метода Ньютона для системы R(x) = 0 прини мает вид r k k+1 k (Q(T (xk )(xk+1 xk )))i ai = F (x )(x x )+ i= r k (QT (xk ))i ai.

= F (x ) i= Для данного метода получены результаты о сходимости, аналогичные результатам, полу ченным в главе 1.

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

Рассматривается уравнение (1), где F : O IRm гладкое отображение, O IRn открытое множество, n m. Предполагается, что отображение F дифференцируемо (но не обязательно дважды дифференцируемо) на O.

Пусть 1,..., r ортонормированный базис в подпространстве (im F ()) = x T ker(F ()). Тогда точка x удовлетворяет системе уравнений x (F (x))T s = 0, s = 1,..., r.

F (x) = 0, (30) Зададим оператор выбора, т.е. линейный оператор R = (R0, R1,..., Rr ) : IRm r n n s=1 IR IR, и вместо переопределенной (в случае, когда x особое решение уравне ния (1)) системы (30) введем уравнение R (x) = 0, где отображение R : O IRn задается формулой R (x) = R(F (x), (F (x))T 1,..., (F (x))T r ) = s s F (x), R r = R0 F (x) + ··· s s F (x), Rn s= (через Rj обозначена j-я строка матрицы Rs, s = 1,..., r, j = 1,..., n).

s Пусть каждое из отображений x s F (x) : O IRn, s = 1,..., r, дифференцируемо в любой точке множества O по любому направлению в IRn. Тогда итерация ньютоновского метода примет вид s ( F ) (xk ;

R1 ) s r R0 F (xk ) + (xk+1 xk ) = ··· ( s F ) (xk ;

Rn ) s s= r 0 k Rs ( s F (xk )).

= R F (x ) + s= В разделе 3.2 данный метод реализуется для гладких переформулировок нелинейных комплементарных задач (NCP).

Нелинейная комплементарная задача ставится следующим образом:

найти x IRn такой, что G(x) 0, x 0, G(x), x = 0, (31) n n где G : IR IR гладкое отображение. Множество решений NCP (31) совпадает с множеством решений уравнения (1), где F : IRn IRn имеет компоненты Fi (x) = 2Gi (x)xi (min{0, Gi (x) + xi })2, i = 1,..., n.

Соответственно, возникает идея решать NCP (31) применяя к (1) с таким оператором F те или иные численные методы решения систем нелинейных уравнений. Однако, реализации этой идеи неизбежно связаны с преодолением весьма серьезных трудностей.

А именно, пусть x – решение NCP (31). Предположим, что отображение G дважды непрерывно дифференцируемо в некоторой окрестности точки x. Тогда отображение F имеет вблизи x производную, которая удовлетворяет условию Липшица, причем для лю бого x из этой окрестности справедливы равенства Fi (x) = 2(xi Gi (x) + Gi (x)ei min{0, Gi (x) + xi }(Gi (x) + ei )), (32) i = 1,..., n.

В частности, 0, если i I0, Fi () = 2 xi Gi (), если i I1, x x i = 1,..., n, Gi ()ei, если i I2, x где используются множества индексов I0 = I0 () = {i = 1,..., n | Gi () = 0, xi = 0}, x x I1 = I1 () = {i = 1,..., n | Gi () = 0, xi 0}, x x I2 = I2 () = {i = 1,..., n | Gi () 0, xi = 0}.

x x Отсюда следует, что если в решении x нарушается условие строгой дополнительности I0 =, которое принято считать весьма обременительным требованием, то x неизбежно является особым решением уравнения (1), т.е.

det F () = 0, x и эффективное отыскание этого решения стандартными ньютоновскими методами для уравнения (1) с оператором (32) становится невозможным.

С другой стороны, специальные ньютоновские методы для отыскания особых реше ний нелинейных уравнений, разработанные, например, А.Н. Дарьиной, А.Ф. Измаиловым, М.В. Солодовым и в главе 1, в данном случае также напрямую неприменимы, поскольку эти методы предполагают двукратную дифференцируемость F, что для данного отобра жения, вообще говоря, не имеет места ни при каких требованиях гладкости отображения G. Соответственно, применяется специальный подход из раздела 3.1.

В приложении представлены результаты вычислительного эксперимента для разра ботанных алгоритмов на некоторых тестовых примерах. Поведение алгоритмов сравнива лось с традиционными численными методами: для систем нелинейных уравнений и для H-уравнения Чандрасехара сравнение проводилось с методом Ньютона, для нелинейных краевых задач – с методом квазилинеаризации.

В заключении сформулированы основные результаты, полученные в диссертации.

Автор выражает глубокую благодарность своему научному руководителю Алексею Феридовичу Измаилову за постановку задачи, постоянное внимание к работе, ценные замечания и поддержку.

Работа выполнена при частичной финансовой поддержке Российского фонда фунда ментальных исследований (проекты 07-01-00270, 07-01-00416).

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ 1. Измаилов А. Ф., Штуца М. Ю. Класс ньютоновских методов для отыскания особых решений нелинейных уравнений при ослабленных требованиях гладкости // Теорети ческие и прикладные задачи нелинейного анализа. М.: ВЦ РАН, 2005. С. 62 75.

2. Измаилов А. Ф., Штуца М. Ю. Класс ньютоновских методов для нелинейных ком плементарных задач // Теоретические и прикладные задачи нелинейного анализа.

М.: ВЦ РАН, 2006. С. 3 22.

3. Izmailov A. F., Shtutsa M. Yu. Gauss-Newton method for nding singular solutions of nonlinear equations // Communications. Cermcs international conference of young scientists. Chisinau, 2006. P. 102-106.

4. Ерина М. Ю. Ньютоновские методы для отыскания особых решений систем нелиней ных уравнений // Тез. докл. XIV Международная конференция студентов, аспирантов и молодых ученых "Ломоносов";

секция "Вычислительная математика и кибернети ка". М.: Издательский отдел факультета ВМиК МГУ, 2007. С. 25.

5. Izmailov A. F., Yerina M. Yu. Gauss-Newton method for nding singular solutions of nonlinear equations // Труды. V Московская международная конференция по исследо ванию операций (ORM2007). М.: МАКС Пресс, 2007. С. 169-170.

6. Ерина М. Ю., Измаилов А. Ф. Метод Гаусса Ньютона для отыскания особых реше ний систем нелинейных уравнений // ЖВМ и МФ. 2007. Т. 47, № 5. С. 784 795.

7. Ерина М. Ю., Измаилов А. Ф. Определяющие системы для уравнений с фредгольмо выми производными // Теоретические и прикладные задачи нелинейного анализа.

М.: ВЦ РАН, 2007. С. 31 61.

8. Ерина М. Ю. Об устойчивости определяющих систем для особых решений нелиней ных уравнений // Теоретические и прикладные задачи нелинейного анализа. М.: ВЦ РАН, 2007. С. 18 30.

9. Ерина М. Ю., Измаилов А. Ф. Определяющие системы и ньютоновские методы для отыскания особых решений нелинейных краевых задач // ЖВМ и МФ. 2007.

Т. 47, № 9. С. 1467 1485.



 

Похожие работы:





 
2013 www.netess.ru - «Бесплатная библиотека авторефератов кандидатских и докторских диссертаций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.