Ньютоновские методы поиска особых решений нелинейных уравнений тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

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

Ерина Мария Юрьевна

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

01 01 09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 2007

003164398

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

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

Официальные оппоненты доктор физико-математических наук,

профессор Жадан Виталий Григорьевич,

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

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

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

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

С текстом автореферата можно ознакомиться на официальном сайте факультета ВМиК Московского государственного университета им М В Ломоносова http //www es msu su в разделе «Наука» - «Работа диссертационных советов» - «Д 501 001 44»

Автореферат разослан « jÜ- » января 2008 г

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

H П Трифонов

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

Актуальность темы. Еще в 70-е годы Х1Х-го века было установлено (Е Schroder), что метод Ньютона обладает лишь линейной скоростью сходимости к кратному корню одного скалярного уравнения с одной неизвестной Квадратичная скорость сходимости может быть восстановлена путем домножения стандартного шага метода на кратность корня Первая попытка обощить эти результаты на мпогомерный случай была сделана в 60-е годы ХХ-го века (L В Rail) В свою очередь, эта работа инициировала целый ряд публикаций (D W Decker, А О Griewank, С Т Kelley, Н В Keller, G W Reddien) Итогом этих исследований стало следующее утверждение в лучшем случае удается гарантировать линейную скорость сходимости метода Ньютона к особому решению, и, кроме того, начальное приближение недостаточно выбирать просто близким к исходному решению (множество подходящих начальных приближений может не содержать окрестности точного решения, хотя это множество, как правило, в определенном смысле «плотно»)

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

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

В настоящее время доминирующим в области численного отыскания особых решений представляется другой подход, связанный с построением так называемых расширенных (еще говорят — определяющих) систем Этот подход был предложен в 70-е годы ХХ-го века (R Seydel, Н Weber, W Werner, G Moore, A Spence), однако, идея настолько естественна, что, возможно, она появлялась независимо и в дру! их работах Идея состоит в том, чтобы включить исходпое уравнение в семейство уравнений, зависящее от некоторых дополнительных переменных (параметров) таким образом, чтобы оператор новой системы имел сюръективную производную в соответствующем решении Этот первый этап называется раскладыванием («unfolding») особенности Второй этап, называемый иногда сечением («cut»), состоит в нахождении дополнительных уравнений, делающих расширенную систему квадратной, причем так, чтобы искомому особому решению соответствовало регулярное (в определенном выше смысле) решение получаемой расширенной системы Тогда это решение можно искать любым традиционным численным методом (например, методами ньютоновского типа)

Среди недавних исследований по численным методам поиска особых решений отметим разработки как зарубежных (Е L Allgower, К Böhmer, W Govaerts, , М Hermann, А Ноу, V Janovsky, Р Kunkel, W Middelman), так и отечественных (OA Брежнева, А Ф Измаилов, А А Третьяков, А Хмура) авторов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

F(x) = 0, (1)

где F О —> Elm — дважды непрерывно дифференцируемое отображение, О С ГО" — открытое множество, п>тп Решение х е О уравнения (1) называется особым, если

rankF'(x) < т

или, другими словами,

г — corankF'(i) > 0

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

Структуру особенности F в точке х, а точнее, структуру образа F'(x), можно описать матричным уравнением

PF\x) = 0, (2)

где Р £ lRmxm — проектор на некоторое прямое дополнение Vj подпространства У1 = im F'(x) в IRm параллельно Yi Точка х удовлетворяет (2), но, во-первых, Р в общем случае не может быть известно точно (без знания искомого х), а во-вторых, система (2) содержит слишком много уравнений Поэтому, во-первых, Р в (2) следует заменить некоторой его аппроксимацией Р О —► IRmxm (подразумевается, что Р(х) = Р), а во-вторых следует оставить в системе

F(x) = 0, P(x)F'(x) = 0 (3)

лишь «существенную часть» второго уравнения

Все известные па сегодня способы выбора проектора Р() предполагают знание коран-га особенности г Иногда г может быть известно из анализа, являющегося внешним по отношению к описываемому подходу С другой стороны, г может рассматриваться как параметр с конечным числом возможных значений Наконец, известны регулярные процедуры для опредечения г, предполагающие, что известна точка в IR™ достаточно близкая к х (такая точка нужна в любом случае, поскольку речь идет о локальных методах ньютоновского типа)

Раздел 111 посвящен описанию двух способов реализации отображения Р(), на основе которых конструируется определяющая система вида

Ф(х) = 0, (4)

где Ф О -+ И1" х _ гладкое отображение

Один из способов выбора Р{) заключается в следующем Зафиксируем матрицы А 6

jpjnx(n-m+r) иВе Emxr ^^ 4TQ

И" = ker F'(x) © ker Лт, IRm = imf(i) © imB (5)

Эти условия подразумевают, в частности, что

т8&кА = п — тп + г, rank В = т Тогда существует единственная пара матриц К € и Се Щ,™*'' такая, что

F'{x)K = 0, Лт К = bVm+r, {F\x))TC = О, ВТС = Er

Столбцы К и С образуют базисы kerF'(x) и (lrnffi))1 соответственно Проектор на Уг параллельно Yi в IRm задается формулой

