Need an explanation for bisection method

[callister]

Guys..Can anyone help me to explain what really happened in the while loop and both of the if else loop that makes this coding can find the root using bisection method.Thank you...

#include "stdafx.h"
#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;

double f( double);

int main ( int argc, char *argv[])
{
int kmax;
double a,b,eps;
cout <<" Input a,b, eps, kmax\n ";
cin>> a >> b >> eps >> kmax;//use big kmax , eps 0.5e-6
cout << " The input data are\n";
cout << "a= "<< a << "b= "<< b;
cout << "eps= "<< eps << "kmax= "<< kmax<< endl;
cout<< " The results are\n";
cout<< "k      a	b	x        f(x)\n";

int k=1;

double x=0.5*(a+b );//first bisection

    while (( k<=kmax) && (fabs(f(x))>eps))  // <-- this has changed
        {
                cout << setw(2)<< k << setprecision(5)<< fixed<< setw(8)<< a<< setw(8)<< b << setprecision(6) <<setw(10)<<x<< setw(12)<<f(x) << endl;
              if (f(x) <0)
                a=x;
                else
                b=x;
                x= 0.5*(a+b);

                k++;
        }
        if ( (k>kmax) || ( fabs(f(x)) > eps ) )
                cout << "no convergence";
        else
                cout << " \nThe root = "<< x<< endl;

return 0;
}
double f(double x){
  return (tan(x)-x);
  }

[WaltP]

See This

[callister]

I know how bisection method works..It just that I don't know how that loop can make it work..

[StuXYZ]

I know how bisection method works..It just that I don't know how that loop can make it work..

Well the real problem is that the loop does not work. Or more accurately only works for the specific instance when f(a) <0 and f(b) >0 and there is only one root between a and b.

To actually understand what is going on you are going to HAVE to go through it with a piece of paper.
(i) Draw the graph of tan(x)-x
(ii) Observe that it has multiple roots - near [TEX]\pm\pi/2 + n\pi[/TEX].
(iii) Observer the discontinuity at exactly [TEX]\pm\pi/2 + n\pi[/TEX].
(iv) Observe that for +ve x the discontinuity is on the right of the root and for -ve x it is on the left.
(v) Obsever that there is a root at x=0.

So in all tan(x)-x is an awful function to test first, use a polynominal, until you understand the method. [which doesn't have a root at x=0 since that always leads to lots of programming errors.]

Next: take the graph of your function and mark the variables a,b and x, on the x-axis. Just take three different pens/pencils and put them vertically on the correct x-axis point.

Step through the code adjusting the pens as the variables change.

In short bisection is the same as the childrens game, guess a number, were you are told higher and lower, you remember a, and b as the highest value that got a lower-call, and lowest value that got a higher-call. x is your next guess.

[callister]

So, the loop that I'm using is incorrect? But the program works perfectly...huhu...

[StuXYZ]

So, the loop that I'm using is incorrect? But the program works perfectly...huhu...

No the program doesn't work ALWAYS:

Enter a=4.4 b=5.5 and then why does this not find the root at
4.493409 ?

Or -4 and 0.5 does not find the root at 0.

That is the problem with the loop, it fails as it skips over the singularities. This can be corrected .

The errors that exist are :
(a) If f(a) >0 and f(b)< 0 then it fails
(b) If f(x) within the range a -> b has a singularity it CAN fail [but not always].

Otherwise the program is kind of ok. It makes too many calls to f(x)
[cache the value and then use it in the fabs test.]

The algorithm is best tried with pen and paper and a graph.
use gnuplot and type plot tan(x)-x and you will see the mess that this function is.