Module

for

The Accelerated and Modified Newton Methods

Background

Newton's method is commonly used to find the root of an equation.  If the root is simple then the extension to Halley's method will increase the order of convergence from quadratic to cubic.  At a multiple root it can be speed up with the accelerated Newton-Raphson and modified Newton-Raphson methods.

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

for

will converge to for any initial approximation  .

Definition (Order of a Root)  Assume that  f(x)  and its derivatives    are defined and continuous on an interval about  x = p.  We say that  f(x) = 0  has a root of order  m  at   x = p  if and only if

.

A root of order  m = 1  is often called a simple root, and if  m > 1  it is called a multiple root.  A root of order  m = 2  is sometimes called a double root, and so on.  The next result will illuminate these concepts.

Definition (Order of Convergence)  Assume that   converges to  p,  and set  .    If two positive constants    exist, and

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.

Theorem (Convergence Rate for Newton-Raphson Iteration)  Assume that Newton-Raphson iteration produces a sequence   that converges to the root  p  of the function  .

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.

Algorithm (Newton-Raphson Iteration).  To find a root of    given an initial approximation    using the iteration

for    .

Computer Programs  Newton-Raphson Method  Newton-Raphson Method

Mathematica Subroutine (Newton-Raphson Iteration).

``````
``````

Example 1.  Use Newton's method to find the roots of the cubic polynomial  .
1 (a) Fast Convergence.  Investigate quadratic convergence at the simple root  ,  using the starting value
1 (b) Slow Convergence.  Investigate linear convergence at the double root  ,  using the starting value
Solution 1 (a).
Solution 1 (b).

Theorem (Acceleration of Newton-Raphson Iteration)  Given that the Newton-Raphson algorithm produces a sequence that converges linearly to the root    of order   .  Then the accelerated Newton-Raphson formula

for

will produce a sequence that converges quadratically to  p.

Mathematica Subroutine (Accelerated Newton-Raphson Iteration).

``````
``````

Example 2.  Use the accelerated Newton's method to find the double root  ,  of the cubic polynomial  .  Use the starting value
Solution 2.

Example 3.  Use the accelerated Newton's method to find the double root  ,  and triple root   ,  of the cubic polynomial  .
Solution 3.

More Background

If
f(x)  has a root of multiplicity   m   at  x=p  , then  f(x)  can be expressed in the form

where  .  In this situation, the function  h(x)  is defined by

and it is easy to prove that
h(x)  has a simple root at  x=p.  When Newton's method is applied for finding the root  x=p  of  h(x)  we obtain the following result.

Theorem (Modified Newton-Raphson Iteration)  Given that the Newton-Raphson algorithm produces a sequence that converges linearly to the root    of multiplicity   .  Then the modified Newton-Raphson formula

which can be simplified as

for

will produce a sequence that converges quadratically to  p.

Mathematica Subroutine (Modified Newton-Raphson Iteration).

``````
``````

Example 4.  Use the modified Newton's method to find the double root  ,  of the cubic polynomial  .  Use the starting value
Solution 4.

Example 5.  Use the modified Newton's method to find the double root  ,  and triple root   ,  of the cubic polynomial  .
Solution 5.

Example 6.  Consider the function  .
6 (a).  Use Newton's method to find the multiple root  .
6 (b).  Use the accelerated Newton's method to find the multiple root  .
6 (c).  Use the modified Newton's method to find the multiple root  .
Solution 6 (a).
Solution 6 (b).
Solution 6 (c).

Animations ( Newton's Method  Newton's Method ).

Old Lab Project ( Newton's Method  Newton's Method ).

Newton-Raphson Method  Newton-Raphson Method  Internet hyperlinks to web sites and a bibliography of articles.

(c) John H. Mathews 2004