Solve Bisection Problem in C++: Find the Root

  • C/C++
  • Thread starter ggeo1
  • Start date
  • Tags
    C++
In summary, the code is trying to find the root of a function using bisection, but keeps getting errors. I found the solution with the help of a math software program, and it was x=-3.18306.
  • #1
ggeo1
63
0
Hello,

I wrote a code for my problem but i can't find the mistake.It doesn't give me the right answer.
We must find the root using bisection method.
I found with mathematica that the solution is x= -3.18306.

The function values are x (-4,-3).

Any help is welcome!

Code:
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstdlib>


using namespace std;

double function(double); // declare of function

int main()
{


    double x1,x2,x3,error;
    double eps=pow(10,-6); //my error tolerance

    cout << "Give x1 : "<<endl;
    cin >>x1;
    cout << "Give x2 : "<<endl;
    cin >>x2;

    error = abs((x1-x2)/x1); //compute relative error

     int i=1;

     while ((error > eps)  || (function(x3))!=0) // execute the loop as far as these conditions exist

     {

        x3=(x1+x2)/2.0; // midpoint

        if ((function(x3))*(function(x1)) <0) //condition for bisection method

        x2=x3;

        else

        x1=x3;

        i++;

cout << " The function(root) is : " << function(x3) << "\t and the root is : " << x3<<endl;

     }


   return 0;
}

    double function(double x) // my function

    {
        double y;
        y =exp(x)-sin((3.14159265*x)/180.0);
        return y;
    }
 
Technology news on Phys.org
  • #2
You are never changing error.
 
  • #3
In your function definition you treat x as if it were radians in exp(x) but as if it were degrees in the sin argument.

Make up your mind, is x degrees or radians?
 
  • #4
In your function definition you treat x as if it were radians in exp(x) but as if it were degrees in the sin argument.

Make up your mind, is x degrees or radians?

Ok i changed that.

You are never changing error.

Thanks!It works fine now.
But i can't stop the loop.Is there any way to stop without using for?

EDIT :: If i use continue ,it stops but it doesn't give the result.

Code:
if ((function(x3))*(function(x1)) <0)
        {//condition for bisection method

        x2=x3;

        continue;

        }


        else {

        x1=x3;
        }

        cout << " The function(root) is : " << function(x3) << "\t and the root is : " << x3<<endl;
 
Last edited:
  • #5
Hint - think about your condition:

Code:
while ((error > eps)  || (function(x3))!=0)
 
  • #6
while ((error > eps) || (function(x3))!=0)

I think its right.I want the loop to continue until error<eps or function(x3)=0
 
  • #7
So when are you updating the variable 'error'?
 
  • #8
The error depends on x1 and x2 ,so because these are constants (the user gives them once) ,the error will be constant.So,it doesn't matter if the error is in the while loop or not.

Something am i missing here?
 
  • #9
ggeo1 said:
Something am i missing here?

Yes, x3.
 
  • #10
What do you mean?

x3 must be in the while loop.
 
  • #11
And it is, check the first post.
 
  • #12
Ok , i am a bit confused now.
If i got it well , error must be the half in every iteration.
So , i wrote this code now,but it still doesn't stop the loop and it doesn't give the right results.
It works only for some values

Code:
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstdlib>


using namespace std;

double function(double); // declare of function

int main()
{


    double x1,x2,x3,error;
    double eps=pow(10,-6); //my error tolerance

    cout << "Give x1 , x(-4,-3) : "<<endl;
    cin >>x1;
    cout << "Give x2 , x(-4,-3) : "<<endl;
    cin >>x2;




    int i=0;
    double errorx=error;

    while ((errorx > eps)  || (function(x3))!=0) // execute the loop as far as these conditions exist

     {

        error = abs((x1-x2)/x1);//compute relative error

        errorx=(1.0/2.0)*errorx; //in every step error must be the half

        x3=(x1+x2)/2.0; // midpoint


        if ((function(x3))*(function(x1)) <0) {  //condition for bisection method

        x2=x3;

              }

        else {

        x1=x3;
        }


        i++;


cout << " The function(root) is : " << function(x3) << "\t and the root is : " << x3<<endl;

     }
     cout << "The number of iterations was : "<<i <<endl;


   return 0;
}

    double function(double x) // my function

    {
        double y;
        y =exp(x)-sin(x);
        return y;
    }
 
  • #13
