Next: 7.3 Numerical integration
Up: 7.2 Rootfinding (optimization)
Previous: 7.2.1 Bisection
Contents
The bisection method is a very intuitive method for finding a root but
there are other ways that are more efficient (find the root in fewer
iterations). Perhaps the best known root finding algorithm is Newton's
method (a.k.a. NewtonRaphson method). Recall that the Taylor's series
expansion for a function is
In words, the first two terms of
the series say that the function can be approximated, at one point, by
taking it's value () at a nearby point () and using the slope
() at that point to extrapolate to the point where we want to
approximate the function. Figure 7.3 illustrates the idea.
Figure 7.3:
Illustration of the Taylor's series expansion approximation for
a function . The blue line is the actual function and the
red line is the approximation to given by the first two terms of
the Taylor's series. Close to the error in the approximation is
small but as increases, the error becomes significant.

In the figure, the blue line is the actual function and the red line
is the approximation to given by the the first two terms of the
Taylor's series. In Newton's method, the root of the approximate is
used to get a guess for the actual root (see figure). A new Taylor's series
is then computed around this new guess, which yields another guess that is
(usually) even closer to the actual root. Two steps of the process are
shown in Fig. 7.4
Figure 7.4:
Illustration of two steps of the Newton's method for root
finding. The starting point for the method is . The red line is the first
approximation to with yields the first guess at the root which is
. The function is then reapproximated by a Taylor's expansion about
the point , illustrated by the green line. The root of the second
approximation is , already close to the actual root of .

The algorithm of Newton's rootfinding method can be summarized as follows:
 Specify the starting guess and the desired accuracy .
 Compute the next guess from the current guess using
.
 Repeat step 2 until the desired accuracy is met, that is, until
or
, either criterion can be
used depending on the situation.
It is possible that Newton's method will not converge if the initial guess
is too far away from the actual root depending on the particular form of
. So it is a good idea to limit the number of iterations allowed by
your program to prevent the algorithm from iterating forever without
success. Implementation of Newton's method is left as an assignment for the
student.
Figure 7.5:
Illustration of a secant and tangent to . Obviously, as
becomes smaller and smaller, the secant and tangent will
become more and more similar. In the limit
, they
will become identical.

One of the problems with Newton's method is that the derivative of
must be known. In many cases, the derivative is not known or may be too
time consuming to compute. In these cases, the secant method offers a
viable alternative. The secant method is really the same method as Newton's
method except the exact derivative is replaced with an approximate,
``numerical'' derivative.
The derivative
is defined as
. If,
instead of taking the limit, a finite is used then this
expression, rather than giving a tangent to , gives a
line (a secant) that passes through at and at
as shown in Fig. 7.5. Obviously, as becomes
smaller, the secant and tangent approach the same slope. In the limit
, they will become identical.
In the secant method, is approximated by a ``finite difference''
derivative (i.e., ). Other than this, it is identical to
Newton's method. In contrast to the secant method, Newton's method could be
called a ``tangent'' method. The secant method algorithm for a computer
program is summarized in the following.
 Specify two starting guesses and , and the desired accuracy .
 Compute the next guess from the current guess using
. Note that
where is the just
slope of the line passing between and .
 Repeat step 2 until the desired accuracy is met, that is, until
or
, either criterion can be
used depending on the situation.
Actual implementation of the method in a program will be left as an
assignment.
Next: 7.3 Numerical integration
Up: 7.2 Rootfinding (optimization)
Previous: 7.2.1 Bisection
Contents
Gus Hart
20050128