Error Estimation and Error Verification of Newton's Method

Let $f$ be a function that satisfies the conditions to apply Newton's Method and converges to the root $\alpha$. We will now develop a way to estimate the error of the approximation iterates $x_n$ (obtained from Newton's Method) from the root $\alpha$. Note that since $\alpha$ is a root of $f$, then $f(\alpha) = 0$ and thus by the Mean Value Theorem, for some $\xi_n$ between $x_n$ and $\alpha$, we have that:

(1)

\begin{align} \quad f(x_n) = f(x_n) - f(\alpha) = f'(\xi_n)(x_n - \alpha) \\ \quad (x_n - \alpha) = \frac{f(x_n)}{f'(\xi_n)} \\ \quad \alpha - x_n = - \frac{f(x_n)}{f'(\xi_n)} \end{align}

The exact error is given above, however, we don't necessary know what $\xi_n$ is. Instead, let's find a suitable value to replace $\xi_n$ with. Suppose that $x_n$ is close to $\alpha$. Then $\xi_n$ is close to $x_n$ since $\xi_n$ is between $x_n$ and $\alpha$ and thus the error is approximated as:

(2)

\begin{align} \quad \alpha - x_n \approx - \frac{f(x_n)}{f'(x_n)} \end{align}

Now recall that the general iteration formula for Newton's Method is $x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$ and so $-\frac{f(x_n)}{f'(x_n)} = x_{n+1} - x_n$. Substituting this into our error approximation above and we get that:

(3)

\begin{align} \quad \alpha - x_n \approx x_{n+1} - x_n \end{align}

Therefore if we are given an allowable error of $\epsilon$, then if we can ensure that $x_{n+1} - x_n < \epsilon$ then it's likely that the error between $x_n$ and $\alpha$ is less than $\epsilon$ or almost less than $\epsilon$.

Error Verification

We saw above that the error between the root $\alpha$ and our approximation $x$ is approximately equal to $x_{n+1} - x_n$ however, if $x_{n+1} - x_n < \epsilon$ then it is possible that $\alpha - x_n > \epsilon$ still.

To verify that $x_{n+1} - x_n < \epsilon$, we can test to see whether $f(x_n - \epsilon) \cdot f(x_n + \epsilon) < 0$. If so, then we know that a root $\alpha$ exists between them and i within $\epsilon$ of our approximation $x_n$.