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.
• The test to see that $f(x)$ does change sign between points $a$ and $b$ is to see if $f(a)*f(b) < 0$ (see Fig. 3.1).

  Figure 3.1: Testing for a change in sign of f(x) will bracket either a root or singularity.

  

  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 $f(x)$ is useful to know where to start.

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]$.

>> format long e
>> fa=1e-120;fb=-2e-300;
>> fa*fb
ans =     0
>> sign(fa)~=sign(fb)
ans =     1

• Example: Apply Bisection to $x-x^{1/3}-2=0$. 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, $y=f(x)=sin(x)$. 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;
  $$f(x)=x-x^{1/3}-2$$

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

  In both example, try with different intervals.

• Example: The function; $f(x)=3x + sin(x) - e^x$
• Look at to the plot of the function to learn where the function crosses the x-axis. MATLAB can do it for us:

  

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

  
• We see from the figure that indicates there are zeros at about $x=0.35$ and $1.9$.

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.

• To obtain the true value for the root, which is needed to compute the actual error $\Rightarrow$ 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 $x$ that makes $f(x)$ 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).

  Figure 3.3: The stopping criterion for a root-finding procedure should involve a tolerance on $x$, as well as a tolerance on $f(x)$.

  
• This guarantee can be avoided, if the function has a slope very near to zero at the root.

• Because the interval $[a, b]$ is halved each time, the number of iterations to achieve a specified accuracy is known in advance.
• The last 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$$

• 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.