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.

Expand    in a Taylor polynomial of degree n = 1, about    to get  

        .  

Since    is a zero of  ,  set    in the above equation and obtain

        .  

Which can be rewritten as  

        .  

Now assume that    for all    near the root  ,  and observe that  , so that we can divide by it and obtain:

        .  

Rearrange the terms and simplify to get  

        .  

The above equation can be rewritten as:  

        .  

Now use the Newton-Raphson iteration formula    and substitute it into the above equation to obtain:  

        .  

Assuming     and      when k is sufficiently large yields  

        ,
    
        .

Now take absolute values and obtain the desired conclusion

        .

Q. E. D.

(c) John H. Mathews 2004