Namespaces
Variants
Actions

Difference between revisions of "Dichotomy method"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
 +
<!--
 +
d0316101.png
 +
$#A+1 = 44 n = 0
 +
$#C+1 = 44 : ~/encyclopedia/old_files/data/D031/D.0301610 Dichotomy method,
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
''method of division in halves''
 
''method of division in halves''
  
A method for numerically solving equations in a single unknown. Consider the equation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031610/d0316101.png" /> with a continuous function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031610/d0316102.png" /> on the interval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031610/d0316103.png" /> which takes values of different signs at the end points of the interval and which has a single root <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031610/d0316104.png" /> within <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031610/d0316105.png" />. To find <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031610/d0316106.png" /> approximately, one divides <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031610/d0316107.png" /> into halves and calculates the value of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031610/d0316108.png" /> at the midpoint <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031610/d0316109.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031610/d03161010.png" />, one takes the two intervals <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031610/d03161011.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031610/d03161012.png" /> and from them selects for the next dichotomy the one at the end points of which the values of the function differ in sign. This continued division into halves gives a sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031610/d03161013.png" /> which converges to the root <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031610/d03161014.png" /> with the rate of a geometrical progression:
+
A method for numerically solving equations in a single unknown. Consider the equation $  f( x) = 0 $
 +
with a continuous function $  f $
 +
on the interval $  [ a, b] $
 +
which takes values of different signs at the end points of the interval and which has a single root $  x _ {*} $
 +
within $  [ a, b] $.  
 +
To find $  x _ {*} $
 +
approximately, one divides $  [ a, b] $
 +
into halves and calculates the value of $  f( x _ {1} ) $
 +
at the midpoint $  x _ {1} = ( a+ b)/2 $.  
 +
If $  f( x _ {1} ) \neq 0 $,  
 +
one takes the two intervals $  [ a, x _ {1} ] $
 +
and $  [ x _ {1} , b] $
 +
and from them selects for the next dichotomy the one at the end points of which the values of the function differ in sign. This continued division into halves gives a sequence $  x _ {1} , x _ {2} \dots $
 +
which converges to the root $  x _ {*} $
 +
with the rate of a geometrical progression:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031610/d03161015.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>
+
$$ \tag{1 }
 +
| x _ {n} - x _ {*} |  \leq 
 +
\frac{b- a }{2  ^ {n} }
 +
,\ \
 +
n= 1, 2 \dots
 +
$$
  
where the bound (1) cannot be improved upon in this class of functions. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031610/d03161016.png" /> has more than one root in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031610/d03161017.png" />, the sequence will converge to one of them.
+
where the bound (1) cannot be improved upon in this class of functions. If $  f $
 +
has more than one root in $  [ a, b] $,
 +
the sequence will converge to one of them.
  
 
A method for minimizing a function of one variable. One has to find the minimum
 
A method for minimizing a function of one variable. One has to find the minimum
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031610/d03161018.png" /></td> </tr></table>
+
$$
 +
f _ {*}  = \min _ {a \leq  x \leq  b }  f( x)
 +
$$
  
of a unimodal function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031610/d03161019.png" /> on an interval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031610/d03161020.png" /> and to determine the point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031610/d03161021.png" /> at which it is attained. For this, one divides <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031610/d03161022.png" /> into halves and near the middle <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031610/d03161023.png" /> calculates the values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031610/d03161024.png" /> at the two points <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031610/d03161025.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031610/d03161026.png" />, where the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031610/d03161027.png" /> is a parameter of the method and is sufficiently small. Then the values <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031610/d03161028.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031610/d03161029.png" /> are compared, and on the basis that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031610/d03161030.png" /> is unimodal one selects from the two intervals <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031610/d03161031.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031610/d03161032.png" /> the one that certainly contains <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031610/d03161033.png" />. For example, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031610/d03161034.png" />, this will be <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031610/d03161035.png" />, otherwise <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031610/d03161036.png" />. The interval is again divided into halves, and near the middle <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031610/d03161037.png" /> one takes two points <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031610/d03161038.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031610/d03161039.png" />, compares the values of the function, etc. As a result, one obtains a sequence of midpoints <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031610/d03161040.png" /> for which
+
of a unimodal function $  f $
 +
