Roots By Iterative Methods

The Newton-Raphson method is a powerful numerical technique for finding roots based on linear approximation. It uses an initial guess $x_0$ to approximate the solution of $f(x) = 0$.

Derivation

Let $c$ be the exact root ($f(c) = 0$) and $x_0$ be an initial estimate. The Newton-Raphson formula for a new estimate $x_1$ is derived by constructing the tangent to $f(x)$ at the point $P(x_0, f(x_0))$.

The slope of the tangent line at $P$ is given by the derivative $f'(x_0)$. From the geometry of the tangent line, we also have:

$f'(x_0) = \frac{f(x_0) - 0}{x_0 - x_1} = \frac{f(x_0)}{x_0 - x_1}$

Rearranging this equation to solve for $x_1$:

$x_0 - x_1 = \frac{f(x_0)}{f'(x_0)}$

$x_1 = x_0 - \frac{f(x_0)}{f'(x_0)}$

Repeating this process using $x_1$ as the new initial approximation gives:

$x_2 = x_1 - \frac{f(x_1)}{f'(x_1)}$

In general, the Newton-Raphson formula is:

$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} \quad (8.1)$

This formula iteratively improves the estimate until $x_n$ converges to the exact root $c$.

The Newton-Raphson method generally assumes that there is an interval $[a, b]$ where $f(a)$ and $f(b)$ have opposite signs ($f(a) \cdot f(b) < 0$), indicating a root exists within the interval.

Example 1

Use the Newton-Raphson method to perform three iterations to approximate the root of $f(x) = x^2 - 2x - 1$ in the interval $[2, 3]$, starting with $x_0 = 2$, correct to three decimal places.

Solution:

$f(x) = x^2 - 2x - 1$

$f'(x) = 2x - 2$

Check for root in the interval:

$f(2) = 2^2 - 2(2) - 1 = -1$

$f(3) = 3^2 - 2(3) - 1 = 2$

Since $f(2)f(3) < 0$, a root exists in $[2, 3]$.

Newton-Raphson formula: $x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$

Iteration 1:

$x_1 = x_0 - \frac{f(x_0)}{f'(x_0)} = 2 - \frac{f(2)}{f'(2)} = 2 - \frac{-1}{2} = 2.5$

Iteration 2:

$x_2 = x_1 - \frac{f(x_1)}{f'(x_1)} = 2.5 - \frac{f(2.5)}{f'(2.5)} = 2.5 - \frac{0.25}{3} \approx 2.416667$

Iteration 3:

$x_3 = x_2 - \frac{f(x_2)}{f'(x_2)} \approx 2.416667 - \frac{f(2.416667)}{f'(2.416667)} \approx 2.416667 - \frac{0.006944}{2.833334} \approx 2.414214$

Thus, $x_3 \approx 2.414$ (correct to three decimal places).

Example 2

If $f(x) = \frac{\sin(x) - 1}{\cos(x)}$, show that the Newton-Raphson method leads to the recurrence formula $x_{n+1} = x_n + \cos(x_n)$.

Solution:

$f(x) = \frac{\sin(x) - 1}{\cos(x)}$

Using the quotient rule:

$f'(x) = \frac{\cos(x)\cos(x) - (\sin(x) - 1)(-\sin(x))}{\cos^2(x)} = \frac{\cos^2(x) + \sin^2(x) - \sin(x)}{\cos^2(x)} = \frac{1 - \sin(x)}{\cos^2(x)}$

Newton-Raphson formula:

$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} = x_n - \frac{\frac{\sin(x_n) - 1}{\cos(x_n)}}{\frac{1 - \sin(x_n)}{\cos^2(x_n)}} = x_n - \frac{\sin(x_n) - 1}{\cos(x_n)} \cdot \frac{\cos^2(x_n)}{1 - \sin(x_n)} = x_n + \cos(x_n)$

Example 3

Use the Newton-Raphson method to estimate the real root of $f(x) = x^3 + 2x^2 + 8x + 3 = 0$. Perform two iterations, starting with $x_0 = 0$, correct to three decimal places.

Solution:

$f(x) = x^3 + 2x^2 + 8x + 3$

$f'(x) = 3x^2 + 4x + 8$

Iteration 1:

$x_1 = x_0 - \frac{f(x_0)}{f'(x_0)} = 0 - \frac{3}{8} = -0.375$

Iteration 2:

$x_2 = x_1 - \frac{f(x_1)}{f'(x_1)} = -0.375 - \frac{f(-0.375)}{f'(-0.375)} = -0.375 - \frac{-0.08789}{-0.3125+8} \approx -0.375-\frac{-0.08789}{7.6875}\approx -0.3635$

or $-0.364$ to 3 d.p.

Example 4

Starting with $x_0 = 1$, find the solution of $f(x) = x - \cos(x) = 0$ in the interval $[0, \frac{\pi}{2}]$ using the Newton-Raphson method, correct to six decimal places.

Solution:

$f(x) = x - \cos(x)$

$f'(x) = 1 + \sin(x)$

Newton-Raphson formula: $x_{n+1} = x_n - \frac{x_n - \cos(x_n)}{1 + \sin(x_n)}$

Iteration 1: $x_1 = 1 - \frac{1 - \cos(1)}{1 + \sin(1)} \approx 0.750364$

Iteration 2: $x_2 \approx 0.739113$

Iteration 3: $x_3 \approx 0.739085$

Iteration 4: $x_4 \approx 0.739085$

The solution is approximately $0.739085$.

The Newton-Raphson formula can be used to estimate the $n$th root and reciprocal of a number.

The $r$th root of a positive number

Let $x = \sqrt[r]{N}$, which implies $x^r = N$ or $x^r - N = 0$. We can define a function $f(x) = x^r - N$.

The general form is $f(x_n) = x_n^r - N$ (8.2)

Differentiating (8.2) gives $f'(x_n) = rx_n^{r-1}$ (8.3)

Substituting (8.2) and (8.3) into the Newton-Raphson formula $x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$:

$x_{n+1} = x_n - \frac{x_n^r - N}{rx_n^{r-1}} = x_n - \frac{x_n^r}{rx_n^{r-1}} + \frac{N}{rx_n^{r-1}} = x_n - \frac{x_n}{r} + \frac{N}{rx_n^{r-1}} = \frac{rx_n}{r} - \frac{x_n}{r} + \frac{N}{rx_n^{r-1}}$

$x_{n+1} = \frac{(r-1)x_n + \frac{N}{x_n^{r-1}}}{r} = \frac{1}{r}\left((r-1)x_n + \frac{N}{x_n^{r-1}}\right)$

Therefore, the $r$th root of a positive number $N$ is given by:

$x_{n+1} = \frac{1}{r}\left((r-1)x_n + \frac{N}{x_n^{r-1}}\right) \quad \text{for } r \ge 2.$

Example 1: Square root of 8

Show that the iterative formula $x_{n+1} = \frac{1}{2}\left(x_n + \frac{N}{x_n}\right)$ can be used to approximate the square root of $N$. Then, perform 3 iterations starting with $x_0 = 2.5$ to approximate $\sqrt{8}$.

Solution:

For the square root, $r = 2$. Substituting into the general formula:

$x_{n+1} = \frac{1}{2}\left((2-1)x_n + \frac{N}{x_n^{2-1}}\right) = \frac{1}{2}\left(x_n + \frac{N}{x_n}\right)$

Now, with $N = 8$ and $x_0 = 2.5$:

Iteration 1: $x_1 = \frac{1}{2}\left(2.5 + \frac{8}{2.5}\right) = \frac{1}{2}(2.5 + 3.2) = 2.85$

Iteration 2: $x_2 = \frac{1}{2}\left(2.85 + \frac{8}{2.85}\right) \approx \frac{1}{2}(2.85 + 2.8070) \approx 2.8285$

Iteration 3: $x_3 = \frac{1}{2}\left(2.8285 + \frac{8}{2.8285}\right) \approx \frac{1}{2}(2.8285 + 2.8284) \approx 2.82845 \approx 2.8284$

Therefore, $\sqrt{8} \approx 2.8284$.

Example 2: Cube root of 10

Use the Newton-Raphson method to find the cube root of 10 starting with $x_0 = 2$ by performing 4 iterations.

Solution:

$x_{n+1} = \frac{1}{3}\left(2x_n + \frac{10}{x_n^2}\right)$

Iteration 1: $x_1 = \frac{1}{3}\left(2(2) + \frac{10}{2^2}\right) = \frac{1}{3}(4 + 2.5) = \frac{6.5}{3} \approx 2.16667$

Iteration 2: $x_2 = \frac{1}{3}\left(2(2.16667) + \frac{10}{2.16667^2}\right) \approx \frac{1}{3}(4.33334 + 2.126) \approx 2.1531$ or $2.153$

Iteration 3: $x_3 \approx \frac{1}{3}\left(2(2.153) + \frac{10}{2.153^2}\right)\approx 2.15443$

Iteration 4: $x_4 \approx \frac{1}{3}\left(2(2.15443) + \frac{10}{2.15443^2}\right) \approx 2.15443$ or $2.154$

Therefore, $\sqrt[3]{10} \approx 2.1544$.

Example 3: 5th root of 99

Use the Newton-Raphson method to find the 5th root of 99 starting with $x_0 = 2$ by performing 5 iterations.

Solution:

$x_{n+1} = \frac{1}{5}\left(4x_n + \frac{99}{x_n^4}\right)$

Iteration 1: $x_1 = \frac{1}{5}\left(4(2) + \frac{99}{2^4}\right) = \frac{1}{5}(8 + 6.1875) \approx 2.8375$

Iteration 2: $x_2 \approx \frac{1}{5}\left(4(2.8375) + \frac{99}{2.8375^4}\right) \approx 2.5754$ or $2.575$

Iteration 3: $x_3 \approx \frac{1}{5}\left(4(2.575) + \frac{99}{2.575^4}\right) \approx 2.5104$ or $2.51$

Iteration 4: $x_4 \approx \frac{1}{5}\left(4(2.51) + \frac{99}{2.51^4}\right) \approx 2.5069$ or $2.507$

Iteration 5: $x_5 \approx \frac{1}{5}\left(4(2.507) + \frac{99}{2.507^4}\right) \approx 2.5068$ or $2.507$

Therefore, $\sqrt[5]{99} \approx 2.5068$.

Finding the reciprocal of a number using the Newton-Raphson formula

If $N$ is a non-zero number, its reciprocal is $\frac{1}{N}$. If $x$ is an approximation of the reciprocal, then $x \approx \frac{1}{N}$, or $Nx \approx 1$, which can be written as $f(x) = Nx - 1 = 0$.

The general formula is $f(x_n) = Nx_n - 1$ (8.4)

Differentiating (8.4) with respect to $x$:

$f'(x_n) = N \quad (8.5)$

Substituting (8.4) and (8.5) into the Newton-Raphson formula $x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$:

$x_{n+1} = x_n - \frac{Nx_n - 1}{N} = x_n - x_n + \frac{1}{N} = \frac{1}{N}$

This derivation is incorrect and does not give an iterative formula.

The correct derivation is as follows. We want to find the reciprocal of $N$, so we consider the function $f(x) = \frac{1}{x} - N$. Then $f'(x) = -\frac{1}{x^2}$. Applying the Newton-Raphson method:

$x_{n+1} = x_n - \frac{\frac{1}{x_n} - N}{-\frac{1}{x_n^2}} = x_n + x_n^2\left(\frac{1}{x_n} - N\right) = x_n + x_n - Nx_n^2 = 2x_n - Nx_n^2 = x_n(2 - Nx_n)$

Thus, the correct iterative formula is:

$x_{n+1} = x_n(2 - Nx_n)$

Example 1: Reciprocal of 2.5

Use the Newton-Raphson method to find the reciprocal of 2.5 starting with $x_0 = 0.3$ by performing 3 iterations.

Solution:

$N = 2.5$, $x_0 = 0.3$

Formula: $x_{n+1} = x_n(2 - 2.5x_n)$

Iteration 1: $x_1 = 0.3(2 - 2.5 \times 0.3) = 0.3(2 - 0.75) = 0.3(1.25) = 0.375$

Iteration 2: $x_2 = 0.375(2 - 2.5 \times 0.375) = 0.375(2 - 0.9375) = 0.375(1.0625) = 0.3984375$

Iteration 3: $x_3 = 0.3984375(2 - 2.5 \times 0.3984375) = 0.3984375(2 - 0.99609375) = 0.3984375(1.00390625) \approx 0.4000$ or $0.4$

The approximate reciprocal of 2.5 is $0.4$.

Example 2: Reciprocal of $\frac{19}{7}$

Use the Newton-Raphson method to find the reciprocal of $\frac{19}{7}$ by performing five iterations using $x_0 = 2$ as an initial guess.

Solution:

$N = \frac{19}{7} \approx 2.714286$, $x_0 = 2$

Formula: $x_{n+1} = x_n(2 - \frac{19}{7}x_n)$

Iteration 1: $x_1 = 2(2 - \frac{19}{7} \times 2) = 2(2-5.42857) = -6.85714$

This is incorrect, the initial guess is too far from the actual reciprocal which is $\frac{7}{19}\approx 0.3684$. We will use an initial guess of $0.3$.

Using $x_0 = 0.3$:

Iteration 1: $x_1 = 0.3(2 - \frac{19}{7} \times 0.3) = 0.3(2-0.814286) = 0.355714$ or $0.356$

Iteration 2: $x_2 = 0.356(2 - \frac{19}{7} \times 0.356) \approx 0.3678$ or $0.368$

Iteration 3: $x_3 \approx 0.3684$ or $0.368$

Iteration 4: $x_4 \approx 0.3684$ or $0.368$

Iteration 5: $x_5 \approx 0.3684$ or $0.368$

The reciprocal of $\frac{19}{7}$ is $\frac{7}{19} \approx 0.3684$.

The secant method is similar to the Newton-Raphson method but uses two initial values and approximates the derivative using a finite difference (the slope of the secant line). The root is approximated using the secant line through two points.

The slope of the secant line through points $A(x_{n-1}, f(x_{n-1}))$ and $B(x_n, f(x_n))$ approximates the derivative at $x_n$:

$f'(x_n) \approx \frac{f(x_n) - f(x_{n-1})}{x_n - x_{n-1}} \quad (8.6)$

Substituting (8.6) into the Newton-Raphson formula $x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$ gives the secant formula:

$x_{n+1} = x_n - \frac{f(x_n)}{\frac{f(x_n) - f(x_{n-1})}{x_n - x_{n-1}}} = x_n - f(x_n)\frac{x_n - x_{n-1}}{f(x_n) - f(x_{n-1})}$

for $n = 1, 2, 3, \ldots$

Example 1

Using the secant formula with $x_0 = 1.5$ and $x_1 = 1$, find the root of the function $f(x) = x^2 - 2 = 0$ to four decimal places by performing 3 iterations.

Solution:

$f(x) = x^2 - 2$

Iteration 1 ($n=1$):

$x_2 = x_1 - f(x_1)\frac{x_1 - x_0}{f(x_1) - f(x_0)} = 1 - (-1)\frac{1 - 1.5}{-1 - 0.25} = 1 - (-1)\frac{-0.5}{-1.25} = 1 - 0.4 = 1.4$

Iteration 2 ($n=2$):

$x_3 = x_2 - f(x_2)\frac{x_2 - x_1}{f(x_2) - f(x_1)} = 1.4 - (1.4^2 - 2)\frac{1.4 - 1}{(1.4^2 - 2) - (-1)} = 1.4 - (1.96-2)\frac{0.4}{-0.04+1}=1.4-(-0.04)\frac{0.4}{0.96} = 1.4 + \frac{0.016}{0.96}\approx 1.4 + 0.016667 \approx 1.4167$

Iteration 3 ($n=3$):

$x_4 = x_3 - f(x_3)\frac{x_3 - x_2}{f(x_3) - f(x_2)} = 1.4167 - (1.4167^2 - 2)\frac{1.4167 - 1.4}{(1.4167^2 - 2) - (1.4^2-2)} \approx 1.4167 - (0.0070)\frac{0.0167}{0.0070-(-0.04)}\approx 1.4167 - (0.0070)\frac{0.0167}{0.0470}\approx 1.4167-0.0025\approx 1.4142$

The root is approximately $1.4142$.

Example 2

Use the secant method to estimate the root of $f(x) = e^{-x} - x$. Perform 3 iterations with initial estimates of $x_0 = 0$ and $x_1 = 1$. In each iteration, find the percentage relative error if the true root is $0.56714329$.

Solution:

$f(x) = e^{-x} - x$

Iteration 1 ($n=1$):

$x_2 = 1 - (e^{-1} - 1)\frac{1 - 0}{(e^{-1} - 1) - (e^0 - 0)} = 1 - (0.36788-1)\frac{1}{0.36788-1-1} = 1-\frac{-0.63212}{-1.63212}\approx 1-0.3873 = 0.6127$

Percentage relative error: $\frac{|0.56714329 - 0.6127|}{0.56714329} \times 100\% \approx 8.03\%$

Iteration 2 ($n=2$):

$x_3 = 0.6127 - (e^{-0.6127} - 0.6127)\frac{0.6127-1}{(e^{-0.6127} - 0.6127)-(e^{-1}-1)}\approx 0.6127-(0.5428-0.6127)\frac{-0.3873}{0.5428-0.6127-0.3678+1}\approx 0.6127-(-0.0699)\frac{-0.3873}{0.5623}\approx 0.6127-0.0481\approx 0.5646$

Percentage relative error: $\frac{|0.56714329 - 0.5646|}{0.56714329} \times 100\% \approx 0.45\%$

Iteration 3 ($n=3$):

$x_4\approx 0.5671$

Percentage relative error: $\frac{|0.56714329 - 0.5671|}{0.56714329} \times 100\% \approx 0.0076\%$

Example 3

Use the secant formula in four iterations to obtain an approximation of the root of the equation $f(x) = x^2 - 2x - 1 = 0$ if it lies between $x_0 = 2$ and $x_1 = 3$.

Iteration 1: $x_2 = 3 - (3^2-2(3)-1)\frac{3-2}{(3^2-2(3)-1)-(2^2-2(2)-1)} = 3 - 2\frac{1}{2-(-1)} = 3-\frac{2}{3} = \frac{7}{3}\approx 2.3333$

Iteration 2: $x_3 \approx 2.4$

Iteration 3: $x_4 \approx 2.4146$

Iteration 4: $x_5 \approx 2.4142$