Due: in the CSE dropbox by 5pm Eastern time Monday 18 February 2008. Remember to upload the Java file and not the class file.

You are to write a simple version of a bisection method for finding roots of equations. As explained in class, if a continuous function f(x) is negative for some value xLeft and is positive for some value xRight then the function must have a zero at some point between xLeft and xRight .

If this is true, then we may approximate the root of f(x) by the midpoint of the interval between xLeft and xRight ; this midpoint has the value
xMid = (xRight - xLeft)/2.0 .
If we make this approximation, that is, if we declare the approximate value of the root of f(x) to be
xMid = (xRight - xLeft)/2.0 ,
then the maximum error in our approximation is the distance from xMid to either end of the interval, and this distance is
Math.abs( xLeft - xMid ) = Math.abs( xRight - xMid ) .

Rules:

• You are to input the error tolerance epsilon as well as the initial values for xLeft and xRight from the console; use the third version of the main class for the Newton method code (on the website) as your template for this. Your main method should thus take these three values as input, check for correctness, echo the values back, and then invoke with
  root = rootFinder.findRoot(xLeft,xRight,epsilon)
  a method that do the bisection method. The main class should also print out the root and a message that says the program is terminating normally.
• You should check in the main class that xLeft < xRight and exit the program if they are not.
• You need not do the checking to ensure that the three input values are in fact double values.
• YOU MAY ASSUME in your code that the function is negative at the left endpoint and is positive at the right endpoint, and not the other way around. To handle both cases requires a slightly more complicated control structure, as was explained in class.
• You must include in your program a System.out.println() statement inside the loop that will print out the left endpoint, midpoint, right endpoint, functional value, and error approximation at every iteration.
• READ TO THE BOTTOM TO FIND OUT WHAT YOU NEED TO TURN IN!!!!
• Test your program with a cubic polynomial method hard-coded as

    private double f(double x)
    {
      double returnValue;
      returnValue = x*x*x + 2.0*x*x + 4.0*x + 6.0;
      return returnValue;
    }
  

  If you do this, and if you use 0.01 as the tolerance epsilon and if you use -4.0 and 4.0 as the endpoints, then you might get

  Find a root between -4.0 and 4.0
  Stop when the approximation is within < 0.01 of the root
  Original: left:-4.0 mid:0.0 right:4.0 f(xMid):6.0
      error:4.0
  New: left:-4.0 mid:-2.0 right:0.0 f(xMid):-2.0
      error:2.0
  New: left:-2.0 mid:-1.0 right:0.0 f(xMid):3.0
      error:1.0
  New: left:-2.0 mid:-1.5 right:-1.0 f(xMid):1.125
      error:0.5
  New: left:-2.0 mid:-1.75 right:-1.5 f(xMid):-0.234375
      error:0.25
  New: left:-1.75 mid:-1.625 right:-1.5 f(xMid):0.490234375
      error:0.125
  New: left:-1.75 mid:-1.6875 right:-1.625
      f(xMid):0.139892578125 error:0.0625
  New: left:-1.75 mid:-1.71875 right:-1.6875
      f(xMid):-0.044158935546875 error:0.03125
  New: left:-1.71875 mid:-1.703125 right:-1.6875
      f(xMid):0.048625946044921875 error:0.015625
  New: left:-1.71875 mid:-1.7109375 right:-1.703125
      f(xMid):0.0024247169494628906 error:0.0078125
  Approximate root is -1.7109375
  Program terminating normally
  

  as the output from your program. This is the output from my program. the "original" line is printed
• NOTE THAT MOST OF THE COMPLICATION in this program is simply getting the left, right, midpoint, functional value, and error approximation synchronized properly. In my program, the first two lines of output come from the main class. The "Original" line in the output is printed before entering the loop. the "New" lines are printed from inside the loop, and the "Approximate root" line is printed after the loop finishes and before returning a value for the root to the main class. Notice that the last value printed as the "new" midpoint is the value returned as the approximate root. This means that I have printed my "new" output lines at the bottom of the loop and not the top of the loop, and it's why the "original" line has to be done before the loop. That is, my code reads

  print "original values"
  while ()
  {
    recompute midpoint and endpoints
    print "new values"
  }
  print "approximate" (which is the same as the last "new")
  

  This seems to me to be a little more sensible than the alternative, which would be

  while ()
  {
    print "current values"
    recompute midpoint and endpoints
  }
  print "approximate" (which is the new midpoint and
         has not yet been printed out)
  

• You will need to use the Math.abs() function; look this up on the web.
• TURN IN your program with a cubic polynomial method hard-coded as

    private double f(double x)
    {
      double returnValue;
      returnValue = x*x*x + 7.0*x*x - 9.0*x + 1.0;
      return returnValue;
    }
  

  My suggestion is that you leave in both lines for evaluation of the function and just comment out the line you don't need. The root for this function is a little smaller than -8.0 so if you bracket the approximate root with -10.0 and 10.0 then the program will run just fine.