You never initialize errorx. I guess you think it is width of the x1..x2 interval, but it is not.

Don't you know how to use debugger, to trace values of the variables during execution? If you don't have debugger, you can always cout << variable somewhere in your code to trace how its value changes.
 
  • #14
One thing that hasn't been pointed out is that your loop continues if errorx > eps or function(x3) != 0. Looking at the 2nd condition, it is ineffective to use logic that tests whether a floating point number is equal to 0. Instead of testing whether a float or double equals zero, test to see if it is "close enough" to zero, say within .0000001 or other appropriate tolerance.
 
  • #15
I was aiming at that too. Chances that function() will return exactly zero are negligible.
 
  • #16
ggeo1 said:
double eps=pow(10,-6);
Word of advice: Don't use pow() unless there is no escaping the use of it. That use is completely unwarranted here. Using double eps=1e-6; is much preferable in this case.


double errorx=error;
Why have you introduced another variable here? What is the point of doing so? You have not computed error yet, so this statement does not do what you think it does. Learn to use your debugger.


while ((errorx > eps) || (function(x3))!=0)
Why are you using logical or? This loop will terminate when errorx is less than or equal to eps and function(x3) is identically equal to zero. In other words, you have pretty much guaranteed an infinite loop.

error = abs((x1-x2)/x1);
errorx=(1.0/2.0)*errorx;
Once again, why two variables?
 
  • #17
Hello,

First of all thank you all for your answers.
One problem was the function(x3)!=0 , so i changed it to function(x3)>0.001
The loop stops now , but it doesn't give me the right answer always.

Why are you using logical or? This loop will terminate when errorx is less than or equal to eps and function(x3) is identically equal to zero. In other words, you have pretty much guaranteed an infinite loop.

Is there a way not to use logical or?

