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 functionMathworldPlanetmath, and two values x1 and x2 such that f(x1)f(x2)<0. Since f(x1) and f(x2) have opposite signs, we know by the intermediate value theorem that there exists a solution x^ and that x1x^x2, and with only n+1 function evaluations we can find a shorter interval of length ϵ=|x1-x2|2-n that contains x^. If we take the solution xs=(x1+x2)/2 we get an error |xs-x^|<ϵ.

Algorithm IntervalHalving(x1,x2,f(x),ϵ)
Input: x1,x2,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 f(x1)f(x2)<0


while end-start<ϵ

if f(middle)f(start)<0 then





end xs(start+end)/2 // the solution

The algorithm works by taking an interval [x1,x2] and dividing it into two intervals of equal size. Look at a point in the middle, xm. If the function changes sign in the interval [x1,xm], that is f(x1)f(xm)<0, then by the intermediate value theorem we have a solution in this interval. If not, then the solution is in the interval [xm,x2]. 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 differentiableMathworldPlanetmathPlanetmath 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