Module

for

Newton's Method

    If 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 Raphson (1648-1715).  

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  .  

Proof  Newton-Raphson Method  Newton-Raphson Method  

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 three roots of the cubic polynomial  .  
Determine the Newton-Raphson iteration formula    that is used.  Show details of the computations for the starting value  .
Solution 1.

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.

Proof  Newton-Raphson Method  Newton-Raphson Method  

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

Reduce the volume of printout.

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

  and  

Concise Program for the Newton-Raphson Method

Now test this subroutine using the function in Example 1.  

Error Checking in the Newton-Raphson Method

Error checking can be added to the Newton-Raphson method.  Here we have added a third parameter    to the subroutine which estimate the accuracy of the numerical solution.

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  .  By interrogating  k  afterward we can see how many iterations were actually performed.

Various Scenarios and Animations for Newton-Raphson Iteration.

Example 3. Fast Convergence  Find the solution to  .  Use the starting approximation  .  
Solution 3.

Example 4. Slow Convergence  Find the solution to  .  Use the starting approximation  .  
Solution 4.

Example 5. Convergence, Oscillation  Find the solution to  .  Use the starting approximation  .  
Solution 5.

Example 6. NON Convergence, Cycling  Find the solution to  .  Use the starting approximation  .  
Solution 6.

Example 7. NON Convergence, Diverging to Infinity  Find the solution to  .  Use the starting approximation  .  
Solution 7.

Example 8. NON Convergence, Divergent Oscillation  Find the solution to  .  Use the starting approximation  .  
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