Inmathematics, thebisection method is aroot-finding method that applies to anycontinuous function for which one knows two values with opposite signs. The method consists of repeatedlybisecting theinterval defined by these values and then selecting the subinterval in which the function changes sign, and therefore must contain aroot. 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 theinterval halving method,^[2] thebinary search method,^[3] or thedichotomy method.^[4]

Forpolynomials, 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; seeReal-root isolation.

The method is applicable for numerically solving the equationf(x) = 0 for thereal variablex, wheref is acontinuous function defined on an interval [a, b] and wheref(a) andf(b) have opposite signs. In this casea andb are said to bracket a root since, by theintermediate value theorem, the continuous functionf must have at least one root in the interval (a,b).

At each step the method divides the interval in two parts/halves by computing the midpointc = (a+b) / 2 of the interval and the value of the functionf(c) at that point. Ifc itself is a root then the process has succeeded and stops. Otherwise, there are now only two possibilities: eitherf(a) andf(c) have opposite signs and bracket a root, orf(c) andf(b) have opposite signs and bracket a root.^[5] The method selects the subinterval that is guaranteed to be a bracket as the new interval to be used in the next step. In this way an interval that contains a zero off is reduced in width by 50% at each step. The process is continued until the interval is sufficiently small.

Explicitly, iff(c)=0 thenc may be taken as the solution and the process stops. Otherwise, iff(a) andf(c) have opposite signs, then the method setsc as the new value forb, and iff(b) andf(c) have opposite signs then the method setsc as the newa. In both cases, the newf(a) andf(b) have opposite signs, so the method is applicable to this smaller interval.^[6]

The input for the method is a continuous functionf, an interval [a,b], and the function valuesf(a) andf(b). The function values are of opposite sign (there is at least one zero crossing within the interval). Each iteration performs these steps:

1. Calculatec, the midpoint of the interval,c =⁠a+b/2⁠.
2. Calculate the function value at the midpoint,f(c).
3. If convergence is satisfactory (that is,c −a is sufficiently small, or |f(c)| is sufficiently small), returnc and stop iterating.
4. Examine the sign off(c) and replace either (a,f(a)) or (b,f(b)) with (c,f(c)) so that there is a zero crossing within the new interval.

When implementing the method on a computer, there can be problems with finite precision, so there are often additional convergence tests or limits to the number of iterations. Althoughf is continuous, finite precision may preclude a function value ever being zero. For example, considerf(x) = cosx; there is no floating-point value approximatingx =π/2 that gives exactly zero. Additionally, the difference betweena andb is limited by the floating point precision; i.e., as the difference betweena andb decreases, at some point the midpoint of[a,b] will be numerically identical to (within floating point precision of) eithera orb.

The method may be written inpseudocode as follows:^[7]

input: Functionf,        endpoint valuesa,b,        toleranceTOL,        maximum iterationsNMAXconditions:a <b,             eitherf(a) < 0 andf(b) > 0 orf(a) > 0 andf(b) < 0output: value which differs from a root off(x) = 0 by less thanTOLN ← 1whileN ≤NMAXdo// limit iterations to prevent infinite loopc ← (a +b)/2// new midpointiff(c) = 0 or (b –a)/2 <TOLthen// solution found        Output(c)Stopend ifN ←N + 1// increment step counterif sign(f(c)) = sign(f(a))thena ←celseb ←c// new intervalend whileOutput("Method failed.")// max number of steps exceeded

Suppose that the bisection method is used to find a root of the polynomial

${\displaystyle f(x)=x^3-x-2.}$ 

First, two numbers${\displaystyle a}$  and${\displaystyle b}$  have to be found such that${\displaystyle f(a)}$  and${\displaystyle f(b)}$  have opposite signs. For the above function,${\displaystyle a=1}$  and${\displaystyle b=2}$  satisfy this criterion, as

${\displaystyle f(1)=(1{)}^3-(1)-2=-2}$ 

and

${\displaystyle f(2)=(2{)}^3-(2)-2=+4.}$ 

Because the function is continuous, there must be a root within the interval [1, 2].

In the first iteration, the end points of the interval which brackets the root are${\displaystyle a_1=1}$  and${\displaystyle b_1=2}$ , so the midpoint is

${\displaystyle c_1=\frac{2+1}{2}=1.5}$ 

The function value at the midpoint is${\displaystyle f(c_1)=(1.5{)}^3-(1.5)-2=-0.125}$ . Because${\displaystyle f(c_1)}$  is negative,${\displaystyle a=1}$  is replaced with${\displaystyle a=1.5}$  for the next iteration to ensure that${\displaystyle f(a)}$  and${\displaystyle f(b)}$  have opposite signs. As this continues, the interval between${\displaystyle a}$  and${\displaystyle b}$  will become increasingly smaller, converging on the root of the function. See this happen in the table below.

After 13 iterations, it becomes apparent that there is a convergence to about 1.521: a root for the polynomial.

The method is guaranteed to converge to a root off iff is acontinuous function on the interval [a,b] andf(a) andf(b) have opposite signs. Theabsolute error is halved at each step so the methodconverges linearly. Specifically, ifc₁ =⁠a+b/2⁠ is the midpoint of the initial interval, andc_n is the midpoint of the interval in thenth step, then the difference betweenc_n and a solutionc is bounded by^[8]

${\displaystyle |c_n-c|\le \frac{|b-a|}{2^n}.}$ 

This formula can be used to determine, in advance, an upper bound on the number of iterations that the bisection method needs to converge to a root to within a certain tolerance.The numbern of iterations needed to achieve a required tolerance ε (that is, an error guaranteed to be at most ε), is bounded by

