8 replies to this topic

[Yuriy M]

Hi guys. :)

I need a second opinion on a bisection program that involves a stipulation that if the user enters an interval longer than one unit, the program will check the one-unit segments of the interval until a subinterval is found with different signs for the values of the function (in this case, function g). The program should then use the bisection method with the subinterval and the function.

Here is what I have:

#include <stdio.h>
#include <math.h>

double bisect(double x_left, double x_right, double epsilon, double f(double farg), int *errp);

double g(double x);

int main(void)
{
    double x_left, x_right, /* left, right endpoints of interval */
           epsilon,         /* error tolerance */
           root;
    int    error;
    
    /* Get endpoints and error tolerance from user */
    printf("\nEnter interval endpoints> ");
    scanf("%lf%lf", &x_left, &x_right);
    printf("\nEnter tolerance> ");
    scanf("%lf", &epsilon);
    
    /* Check if interval is greater than one unit */
   
    if (x_left - x_right > 1.0 || x_left - x_right > -1.0)
    {
     while (x_left != x_right)
     {
      printf("\nNew segmented interval is [%.7f, %.7f]", x_left, x_right);
     
      if (x_left > x_right)
      {
       x_left = x_left - 1.0;
       x_right = x_right + 1.0;
       
       if (x_right - x_left <= 1.0 || x_right - x_left <= -1.0)
        break;
      }
      else
      {
       x_left = x_left + 1.0;    
       x_right = x_right - 1.0;
       
       if (x_right - x_left <= 1.0 ||  x_right - x_left <= -1.0)
        break;
      }
     }
    }
    else if (x_right - x_left > 1.0 || x_right - x_left > -1.0)
    {
     while (x_left != x_right)
     {
      printf("\nNew segmented interval is [%.7f, %.7f]", x_left, x_right);
     
      if (x_right > x_left)
      {
       x_right = x_right - 1.0;
       x_left = x_left + 1.0;
       
       if (x_right - x_left <= 1.0 ||x_right - x_left <= -1.0)
        break;
      }
      else
      {
       x_right = x_right + 1.0;    
       x_left = x_left - 1.0;
       
       if (x_right - x_left <= 1.0 || x_right - x_left <= -1.0)
        break;
      }
     }
    }
   
    /* Use bisect function to look for root of g */
    printf("\n\nFunction g");
    root = bisect(x_left, x_right, epsilon, g, &error);
    if (!error)
     printf("\n   g(%.7f) = %e\n", root, g(root));   
     
    return 0;
}

/* Implements the bisection method for finding a root of a function f.  Finds a root (and sets output parameter error flag to 0)
   if signs of fp(x_left) and fp(x_right) are different.  Otherwise sets output parameter error flag to 1.
*/

double bisect(double x_left,              /* input - endpoints of interval in */
              double x_right,             /*         which to look for a root */
              double epsilon,             /* input - error tolerance */
              double f(double farg),      /* input - the function */
              int *errp)                  /* output - error flag */
{
       double x_mid,                      /* midpoint of interval */
              f_left,                     /* f(x_left)            */
              f_mid,                      /* f(x_mid)             */
              f_right;                    /* f(x_right)           */
       int    root_found = 0;
       
       /* Computes function values at initial endpoints of interval */
       f_left = f(x_left);
       f_right = f(x_right);
       
       /* If no change of sign occurs on the interval there is not a unique root.  Searches for the unique root if there is one. */
       
       if (f_left * f_right > 0)  /* same sign */
       {
        *errp = 1;
        printf("\nMay be no root in [%.7f, %.7f]", x_left, x_right);
       }
       else
       {
        *errp = 0;
        
        /* Searches as long as interval size is large enough and no root has been found */
        while (fabs(x_right - x_left) > epsilon && !root_found)
        {
         /* Computes midpoint and function value at midpoint */
         x_mid = (x_left + x_right) / 2.0;
         f_mid = f(x_mid);
         
         if (f_mid == 0.0) /* Here's the root */
          root_found = 1;
         else if (f_left * f_mid < 0.0) /* Root in [x_left, x_mid] */
          x_right = x_mid;
         else /* Root in [x_mid, x_right] */
         {
          x_left = x_mid;
          f_left = f_mid;
         }
         
         /* Prints root and interval or new interval */
         if (root_found)
          printf("\nRoot found at x = %.7f, midpoint of [%.7f, %.7f]", x_mid, x_left, x_right);
         else
          printf("\nNew interval is [%.7f, %.7f]", x_left, x_right);
        }
       }
       
       /* If there is a root, it is the midpoint of [x_left, x_right] */
       return ((x_left + x_right) / 2.0);
}