Р = ВСТ

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

F'(x)K-BT = 0, ATK = En-m+r, (6)

(F(x))TC — АТт = О, ВТС = ЕГ (7)

относительно неизвестных {К, С, Т) е ]R"x("-m+r) х lRm*r х IRrx(n'm+r), х е О играет здесь роль параметра Используя теорему о малом возмущении обратимого оператора, получаем, что в сделанных предположениях существуют непрерывно дифференцируемые отображения К{) О - H"x("-m+r), С() О IRmxr и Т{) О - lRr><(n-m+r) такие, что

К(х) = К, С(х) = С, Т(х) = О

Аппроксимация Р() выбирается следующим образом для х £ О

Р(х) = В(С(х))т

Тогда согласно (7)

P(x)F'(х) = В(С(х))тР'(х) = ВТ(х)Ат V* € О

Введем отображение Ф О —> ]Rm х IRrx(n~m+r),

Ф(х) = (F(x), Т(х)) = (F(x), Ti(®), , Гг(х)), (8)

где через Т,(г) обозначена г-я строка матрицы Т(х) , i = 1, , г Пусть е? — векторы стандартного базиса в И", 7 = 1, , п Введенное отображение Ф непрерывно дифференцируемо на О, причем для вычисления производной этого отображения можно использовать следующую формулу для всякого х € О

ВДе* = ((С(х))т№)И)ВД„ г = 1, , г, j = 1, ,п (9)

Отметим также, что для вычисления производной Т можно воспользоваться явной формулой

= (F"(X)[K']fC, 6

где К1 к С - столбцы матриц К(х) и С(х) соответственно, » = 1, ,г, , п

Следующее предложение дает необходимое и достаточное условие того, что

кегФ'(х) = {0} (10)

(что равносильно невырожденности матрицы (Ф'(х))тФ'(х)) и, в частности, х является изолированным решением уравнения (4)

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

{£ 6 кег^'(х) | х] е илГ(х) Ух е кегГ(х)} = {0} (11)

Условие (11) известно как условие невырожденности второго дифференциала Система (4) при г > 0, по-прежнему, является переопределенной Общий оператор выбора - это отображение Щ) ИГ -» £(1ЕГ х игх(п-т+г', Ж") Задав это отображение, от системы (4) переходим к системе

7г(х)Ф(х) = 0 (12)

В разделе 112 описываются две конкретные реализации оператора выбора, которые представляются наиболее естественными

1) Щ ) = К, где И € £(Ит х и") _ фиксированный (постоянный) опергъ тор,

2) П ) = (Ф'( ))т

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

КФ '{хк){хк+1-хк) = -ПФхк (13)

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

Для второго способа задания Щ ) итерация метода Ньютона для уравнения (12) имеет вид

(Ф"(**)[**+1 - х^])тФ(х":) + (Ф'^^Ф'^Хх*« - хк) = -(Ф'{хк))ТЩхк), и может быть заменена своей неточной версией без ущерба для скорости сходимости

(Ф'(х*))ТФ'(**)(®*+1 -хк) = -(Ф'(х*))тФ(х*),

что соответствует методу Гаусса—Ньютона для уравнения (4) Данная модификация позволяет избежать необходимости вычислять вторые производные Ф Для введенного в (8) отображения Ф эта формула принимает вид

(^(х*))Мх*) + £(7Г(х*)№^ (Xм - хк) =

= - ^'(х*))^(х*) + ¿гах^ГДх')^ (14)

Из предложения 1 и стандартного результата о локальной сверхлинейной сходимости метода Гаусса-Ньютона вытекает

Теорема 1. Пусть в решении х уравнения (1) выполнено условие (11) невырожденности второго дифференциала

Тогда если матрицы А и В удовлетворяют условию (5), а начальное приближение х° € И" достаточно близко к х, то итерационный процесс (14) корректно определяет траекторию {х*}, которая сходится к х со сверхлинейной скоростью

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

В разделе 1 2 предлагаются конструктивные способы идентификации коранга особенности г и выбора матриц А и В, необходимых для реализации описанного подхода, по имеющемуся начальному приближению х° € Ж" Эти способы основаны на оценке расстояния до решения при выполнении условия 2-регулярности

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

F^x) = U(x)Z(x){V(x))T,

где E(i) е К.™*" - диагональная матрица, на диагонали которой стоят сингулярные числа £г,(х), г = 1, , ш, ^(х) > (72{х) > > ат{х) > 0, U(x) е Hmxm и V(x) S ]RnXB -ортогональные матрицы

Положим

ф°) = т - тах{г = 1, , т | <7,(х°) > ||F(x°)||e''2} (15)

Далее, считая коранг г определенным, столбцы матрицы А и 6' матрицы В зададим следующим образом

a? = v3(x°), ] =т — г + 1, , га, Ь'= и'(х°), г ~ т — г + 1, , т, (16)

где для всякого х 6 О через и'(х), г = 1, , т, и v1(x), j = 1, , п, обозначены столбцы матриц U и V соответственно

Предложение 2. Пусть в решении х уравнения (1) выполнено

