interval halving

Interval halving is an efficient method for solving equations. The requirements for using this method are that we have an equation $f(x)=0$ where $f(x)$ is a continuous function, and two values $x_1$ and $x_2$ such that . Since $f(x_1)$ and $f(x_2)$ have opposite signs, we know by the intermediate value theorem that there exists a solution $\widehat{x}$ and that $x_1\le \widehat{x}\le x_2$, and with only $n+1$ function evaluations we can find a shorter interval of length $ϵ=|x_1-x_2|2^{-n}$ that contains $\widehat{x}$. If we take the solution $x_s=(x_1+x_2)/2$ we get an error .

Algorithm IntervalHalving(${\mathrm{x}}_{\mathrm{1}}\mathrm{,}{\mathrm{x}}_{\mathrm{2}}\mathrm{,}\mathrm{f}\mathtt{}\mathrm{(}\mathrm{x}\mathrm{)}\mathrm{,}\mathrm{ϵ}$)
Input: $x_1,x_2,f(x)$ as above. $ϵ$ is the length of the desired interval
Output: A solution to the equation $f(x)=0$ that lies in an interval of length . Requires

$start\leftarrow min(x_1,x_2)$
$end\leftarrow max(x_1,x_2)$
$middle\leftarrow (start+end)/2$

while
          begin

if then

$end\leftarrow middle$

else

$start\leftarrow middle$

$middle\leftarrow (start+end)/2$

end $x_s\leftarrow (start+end)/2$ // the solution

The algorithm works by taking an interval $[x_1,x_2]$ and dividing it into two intervals of equal size. Look at a point in the middle, $x_m$. If the function changes sign in the interval $[x_1,x_m]$, that is , then by the intermediate value theorem we have a solution in this interval. If not, then the solution is in the interval $[x_m,x_2]$. Repeat this until you get a sufficiently smal interval.

Interval halving is very useful in that it only requires the function to be continuous. More efficient methods like Newton’s method require that the function is differentiable and that we have to have a good starting point. Interval halving has linear convergence while Newton’s method has quadratic convergence.

Title	interval halving
Canonical name	IntervalHalving
Date of creation	2013-03-22 14:20:02
Last modified on	2013-03-22 14:20:02
Owner	mathcam (2727)
Last modified by	mathcam (2727)
Numerical id	12
Author	mathcam (2727)
Entry type	Algorithm
Classification	msc 49M15
Synonym	bisection algorithm