Hi everyone. This is my first post here at DW.

I was just experimenting with programs and thus I am trying to implement Bisection Method & False Position / Regula Falsi Method into a C++ program. Once I am done doing these two, ill start coding the Newton-Raphson Method.

All of the above mentioned methods are used in finding the root of a given polynomial, by the use of multiple iterations.

Now, ill first talk about the Bisection Method program. This program which i made may not be efficient / good, but it does its job in a crippled manner.

PROBLEMS in BISECTION METHOD :
1. Among the successful roots found out by the program of a polynomial are not accurate. (I did a counter check using a scientific calculator)
2. The program is not capable of finding the root of a polynomial even though a root exists.
3. For most of the polynomials, it hangs in the last do-while loop which is to find the root.

/* x0 - number at which, f(x0) yields the smallest possible negative value.
     x1 - number at which, f(x0) yields the smallest possible positive value.
     x2 - the mid-point or bisection of x0,x1
      x  - variable used in the computation of f(x)
      a -  the coefficient of x^2, in the polynomial of the form : ax^2+bx+c=0
      b -  the coefficient of x, in the polynomial of the form : ax^2+bx+c=0
      c -  the value of c, in the polynomial of the form : ax^2+bx+c=0
      fx - the computed value of f(x), using different values of x during different iterations.
*/

#include<iostream.h>
#include<conio.h>
#include<math.h>

void bisection()
{
float x=0,x0=0,x1=0,x2=0;
int i=0,a=0,b=0,c=0,fx=0;

cout<<"\n              Find root of a given polynomial by BISECTION METHOD";
cout<<"\n\nEnter the polynomial which is in the form ax^2+bx+c=0 :";
cout<<"\n\na=";
cin>>a;
cout<<"b=";
cin>>b;
cout<<"c=";
cin>>c;

/* First do-while loop to find : x0 */

do
{
x=i;
fx=((a*pow(x,2))+(b*x)+c);

if (fx<0)
{
x0=i;
}

i++;
}while(fx>0);

i=0;

/* Second do-while loop to find : x1 */

do
{
x=i;
fx=((a*pow(x,2))+(b*x)+c);

if (fx>0)
{
x1=i;
}

i++;
}while(fx<0);
cout<<"\nRoot of the given polynomial lies between "<<x0<<" and "<<x1;

/* Third do-while loop to find : x2 */

do
{
x2=((x0+x1)/2);
x=x2;
fx=((a*pow(x,2))+(b*x)+c);

if (fx<0)
{
x0=x2;
}

if (fx>0)
{
x1=x2;
}}while(fx!=0);

cout<<"\n\nThe root of the given polynomial is : "<< x2;
}

/* Main Function */

void main()
{
clrscr();
bisection();
getch();
}

Now coming on to the Regula Falsi method.
PROBLEMS IN FALSE POSITION / REGULA FALSI :
1. same as above.

/* x0 - number at which, f(x0) yields the smallest possible negative value.
     x1 - number at which, f(x0) yields the smallest possible positive value.
     x2 - the value which is computed using the False Position / Regula Falsi Method.
      x  - variable used in the computation of f(x)
      a -  the coefficient of x^2, in the polynomial of the form : ax^2+bx+c=0
      b -  the coefficient of x, in the polynomial of the form : ax^2+bx+c=0
      c -  the value of c, in the polynomial of the form : ax^2+bx+c=0
      fx - the computed value of f(x), using different values of x during different iterations.
*/

#include<iostream.h>
#include<conio.h>
#include<math.h>