е ker F'(x) I F»(2)[f, i] € imf(x)} = {0} (17)

Тогда если начальное приближение х° е И" достаточно близкб к х, то число г = г(х°), определяемое согласно (15), совпадает с corankF'(x), а матрицы А и В, столбцы которых определяются согласно (16), удовлетворяют условию (5)

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

Алгоритм N08

1 Выбираем вариант А или Б алгоритма В случае варианта А, выбираем И е £(Цтх Пггх(""т+г', т.")

2 Фиксируем в е (О, 1) Полагаем к = 0 и выбираем х° € И"

3 Вычисляем сингулярное разложение /•"(х0) и определяем число г = г(х°) согласно (15) Задаем матрицы А 6 И"х("-т+г) и В е Итхг со столбцами определяемыми согласно

4. Решая матричные линейные системы (6), (7), вычисляем матрицы К(хк), С(хк) и

5. Вычисляем матрицы Х|'(х), г = 1, , г, по формулам (9)

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

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

Тогда если начальное приближение х° б Ж" достаточно близкд к х, то вариант Б алгоритма корректно определяет траекторию {хк}, которая сходится кх со сверхлинейной скоростью

Аналогичное утверждение имеет место и для варианта А алгоритма N08, с той только разницей, что оно будет верно для почти любого "Я е £(Ш,т х ИГ*("-т+г)) Ц")

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

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

В разделе 2 1 рассматривается краевая задача

где / П1 х Ип —» К" и д И" х ГО" —> И.™ — заданные отображения Пусть § — открытое множество вКх И" Введем множества

Отображение / непрерывно и дважды непрерывно дифференцируемо по второй переменной на а д дважды непрерывно дифференцируемо на {7о х Ог Пусть, наконец, х() 6 СД[0, 1] — решение задачи (18), (19), график которого ¡*гарЬх = {(¿, х(4)) | I е [О, 1]} содержится в в

Решение х() задачи (18), (19) естественно назвать особым, если вырождена матрица

(16)

Т(х*)

х = /(«, х), 4 е [о, 1], г(х(о), х(1)) = о,

(18) (19)

а1о,1] = еп([о, 1]хив), д0 = {хе (О, х) е д}, 51 = {х е ЕГ| (1, X) е д}

*! = х(4))Фь Ф1(0) = Еп

(20)

В разделе 211 речь идет о редукции краевых задач для обыкновенных дифференциальных уравнений к конечномерным системам уравнений Применяя к уравнению (18) теорему о дифференцируемой зависимости решения от начальных условий и теорему единственности, получаем следущее найдется окрестность О точки ¿(0) в Ж" и гладкое <р [0, 1] х О -> К"

V = /(*■ ¥>). (22)

¥>(0) = х (23)

Тогда Vi е [0, 1]

причем Vz € О, V£ е И"

<p(t, í(0)) = x(t),

g(í, x) = 4-1 (í, x), |j(í, я){ = «a(í, x, O,

где , x) [0, 1] —»]R"X" — фундаментальная матрица линеаризованного на функции <р( i х) уравнения (18), те решение матричной начальной задачи (20), (21), а Ф2( > £) [0, 1] —> IR,nxn — решение матричной начальной задачи

= + «6 [0,1], (24)

Ф2(0) = 0 (25)

Введем отображение

F О —> И", F(x) = д(х, V(l, х)) Краевая задача (18), (19) сводится к конечномерной системе (1) с таким оператором F

Предложение 3. В сделанных предположениях отображение F удовлетворяет в точке х условию невырожденности второго дифференциала (11) тогда и только тогда, когда

£ € ker F1

f(s, £(!))[(£> ЫШ (*. ^С1)*)] +

+ ^¡■(2, £(1))Ф2(1,Оге1т^1У*екег.р} ={0},

где ф{) — <р{, х), Ф2(, £) = ! х, О Кроме того, отображение ^ удовлетворяет в точке х условию (17) тогда и только тогда, когда

£ GkerF1

g"(x, <?(!))[(£, ФгШ, (Í, Ф,(1)С)] +

Раздел 212 посвящен применению к краевым задачам алгоритмов, описанных в главе 1 Реализация данных алгоритмов требует решения на каждой итерации вспомогательных матричных начальных задач (22), (23), (20), (21) и (24), (25) Последнее же, разумеется, делается приближенно, что приводит к необходимости принимать во внимание неизбежную неточность вычисления значений и производных отображения Р Рассматривается случай, когда для решения вспомогательных начальных задач используется

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

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

К важнейшим типам особеппостей отображений бесконечномерных пространств относится так называемая «фредгольмова вырожденность» Пусть X — банахово пространство, О — окрестность точки х в X, отображение F О —» X дважды непрерывно дифференцируемо на О, причем его производная F'(x) является фредголъмовым оператором, те подпространство imf(i) замкнуто и

dimkerF'(i) = dimker(F'(z))* = г

при некотором (конечном) г

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

F(x) = х() — f1 f( ,т, х(т)) dr, х()еХ, J о

