The Bisection Method

Introduction to Data Science Finding Roots of Equation The Bisection Method

Now that you understand how polynomials are reduced, we can move on to the more intricate details of how the roots are found in the first place.

If you are familiar with the basics of data structures and algorithms, you would probably have come across a search algorithm known as binary search. The bisection method follows the same principles, such as:

Having a pre-defined interval consisting of an upper and lower bound.
Splitting the interval into two halves
Comparing the midpoint against the target value (or root in this case) to decide which half contains it.

One notable difference of the bisection method would be the continuous values of numerical roots in contrast to binary search which assumes the discrete values of indexed items. Thus, the algorithm would have to be terminated either once a certain threshold has been reached or after a set number of iterations.

Case Study:

In finance, options are a derivative asset class – which means that the price movements underlying security (typically stocks) affects it. Besides the price of the underlying, options are also affected by volatility and time-decay – the price of an option decreases as time passes up till its expiry date. This rate of price decay increases with time, hence it is typically not advised to hold an option until expiration.

As a boy from Bulgaria, Samuel P. wants to grow his wealth through trading options. Since he has limited capital, he decides that buying options for the sake of exercising them is not a good strategy. However, the greedy trader chooses to buy At-The-Money options (of this up-and-coming company called Gnome Mechanics Enterprise) as they are cheaper and provide more leverage.

For the sake of simplicity, assume that the price of an ATM option can be calculated by the function $f(x) = 12ln(-12x+12.18)-30$ , taking the expiration date to be day 0 (hence 120 days before expiration would be represented by x=-120).

Question:

At day -120, Samuel buys a call option at $57.50. Given that he can only afford to lose 10% of his capital, how long can he afford to hold his option without selling?

Minimum value of option allowed before selling

= $(100% – 10%)\cdot(57.50)$

= $ $51.75$

In order to find the number of days Samuel can afford to hold his option, we have to solve the equation $f(x)=51.75$ which is equivalent to finding the root of $f(x)-51.75=0$ .

Explanation

Above is the graph of $f(x)=sin(x)+3/(4x)$ . Given that there is no known analytical method of finding its roots, a numerical method will have to be used instead.

Part 1 – Determining the existence of a root

There are three conditions to determine the existence of a root numerically:

The function has to be continuous over the domain in question. Analytically, we know that $f$ is a continuous function for the domain $2.5 \leq x \leq 4.5$ , so this holds.
The function itself has to be known to calculate the upper and lower bounds. This condition is also fulfilled as we also know that $f(x)=sin(x)+3/(4x)$
The upper and lower bounds need to be of opposite signs. As $f(2.5)=0.898$ and $f(4.5)=-0.811<br />$ , the final condition is satisfied.

Therefore, we can conclude that a root exists in the domain $D_f=[2.5,4.5]$ over the function $f$

Part 2 – Calculating the root

This is the iterative part of the process. Given the lower and upper bounds of $f(2.5) and f(4.5)$ , the bisection method can be outlined as:

Select values for the upper and lower bounds, $l = 2.5, u = 4.5$ .
Calculate the midpoint $p=(l+u)/2$ .
If $f(p) = 0$ , then the root is found, $latex x = p $. Stop.
Else $f(p) \neq 0$
a. If $f(p) \cdot f(l) > 0 , l = p , u = u$
b. If $f(p) \cdot f(u) > 0 , l = l , u = p$
Repeat steps 2 to 4 until a pre-specified tolerance is satisfied or the maximum number of iterations is reached.

Based on the analytical method, there is a root at some point between $x=2.5$ and $x=4.5$ . We can label the lower bound $l=2.5$ and upper bound $u=4.5$ as shown in Figure 3.2 above.

Next, we calculate the midpoint of $l$ and $u$ , $p=(l+u)/2=3.5$ .

As $f(p)*f(u)>0$ , $u=p=3.5$ .

The process then repeats with $p=(l+u)/2=3$ , generating the following set of values with each iteration:

Iteration	l	u	p
1	2.5	4.5	3.5
2	2.5	3.5	3
3	3	3.5	3.25
4	3.25	3.5	3.375
5	3.25	3.375	3.3125
6	3.3125	3.375	3.34375
7	3.34375	3.375	3.359375
8	3.359375	3.375	3.367188
9	3.359375	3.367188	3.363281
10	3.363281	3.367188	3.365234
11	3.365234	3.367188	3.366211

Efficiency

Notice that it took 11 iterations for the method to get an estimate that is correct to 3 decimal places, 3.366.

Although the Bisection Method is very simple and robust, it is not very efficient as the absolute error is halved with each iteration. As such, the method converges linearly which makes it slower compared to other methods (like the Newton-Rhapson Method).

Below is the iterative part of the bisection method implemented from first principles using kotlin:

				
					import kotlin.math.sin as sin

fun testFunction(x: Double):Double{
    return sin(x)+3/(4*x)
}

fun bisectionMethod(myFunction: (x: Double) -&gt; Double, lowerBound: Double, upperBound: Double, maxMargin: Double, maxIterations: Int): Double{
    var lower: Double = lowerBound
    var upper: Double = upperBound
    if (myFunction(lower)*myFunction(upper)&gt;0.0){
        return 0.0  // lower and upper bounds have the same sign
    }
    var mid: Double=(lower+upper)/2
    var iterations = 0
    while (upper-lower&gt;=maxMargin &amp;&amp; iterations0){
            upper = mid
        }
        else{
            lower = mid
        }
        iterations+=1
    }
    return mid
}

bisectionMethod(::testFunction, 2.5, 4.5, 0.001, 99)

Output:

In S2, the bisection method is implemented as the following:

				
					UnivariateRealFunction f = new AbstractUnivariateRealFunction() {
 @Override
 public double evaluate(double x) {
 return x * Math.sin(x) - 3; // x * six(x) - 3 = 0
 }
};
BisectionRoot solver = new BisectionRoot(1e-8, 30);
double root = solver.solve(f, 12., 14.);
double fx = f.evaluate(root);
System.out.println(String.format("f(%f) = %f", root, fx));

				
					import kotlin.math.sin as sin

fun testFunction(x: Double):Double{
    return sin(x)+3/(4*x)
}

fun bisectionMethod(myFunction: (x: Double) -&gt; Double, lowerBound: Double, upperBound: Double, maxMargin: Double, maxIterations: Int): Double{
    var lower: Double = lowerBound
    var upper: Double = upperBound
    if (myFunction(lower)*myFunction(upper)&gt;0.0){
        return 0.0  // lower and upper bounds have the same sign
    }
    var mid: Double=(lower+upper)/2
    var iterations = 0
    while (upper-lower&gt;=maxMargin &amp;&amp; iterations0){
            upper = mid
        }
        else{
            lower = mid
        }
        iterations+=1
    }
    return mid
}

bisectionMethod(::testFunction, 2.5, 4.5, 0.001, 99)

Previous Topic

Back to Lesson

Next Topic