void falsepos()
{
float temp=0,x=0,x0=0,x1=0,x2=0,fx0=0,fx1=0;
int i=0,a=0,b=0,c=0,fx=0;

cout<<"\n              Find root of a given polynomial by REGULA FALSI METHOD";
cout<<"\n\nEnter the polynomial which is in the form ax^2+bx+c=0 :";
cout<<"\n\na=";
cin>>a;
cout<<"b=";
cin>>b;
cout<<"c=";
cin>>c;

/* First do-while loop to find : x0 */

do
{
x=i;
fx=((a*pow(x,2))+(b*x)+c);

if (fx<0)
{
x0=i;
}

i++;
}while(fx>0);

i=0;

/* Second do-while loop to find : x1 */

do
{
x=i;
fx=((a*pow(x,2))+(b*x)+c);

if (fx>0)
{
x1=i;
}

i++;
}while(fx<0);
cout<<"\nRoot of the given polynomial lies between "<<x0<<" and "<<x1;

/* Third do-while loop to find : x2 */

do
{
if(x1<x0)
{
temp=x0;
x0=x1;
x1=temp;
}

fx0=((a*pow(x0,2))+(b*x0)+c);
fx1=((a*pow(x1,2))+(b*x1)+c);
x2=(x0-(((fx0)*(x1-x0))/((fx1)-(fx0))));
x=x2;
fx=((a*pow(x,2))+(b*x)+c);

if (fx<0)
{
x0=x2;
}

if (fx>0)
{
x1=x2;
}}while(fx!=0);

cout<<"\n\nThe root of the given polynomial is : "<< x2;
}

/* Main Function */

void main()
{
clrscr();
falsepos();
getch();
}

Please help me out. Thanks in advance. :)

look it depends on the kind of polynomial and the coeff u r taking..

ax2+bx+c=0 will be increasing function for most value of x if a, b and c are all positive. so you will never get its value less than 0 for most values of x and f(x) will go on increasing over ur while loop and u will stuck in an infinite loop.

Comments
Thanks for your useful suggestions, it helped me a lot.

Yeah i understand what you're trying to say. But even among the roots, which the program is able to find out successfully, there is some amount of deviation between it and the roots found out with the help of a scientific calculator. Not sure why that's the case ... ?

In some cases, the above mentioned deviation is small, but at times, it differs by huge factors. In simple words, the program isn't yielding accurate / stable results.

Also, something else i would like to know : Is there any way by which, we can control the precision of the value, returned by a variable which is of float datatype, in C++ ?

for eg, 52/63 = 0.825396825
so can we set the precision, so that 0.825 or something like that is displayed, and not 0.825396825 ?

Edited 6 Years Ago by n21115: n/a

I have worked on both the programs and have been able to upgrade and improve the previous programs by a very large factor. There are uncountable new and improved things in this version. I have been successful in eliminating quite a part of the probability of any inaccuracy.

Im impatiently waiting for some constructive criticism as well as appreciation and suggestion. So please feel free to let me know of your suggestions to improve these programs further.

Bisection Method :

/* x0 - number at which, f(x0) yields the smallest possible negative value.
     x1 - number at which, f(x0) yields the smallest possible positive value.
     x2 - the mid-point or bisection of x0,x1
      x  - variable used in the computation of f(x)
      a -  the coefficient of x^2, in the polynomial of the form : ax^2+bx+c=0
      b -  the coefficient of x, in the polynomial of the form : ax^2+bx+c=0
      c -  the value of c, in the polynomial of the form : ax^2+bx+c=0
      fx - the computed value of f(x), using different values of x during different iterations.
*/

#include<iostream.h>
#include<conio.h>
#include<math.h>
#include<process.h>