где / ExEx Em —> И"1 — гладкое отображение, в качестве пространста X в данном случае можно взять Cm[0, 1] или ¿2,т[0, 1] В случае фредгольмова F'(x), решение х уравнения

F{x) = О

является особым, если г > О

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

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

Раздел 2 2 2 содержит обобщение на случай фредгольмовых производных конечномерного подхода поиска особых решений нелинейных уравнений, рассмотренного в главе 1 Структуру особенности F в точке х, а точнее, структуру образа F'(x) можно описать уравнением

PF'{x) = О,

где Р X —> X — (непрерывный) проектор на (г-мерное) прямое дополнение подпространства 1 mF'(x) в X параллельно imF'(x) Заменяя Р некоторой его аппроксимацией Р О —+ С(Х, X) (подразумевается, что Р{х) = Р), получаем систему уравнений

F(x) = 0, Р(х)? (х) = О

Считая г известным, зафиксируем линейно независимые наборы а1, , аг 6 X и а*, , а' € X* такие, что

imF'(x)nlm{a\ , ог} = {0}, im(F'(x) ) * П lm{aj, , а'г } = {0}

Чтобы аппроксимировать х1, , хг и xj, , х* рассмотрим следующие линейные системы

.=1, , г,

J=1

(а*, хг) = 5,J, г, 3 = 1, ,г,

Г

(Пг))*хГ-£тча; = о, » = 1, ,г,

3-1

(х',а3)=5,j, I, з = 1, ,г

относительно неизвестных , хг 6 XÏ> i Xr S X* и Г е IRrxr, где х 6 О играет

роль параметра

Определяющая система имеет вид

Ф(х) = 0, (26)

где Ф О —> X х Игхг,

Ф(х) = (F(x), Т(х)) (27)

Явная формула для производной Т

ВД = (F" (х) [xJ (х) ] ) * х* (х), 1,3 = 1, , Г

Следующее предложение является естественным обобщением предложения 1 для конечномерного случая, описанного в разделе 11 1, и дает необходимое и достаточное условие того, что

кегФ'(х) = {0} (28)

и, в частности, что х является изолированным решением уравнения (26)

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

{£ е kerF'(x) | F"(x)[£, х] 6 imF'(x) Vx е kerF'(x)} = {0}

Если использовать базисы xl, , хг в kerF'(x) и xj, , х* в ker(Fv(x))*, то это условие можно записать в виде

ja 6 Иг J2 **]> = 0 Vi, з = 1, , г| = {0}

Иными словами, это условие линейной независимости матриц

Л, = ((х,*, ^[¡Е», **]»,.,=1, ,г> *!=1, ,Г

Далее, распространяя описанный в главе 1 подход с использованием оператора выбора, получаем следующее если оператор выбора имеет вид И 6 С(Х х Нг*г, X),

г

Т) =£ + { е жп, т е 1ГХГ, (29)

>=1

где 2 £ £(ИГХГ, ПГ), то тогда итерация метода Ньютона для системы 71Ф(х) = 0 принимает вид

г

Р'(хк)(хк+1 - х*) + £(д(Т'(х*)(х*+1 - х*))),а' = 1=1

1=1

Для данного метода получены результаты о сходимости, аналогичные результатам, полученным в главе 1

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

Рассматривается уравнение (1), где Р О —» И"1 — гладкое отображение, О С И" — открытое множество, п>тп Предполагается, что отображение Р дифференцируемо (но не обязательно дважды дифференцируемо) на О

Пусть т]1, , г)т — ортонормированный базис в подпространстве (нп-Г^х))-1- = кег(.Р(х))т Тогда точка х удовлетворяет системе уравнений

^(х) = 0, (^(х)УУ = 0, 5 = 1, , г (30)

Зададим оператор выбора, те линейный оператор % = (Я0, Л1, , 1С) Ит х 08=1 ~* и вместо переопределенной (в случае, когда х — особое решение уравнения (1)) системы (30) введем уравнение

Фя(х) = 0,

где отображение Ф^ О —» И" задается формулой

Фл(х) = К(Р(х), (Р'(х))тг?\ , (Р"(х))тг)г) = г ( (г,'Р(х), Щ)

.-1 V МП*), щ.)

(через Щ обозначена ]-я строка матрицы Я', 3=1, , г, у = 1, , п)

Пусть каждое из отображений х —> т}'Р{х) О —» И", я = 1, , г, дифференцируемо в любой точке множества О по любому направлению в И" Тогда итерация ньютоновского метода примет вид

