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

  Figure 3.2: 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.
• 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.

      1 import numpy as np
      2 from math import *
      3 def f(x):
      4     return 3*x+sin(x)-exp(x)
      5 xval=[]
      6 funval=[]
      7 kfirst=0.0; klast=2.0; kincrement=0.01
      8 for j in np.arange(kfirst, klast + kincrement, kincrement):
      9     xval.append(j)
     10     funval.append(f(j))
     11 import matplotlib.pyplot as plt
     12 plt.title('$f(x)=3x+sin(x)-e^x$')
     13 plt.xlabel('X Value')
     14 plt.ylabel('Function Value')
     15 plt.plot(xval, funval, '-')
     16 plt.grid()
     17 plt.savefig('function_plot.eps')
     18 plt.show()
  

  Figure 3.3: Code and 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$.

• Apply Bisection method to $f(x)=3x + sin(x) - e^x$. (Example py-file: mybisect.py)

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.).
• The major objection of interval halving has been that it is slow to converge.

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

Bisection is generally recommended for finding an approximate value for the root, and then this value is refined by more efficient methods.