/* Functions for which roots are sought */

/* 3     2     5x - 2x + 3 */
double g(double x)
{
    return (5 * pow(x, 3.0) - 2 * pow(x, 2.0) + 3);
}

I've put together a piece of code in main that checks each endpoint by 1.0 until they are at or less than interval of 1. Afterwards, the bisection function is called. I appear to be having no luck though as the function always comes out with no result. What could I be doing wrong? :confused:

[WingedPanther]

What inputs are you using? Also, this statement is wrong:

if (x_left - x_right > 1.0 || x_left - x_right > -1.0)

should be

(x_left - x_right > 1.0 || x_left - x_right < -1.0)

[Yuriy M]

I'm using inputs like:

x_left = -1.0
x_right = 3.0

or

x_left = -4.5
x_right = 6.2

and the program would display such values like [-1.0000000, 3.0000000] followed up by [0.0000000], 2.0000000] or [-4.5000000, 6.2000000] followed up by [-3.5000000, 5.2000000]. The program would stop bringing the endpoints together when they come within an interval of 1.0 and then call function g to help calculate the root through bisection. For some reason, the function cannot seem to determine the root when I do it by this method. However, when I remove the block of code that calculates the endpoints by 1.0, the function works as intended. I'm not sure why it works when the block of code is removed and not when the block of code is established. There doesn't appear to be anything within the block of code that I see that would cause the endpoints to be disregarded in the bisection method. What could I be missing? :confused:

P.S. Here is a more simplified version of the code block:

#include <stdio.h>
#include <math.h>

double bisect(double x_left, double x_right, double epsilon, double f(double farg), int *errp);

double g(double x);

int main(void)
{
    double x_left, x_right, /* left, right endpoints of interval */
           epsilon,         /* error tolerance */
           root;
    int    error;
    
    /* Get endpoints and error tolerance from user */
    printf("\nEnter interval endpoints> ");
    scanf("%lf%lf", &x_left, &x_right);
    printf("\nEnter tolerance> ");
    scanf("%lf", &epsilon);
    
    /* Check if interval is greater than one unit */
   
    if (x_left - x_right > 1.0 || x_right - x_left > 1.0 || x_left - x_right < -1.0 || x_right - x_left < -1.0)
    {
     if (x_left >= 0.0 && x_right <= 0.0)
     {
      while (x_left >= 0.0 && x_right <= 0.0)
      {
       if (x_left < 0.0 && x_right > 0.0)
        break;
       else
       {
        x_left = x_left - 1.0;          
        x_right = x_right + 1.0;
        printf("\nNew interval is [%.7f, %.7f]", x_left, x_right);
       }
      }
     }
     else if (x_left <= 0.0 && x_right >= 0.0)
     {
      while (x_left <= 0.0 && x_right >= 0.0)
      {
       if (x_left > 0.0 && x_right < 0.0)
        break;
       else
       {
        x_left = x_left + 1.0;
        x_right = x_right - 1.0;
        printf("\nNew interval is [%.7f, %.7f]", x_left, x_right);
       }
      }
     }
    }
     
    /* Use bisect function to look for root of g */
    printf("\n\nFunction g");
    root = bisect(x_left, x_right, epsilon, g, &error);
    if (!error)
     printf("\n   g(%.7f) = %e\n", root, g(root));   
     
    return 0;
}

/* Implements the bisection method for finding a root of a function f.  Finds a root (and sets output parameter error flag to 0)
   if signs of fp(x_left) and fp(x_right) are different.  Otherwise sets output parameter error flag to 1.
*/

