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 [Graphics:Images/NewtonAccelerateMod_gr_1.gif] and there exists a number [Graphics:Images/NewtonAccelerateMod_gr_2.gif], where [Graphics:Images/NewtonAccelerateMod_gr_3.gif].  If   [Graphics:Images/NewtonAccelerateMod_gr_4.gif], then there exists a [Graphics:Images/NewtonAccelerateMod_gr_5.gif] such that the sequence [Graphics:Images/NewtonAccelerateMod_gr_6.gif] defined by the iteration  

    [Graphics:Images/NewtonAccelerateMod_gr_7.gif]    for    [Graphics:Images/NewtonAccelerateMod_gr_8.gif]  

will converge to [Graphics:Images/NewtonAccelerateMod_gr_9.gif] for any initial approximation  [Graphics:Images/NewtonAccelerateMod_gr_10.gif].  

Proof  Newton-Raphson Method  Newton-Raphson Method  

 

Definition (Order of a Root)  Assume that  f(x)  and its derivatives  [Graphics:Images/NewtonAccelerateMod_gr_11.gif]  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  

    
[Graphics:Images/NewtonAccelerateMod_gr_12.gif].  

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  [Graphics:Images/NewtonAccelerateMod_gr_13.gif] converges to  p,  and set  [Graphics:Images/NewtonAccelerateMod_gr_14.gif].    If two positive constants  [Graphics:Images/NewtonAccelerateMod_gr_15.gif]  exist, and  

    
[Graphics:Images/NewtonAccelerateMod_gr_16.gif]

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  [Graphics:Images/NewtonAccelerateMod_gr_17.gif]  are given special  consideration.

(i)   If  [Graphics:Images/NewtonAccelerateMod_gr_18.gif], the convergence of  [Graphics:Images/NewtonAccelerateMod_gr_19.gif]  is called linear.

(ii)  If  [Graphics:Images/NewtonAccelerateMod_gr_20.gif], the convergence of  [Graphics:Images/NewtonAccelerateMod_gr_21.gif]  is called quadratic.

 

Theorem (Convergence Rate for Newton-Raphson Iteration)  Assume that Newton-Raphson iteration produces a sequence  [Graphics:Images/NewtonAccelerateMod_gr_22.gif] that converges to the root  p  of the function  [Graphics:Images/NewtonAccelerateMod_gr_23.gif].  

If  p  is a simple root, then convergence is quadratic and  [Graphics:Images/NewtonAccelerateMod_gr_24.gif]  for  k  sufficiently large.

If  p  is a multiple root of order  m,  then convergence is linear and  [Graphics:Images/NewtonAccelerateMod_gr_25.gif]  for  k  sufficiently large.

Proof  Newton-Raphson Method  Newton-Raphson Method  

 

Algorithm (Newton-Raphson Iteration).  To find a root of  [Graphics:Images/NewtonAccelerateMod_gr_26.gif]  given an initial approximation  [Graphics:Images/NewtonAccelerateMod_gr_27.gif]  using the iteration  

    [Graphics:Images/NewtonAccelerateMod_gr_28.gif]   for    [Graphics:Images/NewtonAccelerateMod_gr_29.gif].

Computer Programs  Newton-Raphson Method  Newton-Raphson Method  

Mathematica Subroutine (Newton-Raphson Iteration).

[Graphics:Images/NewtonAccelerateMod_gr_30.gif]

Example 1.  Use Newton's method to find the roots of the cubic polynomial  [Graphics:Images/NewtonAccelerateMod_gr_31.gif].  
1 (a) Fast Convergence.  Investigate quadratic convergence at the simple root  [Graphics:Images/NewtonAccelerateMod_gr_32.gif],  using the starting value  [Graphics:Images/NewtonAccelerateMod_gr_33.gif]
1 (b) Slow Convergence.  Investigate linear convergence at the double root  [Graphics:Images/NewtonAccelerateMod_gr_34.gif],  using the starting value  [Graphics:Images/NewtonAccelerateMod_gr_35.gif]
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  [Graphics:Images/NewtonAccelerateMod_gr_112.gif]  of order   [Graphics:Images/NewtonAccelerateMod_gr_113.gif].  Then the accelerated Newton-Raphson formula

    [Graphics:Images/NewtonAccelerateMod_gr_114.gif]    for    [Graphics:Images/NewtonAccelerateMod_gr_115.gif]  

