Next: 7.3 Numerical integration Up: 7.2 Root-finding (optimization) Previous: 7.2.1 Bisection   Contents

7.2.2 Newton's Method and the Secant Method

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. Newton-Raphson 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.
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
The algorithm of Newton's root-finding method can be summarized as follows:
1. Specify the starting guess and the desired accuracy .
2. Compute the next guess from the current guess using .
3. 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.
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.
1. Specify two starting guesses and , and the desired accuracy .
2. Compute the next guess from the current guess using . Note that where is the just slope of the line passing between and .
3. 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 Root-finding (optimization) Previous: 7.2.1 Bisection   Contents
Gus Hart 2005-01-28