Bisection method

Imagine you are looking for a hidden spot. First, pick two points. One point must be high and one must be low.

Find the middle point between them. Check if the hidden spot is on the left or the right. Pick that side to keep.

Now you have a smaller space. Do it again by finding a new middle. Each time, the space gets half as big.

This way is very simple and strong. It is also a bit slow. We use it to get a close guess.

It helps us find a starting point. Then, we can use faster ways to finish.

Imagine you are looking for a hidden spot on a line. To start, you pick two points. One point must be high and one must be low. This means they have opposite signs. These two points trap or "bracket" the hidden spot, which we call a root.

First, find the middle point between your two marks. Check the value at that middle point. If it is the root, you are done! If not, look at the signs. Pick the side where the signs are still opposite. This side must contain the root.

Now, you have a smaller space. Repeat these steps again and again. Each time, the space gets half as big. This is why some call it the interval halving method. It is also called the binary search method.

This way is very simple and strong. But it is also a bit slow. We often use it to get a rough guess. Then, we use faster ways to find the exact answer. You can even use this for many dimensions. These are called generalized bisection methods.

Sometimes we need to find a very specific spot on a line. In math, we call this spot a root. A root is where a continuous function equals zero. To find it, we use the bisection method. This method is also called the interval halving method. Some people call it the binary search method or the dichotomy method. It is a very simple and robust way to find an answer. However, it can be a relatively slow process.

To start, you must find two values that bracket a root. These values must have opposite signs. One value must be positive and the other must be negative. This works because of the intermediate value theorem. This theorem says a continuous function must cross zero between those points. First, you find the midpoint of your two values. You then check the value of the function at that midpoint. If the midpoint is the root, you are finished.

If the midpoint is not the root, you must look at the signs. You check if the midpoint and your original points have opposite signs. You then select the new, smaller interval that contains the sign change. This new interval is guaranteed to bracket the root. Each step reduces the width of your interval by 50%. You repeat this many times to get closer to the answer. You stop when the interval is small enough for your needs.

There are different ways to decide when to stop. Burden and Faires wrote about this in 2016. They identified three main stopping conditions. One is called absolute tolerance. Another is called relative tolerance. Relative tolerance is often the best choice if you do not know the root's value. You can also use the absolute difference between points. These rules help you decide when your answer is accurate enough.

This method can even work in many dimensions. These are called generalized bisection methods. Some versions use something called a characteristic polyhedron. For example, in two dimensions, this might be a quadrilateral. The method uses the signs of the function at the corners. It picks an edge and finds a new midpoint. This helps find roots in more complex spaces. It is a reliable way to start a hard math job.

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.