bisection

Bisection is a simple bracketing method for finding a root of a real-valued function. If a function f is continuous on an interval [a, b] and f(a) and f(b) have opposite signs, the intermediate value theorem guarantees at least one root in [a, b]. The method works by repeatedly halving the interval while preserving a sign change, thus maintaining a bracket around a root.

The procedure is as follows: compute the midpoint c = (a + b) / 2 and evaluate f(c). If f(c) equals zero, c is a root. If f(a) and f(c) have opposite signs, set b = c; otherwise, set a = c. Repeat these steps until the interval length |b − a| is within a chosen tolerance or until |f(c)| is sufficiently small.

Convergence and accuracy are straightforward. Each iteration halves the interval length, so after n iterations the root lies within an interval of length (b − a) / 2^n. Consequently, the error is bounded by (b − a) / 2^n. The method is guaranteed to converge for a single simple root in the initial bracket, provided f is continuous on [a, b] and f(a) and f(b) have opposite signs. If the root is not simple (for example, a multiple root), convergence can be slower but remains linear rather than quadratic, and the method still terminates under the same bracketing conditions.

Bisection is valued for robustness and simplicity, especially when derivative information is unavailable or unreliable. Its main drawback is relatively slow convergence compared with methods that use derivative information or more sophisticated bracketing strategies. It is widely used in numerical analysis for solving equations in one variable and as a fallback when other methods fail to bracket a root.