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  .  

Remark.  The function    defined by the formula  

        

is called the Newton-Raphson iteration formula.  Since  ,  it is easy to see that  .  Thus the Newton-Raphson iteration for finding the root of the equation  ,  is accomplished by finding the fixed point of the function  .  

Geometric construction.

Derivation.

Proof.

Corollary (Newton's Iteration for Finding Square Roots)  Assume that    is a real number ant let    be an initial approximation to  .  Define the sequence   using the recursive rule  

    .  

Then the sequence   converges to  ;  that is,  .  

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

    .  

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

Lemma  If the equation    has a root of order    at  ,  then there exists a continuous function    so that    can be expressed as the product  

    .  

Speed of Convergence

    The distinguishing property we seek is the following.  If  p  is a simple root of  f(x) = 0,  Newton's method will converge rapidly, and the number of accurate decimal places (roughly) doubles with each iteration.  On the other hand, if  p  is a multiple root, the error in each successive approximation is a fraction of the previous error.  To make this precise, we define the order of convergence.  This is a measure of how rapidly a sequence converges.

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.

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

    

will produce a sequence    that converges quadratically to  p.

 Return to Numerical Methods - Numerical Analysis

(c) John H. Mathews 2004