Interval halving is an efficient method for solving equations. The requirements for using this method are that we have an equation where is a continuous function, and two values and such that . Since and have opposite signs, we know by the intermediate value theorem that there exists a solution and that , and with only function evaluations we can find a shorter interval of length that contains . If we take the solution we get an error .
Input: as above. is the length of the desired interval
Output: A solution to the equation that lies in an interval of length . Requires
end // the solution
The algorithm works by taking an interval and dividing it into two intervals of equal size. Look at a point in the middle, . If the function changes sign in the interval , that is , then by the intermediate value theorem we have a solution in this interval. If not, then the solution is in the interval . 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.
|Date of creation||2013-03-22 14:20:02|
|Last modified on||2013-03-22 14:20:02|
|Last modified by||mathcam (2727)|