Numerical methods are mathematical methods used to find an approximation of a solution to a mathematical problem. The counterpart of a numerical method is an analytical method. As humans, we naturally resort to using analytical methods to solve mathematical problems (algebraic manipulation, logic, clever thinking). We are not quite adept at doing additions, subtractions or multiplications quickly (Try to multiply two 20x20 integer matrices and measure the time it takes you to complete the multiplication) however, so we resort to computers to do such heavy, repetitive work.

Bisection Method

Bisection Method is an elementary root-finding algorithm. Why are we interested in finding roots? Simply put, when we want to find a solution to an equation in the unknown x, the equation can be rewritten as f(x) = 0. The root is the value of x that satisfies the equation f(x) = 0 when the function is evaluated at the value x. In other words, the value of the root gives us a solution to the equation. Applications of root finding algorithms are numerous in many engineering fields where we want to solve difficult equations (for example, ballistics in physics).

The first step of the algorithm is to define an interval [a,b] where we believe the root will be. A good way to define your first interval is to plot the function to visually see roots (points where the function intercepts the x-axis). We proceed to reduce the interval length until the solution has been isolated as accurately as we desire (remember, we do not compute an exact solution, only an approximation).

At each iteration, we evaluate the function at the midpoint of the current interval and compare it to the sign of the function evaluated at our current point a. Depending on the sign of the function at the midpoint, we can discard the upper half or lower half of the interval.

• If the sign of the function at the midpoint is equal to the sign of the function at our current point a, then our interval becomes
  • (midpoint,b)
• Else
  • (a,midpoint)

We repeat the process until the interval isolates the root of the equation as accurately as desired. The main advantage of this numerical method is that if a function is continuous between the two initial guesses, the bisection method is guaranteed to converge. However, the main drawback of this algorithm is that it converges slowly.

Graphically, Bisection Method looks like this:

(Imagen taken from the University of Nebraska-Lincoln's Computer Science and Engineering website.)

Some readers may have noticed that this algorithm is akin to the binary search algorithm.

F# implementation

F# is a multi-paradigm programming language. It can be used for functional, imperative and object-oriented programming. This implementation is a purely functional one.

let rec Bisection_Method (f:float -> float) (a:float) (b:float) (tol:float) (iternum:int) :float =
    //assert that there is a root inside the interval
    if (sign(f a) * sign(f b) > 0) then 
        printfn "No root inside the interval! Returning 0."
        0.0
    else
        let m = (a+b)/2.0
        //if our approximation is not good enough, recursively iterate until it is.
        if (b-a >= tol ) then
            printfn "iternum: %d | midpoint: %f" iternum m
            (*if the sign of the function at the midpoint is equal to the sign of the function at our current point,
            discard the lower half of the interval 
            *)
            if sign(f a) * sign(f m) > 0 then
                Bisection_Method f m b tol (iternum+1)
            else
                Bisection_Method f a m tol (iternum+1)
        else
            printfn "\nfinal number of iterations: %d | root value: %f" iternum m
            m

It was a challenge to program the Bisection Method with a functional approach, as I am used to imperative and object-oriented programming paradigms. Nevertheless, I am satisfied with the elegant, mathematical solution that can be implemented with a functional language (try implementing this method in C).

Github link with a sample equation