Bisection method: Difference between revisions

Latest revision as of 02:20, 26 December 2025

Template:Short description Script error: No such module "about".

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

In mathematics, the bisection method is a root-finding method that applies to any continuous function for which one knows two values with opposite signs. The method consists of repeatedly bisecting the interval defined by these values, then selecting the subinterval in which the function changes sign, which therefore must contain a 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.^[1] The method is also called the interval halving method,^[2] the binary search method,Template:Efn^[3] or the dichotomy method.^[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

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 the same signs,

then the method sets $a = c$ ,
else the method sets $b = c$ .

In both cases, the new $f (a)$ and $f (b)$ have opposite signs, so the method may be applied to this smaller interval.^[6]

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 ( $ϵ$ ). Burden and Faires (2016) identify the three stopping conditions:^[7]

Absolute tolerance: $| p_{N} - p_{N - 1} | < ϵ$
Relative tolerance: $| \frac{p_{N} - p_{N - 1}}{p_{N}} | < ϵ,$ || $p_{N} \neq 0$
$| f (p_{N}) | < ϵ .$

$| f (p_{N}) | < ϵ$ does not give an accurate result to within $ϵ$ unless $| f^{'} (p_{N}) | \geq 1$ . The other two possibilities represent different concepts: the absolute difference $| c - a | \leq 5 \times 1 0^{- t}$ says that c and a are the same to $t$ decimal places, while the relative difference $| \frac{c - a}{c} | \leq 5 \times 1 0^{- t}$ says that c and a are the same to $t$ significant figures.^[8] If nothing is known about the value of the root, then relative tolerance is the best stopping condition.^[9]

Iteration process

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

Calculate $c$ , the midpoint of the interval, $c = \frac{a + b}{2}$ ;
Calculate the function value at the midpoint, $f (c)$ ;
If $f (c) = 0$ , return c;
If convergence is satisfactory (that is, $| c - a | \leq 5 \times 1 0^{- t} | c |$ ), return $c$ ;
Examine the sign of $f (c)$ and replace either $a$ or $b$ with $c$ 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

f (x) = x^{3} - x - 2 .

First, two numbers $a$ and $b$ have to be found such that $f (a)$ and $f (b)$ have opposite signs. For the above function, $a = 1$ and $b = 2$ satisfy this criterion, as

f (1) = (1)^{3} - (1) - 2 = - 2

and

f (2) = (2)^{3} - (2) - 2 = + 4 .

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:

Iteration	$a_{n}$	$b_{n}$	$c_{n}$	$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.

Generalization to higher dimensions

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

Methods based on degree computation

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

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^[13] (also called an admissible polygon)^[14] 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, ATemplate:--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 Template:Mvar. Then, at least $\log_{2} (D / ε)$ bisections of edges are required so that the diameter of the remaining polygon will be at most $ε$ .^[14]Template:Rp

Notes

Template:Notelist

References

↑ Script error: No such module "Footnotes".
↑ Script error: No such module "citation/CS1".
↑ Script error: No such module "Footnotes".
↑ Script error: No such module "citation/CS1".
↑ If the function has the same sign at the endpoints of an interval, the endpoints may or may not bracket roots of the function.
↑ Script error: No such module "Footnotes".
↑ Script error: No such module "Footnotes".
↑ Script error: No such module "Footnotes".
↑ Script error: No such module "Footnotes".
↑ Script error: No such module "Citation/CS1".
↑ Script error: No such module "Citation/CS1".
↑ Script error: No such module "Citation/CS1".
↑ Script error: No such module "Citation/CS1".
↑ ^a ^b Script error: No such module "Citation/CS1".

Script error: No such module "Check for unknown parameters".

Script error: No such module "citation/CS1".

External links

Script error: No such module "Side box".

Bisection Method Notes, PPT, Mathcad, Maple, Matlab, Mathematica from Holistic Numerical Methods Institute

Template:Root-finding algorithms ⊤

[1] Script error: No such module "Footnotes".

[2] Script error: No such module "citation/CS1".

[3] Script error: No such module "Footnotes".

[4] Script error: No such module "citation/CS1".

[5] If the function has the same sign at the endpoints of an interval, the endpoints may or may not bracket roots of the function.

[6] Script error: No such module "Footnotes".

[7] Script error: No such module "Footnotes".

[8] Script error: No such module "Footnotes".

[9] Script error: No such module "Footnotes".

[10] Script error: No such module "Citation/CS1".

[11] Script error: No such module "Citation/CS1".

[12] Script error: No such module "Citation/CS1".

[13] Script error: No such module "Citation/CS1".

[:2-14] Script error: No such module "Citation/CS1".

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

@@ Line 1: / Line 1: @@
 {{short description|Algorithm for finding a zero of a function}}
-{{about|searching 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)}}
+{{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 [a<sub>1</sub>;b<sub>1</sub>]. 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 and then selecting the  subinterval in which the function changes sign, and 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|1985|p=31}}</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|1985|p=28}}</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>
+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 method''',{{efn|Not to be confused with the [[binary search algorithm]] of searching a finite sorted array.}}<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 ''f''(''x'')&nbsp;=&nbsp;0 for the [[Real number|real]] variable ''x'', where ''f'' is a [[continuous function]] defined on an interval [''a'',&nbsp;''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'').
+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 ''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.<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 ''f'' is reduced in width by 50% at each step. The process is continued until the interval is sufficiently small.
+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 ''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.<ref>{{Harvnb|Burden|Faires|1985|p=28}} for section</ref>
+Explicitly, if <math>f(c)=0</math>  then <math>c</math> may be taken as the solution and the process stops.
-=== Iteration tasks ===
+Otherwise,
-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:
+if <math>f(a)</math> and <math>f(c)</math> have the same signs,
-# Calculate ''c'', the midpoint of the interval, ''c'' = {{sfrac|''a ''+ ''b''|2}}.
+*then the method sets <math>a = c</math>,
-# Calculate the function value at the midpoint, ''f''(''c'').
+*else  the method sets <math>b = c</math>.
-# If convergence is satisfactory (that is, ''c'' &minus; ''a'' is sufficiently small, or |''f''(''c'')| is sufficiently small), return ''c'' and stop iterating.
+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>
-# 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.
-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 {{math|1=''f''(''x'') = cos ''x''}}; there is no floating-point value approximating {{math|1=''x'' = {{pi}}/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 {{math|[''a'', ''b'']}} will be numerically identical to (within floating point precision of) either ''a'' or ''b''.
+Once the process starts, the signs at the left and right ends of the interval remain the same for all iterations.
-===Algorithm===
+=== Stopping conditions===
-The method may be written in [[pseudocode]] as follows:<ref>{{Harvnb|Burden|Faires|1985|p=29}}. This version recomputes the function values at each iteration rather than carrying them to the next iterations.</ref>
+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>
- '''input:''' Function ''f'',
+* Absolute tolerance: <math>|p_N-p_{N-1}|<\epsilon</math>
-        endpoint values ''a'', ''b'',
+* Relative tolerance: <math>\left|\frac{p_N-p_{N-1}}{p_N}\right|<\epsilon,</math>||<math>p_N\ne 0</math>
-        tolerance ''TOL'',
+* <math>|f(p_N)|<\epsilon.</math>
-        maximum iterations ''NMAX''
+<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>
- '''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'' '''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 interval''
- '''end while'''
- Output("Method failed.") ''// max number of steps exceeded''
-=== Example: Finding the root of a polynomial ===
+=== 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>
@@ Line 53: / Line 46: @@
 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].
+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:
-In the first iteration, the end points of the interval which brackets the root are  <math> a_1 = 1 </math> and <math> b_1 = 2 </math>, so the midpoint is
-:<math> c_1 = \frac{2+1}{2} = 1.5 </math>
-The function value at the midpoint is <math> f(c_1) = (1.5)^3 - (1.5) - 2 = -0.125 </math>. Because <math> f(c_1) </math> is negative,  <math> a = 1 </math> is replaced with <math> a = 1.5 </math> for the next iteration to ensure that <math> f(a) </math> and <math> f(b) </math> have opposite signs.  As this continues, the interval between <math> a </math> and <math> b </math> will become increasingly smaller, converging on the root of the function.  See this happen in the table below.
 {| class="wikitable"
 ! Iteration !! <math>a_n</math> !! <math>b_n</math> !! <math>c_n</math> !! <math>f(c_n)</math>
@@ Line 94: / Line 82: @@
 After 13 iterations, it becomes apparent that there is a convergence to about 1.521: a root for the polynomial.
-== Analysis ==
-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 [[approximation error|absolute error]] is halved at each step so the method [[Rate of convergence|converges linearly]]. Specifically, if ''c''<sub>1</sub> = {{sfrac|''a''+''b''|2}} is the midpoint of the initial interval, and ''c''<sub>''n''</sub> is the midpoint of the interval in the ''n''th step, then the difference between ''c''<sub>''n''</sub> and a solution ''c'' is bounded by<ref>{{Harvnb|Burden|Faires|1985|p=31}}, Theorem 2.1</ref>
-:<math>|c_n-c|\le\frac{|b-a|}{2^n}.</math>
-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
-:<math>n \le n_{1/2} \equiv \left\lceil\log_2\left(\frac{\epsilon_0}{\epsilon}\right)\right\rceil, </math>
-where the initial bracket size <math>\epsilon_0 = |b-a|</math> and the required bracket size <math>\epsilon \le \epsilon_0.</math> 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<sub>n</sub>  to the solution c that in the ''worst case'' has an <math>\epsilon</math> absolute error with less than  n<sub>1/2</sub>  iterations.<ref name=":0">{{Cite journal|last=Sikorski|first=K.|date=1982-02-01|title=Bisection is optimal|url=https://doi.org/10.1007/BF01459080|journal=Numerische Mathematik|language=en|volume=40|issue=1|pages=111–117|doi=10.1007/BF01459080|s2cid=119952605 |issn=0945-3245}}</ref> This is also true under several common assumptions on function f and the behaviour of the function in the neighbourhood of the root.<ref name=":0" /><ref>{{Cite journal|last=Sikorski|first=K|date=1985-12-01|title=Optimal solution of nonlinear equations|journal=Journal of Complexity|language=en|volume=1|issue=2|pages=197–209|doi=10.1016/0885-064X(85)90011-1|issn=0885-064X|doi-access=}}</ref>
-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 <ref>{{Cite journal|last1=Graf|first1=Siegfried|last2=Novak|first2=Erich|last3=Papageorgiou|first3=Anargyros|date=1989-07-01|title=Bisection is not optimal on the average|url=https://doi.org/10.1007/BF01396051|journal=Numerische Mathematik|language=en|volume=55|issue=4|pages=481–491|doi=10.1007/BF01396051|s2cid=119546369 |issn=0945-3245}}</ref><ref>{{Cite journal|last=Novak|first=Erich|date=1989-12-01|title=Average-case results for zero finding|journal=Journal of Complexity|language=en|volume=5|issue=4|pages=489–501|doi=10.1016/0885-064X(89)90022-8|issn=0885-064X|doi-access=free}}</ref> as well as ''asymptotic performance''.<ref name=":1">{{Cite journal|last1=Oliveira|first1=I. F. D.|last2=Takahashi|first2=R. H. C.|date=2020-12-06|title=An Enhancement of the Bisection Method Average Performance Preserving Minmax Optimality|url=https://doi.org/10.1145/3423597|journal=ACM Transactions on Mathematical Software|volume=47|issue=1|pages=5:1–5:24|doi=10.1145/3423597|s2cid=230586635 |issn=0098-3500}}</ref> 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 [[Rate of convergence|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]].<ref name=":1" /><ref>{{Cite web|last=Ivo|first=Oliveira|date=2020-12-14|title=An Improved Bisection Method|doi=10.1145/3423597 |s2cid=230586635 |url=https://link.growkudos.com/1iwxps83474}}</ref>{{Primary source inline|date=November 2024}}
-<!-- Therefore, the linear convergence is expressed by <math>\epsilon_{n+1} = \text{constant} \times \epsilon_n^m, \ m=1 .</math> :: Commented out; "Therefore"? If this needs to be said, it has to be said in a better way. -->
 == Generalization to higher dimensions ==
-The bisection method has been generalized to multi-dimensional functions. Such methods are called '''generalized bisection methods'''.<ref>{{Cite journal |last1=Mourrain |first1=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 |journal=Journal of Complexity |language=en |volume=18 |issue=2 |pages=612–640 |doi=10.1006/jcom.2001.0636 |issn=0885-064X|doi-access=free }}</ref><ref>{{Cite book |last=Vrahatis |first=Michael N. |title=Numerical Computations: Theory and Algorithms |chapter=Generalizations of the Intermediate Value Theorem for Approximating Fixed Points and Zeros of Continuous Functions |series=Lecture Notes in Computer Science |date=2020 |volume=11974 |editor-last=Sergeyev |editor-first=Yaroslav D. |editor2-last=Kvasov |editor2-first=Dmitri E. |chapter-url=https://link.springer.com/chapter/10.1007/978-3-030-40616-5_17 |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|s2cid=211160947 }}</ref>
+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]], which for a bounded region <math>\Omega \subseteq \mathbb{R}^n</math> and a differentiable function <math>f: \mathbb{R}^n \rightarrow \mathbb{R}^n</math> is defined as a sum over its roots:
+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>
-:<math>\deg(f, \Omega) := \sum_{y\in f^{-1}(\mathbf{0})} \sgn \det(Df(y))</math>,
-where <math>Df(y)</math> is the [[Jacobian matrix]], <math>\mathbf{0} = (0,0,...,0)^T</math>, and
-:<math>\sgn(x) = \begin{cases}
-, & x>0 \\
-, & x=0 \\
--1, & x<0 \\
-\end{cases}</math>
-is the [[sign function]].<ref>{{cite journal |last1=Polymilis |first1=C. |last2=Servizi |first2=G. |last3=Turchetti |first3=G. |last4=Skokos |first4=Ch. |last5=Vrahatis |first5=M. N. |journal=Libration Point Orbits and Applications |title=Locating Periodic Orbits by Topological Degree Theory |date=May 2003 |pages=665–676 |doi=10.1142/9789812704849_0031 |arxiv=nlin/0211044 |isbn=978-981-238-363-1 }}</ref> In order for a root to exist, it is sufficient that <math>\deg(f, \Omega) \neq 0</math>, and this can be verified using a [[surface integral]] over the boundary of <math>\Omega</math>.<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 |s2cid=122058552 |issn=0945-3245}}</ref>
 === Characteristic bisection method ===
-The '''characteristic bisection method''' uses only the signs of a function in different points. Lef ''f'' be a function from R<sup>d</sup> to R<sup>d</sup>, 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 |bibcode=1995JCoPh.119..105V |issn=0021-9991}}</ref>''' (also called an '''admissible polygon''')<ref name=":2">{{Cite journal |last1=Vrahatis |first1=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 |s2cid=121771945 |issn=0945-3245}}</ref> of ''f'' is a [[polytope]] in R<sup>''d''</sup>, having 2<sup>d</sup> vertices, such that in each vertex '''v''', the combination of signs of ''f''('''v''') is unique and the [[Degree of a continuous mapping#Maps from closed region|topological degree of ''f'' on its interior]] is not zero (a necessary criterion to ensure the existence of a root).<ref name=":3">{{cite journal |last1=Vrahatis |first1=M.N. |last2=Perdiou |first2=A.E. |last3=Kalantonis |first3=V.S. |last4=Perdios |first4=E.A. |last5=Papadakis |first5=K. |last6=Prosmiti |first6=R. |last7=Farantos |first7=S.C. |title=Application of the Characteristic Bisection Method for locating and computing periodic orbits in molecular systems |journal=Computer Physics Communications |date=July 2001 |volume=138 |issue=1 |pages=53–68 |doi=10.1016/S0010-4655(01)00190-4|bibcode=2001CoPhC.138...53V }}</ref> For example, for ''d''=2, a characteristic polyhedron of ''f'' is a [[quadrilateral]] with vertices (say) A,B,C,D, such that:
+The '''characteristic bisection method''' uses only the signs of a function in different points. Lef ''f'' be a function from R<sup>''d''</sup> to R<sup>''d''</sup>, 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<sup>''d''</sup>, having 2<sup>''d''</sup> 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:
-* {{tmath|1=\sgn f(A) = (-,-)}}, that is, ''f''<sub>1</sub>(A)<0, ''f''<sub>2</sub>(A)<0.
+* Sign ''f''(A) = (&minus;,&minus;), that is, ''f''<sub>1</sub>(A)<0, ''f''<sub>2</sub>(A)<0.
-* {{tmath|1=\sgn f(B) = (-,+)}},  that is, ''f''<sub>1</sub>(B)<0, ''f''<sub>2</sub>(B)>0.
+* Sign ''f''(B) = (&minus;,+),  that is, ''f''<sub>1</sub>(B)<0, ''f''<sub>2</sub>(B)>0.
-* {{tmath|1=\sgn f(C) = (+,-)}},  that is, ''f''<sub>1</sub>(C)>0, ''f''<sub>2</sub>(C)<0.
+* Sign ''f''(C) = (+,&minus;),  that is, ''f''<sub>1</sub>(C)>0, ''f''<sub>2</sub>(C)<0.
-* {{tmath|1=\sgn f(D) = (+,+)}},  that is, ''f''<sub>1</sub>(D)>0, ''f''<sub>2</sub>(D)>0.
+* Sign ''f''(D) = (+,+),  that is, ''f''<sub>1</sub>(D)>0, ''f''<sub>2</sub>(D)>0.
-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. 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.
+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 {{tmath|1=\sgn f(M) = \sgn(A)}}, then A is replaced by M, and we get a smaller characteristic polyhedron.
+* If Sign ''f''(M) = Sign(A), then A is replaced by M, and we get a smaller characteristic polyhedron.
-* If {{tmath|1=\sgn f(M) = \sgn(B)}}, then B 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 {{mvar|D}}. 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}}
-Suppose the diameter (= length of longest proper edge) of the original characteristic polyhedron is {{mvar|D}}. 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 {{mvar|&epsilon;}}.<ref name=":2" />{{Rp|page=11|location=Lemma.4.7}} If the topological degree of the initial polyhedron is not zero, then there is a procedure that can choose an edge such that the next polyhedron also has nonzero degree.<ref name=":3"/><ref>{{cite journal |last1=Vrahatis |first1=Michael N. |title=Solving systems of nonlinear equations using the nonzero value of the topological degree |journal=ACM Transactions on Mathematical Software |date=December 1988 |volume=14 |issue=4 |pages=312–329 |doi=10.1145/50063.214384}}</ref>
 == See also ==
