# 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 $\u03f5=|{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{\u03f5}$)

Input: ${x}_{1},{x}_{2},f(x)$ as above. $\u03f5$ 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 |