Bisection method

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.

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.

[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.

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.

[5] The method selects the subinterval that is guaranteed to be a bracket as the new interval to be used in the next step.

The process is continued until the interval is sufficiently small.

In both cases, the new f(a) and f(b) have opposite signs, so the method is applicable to this smaller interval.

The function values are of opposite sign (there is at least one zero crossing within the interval).

Each iteration performs these steps: 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.

satisfy this criterion, as and 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

will become increasingly smaller, converging on the root of the function.

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 c1 = ⁠a+b/2⁠ is the midpoint of the initial interval, and cn is the midpoint of the interval in the nth step, then the difference between cn and a solution c is bounded by[8] 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 where the initial bracket size

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 cn to the solution c that in the worst case has an

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][non-primary source needed] The bisection method has been generalized to multi-dimensional functions.

[15][16] Some of these methods are based on computing the topological degree, which for a bounded region

[18] The characteristic bisection method uses only the signs of a function in different points.

A characteristic polyhedron[19] (also called an admissible polygon)[20] of f is a polytope in Rd, having 2d vertices, such that in each vertex v, the combination of signs of f(v) is unique and the topological degree of f on its interior is not zero (a necessary criterion to ensure the existence of a root).

[21] For example, for d=2, a characteristic polyhedron of f is a quadrilateral with vertices (say) A,B,C,D, such that: A proper 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.

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: Suppose the diameter (= length of longest proper edge) of the original characteristic polyhedron is D. Then, at least

bisections of edges are required so that the diameter of the remaining polygon will be at most ε.