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

• Ерина, Мария Юрьевна
• кандидат физико-математических наук
• 2007

Оглавление диссертации кандидат физико-математических наук Ерина, Мария Юрьевна

Введение

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Ерина, Мария Юрьевна, 2007 год

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.