Newton-Raphson Method

The Newton-Raphson method is an iterative technique for approximating a root of a polynomial $ p(x) $: $$ x_{n+1} = x_n - \frac{p(x_n)}{p'(x_n)} $$ where $ x_n $ represents the current estimate of the root, $ p(x) $ is the polynomial, and $ p'(x) $ is its derivative.

This numerical method is especially useful for finding a real (albeit approximate) root of a polynomial when no rational or integer solutions are evident.

The Newton-Raphson method is highly efficient and typically converges rapidly to a real root-particularly when the initial guess $ x_0 $ is sufficiently close to the actual solution.

A practical example

Let’s look at a concrete example of how to apply the Newton-Raphson method to find a real root of a polynomial.

Consider the polynomial $ p(x) = x^3 - x^2 - 1 $.

We begin by choosing an initial approximation. Let’s take: $$ x_0 = 1.5 $$

Next, we compute the derivative of the polynomial. For $ p(x) = x^3 - x^2 - 1 $, we have: $$ p'(x) = 3x^2 - 2x $$

Now we start the iterative process.

Iteration 1

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

$$ x_1 = 1.5 - \frac{(1.5)^3 - (1.5)^2 - 1}{3(1.5)^2 - 2(1.5)} $$

$$ x_1 = 1.5 - \frac{3.375 - 2.25 - 1}{6.75 - 3} $$

$$ x_1 = 1.5 - \frac{0.125}{3.75} $$

$$ x_1 = 1.5 - 0.0333 $$

$$ x_1 = 1.4667 $$

Iteration 2

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

$$ x_2 = 1.4667 - \frac{(1.4667)^3 - (1.4667)^2 - 1}{3(1.4667)^2 - 2(1.4667)} $$

$$ x_2 = 1.4667 - \frac{3.1550 - 2.1511 - 1}{6.4533 - 2.9333} $$

$$ x_2 = 1.4667 - \frac{0.0039}{3.5200} $$

$$ x_2 = 1.4667 - 0.001 $$

$$ x_2 = 1.4656 $$

Let’s now evaluate the difference between successive approximations:

$$ \epsilon = | x_2 - x_1 | = |1.4656 - 1.4667| = 0.001 $$

Note. Technically, the subtracted value-0.001-already represents the difference between the two approximations. So, computing it again is redundant. However, for clarity and instructional purposes, we’ve explicitly shown the calculation.

Iteration 3

$$ x_3 = x_2 - \frac{p(x_2)}{p'(x_2)} $$

$$ x_3 = 1.4656 - \frac{(1.4656)^3 - (1.4656)^2 - 1}{3(1.4656)^2 - 2(1.4656)} $$

$$ x_3 = 1.4656 - \frac{3.148 - 2.1479 - 1}{6.4439 - 2.9312} $$

$$ x_3 = 1.4656 - \frac{0.0001}{3.5127} $$

$$ x_3 = 1.4655 $$

And again, we compute the change between iterations:

$$ \epsilon = |x_3 - x_2| = |1.4655 - 1.4656| = 0.0001 $$

We continue this process until the difference between $ x_{n+1} $ and $ x_n $ falls below a predefined tolerance level-for instance, $ \epsilon < 0.001 $ or $ \epsilon < 0.0001 $.

Eventually, the sequence converges toward a real root of the polynomial $ p(x) $.

In this example, the value $ x \approx 1.4655 $ is already accurate enough to be considered a reliable approximation of the root.

Verification. Substituting $ x \approx 1.4655 $ back into the original polynomial $ p(x) = x^3 - x^2 - 1 $, we get: $$ p(1.4655) = 1.4655^3 - 1.4655^2 - 1 = -0.00025 $$ The result is very close to zero, confirming that we’re extremely close to the true root.

And so the process continues.