Objective

Create a function to find a root of a given polynomial function in a given interval.

Difficulty

Average

Description

Solving a polynomial is a common activity in the study of algebra and functions. Given a particular function ::f::, its solution is defined as those values in the domain such that ::f:: map each of them to ::0::.

In notational form, this means that if ::f(x) = 0::, then ::x:: is called a solution of the polynomial. Sometimes, it's also called the root of the polynomial.

For instance, given the polynomial ::f(x) = x^2 - 2x + 1::, it has only one solution which is ::x = 1::. But if given the polynomial ::f(x) = x^2 + 2x - 15::, it has two solutions, namely ::x = -5:: and ::x = 3::.

Programatically solving a given polynomial is an interesting activity. One simple and popular technique is the bisection method.

It finds a solution to a polynomial in a given interval by a divide-and-conquer strategy, i.e. continuously halving the interval until the difference between the end points (of the interval) is so small that we can safely end the computation there. At that point, the mid point of the interval is the root of the polynomial.

In more detail, the bisection method works as follows:

We are given an interval ::[a, b]:: which is merely a guess for an interval where a root of the polynomial might lie. We start by determining if there is a sign change in the interval.

If there is, then based on the fact that the function is continuous, this simply means that the function cuts through the x-axis and therefore has a root.

The way this root is found is as follows:

  • The midpoint ::m:: of the interval ::[a, b]:: is computed.
  • From the intervals ::[a, m]:: and ::[m, b]::, which ever has a sign change, that's used as the next interval.
  • Step 1 and step 2 is repeated until the absolute difference between ::a:: and ::b:: is less than a given value, usually denoted as ::\epsilon::.

Let's demonstrate the bisection method on the function ::f(x) = x^2 + 2x - 15:: and the interval ::[2, 10]::. We'll also suppose that ::\epsilon = 0.001::.

First, let's see whether there is a sign change in the interval for ::f::. Since ::f(2) = -7:: and ::f(10) = 105::, there is clearly a sign change and we can, likewise, proceed further.

Starting with the interval ::[2, 10]:::

  • The midpoint ::m:: of ::2:: and ::10:: is ::6::.
  • ::f(6) = 33::, likewise from the intervals ::[2, 6]:: and ::[6, 10]::, the former interval is the one where the sign change exists. Hence, we drop ::[6, 10]:: and proceed with ::[2, 6]::.

To the next iteration with the interval ::[2, 6]:::

  • The midpoint ::m:: of ::2:: and ::6:: is ::4::.
  • ::f(4) = 9::, likewise from the intervals ::[2, 4]:: and ::[4, 6]::, once again the former interval is the one where the sign change exists. Hence, we drop ::[4, 6]:: and proceed with ::[2, 4]::.

To the next iteration with the interval ::[2, 4]:::

  • The midpoint ::m:: of ::2:: and ::4:: is ::3::.
  • ::f(3) = 0::. Voila! We just found a root, i.e. ::x = 3::, and hence end the iterations.

In the case above, we hit an exact root while computing the midpoint of the given interval and had to likewise end the bisection method with that solution.

Note that this doesn't happen always — sometimes, the ::x:: values converge down to such numbers that the difference between them is less than or equal to ::\epsilon::. At that point, the midpoint of these very close values is termed as the root of the given polynomial.

In this exercise, you have to create a bisection() function in order to compute a root of a given polynomial function in a particular interval, if there is a root in the interval.

The polynomial function gets passed as the first argument to bisection(), while the second and third arguments represent the starting and ending points of the interval, respectively.

If there isn't a guarantee that there exists a root of the polynomial in the given interval, i.e. there is no sign change, the function bisection() must return null.

In addition to this, you must take ::\epsilon:: as ::0.0001:: in the function.

Following is an illustration of the usage of this function:

function f(x) { return x ** 2 + 2 * x - 15 }
undefined
bisection(f, 2, 10)
3
bisection(f, -6, -4)
-5
bisection(f, 3, 4)
3
bisection(f, -6, 10)
null
bisection(f, 100, 1000)
null
function f(x) { return (x - 1) * (x + 1) }
undefined
bisection(f, 0, 10)
1
bisection(f, -10, 0)
-1
bisection(f, -10, 10)
null
View Solution

New file

Inside the directory you created for this course on JavaScript, create a new folder called Exercise-10-Bisection-Method and put the .html solution files for this exercise within it.

Solution

First, let's decide on the naming of bisection()'s parameters:

  • The first argument is the polynomial function whose root we ought to find. A conventional name would be f.
  • The second argument is the starting point of the interval. In the discussion above, we called it ::a::, and although we could name it a in bisection() as well, we'll rather go with the name x1. That's because with x1, it'll be easier to name the corresponding y-value, i.e. y1.
  • On the same lines, we'll call the third argument x2.

This gives us the following definition:

function bisection(f, x1, x2) {
   // Code to go here...
}

Now, let's begin crafting the body of bisection().

It's a good programming practice to define constants right at the start of a script/function. In our case, the value of ::\epsilon:: is to be taken as 0.0001, and since this is a constant, we'll define it right at the start in bisection() as epsilon:

function bisection(f, x1, x2) {
   const epsilon = 0.0001;
}