@@ Line 141: / Line 109: @@
 *[[Lehmer–Schur algorithm]], generalization of the bisection method in the complex plane
 *[[Nested intervals]]
+== Notes ==
+{{notelist}}
 == References ==
 {{reflist|30em}}
-* {{Citation | last1=Burden | first1=Richard L. | last2=Faires | first2=J. Douglas | title=Numerical Analysis | publisher=PWS Publishers | edition=3rd | isbn=0-87150-857-5 | year=1985 | chapter=2.1 The Bisection Algorithm | url-access=registration | url=https://archive.org/details/numericalanalys00burd }}
+* {{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==
@@ Line 151: / Line 122: @@
 == External links ==
-{{wikiversity|The bisection method}}
 {{wikibooks|Numerical Methods|Equation Solving}}
-*{{MathWorld|title=Bisection|urlname=Bisection}}
 * [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: Difference between revisions

Latest revision as of 02:20, 26 December 2025

Contents

The method

Stopping conditions

Iteration process

Example

Generalization to higher dimensions

Methods based on degree computation

Characteristic bisection method

See also

Notes

References

Further reading

External links

Navigation menu

Bisection method: Difference between revisions

Latest revision as of 02:20, 26 December 2025

The method

Stopping conditions

Iteration process

Example

Generalization to higher dimensions

Methods based on degree computation

Characteristic bisection method

See also

Notes

References

Further reading

External links

Navigation menu

Search