Graphics Reference
In-Depth Information
x
k+1
x
k
x
k
x
k
(a)
(b)
(c)
Figure 4.20.
Problems with the Newton-Raphson method.
The Newton-Raphson method is pretty good. There are theorems about when and
how fast the sequence of points it generates converges (it basically has quadratic con-
vergence) and upper bounds for errors. (See any text on numerical analysis.) There
are some well-known problems however:
(1) Near critical points, even if we ignore the problem of numerical instability
since we are dividing by a very small quantity, points of the sequence may
move far away from the actual root (see Figure 4.20(a)).
(2) The sequence of points can home in on a more distant and “wrong” root (see
Figure 4.20(b)).
(3) The points of the sequence may oscillate and not converge (see Figure 4.20(c)).
(4) Near multiple roots (where f¢(x) approaches 0 as f(x) does), we may have slow
convergence.
More sophisticated methods that overcome some of these problems are known, nev-
ertheless, the method is widely used because it is so simple to implement. It seems to
converge very rapidly in practice and one often has very high accuracy for the root
after only several iterations. In any case though, it always helps if one knows some-
thing about the function f. If one can make a good initial estimate, then one is usually
in good shape. Of course, choosing a good initial estimate is often a major problem
with using the method. Some bounds for the location of zeros are known. The reader
will find more information in most topics on numerical methods. For an interesting
history of how the method got its name see [Alex96]. Finally, note that what we have
just said about real functions also applies to complex functions f :
C
Æ
C
.
The Newton-Raphson method generalizes to higher dimensions and functions of
several variables because there is a similar Taylor expansion
()
=
(
+
()
-
(
)
+ higher-order terms.
f
xx
f
f
xxx
k
k
k
In other words, the only difference between what we have now and what we had before
is that now we need to solve a
system
of linear equations
()
+-
(
)
¢
()
=
f
xxxx0
f
(4.15)
k
k
k