Up next, we'll calculate the mappings of x1 and x2 (i.e. the corresponding y-values), namely y1 and y2, and then check whether either of them is 0.

If that is the case, it means that we're provided with a root of the polynomial function and hence should return that root, without executing any further.

This is accomplished below:

function bisection(f, x1, x2) {
   const epsilon = 0.0001;
   var y1 = f(x1);
   var y2 = f(x2);

   // If provided with a root, return that root.
   if (y1 === 0) {
      return x1;
   }
   if (y2 === 0) {
      return x2;
   }
}

The first step in bisection() is to determine whether there is a sign change in the given interval. This requires a simple if condition.

If there is no sign change, we assume the worst case that there is no root in the interval, and just return null:

function bisection(f, x1, x2) {
   const epsilon = 0.0001;
   var y1 = f(x1);
   var y2 = f(x2);

   // If provided with a root, return that root.
   if (y1 === 0) {
      return x1;
   }
   if (y2 === 0) {
      return x2;
   }

   // If there is no sign change in the interval [x1, x2],
   // return null.
   if (y1 * y2 > 0) {
      return null;
   }
}
When there is no sign change in a given interval, there still might be some roots in there. But the thing is that we can't be sure about this, and therefore to keep from running into a meaningless iteration, we return null.

If the if block above gets skipped, that simply means that there is a sign change in the interval and therefore there is surely at least one root to find.

Step one is to calculate the difference in the provided x1 and x2 values. If the difference is less than or equal to epsilon which is 0.0001, then this repetitive bisection must end.

Needless to say the idea of repetitively bisecting the given interval hints us at a loop, and specifically a while loop as we don't know the number of iterations to be performed. The loop's condition is simple — if the difference between x1 and x2 is greater than epsilon, we must continue with the bisection.

Thus far, we get to the following code:

function bisection(f, x1, x2) {
   const epsilon = 0.0001;
   var y1 = f(x1);
   var y2 = f(x2);

   // If provided with a root, return that root.
   if (y1 === 0) {
      return x1;
   }
   if (y2 === 0) {
      return x2;
   }

   // If there is no sign change in the interval [x1, x2],
   // return null.
   if (y1 * y2 > 0) {
      return null;
   }

   var xMid, yMid;
   var diff = Math.abs(x1 - x2);

   while (diff > epsilon) {
      // Code to go here...
   }
}

Note the use of Math.abs() in computing the difference between x1 and x2. It's necessary because we are only interested in how close are the given values together, not in the sign of the difference.

Inside the while loop, we first compute the mid point of x1 and x2, namely xMid, and then compute its mapping under the provided function f. We call this mapping of xMid as yMid.

After this, we check which interval has the sign change and then proceed with that interval for the next iteration, after recomputing the absolute difference between x1 and x2.

Here's the code accomplishing all of this:

function bisection(f, x1, x2) {
   const epsilon = 0.0001;
   var y1 = f(x1);
   var y2 = f(x2);

   // If provided with a root, return that root.
   if (y1 === 0) {
      return x1;
   }
   if (y2 === 0) {
      return x2;
   }

   // If there is no sign change in the interval [x1, x2],
   // return null.
   if (y1 * y2 > 0) {
      return null;
   }

   var xMid, yMid;
   var diff = Math.abs(x1 - x2);

   while (diff > epsilon) {
      xMid = (x1 + x2) / 2;
      yMid = f(xMid);

      // If the mid point is a root, return it.
      if (yMid === 0) {
         return xMid;
      }

      // Determine which of the intervals [x1, xMid] and [xMid, x2]
      // has the sign change, and then continue with that interval.
      if (y1 * yMid <= 0) {
         x2 = xMid;
      }
      else {
         x1 = xMid;
      }

      diff = Math.abs(x1 - x2);
   }

   // Code to go here...
}

In the end, we calculate the mid point of x1 and x2 again, based on their new values, and then round the result to 3 decimal places.

Here's the complete definition of bisection():

function bisection(f, x1, x2) {
   const epsilon = 0.0001;
   var y1 = f(x1);
   var y2 = f(x2);

   // If provided with a root, return that root.
   if (y1 === 0) {
      return x1;
   }
   if (y2 === 0) {
      return x2;
   }

   // If there is no sign change in the interval [x1, x2],
   // return null.
   if (y1 * y2 > 0) {
      return null;
   }

   var xMid, yMid;
   var diff = Math.abs(x1 - x2);

   while (diff > epsilon) {
      xMid = (x1 + x2) / 2;
      yMid = f(xMid);

      // If the mid point is a root, return it.
      if (yMid === 0) {
         return xMid;
      }

      // Determine which of the intervals [x1, xMid] and [xMid, x2]
      // has the sign change, and then continue with that interval.
      if (y1 * yMid <= 0) {
         x2 = xMid;
      }
      else {
         x1 = xMid;
      }

      diff = Math.abs(x1 - x2);
   }

   xMid = (x1 + x2) / 2
   return Number(xMid.toFixed(3));
}

Note the expression Number(xMid.toFixed(3)). xMid.toFixed(3) serves to round xMid to 3 decimal places and then return the result in the form of a string. Number() then converts this string into a number that can be returned by bisection().

And this completes the exercise.