double bisect(double x_left,              /* input - endpoints of interval in */
              double x_right,             /*         which to look for a root */
              double epsilon,             /* input - error tolerance */
              double f(double farg),      /* input - the function */
              int *errp)                  /* output - error flag */
{
       double x_mid,                      /* midpoint of interval */
              f_left,                     /* f(x_left)            */
              f_mid,                      /* f(x_mid)             */
              f_right;                    /* f(x_right)           */
       int    root_found = 0;
       
       /* Computes function values at initial endpoints of interval */
       f_left = f(x_left);
       f_right = f(x_right);
       
       /* If no change of sign occurs on the interval there is not a unique root.  Searches for the unique root if there is one. */
       
       if (f_left * f_right > 0)  /* same sign */
       {
        *errp = 1;
        printf("\nMay be no root in [%.7f, %.7f]", x_left, x_right);
       }
       else
       {
        *errp = 0;
        
        /* Searches as long as interval size is large enough and no root has been found */
        while (fabs(x_right - x_left) > epsilon && !root_found)
        {
         /* Computes midpoint and function value at midpoint */
         x_mid = (x_left + x_right) / 2.0;
         f_mid = f(x_mid);
         
         if (f_mid == 0.0) /* Here's the root */
          root_found = 1;
         else if (f_left * f_mid < 0.0) /* Root in [x_left, x_mid] */
          x_right = x_mid;
         else /* Root in [x_mid, x_right] */
         {
          x_left = x_mid;
          f_left = f_mid;
         }
         
         /* Prints root and interval or new interval */
         if (root_found)
          printf("\nRoot found at x = %.7f, midpoint of [%.7f, %.7f]", x_mid, x_left, x_right);
         else
          printf("\nNew interval is [%.7f, %.7f]", x_left, x_right);
        }
       }
       
       /* If there is a root, it is the midpoint of [x_left, x_right] */
       return ((x_left + x_right) / 2.0);
}

/* Functions for which roots are sought */

/* 3     2     5x - 2x + 3 */
double g(double x)
{
    return (5 * pow(x, 3.0) - 2 * pow(x, 2.0) + 3);
}

Edited by Yuriy M, 02 December 2011 - 07:13 PM.

[WingedPanther]

Notes:
Your first if statement doesn't need the comparisons to -1. You covered it with the two directions compared to 1.
The root is actually located at approximately -0.729. When I enter -1,3, it immediately drops the range to 0 to 2, which excludes the root! You can't just reduce the range to the center, or you potentially chop out the root. My guess is your comparisons should be based on g(x_left) and g(x_right), not x_left and x_right.

[Yuriy M]

Is this more like it?

#include <stdio.h>
#include <math.h>

double bisect(double x_left, double x_right, double epsilon, double f(double farg), int *errp);

double g(double x);

int main(void)
{
    double x_left, x_right, /* left, right endpoints of interval */
           epsilon,         /* error tolerance */
           root;
    int    error;
    
    /* Get endpoints and error tolerance from user */
    printf("\nEnter interval endpoints> ");
    scanf("%lf%lf", &x_left, &x_right);
    printf("\nEnter tolerance> ");
    scanf("%lf", &epsilon);
    printf("\nStarting interval is [%.7f, %.7f]", x_left, x_right);
    
    /* Check if interval is greater than one unit */
    
    if (x_left - x_right > 1.0 || x_right - x_left > 1.0)
    {
     x_left = g(x_left);
     x_right = g(x_right);
     
     while (x_left >= 0.0 && x_right <= 0.0)
     {
      if (x_left >= 0.0 && x_right <= 0.0)
       break;
      else
      {
       x_left = x_left + 1.0;
       x_right = x_right - 1.0;
      }
     }
     while (x_right <= 0.0 && x_left >= 0.0)
     {
      if (x_right <= 0.0 && x_left >= 0.0)
       break;        
      else
      {
       x_left = x_left - 1.0;
       x_right = x_right + 1.0;
      }
     }
    }
    
    /* Use bisect function to look for root of g */
    printf("\n\nFunction g");
    root = bisect(x_left, x_right, epsilon, g, &error);
    if (!error)
     printf("\n   g(%.7f) = %e\n", root, g(root));   
     
    return 0;
}

/* Implements the bisection method for finding a root of a function f.  Finds a root (and sets output parameter error flag to 0)
   if signs of fp(x_left) and fp(x_right) are different.  Otherwise sets output parameter error flag to 1.
*/

