Bisection method
Encyclopedia
The bisection method in mathematics
is a root-finding method which repeatedly bisects an interval
and then selects a subinterval in which a root must lie for further processing. 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. The method is also called the binary search method and is similar to the computer science Binary Search
, where the range of possible solutions is halved each iteration.
variable x, where f is a continuous function
defined on an interval [a, b] and 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 f must have at least one root in the interval (a, b).
At each step the method divides the interval in two by computing the midpoint c = (a+b) / 2 of the interval and the value of the function f(c) at that point. Unless c is itself a root (which is very unlikely, but possible) there are now 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. The method selects the subinterval that is a bracket as a new interval to be used in the next step. In this way the 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(a) and f(c) are opposite signs, then the method sets c as the new value for b, and if f(b) and f(c) are opposite signs then the method sets c as the new a. (If f(c)=0 then c may be taken as the solution and the process stops.) In both cases, the new f(a) and f(b) have opposite signs, so the method is applicable to this smaller interval.
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
, which is comparatively slow.
Specifically, if p1 = (a+b)/2 is the midpoint of the initial interval, and pn is the midpoint of the interval in the nth step, then the difference between pn and a solution p is bounded by
This formula can be used to determine in advance the number of iterations that the bisection method would need to converge to a root to within a certain tolerance.
as follows:
INPUT: Function f, endpoint values a, b, tolerance TOL, maximum iterations NMAX
CONDITIONS: a < b, either f(a) < 0 and f(b) > 0 or f(a) > 0 and f(b) < 0
OUTPUT: value which differs from a root of f(x)=0 by less than TOL
N ← 1
While N ≤ NMAX { 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
}
N ← N + 1 increment step counter
If sign(f(c)) = sign(f(a)) then a ← c else b ← c new interval
}
Output("Method failed.") max number of steps exceeded
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
is a root-finding method which repeatedly bisects an interval
Interval (mathematics)
In mathematics, a interval is a set of real numbers with the property that any number that lies between two numbers in the set is also included in the set. For example, the set of all numbers satisfying is an interval which contains and , as well as all numbers between them...
and then selects a subinterval in which a root must lie for further processing. 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. The method is also called the binary search method and is similar to the computer science Binary Search
Binary search algorithm
In computer science, a binary search or half-interval search algorithm finds the position of a specified value within a sorted array. At each stage, the algorithm compares the input key value with the key value of the middle element of the array. If the keys match, then a matching element has been...
, where the range of possible solutions is halved each iteration.
The method
The method is applicable when we wish to solve the equation f(x) = 0 for the realReal number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
variable x, where f is a continuous function
Continuous function
In mathematics, a continuous function is a function for which, intuitively, "small" changes in the input result in "small" changes in the output. Otherwise, a function is said to be "discontinuous". A continuous function with a continuous inverse function is called "bicontinuous".Continuity of...
defined on an interval [a, b] and 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
Intermediate value theorem
In mathematical analysis, the intermediate value theorem states that for each value between the least upper bound and greatest lower bound of the image of a continuous function there is at least one point in its domain that the function maps to that value....
, the f must have at least one root in the interval (a, b).
At each step the method divides the interval in two by computing the midpoint c = (a+b) / 2 of the interval and the value of the function f(c) at that point. Unless c is itself a root (which is very unlikely, but possible) there are now 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. The method selects the subinterval that is a bracket as a new interval to be used in the next step. In this way the 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(a) and f(c) are opposite signs, then the method sets c as the new value for b, and if f(b) and f(c) are opposite signs then the method sets c as the new a. (If f(c)=0 then c may be taken as the solution and the process stops.) In both cases, the new f(a) and f(b) have opposite signs, so the method is applicable to this smaller interval.
Analysis
The method is guaranteed to converge to a root of f if f is a continuous functionContinuous function
In mathematics, a continuous function is a function for which, intuitively, "small" changes in the input result in "small" changes in the output. Otherwise, a function is said to be "discontinuous". A continuous function with a continuous inverse function is called "bicontinuous".Continuity of...
on the interval [a, b] and f(a) and f(b) have opposite signs. The absolute error
Approximation error
The approximation error in some data is the discrepancy between an exact value and some approximation to it. An approximation error can occur because#the measurement of the data is not precise due to the instruments...
is halved at each step so the method converges linearly
Rate of convergence
In numerical analysis, the speed at which a convergent sequence approaches its limit is called the rate of convergence. Although strictly speaking, a limit does not give information about any finite first part of the sequence, this concept is of practical importance if we deal with a sequence of...
, which is comparatively slow.
Specifically, if p1 = (a+b)/2 is the midpoint of the initial interval, and pn is the midpoint of the interval in the nth step, then the difference between pn and a solution p is bounded by
This formula can be used to determine in advance the number of iterations that the bisection method would need to converge to a root to within a certain tolerance.
Pseudocode
The method may be written in PseudocodePseudocode
In computer science and numerical computation, pseudocode is a compact and informal high-level description of the operating principle of a computer program or other algorithm. It uses the structural conventions of a programming language, but is intended for human reading rather than machine reading...
as follows:
INPUT: Function f, endpoint values a, b, tolerance TOL, maximum iterations NMAX
CONDITIONS: a < b, either f(a) < 0 and f(b) > 0 or f(a) > 0 and f(b) < 0
OUTPUT: value which differs from a root of f(x)=0 by less than TOL
N ← 1
While N ≤ NMAX { 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
}
N ← N + 1 increment step counter
If sign(f(c)) = sign(f(a)) then a ← c else b ← c new interval
}
Output("Method failed.") max number of steps exceeded
See also
- Secant methodSecant methodIn numerical analysis, the secant method is a root-finding algorithm that uses a succession of roots of secant lines to better approximate a root of a function f. The secant method can be thought of as a finite difference approximation of Newton's method. However, the method was developed...
- Newton's methodNewton's methodIn numerical analysis, Newton's method , named after Isaac Newton and Joseph Raphson, is a method for finding successively better approximations to the roots of a real-valued function. The algorithm is first in the class of Householder's methods, succeeded by Halley's method...
- Root-finding algorithmRoot-finding algorithmA root-finding algorithm is a numerical method, or algorithm, for finding a value x such that f = 0, for a given function f. Such an x is called a root of the function f....
- Binary search algorithmBinary search algorithmIn computer science, a binary search or half-interval search algorithm finds the position of a specified value within a sorted array. At each stage, the algorithm compares the input key value with the key value of the middle element of the array. If the keys match, then a matching element has been...
- Lehmer-Schur algorithmLehmer-Schur algorithmIn mathematics, the Lehmer–Schur algorithm is a root-finding algorithm extending the one-dimensional bracketing used by the bisection method to find the roots of a function of one complex variable inside any rectangular region of the function's holomorphicity .The rectangle in question is...
, generalization of the bisection method in the complex plane - Nested intervalsNested intervalsIn mathematics, a sequence of nested intervals is understood as a collection of sets of real numberssuch that each set In is an interval of the real line, for n = 1, 2, 3, ... , and that furtherfor all n...
- Brent's methodBrent's methodIn numerical analysis, Brent's method is a complicated but popular root-finding algorithm combining the bisection method, the secant method and inverse quadratic interpolation. It has the reliability of bisection but it can be as quick as some of the less reliable methods...
External links
- http://www.torkian.info/Site/Research/Entries/2008/2/28_Root-finding_algorithm_Java_Code_(_Secant%2C_Bisection%2C_Newton_).html Java code by Behzad Torkian
- Bisection Method Notes, PPT, Mathcad, Maple, Matlab, Mathematica from Holistic Numerical Methods Institute
- Module for the Bisection Method by John H. Mathews