void bisection()
{
float x=0,x0=0,x1=0,x2=0,fx=0,fpos=0,fneg=0,checkans=0;
int a=0,b=0,c=0,i=0,fxverify=0;

cout<<"\n                    Copyright (C) R.D. - All rights reserved.";
cout<<"\n              Find root of a given polynomial by BISECTION METHOD";
cout<<"\n\nEnter the polynomial which is in the form ax^2+bx+c=0 :";
cout<<"\n\na=";
cin>>a;
cout<<"b=";
cin>>b;
cout<<"c=";
cin>>c;

/* First do-while loop to find : x0 */

do
{
x=i;
fx=((a*pow(x,2))+(b*x)+c);

if (fx<0)
{
x0=i;
}

i++;

if(i==5000)
{cout<<"\nThe given equation is an increasing function, thus,";
cout<<"\nThere are no roots of the given equation";
cout<<" for which f(x)=0";
cout<<"\n\nThe program will now exit. Press any key to continue ...";
getch(); exit(0);}

}while(fx>0);

i=0;

/* Second do-while loop to find : x1 */

do
{
x=i;
fx=((a*pow(x,2))+(b*x)+c);

if (fx>0)
{
x1=i;
}

i++;

if(i==5000)
{cout<<"\nThe given equation is a decreasing function, thus,";
cout<<"\nThere are no roots of the given equation";
cout<<" for which f(x)=0";
cout<<"\n\nThe program will now exit. Press any key to continue ...";
getch(); exit(0);}

}while(fx<0);

fneg=x0; fpos=x1;

/* Third do-while loop to find : x2 */

i=0;

do
{
checkans=x2;

x2=((x0+x1)/2);

if(checkans==x2)
{break;}

cout<<"\nIteration number : "<<i<<" ,"<<"root exists between "<<x0<<" and "<<x1;

x=x2;
fx=((a*pow(x,2))+(b*x)+c);

if (fx<0)
{
x0=x2;
}

if (fx>0)
{
x1=x2;
}

i++;
}while(checkans!=x2);

cout<<"\n\nThe given polynomial is : "<<"("<<a<<")"<<"(x)"<<"^2 + "<<"("<<b<<")"<<"(x) + "<<"("<<c<<") = 0";
cout<<"\n\nRoot of the given polynomial lies between "<<fneg<<" and "<<fpos;
cout<<"\n\nThe root of the given polynomial is : "<< x2;

fxverify=((a*pow(x2,2))+(b*x2)+c);
cout<<"\n\nVerification : f("<<x2<<") = "<<a<<"("<<x2<<")"<<"^2 + "<<"("<<b<<")"<<"("<<x2<<")"<<" + "<<"("<<c<<")";
cout<<"\n               f("<<x2<<") = "<<fxverify;
}

/* Main Function */

void main()
{
clrscr();
bisection();
getch();
}

False Position / Regula Falsi / Secant Method :

/* x0 - number at which, f(x0) yields the smallest possible negative value.
     x1 - number at which, f(x0) yields the smallest possible positive value.
     x2 - the number which is computed by using the False Position / Regula Falsi / Secant Method.
      x  - variable used in the computation of f(x)
      a -  the coefficient of x^2, in the polynomial of the form : ax^2+bx+c=0
      b -  the coefficient of x, in the polynomial of the form : ax^2+bx+c=0
      c -  the value of c, in the polynomial of the form : ax^2+bx+c=0
      fx - the computed value of f(x), using different values of x during different iterations.
*/

#include<iostream.h>
#include<conio.h>
#include<math.h>
#include<process.h>

void falsepos()
{
float x=0,x0=0,x1=0,x2=0,fpos=0,fneg=0,fx=0,fx1=0,fx0=0,temp=0,checkans=0;
int a=0,b=0,c=0,i=0,fxverify=0;

cout<<"\n                    Copyright (C) R.D. - All rights reserved.";
cout<<"\n              Find root of a given polynomial by FALSE POSITION METHOD";
cout<<"\n\nEnter the polynomial which is in the form ax^2+bx+c=0 :";
cout<<"\n\na=";
cin>>a;
cout<<"b=";
cin>>b;
cout<<"c=";
cin>>c;

/* First do-while loop to find : x0 */

do
{
x=i;
fx=((a*pow(x,2))+(b*x)+c);

if (fx<0)
{
x0=i;
}

i++;

if(i==5000)
{cout<<"\nThe given equation is an increasing function, thus,";
cout<<"\nThere are no roots of the given equation";
cout<<" for which f(x)=0";
cout<<"\n\nThe program will now exit. Press any key to continue ...";
getch(); exit(0);}

}while(fx>0);

i=0;

/* Second do-while loop to find : x1 */

do
{
x=i;
fx=((a*pow(x,2))+(b*x)+c);

if (fx>0)
{
x1=i;
}

i++;

if(i==5000)
{cout<<"\nThe given equation is a decreasing function, thus,";
cout<<"\nThere are no roots of the given equation";
cout<<" for which f(x)=0";
cout<<"\n\nThe program will now exit. Press any key to continue ...";
getch(); exit(0);}

}while(fx<0);

fneg=x0; fpos=x1;

/* Third do-while loop to find : x2 */

i=0;

do
{
if(x1<x0)
{temp=x0; x0=x1; x1=temp;}

fx0=((a*pow(x0,2))+(b*x0)+c);
fx1=((a*pow(x1,2))+(b*x1)+c);

checkans=x2;

x2=(x1-(((x1-x0)/(fx1-fx0))*fx1));

if(checkans==x2)
{break;}

cout<<"\nIteration number : "<<i<<" ,"<<"root exists between "<<x0<<" and "<<x1;

x=x2;
fx=((a*pow(x,2))+(b*x)+c);

if (fx<0)
{
x0=x2;
}

if (fx>0)
{
x1=x2;
}

i++;
}while(checkans!=x2);

cout<<"\n\nThe given polynomial is : "<<"("<<a<<")"<<"(x)"<<"^2 + "<<"("<<b<<")"<<"(x) + "<<"("<<c<<") = 0";
cout<<"\n\nRoot of the given polynomial lies between "<<fneg<<" and "<<fpos;
cout<<"\n\nThe root of the given polynomial is : "<< x2;

fxverify=((a*pow(x2,2))+(b*x2)+c);
cout<<"\n\nVerification : f("<<x2<<") = "<<a<<"("<<x2<<")"<<"^2 + "<<"("<<b<<")"<<"("<<x2<<")"<<" + "<<"("<<c<<")";
cout<<"\n               f("<<x2<<") = "<<fxverify;
}

