Inexact Newton Methods

A classical algorithm for solving the system of nonlinear equations $F(x) = 0$ is Newton’s method \[ xk + 1 = x_k + s_k , {where }F'(x_k )s_k = - F(x_k ), x_0 { 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: \[ xk + 1 = x_k + s_k , {where }F'(x_k )s_k = - F(x_k ) + r_k , {{\| {r_k } \|} / {\| {F(x_k )} \|}} η _k \] 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.