  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 ).

Research Experience for Undergraduates

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

Download this Mathematica Notebook Accelerated and Modified Newton Methods

Return to Numerical Methods - Numerical Analysis

(c) John H. Mathews 2004