1.4 Inexact Newton Methods

Rather than approximate the Jacobian, one could instead solve the equation for the Newton step approximately. An inexact Newton method [22] uses as a Newton step a vector s that satisfies the inexact Newton condition

The parameter ? (the forcing term) can be varied as the Newton iteration progresses. Choosing a small value of ? will make the iteration more like Newton's method, therefore leading to convergence in fewer iterations. However, a small value of ? may make computing a step that satisfies (1.10) very expensive. The local convergence theory [22, 42] for inexact Newton methods reflects the intuitive idea that a small value of ? leads to fewer iterations. Theorem 1.3 is a typical example of such a convergence result.

Theorem 1.3

Let the standard assumptions hold. Then there are ? and ? such that, if x ₀ ? ( ?), { ? _n} ? [0, ?], then the inexact Newton iteration

where

converges q-linearly to x*. Moreover,

• if ? _n ? 0, the convergence is q-superlinear, and

• if ? _n ? K _? F ( x _n) ^p for some K _? > 0, the convergence is q-superlinear with q-order 1 + p.

Errors in the function evaluation will, in general, lead to stagnation of the iteration.

One can use Theorem 1.3 to analyze the chord method or the secant method. In the...