Рассматривается простейшая процедура экстраполяции, а именно, удвоение шага, для ускорения сходимости ньютоновских методов к особым решениям гладких нелинейных уравнений. Демонстрируется, что ускоряющий эффект этой процедуры для разных ньютоновских методов может быть разным. Для линейно-квадратичных уравнений приводятся теоретические результаты, дающие количественные оценки потенциального эффекта от экстраполяции для методов Ньютона, Левенберга–Марквардта, а также недавно предложенного ньютоновского метода с подзадачами линейного программирования, в определенном смысле объясняющие наблюдаемую разницу. Теоретически анализ основан на интерпретации этих методов как возмущенного метода Ньютона с соответствующими оценками на возмущения, а также на тонких результатах, количественно характеризующих шаг такого возмущенного метода и его локальную сходимость с линейной скоростью к особым решениям, в которых выполняется условие 2-регулярности по направлению из ядра первой производной. Также проводятся численные эксперименты для глобализаций указанных алгоритмов, снабженных выбором параметра длины шага, на двух тестовых наборах. Экспериментальные наблюдения подтверждают теоретические результаты, а также демонстрируют, что в случаях, когда уравнение содержит нелинейные и неквадратичные члены, эффект от экстраполяции выравнивается.
We consider the simplest extrapolation procedure, specifically doubling the step, intended for acceleration of convergence of Newton-type methods to singular solutions of smooth nonlinear equations. We demonstrate that the acceleration effect of this procedure can be different for different Newton-type methods. For linear-quadratic equations we provide theoretical results yielding quantitative estimates of the potential effect of extrapolation for the Newton method, for the Levenberg–Marquardt method, and for the recently proposed LP-Newton method, in some sense explaining the observed difference. Theoretical analysis relies on interpretation of these methods as a perturbed Newton method with the appropriate estimates of perturbations, as well as on sharp results yielding a quantitative characterization of a step of such perturbed method, and its local convergence at a linear rate to singular solutions satisfying the 2-regularity condition in a direction from the null space of the first derivative. Furthermore, we perform numerical experiments with globalized versions of the algorithms in question, equipped with choosing the stepsize parameter, on two sets of test problems. Experimental observations confirm the theoretical results, and also demonstrate that in cases when the equation contains nonlinear and nonquadratic terms, the effect of extrapolation is evened out.
The authors declare that there are no conflicts of interest present.