double bisect(double x_left,              /* input - endpoints of interval in */
              double x_right,             /*         which to look for a root */
              double epsilon,             /* input - error tolerance */
              double f(double farg),      /* input - the function */
              int *errp)                  /* output - error flag */
{
       double x_mid,                      /* midpoint of interval */
              f_left,                     /* f(x_left)            */
              f_mid,                      /* f(x_mid)             */
              f_right;                    /* f(x_right)           */
       int    root_found = 0;
       
       /* Computes function values at initial endpoints of interval */
       f_left = f(x_left);
       f_right = f(x_right);
       
       /* If no change of sign occurs on the interval there is not a unique root.  Searches for the unique root if there is one. */
       
       if (f_left * f_right > 0)  /* same sign */
       {
        *errp = 1;
        printf("\nMay be no root in [%.7f, %.7f]", x_left, x_right);
       }
       else
       {
        *errp = 0;
        
        /* Searches as long as interval size is large enough and no root has been found */
        while (fabs(x_right - x_left) > epsilon && !root_found)
        {
         /* Computes midpoint and function value at midpoint */
         x_mid = (x_left + x_right) / 2.0;
         f_mid = f(x_mid);
         
         if (f_mid == 0.0) /* Here's the root */
          root_found = 1;
         else if (f_left * f_mid < 0.0) /* Root in [x_left, x_mid] */
          x_right = x_mid;
         else /* Root in [x_mid, x_right] */
         {
          x_left = x_mid;
          f_left = f_mid;
         }
         
         /* Prints root and interval or new interval */
         if (root_found)
          printf("\nRoot found at x = %.7f, midpoint of [%.7f, %.7f]", x_mid, x_left, x_right);
         else
          printf("\nNew interval is [%.7f, %.7f]", x_left, x_right);
        }
       }
       
       /* If there is a root, it is the midpoint of [x_left, x_right] */
       return ((x_left + x_right) / 2.0);
}

/* Functions for which roots are sought */

/* 3     2     5x - 2x + 3 */
double g(double x)
{
    return (5 * pow(x, 3.0) - 2 * pow(x, 2.0) + 3);
}

Test runs of the program are now indicating roots or approximate roots. However, I still feel the need for a second opinion. :worry:

[WingedPanther]

no no no no no. You don't want to confuse the x values with the g(x) values.

Here's a good rule of thumb: use new variables, so y_left = g(x_left), and y_right = g(x_right). Do some hand tracing on your code to get a better sense of what's happening, so you can see the problems.

[Yuriy M]

Okay! Updates:

• Created two new variables x_left_end and x_right_end to serve as border values for the interval.
  
• Created two new variables y_left and y_right to store the function processed values of each segmented endpoint. The variables are then checked for opposing sign values. If the values contain sign values that are opposite to one another, the bisect function is called and bisection is executed. Otherwise, the interval segment is moved by 1.0 for both endpoint values provided that they remain within the borders of x_left_end and x_right_end.

And the code:

#include <stdio.h>
#include <math.h>

double bisect(double x_left, double x_right, double epsilon, double f(double farg), int *errp);

double g(double x);

int main(void)
{
    double x_left, x_right, /* left, right endpoints of interval */
           x_left_end, x_right_end,
           y_left, y_right,
           epsilon,         /* error tolerance */
           root;
    int    error;
    
    /* Get endpoints and error tolerance from user */
    printf("\nEnter interval endpoints> ");
    scanf("%lf%lf", &x_left, &x_right);
    printf("\nEnter tolerance> ");
    scanf("%lf", &epsilon);
    printf("\nStarting interval is [%.7f, %.7f]", x_left, x_right);
    
    x_left_end = x_left;
    x_right_end = x_right;
    
    /* Check if interval is greater than one unit */
  
    if (fabs(x_left - x_right) > 1.0 || fabs(x_right - x_left) > 1.0)
    {
     if (x_right > x_left)
     {
      for (x_left_end; x_left_end < x_right_end; x_left_end++)
      {
       y_left = g(x_left_end);
       y_right = g(x_right);
      
       if ((y_left < 0.0 && y_right > 0.0) || (y_left > 0.0 && y_right < 0.0))
       {
        printf("\n\nFunction g with x");
        root = bisect(x_left_end, x_right, epsilon, g, &error);
        if (!error)
         printf("\n   g(%.7f) = %e\n", root, g(root));  
        break;   
       }
       x_right = x_left_end + 1.0;
       printf("\nNew segment is [%.7f, %.7f]", x_left_end, x_right);
      }
      if (x_left_end >= x_right_end)
       printf("\nNo root found.\n");
     }
     else if (x_left > x_right)
     {
      for (x_left_end; x_left_end > x_right_end; x_left_end--)
      {
       y_left = g(x_left_end);
       y_right = g(x_right);
      
       if ((y_left < 0.0 && y_right > 0.0) || (y_left > 0.0 && y_right < 0.0))
       {
        printf("\n\nFunction g with y");
        root = bisect(x_left_end, x_right, epsilon, g, &error);
        if (!error)
         printf("\n   g(%.7f) = %e\n", root, g(root));  
        break;  
       }
       x_right = x_left_end - 1.0;
       printf("\nNew segment is [%.7f, %.7f]", x_left_end, x_right);
      }
      if (x_left_end <= x_right_end)
       printf("\nNo root found.\n");    
     }
    }
    else
    {
     /* Use bisect function to look for root of g */
     printf("\n\nFunction g");
     root = bisect(x_left, x_right, epsilon, g, &error);
     if (!error)
      printf("\n   g(%.7f) = %e\n", root, g(root));   
    }
}

