# Dichotomy method

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)