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