~2025-34958-91 at 22:56, 19 November 2025

2025-11-19T22:56:52Z

New page

{{short description|Algorithm for finding a zero of a function}}
{{about|searching for zeros of continuous functions|searching a finite sorted array|binary search algorithm|the method of determining what software change caused a change in behavior|Bisection (software engineering)}}

[[Image:Bisection method.svg|250px|thumb|A few steps of the bisection method applied over the starting range [a1;b1]. The bigger red dot is the root of the function.]]

In [[mathematics]], the '''bisection method''' is a [[Root-finding algorithm|root-finding method]] that applies to any [[continuous function]] for which one knows two values with opposite signs. The method consists of repeatedly [[Bisection|bisecting]] the [[Interval (mathematics)|interval]] defined by these values, then selecting the subinterval in which the function changes sign, which therefore must contain a [[Root of a function|root]]. 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.<ref>{{Harvnb|Burden|Faires|2016|p=51}}</ref> The method is also called the '''interval halving''' method,<ref>{{cite web |url=http://siber.cankaya.edu.tr/NumericalComputations/ceng375/node32.html |title=Interval Halving (Bisection) |access-date=2013-11-07 |url-status=dead |archive-url=https://web.archive.org/web/20130519092250/http://siber.cankaya.edu.tr/NumericalComputations/ceng375/node32.html |archive-date=2013-05-19 }}</ref> the '''[[Binary search algorithm|binary search method]]''',<ref>{{Harvnb|Burden|Faires|2016|p=48}}</ref> or the '''dichotomy method'''.<ref>{{Cite web|title = Dichotomy method - Encyclopedia of Mathematics|url = https://www.encyclopediaofmath.org/index.php/Dichotomy_method|website = www.encyclopediaofmath.org|access-date = 2015-12-21}}</ref>

For [[polynomial]]s, 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 ==
The method is applicable for numerically solving the equation <math>f(x) = 0</math> for the [[Real number|real]] variable <math>x</math>, where <math>f</math> is a [[continuous function]] defined on an interval <math>[a,b]</math> and where <math>f(a)</math> and <math>f(b)</math> have opposite signs. In this case <math>a</math> and <math>b</math> are said to bracket a root since, by the [[intermediate value theorem]], the continuous function <math>f</math> must have at least one root in the interval <math>(a,b)</math>.

At each step the method divides the interval in two parts/halves by computing the midpoint <math>c=(a+b)/2</math> of the interval and the value of the function <math>f(c)</math> at that point. If <math>c</math> itself is a root then the process has succeeded and stops. Otherwise, there are now only two possibilities: either <math>f(a)</math> and <math>f(c)</math> have opposite signs and bracket a root, or <math>f(c)</math> and <math>f(b)</math> have opposite signs and bracket a root.<ref>If the function has the same sign at the endpoints of an interval, the endpoints may or may not bracket roots of the function.</ref> 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 <math>f</math> is reduced in width by 50% at each step. The process is continued until the interval is sufficiently small.

Explicitly, if <math>f(c)=0</math> then <math>c</math> may be taken as the solution and the process stops.

Otherwise,
if <math>f(a)</math> and <math>f(c)</math> have the same signs,
*then the method sets <math>a = c</math>,
*else the method sets <math>b = c</math>.
In both cases, the new <math>f(a)</math> and <math>f(b)</math> have opposite signs, so the method may be applied to this smaller interval.<ref>{{Harvnb|Burden|Faires|2016|p=48}}</ref>

Once the process starts, the signs at the left and right ends of the interval remain the same for all iterations.

=== Stopping conditions===
In order to determine when the iteration should stop, it is necessary to consider various possible stopping conditions with respect to a tolerance (<math>\epsilon</math>). Burden and Faires (2016) identify the three stopping conditions:<ref>{{Harvnb|Burden|Faires|2016|p=50}}</ref>
* Absolute tolerance: <math>|p_N-p_{N-1}|<\epsilon</math>
* Relative tolerance: <math>\left|\frac{p_N-p_{N-1}}{p_N}\right|<\epsilon,</math>||<math>p_N\ne 0</math>
* <math>|f(p_N)|<\epsilon.</math>
<math>|f(p_N)|<\epsilon</math> does not give an accurate result to within <math>\epsilon</math> unless <math>|f'(p_N)| \ge 1</math>. The other two possibilities represent different concepts: the absolute difference <math>|c -a| \le 5\times10^{-t}</math> says that c and a are the same to <math>t</math> decimal places, while the relative difference <math>\left|\frac{c -a}{c}\right| \le 5\times10^{-t}</math> says that c and a are the same to <math>t</math> [[significant figures]].<ref>{{Harvnb|Burden|Faires|2016|p=18}}</ref> If nothing is known about the value of the root, then relative tolerance is the best stopping condition.<ref>{{Harvnb|Burden|Faires|2016|p=50}}</ref>

=== Iteration process ===

The input for the method is a continuous function <math>f</math> and an interval <math>[a, b]</math>, such that the function values <math>f(a)</math> and <math>f(b)</math> are of opposite sign (there is at least one zero crossing within the interval). Each iteration performs these steps:
# Calculate <math>c</math>, the midpoint of the interval, <math>c = \frac{a+b}{2}</math>;
# Calculate the function value at the midpoint, <math>f(c)</math>;
# If <math>f(c) = 0</math>, return c;
# If convergence is satisfactory (that is, <math>\left|c- a\right| \le 5\times10^{-t}|c|</math>), return <math>c</math>;
# Examine the sign of <math>f(c)</math> and replace either <math>a</math> or <math>b</math> with <math>c</math> so that there is a zero crossing within the new interval.

=== Example ===
Suppose that the bisection method is used to find a root of the polynomial
:<math> f(x) = x^3 - x - 2 \,.</math>
First, two numbers <math> a </math> and <math> b </math> have to be found such that <math>f(a)</math> and <math>f(b)</math> have opposite signs. For the above function, <math> a = 1 </math> and <math> b = 2 </math> satisfy this criterion, as
:<math> f(1) = (1)^3 - (1) - 2 = -2 </math>
and
:<math> f(2) = (2)^3 - (2) - 2 = +4 \,.</math>
Because the function is continuous, there must be a root within the interval [1, 2]. Iterating the bisection method on this interval gives increasingly accurate approximations:
{| class="wikitable"
! Iteration !! <math>a_n</math> !! <math>b_n</math> !! <math>c_n</math> !! <math>f(c_n)</math>
|- style="text-align: left;"
| style="text-align: right;" |1|| 1 || 2 || 1.5 || −0.125
|- style="text-align: left;"
| style="text-align: right;" |2|| 1.5|| 2|| 1.75|| style="text-align: right;" | 1.6093750
|- style="text-align: left;"
| style="text-align: right;" |3|| 1.5|| 1.75|| 1.625|| style="text-align: right;" | 0.6660156
|- style="text-align: left;"
| style="text-align: right;" |4|| 1.5|| 1.625|| 1.5625|| style="text-align: right;" | 0.2521973
|- style="text-align: left;"
| style="text-align: right;" |5|| 1.5|| 1.5625|| 1.5312500|| style="text-align: right;" | 0.0591125
|- style="text-align: left;"
| style="text-align: right;" |6|| 1.5|| 1.5312500|| 1.5156250|| −0.0340538
|- style="text-align: left;"
| style="text-align: right;" |7|| 1.5156250|| 1.5312500|| 1.5234375|| style="text-align: right;" | 0.0122504
|- style="text-align: left;"
| style="text-align: right;" |8|| 1.5156250|| 1.5234375|| 1.5195313|| −0.0109712
|- style="text-align: left;"
| style="text-align: right;" |9|| 1.5195313|| 1.5234375|| 1.5214844|| style="text-align: right;" | 0.0006222
|- style="text-align: left;"
| style="text-align: right;" |10|| 1.5195313|| 1.5214844|| 1.5205078|| −0.0051789
|- style="text-align: left;"
| style="text-align: right;" |11|| 1.5205078|| 1.5214844|| 1.5209961|| −0.0022794
|- style="text-align: left;"
| style="text-align: right;" |12|| 1.5209961|| 1.5214844|| 1.5212402|| −0.0008289
|- style="text-align: left;"
| style="text-align: right;" |13|| 1.5212402|| 1.5214844|| 1.5213623|| −0.0001034
|- style="text-align: left;"
| style="text-align: right;" |14|| 1.5213623|| 1.5214844|| 1.5214233|| style="text-align: right;" | 0.0002594
|-style="text-align: left;"
| style="text-align: right;" |15|| 1.5213623|| 1.5214233|| 1.5213928|| style="text-align: right;" | 0.0000780
|}

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

== Generalization to higher dimensions ==
The bisection method has been generalized to multi-dimensional functions. Such methods are called '''generalized bisection methods'''.<ref>{{Cite journal |last=Mourrain |first=B. |last2=Vrahatis |first2=M. N. |last3=Yakoubsohn |first3=J. C. |date=2002-06-01 |title=On the Complexity of Isolating Real Roots and Computing with Certainty the Topological Degree |url=https://www.sciencedirect.com/science/article/pii/S0885064X01906363 |journal=Journal of Complexity |language=en |volume=18 |issue=2 |pages=612–640 |doi=10.1006/jcom.2001.0636 |issn=0885-064X|url-access=subscription }}</ref><ref>{{Cite journal |last=Vrahatis |first=Michael N. |date=2020 |editor-last=Sergeyev |editor-first=Yaroslav D. |editor2-last=Kvasov |editor2-first=Dmitri E. |title=Generalizations of the Intermediate Value Theorem for Approximating Fixed Points and Zeros of Continuous Functions |url=https://link.springer.com/chapter/10.1007/978-3-030-40616-5_17 |journal=Numerical Computations: Theory and Algorithms |language=en |location=Cham |publisher=Springer International Publishing |pages=223–238 |doi=10.1007/978-3-030-40616-5_17 |isbn=978-3-030-40616-5|url-access=subscription }}</ref>

=== Methods based on degree computation ===
Some of these methods are based on computing the [[topological degree]].<ref>{{Cite journal |last=Kearfott |first=Baker |date=1979-06-01 |title=An efficient degree-computation method for a generalized method of bisection |url=https://doi.org/10.1007/BF01404868 |journal=Numerische Mathematik |language=en |volume=32 |issue=2 |pages=109–127 |doi=10.1007/BF01404868 |issn=0945-3245|url-access=subscription }}</ref>

=== Characteristic bisection method ===
The '''characteristic bisection method''' uses only the signs of a function in different points. Lef ''f'' be a function from Rd to Rd, for some integer ''d'' ≥ 2. A '''characteristic polyhedron'''<ref>{{Cite journal |last=Vrahatis |first=Michael N. |date=1995-06-01 |title=An Efficient Method for Locating and Computing Periodic Orbits of Nonlinear Mappings |url=https://www.sciencedirect.com/science/article/pii/S0021999185711199 |journal=Journal of Computational Physics |language=en |volume=119 |issue=1 |pages=105–119 |doi=10.1006/jcph.1995.1119 |issn=0021-9991|url-access=subscription }}</ref> (also called an '''admissible polygon''')<ref name=":2">{{Cite journal |last=Vrahatis |first=M. N. |last2=Iordanidis |first2=K. I. |date=1986-03-01 |title=A rapid Generalized Method of Bisection for solving Systems of Non-linear Equations |url=https://doi.org/10.1007/BF01389620 |journal=Numerische Mathematik |language=en |volume=49 |issue=2 |pages=123–138 |doi=10.1007/BF01389620 |issn=0945-3245|url-access=subscription }}</ref> of ''f'' is a [[polyhedron]] in R''d'', having 2d 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, f1(A)<0, f2(A)<0.
* Sign ''f''(B) = (-,+), that is, f1(B)<0, f2(B)>0.
* Sign ''f''(C) = (+,-), that is, f1(C)>0, f2(C)<0.
* Sign ''f''(D) = (+,+), that is, f1(D)>0, f2(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 ''<math>D</math>''. Then, at least <math>\log_2(D/\varepsilon)</math> bisections of edges are required so that the diameter of the remaining polygon will be at most <math>\varepsilon</math>.<ref name=":2" />{{Rp|page=11|location=Lemma.4.7}}

== See also ==
*[[Binary search algorithm]]
*[[Lehmer–Schur algorithm]], generalization of the bisection method in the complex plane
*[[Nested intervals]]

== References ==
{{reflist|30em}}
* {{Citation | last1=Burden | first1=Richard L. | last2=Faires | first2=J. Douglas | title=Numerical Analysis | publisher=Cenage Learning | edition=10th | isbn=978-1-305-25366-7 | year=2016 | chapter=2.1 The Bisection Algorithm | url-access=registration | url=https://archive.org/details/numericalanalys00burd }}

==Further reading==
* {{Citation | last1=Corliss | first1=George | title=Which root does the bisection algorithm find? | year=1977 | journal=SIAM Review | issn=1095-7200 | volume=19 | issue=2 | pages=325–327 | doi=10.1137/1019044 |ref=none}}
* {{Citation | last1=Kaw | first1=Autar | last2=Kalu | first2=Egwu | year=2008 | title=Numerical Methods with Applications | edition=1st | url=http://numericalmethods.eng.usf.edu/topics/textbook_index.html | ref=none | url-status=dead | archive-url=https://web.archive.org/web/20090413123941/http://numericalmethods.eng.usf.edu/topics/textbook_index.html | archive-date=2009-04-13 }}

== External links ==

{{wikibooks|Numerical Methods|Equation Solving}}

* [https://web.archive.org/web/20060901073129/http://numericalmethods.eng.usf.edu/topics/bisection_method.html Bisection Method] Notes, PPT, Mathcad, Maple, Matlab, Mathematica from [https://web.archive.org/web/20060906070428/http://numericalmethods.eng.usf.edu/ Holistic Numerical Methods Institute]

{{Root-finding algorithms}}

[[Category:Quasi-Newton methods]]
[[Category:Articles with example pseudocode]]
[[Category:Root-finding algorithms]]
⊤

Bisection method - Revision history

~2025-34958-91 at 22:56, 19 November 2025