Laboratory 5 - The Bisection root finding method

Finding a "root" (or a "zero") of a nonlinear function is a generic widely used numerical technique in engineering problem solving, and we will demonstrate the approach in terms of a simple example. Assume that we wish to determine the value of . We recall that , thus we can rephrase the problem as "what value of x makes sin(x) zero?". Consider the plot of sin(x) between x = 0 to , as shown below:

The first thing that we notice is there are in fact three roots in this range, at x = 0, , and . This leads to an ambiguity, and, unlike humans, computers cannot cope with ambiguity. We have to be sure to choose a range of x such as to isolate a single root.

There are many different root finding techniques available, and the simplest and most popular method is the so-called "Bisection" method. This method is illustrated in the following plot (notice the range of x has been reduced to [1, 4].)

• We first check whether there exists a single root between low and high. This can be done by determining that sin(low) is of opposite sign to that of sin(high) as follows:

     if(sin(low) * sin(high) > 0.0) 
        cout << "WARNING! No single solution within bounds [" 
             << low << ", " << high << "]\n";

• We then "bisect" the domain by determining the midpoint mid. If (as in our example above) the sign of sin(mid) is the same as that of sin(low), we reduce the entire search domain in half by simply assigning to low the value mid (low = mid), otherwise we assign to high the value of mid. Obviously whenever we change the value of low or high we need to re-evaluate mid, as shown.

mid = (low + high) / 2.0;
if(sin(low) * sin(mid) > 0.0)
   low = mid;
else
   high = mid;
mid = (low + high) / 2.0;

• This process is repeated in a while loop until the range of (high - low) is less than some small value (pronounced "epsilon"). When this is completed then the last value of mid will in fact be the required root.

      while(fabs(high - low) > epsilon) {

              /* loop statements */ 

      }

We now come to the actual lab - putting this all together. Change directory to the week5/lab-sinroot directory and list the various files as follows:

cd /home/condor/et181/week5/lab_sinroot
ls

Copy the program sinroot.cpp to your home directory, and return to your home directory as follows:

cp sinroot.cpp ~
cd

The listing of this program follows:

//********************************************************************** // FILENAME: sinroot.cpp * // PROGRAMMER: Dr.Iz (Urieli) * // DATE: 08/14/03 * // USAGE: The user is requested to enter a lo and hi value in * // radians as well as the required accuracy of the solution * // (epsilon), and the root of sine(x) within bounds [lo, hi] * // is evaluated and displayed. * // DESCRIPTION: The bisection method function "sin_root" is used * // to evaluate the root, if a valid single root exists. * //********************************************************************** #include <iostream> #include <cmath> using namespace std; float sin_root(float lo, float hi, float epsilon); // The root of sine(x) within [lo, hi], accuracy epsilon int main() { float lo, hi, epsilon, root; cout << "evaluate the root of sin(x) using bisection method\n"; cout << "enter the lo and hi bounds of x in radians\n"; cin >> lo >> hi; cout << "bounds entered are [" << lo << "," << hi << "]\n"; cout << "enter the allowable error bound (epsilon)\n"; cin >> epsilon; cout << "error bound entered is " << epsilon << endl; root = sin_root(lo, hi, epsilon); cout << "root is " << root << endl; return 0; } //********************************************************************** // FUNCTION: sin_root * // to find the root of the <cmath> function "sin" * // FILENAME: sinroot.cpp * // PROGRAMMER: (your name) * // DATE: (tpdays date) * // PRE: float bounds [lo, hi] have values * // epsilon (allowable error in root) has a value * // POST: either the float root has been determined within a * // tolerance epsilon and has been returned * // or a warning message has been displayed * //********************************************************************** float sin_root(float lo, float hi, float epsilon) { //####################################################################### // replace the following "stub" with the correct function "sin_root" cout << "you have entered the function \"sin_root\"\n"; cout << "at this stage only a stub returning value 0\n"; return 0; //####################################################################### }

Once your program is working, you will need to consider a number of exception conditions:

• There is no single root enclosed by the bounds lo and hi. In this case a warning message should be printed out and value zero should be returned.
  
• The value epsilon chosen is unrealistic (e.g. zero). This can easily lead to an infinite loop, one of the seven deadly sins of programming! You should limit the number of loop repetitions to a value imax (choose a suitable value) and print out a warning message if the number of loop cycles reaches this value.

Be sure to show what you have done to the lab tutor. You will be graded on the work that you do during the lab session.

Telnet: "condor"