The Algorithm for Newton's Method for Approximating Roots

# The Algorithm for Newton's Method for Approximating Roots

We will now look at the algorithm for Newton's Method for approximating roots to functions.

Obtain a function $f$ and assume that a root $\alpha$ exists. Obtain an initial approximation $x_0$ to this root. Also obtain a maximum number of iterations allowed and an error tolerance $\epsilon$.

For $i = 1, 2, ...$ up to the maximum number of iterations prescribed:

Step 1: Obtain the successive approximations of the root $\alpha$ with the following formula:

(1)
\begin{align} \quad x_i = x_{i-1} - \frac{f(x_{i-1})}{f'(x_{i-1})} \end{align}

Step 2: Check the error tolerance:

(2)
\begin{align} \quad \mid x_n - x_{n-1} \mid < \epsilon \end{align}

If the above inequality does not hold, then continue to obtain successive approximations for $\alpha$. If the above inequality is true, then further verify the accuracy of $x_n$. Check that to see whether or not:

(3)
\begin{align} \quad f(x_n + \epsilon) \cdot f(x_n - \epsilon) < 0 \end{align}

If the signs of $f(x_n + \epsilon)$ and $f(x_n - \epsilon)$ are opposites of each other, then the accuracy of $x_n$ is verified and stop the algorithm. $x_n$ is a good approximation to $\alpha$. If the signs of $f(x_n + \epsilon)$ and $f(x_n - \epsilon)$ are the same, then $\alpha$ is not contained in the small interval $[x_n - \epsilon, x_n + \epsilon]$. Print out an error message.

If the maximum number of iterations is reached, then print our a failure message.