/* Implements the bisection method for finding a root of a function f.  Finds a root (and sets output parameter error flag to 0)
   if signs of fp(x_left) and fp(x_right) are different.  Otherwise sets output parameter error flag to 1.
*/

double bisect(double x_left,              /* input - endpoints of interval in */
              double x_right,             /*         which to look for a root */
              double epsilon,             /* input - error tolerance */
              double f(double farg),      /* input - the function */
              int *errp)                  /* output - error flag */
{
       double x_mid,                      /* midpoint of interval */
              f_left,                     /* f(x_left)            */
              f_mid,                      /* f(x_mid)             */
              f_right;                    /* f(x_right)           */
       int    root_found = 0;
       
       /* Computes function values at initial endpoints of interval */
       f_left = f(x_left);
       f_right = f(x_right);
       
       /* If no change of sign occurs on the interval there is not a unique root.  Searches for the unique root if there is one. */
       
       if (f_left * f_right > 0)  /* same sign */
       {
        *errp = 1;
        printf("\nMay be no root in [%.7f, %.7f]", x_left, x_right);
       }
       else
       {
        *errp = 0;
        
        /* Searches as long as interval size is large enough and no root has been found */
        while (fabs(x_right - x_left) > epsilon && !root_found)
        {
         /* Computes midpoint and function value at midpoint */
         x_mid = (x_left + x_right) / 2.0;
         f_mid = f(x_mid);
         
         if (f_mid == 0.0) /* Here's the root */
          root_found = 1;
         else if (f_left * f_mid < 0.0) /* Root in [x_left, x_mid] */
          x_right = x_mid;
         else /* Root in [x_mid, x_right] */
         {
          x_left = x_mid;
          f_left = f_mid;
         }
         
         /* Prints root and interval or new interval */
         if (root_found)
          printf("\nRoot found at x = %.7f, midpoint of [%.7f, %.7f]", x_mid, x_left, x_right);
         else
          printf("\nNew interval is [%.7f, %.7f]", x_left, x_right);
        }
       }
       
       /* If there is a root, it is the midpoint of [x_left, x_right] */
       return ((x_left + x_right) / 2.0);
}

/* Functions for which roots are sought */

/* 3     2     5x - 2x + 3 */
double g(double x)
{
    return (5 * pow(x, 3.0) - 2 * pow(x, 2.0) + 3);
}

I've also done some hand tracing to verify that the calculations are performing to program specifications. Things should be okay now.

[WingedPanther]

Good to hear it.

I love tracing code to be sure it does what I intended. Extra outputs are great for that.

[Yuriy M]

Thanks. :)

Here are the original requirements of the program that led to the coding:

textbook said:

Create a bisection program where if the user enters an interval longer than one unit, the program checks one-unit segments of the interval until a subinterval is found with different signs for the values of function g(x) = 5x^3 - 2x^2 + 3. The program should then call a function bisect that performs the bisection operation with this subinterval and function g(x).

Hope it lived up to the program's expectations. The tracing and calculations seemed fine.