Bisection method

The method is applicable for numerically solving the equation f(x) = 0 for the real variable x, where f is a continuous function defined on an interval [a, b] and where f(a) and f(b) have opposite signs. In this case a and b are said to bracket a root since, by the intermediate value theorem, the continuous function f 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 midpoint c = (a+b) / 2 of the interval and the value of the function f(c) at that point. If c itself is a root then the process has succeeded and stops. Otherwise, there are now only two possibilities: either f(a) and f(c) have opposite signs and bracket a root, or f(c) and f(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 of f is reduced in width by 50% at each step. The process is continued until the interval is sufficiently small.

Explicitly, if f(c)=0 then c may be taken as the solution and the process stops. Otherwise, if f(a) and f(c) have opposite signs, then the method sets c as the new value for b, and if f(b) and f(c) have opposite signs then the method sets c as the new a. In both cases, the new f(a) and f(b) have opposite signs, so the method is applicable to this smaller interval.^[6]

Iteration tasks

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

1. Calculate c, 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), return c and stop iterating.
4. Examine the sign of f(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. ME = bfe

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. Although f is continuous, finite precision may preclude a function value ever being zero. For example, consider f(x) = cos x; there is no floating-point value approximating x = π/2 that gives exactly zero. Additionally, the difference between a and b is limited by the floating point precision; i.e., as the difference between a and b decreases, at some point the midpoint of [a, b] will be numerically identical to (within floating point precision of) either a or b.

Algorithm

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

input: Function f,        endpoint values a, b,        tolerance TOL,        maximum iterations NMAXconditions: a < b,             either f(a) < 0 and f(b) > 0 or f(a) > 0 and f(b) < 0output: value which differs from a root of f(x) = 0 by less than TOL N ← 1while N ≤ NMAX do // limit iterations to prevent infinite loop    c ← (a + b)/2 // new midpoint    if f(c) = 0 or (b – a)/2 < TOL then // solution found        Output(c)        Stop    end if    N ← N + 1 // increment step counter    if sign(f(c)) = sign(f(a)) then a ← c else b ← c // new intervalend whileOutput("Method failed.") // max number of steps exceeded

Example: Finding the root of a polynomial

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.

Iteration	${\displaystyle a_{n}}$	${\displaystyle b_{n}}$	${\displaystyle c_{n}}$	${\displaystyle f(c_{n})}$
1	1	2	1.5	−0.125
2	1.5	2	1.75	1.6093750
3	1.5	1.75	1.625	0.6660156
4	1.5	1.625	1.5625	0.2521973
5	1.5	1.5625	1.5312500	0.0591125
6	1.5	1.5312500	1.5156250	−0.0340538
7	1.5156250	1.5312500	1.5234375	0.0122504
8	1.5156250	1.5234375	1.5195313	−0.0109712
9	1.5195313	1.5234375	1.5214844	0.0006222
10	1.5195313	1.5214844	1.5205078	−0.0051789
11	1.5205078	1.5214844	1.5209961	−0.0022794
12	1.5209961	1.5214844	1.5212402	−0.0008289
13	1.5212402	1.5214844	1.5213623	−0.0001034
14	1.5213623	1.5214844	1.5214233	0.0002594
15	1.5213623	1.5214233	1.5213928	0.0000780

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 of f if f is a continuous function on the interval [a, b] and f(a) and f(b) have opposite signs. The absolute error is halved at each step so the method converges linearly. Specifically, if c₁ = a+b/2 is the midpoint of the initial interval, and c_n is the midpoint of the interval in the nth step, then the difference between c_n and a solution c is bounded by^[8]

${\displaystyle |c_{n}-c|\leq {\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 number n of iterations needed to achieve a required tolerance ε (that is, an error guaranteed to be at most ε), is bounded by

${\displaystyle n\leq n_{1/2}\equiv \left\lceil \log _{2}\left({\frac {\epsilon _{0}}{\epsilon }}\right)\right\rceil ,}$

where the initial bracket size ${\displaystyle \epsilon _{0}=|b-a|}$ and the required bracket size ${\displaystyle \epsilon \leq \epsilon _{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 the worst case has an ${\displaystyle \epsilon }$ 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 to average performance under standard assumptions ^[11][12] as well as asymptotic performance.^[13] Popular alternatives to the bisection method, such as the secant method, Ridders' method or Brent's method (amongst others), typically perform better since they trade-off worst case performance to achieve higher orders 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 the ITP Method.^[13][14]

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

Methods based on degree computation

Some of these methods are based on computing the topological degree.^[17]

Characteristic bisection method

The characteristic bisection method uses only the signs of a function in different points. Lef f be a function from R^d to R^d, for some integer d ≥ 2. A characteristic polyhedron^[18] (also called an admissible polygon)^[19] of f is a polyhedron in R^d, having 2^d vertices, such that in each vertex v, the combination of signs of f(v) is unique. For example, for d=2, a characteristic polyhedron of f is a quadrilateral with vertices (say) A,B,C,D, such that:

• Sign f(A) = (-,-), that is, f₁(A)<0, f₂(A)<0.
• Sign f(B) = (-,+), that is, f₁(B)<0, f₂(B)>0.
• Sign f(C) = (+,-), that is, f₁(C)>0, f₂(C)<0.
• Sign f(D) = (+,+), that is, f₁(D)>0, f₂(D)>0.

A proper edge of a characteristic polygon is a 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. A diagonal is a pair of vertices, such that the sign vector differs by all d 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 of f in its mid-point (say, M). Then it proceeds as follows:

• If Sign f(M) = Sign(A), then A is replaced by M, and we get a smaller characteristic polyhedron.
• If Sign f(M) = Sign(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 is ${\displaystyle D}$ . Then, at least ${\displaystyle \log _{2}(D/\varepsilon )}$ bisections of edges are required so that the diameter of the remaining polygon will be at most ${\displaystyle \varepsilon }$ .^{[19]: 11, Lemma.4.7}

• 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 from the original on 2009-04-13

Wikiversity has learning resources about The bisection method

The Wikibook Numerical Methods has a page on the topic of: Equation Solving

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