INTRO:
The
Bisection Method is a very well-known root-finding algorithm that always comes at the very beginning of every book on
Numerical Analysis.
The algorithm searches for a root in the interval, $latex [a_{0},b_{0}]$ in whose endpoints the
continuous problem function, $latex f(x)$, takes opposite signs:
$latex f(a_{0})f(b_{0})<0$
The
Bisection Method is based on Bolzano's
Intermediate Value Theorem, and it can give, also, an alternate proof for it. (Reference [1])
Here, it does not matter function values: The algorithm does not use any other information from $latex f(x)$, other than its sign changes.
There are excelent pages on the internet that deal with this topic, (references [1], [2] and [3] for example), and it would be useless to add more redundant and, for sure, worse presented summary about this numerical method.
I just want to take out something hidden inside the computer software, a small piece of math inside the programming area.
THE LOST FUNCTION
The core of the
Bisection Method is the conditional
IF... THEN... sentence, where the algorithm chooses in which half of the interval is the desired root.
This conditional evaluation can be converted into a
decision function, Let's say $latex \delta_i$, gives $latex 0$ if the root is on the left half interval and $latex 1$, otherwise.
Now the iterative sequence can be rewritten using this function, $latex \delta_i$, where:
$latex m_{i}$ is the midpoint of the search interval:
$latex \displaystyle m_{i}=\frac{a_{i}+b_{i}}{2}$
$latex \delta_{i}$ is the decision function, and the $latex \delta(i,j)$, in the second member, is the
Kronecker's delta:
$latex \delta_i=\delta(sgn(f(m_{i})),sgn(f(a_{i})))$
Then:
$latex \delta_{i} = \left\{ \begin{array}{ll} 1 & \mbox{if } (sgn(f(m_{i})=sgn(f(a_{i})) \\\\ 0 & \mbox{if } (sgn(f(m_{i})\neq sgn(f(a_{i})) \end{array}$
The endpoints of the search interval must be:
$latex {[a_{i+1}, b_{i+1}]} = \left\{ \begin{array}{ll} {[m_{i},b_{i}]} & \mbox{if }(\delta_{i}=0) \\\\ {[a_{i},m_{i}]} & \mbox{if } (\delta_{i}=1) \end{array}$
Then, they can be expressed with the aid of $latex \delta_{i}$, as:
$latex a_{i+1}=a_{i}+\delta_{i}\cdot (m_{i}-a_{i})$
$latex b_{i+1}=b_{i}+(1-\delta_{i})\cdot (m_{i}-b_{i})$
Note:
If $latex f(x)$, has only a single root in the interval $latex [a_{0},b_{0}]$, then it is possible to use an alternate version of the decision function:
$latex \delta_i=\delta(sgn(f(m_{i})),sgn(f(a_{0})))$
with the advantage that then it is not necessary to evaluate $latex f(a_{i})$ in the main loop of the algorithm: this implies an improvement in performance.
LENGTHS RATIO:
We can name lengths ratio between intervals $latex [a_{0},a_{i}]$, and $latex [a_{0},b_{0}]$, as the parameter:
$latex \theta_{i}=\frac{a_{i}-a_{0}}{b_{0}-a_{0}}$
If $latex \theta_{i}$ is expressed as a function of $latex \delta_{i}$:
$latex \displaystyle \theta_{i}=\sum_{k=0}^{i-1} \frac{\delta_{k}}{2^{k+1}}$
The sequence formed by the distinct values of the decision function, $latex \delta_{i}$, matches up with the
binary expansion (or the binary digits) of $latex \theta_{i}$
Then the midpoint and the endpoints of the interval in function of $latex \theta_{i}$, are:
$latex a_{i}=a_{0}+(b_{0}-a_{0})\cdot \theta_{i}$
$latex \displaystyle m_{i}=a_{0}+(b_{0}-a_{0})\cdot \left(\theta_{i}+\frac{1}{2^{i+1}}\right)$
$latex \displaystyle b_{i}=a_{0}+(b_{0}-a_{0})\cdot \left(\theta_{i}+\frac{1}{2^{i}}\right)$
HACKING BISECTION METHOD:
The connection between $latex \delta_{i}$ and $latex \theta_{i}$ can be used to turn Bisection Method into a method to find the binary expansion of a root of any function that holds with theorem hypothesis.
For example if we take:
$latex f(x)=x^2-x_{0}$, where $latex x_{0}>0$
with $latex a_{0}=0$ and $latex b_{0}=2^{k}$, where $latex 2^{k-1} < \sqrt{x_{0}} < 2^{k}$, then:
$latex \sqrt{x_{0}}=\lim_{i \to +\infty}{\theta_{i}}$
and the sequence of $latex \delta_{i}$ gives the binary digits of $latex \sqrt{x_{0}}$
Archives:
[a]-010910-Binary Bisection.nb
References:
[1]-Mohamed A. Khamsi, Helmut Knaust - SOSMATH - The Bisection Method
[2]-John H. Mathews - California State Univ. Fullerton - Module for The Bisection Method
[3]-Holistic Numerical Methods Institute- - Bisection Method: Nonlinear Equations
