Accelerating convergence of Newton-type methods to singular solutions of nonlinear equations

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 LPNewton 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.