will produce a sequence [Graphics:Images/NewtonAccelerateMod_gr_116.gif] that converges quadratically to  p.  

Proof  Accelerated & Modified Newton-Raphson  Accelerated & Modified Newton-Raphson  

 

Computer Programs  Accelerated & Modified Newton-Raphson  Accelerated & Modified Newton-Raphson  

Mathematica Subroutine (Accelerated Newton-Raphson Iteration).

[Graphics:Images/NewtonAccelerateMod_gr_117.gif]

Example 2.  Use the accelerated Newton's method to find the double root  [Graphics:Images/NewtonAccelerateMod_gr_118.gif],  of the cubic polynomial  [Graphics:Images/NewtonAccelerateMod_gr_119.gif].  Use the starting value  [Graphics:Images/NewtonAccelerateMod_gr_120.gif]
Solution 2.

 

Example 3.  Use the accelerated Newton's method to find the double root  [Graphics:Images/NewtonAccelerateMod_gr_158.gif],  and triple root   [Graphics:Images/NewtonAccelerateMod_gr_159.gif],  of the cubic polynomial  [Graphics:Images/NewtonAccelerateMod_gr_160.gif].  
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
     
         
[Graphics:Images/NewtonAccelerateMod_gr_223.gif]

where  [Graphics:Images/NewtonAccelerateMod_gr_224.gif].  In this situation, the function  h(x)  is defined by

        [Graphics:Images/NewtonAccelerateMod_gr_225.gif]

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  [Graphics:Images/NewtonAccelerateMod_gr_226.gif]  of multiplicity   [Graphics:Images/NewtonAccelerateMod_gr_227.gif].  Then the modified Newton-Raphson formula

    [Graphics:Images/NewtonAccelerateMod_gr_228.gif]     
    
which can be simplified as

        for    [Graphics:Images/NewtonAccelerateMod_gr_230.gif]  

will produce a sequence [Graphics:Images/NewtonAccelerateMod_gr_231.gif] that converges quadratically to  p.  

Proof  Accelerated & Modified Newton-Raphson  Accelerated & Modified Newton-Raphson  

 

Computer Programs  Accelerated & Modified Newton-Raphson  Accelerated & Modified Newton-Raphson  

Mathematica Subroutine (Modified Newton-Raphson Iteration).

[Graphics:Images/NewtonAccelerateMod_gr_232.gif]

Example 4.  Use the modified Newton's method to find the double root  [Graphics:Images/NewtonAccelerateMod_gr_233.gif],  of the cubic polynomial  [Graphics:Images/NewtonAccelerateMod_gr_234.gif].  Use the starting value  [Graphics:Images/NewtonAccelerateMod_gr_235.gif]
Solution 4.

 

Example 5.  Use the modified Newton's method to find the double root  [Graphics:Images/NewtonAccelerateMod_gr_274.gif],  and triple root   [Graphics:Images/NewtonAccelerateMod_gr_275.gif],  of the cubic polynomial  [Graphics:Images/NewtonAccelerateMod_gr_276.gif].  
Solution 5.

 

Example 6.  Consider the function  [Graphics:Images/NewtonAccelerateMod_gr_334.gif].  
6 (a).  Use Newton's method to find the multiple root  [Graphics:Images/NewtonAccelerateMod_gr_335.gif].  
6 (b).  Use the accelerated Newton's method to find the multiple root  [Graphics:Images/NewtonAccelerateMod_gr_336.gif].  
6 (c).  Use the modified Newton's method to find the multiple root  [Graphics:Images/NewtonAccelerateMod_gr_337.gif].  
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