Inexact Newton Methods

A classical algorithm for solving the system of nonlinear equations F (x) = 0 is Newton’s method \ x₊ + ₁ = xₖ + sₖ, where F' (xₖ) sₖ = - F (xₖ), x₀ given. \ The method is attractive because it converges rapidly from any sufficiently good initial guess x₀. However, solving a system of linear equations (the Newton equations) at each stage can be expensive if the number of unknowns is large and may not be justified when xₖ is far from a solution. Therefore, we consider the class of inexact Newton methods: \ x₊ + ₁ = xₖ + sₖ, where F' (xₖ) sₖ = - F (xₖ) + rₖ, {\| {rₖ \|} / \| {F (xₖ) \|}} ₖ \ which solve the Newton equations only approximately and in some unspecified manner. Under the natural assumption that the forcing sequence \ nₖ \ is uniformly less than one, we show that all such methods are locally convergent and characterize the order of convergence in terms of the rate of convergence of the relative residuals \ {{\|rₖ \| / \|F (xₖ) \|}\}. Finally, we indicate how these general results can be used to construct and analyze specific methods for solving systems of nonlinear equations.