Bisection Method¶

Overview¶

In mathematics, the bisection method is a root-finding method that applies to any continuous functions for which one knows two values with opposite signs. The method consists of repeatedly bisecting the interval defined by these values and then selecting the subinterval in which the function changes sign, and therefore must contain a root. It is a very simple and robust method, but it is also relatively slow. Because of this, it is often used to obtain a rough approximation to a solution which is then used as a starting point for more rapidly converging methods. The method is also called the interval halving method, the binary search method, or the dichotomy method.

The Method¶

The method is applicable for numerically solving the equation \(f(x) = 0\) for the real variable \(x\), where \(f\) is a continuous function defined on an interval \([a, b]\) and where \(f(a)\) and \(f(b)\) have opposite signs. In this case \(a\) and \(b\) are said to bracket a root since, by the intermediate value theorem, the continuous function \(f\) must have at least one root in the interval \((a, b)\).

At each step the method divides the interval in two by computing the midpoint \(c = \frac{a+b}{2}\) of the interval and the value of the function \(f(c)\) at that point. Unless \(c\) is itself a root (which is very unlikely, but possible) there are now only two possibilities: either \(f(a)\) and \(f(c)\) have opposite signs and bracket a root, or \(f(c)\) and \(f(b)\) have opposite signs and bracket a root. The method selects the subinterval that is guaranteed to be a bracket as the new interval to be used in the next step. In this way an interval that contains a zero of \(f\) is reduced in width by 50% at each step. The process is continued until the interval is sufficiently small.

Explicitly, if \(f(a)\) and \(f(c)\) have opposite signs, then the method sets \(c\) as the new value for \(b\), and if \(f(b)\) and \(f(c)\) have opposite signs then the method sets \(c\) as the new \(a\). (If \(f(c)=0\) then \(c\) may be taken as the solution and the process stops.) In both cases, the new \(f(a)\) and \(f(b)\) have opposite signs, so the method is applicable to this smaller interval.

Iteration Tasks¶

Calculate \(c\), the midpoint of the interval, \(c=\frac{a+b}{2}\).
Calculate the function value at the midpoint, \(f(c)\).
If convergence is satisfactory (that is, \(c-a\) is sufficiently small, or \(|f(c)|\) is sufficiently small), return \(c\) and stop iterating.
Examine the sign of \(f(c)\) and replace either \((a, f(a))\) or \((b, f(b))\) with \((c, f(c))\) so that there is a zero crossing within the new interval.

Usage¶

Imagine that we want to find the root of the following function:

\begin{equation} f(x) = \sin{(x)}, x \in [-1, 1] \end{equation}

Then the code will look like this:

// example_root_bisection.cpp

#include <iostream>
#include "../src/numerary.hpp" // Numerary library

using namespace std;
using namespace numerary;

/* Function to found the root */
double f(double x) {
    return sin(x);
}

/* The main function */
int main() {

    const double eps = 1.e-9; // eps value for method (1.e-9 by default)
    double a = -1; // "a" value of segment [a, b]
    double b = 1; // "b" value of segment [a, b]
    double root;
    short int is_found;

    is_found = Numerary::root(f, a, b, &root, "bisection", eps);

    if (is_found == 1) {
        cout << "Root is in x = " << root << endl;
    } else {
        cout << "Method not allowed!" << endl;
    }

    return 0;
}