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:
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?
|
|