Section 2.4 Newton-Raphson and Secant Methods
are continuous near a root ,
then this extra information regarding the nature of
can be used to develop algorithms that will produce sequences
that converge faster to
than either the bisection or false position method. The
Newton-Raphson (or simply Newton's) method is one of the most useful
and best known algorithms that relies on the continuity of . The
method is attributed to Sir
Isaac Newton (1643-1727) and Joseph
Theorem (Newton-Raphson Theorem). Assume that and there exists a number , where . If , then there exists a such that the sequence defined by the iteration
will converge to for any initial approximation .
by the formula
is called the Newton-Raphson iteration formula. Since , it is easy to see that . Thus the Newton-Raphson iteration for finding the root of the equation , is accomplished by finding the fixed point of the function .
(Newton's Iteration for Finding Square Roots) Assume
a real number ant let be
an initial approximation to . Define
the recursive rule
Then the sequence converges to ; that is, .
of a Root) Assume
and its derivatives
are defined and continuous on an
interval about .
We say that has a root of order at if and only if
A root of
often called a simple
is called a multiple
root. A root of
is sometimes called a double
root, and so
on. The next result will illuminate these concepts.
the equation has
a root of order at , then
there exists a continuous function so
be expressed as the product
Speed of Convergence
The distinguishing property we seek is the following. If p is a simple root of f(x) = 0, Newton's method will converge rapidly, and the number of accurate decimal places (roughly) doubles with each iteration. On the other hand, if p is a multiple root, the error in each successive approximation is a fraction of the previous error. To make this precise, we define the order of convergence. This is a measure of how rapidly a sequence converges.
of Convergence) Assume
to p, and set . If
two positive constants exist,
then the sequence is said to converge to p with order of convergence R. The number A is called the asymptotic error constant. The cases are given special consideration.
(i) If , the convergence of is called linear.
(ii) If , the convergence of is called quadratic.
(Convergence Rate for Newton-Raphson
that Newton-Raphson iteration produces a
converges to the root p of the
If p is a simple root, then convergence is quadratic and for k sufficiently large.
If p is a multiple root of order m, then convergence is linear and for k sufficiently large.
of Newton-Raphson Iteration) Suppose
that the Newton-Raphson algorithm produces a sequence that converges
linearly to the root of
order . Then
the modified Newton-Raphson iteration formula
will produce a sequence that converges quadratically to p.
Return to Numerical Methods - Numerical Analysis
(c) John H. Mathews 2004