Derivation of the Error Estimate

Let r be a root of f[x] , let x[n] be the approximation to the root from the step n of Newton's method, and let e[n] = r - x[n] be the error at the step n. Our objective will be to express e[n+1] in terms of e[n]. According to our Newton's method approximation,

In[24]:=

  Clear[f,x,n]
  linearEqn = 
  	0 == tangent[x[n+1], x[n]]

Out[24]=

  0 == f[x[n]] + (-x[n] + x[1 + n]) f'[x[n]]

We want to compare this with our exact solution, which is a root of f. The tangent line equation above looks something like Taylor's formula. Expanding f in a Taylor series about x[n],

In[25]:=

  Clear[f,t,x,n]
  seriesEqn1 =
  	f[t] == Series[f[t], {t,x[n],2}]

Out[25]=

                                                              2
                                          f''[x[n]] (t - x[n])
  f[t] == f[x[n]] + f'[x[n]] (t - x[n]) + --------------------- + 
                                                    2
   
                3
     O[t - x[n]]

We can get 0 on the left hand side of the series equation by substituting r for t.

In[26]:=

  seriesEqn2 = seriesEqn1 //.{t -> r, f[r] -> 0}

Out[26]=

                                                           2
                                       f''[x[n]] (r - x[n])
  0 == f[x[n]] + f'[x[n]] (r - x[n]) + --------------------- + 
                                                 2
   
                3
     O[r - x[n]]

Subtracting the tangent line equation from the series equation; that is, subtracting the approximate from the exact, we get

In[27]:=

  errorEqn1 =
  	Simplify[seriesEqn2[[2]] - linearEqn[[2]] == 0]

Out[27]=

  (x[n] - x[1 + n]) f'[x[n]] + f'[x[n]] (r - x[n]) + 
   
                         2
     f''[x[n]] (r - x[n])               3
     --------------------- + O[r - x[n]]  == 0
               2

We can factor f'[x[n]] from the first two terms, but we will need to drop the O[r - x[n]]^3 term.

In[28]:=

  errorEqn2 =
  	Collect[ errorEqn1[[1]]//Normal, f'[x[n]] ]  == 0

Out[28]=

                                      2
                            (r - x[n])  f''[x[n]]
  (r - x[1 + n]) f'[x[n]] + --------------------- == 0
                                      2

Substituting our definition for e[n] = r - x[n],

In[29]:=

  errorEqn3 = errorEqn2 /.
  			{(r - x[n]) -> e[n], (r - x[n+1]) -> e[n+1]}

Out[29]=

                          2
                      e[n]  f''[x[n]]
  e[1 + n] f'[x[n]] + --------------- == 0
                             2

Finally, solving for e[n+1],

In[30]:=

  errorEstimate = Solve[errorEqn3, e[n+1]]

Out[30]=

                      2
                -(e[n]  f''[x[n]])
  {{e[1 + n] -> ------------------}}
                    2 f'[x[n]]

This error estimate is not quite correct, since we dropped the
O[r - x[n]]^3 term. We should replace f''[x[n]] with f''[a] for some a between r and x[n].

This analysis gives us the following theorem.

Theorem: If f, f', and f'' are continuous, f'[r] is not 0, and x[0] is sufficiently close to r, then Newton's method converges to the root.

Up to Error Analysis