${\displaystyle n\le n_{1/2}\equiv \lceil {\log }_2\left(\frac{{ϵ}_0}{ϵ}\right)\rceil ,}$ 

where the initial bracket size${\displaystyle {ϵ}_0=|b-a|}$  and the required bracket size${\displaystyle ϵ\le {ϵ}_0.}$  The main motivation to use the bisection method is that over the set of continuous functions, no other method can guarantee to produce an estimate c_n to the solution c that in theworst case has an${\displaystyle ϵ}$  absolute error with less than n_1/2 iterations.^[9] This is also true under several common assumptions on function f and the behaviour of the function in the neighbourhood of the root.^[9][10]

However, despite the bisection method being optimal with respect to worst case performance under absolute error criteria it is sub-optimal with respect toaverage performance under standard assumptions^[11][12] as well asasymptotic performance.^[13] Popular alternatives to the bisection method, such as thesecant method,Ridders' method orBrent's method (amongst others), typically perform better since they trade-off worst case performance to achieve higherorders of convergence to the root. And, a strict improvement to the bisection method can be achieved with a higher order of convergence without trading-off worst case performance with theITP Method.^{[13][14][non-primary source needed]}

The bisection method has been generalized to multi-dimensional functions. Such methods are calledgeneralized bisection methods.^[15][16]

Some of these methods are based on computing thetopological degree, which for a bounded region${\displaystyle \mathrm{\Omega }\subseteq {\mathbb{R}}^n}$  and a differentiable function${\displaystyle f:{\mathbb{R}}^n\to {\mathbb{R}}^n}$  is defined as a sum over its roots:

${\displaystyle \mathrm{deg}(f,\mathrm{\Omega }):=\sum _{y\in f^{-1}(\mathbf{0})}\mathrm{sgn}det(Df(y))}$ ,

where${\displaystyle Df(y)}$  is theJacobian matrix,${\displaystyle \mathbf{0}=(0,0,...,0{)}^T}$ , and

 

is thesign function.^[17] In order for a root to exist, it is sufficient that${\displaystyle \mathrm{deg}(f,\mathrm{\Omega })\ne 0}$ , and this can be verified using asurface integral over the boundary of${\displaystyle \mathrm{\Omega }}$ .^[18]

Thecharacteristic bisection method uses only the signs of a function in different points. Leff be a function from R^d to R^d, for some integerd ≥ 2. Acharacteristic polyhedron^[19] (also called anadmissible polygon)^[20] off is apolytope in R^d, having 2^d vertices, such that in each vertexv, the combination of signs off(v) is unique and thetopological degree off on its interior is not zero (a necessary criterion to ensure the existence of a root).^[21] For example, ford=2, a characteristic polyhedron off is aquadrilateral with vertices (say) A,B,C,D, such that:

• ⁠${\displaystyle \mathrm{sgn}f(A)=(-,-)}$ ⁠, that is,f₁(A)<0,f₂(A)<0.
• ⁠${\displaystyle \mathrm{sgn}f(B)=(-,+)}$ ⁠, that is,f₁(B)<0,f₂(B)>0.
• ⁠${\displaystyle \mathrm{sgn}f(C)=(+,-)}$ ⁠, that is,f₁(C)>0,f₂(C)<0.
• ⁠${\displaystyle \mathrm{sgn}f(D)=(+,+)}$ ⁠, that is,f₁(D)>0,f₂(D)>0.

Aproper edge of a characteristic polygon is an edge between a pair of vertices, such that the sign vector differs by only a single sign. In the above example, the proper edges of the characteristic quadrilateral are AB, AC, BD and CD. Adiagonal is a pair of vertices, such that the sign vector differs by alld signs. In the above example, the diagonals are AD and BC.

At each iteration, the algorithm picks a proper edge of the polyhedron (say, A—B), and computes the signs off in its mid-point (say, M). Then it proceeds as follows:

• If⁠${\displaystyle \mathrm{sgn}f(M)=\mathrm{sgn}(A)}$ ⁠, then A is replaced by M, and we get a smaller characteristic polyhedron.
• If⁠${\displaystyle \mathrm{sgn}f(M)=\mathrm{sgn}(B)}$ ⁠, then B is replaced by M, and we get a smaller characteristic polyhedron.
• Else, we pick a new proper edge and try again.

Suppose the diameter (= length of longest proper edge) of the original characteristic polyhedron isD. Then, at least${\displaystyle {\log }_2(D/\epsilon )}$  bisections of edges are required so that the diameter of the remaining polygon will be at mostε.^{[20]: 11, Lemma.4.7} If the topological degree of the initial polyhedron is not zero, then there is a procedure that can choose an edge such that the next polyhedron also has nonzero degree.^[21][22]

• Binary search algorithm
• Lehmer–Schur algorithm, generalization of the bisection method in the complex plane
• Nested intervals

• Burden, Richard L.; Faires, J. Douglas (1985), "2.1 The Bisection Algorithm",Numerical Analysis (3rd ed.), PWS Publishers,ISBN 0-87150-857-5

• Corliss, George (1977), "Which root does the bisection algorithm find?",SIAM Review,19 (2):325–327,doi:10.1137/1019044,ISSN 1095-7200
• Kaw, Autar; Kalu, Egwu (2008),Numerical Methods with Applications (1st ed.), archived fromthe original on 2009-04-13

• Weisstein, Eric W."Bisection".MathWorld.
• Bisection Method Notes, PPT, Mathcad, Maple, Matlab, Mathematica fromHolistic Numerical Methods Institute