/* Main Function */

void main()
{
clrscr();
falsepos();
getch();
}

The programs have been updated :

1. They can now find the roots of the equations of these forms :
ax^2+bx+c=0
ax^3+bx^2+cx+d=0
ax^4+bx^3+cx^2+dx+e=0
(x^2)-n=0 [For finding the square root of a number]

2. They show the whole iteration process status : current iteration number, both the points between which, the root exists.

3. After finding the root, the whole verification process is shown step by step. (f(x)=0 is proved)

4. If the given equation is increasing or decreasing, and no root exists for the given equation, this is declared at the appropriate point and the program quits.

5. The previous programs were run without imposing any limits, the new updated version, though, uses logical limits which results in a better and much more efficient program.

But there is a slight problem. Whenever the root of the equation of the type : (x^2)-n=0, is to be calculated, it shows a "FLOATING POINT ERROR : DOMAIN". IMP : This error originates only when the square root of the number is a whole number (sqrt of 4=2) This equation, by the way, is used to find the root of a given number by using the false position method.

As always, i would be extremely happy to receive some constructive feedback and suggestions.

Edited 6 Years Ago by n21115: n/a

Attachments
/* x0 - number at which, f(x0) yields the smallest possible negative value.
     x1 - number at which, f(x0) yields the smallest possible positive value.
     x2 - the number which is computed by using the False Position / Regula Falsi / Secant Method.
      x  - variable used in the computation of f(x)
      fx - the computed value of f(x), using different values of x during different iterations.
*/

#include<iostream.h>
#include<conio.h>
#include<math.h>
#include<process.h>