Here is my new code now.( errorx was a mistake.it didn't made sense,so i removed it)

Code:
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstdlib>


using namespace std;

double function(double); // declare of function

int main()
{


    double x1,x2,x3,error;
    double eps=1e-6; //my error tolerance

    cout << "Give x1 , x(-4,-3) : "<<endl;
    cin >>x1;
    cout << "Give x2 , x(-4,-3) : "<<endl;
    cin >>x2;





    int i=0;

    while ((error > eps)  || (function(x3))>=0.001) // execute the loop as far as these conditions exist

     {

        error = abs((x1-x2)/x1);//compute relative error
        x3=(x1+x2)/2.0; // midpoint


        if ((function(x3))*(function(x1)) <0) {  //condition for bisection method

        x2=x3;

              }

        else {

        x1=x3;
        }


        i++;


cout << " The function(root) is : " << function(x3) << "\t and the root is : " << x3<<endl;

     }
     cout << "The number of iterations was : "<<i <<endl;


   return 0;
}

    double function(double x) // my function

    {
        double y;
        y =exp(x)-sin(x);
        return y;
    }
 
  • #18
Without going into the issue of whether the logical OR is needed, you're only checking function(x3) >= .001. If function(x3) is close to zero but negative, your condition won't catch that. For this condition it would be better to use fabs(function(x3) >= .001) to get the absolute value of function(x3).
 
  • #19
You were right.Now,the loop stops but again it doesn't give me always the right results!
I can't figure it!
 
  • #20
What are you entering for the initial values of x1 and x2? There is a solution at about -3.2. If your starting values don't bracket this value, you won't be able to use bisection to get a solution.
 
  • #21
My values must be in the area (-4,-3).
If i enter x1=-4 and x2=-3 ,it gives me the right result , -3.18306 (although it isn't the last iteration.the last 3 iterations have this value)

Give x1 , x(-4,-3) :
-4
Give x2 , x(-4,-3) :
-3
The function(root) is : -0.320586 and the root is : -3.5
The function(root) is : -0.0694209 and the root is : -3.25
The function(root) is : 0.0605288 and the root is : -3.125
The function(root) is : -0.00461629 and the root is : -3.1875
The function(root) is : 0.0279283 and the root is : -3.15625
The function(root) is : 0.0116472 and the root is : -3.17188
The function(root) is : 0.00351302 and the root is : -3.17969
The function(root) is : -0.000552274 and the root is : -3.18359
The function(root) is : 0.00148022 and the root is : -3.18164
The function(root) is : 0.000463933 and the root is : -3.18262
The function(root) is : -4.41804e-05 and the root is : -3.18311
The function(root) is : 0.000209874 and the root is : -3.18286
The function(root) is : 8.2846e-05 and the root is : -3.18298
The function(root) is : 1.93326e-05 and the root is : -3.18304
The function(root) is : -1.2424e-05 and the root is : -3.18307
The function(root) is : 3.45432e-06 and the root is : -3.18306 here,it finds the value but it continues to search.How can i handle that?

The function(root) is : -4.48482e-06 and the root is : -3.18307
The function(root) is : -5.15249e-07 and the root is : -3.18306
The function(root) is : 1.46954e-06 and the root is : -3.18306
The function(root) is : 4.77143e-07 and the root is : -3.18306
The number of iterations was : 20


If i enter for example x1=-3.6 and x2=-3.2 ,it gives me as result -3.2 (the last two iterations have this value).
 
  • #22
Your while loop is controlled by two values, error and f(x3). I think it might make sense to have the loop controlled just by f(x3) so that when fabs(f(x3)) < .00001, say, the loop exits.

You could also have some other check inside the loop to prevent it from running forever, such as a check that the current value of x3 isn't too close to the previous value of x3. If the two values are too close, break out of the loop.
 
  • #23
Your while loop is controlled by two values, error and f(x3). I think it might make sense to have the loop controlled just by f(x3) so that when fabs(f(x3)) < .00001, say, the loop exits.

I must leave these two conditions.(its the excersice)
(But also if i leave error outside ,it doesn't work.)

You could also have some other check inside the loop to prevent it from running forever, such as a check that the current value of x3 isn't too close to the previous value of x3. If the two values are too close, break out of the loop.

I did this ,but i don't now if its right.(the result its still the same as before)

Code:
double newx3=0;
while ...


            newx3=newx3-x3;
       if (fabs(newx3-x3)<0.001)
         break;

         i++;
...
 
  • #24
Hello,
I didn't check this :
that the current value of x3 isn't too close to the previous value of x3. If the two values are too close, break out of the loop

but i think its ok!

The code is fine.The problem was that i chose regions (x1 and x2) that were both from the same side of the solution.

Thanks you all!

(now i have another problem with Newton-rapshon method ,so i am opening new thread)
 

1. What is the bisection method in C++?

The bisection method in C++ is a numerical algorithm used to find the root of a given function. It involves repeatedly dividing an interval in half and checking which sub-interval contains the root. This process is continued until the root is approximated within a desired accuracy.

2. How do I implement the bisection method in C++?

To implement the bisection method in C++, you will need to define your function, choose an initial interval, and specify the desired accuracy. Then, using a while loop, you can repeatedly divide the interval in half and check for the root within the sub-intervals. This process is continued until the root is found within the desired accuracy.

3. What is the time complexity of the bisection method in C++?

The time complexity of the bisection method in C++ is O(log(n)), where n is the number of iterations needed to approximate the root. This makes it a highly efficient algorithm for finding roots of functions.

4. Can the bisection method fail to find the root in C++?

Yes, the bisection method can fail to find the root in C++ if the initial interval does not contain the root or if the function is not continuous within the interval. In these cases, the algorithm will continue to iterate without converging to the root.

5. How do I know if the bisection method in C++ has found the root?

You can determine if the bisection method has found the root in C++ by checking if the function value at the midpoint of the current interval is close enough to zero, within the desired accuracy. If it is, then the midpoint is considered the root and the algorithm will terminate.

Similar threads

  • Programming and Computer Science
Replies
5
Views
2K
  • Programming and Computer Science
Replies
6
Views
8K
  • Programming and Computer Science
Replies
7
Views
1K
  • Programming and Computer Science
2
Replies
39
Views
3K
  • Programming and Computer Science
Replies
23
Views
2K
  • Programming and Computer Science
Replies
12
Views
1K
  • Programming and Computer Science
Replies
4
Views
2K
Replies
10
Views
904
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
  • Programming and Computer Science
Replies
6
Views
834
Back
Top