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