void falsepos()
{
float x=0,x0=0,x1=0,x2=0,fpos=0,fneg=0,fx=0,fx1=0,fx0=0,temp=0,checkans=0;
int a=0,b=0,c=0,d=0,e=0,n=0,i=0,fxverify=0,menuopt=0;

cout<<"\n                    Copyright (C) R.D. - All rights reserved.";
cout<<"\n              Find root of a given polynomial by FALSE POSITION METHOD";
cout<<"\n\nSelect the type of equation, whose root is to be computed :";
cout<<"\n\nEnter 1 for quadratic equations of the form :   ax^2+bx+c=0";
cout<<"\nEnter 2 for cubic equations of the form :       ax^3+bx^2+cx+d=0";
cout<<"\nEnter 3 for quartic equations of the form :     ax^4+bx^3+cx^2+dx+e=0";
cout<<"\nEnter 4 for finding the square root of a number";
cout<<"\n\nEnter your desired choice : ";
cin>>menuopt;

if(menuopt==1)
{
clrscr();
cout<<"\n\nEnter the polynomial which is in the form ax^2+bx+c=0 :";
cout<<"\n\na="; cin>>a;
cout<<"b="; cin>>b;
cout<<"c="; cin>>c;
}

if(menuopt==2)
{
clrscr();
cout<<"\n\nEnter the polynomial which is in the form ax^3+bx^2+cx+d=0 :";
cout<<"\n\na="; cin>>a;
cout<<"b="; cin>>b;
cout<<"c="; cin>>c;
cout<<"d="; cin>>d;
}

if(menuopt==3)
{
clrscr();
cout<<"\n\nEnter the polynomial which is in the form ax^4+bx^3+cx^2+dx+e=0 :";
cout<<"\n\na="; cin>>a;
cout<<"b="; cin>>b;
cout<<"c="; cin>>c;
cout<<"d="; cin>>d;
cout<<"e="; cin>>e;
}

if(menuopt==4)
{
clrscr();
cout<<"\n\nEnter the polynomial which is in the form (x^2)-n=0 :";
cout<<"\n\nEnter the number whose square root is to be computed : "; cin>>n;
}


/* First do-while loop to find : x0 */

do
{
x=i;

if(menuopt==1)
{fx=((a*pow(x,2))+(b*x)+c);}
if(menuopt==2)
{fx=((a*pow(x,3))+(b*pow(x,2))+(c*x)+d);}
if(menuopt==3)
{fx=((a*pow(x,4))+(b*pow(x,3))+(c*pow(x,2))+(d*x)+e);}
if(menuopt==4)
{fx=((pow(x,2))-n);}

if (fx<0)
{
x0=i;
}

i++;

if(i==5000)
{cout<<"\nThe given equation is an increasing function, thus,";
cout<<"\nThere are no roots of the given equation";
cout<<" for which f(x)=0";
cout<<"\n\nThe program will now exit. Press any key to continue ...";
getch(); exit(0);}

}while(fx>0);


i=0;

/* Second do-while loop to find : x1 */

do
{
x=i;

if(menuopt==1)
{fx=((a*pow(x,2))+(b*x)+c);}
if(menuopt==2)
{fx=((a*pow(x,3))+(b*pow(x,2))+(c*x)+d);}
if(menuopt==3)
{fx=((a*pow(x,4))+(b*pow(x,3))+(c*pow(x,2))+(d*x)+e);}
if(menuopt==4)
{fx=((pow(x,2))-n);}

if (fx>0)
{
x1=i;
}

i++;

if(i==5000)
{cout<<"\nThe given equation is a decreasing function, thus,";
cout<<"\nThere are no roots of the given equation";
cout<<" for which f(x)=0";
cout<<"\n\nThe program will now exit. Press any key to continue ...";
getch(); exit(0);}

}while(fx<0);

fneg=x0; fpos=x1;

/* Third do-while loop to find : x2 */

i=0;

do
{
if(x1<x0)
{temp=x0; x0=x1; x1=temp;}

if(menuopt==1)
{fx0=((a*pow(x0,2))+(b*x0)+c);
fx1=((a*pow(x1,2))+(b*x1)+c);}

if(menuopt==2)
{fx0=((a*pow(x0,3))+(b*pow(x0,2))+(c*x0)+d);
fx1=((a*pow(x1,3))+(b*pow(x1,2))+(c*x1)+d);}

if(menuopt==3)
{fx0=((a*pow(x0,4))+(b*pow(x0,3))+(c*pow(x0,2))+(d*x0)+e);
fx1=((a*pow(x1,4))+(b*pow(x1,3))+(c*pow(x1,2))+(d*x1)+e);}

if(menuopt==4)
{fx0=((pow(x0,2))-n);
fx1=((pow(x1,2))-n);}

checkans=x2;

x2=(x1-(((x1-x0)/(fx1-fx0))*fx1));

if(checkans==x2)
{break;}

cout<<"\nIteration number : "<<i<<" ,"<<"root exists between "<<x0<<" and "<<x1;

x=x2;

if(menuopt==1)
{fx=((a*pow(x,2))+(b*x)+c);}
if(menuopt==2)
{fx=((a*pow(x,3))+(b*pow(x,2))+(c*x)+d);}
if(menuopt==3)
{fx=((a*pow(x,4))+(b*pow(x,3))+(c*pow(x,2))+(d*x)+e);}
if(menuopt==4)
{fx=((pow(x,2))-n);}

if (fx<0)
{
x0=x2;
}

if (fx>0)
{
x1=x2;
}

i++;
}while(checkans!=x2);


if(menuopt==1)
{
cout<<"\n\nThe given polynomial is : "<<"("<<a<<")"<<"(x)"<<"^2 + "<<"("<<b<<")"<<"(x) + "<<"("<<c<<") = 0";
cout<<"\n\nRoot of the given polynomial lies between "<<fneg<<" and "<<fpos;
cout<<"\n\nThe root of the given polynomial is : "<< x2;

fxverify=((a*pow(x2,2))+(b*x2)+c);
cout<<"\n\nVerification : f("<<x2<<") = "<<a<<"("<<x2<<")"<<"^2 + "<<"("<<b<<")"<<"("<<x2<<")"<<" + "<<"("<<c<<")";
cout<<"\n               f("<<x2<<") = "<<fxverify;
}

if(menuopt==2)
{
cout<<"\n\nThe given polynomial is : "<<"("<<a<<")"<<"(x)"<<"^3 + "<<"("<<b<<")"<<"(x)"<<"^2 + "<<"("<<c<<")"<<"(x) + "<<"("<<d<<") = 0";
cout<<"\n\nRoot of the given polynomial lies between "<<fneg<<" and "<<fpos;
cout<<"\n\nThe root of the given polynomial is : "<< x2;

fxverify=((a*pow(x2,3))+(b*pow(x2,2))+(c*x2)+d);
cout<<"\n\nVerification : f("<<x2<<") = "<<a<<"("<<x2<<")"<<"^3 + "<<b<<"("<<x2<<")"<<"^2 + "<<"("<<c<<")"<<"("<<x2<<")"<<" + "<<"("<<d<<")";
cout<<"\n               f("<<x2<<") = "<<fxverify;
}

if(menuopt==3)
{
cout<<"\n\nThe given polynomial is : "<<"("<<a<<")"<<"(x)"<<"^4 + "<<"("<<b<<")"<<"(x)"<<"^3 + "<<"("<<c<<")"<<"(x)"<<"^2 + "<<"("<<d<<")"<<"(x) + "<<"("<<e<<") = 0";
cout<<"\n\nRoot of the given polynomial lies between "<<fneg<<" and "<<fpos;
cout<<"\n\nThe root of the given polynomial is : "<< x2;

fxverify=((a*pow(x2,4))+(b*pow(x2,3))+(c*pow(x2,2))+(d*x2)+e);
cout<<"\n\nVerification : f("<<x2<<") = "<<"("<<a<<")("<<x2<<")"<<"^4 + ("<<b<<")("<<x2<<")"<<"^3 + ("<<c<<")("<<x2<<")"<<"^2 + "<<"("<<d<<")"<<"("<<x2<<")"<<" + "<<"("<<e<<")";
cout<<"\n               f("<<x2<<") = "<<fxverify;
}

if(menuopt==4)
{
cout<<"\n\nThe given polynomial is : "<<"(x^2)-"<<n<<" = 0";
cout<<"\n\nRoot of the given polynomial lies between "<<fneg<<" and "<<fpos;
cout<<"\n\nThe root of the given polynomial is : "<< x2;

fxverify=((pow(x2,2))-n);
cout<<"\n\nVerification : f("<<x2<<") = "<<"("<<x2<<"^2) - "<<n<<" = 0";
cout<<"\n               f("<<x2<<") = "<<fxverify;
}


}

