A few steps of the bisection method applied over the starting range [a₁;b₁]. The red dot is the root of the function.

In mathematics, the bisection method is a root-finding algorithm which works by repeatedly dividing an interval in half and then selecting the subinterval in which the root exists. Image File history File links Download high resolution version (838x977, 40 KB) Bisection method to find zeroes of a function Drawn by fr:Utilisateur:Dake with Inkscape 0. ... Image File history File links Download high resolution version (838x977, 40 KB) Bisection method to find zeroes of a function Drawn by fr:Utilisateur:Dake with Inkscape 0. ... Euclid, Greek mathematician, 3rd century BC, known today as the father of geometry; shown here in a detail of The School of Athens by Raphael. ... A root-finding algorithm is a numerical method, or algorithm, for finding a value x such that f(x) = 0, for a given function f. ... In mathematics, interval is a concept relating to the sequence and set-membership of one or more numbers. ... In mathematics, a root (or a zero) of a function f is an element x in the domain of f such that f(x) = 0. ...

Suppose we want to solve the equation f(x) = 0. Given two points a and b such that f(a) and f(b) have opposite signs, we know by the intermediate value theorem that f must have at least one root in the interval [a, b] as long as f is continuous. The bisection method divides the interval in two by computing c = (a+b) / 2. There are now two possibilities: either f(a) and f(c) have opposite signs, or f(c) and f(b) have opposite signs. The bisection algorithm is then applied to the sub-interval where the sign change occurs, meaning that the bisection algorithm is inherently recursive. In analysis, the intermediate value theorem is either of two theorems of which an account is given below. ... In mathematics, a continuous function is a function for which, intuitively, small changes in the input result in small changes in the output. ... A Sierpinski triangle —a confined recursion of triangles to form a geometric lattice. ...

The bisection method is less efficient than Newton's method but it is much less prone to odd behavior. In numerical analysis, Newtons method (or the Newton–Raphson method or the Newton–Fourier method) is an efficient algorithm for finding approximations to the zeros (or roots) of a real-valued function. ...

If f is a continuous function on the interval [a, b] and f(a)f(b) < 0, then the bisection method converges to a root of f. In fact, the absolute error for the bisection method is at most In mathematics, a continuous function is a function for which, intuitively, small changes in the input result in small changes in the output. ... In the absence of a more specific context, convergence denotes the approach toward a definite value, as time goes on; or to a definite point, a common view or opinion, or toward a fixed or equilibrium state. ... In the mathematical subfield of numerical analysis the approximation error in some data is the discrepancy between an exact value and some approximation to it. ...

after n steps. In other words, the error is halved at every step, so the method converges linearly, which is quite slow. On the positive side, the method is guaranteed to converge if f(a) and f(b) have different sign. In numerical analysis (a branch of mathematics), the speed at which a convergent sequence approaches its limit is called the rate of convergence. ...

Pseudo-code

Here is a representation of the bisection method in Visual Basic code. The variables xL and xR correspond to a and b above. The initial xL and xR must be chosen so that f(xL) and f(xR) are of opposite sign (they 'bracket' a root). The variable epsilon specifies how precise the result will be.

 'Bisection Method 'Start loop Do While (xR - xL) > epsilon 'Calculate midpoint of domain xM = (xR + xL) / 2 'Find f(xM) If ((f(xL) * f(xM)) > 0) Then 'Throw away left half xL = xM Else 'Throw away right half xR = xM End If Loop 

External links

• Bisection Method on Mathcad Application Server.
• Bisection Method Notes, PPT, Mathcad, Maple, Matlab, Mathematica

Reference

• Richard L. Burden, J. Douglas Faires (2000), "Numerical Analysis, (7th Ed)", Brooks/Cole. ISBN 0-534-38216-9.