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.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License