Bisection method

The bisection method is a robust root-finding algorithm. It is used to find the value of a variable that makes a continuous function equal to zero. In mathematics, this zero-point is known as a root. This method is also referred to as the interval halving method. Some mathematicians call it the binary search method or the dichotomy method. While the process is very simple and reliable, it is also relatively slow. Because of this speed, it is often used to find a rough approximation. This approximation then serves as a starting point for faster, more rapidly converging methods.

To use this method, you must start with a continuous function. You also need an initial interval defined by two values, $a$ and $b$. These two values must bracket a root. Bracketing means that the function values at these points have opposite signs. One value must be positive and the other must be negative. This requirement works because of the intermediate value theorem. This theorem states that a continuous function must cross zero at least once between two points with opposite signs.

The mechanism of the bisection method follows a specific sequence of steps. First, you calculate the midpoint, $c$, of the current interval. Next, you calculate the value of the function at that midpoint. If the function value at $c$ is exactly zero, then $c$ is the root. In this case, the process is successful and stops immediately. If $c$ is not the root, you must examine the signs of the function at the endpoints. You check if $a$ and $c$ have opposite signs, or if $c$ and $b$ have opposite signs.

Once you examine the signs, you select the new subinterval. You choose the specific interval that is guaranteed to contain the sign change. This new interval becomes your working range for the next iteration. By doing this, you reduce the width of the interval by exactly 50% at each step. You repeat this cycle of halving and selecting. The process continues until the interval becomes sufficiently small. Once the process begins, the signs at the left and right ends of the interval remain the same for every iteration.

Deciding when to stop the process requires a stopping condition. This is often defined by a tolerance, denoted by the symbol $\epsilon$. In 2016, authors Burden and Faires identified three specific stopping conditions. The first is absolute tolerance. This ensures the result is accurate within a specific range. The second is the absolute difference between points. This means the points $c$ and $a$ are the same to a certain number of decimal places. The third is relative tolerance. This means the points are the same to a certain number of significant figures. Relative tolerance is considered the best stopping condition if the value of the root is unknown.

Consider an example using the polynomial $f(x) = x^3 - 2x^2 + x - 2$. To find a root, we can choose the interval $[1, 2]$. At $x=1$, the function value is $-2$. At $x=2$, the function value is $0$. Wait, if the value is $0$, we have found the root. Let us look at a different interval where the signs are opposite. If we iterate through many steps, the interval shrinks closer to the true root. After 13 iterations on a specific polynomial, the value might converge to approximately $1.521$. This shows how the interval narrows down to a single point.

The bisection method can also be generalized to higher dimensions. These are known as generalized bisection methods. Some of these versions are based on computing the topological degree. Another version is the characteristic bisection method. This method uses only the signs of a function at different points. In two dimensions, it might use a characteristic polyhedron, such as a quadrilateral. This shape has four vertices where each combination of signs is unique. The algorithm picks a proper edge and finds the midpoint. It then replaces a vertex to create a smaller characteristic polyhedron. This allows the method to find roots in much more complex mathematical spaces.