/ Г { {п°Р'У(х\ Щ) \\

+ £ (х*+1-х') =

В разделе 3 2 данный метод реализуется для гладких переформулировок нелинейных комплементарных задач (ИСР)

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

найти хбПГ такой, что

в{х) >0, х > 0, (<?(х), х) = 0, (31)

где С И" —> Ж" — гладкое отображение Множество решений МСР (31) совпадает с множеством решений уравнения (1), где Р И" —» Ип имеет компоненты

Р,(ж) = 2<3,(х)х, - (тт{0, в^х) + х,})2, 1=1, ,п

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

А именно, пусть х - решение МСР (31) Предположим, что отображение С? дважды непрерывно дифференцируемо в некоторой окрестности точки х Тогда отображение Г имеет вблизи х производную, которая удовлетворяет условию Липшица, причем для любого х из этой окрестности справедливы равенства

Р;(х) = 2(х,в',(х) + в,(хУ - тт{0, <3,(х) + х.^С^х) + е')), (32)

г = 1, ,п

В частности,

!0, если г € /о,

х,С,(х), если г € 1и » = 1, , п, 0,(х)е', если г € /г, где используются множества индексов

1о = /о(2) = {» = 1, , п | С,(х) = 0, х, = 0},

Д = Д(2) = {| = 1, , п | в,(х) = 0, х, > 0},

/2 = 12(х) = {1 = 1, , п | в,{х) > 0, х, = 0}

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

ае^ж) = 0,

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

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

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

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1 Измаилов А Ф , Штуца M Ю Класс ньютоновских методов для отыскания особых решений нелинейных уравнений при ослабленных требованиях гладкости // Теоретические и прикладные задачи нелинейного анализа — M ВЦ РАН, 2005 — С 62—75

2 Измаилов А Ф , Штуца M Ю Класс ньютоновских методов для нелинейных комплементарных задач // Теоретические и прикладные задачи нелинейного анализа — M ВЦ РАН, 2006 - С 3-22

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

4 Ерина M Ю Ньютоновские методы для отыскания особых решений систем нелинейных уравнений // Тез докл XIV Международная конференция студентов, аспирантов и молодых ученых "Ломоносов", секция "Вычислительная математика и кибернетика" — M Издательский отдел факультета ВМиК МГУ, 2007 — С 25

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

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

7 Ерина M Ю, Измаилов А Ф Определяющие системы для уравнений с фредгольмо-выми производными // Теоретические и прикладные задачи нелинейного анализа — M ВЦ РАН, 2007 - С 31-61

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

9 Ерина M Ю , Измаилов А Ф Определяющие системы и ньютоновские методы для отыскания особых решений нелинейных краевых задач // ЖВМ и МФ — 2007 — Т 47, № 9 - С 1467-1485

Напечатано с готового оригинал-макета

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01 12 99 г Подписано к печати 23 10 2007 г Формат 60x90 1/16 Услпечл 1,0 Тираж 100 экз Заказ 544 Тел 939-3890 Тел /Факс 939-3891 119992, ГСП-2, Москва, Ленинские горы, МГУ им М В Ломоносова, 2-й учебный корпус, 627 к

Введение

Основные обозначения

1 Определяющие системы

1.1 Построение определяющих систем и ньютоновские методы.

1.1.1 Способы выбора проектора.

1.1.2 Ньютоновские методы.

1.2 Реализуемые алгоритмы

1.3 Устойчивость.

2 Краевые задачи и уравнения с фредгольмовыми производными

2.1 Нелинейные краевые задачи.

2.1.1 Конечномерная редукция.^.

2.1.2 Реализация для краевых задач

2.2 Уравнения с фредгольмовыми производными.

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

2.2.2 Построение определяющей системы.

3 Уравнения с ограниченной гладкостью и комплементарные задачи

3.1 Уравнения с липшицевой первой производной.

3.1.1 Построение определяющей системы.

3.1.2 Метод Ньютона в ослабленных требованиях гладкости.

3.2 Нелинейные комплементарные задачи

3.2.1 Метод Ньютона для NCP.

3.2.2 Условия регулярности.

В данной диссертационной работе изучаются особые решения нелинейного уравнения

F(x) = 0, (1) где F : О —> IRm — обладающее определенной гладкостью отображение, О С Ж" — открытое множество, п>т. Решение х Е О уравнения (1) называется особым, если rank F'(x) < т, или, другими словами, г = corank F'(x) > 0.

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

Важнейшие приложения, в связи с которыми появляется необходимость анализа и численного отыскания особых решений, возникают, скажем, в теории бифуркаций (см., например, обзор в [55]), а также в оптимизации, включая комплементарные и связанные с ними задачи [50], [18].

По всей видимости, началом исследований по проблематике особых решений и численных методов их отыскания можно считать работу [63], в которой было установлено, что метод Ньютона обладает лишь линейной скоростью сходимости к кратному корню одного скалярного уравнения с одной неизвестной (n = 1), но квадратичную скорость сходимости можно восстановить домножением стандартного шага метода на кратность корня.

Внимание к этой проблематике было привлечено вновь в [59], где была сделана первая попытка обобщить результаты из [63] на многомерный случай. В свою очередь, работа [59] инициировала целый ряд публикаций [61], [33], [60], [35], [36], [44], [34], [37], [38], [45], где детально исследовалось поведение методов ньютоновского типа в окрестности особого решения (см. также обзор в [43]). Итог этих исследований можно подвести следующим утверждением: в лучшем случае удается гарантировать линейную скорость сходимости метода Ньютона к особому решению, и, кроме того, начальное приближение не достаточно выбирать просто близким к искомому решению (множество подходящих начальных приближений может не содержать окрестности точного решения, хотя это множество, как правило, в определенном смысле «плотно»; см. [44], [43]). Отыскание особых решений связано с еще одной известной трудностью — возможной неустойчивостью таких решений по отношению к возмущениям отображения F [18], а также неустойчивостью процессов ньютоновского типа к вычислительным ошибкам вблизи таких решений [43].

