Содержание к диссертации
Введение
1 Определяющие системы 13
1.1 Построение определяющих систем и ньютоновские методы 13
1.1.1 Способы выбора проектора 15
1.1.2 Ньютоновские методы 20
1.2 Реализуемые алгоритмы 24
1.3 Устойчивость 29
2 Краевые задачи и уравнения с фредгольмовыми производными 34
2.1 Нелинейные краевые задачи 34
2.1.1 Конечномерная редукция 35
2.1.2 Реализация для краевых задач 37
2.2 Уравнения с фредгольмовыми производными 49
2.2.1 Некоторые сведения о фредгольмовых линейных операторах . 50
2.2.2 Построение определяющей системы 57
3 Уравнения с ограниченной гладкостью и комплементарные задачи 69
3.1 Уравнения с липшицевой первой производной 69
3.1.1 Построение определяющей системы 69
3.1.2 Метод Ньютона в ослабленных требованиях гладкости 72
3.2 Нелинейные комплементарные задачи 77
3.2.1 Метод Ньютона для NCP 78
3.2.2 Условия регулярности 82
Приложение. Вычислительные примеры 88
А Системы нелинейных уравнений 88
Б Нелинейные краевые задачи 92
В Уравнения с фредгольмовыми производными 95
Заключение 97
Литература 98
Введение к работе
В данной диссертационной работе изучаются особые решения нелинейного уравнения
F(x) = О, (1)
где F : О —> Шт — обладающее определенной гладкостью отображение, О С И" — открытое множество, п > т. Решение х Є О уравнения (1) называется особым, если
rank F'(x) < т,
или, другими словами,
г = corankF'(.T) > 0.
В противном случае решение х называется регулярным.
Важнейшие приложения, в связи с которыми появляется необходимость анализа и численного отыскания особых решений, возникают, скажем, в теории бифуркаций (см., например, обзор в [55]), а также в оптимизации, включая комплементарные и связанные с ними задачи [50], [18|.
По всей видимости, началом исследований по проблематике особых решений и численных методов их отыскания можно считать работу [63], в которой было установлено, что метод Ньютона обладает лишь линейной скоростью сходимости к кратному корню одного скалярного уравнения с одной неизвестной (п = 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], [ЗО], [47], где главное внимание уделялось ослаблению ограничений на г, а также получению расширенных систем как можно меньшего размера. Нужно особо отметить работу [58], в которой была предложена минимально расширенная определяющая система для произвольного г, а также работы [41], где делается попытка подведения идеологической базы иод «unfolding-cut», и [28], содержащую фундаментальное изложение данного подхода и его реализаций. Среди недавних публикаций отметим [42], [7], [48], [29].
Заметим, что реализация обоих этапов подхода «unfolding-cut» требует определенной информированности о структуре особенности. Минимальным из таких требований является знание числа г. Это можно интерпретировать следующим образом: ищется не просто решение уравнения (1), и даже не просто особое решение, а особое решение заданного коранга. С другой стороны, существуют способы определения г без точного знания х (см. [58], [28], [18, п. 3.1.3] и раздел 1.2 данной работы).
Основным недостатком подхода «unfolding-cut» является то, что размер системы уравнений, которую нужно решать, неизбежно увеличивается. В определенном смысле этот недостаток был преодолен в [29], за счет выделения ньютоновских итераций по исходной переменной.
Общий подход к построению (действительно) минимально расширенных определяющих систем был предложен в [б], где также был предложен один из вариантов реализации указанного подхода, приводящий к явным формулам для итерационной матрицы метода Ньютона, применяемого к определяющей системе. Эта реализация обобщает конструкции из работ [16], [14], которые, в свою очередь, использовали идею так называемого 2-факторметода [4], [17]. Получаемое на этом пути регуляризованное уравнение (определяющая система) имеет ту же размерность, что и исходное уравнение (1).
Целью диссертации является построение новых численных методов ньютоновского типа, позволяющих находить особые решения нелинейных уравнении в очень слабых предположениях невырожденности.
В главе 1 изучается подход к численному отысканию особых решений систем нелинейных уравнений, состоящий в построении (переопределенной) определяющей системы и применении к ней методов ньютоновского типа. Этот подход приводит к полностью реализуемым локальным алгоритмам, не содержащим недетерминированных элементов и обладающим локальной сверхлинейной сходимостью в очень слабых
Введение
предположениях.
Структуру особенности F в точке х, а точнее, структуру образа F'(x), можно описать матричным уравнением
PF'(x) = О, (2)
где Р Є ]RmXm — проектор на некоторое прямое дополнение Y2 подпространства Yi = imF'(x) в Шт параллельно Y\. Заметим, что такое описание в определенном смысле оптимально: оно полное, и не приводит к необходимости введения дополнительных переменных. Точка х удовлетворяет (2), но, во-первых, Р в общем случае не может быть известно точно (без знания искомого х), а во-вторых, система (2) содержит слишком много уравнений. Поэтому, во-первых, Р в (2) следует заменить некоторой его аппроксимацией Р : О — Щ,тхт (подразумевается, что Р(х) = Р), а во-вторых, следует организовать выбор нужного числа, а именно п уравнений из системы
F{x) = О, P(x)F'(x) = 0, (3)
возможно, допуская «перемешивание» этих уравнений. Если аппроксимация Р{х) зависит от х Є О гладким образом, то к получаемой таким образом системе можно применять метод Ньютона. Такой подход был реализован в [6].
Все известные на сегодня способы выбора проектора Р(-) предполагают знание коранга особенности г. Иногда г может быть известно из анализа, являющегося внешним по отношению к описываемому подходу. С другой стороны, г может рассматриваться как параметр с конечным числом возможных значений. Наконец, известны регулярные процедуры для определения г, предполагающие, что известна точка в IR" достаточно близкая к х (такая точка нужна в любом случае, поскольку речь идет о локальных методах ньютоновского типа).
Способы выбора проектора
По всей видимости, началом исследований по проблематике особых решений и численных методов их отыскания можно считать работу [63], в которой было установлено, что метод Ньютона обладает лишь линейной скоростью сходимости к кратному корню одного скалярного уравнения с одной неизвестной (п = 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], [ЗО], [47], где главное внимание уделялось ослаблению ограничений на г, а также получению расширенных систем как можно меньшего размера. Нужно особо отметить работу [58], в которой была предложена минимально расширенная определяющая система для произвольного г, а также работы [41], где делается попытка подведения идеологической базы иод «unfolding-cut», и [28], содержащую фундаментальное изложение данного подхода и его реализаций. Среди недавних публикаций отметим [42], [7], [48], [29].
Реализуемые алгоритмы
Заметим, что реализация обоих этапов подхода «unfolding-cut» требует определенной информированности о структуре особенности. Минимальным из таких требований является знание числа г. Это можно интерпретировать следующим образом: ищется не просто решение уравнения (1), и даже не просто особое решение, а особое решение заданного коранга. С другой стороны, существуют способы определения г без точного знания х (см. [58], [28], [18, п. 3.1.3] и раздел 1.2 данной работы).
Основным недостатком подхода «unfolding-cut» является то, что размер системы уравнений, которую нужно решать, неизбежно увеличивается. В определенном смысле этот недостаток был преодолен в [29], за счет выделения ньютоновских итераций по исходной переменной.
Общий подход к построению (действительно) минимально расширенных определяющих систем был предложен в [б], где также был предложен один из вариантов реализации указанного подхода, приводящий к явным формулам для итерационной матрицы метода Ньютона, применяемого к определяющей системе. Эта реализация обобщает конструкции из работ [16], [14], которые, в свою очередь, использовали идею так называемого 2-факторметода [4], [17]. Получаемое на этом пути регуляризованное уравнение (определяющая система) имеет ту же размерность, что и исходное уравнение (1).Целью диссертации является построение новых численных методов ньютоновского типа, позволяющих находить особые решения нелинейных уравнении в очень слабых предположениях невырожденности. В главе 1 изучается подход к численному отысканию особых решений систем нелинейных уравнений, состоящий в построении (переопределенной) определяющей системы и применении к ней методов ньютоновского типа. Этот подход приводит к полностью реализуемым локальным алгоритмам, не содержащим недетерминированных элементов и обладающим локальной сверхлинейной сходимостью в очень слабых предположениях. Структуру особенности F в точке х, а точнее, структуру образа F (x), можно описать матричным уравнением PF (x) = О, (2) где Р Є ]RmXm — проектор на некоторое прямое дополнение Y2 подпространства Yi = imF (x) в Шт параллельно Y\. Заметим, что такое описание в определенном смысле оптимально: оно полное, и не приводит к необходимости введения дополнительных переменных. Точка х удовлетворяет (2), но, во-первых, Р в общем случае не может быть известно точно (без знания искомого х), а во-вторых, система (2) содержит слишком много уравнений. Поэтому, во-первых, Р в (2) следует заменить некоторой его аппроксимацией Р : О — Щ,тхт (подразумевается, что Р(х) = Р), а во-вторых, следует организовать выбор нужного числа, а именно п уравнений из системы F{x) = О, P(x)F (x) = 0, (3) возможно, допуская «перемешивание» этих уравнений. Если аппроксимация Р{х) зависит от х Є О гладким образом, то к получаемой таким образом системе можно применять метод Ньютона.
Такой подход был реализован в [6]. Все известные на сегодня способы выбора проектора Р(-) предполагают знание коранга особенности г. Иногда г может быть известно из анализа, являющегося внешним по отношению к описываемому подходу. С другой стороны, г может рассматриваться как параметр с конечным числом возможных значений. Наконец, известны регулярные процедуры для определения г, предполагающие, что известна точка в IR" достаточно близкая к х (такая точка нужна в любом случае, поскольку речь идет о локальных методах ньютоновского типа). Раздел 1.1.1 посвящен описанию двух способов реализации отображения Р(-), на основе которых конструируется определяющая система вида Ф(х) = 0, (4) где Ф : О — Кт х ]р{/гх(п-т+г) _ гладкое отображение. Идея состоит в том, чтобы оставить в этой системе лишь «существенную часть» второго уравнения в (3). Система (4) при г 0 является переопределенной. Общий оператор выбора — это отображение Я(-) : ШГ - (Rm х х(п-т+г) - Задав это отображение, от системы (4) переходим к системе Щх)Ф(х) = 0. (5) В разделе 1.1.2 описываются две конкретные реализации оператора выбора, которые представляются наиболее естественными: 1) Щ-) = П, где Ті Є С(Жт х W {n m+r\ ПГ) - фиксированный (постоянный) оператор; 2) ад = (Ф (-))Т К системе (5) с постоянным оператором выбора могут применяться стандартные численные методы (например, метод Ньютона). В очень слабых предположениях на первые две производные F в искомом решении х можно показать, что при почти любом 7 такой процесс будет обладать локальной сверхлинейной сходимостью. То есть, 7. можно выбирать, скажем, случайным образом. Однако, соответствующие алгоритмы будут не вполне детерминированными. Вместе с тем, в некоторых случаях реализация этого способа оказывается затруднительной, и приходится применять первый (более простой, хотя и недетерминированный) способ.
Конечномерная редукция
Для второго способа задания 7(-) итерация метода Ньютона для уравнения (5) имеет вид (Ф"{хк)[хк+1 - хк})ТФ(хк) + (Ф (хк))тФ (хк)(хк+1 - хк) = -(Ф (хк))тФ(хк), и может быть заменена своей неточной версией без ущерба для скорости сходимости: (Ф (хк))тФ (хк)(хк+1 - хк) = -(Ф (хк))тФ(хк), что соответствует методу Гаусса—Ньютона для уравнения (4). Данная модификация позволяет избежать необходимости вычислять вторые производные Ф.
Таким образом, вместо явного уменьшения числа уравнений до п, здесь «выбор» нужных уравнений происходит автоматически, в рамках итерации метода Гаусса-Ньютона, причем это не сопровождается «проигрышем» в условиях регулярности, гарантирующих локальную сверхлинейнуго сходимость. В частности, такие алгоритмы являются полностью детерминированными, а их обоснование не требует согласования качества используемого оператора выбора (который обычно назначается случайным образом) с требуемым качеством начального приближения (которое далеко не всегда контролируемо). С другой стороны при малых г новые алгоритмы могут быть достаточно экономичными в плане трудоемкости их итераций, которая также анализируется в разделе 1.1.2.
В разделе 1.2 предлагаются конструктивные способы идентификации коранга особенности г и выбора других параметров, необходимых для реализации описанного подхода, по имеющемуся начальному приближению х Є IR". Эти способы основаны на оценке расстояния до решения при выполнении условия 2-регулярности. Приведен итоговый, полностью реализуемый алгоритм для отыскания особых решений систем нелинейных уравнений. В разделе 1.3 изучается устойчивость данного подхода отыскания особых решений по отношению к возмущению оператора уравнения. Глава 2 посвящена эффективным численным методам поиска особых решений нелинейных краевых задач и нелинейных операторных уравнений с фредгольмовыми производными. В разделе 2.1 рассматриваются краевые задачи. В частности, в разделе 2.1.1 речь идет о редукции краевых задач для обыкновенных дифференциальных уравнений к конечномерным системам уравнений. Раздел 2.1.2 посвящен применению к краевым задачам алгоритмов, описанных в главе 1. Реализация данных алгоритмов требует решения на каждой итерации вспомогательных матричных начальных задач. Последнее же, разумеется, делается приближенно, что приводит к необходимости принимать во внимание неизбежную неточность вычисления значений и производных отображения F. Рассматривается случай, когда для решения вспомогательных начальных задач используется простейшая разностная схема, а именно схема Эйлера, и показывается, что возникающие при этом погрешности можно интерпретировать как гладкое возмущение отображения F, удовлетворяющее всем условиям теорем об устойчивости из раздела 1.3. Раздел 2.2 посвящен уравнениям с фредгольмовыми производными и, в частности, интегральным уравнениям. Заметим, что для интегральных уравнений полная конечномерная редукция невозможна: они бесконечномерны по существу, в отличие, скажем, от краевых задач для обыкновенных дифференциальных уравнений. Кроме того, конечномерную аппроксимацию исходного интегрального уравнения (например, с помощью замены интеграла квадратурами; см., например, [18, приложение А]) с особым решением обосновать едва ли возможно. Во-первых, особое решение может не быть устойчивым по отношению к такому «возмущению», и тогда аппроксимирую щее конечномерное уравнение может вообще не иметь решений. Во-вторых, если даже искомое решение устойчиво, то соответствующее решение конечномерного уравнения может быть — и обычно будет — неособым (и специальные методы поиска особых решений для этого уравнения не сработают), а «почти особым» (и стандартные подходы также будут неэффективны).
Построение определяющей системы
Иными словами, представляется более правильным осуществлять «регуляризацию» (в том или ином смысле этого слова) исходного бесконечномерного уравнения, а уже потом строить конечномерные аппроксимации регуляризованного уравнения. В разделе 2.2.1 приводятся некоторые сведения о фред-гольмовых линейных операторах. Раздел 2.2.2 содержит обобщение на случай фред-гольмовых производных конечномерного подхода поиска особых решений нелинейных уравнений, рассмотренного в главе 1. В главе 3 предлагается специальный метод ньютоновского типа для поиска решения определяющей системы в случае, когда оператор исходного уравнения обладает лишь первой, но не второй производной. Общая конструкция метода приведена в разделе 3.1. В разделе 3.2 данный метод реализуется для гладких переформулировок нелинейных комплементарных задач (NCP). Нелинейная комплементарная задача ставится следующим образом: найти х Є Ш" такой, что G{x) О, х 0, (G{x), х) = 0, (6) где G : Ж" —» IR" — гладкое отображение. Множество решений NCP (6) совпадает с множеством решений уравнения (1), где F : IRn — Кп имеет компоненты Fi(x) = 2Gi(x)xi-(min{0,Gi{x)+xi})2, і = 1,..., п. (7) Соответственно, возникает идея решать NCP (6) применяя к (1) с таким оператором F те или иные численные методы решения систем нелинейных уравнений. Однако, реализации этой идеи неизбежно связаны с преодолением весьма серьезных трудностей. А именно, пусть х - решение NCP (6). Предположим, что отображение G дважды непрерывно дифференцируемо в некоторой окрестности точки х. Тогда отображение F имеет вблизи х производную, которая удовлетворяет условию Липшица, причем для любого х из этой окрестности справедливы равенства F {x) = 2(х{С{(х) + Gdxy - min{0, Gi{x) + x G x) + e% (8) г = 1, ..., п. В частности, ( 0, если і Є /о, і (ж) — 2 XjG x), если г Є /і, і — 1, ..., п, (9) Gi(x)e\ если г Є /г, где используются множества индексов I0 = /о (ж) = {г = 1, ..., п Gi(:r) = 0, щ = 0}, Ji = h(x) = {г = 1, ..., та Gi(x) = 0, х{ 0}, /2 = 12{х) = {і = 1, ..., п Gi(.f) 0, ЖІ = 0}. Отсюда следует, что если в решении х нарушается условие строгой дополнительности 1о — 0, которое принято считать весьма обременительным требованием, то х неизбежно является особым решением уравнения (1), т.е. detF (x) = 0, и эффективное отыскание этого решения стандартными ньютоновскими методами для уравнения (1) с оператором (8) становится невозможным. С другой стороны, специальные ньютоновские методы для отыскания особых решений нелинейных уравнений, разработанные, например, в [52, 8, 32] и в главе 1, в данном случае также напрямую неприменимы, поскольку эти методы предполагают двукратную дифференцируемость F, что для данного отображения, вообще говоря, не имеет места ни при каких требованиях гладкости отображения G. Соответственно, применяется специальный подход из раздела 3.1. В приложении представлены результаты вычислительного эксперимента для разработанных алгоритмов на некоторых тестах из [18] и [65]. Поведение алгоритмов сравнивалось с традиционными численными методами: для систем нелинейных уравнений и для Я-уравнения Чандрасехара сравнение проводилось с методом Ньютона, для нелинейных краевых задач - с методом квазилинеаризации. В заключении сформулированы основные результаты, полученные в диссертации. Автор выражает глубокую благодарность своему научному руководителю Алексею Феридовичу Измайлову за постановку задачи, постоянное внимание к работе, ценные замечания, поддержку и безмерное терпение.
