Loop problem with Newton-Raphson iteration

[rojan1918]

So I have a problem with the following code. In the functions NewRapHorner and HornerDivPol I am supposed to find the roots of the polynomial. If the polynomial has no roots you have the option to go back beginning from the Horner function i. e. same polynomial. If there is at least one root, but less roots than the the degree of the polynomial it will automaically go back to the Horner function. Here is the problem. If I for example type in the polynomial f(x)=5x^5+6x^4-8x^3-12x^2+14x+7 it first time finds one root and then stops cause of max. number of iterations(this is correct and no problem here). Then when it starts from Horner and I come to NewRapHorner and try to find roots again it can't find this root even though its the same polynomial! I've tried to figure out the problem, but can't seem to find it. Hope someone can help.

#include <iostream>
#include <iomanip>
#include <math.h>
#include <stdlib.h>
#define MAXDEGREE 10

using namespace std;

void TypeDegree(int &n);
void TypeKoefficients(double a[MAXDEGREE+1], int n);
void OutputKoefficients(double a[MAXDEGREE+1], int n);
void OutputPolynomium(double a[MAXDEGREE+1], int n);
void FixPolynomium(double a[MAXDEGREE+1], int n);
void Horner(int n, double a[MAXDEGREE], double x);
void TypeNRData(double &x0, double &eps, int &N);
void NewRapHorner(double x0, double eps, int N, int n, double a[MAXDEGREE+1],double b[MAXDEGREE+1], double &root, int &success);
void HornerDivPol(int &n,double b[MAXDEGREE+1],double root);

int main() {
	int n,N,success,i=0,j=0;
	double a[MAXDEGREE+1],b[MAXDEGREE+1],fx,dfx,x,x0,eps,root,RootTabel[MAXDEGREE];
	char answer;

	TypeDegree(n);
    TypeKoefficients(a,n);
    OutputKoefficients(a,n);
    OutputPolynomium(a,n);
    cout<<"Would you like to change one or more of the coefficients of the polynomial?"<<endl<< "Answer y for yes or n for no";
    cin>>answer;
    if(answer=='y')
    FixPolynomium(a,n);
    do{
    for(i=0;i<=n;i++)
    b[i]=a[i];
    Horner(n,a,x);
    cout<<"\nWould you like to enter data for NR?";
    cin>>answer;
    if(answer=='j')
    TypeNRData(x0,eps,N);
    else{
    	cout<<"Thanks for using the program!";
    	return 0;
    }
	NewRapHorner(x0,eps,N,n,a,b,root,success);
    if(success==1){
	RootTabel[0]=root;
    do{
		HornerDivPol(n,b,root);
		NewRapHorner(x0,eps,N,n,a,b,root,success);
		i++;
	    RootTabel[i]=root;
	    if(success==0)
	    answer='y';
		}while(success==1 and n>1);
    if(n==1)
    return 0;
    }
    else{
    	cout<<"\nWould you like to try the program again from were you start by entering x for f(x) and an interval?";
    	cin>>answer;
    	if(answer=='n'){
    		cout<<"Thanks for using the program!";
    		return 0;
    	}
    }
    }while(answer=='y');

		return 0;
}

void TypeDegree(int &n){
	cout<<"Enter the degree og the polynomium you want: ";
	cin>>n;
}

void TypeKoefficients(double a[MAXDEGREE+1], int n){
	cout<<"Enter the coefficients of the polynomium with the coefficient belonging to the highest x-degree first: ";

	for(int i=0; i<=n;i++){
		cin>>a[i];
	}
}

void OutputKoefficients(double a[MAXDEGREE+1], int n){
	for(int i=0; i<=n;i++)
    cout<<a[i]<<" ";

	cout<<endl;
}

void OutputPolynomium(double a[MAXDEGREE+1], int n){
	cout<<"f(x)=";
	for(int i=0;i<=n;i++){
		cout<<a[i];
		if(n-i!=0){
			cout<<"(x^"<<n-i<<")";
		}
		if(a[i+1]>=0){
			if(i==n){
				break;
			}
		cout<<"+";

		}
	}
	cout<<endl;
}

void FixPolynomium(double a[MAXDEGREE+1], int n){
	int i;
	char answer;
	do{

	do{
	cout<<"Which coefficient do you want to change?";
	cin>>i;
	cout<<"Enter the new number";
	cin>>a[i-1];
	cout<<"Do you want to change another coefficient or the same? Enter y for yes or n for no";
	cin>>answer;
	}while(answer=='y');

	cout<<"The polynomium looks like the following"<<endl;

	cout<<"f(x)=";
	for(int i=0;i<=n;i++){
		cout<<a[i];
		if(n-i!=0){
			cout<<"(x^"<<n-i<<")";
		}
		if(a[i+1]>=0){
			if(i==n){
				break;
			}
		cout<<"+";

		}
	}
	cout<<"\nDo you want to change one or more coefficients int the new polynomium?"<<endl<< "answer y for yes or n for no";
	cin>>answer;
	}while(answer=='y');
}