В этом контексте был предложен ряд модификаций метода Ньютона, направленных на восстановление присущей ему высокой скорости сходимости (см. обзоры в [38] и [43]). Эти модификации базируются на сочетании многошаговых вариантов метода Ньютона с основной идеей работы [63] (то есть, с удлинением шага). Однако, такие модификации не позволяют преодолеть остальные трудности, упомянутые выше. Кроме того, условия, используемые для обоснования этих модификаций, весьма ограничительные: эти условия могут выполняться лишь при г < 2 [38]. Аналогичные трудности возникают в связи с так называемыми тензорными методами [62], [40]: по-видимому, обоснованные реализации последних известны только для г < 1.

В настоящее время доминирующим в области численного отыскания особых решений представляется другой подход, связанный с построением так называемых расширенных (еще говорят — определяющих) систем. Этот подход впервые был предложен в работах [64], [66], [56], однако, идея настолько естественна, что, возможно, она появлялась независимо и в других работах. Идея состоит в том, чтобы включить уравнение (1) в семейство уравнений, зависящее от некоторых дополнительных переменных (параметров) таким образом, чтобы оператор новой системы имел сюръективную производную в соответствующем решении. Этот первый этап называется раскладыванием («unfolding») особенности. Второй этап, называемый иногда сечением («cut»), состоит в нахождении дополнительных уравнений, делающих расширенную систему квадратной, причем так, чтобы искомому особому решению соответствовало регулярное (в определенном выше смысле) решение получаемой расширенной системы. Тогда это решение можно искать любым традиционным численным методом (например, методами ньютоновского типа).

В первых публикациях, посвященных подходу «unfolding-cut», рассматривался только случай г — 1. Подход получил дальнейшее развитие в работах [43], [68], [54],

46], [67], [49], [30], [47], где главное внимание уделялось ослаблению ограничений на г, а также получению расширенных систем как можно меньшего размера. Нужно особо отметить работу [58], в которой была предложена минимально расширенная определяющая система для произвольного г, а также работы [41], где делается попытка подведения идеологической базы под «unfolding-cut», и [28], содержащую фундаментальное изложение данного подхода и его реализаций. Среди недавних публикаций отметим [42], [7], [48], [29].

Заметим, что реализация обоих этапов подхода «unfolding-cut» требует определенной информированности о структуре особенности. Минимальным из таких требований является знание числа г. Это можно интерпретировать следующим образом: ищется не просто решение уравнения (1), и даже не просто особое решение, а особое решение заданного коранга. С другой стороны, существуют способы определения г без точного знания ж (см. [58], [28], [18, п. 3.1.3] и раздел 1.2 данной работы).

Основным недостатком подхода «unfolding-cut» является то, что размер системы уравнений, которую нужно решать, неизбежно увеличивается. В определенном смысле этот недостаток был преодолен в [29], за счет выделения ньютоновских итераций по исходной переменной.

Общий подход к построению (действительно) минимально расширенных определяющих систем был предложен в [6], где также был предложен один из вариантов реализации указанного подхода, приводящий к явным формулам для итерационной матрицы метода Ньютона, применяемого к определяющей системе. Эта реализация обобщает конструкции из работ [16], [14], которые, в свою очередь, использовали идею так называемого 2-факторметода [4], [17]. Получаемое на этом пути регуляризованное уравнение (определяющая система) имеет ту же размерность, что и исходное уравнение (1).

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

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

Структуру особенности F в точке х, а точнее, структуру образа F'(x), можно описать матричным уравнением

PF'(x) = 0, (2) где Р е Итхтп — проектор на некоторое прямое дополнение У2 подпространства Yi — imF'(x) в Ит параллельно Y\. Заметим, что такое описание в определенном смысле оптимально: оно полное, и не приводит к необходимости введения дополнительных переменных. Точка х удовлетворяет (2), но, во-первых, Р в общем случае не может быть известно точно (без знания искомого х), а во-вторых, система (2) содержит слишком много уравнений. Поэтому, во-первых, Р в (2) следует заменить некоторой его аппроксимацией Р : О —> IRmxm (подразумевается, что Р{х) = Р), а во-вторых, следует организовать выбор нужного числа, а именно п уравнений из системы

F{x) = 0, P(x)F'(x) = 0, (3) возможно, допуская «перемешивание» этих уравнений. Если аппроксимация Р(х) зависит от х € О гладким образом, то к получаемой таким образом системе можно применять метод Ньютона. Такой подход был реализован в [6].

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

Заключение

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

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

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

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

1. Алексеев В. М., Тихомиров В. М., Фомин С. В. Оптимальное управление. — М.: Наука, 1979.

2. Банах С. Теория линейных операций. — Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001.

3. Бахвалов Н. С., Жидков Н. П., Кобельков Г. М. Численные методы. — М.: Наука, 1987.

4. Белаги К. Н., Третьяков А. А. Методы решения вырожденных задач // ЖВМ и МФ. 1988. - Т. 28, № 7. - С. 1097-1102.

