# Interval Halving (Bisection)

• Interval halving (bisection), an ancient but effective method for finding a zero of .
• It begins with two values for that bracket a root.
• The function changes signs at these two x-values and, if is continuous, there must be at least one root between the values.
• The test to see that does change sign between points and is to see if (see Fig. 3.1).

The bisection method then

• successively divides the initial interval in half,
• finds in which half the root(s) must lie,
• and repeats with the endpoints of the smaller interval.

• A plot of is useful to know where to start.

An algorithm for halving the interval (Bisection):

• Think about the multiplication factor, 2.
• The final value of approximates the root, and it is in error by not more than .
• The method may produce a false root if is discontinuous on .

>> format long e
>> fa=1e-120;fb=-2e-300;
>> fa*fb
ans =     0
>> sign(fa)~=sign(fb)
ans =     1
• Example: Apply Bisection to . http://siber.cankaya.edu.tr/ozdogan/NumericalComputations/mfiles/chapter1/demoBisect.m m-file: demoBisect.m
>> demoBisect(3,4)

• Example: Bracketing the roots of the function, . http://siber.cankaya.edu.tr/ozdogan/NumericalComputations/mfiles/chapter1/brackPlot.m m-file: brackPlot.m
>> brackPlot('sin',-pi,pi)
>> brackPlot('sin',-2*pi,2*pi)
>> brackPlot('sin',-4*pi,4*pi)

• Now, try with a user (you!) defined function;

>> brackPlot('fx3',?,?)

In both example, try with different intervals.

• Example: The function;
• Look at to the plot of the function to learn where the function crosses the x-axis. MATLAB can do it for us:

• We see from the figure that indicates there are zeros at about and .

• To obtain the true value for the root, which is needed to compute the actual error MATLAB

• A general implementation of bisection (http://siber.cankaya.edu.tr/ozdogan/NumericalComputations//mfiles/chapter1/bisect.m m-file: bisect.m)

• It is shown above how brackPlot can be combined with bisect to find a single root of an equation.
• The same procedure can be extended to find more than one root if more than root exists. Consider the code

Use an appropriate 'myFunction', a suggestion is sine function.

The root is (almost) never known exactly, since it is extremely unlikely that a numerical procedure will find the precise value of that makes exactly zero in floating-point arithmetic.

• The main advantage of interval halving is that it is guaranteed to work (continuous & bracket).
• The algorithm must decide how close to the root the guess should be before stopping the search (see Fig. 3.3).
• This guarantee can be avoided, if the function has a slope very near to zero at the root.

• Because the interval is halved each time, the number of iterations to achieve a specified accuracy is known in advance.
• The last value of differs from the true root by less than the last interval.
• So we can say with surely that

• When there are multiple roots, interval halving may not be applicable, because the function may not change sign at points on either side of the roots.
• The major objection of interval halving has been that it is slow to converge.
• Bisection is generally recommended for finding an approximate value for the root, and then this value is refined by more efficient methods.

Cem Ozdogan 2011-12-27