Question

The equation f(x) = (1 ‐ x) cos x ‐ sin x = 0 has at least one root between a = 0 and b = 1 since f(a)f(b) < 0. The bisection method of finding the root proceeds as follows: a. It finds the midpoint r = (a + b)/2. b. If f(r) = 0, then r is the root. If |b ‐ a| is very small less than ∈ then also we can take r as the root. In either of the cases, our job is done. c. If f(r) ≠ 0 and f(a)f(r) < 0, then the root lies between a and r. We assign r to b and go to step a. d. If f(r) ≠ 0 and f(b)f(r) < 0, then the root lies between r and b. We assign r to a and go to step a. e. If the number of iterations is high, we may stop the process with appropriate message. Write the following functions with the specifications mentioned. 1. Function func takes a real number x as argument and returns the value of f(x). 2. Function cbracket takes two real numbers a and b as arguments and returns 1 if at least one real root of f(x) lies between a and b, and 0 otherwise. 3. Function rootb that takes three real numbers a, b,∈ and an integer Nmax as arguments. This function returns the root of f(x) using bisection method. If the number of iterations is more than Nmax then the function terminates with appropriate message. Write a C program using the above functions. This program accepts a; b and Nmax from the user and prints out the root (if any).

Sample output:

Enter eps and Nmax :1.e‐6 20

Enter a, b :0 3

Root must be bracketed

Enter eps and Nmax :1.e‐6 10

Enter a, b :0 2

Increase the max iteration

Enter eps and Nmax :1.e‐6 50

Enter a, b :0 2

Root = 0.479731

Answer 1

This is quite easy. If you just follow the definition of the four steps given above then you'll realise that coding is not that difficult indeed. Just turn down the statements(rules) into equivalent C++ statements.

Here is a working program written in C which has all the functions as asked in the problem statement.

NOTE:

• The code includes various comments to ease understanding and readability. Feel free to ask any doubts in the comments.
• You can also print the state variables and see what's going on by printing current values of r, a and b.

#include<stdio.h>
#include<math.h>   //for invoking cos and sin functions from library

double func(double x){
   /*
   returns f(x) = (1-x)cos(x) - sin(x)
   */
  
   double ans = (1 - x) * cos(x) - sin(x);   //just plug in the required formula!
   return ans;
}

int cbracket(double a, double b){
   /*
   checks whether f(a)f(b) < 0 or not.
   if true, then a root exists between a and b otherwise false.
   returns 1 in the first case and 0 in the latter.
   */
  
   double f_a = func(a);   //calculate f(a)
   double f_b = func(b);   //calculate f(b)
   if(f_a * f_b < 0)
       return 1;
   else
       return 0;
}

double rootb(double a, double b, double epsilon, int nmax){
   /*
   returns -1 if number of iterations required exceeds nmax.
   returns the root found by bisection method otherwise.
   simply follow the four rules given in the problem definition.
   */
  
   if(func(a) == 0)   //sanity checks so that f(a)f(b) < 0 doesn't fail
       return a;
   else if (func(b) == 0)   //sanity checks so that f(a)f(b) < 0 doesn't fail
       return b;
   else{
       int iterations = 0;   //variable to keep track of the number of divisions of intervals(iterations)
       int flag = 0;   /*this will be set to 1, once either a root r is found(f(r) = 0) or the difference between left and right endpoints is less than eps.*/
       double current_left = a;   //current left end point of the interval to check root in
       double current_right = b;   //current right end point of the interval to check root in
       double current_r = 0;   /*our current best estimate of r(mid-point of current_left and current_right)*/
       while(!flag && iterations <= nmax){   /*we will iterate till either we run out of iterations or a root is found*/
           current_r = (current_left + current_right)/2.0;   //bisect interval now
           iterations += 1;   //increment count for iterations done so far
           double val = func(current_r);
           double diff = current_right - current_left;
           if(val == 0)   //check if root is found or not
               flag = 1;
           else if(diff <= epsilon)   //check if difference between end points falls under eps
               flag = 1;
           else{
               int f1 = cbracket(current_left, current_r);   //check whether f(a)f(r) < 0
               int f2 = cbracket(current_r, current_right);   //check whether f(r)f(b) < 0
               if(f1 == 1)
                   current_right = current_r;   //we'll now search in (a, r)
               else
                   current_left = current_r;   //we'll now search in (r, b)
           }
       }
       if(iterations > nmax)
           return -1;
       else
           return current_r;
   }
}

int main(){
   double a, b, eps;
   int nmax;
   printf("%s", "Enter eps and Nmax :");
   scanf("%lf %d", &eps, &nmax);
   printf("%s", "Enter a, b :");
   scanf("%lf %lf", &a, &b);
   if(a > b){   //ensure that a is always lesser than b. swap a and b otherwise
       double temp = a;
       a = b;
       b = temp;
   }
   if(cbracket(a, b) == 0)
       printf("Root must be bracketed\n");
   else{
       double val = rootb(a, b, eps, nmax);
       if(val == -1)
           printf("Increase the max iteration\n");
       else
           printf("Root = %lf\n", val);
   }
   return 0;
}