5. Беллман Р., Калаба Р. Квазилинеаризация и нелинейные краевые задачи. — М.: Мир, 1968.

6. Брежнева О. А., Измаилов А. Ф. О построении определяющих систем для отыскания особых решений нелинейных уравнений // ЖВМ и МФ. — 2002. — Т. 42, № 1. С. 10-22.

7. Брежнева О. А., Измаилов А, Ф., Третьяков А. А., Хмура А. Один подход к поиску особых решений системы нелинейных уравнений общего вида // ЖВМ и МФ. 2000. - Т. 40, № 3. - С. 365-377.

8. Дарьина А. И., Измаилов А. Ф., Солодов М. В. Смешанные комплементарные задачи: регулярность, оценки расстояния до решения и ньютоновские методы // ЖВМ и МФ. 2004. - Т. 44, № 1. - С. 51-69.

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

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

11. Ерина М. Ю., Измаилов А. Ф. Определяющие системы для уравнений с фредгольмовыми производными // Теоретические и прикладные задачи нелинейного анализа. М.: ВЦ РАН, 2007. - С. 31-61.

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

13. Измаилов А. Ф. Об одном классе определяющих систем для особых решений нелинейных уравнений // Вопросы моделирования и анализа в задачах принятия решений. М.: ВЦ РАН, 2002. - С. 18-57.

14. Измаилов А. Ф. Устойчивые методы для отыскания 2-регулярных решений нелинейных операторных уравнений // ЖВМ и МФ. — 1996. — Т. 36, № 9. — С. 22—24.

15. Измаилов А. Ф., Солодов М. В. Численные методы оптимизации. — М.: Физмат-лит, 2003.

16. Измаилов А. Ф., Третьяков А. А. О локальной регуляризации некоторых классов нелинейных операторных уравнений // ЖВМ и МФ. — 1996. — Т. 36, № 7. — С. 15-29.

17. Измаилов А. Ф., Третьяков А. А. Факторанализ нелинейных отображений. — М.: Наука, 1994.

18. Измаилов А. Ф., Третьяков А. А. 2-регулярные решения нелинейных задач. Теория и численные методы. — М.: Физматлит, 1999.

19. Измаилов А. Ф., Штуца М. Ю. Класс ньютоновских методов для нелинейных комплементарных задач // Теоретические и прикладные задачи нелинейного анализа. М.: ВЦ РАН, 2006. - С. 3-22.

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

21. Теоретические и прикладные задачи нелинейного анализа. — М.: ВЦ РАН, 2005.- С. 62-75.

22. Иоффе А. Д., Тихомиров В. М. Теория экстремальных задач. — М.: Наука, 1974.

23. Kamo Т. Теория возмущений линейных операторов. — М.: Мир, 1972.

24. Кларк Ф. Оптимизация и негладкий анализ. — М.: Наука, 1988.

25. Лоусон Ч., Хенсон Р. Численное решение задач метода наименьших квадратов.1. М.: Наука, 1986.

26. Ортега Дж., Рейнболдт В. Итерационные методы решения нелинейных систем уравнений со многими неизвестными. — М.: Мир, 1975.

27. Пресдорф 3. Некоторые классы сингулярных уравнений. — М.: Мир, 1979.

28. Треногин В. А. Функциональный анализ. — М.: Наука, 1980.

29. Allgower Е. L., Bohmer К. Resolving singular nonlinear equations // Rocky Mountain J. Math. 1988. - V. 18. - P. 225-268.

30. Allgower E. L., Bohmer K., Hoy A., Janovsky V. Direct methods for solving singular nonlinear equations // Z. Angew. Math. Mech. 1999. - V. 79. - P. 219-231.

31. Bohmer K., Zhen M. Regularization and computation of bifurcation problrms with corank 2 // Computing. 1989. - V. 41. - P. 307-316.

32. Chandrasekhar S. Radiative transfer. — New York: Dover, 1960.

33. Daryina A. N., Izmailov A. F., Solodov M. V. A class of active-set Newton methods for mixed complementarity problems // SIAM J. Optim. — 2004. — V. 15, № 2. — P. 409-429.

34. Decker D. W., Kelley С. T. Broyden's method for a class of problems having singular Jacobian at the root I I SIAM J. Numer. Anal. 1985. - V. 22. - P. 566-574.

35. Decker D. W., Kelley С. T. Convergence acceleration for Newton's method at singular points // SIAM J. Numer. Anal. 1982. - V. 19. - P. 219-229.

36. Decker D. W., Kelley С. T. Newton's method at singular points. I // SIAM J. Numer. Anal. 1980. - V. 17, № 1. - P. 66-71.

37. Decker D. W., Kelley С. T. Newton's method at singular points. II // SIAM J. Numer. Anal. 1980. - V. 17, № 3. - P. 465-471.

38. Decker D. W., Kelley С. T. Sublinear convergence of the chord method at singular points // Numer. Math. 1983. - V. 42. - P. 147-154.