on an interval $  [ a, b] $
 +
and to determine the point $  x _ {*} $
 +
at which it is attained. For this, one divides $  [ a, b] $
 +
into halves and near the middle $  \overline{x}\; _ {1} = ( a+ b)/2 $
 +
calculates the values of $  f $
 +
at the two points $  x _ {1} = \overline{x}\; _ {1} - \epsilon /2 $
 +
and $  x _ {2} = \overline{x}\; _ {1} + \epsilon /2 $,  
 +
where the number $  \epsilon > 0 $
 +
is a parameter of the method and is sufficiently small. Then the values $  f( x _ {1} ) $
 +
and $  f( x _ {2} ) $
 +
are compared, and on the basis that $  f $
 +
is unimodal one selects from the two intervals $  [ a, x _ {2} ] $
 +
and $  [ x _ {1} , b] $
 +
the one that certainly contains $  x _ {*} $.  
 +
For example, if $  f( x _ {1} ) \leq  f( x _ {2} ) $,  
 +
this will be $  [ a, x _ {2} ] $,  
 +
otherwise $  [ x _ {1} , b] $.  
 +
The interval is again divided into halves, and near the middle $  \overline{x}\; _ {2} $
 +
one takes two points $  x _ {1} = \overline{x}\; _ {2} - \epsilon /2 $
 +
and $  x _ {2} = \overline{x}\; _ {2} + \epsilon /2 $,  
 +
compares the values of the function, etc. As a result, one obtains a sequence of midpoints $  \{ \overline{x}\; _ {n} \} $
 +
for which
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031610/d03161041.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>
+
$$ \tag{2 }
 +
| \overline{x}\; _ {n} - x _ {*} |  \leq 
 +
\frac{b- a- \epsilon }{2  ^ {n} }
 +
+
 +
\frac \epsilon {2}
 +
,\ \
 +
n= 1, 2 , .  . . .
 +
$$
  
As an approximation to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031610/d03161042.png" /> the value <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031610/d03161043.png" /> for sufficiently large <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031610/d03161044.png" /> is taken.
+
As an approximation to $  f _ {*} $
 +
the value $  f( \overline{ {x }}\; _ {n} ) $
 +
for sufficiently large $  n $
 +
is taken.
  
 
The name is given to the method because at each step in this algorithm the segment containing the minimum becomes approximately half the length. The dichotomy method is not the best in the class of unimodal functions. There are more effective methods that enable one to use the same number of calculations on the values of the function to obtain an accuracy better than that of (2) (see, for example, the [[Fibonacci method|Fibonacci method]]).
 
The name is given to the method because at each step in this algorithm the segment containing the minimum becomes approximately half the length. The dichotomy method is not the best in the class of unimodal functions. There are more effective methods that enable one to use the same number of calculations on the values of the function to obtain an accuracy better than that of (2) (see, for example, the [[Fibonacci method|Fibonacci method]]).
Line 21: Line 88:
 
