Bisection method
A simple, robust root-finding method for continuous functions.
The bisection method is a root-finding algorithm in mathematics, applicable to any continuous function for which two values with opposite signs are known. It is a simple and robust technique, though relatively slow, often used to obtain a rough approximation for more rapidly converging methods. The method is also known as interval halving, binary search, or the dichotomy method. It works by repeatedly bisecting an interval defined by two points where the function takes opposite signs, then selecting the subinterval where the sign change persists, which must contain a root by the intermediate value theorem. At each step, the midpoint is calculated, and the function is evaluated there. If the midpoint is not itself a root, the algorithm checks the signs at the midpoint and the original endpoints. If the sign at the midpoint matches the sign at the left endpoint, the left endpoint is replaced by the midpoint; otherwise, the right endpoint is replaced. This process halves the interval width at each iteration, continuing until the interval is sufficiently small. Several stopping conditions exist, including absolute tolerance, relative tolerance, or simply checking if the function value at the midpoint is zero. The relative tolerance condition is often preferred when the root’s magnitude is unknown, as it ensures accuracy to a certain number of significant figures. For polynomials, the method can be extended using tools like Descartes' rule of signs or Sturm's theorem to isolate all real roots efficiently. The bisection method has also been generalized to higher dimensions through approaches such as the characteristic bisection method, which uses sign patterns at the vertices of a polyhedron to narrow down a root in multi-dimensional space.
- field
- Mathematics
- known_for
- Root-finding method for continuous functions
- also_called
- Interval halving method, binary search method, dichotomy method
Lore & Background
The bisection method is a root-finding technique for continuous functions where two input values with opposite signs are known. The method repeatedly bisects the interval between these values and selects the subinterval where the function changes sign, guaranteeing a root is contained within. It is valued for its simplicity and robustness but is relatively slow, often used to obtain a rough approximation that serves as a starting point for faster methods. Also known as interval halving, binary search, or dichotomy, the method applies to solving f(x)=0 for a real variable x, with f continuous on [a,b] and f(a) and f(b) having opposite signs, bracketing at least one root by the intermediate value theorem. At each step, the midpoint c=(a+b)/2 is computed. If f(c)=0, the process stops; otherwise, the sign of f(c) determines which half—[a,c] or [c,b]—contains the sign change, and that subinterval becomes the new [a,b]. This halves the interval width each iteration until it is sufficiently small. Stopping conditions include absolute tolerance, relative tolerance, or a combination; relative tolerance is best when the root’s value is unknown. For polynomials, more elaborate methods like Descartes’ rule of signs or Sturm’s theorem can extend bisection into efficient algorithms for finding all real roots. The method has been generalized to multi-dimensional functions, with some approaches based on topological degree or characteristic polyhedra, where signs at vertices guide bisection of edges to shrink the search region.
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.
Frequently Asked Questions
Who is Bisection method?
Bisection method is a root-finding algorithm from the mathematics canon, featured in the Algorithms And Data Structures 1-24 series. It targets any continuous function for which two bracketing points with opposite signs are already known, then repeatedly splits the interval in half to zero in on a solution.
What are Bisection method's powers and role?
Its signature move is halving a bracketing interval over and over until the remaining segment is acceptably narrow, guaranteeing convergence as long as the function stays continuous. It is celebrated for its robustness and simplicity, though it converges relatively slowly compared to more sophisticated solvers.
How does Bisection method's story end?
Rather than serving as the final act, it typically hands its rough approximation off to faster-converging techniques that demand a solid starting guess. In the broader algorithmic narrative it plays the dependable supporting role of a first pass before the more agile methods take the lead.
Why is Bisection method important?
It requires only continuity and a sign change—no derivatives, no special function structure—making it one of the simplest guaranteed-convergence root finders available. That minimal set of assumptions keeps it a go-to baseline and a staple teaching tool in numerical analysis.
What are Bisection method's aliases in the series?
Fans and textbooks also call it the interval halving method, the binary search method, or the dichotomy method. All three names point to the same repeated-halving strategy for narrowing down a root.
More in Algorithms And Data Structures 1-24
Spotted an error? Know more?
This is a living reference — every entry is fact-audited, and reader corrections feed straight into our audit queue. Suggest an edit · See this site's audit record