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.

**Explanation**

Above is the graph of . 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 is a continuous function for the domain , 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
- The upper and lower bounds need to be of opposite signs. As and , the final condition is satisfied.

Therefore, we can conclude that a root exists in the domain over the function

**Part 2 – Calculating the root**

This is the iterative part of the process. Given the lower and upper bounds of and , the bisection method can be outlined as:

Select values for the upper and lower bounds, .

Calculate the midpoint .

If , then the root is found, . Stop.

Else

a. If

b. IfRepeat 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 and . We can label the lower bound and upper bound as shown in Figure 3.2 above.

Next, we calculate the midpoint of and , .

As , .

The process then repeats with , 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) -> Double, lowerBound: Double, upperBound: Double, maxMargin: Double, maxIterations: Int): Double{
var lower: Double = lowerBound
var upper: Double = upperBound
if (myFunction(lower)*myFunction(upper)>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>=maxMargin && iterations0){
upper = mid
}
else{
lower = mid
}
iterations+=1
}
return mid
}
bisectionMethod(::testFunction, 2.5, 4.5, 0.001, 99)

Output:

3.5 3.0 3.25 3.375 3.3125 3.34375 3.359375 3.3671875 3.36328125 3.365234375 3.3662109375

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));