====References====
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  B.P. Demidovich,  I.A. Maron,  "Foundations of computational mathematics" , Moscow  (1966)  (In Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  D.J. Wilde,  "Optimum seeking methods" , Prentice-Hall  (1964)</TD></TR></table>
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  B.P. Demidovich,  I.A. Maron,  "Foundations of computational mathematics" , Moscow  (1966)  (In Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  D.J. Wilde,  "Optimum seeking methods" , Prentice-Hall  (1964)</TD></TR></table>
 
 
  
 
====Comments====
 
====Comments====

Latest revision as of 17:33, 5 June 2020


method of division in halves

A method for numerically solving equations in a single unknown. Consider the equation $ f( x) = 0 $ with a continuous function $ f $ on the interval $ [ a, b] $ which takes values of different signs at the end points of the interval and which has a single root $ x _ {*} $ within $ [ a, b] $. To find $ x _ {*} $ approximately, one divides $ [ a, b] $ into halves and calculates the value of $ f( x _ {1} ) $ at the midpoint $ x _ {1} = ( a+ b)/2 $. If $ f( x _ {1} ) \neq 0 $, one takes the two intervals $ [ a, x _ {1} ] $ and $ [ x _ {1} , b] $ and from them selects for the next dichotomy the one at the end points of which the values of the function differ in sign. This continued division into halves gives a sequence $ x _ {1} , x _ {2} \dots $ which converges to the root $ x _ {*} $ with the rate of a geometrical progression:

$$ \tag{1 } | x _ {n} - x _ {*} | \leq \frac{b- a }{2 ^ {n} } ,\ \ n= 1, 2 \dots $$

where the bound (1) cannot be improved upon in this class of functions. If $ f $ has more than one root in $ [ a, b] $, the sequence will converge to one of them.

A method for minimizing a function of one variable. One has to find the minimum

$$ f _ {*} = \min _ {a \leq x \leq b } f( x) $$

of a unimodal function $ f $ on an interval $ [ a, b] $ and to determine the point $ x _ {*} $ at which it is attained. For this, one divides $ [ a, b] $ into halves and near the middle $ \overline{x}\; _ {1} = ( a+ b)/2 $ calculates the values of $ f $ at the two points $ x _ {1} = \overline{x}\; _ {1} - \epsilon /2 $ and $ x _ {2} = \overline{x}\; _ {1} + \epsilon /2 $, where the number $ \epsilon > 0 $ is a parameter of the method and is sufficiently small. Then the values $ f( x _ {1} ) $ and $ f( x _ {2} ) $ are compared, and on the basis that $ f $ is unimodal one selects from the two intervals $ [ a, x _ {2} ] $ and $ [ x _ {1} , b] $ the one that certainly contains $ x _ {*} $. For example, if $ f( x _ {1} ) \leq f( x _ {2} ) $, this will be $ [ a, x _ {2} ] $, otherwise $ [ x _ {1} , b] $. The interval is again divided into halves, and near the middle $ \overline{x}\; _ {2} $ one takes two points $ x _ {1} = \overline{x}\; _ {2} - \epsilon /2 $ and $ x _ {2} = \overline{x}\; _ {2} + \epsilon /2 $, compares the values of the function, etc. As a result, one obtains a sequence of midpoints $ \{ \overline{x}\; _ {n} \} $ for which

$$ \tag{2 } | \overline{x}\; _ {n} - x _ {*} | \leq \frac{b- a- \epsilon }{2 ^ {n} } + \frac \epsilon {2} ,\ \ n= 1, 2 , . . . . $$

As an approximation to $ f _ {*} $ the value $ f( \overline{ {x }}\; _ {n} ) $ for sufficiently large $ n $ is taken.

The name is given to the method because at each step in this algorithm the segment containing the minimum becomes approximately half the length. The dichotomy method is not the best in the class of unimodal functions. There are more effective methods that enable one to use the same number of calculations on the values of the function to obtain an accuracy better than that of (2) (see, for example, the Fibonacci method).

References

[1] B.P. Demidovich, I.A. Maron, "Foundations of computational mathematics" , Moscow (1966) (In Russian)
[2] D.J. Wilde, "Optimum seeking methods" , Prentice-Hall (1964)

Comments

The first example of the two dichotomy methods described above is known as the bisection method in the English literature. It is the classical example of an enclosure method (a two-sided method). Since its convergence is fairly slow, one has tried to device more rapidly converging methods. One such method which is often (but not always) faster than the bisection method and whose convergence is also guaranteed, is the Regula Falsi method (method of false position, see, e.g., [a1]). A modification of this method that avoids the disadvantage of the Regula Falsi method is a method of H. Brent [a2], which is based on an earlier algorithm of T. Dekker [a3].

A unimodal function on an interval is a function having only one extremum within the interval.

References

[a1] K.E. Atkinson, "An introduction to numerical analysis" , Wiley (1978)
[a2] H. Brent, "Algorithms for minimization without derivatives" , Prentice-Hall (1973)
[a3] T. Dekker, "Finding a zero by successive linear interpolation" B. Dejon (ed.) P. Henrici (ed.) , Constructive aspects of the fundamental theorem of algebra , Wiley (1969) pp. 37–48
How to Cite This Entry:
Dichotomy method. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Dichotomy_method&oldid=12591
This article was adapted from an original article by M.M. Potapov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article