/* Main Function */

void main()
{
clrscr();
falsepos();
getch();
}

Ironic! We just completed our section on the bisection method in my Numerical Analysis class!

Upon first glance you are using far too many lines of code for this. I would try to take advatage of more recursion in your program. If you like I can post some pseudocode back here later tonight that might point you in the right dirction.

After scrutinizing the bisection code a little more I have one main critique. Correct me if I'm wrong but the first two do loops are unnecessary. Aside from error checking for polynomials that have no roots they do nothing except reiterate costly function evaluations. Big efficiency waste IMO

Here is some pseudocode from a textbook on the bisection method. Look it over to get some ideas for your program. Ask if you have any more questions.

procedure [I]Bisection[/I](f, a, b, nmax, e)
int n, nmax;
double a, b, c, fa, fb, fc, error;
fa = f(a);
fb = f(b);
if sign(fa) == sign(fb)
     output a, b, fa, fb;
     output "function has same signs at a and b";
end if

error = b - a;
for n= 0 to nmax do
     error = error/2;
     c = a + error;
     fc = f(c);
     output n, c, fc, error;
     if |error| < e
          output "convergence";
     end if
     if sign(fa) != sign(fc) 
          b = c;
          fb = fc;
     else
          a = c;
          fa = fc;
     end if
end for
end procedure

Edited 6 Years Ago by _Set: n/a

This article has been dead for over six months. Start a new discussion instead.