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,


  Clear[f,x,n]
  linearEqn = 
  	0 == tangent[x[n+1], 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],


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

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


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

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


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

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


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

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


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

Finally, solving for e[n+1],


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

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