39. Decker D. W., Keller H. В., Kelley С. T. Convergence rates for Newton's method at singular points // SIAM J. Numer. Anal. 1983. - V. 20, № 2. - P. 296-314.

40. Facchinei F., Pang J. S. Finite-dimensional variational inequalities and complementarity problems. — N.Y.: Springer, 2003.

41. Feng D., Frank P. D., Schnabel R. B. Local convergence analysis of tensor methods for nonlinear equations // Math. Progr. — 1993. — V. 62. — P. 427—459.

42. Fink J. P., Rheinboldt W. C. A geometric framework for the numerical study of singular points // SIAM J. Numer. Anal. 1987. - V. 24. - P. 618-633.

43. Govaerts W. Computation of singularities in large nonlinear systems // SIAM J. Numer. Anal. 1997. - V. 34. - P. 867-880.

44. Griewank A. O. On solving nonlinear equations with simple singularities or nearly singular solutions // SIAM Rev. 1985. - V. 27. - P. 537-563.

45. Griewank A. O. Starlike domains of convergence for Newton's method at singularities // Numer. Math. 1980. - V. 35. - P. 95-111.

46. Griewank A. O., Osborne M. R. Analysis of Newton's method at irregular singularities I I SIAM J. Numer. Anal. 1983. - V. 20, № 4. - P. 747-773.

47. Griewank A. 0., Reddien G. W. Characterization and computation of generalized turning points // SIAM J. Numer. Anal. 1984. - V. 21. - P. 176-185.

48. Griewank A. O., Reddien G. W. The aproximate solution of defining equations for generalized turning points // SIAM Л. Numer. Anal. 1996. - V. 33. - P. 1912-1920.

49. Hermann М., Kunkel P., Middelman W. Augmented systems for computation of singular points in Banach space problems // Z. Angew. Math. Mech. — 1998. — V. 78.- P. 39-50.

50. Hoy A. A relation between Newton and Gauss-Newton steps for singular nonlinear equations // Computing. 1988. - V. 40. - P. 19-27.

51. Izmailov A. F., Solodov M. V. Error bounds for 2-regular mappings with lipschitzian derivatives and their applications // Math. Program. — 2001. — V. 89, № 3. — P. 413-435.

52. Izmailov A. F., Solodov M. V. Error bounds for 2-regular mappings with Lipschitzian derivatives and their applications: Technical Report B-125. — Rio de Janeiro, Instituto de Matematica Рига e Aplicada, 2000.

53. Izmailov A. F., Solodov M. V. Superlinearly convergent algorithms for solving singular equations and smooth reformulations of complementarity problems // SIAM J. Optim.- 2002. V. 13, № 2. - P. 386-405.

54. Keller H. B. Numerical methods for two-point boundary value problems. — Waltham: Blaisdell, 1968.

55. Kunkel P. A tree-based analysis of a family of augmented systems for the computation of singular points // IMA J. Numer. Anal. 1996. - V. 16. - P. 501-527.

56. Mittelman H. D., Weber H. Numerical methods for bifurcation problems — a survey and classification // Bifurcation Problems and their Numerical Solution. ISNM 54. Basel, Boston, Birkhauser. — 1980. — P. 1—45.

57. Moore G., Spence A. The calculation of turning points of nonlinear equations // SIAM J. Numer. Anal. 1980. - V. 17. - P. 567-576.

58. Qi L., Sun J. A nonsmooth version of Newton's method // Math. Program. — 1993.- V. 58. P. 353-367.

59. Rabier P. J., Reddien G. W. Characterization and computation of singular points with maximum rank deficiency // SIAM J. Numer. Anal. 1986. - V. 23. - P. 1040-1051.1. Литература 103

60. Rail L. В. Convergence of Newton's process to multiple solutions // Numer. Math. — 1966. V. 9, № 1. - P. 23-37.

61. Reddien G. W. Newton's method and high order singularities // Computers and Math, with Applic. 1979. - V. 5, № 2. - P. 79-86.

62. Reddien G. W. On Newton's method for singular problems // SIAM J. Numer. Anal. 1978. - V. 15, № 5. - P. 993-996.

63. Schnabel R. В., Frank P. D. Tensor methods for nonlinear equations // SIAM J. Numer. Anal. 1984. - V. 21. - P. 815-843.

64. Schroder E. Uber unendlich viele algoritmen zur auflosung der gleichungen // Math. Annalen. 1870. - V. 2. - P. 317-365.

65. Seydel R. Numerical computation of branch points in ordinary differential equations // Numer. Math. 1979. - V. 32, № 1. - P. 51-68.

66. Test examples of systems of nonlinear equations. Version 3-90. — Tallin: Estonian Softweare and Computer Service Company, 1990.

67. Weber H., Werner W. On the accurate determination of nonisolated solutions of nonlinear equations // Computing. — 1981. — V. 26. — P. 315—326.

68. Yamamoto N. A note on solutions of nonlinear equations with singular Jacobian matrices // J. Math. Anal. Appl. 1987. - V. 123, № 1. - P. 152-160.

69. Yamamoto N. Newton's method for singular problems and its applications to boundary value problems // J. Math. Tokushima Univ. 1983. - V. 17. - P. 26-88.