Interval Halving (Bisection)

• Interval halving (bisection), an ancient but effective method for finding a zero of $f(x)$.
• It begins with two values for $x$ that bracket a root.
• The function $f(x)$ changes signs at these two x-values and, if $f(x)$ is continuous, there must be at least one root between the values.
• A plot of $f(x)$ is useful to know where to start.
• 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.
• The test to see that $f(x)$ does change sign between points $a$ and $b$ is to see if $f(a)*f(b) < 0$.

$$f(x)=3x + sin(x) - e^x$$

Look at to the plot of the function (see Fig. 3.1) to learn where the function crosses the x-axis. MATLAB can do it for us:

>> f = inline ( ' 3 *x + sin ( x) - exp ( x) ')
>> fplot ( f, [ 0 2 ]) ; grid on

And we see from the figure that indicates there are zeros at about $x=0.35$ and $1.9$.
An algorithm for Halving the Interval (Bisection):

• Think about the multiplication factor, 2
• The final Value of $x_3$ approximates the root, and it is in error by not more than $\vert x_l - x_2\vert/2$.
• The method may produce a false root if $f(x)$ is discontinuous on $[x_1,x_2]$.

To obtain the true value for the root, which is needed to compute the actual error. MATLAB surely used a more advanced method than bisection.

>> solve('3*x + sin(x) - exp(x)')
ans=
.36042170296032440136932951583028

Figure 3.1: Plot of the function: $f(x)=3x + sin(x) - e^x$

Table 3.1: The bisection method for $f(x)=3x + sin(x) - e^x$, starting from $x_1=0,x_2=1$, using a tolerance value of 1E-4.

• The main advantage of interval halving is that it is guaranteed to work if $f(x)$ is continuous in $[a,b]$ and if the values $x=a$ and $x= b$ actually bracket a root (This guarantee can be avoided, if the function has a slope very near to zero at the root, the precision of the computations may be inadequate.)
• Another important advantage that few other root-finding methods share is that the number of iterations to achieve a specified accuracy is known in advance.
• Because the interval $[a,b]$ is halved each time, the 1last value of $x_3$ differs from the true root by less than $\frac{1}{2}$ the last interval. So we can say with surely that
  $$error after n iterations<\left\vert\frac{(b-a)}{2^n} \right\vert$$

• The major objection of interval halving has been that it is slow to converge.
• Observe in Table 3.1 that the estimate of the root may be better at an earlier iteration than at later (we are closer at iteration 6 than at iteration 7.)
• In spite of arguments that other methods find roots with fewer iterations, interval halving is an important tool. Bisection is generally recommended for finding an approximate value for the root, and then this value is refined by more efficient methods. The reason is that most other root-finding methods require a starting value near to a root (lacking this, they may fail completely).
• 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.