Newton's Method for Zeros

As explained in class, Newton's method for finding the zeros (or roots) of a function f(x) (i.e., the points at which its graph crosses the x-axis) is to take an initial guess for the zero, say x0, to find the corresponding point on the graph and the tangent line at the point, and use the point x1 at which the tangent line meets the x-axis as a new approximation to the root; and repeat the process, in the hope of getting closer to the root at each step:

xn+1 = xn - f(xn)/f'(xn) .

Here are some of examples of this process in practice:

We begin with the polynomial
f(x) = x3 + 3x2 - 9x - 29 ,

for which part of the graph is shown in the screen shot from the Excel spreadsheet program. In the top row of the spreadsheet we see various first approximations to the desired root: 3, 1, 4, 2 and 0. (Note that the formula in the highlighted square, D2, appears in the formula bar above the top of the sheet: it is the Newton's method formula applied to the contents of the cell D1 above it. In all the cells below the first row that have entries, the formula was copied from D2.) Because it is clear from the graph that the zero is just a bit above 3, it is not surprising that if 3 is the first guess, then the process rapidly yields the root accurate to 6 decimal places (visible in the spreadsheet). If 1 is the first guess, there is no second guess: because f'(1) = 0, the tangent line at x=1 is parallel to the x-axis. Using 4 or 2 as first guess means that the process takes one or two more steps than using 3 did to give the same accuracy. And using 0 as a first guess results as a process that wanders far away from the root for about 14 steps before yielding the same accuracy -- the slope at 0 is in the wrong direction, so the tangent line leads us away from the root. So we see that the initial guess is important.
Looking at the graphs of y=2x/(1+x2) and y=Arctan x, we see there are three points at which they cross: one is 0, and the other two are negatives of each other. Calling the positive one of these R (for later reference), we set about to find it by applying Newton's method to the function
2x/(1+x2) - Arctan x .

(You should verify that the formula in cell F2, displayed in the formula bar, is indeed the Newton's method formula applied to the contents of cell F1 -- its original form was a complex fractional expression, simplified here.) We see that the various first guesses give different results: For first guesses of 1.5, 2.5, and 1 the process converges to the desired R, with the value 1.391745; while an initial guess of 0.2 gives a process converging to the root 0; and an initial guess of 3, even though it is well above R, results in a process converging to the third root, -R.
We know exactly what the zeros of x3-4x are: 0, 2 and -2. Applying Newton's method using the computer algebra program Mathematica (you should verify that the formula for Next[x] is what results from simplifying the Newton's method formula in this case), we see:
  • Although the first guess of 1 is between the roots 0 and 2, it happens that the tangent to the graph at x=1 hits the x-axis at the other , -2, and of course the process stops immediately at this root. (By the way, the initial N in the first application of the Next function means "Give a numerical approximation to the answer," so that Mathematica does not just print out "2*1^3/(3*1^2-4)". Mathematica is a very powerful, but very literal-minded, program.)
  • A first guess of 0.5 gives an answer with 11 digits of accuracy in only three steps. We conclude that the graph of the polynomial is very close to a straight line between x=0.5 and x=0.
  • A first guess of 3 converges in three steps to within 3 digits of accuracy of the root 2.
The zero of y = Arctan x is clearly 0, and a first guess of 1 takes only 4 steps to find that answer to 9 digits of accuracy. But a first guess of 2 yields a process that fails to converge at all: each approximation is larger in absolute value than the last, though of the opposite sign. Another alternative is possible, though I have not put it on this sheet: The value R that we found above in the context of another problem was chosen so that, if we had used it as the initial guess, then the second guess would have been -R, the third guess R, the fourth -R, and so on. I.e., the results of the process would have been "periodic", with period 2.
The last example shows how Newton's method fits into an important area of current mathematical research: "chaos theory", which looks for patterns in apparently patternless activity, especially in cases when the activity is governed by precise laws. Repeated applications of the same function (as in Newton's method) is a good source of chaotic behavior for study. Here is another example: The function
y = (9/2*sqrt(3))(x3 - x)

The coefficient 9/2*sqrt(3) is included so that the function takes on all the y-values from -1 to 1 as x takes on all the values from -1 to 1.
As the portion of the spreadsheet shows, for most initial values (-0.7, -0.4, 0.4 and 0.7) in the interval in question, if we repeatedly apply the function, there is no apparent pattern in resulting values, except that they alternate in sign (as is clear from the graph: negative values get taken to positive ones, and vice versa). The exception is the initial value 0, for which all the resulting values are 0. So in this case we seem to have 4 cases of chaotic behavior of "iterates" of the function and one of periodic behavior with period 1.
We can see the results on a graph of the values, as a function of the number of iterations of the function. Do you see a pattern in the green squares (i.e., the results of applying the function repeatedly to -0.4), for example?