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

Рассматривается простейшая процедура экстраполяции, а именно, удвоение шага, для ускорения сходимости ньютоновских методов к особым решениям гладких нелинейных уравнений. Демонстрируется, что ускоряющий эффект этой процедуры для разных ньютоновских методов может быть разным. Для линейно-квадратичных уравнений приводятся теоретические результаты, дающие количественные оценки потенциального эффекта от экстраполяции для методов Ньютона, Левенберга–Марквардта, а также недавно предложенного ньютоновского метода с подзадачами линейного программирования, в определенном смысле объясняющие наблюдаемую разницу. Теоретически анализ основан на интерпретации этих методов как возмущенного метода Ньютона с соответствующими оценками на возмущения, а также на тонких результатах, количественно характеризующих шаг такого возмущенного метода и его локальную сходимость с линейной скоростью к особым решениям, в которых выполняется условие 2-регулярности по направлению из ядра первой производной. Также проводятся численные эксперименты для глобализаций указанных алгоритмов, снабженных выбором параметра длины шага, на двух тестовых наборах. Экспериментальные наблюдения подтверждают теоретические результаты, а также демонстрируют, что в случаях, когда уравнение содержит нелинейные и неквадратичные члены, эффект от экстраполяции выравнивается.