Next: Convergence
of Newton's Method Up: Roots
of a Single-Variable Previous: Bisection
Error Analysis
Newton's Method
While the bisection method has considerable appeal inasmuch as it always
converges (with the appropriate setup) and that the maximum number of iterations
for convergence can be computed in advance, convergence of the bisection
method is slow. Newton's method, described here, aims to improve the rate
of convergence.
In describing Newton's method, consider a function
f(x) which has a root 
. Given an approximate root, 
, the next approximation is found by finding the root of the tangent to
the line at 
. Thus, instead of finding the root to the function f(x),
Newton's method reduces the problem to finding the root to the linear
approximation of f(x) which interpolates 
and has the same slope of f(x) at
. Of course, the slope of the curve at
is given by the derivative at
, 
.
From this simple description, derivation of Newton's
method requires finding the root to the line which passes through
and has the slope
. The equation for this line in point-slope form is
Figure 4.1: Newton's method
approximates the root of f(x) by finding the root to the
linear approximation to f(x) which passes through
and has the slope
.
which passes through the x-axis, producing the approximation 
, when y=0:
Solving this equation for
yields
Equation 4.3 is Newton's method.
As an illustration of Newton's method, consider the
following example, and compare to the same problem solved by the bisection
method, illustrated in Example 4.1:
In reference to Equation 4.3,
one can see the possibility of problems creeping into the iterations associated
with Newton's method. Some problems which might arise are
-
Small values for the derivatives
can lead to very large deviations in the calculation of
. Unfortunately, this scenario may happen when the function has a double
root.
-
If the function has multiple roots, there is no universal technique
for choosing different starting values so as to converge to different roots.
It may be that one root is of paramount interest, whereas convergence of
the method tends always toward other roots. In such a situation, the bisection
method might be called upon to get significantly close to the root of interest,
where Newton's method can then be used to quickly converge.
-
There is a chance (albeit slight) that Newton's method can be caught
in an endless cycling around the root. This can be the case when the root
is near an inflection point.
Additionally, Newton's method requires a mechanism to compute the derivative
of a function, which could be more expensive computationally, than the
added speed of convergence.
Next: Convergence
of Newton's Method Up: Roots
of a Single-Variable Previous: Bisection
Error Analysis
Paul Gray
Wed Oct 28 11:42:13 EST 1998
