Applying Newton's Method

Be sure to review the following pages regarding Newton's Method:

• Newton's Method for Approximating Roots
• Error Estimation and Error Verification of Newton's Method
• The Convergence of Newton's Method

We will now look at an examples of approximating a root with Newton's Method, approximating and verifying the error in our approximations, and then verifying the convergence of this method.

Example 1

Show that there exists a root $\alpha \in (1.5, 2)$ for the function $f(x) = x^3 - 2x - 1$, and use Newton's Method with an initial approximation of $x_0 = 1.75$ until the approximations $x_n$ of $\alpha$ are accurate to four significant digits. Verify the accuracy in $x_n$ and verify the condition $M \mid x_0 - \alpha \mid < 1$ where $M = \max_{1.5 ≤ x ≤ 2} \biggr \rvert \frac{f''(x)}{2f'(x)} \biggr \rvert$ that ensures convergence of Newton's Method with the given initial approximation.

We will first show that a root $\alpha \in (1.5, 2)$ exists for $f(x) = x^3 - 2 - 1$. Note that $f$ is continuous on all of $\mathbb{R}$ and thus continuous on the interval $[1.5, 2]$. Also we have that $f(1.5) = (1.5)^3 - 2(1.5) - 1 = -0.625 < 0$ and $f(2) = (2)^3 - 2(2) - 1 = 3 > 0$. Thus $f(1.5) \cdot f(2) < 0$ and so a root $\alpha$ exists in $(1.5, 2)$.

Now we will set up Newton's Method. We note that $f(x) = x^3 - 2x - 1$ and so $f'(x) = 3x^2 - 2$. For $n ≥ 0$, the iterative formula for Newton's Method is thus obtained as:

(1)

\begin{align} \quad x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} \\ \quad x_{n+1} = x_n - \frac{x_n^3 - 2x_n - 1}{3x_n^2 - 2} \end{align}

The first iteration computes the approximation $x_1$ of $\alpha$ using the initial approximation $x_0 = 1.75$:

(2)

\begin{align} \quad x_1 = x_0 - \frac{x_0^3 - 2x_0 - 1}{3x_0^2 - 2} \\ \quad x_1 = 1.75 - \frac{(1.75)^3 - 2(1.75) - 1}{3(1.75)^2 - 2} \\ \quad x_1 \approx 1.63043478… \end{align}

The second iteration computes the approximation $x_2$ of $\alpha$ using the approximation $x_1 = 1.63043478$:

(3)

\begin{align} \quad x_2 = x_1 - \frac{x_1^3 - 2x_1 - 1}{3x_1^2 - 2} \\ \quad x_2 = 1.63043478- \frac{(1.63043478)^3 - 2(1.63043478) - 1}{3(1.63043478)^2 - 2} \\ \quad x_2 \approx 1.61815955... \end{align}

The third iteration computes the approximation $x_3$ of $\alpha$ using the approximation $x_2 = 1.63043478$:

(4)

\begin{align} \quad x_3 = x_2 - \frac{x_2^3 - 2x_2 - 1}{3x_2^2 - 2} \\ \quad x_3 = 1.61815955- \frac{(1.61815955)^3 - 2(1.61815955) - 1}{3(1.61815955)^2 - 2} \\ \quad x_3 \approx 1.618034001... \end{align}

Note that $\mid x_3 - x_2 \mid = \mid 1.618034001 - 1.61815955 \mid = 0.000125549$. We want to approximate $\alpha$ to four significant digits. We see that we thus want our error $\epsilon$ to be $\epsilon = \frac{1}{2} \cdot 10^{-3} = 0.0005$. We have that $\mid x_3 - x_2 \mid ≤ \epsilon$, so we will stop the iterations.

We will now verify the accuracy of our approximations by bowing that a root $\alpha$ exists between $x_3 - \epsilon$ and $x_3 + \epsilon$. Note that:

(5)

\begin{align} \quad f(x_3 - \epsilon) = f(1.618034001 - 0.0005) = f(1.617534001) = -0.00292576592… < 0 \\ \quad f(x_3 + \epsilon) = f(1.618034001 + 0.0005) = f(1.618534001) = 0.0029283364… > 0 \end{align}

Since $f(x_3 - \epsilon)f(x_3 + \epsilon) < 0$ we have that a root $\alpha \in (x_3 - \epsilon, x_3 + \epsilon)$ which verifies the accuracy of our approximation $x_3$ with at least four significant digits.

We will now verify the condition for convergence such that $M \mid x_0 - \alpha \mid < 1$ where $M = \max_{1.5 ≤ x ≤ 2} \biggr \rvert \frac{f''(x)}{2f'(x)} \biggr \rvert$. We first note that since $x_0 = 1.75 \in (1.5, 2)$ then $\mid x_0 - \alpha \mid$ is going to be less than half of the length of the interval $(1.5, 2)$, that is $\mid x_0 - \alpha \mid < \frac{1}{2} (2 - 1.5) = \frac{1}{4}$.

Now note that $f''(x) = 6x$ and so:

(6)

\begin{align} \quad M = \max_{1.5 ≤ x ≤ 2} \biggr \rvert \frac{f''(x)}{2f'(x)} \biggr \rvert = \max_{1.5 ≤ x ≤ 2} \biggr \rvert \frac{6x}{2(3x^2 - 2)} \biggr \rvert = \max_{1.5 ≤ x ≤ 2} \frac{6x}{6x^2 - 4} = \max_{1.5 ≤ x ≤ 2} \frac{3x}{3x^2 - 2} \end{align}

We can maximize the function above by maximize the numerator and minimizing the denominator for $1.5 ≤ x ≤ 2$ and so:

(7)

\begin{align} \quad M = \frac{\max_{1.5 ≤ x ≤ 2} 3x}{\min_{1.5 ≤ x ≤ 2} 3x^2 - 2} \end{align}

Both the numerator and denominator are continuous on all of $\mathbb{R}$ and hence continuous for $1.5 ≤ x ≤ 2$. The function in the numerator is increasing on this interval so the maximum is obtained at the right endpoint. The function in the denominator is increasing on this interval as well, so the minimum is obtained at the left endpoint and so:

(8)

\begin{align} \quad M = \frac{3(2)}{3(1.5)^2 - 2} = \frac{6}{4.75} \approx 1.26315789… \end{align}

And so we have that:

(9)

\begin{align} \quad M \mid x_0 - \alpha \mid = 1.26315789 \left ( \frac{1}{4} \right ) < 1 \end{align}

Thus we have verified the condition for the convergence of Newton's Method in this example with the initial approximation $x_0 = 1.75$.