Bisection method

Lore & Background

The method applies to solving the equation f(x)=0 for a real variable x, where f is continuous on an interval [a,b] and f(a) and f(b) have opposite signs. By the intermediate value theorem, at least one root exists in (a,b). At each step, the interval is bisected at the midpoint c=(a+b)/2, and the subinterval where the function changes sign is selected. This process halves the interval width at each step until it is sufficiently small.

Reader's Guide

The bisection method is significant for its simplicity and robustness, requiring only that the function be continuous and that initial endpoints bracket a root. It is guaranteed to converge, but its linear convergence rate makes it slower than methods like Newton's method. Consequently, it is often used to obtain a rough approximation that is then refined by faster algorithms. For polynomials, more elaborate methods such as Descartes' rule of signs, Sturm's theorem, and Budan's theorem allow extending the bisection method into efficient algorithms for finding all real roots, a process known as real-root isolation. Stopping conditions include absolute tolerance, relative tolerance, and checking the function value at the midpoint, with relative tolerance recommended when nothing is known about the root's value.

Did You Know?

• The method is also called the interval halving method, binary search method, or dichotomy method.
• It applies to any continuous function for which two values with opposite signs are known.
• At each step, the interval is reduced in width by 50%.
• For polynomials, Descartes' rule of signs, Sturm's theorem, and Budan's theorem can extend the method to find all real roots.