void Horner(int n, double a[MAXDEGREE], double x){

	double A,B,fx,dfx;
	char answer;
	static const int y=n;

	n=y;

	do{
	cout<<endl<<"Enter a number where you want to findd the value of the function in the point and the value of the derivative";
	cin>>x;

	fx=a[0];
    dfx=a[0];

for(int i=0;i<n;i++){

	fx=fx*x+a[i+1];

	if(i!=n-1)
	dfx=dfx*x+fx;
	}

	cout<<"fx = "<<fx<<endl;
    cout<<"dfx = "<<dfx<<endl;


    cout<<"Enter an interval, where you want to see the value of the function at 20 different points"<<endl;
    cin>>A;
    cin>>B;

    cout<< setfill(' ') << setw(1) << "|" << setw(10) << left << "  x  " << setw(1) << "|" << setw(15) << left << "    fx    " << endl;

    x=A;
    for(int i=1;i<=20;i++){
    	fx=a[0];

    	if(i!=1)
    	x+=(B-A)/19;

    	for(int i=0;i<n;i++){

    		fx=fx*x+a[i+1];

    		}
	    cout << "  " <<right<< x << '\t' << "" <<setw(20)<<setprecision(20)<<right<< fx << '\t' <<endl;

    }
    cout<<"Do you want to try again?";
    cin>>answer;
    }while(answer=='y');

}

void TypeNRData(double &x0, double &eps, int &N){
	cout<<"Enter parameters for Newton-Raphson.\nEnter beginning point x0: "<<endl;
	cin>>x0;
	cout<<"Enter tolerance eps: "<<endl;
	cin>>eps;
	cout<<"Enter maximum amount of allowed iterations N: "<<endl;
	cin>>N;
}

void NewRapHorner(double x0, double eps, int N, int n, double a[MAXDEGREE+1],double b[MAXDEGREE+1], double &root, int &success){

	double dfx,fx;
	int i=0,k;


	root=x0;
	k=0;
	i=0;
	do{
		fx=b[0];
		dfx=b[0];

		for(k=0;k<n;k++){

			fx=fx*root+b[k+1];

			if(k!=n-1)
			dfx=dfx*root+fx;
			}


		i++;
		if(dfx==0){
		break;
		}
		root=root-(fx/dfx);


		} while(fabs(fx)>eps and i<N);

	    if(dfx==0){
			cout<<"\nFinished since dfx=0";
        success=0;
				}
	    else if(n>1 and i<N){
			cout<<"\nroot is x = "<<root<<" and f(x) = "<<fx;
			success=1;
			}
		else if(i==N){
			cout<<"\nFinished since we surpassed the number of allowed iterations";
        success=0;
		}
		else{
			cout<<"\nroot is x = "<<-b[1]/b[0]<<" hvor f(x) = "<<fx;
    		cout<<"\nThanks for using the program!";
			exit(1);
		}
}

void HornerDivPol(int &n,double b[MAXDEGREE+1],double root){
	double fx;

	fx=b[0];


for(int i=0;i<n;i++){

	fx=fx*root+b[i+1];
    b[i+1]=fx;
	}
    n-=1;
}

[TheIdeasMan]

Hi,

I quickly compiled using cpp.sh, anf got these warnings:

 In function 'int main()': 
20:22: warning: unused variable 'j' [-Wunused-variable] 
21:39: warning: unused variable 'fx' [-Wunused-variable] 
21:42: warning: unused variable 'dfx' [-Wunused-variable] 
21:60: warning: variable 'RootTabel' set but not used [-Wunused-but-set-variable] 
At global scope: 
207:76: warning: unused parameter 'a' [-Wunused-parameter] 
In function 'int main()': 35:18: warning: 'x' is used uninitialized in this function [-Wuninitialized]

The last one is the most important, always init your variables with something :+) But you get away with it.

The initialisation of your variables depends on the order of the function calls, IMO that's a bit sketchy :+) And you have a thing about sending uninitialised variables to functions, where the variables is set inside the function. Why not have a function that collects all the variables you need, then start calling other functions.?

With C++, one can delay the declaring a variable until it's needed, that is until one has sensible value to assign to it. This is better than declaring a heap of them on 1 line, then hope that one remembers to init them with something.

I haven't looked at the rest of the code.

Good Luck !!

Edit: It's a bit late at my end, sorry I haven't looked into your problem more deeply. ZZZZzzzzz.......

[rojan1918]

I see your point and have tried to fix it, but it doesn't solve my problem which occurs after the first loop in the outer do while loop in the main function

[TheIdeasMan]

Hi,

Sorry I haven't much time again, but I noticed you have this everywhere:

for(i=0;i<=n;i++)
    b[i]=a[i];

That's an array out of bounds access waiting to happen and you will be missing the first value in the array in any case, the normal form of a for loop is this:

for(int i=0; i < n; ++i)

As you point out, your problem is may be bigger than these often minor details. Consider using a debugger to see where things go wrong. Hopefully there will be a GUI one built into you IDE.

Another thing you have in multiple places:
if(dfx==0){

That is almost certainly false, double is not an exact representation, basically it's done with binary fractions. To compare a double with zero, you need to check that the absolute value of the number is less than some arbitrary precision value: 0.0001 say. Create a function to do that. Google about this whole topic, there is plenty written about it.

When putting in a double literal, put numbers on both sides of the decimal point, it's a reminder that you are dealing with double. So, not 0 or .0 or 0. 0.0 is what you want. Magic numbers should be made into const variables instead.

Your code could do with some formatting, most IDE's have a formatting option somewhere.

When you use short variable names, put a comment with their declaration so others have a chance of knowing what they mean.