Globally Convergent Inexact Newton Methods

Abstract

Abstract. Inexact Newton methods for finding a zero of F 1 1 are variations of Newton’s method in which each step only approximately satisfies the linear Newton equation but still reduces the norm of the local linear model of F. Here, inexact Newton methods are formulated that incorporate features designed to improve convergence from arbitrary starting points. For each method, a basic global convergence result is established to the effect that, under reasonable assump-tions, if a sequence of iterates has a limit point at which F is invertible, then that limit point is a solution and the sequence converges to it. When appropriate, it is shown that initial inexact Newton steps are taken near the solution, and so the convergence can ultimately be made as fast as desired, up to the rate of Newton’s method, by forcing the initial linear residuals to be appropriately small. The primary goal is to introduce and analyze new inexact Newton methods, but consideration is also given to "globalizations " of (exact) Newton’s method that can naturally be viewed as inexact Newton methods. Key words, inexact Newton methods, Newton iterative methods, truncated Newton methods, Newton’s method, globally convergent Newton-like methods, global convergence analyses for Newton-like methods AMS subject classification. 65H10