1.2 Newton's Method

The methods in this book are variations of Newton's method. The Newton sequence is

The interpretation of (1.2) is that we model F at the current iterate x _n with a linear function

and let the root of M _n be the next iteration. M _n is called the local linear model. If F ? ( x _n) is nonsingular, then M _n( x _n+1) = 0 is equivalent to (1.2).

Figure 1.1 illustrates the local linear model and the Newton iteration for the scalar equation

Figure 1.1: Newton iteration for the arctan function.

with initial iterate x ₀ = 1. We graph the local linear model

at x _j from the point ( x _j, y _j) = ( x _j, F( x _j)) to the next iteration ( x _{j +1}, 0). The iteration converges rapidly and one can see the linear model becoming more and more accurate. The third iterate is visually indistinguishable from the solution. The MATLAB program ataneg.m creates Figure 1.1 and the other figures in this chapter for the arctan function.

The computation of a Newton iteration requires

1. evaluation of F( x _n) and a test for termination,

2. approximate solution of the equation

   

   for the Newton step s, and

3. construction of x _{n +1} = x _n + ? s, where the step length ?