Module

for

Newton's Method

   

    If [Graphics:Images/Newton'sMethodMod_gr_1.gif] are continuous near a root [Graphics:Images/Newton'sMethodMod_gr_2.gif], then this extra information regarding the nature of [Graphics:Images/Newton'sMethodMod_gr_3.gif] can be used to develop algorithms that will produce sequences [Graphics:Images/Newton'sMethodMod_gr_4.gif] that converge faster to [Graphics:Images/Newton'sMethodMod_gr_5.gif] 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 [Graphics:Images/Newton'sMethodMod_gr_6.gif].  The method is attributed to Sir Isaac Newton (1643-1727) and Joseph Raphson (1648-1715).  

Theorem (Newton-Raphson Theorem).  Assume that [Graphics:Images/Newton'sMethodMod_gr_7.gif] and there exists a number [Graphics:Images/Newton'sMethodMod_gr_8.gif], where [Graphics:Images/Newton'sMethodMod_gr_9.gif].  If   [Graphics:Images/Newton'sMethodMod_gr_10.gif], then there exists a [Graphics:Images/Newton'sMethodMod_gr_11.gif] such that the sequence [Graphics:Images/Newton'sMethodMod_gr_12.gif] defined by the iteration  

    [Graphics:Images/Newton'sMethodMod_gr_13.gif]    for    [Graphics:Images/Newton'sMethodMod_gr_14.gif]  

will converge to [Graphics:Images/Newton'sMethodMod_gr_15.gif] for any initial approximation  [Graphics:Images/Newton'sMethodMod_gr_16.gif].  

Proof  Newton-Raphson Method  Newton-Raphson Method  

 

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

    [Graphics:Images/Newton'sMethodMod_gr_19.gif]   for    [Graphics:Images/Newton'sMethodMod_gr_20.gif].

 

Computer Programs  Newton-Raphson Method  Newton-Raphson Method  

 

Mathematica Subroutine (Newton-Raphson Iteration).

[Graphics:Images/Newton'sMethodMod_gr_21.gif]

Example 1.  Use Newton's method to find the three roots of the cubic polynomial  [Graphics:Images/Newton'sMethodMod_gr_22.gif].  
Determine the Newton-Raphson iteration formula  [Graphics:Images/Newton'sMethodMod_gr_23.gif]  that is used.  Show details of the computations for the starting value  [Graphics:Images/Newton'sMethodMod_gr_24.gif].
Solution 1.

 

Definition (Order of a Root)  Assume that  f(x)  and its derivatives  [Graphics:Images/Newton'sMethodMod_gr_97.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/Newton'sMethodMod_gr_98.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/Newton'sMethodMod_gr_99.gif] converges to  p,  and set  [Graphics:Images/Newton'sMethodMod_gr_100.gif].    If two positive constants  [Graphics:Images/Newton'sMethodMod_gr_101.gif]  exist, and  

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

(i)   If  [Graphics:Images/Newton'sMethodMod_gr_104.gif], the convergence of  [Graphics:Images/Newton'sMethodMod_gr_105.gif]  is called linear.

(ii)  If  [Graphics:Images/Newton'sMethodMod_gr_106.gif], the convergence of  [Graphics:Images/Newton'sMethodMod_gr_107.gif]  is called quadratic.

 

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

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

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

Proof  Newton-Raphson Method  Newton-Raphson Method  

 

Example 2.  Use Newton's method to find the roots of the cubic polynomial  [Graphics:Images/Newton'sMethodMod_gr_112.gif].  
2 (a) Fast Convergence.  Investigate quadratic convergence at the simple root  [Graphics:Images/Newton'sMethodMod_gr_113.gif],  using the starting value  [Graphics:Images/Newton'sMethodMod_gr_114.gif]
2 (b) Slow Convergence.  Investigate linear convergence at the double root  [Graphics:Images/Newton'sMethodMod_gr_115.gif],  using the starting value  [Graphics:Images/Newton'sMethodMod_gr_116.gif]
Solution 2.

 

Reduce the volume of printout.

After you have debugged you program and it is working properly, delete the unnecessary print statements  


