A Quick Recap

In the previous post, we delved into the Bisection Method and implemented our own version of the algorithm. In this post, we will build on top of that knowledge and move a step ahead towards a little bit more advanced method: Newton-Raphson Method.

If you have any questions regarding the intention of finding roots, what are roots, why do we need to understand numericals methods for root finding or why its important to even implement these algorithms, please go back to the previous post and read the introductory section of that post. That should answer most of your queries.

Before We Proceed

Before we begin our dive into Newton-Raphson Method, we need to clear our understanding of a few concepts. These are essential to grasp the method completely. If you already know about these concepts, feel free to move ahead. However, I'am assuming most of us are starting from scratch and don't have clear understanding of these concepts.

In this section, we will talk about slopes, what they mean, line equations, and Slope-point form of line equation.

What is slope?

Slope is how steep a line is. By comparing some lines on the graph, we can guess which line is comparatively steeper.

Remember, $y = f(x)$.

In the above graph, we can see visually that $y = 3x$ is steeper than $y = 2x$ and $y = x$. But how do we define the slope mathematically? Take a look at this graph:

Here, we can see that the slope can be defined using change in $x$ and change in $y$. A more mathematical term for slope is rate of change. Slope gives us the rate of change of a function, how much the value of $y$ increases as $x$ changes. For example, in $y = 2x$, if $x$ increases 1 unit, the value of $y$ increases 2 unit. Even if the change in $x$ is smaller than 1, this relationship will hold. So, a mathematical identity of slope can be defined as, "For every change in $x$, how much $y$ changes." This relationship can be written like this:$$\text{Slope, m} = \frac{\text{change in y}}{\text{change in x}} = \frac{y_2 - y_1}{x_2 - x_1}= \frac{\Delta y}{\Delta x}$$For a straight line, the slope $m$ is constant. This measures how steep the line is and how much $y$ changes with respect to $x$.

However, for a curve, the slope is not constant, it changes at different points. To measure the slope of a curve at a specific point (since curve's don't have constant slope), we use the concept of a tangent line. The tangent line is a straight line that touches the curve at a single point.

In the graph below, we can see that the slope is different at every point.

When we want to find the slope of a curve at a specific point, we begin by taking two points on the curve:

• $P(x_0, f(x_0))$: The point of interest.
• $Q(x_0 + h, f(x_0 + h))$: Another point close to $P$.

The line that passes through $P$ and $Q$ is called a secant line. Its slope is: $$m_{secant} = \frac{f(x_0 + h) - f(x_0)}{x_0 + h - x_0} = \frac{f(x_0 + h) - f(x_0)}{h}$$Here, $\\ x_0 = x_1 \\ x_0 + h = x_2 \\ f(x_0) = y_1 \\ f(x_0 + h) = y_2 \\ h = x_2 - x_1$, distance betwen the two points on x-axis

So, we can see that the formula for $m_{secant}$ is actually the general formula for slope that we derived from a straight line. Now, to make this slope represent the slope of the curve (instead of the secant line), we bring $Q$ closer and closer to $P$. Mathematically, this means: $$h \to 0, \text{ h tends to 0 or h is infinitly close to 0.}$$As $h$ gets smaller, the secant line becomes closer to the tangent line, which just "touches" the curve at $P$.

Take a look at the consecutive graphs as $Q$ gets closer to $P$

When $h=0$, $P$ and $Q$ merge into one point, and the secant becomes the tangent line. The slope of the tangent line is the limit of the secant slope as $h \to 0$: $$m_{tangent} = \lim_{h \to 0} \frac{f(x_0+h)−f(x_0)}{h}$$In the above expression, the value of $h$ never reaches zero as it will make the slope undefined. Instead, it is a value that is infinitly close to zero. This is the definition of the derivative, $f^{\prime}(x_0)$ which is basically $m_{tangent}$.

Now, let's define line equations.

Line Equations

Suppose, we have two points $A(x_1, y_1)$ and $B(x_2, y_2)$ on a straight line. Now, we want to find the general equation of the line so that any arbitrary value of $x$ gives us a point $P(x, y)$ that falls on that line.

To form the equation, we need minimum two points. A single point gives us a location but doesn't provide the direction (slope) of the line. To form the equation, we need to know the direction/slope of the line, $m$.

Now, if $A$, $B$ and $P$ are on the same line, then their slope will be constant and equal. Thus, we can say,

Here, $(1)$ is the general formula for line equation. We can see that the term $\frac{y_2 - y_1}{x_2 - x_1}$ is actually the slope of the line. This leads us to $(2)$, the slope-point form of line equation.

However, if the function $y = f(x)$ is a curve or any other function including lines, then the slope $m$ will be defined as $f^{\prime} (x)$. The derivative of the original function $f(x)$ is used as the general formula for any slope whether its a straight line or a curve. So, we can rewrite the last expression $(2)$ as,

Here, $(3)$ is the Tangent Line Equation (slope-point form of line equation).

Now, equiped with this knowledge, we will begin our dive into Newton-Raphson Method.

Introduction to Newton-Raphson Method

Newton-Raphson Method finds a root by repeatedly drawing the tangent line to a curve, using its x-intercept as the next better guess where the root might be.

Implementation

Below is the psuedocode for the implementation. Try to understand the steps and implement it on your own before looking at the solution.

1. Define the function f(x) that you want to find the root of.

2. Define the derivative fPrime(x) of the function f(x).

3. Input:
x0 - Initial guess
tolerance - Acceptable error in the root value
max_iteration - Maximum number of times the loops should run

4. Set xn = x0, xNext = xn

5. For i=0; i < max_iteration; i++ :
a. If fPrime(xn) = 0, then break loop can't divide by 0
b. Set xNext = xn - f(xn) / fPrime(xn)
c. If abs(xNext - nx) is smaller than tolerance, break loop, root found.

6. Return xn

Here's the implementation of Newton-Raphson Method in a few commonly used languages:

const f = x => Math.exp(-x) * (x ** 3 + x ** 2 - 1) + Math.sin(x);
const fPrime = x => Math.exp(-x) * ((3 * x ** 2 + 2 * x) - (x ** 3 + x ** 2 - 1)) + Math.cos(x);

function newtonRaphson(x0, tol = 1e-10, maxIter = 100) {
  let xn = x0;
  for (let i = 0; i < maxIter; i++) {
    const fx = f(xn), fpx = fPrime(xn);
    if (fpx === 0) return null;
    const xNext = xn - fx / fpx;
    if (Math.abs(xNext - xn) < tol) return xNext;
    xn = xNext;
  }
  console.log("Did not converge.");
  return null;
}

const root = newtonRaphson(1.5);
console.log("Root:", root);

Conclusion

The Newton-Raphson method stands out as one of the most powerful and widely-used techniques for finding roots of real-valued functions. Its speed and elegance lie in its use of both the function and its derivative, allowing it to converge rapidly when given a good initial guess. However, it's not without limitations—issues like division by zero, divergence, or poor initial estimates can hinder performance. To address these shortcomings, several modified versions of the Newton-Raphson method have been developed. For instance, Maehly's procedure, a stabilized version of the Newton-Raphson method designed specifically for finding complex roots of polynomials. Another example is Chebyshev's third-order method, a variant of Newton’s method that used cubic approximations. It looks like this: $$x_{n+1} = x_n - \frac{f(x_n)}{f^\prime(x_n)} \bigg( 1 + \frac{f(x_n) f^{\prime \prime}(x_n)}{2 f^\prime(x_n)^2} \bigg)$$You can look at the concept and derivation from here.