Bisection method

This article is about searching zeros of continuous functions. For searching a finite sorted array, see binary search algorithm. For the method of determining what software change caused a change in behavior, see Bisection (software engineering).
A few steps of the bisection method applied over the starting range [a1;b1]. The bigger red dot is the root of the function.

In mathematics, the bisection method is a root-finding method that applies to any continuous function for which one knows two values with opposite signs. The method consists of repeatedly bisecting the interval defined by these values and then selecting the subinterval in which the function changes sign, and therefore must contain a root. It is a very simple and robust method, but it is also relatively slow. Because of this, it is often used to obtain a rough approximation to a solution which is then used as a starting point for more rapidly converging methods.[1] The method is also called the interval halving method,[2] the binary search method,[3] or the dichotomy method.[4]

For polynomials, more elaborate methods exist for testing the existence of a root in an interval (Descartes' rule of signs, Sturm's theorem, Budan's theorem). They allow extending the bisection method into efficient algorithms for finding all real roots of a polynomial; see Real-root isolation.

  1. ^ Burden & Faires 1985, p. 31
  2. ^ "Interval Halving (Bisection)". Archived from the original on 2013-05-19. Retrieved 2013-11-07.
  3. ^ Burden & Faires 1985, p. 28
  4. ^ "Dichotomy method - Encyclopedia of Mathematics". www.encyclopediaofmath.org. Retrieved 2015-12-21.