[Graphics:Images/Newton'sMethodMod_gr_347.gif]  and  
[Graphics:Images/Newton'sMethodMod_gr_348.gif]

 

Concise Program for the Newton-Raphson Method

[Graphics:Images/Newton'sMethodMod_gr_349.gif]

Now test this subroutine using the function in Example 1.  

[Graphics:Images/Newton'sMethodMod_gr_350.gif]
[Graphics:Images/Newton'sMethodMod_gr_351.gif]

[Graphics:Images/Newton'sMethodMod_gr_352.gif]
[Graphics:Images/Newton'sMethodMod_gr_353.gif]
[Graphics:Images/Newton'sMethodMod_gr_354.gif]
[Graphics:Images/Newton'sMethodMod_gr_355.gif]

[Graphics:Images/Newton'sMethodMod_gr_356.gif]
[Graphics:Images/Newton'sMethodMod_gr_357.gif]
[Graphics:Images/Newton'sMethodMod_gr_358.gif]
[Graphics:Images/Newton'sMethodMod_gr_359.gif]

[Graphics:Images/Newton'sMethodMod_gr_360.gif]
[Graphics:Images/Newton'sMethodMod_gr_361.gif]
[Graphics:Images/Newton'sMethodMod_gr_362.gif]
[Graphics:Images/Newton'sMethodMod_gr_363.gif]

Error Checking in the Newton-Raphson Method

 

Error checking can be added to the Newton-Raphson method.  Here we have added a third parameter  [Graphics:Images/Newton'sMethodMod_gr_364.gif]  to the subroutine which estimate the accuracy of the numerical solution.

[Graphics:Images/Newton'sMethodMod_gr_365.gif]

The following subroutine call uses a maximum of 20 iterations, just to make sure enough iterations are performed.  However, it will terminate when the difference between consecutive iterations is less than  [Graphics:Images/Newton'sMethodMod_gr_366.gif].  By interrogating  k  afterward we can see how many iterations were actually performed.

[Graphics:Images/Newton'sMethodMod_gr_367.gif]
[Graphics:Images/Newton'sMethodMod_gr_368.gif]

[Graphics:Images/Newton'sMethodMod_gr_369.gif]
[Graphics:Images/Newton'sMethodMod_gr_370.gif]
[Graphics:Images/Newton'sMethodMod_gr_371.gif]
[Graphics:Images/Newton'sMethodMod_gr_372.gif]

Various Scenarios and Animations for Newton-Raphson Iteration.

[Graphics:Images/Newton'sMethodMod_gr_373.gif]

Example 3. Fast Convergence  Find the solution to  [Graphics:Images/Newton'sMethodMod_gr_374.gif].  Use the starting approximation  [Graphics:Images/Newton'sMethodMod_gr_375.gif].  
Solution 3.

 

Example 4. Slow Convergence  Find the solution to  [Graphics:Images/Newton'sMethodMod_gr_394.gif].  Use the starting approximation  [Graphics:Images/Newton'sMethodMod_gr_395.gif].  
Solution 4.

 

Example 5. Convergence, Oscillation  Find the solution to  [Graphics:Images/Newton'sMethodMod_gr_433.gif].  Use the starting approximation  [Graphics:Images/Newton'sMethodMod_gr_434.gif].  
Solution 5.

 

Example 6. NON Convergence, Cycling  Find the solution to  [Graphics:Images/Newton'sMethodMod_gr_454.gif].  Use the starting approximation  [Graphics:Images/Newton'sMethodMod_gr_455.gif].  
Solution 6.

 

Example 7. NON Convergence, Diverging to Infinity  Find the solution to  [Graphics:Images/Newton'sMethodMod_gr_484.gif].  Use the starting approximation  [Graphics:Images/Newton'sMethodMod_gr_485.gif].  
Solution 7.

 

Example 8. NON Convergence, Divergent Oscillation  Find the solution to  [Graphics:Images/Newton'sMethodMod_gr_514.gif].  Use the starting approximation  [Graphics:Images/Newton'sMethodMod_gr_515.gif].  
Solution 8.

 

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 Newton-Raphson Method

 

Return to Numerical Methods - Numerical Analysis

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(c) John H. Mathews 2004