Nemton Rhapson Method
Hey, i need help making a method that does the newton rhapson method;
public static double newton(Polynomial p, double x0){
}
newton rhap method is X(i+1)=Xi-(f(Xi)/(f '(Xi)) (Xi is initial x0)
*the answer should return when Xi - X(i-1) < 10^ -8
Polynomial is already defined as an array that just lists the coefficients of the polynomial.(it is a object)
i have already made methods that can
1.evaluate polynomials,
2.find degree of polynomials
3. find derivative of polynomials,
4, add polynomials,
5. multiply polynomials
But i really need help with this mwthod....help please
[665 byte] By [
MaddMana] at [2007-10-2 20:57:54]
Looks straightforward enough, what is the problem?
> Hey, i need help making a method that does the newton
> rhapson method;
> public static double newton(Polynomial p, double
> x0){
>}
> on rhap method is X(i+1)=Xi-(f(Xi)/(f '(Xi)) (Xi is
> initial x0)
> *the answer should return when Xi - X(i-1) < 10^ -8
>
> Polynomial is already defined as an array that just
> lists the coefficients of the polynomial.(it is a
> object)
> have already made methods that can
> .evaluate polynomials,
> 2.find degree of polynomials
> 3. find derivative of polynomials,
> 4, add polynomials,
> 5. multiply polynomials
>
> But i really need help with this mwthod....help please
Like what? Writing it for you? You have every requirement in front of you.
Start with a Polynomial class.
%
At least make an attempt here. Show us what you have tried.
Hell, even providing this:
public class NewtonRaphson {
static public void main(String[] args) {
}
}
would be better than nothing!
You're going to need some basic concepts to your design, such as:
how does the user input the polynomial?
how do you evaluate the polynomial?
how do you evaluate the derivative of the polynomial?
how do you perform the iterative/recursive part of the routine?
etc.
start by fleshing out the major steps the program will have to follow, in either psuedocode or plain english. at least that's a start.
then tackle on problem at a time, and ask for any help you need along the way.
- Adam
this ismy work so far, bits and parts are unfinishedand i know that it is probably of really poor quality, but i am very much so a beginner...so be kind.
public class Polynomial {
//Instance Variables
public int deg;
private int[] p;
//Constructor One
public Polynomial(int n) {
this(make(n));
deg =getDegree();
}
//Constructor Two
public Polynomial(int[] coeffs) {
p=coeffs;
this.p=p;
deg =getDegree();
}
private static int[] make(int n ) {
int[] p= new int[n+1];
p[n]=1;
return p;
}
//Methods
public double evaluate(double x) {
double r=1, value = 0;
for (int i=0; i < p.length; i++, r*=x)
value+= p*r;
return value;
}
public int getDegree(){
deg=p.length-1;
return deg;
}
public int getCoefficient(int r) {
int k = p.length-1;
IllegalArgumentException ie;
if(r < 0){ie=new IllegalArgumentException ("Please select a valid 'power' to get the coefficient of");
throw(ie);} else
{if(r > k) {ie=new IllegalArgumentException ("Please select a valid 'power' to get the coefficient of");
throw(ie);} else{return p[r];}
}
}
public void setCoefficient(int r, int coeff) {
int k = p.length-1;
IllegalArgumentException ie;
if(r < 0){ie=new IllegalArgumentException ("Please select a valid 'power' to set the coefficient to");
throw(ie);} else
{if(r > k) {ie=new IllegalArgumentException ("Please select a valid 'power' to set the coefficient to");
throw(ie);} else{p[r]=coeff;}}
}
public static Polynomial add(Polynomial p1, Polynomial p2){
int a=0;
Polynomial c = new Polynomial(Math.max(p1.deg, p2.deg));
for(int i=0; i<=p1.deg;i++) {a=p1.getCoefficient(i)+p2.getCoefficient(i);
c.setCoefficient(i,a);}
return c;}
public Polynomial derivative(){
int a=0;
Polynomial c= new Polynomial(this.deg-1);
if( this.deg == 0){}else{
for(int i=1; i<=this.deg; i++){
a=this.getCoefficient(i)*i;
c.setCoefficient(i-1,a);
}
}return c;
}
public static Polynomial multiply(Polynomial p1, Polynomial p2){
int[] c = new int[p1.deg+p2.deg+1];
for(int i=0; i<=p1.deg; i++){
for(int j=0; j<=p2.deg; j++) {
c[i+j]= c[i+j]+(p1.getCoefficient(i)*p2.getCoefficient(j)); }
}
Polynomial g=new Polynomial(c);
return g;
}
}
that is polynomial class and this is polynomialRootFinder class
public class PolynomialRootFinder
{
public static double NewtonRhapson(Polynomial p, double x0){
int a=0;
Polynomial c= new Polynomial(p.deg-1);
for(int i=1; i<=p.deg; i++){a=p.getCoefficient(i)*i;
c.setCoefficient(i-1,a);}
double x=0;
double y=0;
y=p.evaluate(x0);
x=c.evaluate(x0);
double b=(x0-(y/x));
return b;
//missing code
}
the problem i am having is writing the missing code..as u can see i have made a very legitimate attempt at the assignment, but i need help writing the iterative part of the code, that goes through and keeps working out new values of Xi, and stops when Xi-X(i-1) < 10^-8....
please help
Please repost your code using [code] tags.
four remarks for that code:
1. you have a method called derivative that returns a new copy of the derivative of the polynomial. Why are you duplicating this code in NewtonRaphson method.
2. NewtonRaphson method should start with a lowercase letter, by convention in java -> i.e. newtonRaphson
3. You going to want to use recursion to solve this.
What you need to do is this:
return NewtonRaphson(b, p);
(i.e. you want to pass the new approximation of the root to the root finding method).
BUT you will also need to include a stopping condition:
if ( abs(b - x0) < delta) return b
else return NewtonRaphson(b, p);
something like that. I suggest that you consult a tutorial on recursive methods.
4. Since you're going to be using the derivative of the polynomial A LOT, I suggest you store a copy of the derivative in the polynomial, using lazy initialization (This is important, you don't want to create the derivative in the constructor, that will give you a stack overflow).
something like this:
private polynomial derivate;
public Polynomial getDerivative() {
if (derivate == null) {
// create the derivative here
}
return derivative;
}
- Adam
I wouldn't use recursion for this. You don't need to keep old state. It's a simple do - while loop.
> I wouldn't use recursion for this. You don't need to
> keep old state. It's a simple do - while loop.
fair enough.
@OP
if you choose not to use recursion, you're going to want to change the code
double b = x0 - (x / y)
return b
to
x0 = x0 - (x / y)
and wrap the whole thing in a while loop. then return x0.
- Adam
> double b = x0 - (x / y)
> return b
>
> to
>
> x0 = x0 - (x / y)
>
scratch that. you still need to keep track of the original x0.
what you need to do is store the new approximation in b, test for how close together the approximations are, then assign b to x0 at the beginning of the loop (except the first time through the loop).
I personally still think this would be easier and more straight forward using recursion, but that's a personal opinion. You don't really NEED to use recursion.
- Adam
this ismy work so far, bits and parts are unfinishedand i know that it is probably of really poor quality, but i am very much so a beginner...so be kind.
public class Polynomial {
//Instance Variables
public int deg;
private int[] p;
//Constructor One
public Polynomial(int n) {
this(make(n));
deg =getDegree();
}
//Constructor Two
public Polynomial(int[] coeffs) {
p=coeffs;
this.p=p;
deg =getDegree();
}
private static int[] make(int n ) {
int[] p= new int[n+1];
p[n]=1;
return p;
}
//Methods
public double evaluate(double x) {
double r=1, value = 0;
for (int i=0; i < p.length; i++, r*=x)
value+= p*r;
return value;
}
public int getDegree(){
deg=p.length-1;
return deg;
}
public int getCoefficient(int r) {
int k = p.length-1;
IllegalArgumentException ie;
if(r < 0){ie=new IllegalArgumentException ("Please select a valid 'power' to get the coefficient of");
throw(ie);} else
{if(r > k) {ie=new IllegalArgumentException ("Please select a valid 'power' to get the coefficient of");
throw(ie);} else{return p[r];}
}
}
public void setCoefficient(int r, int coeff) {
int k = p.length-1;
IllegalArgumentException ie;
if(r < 0){ie=new IllegalArgumentException ("Please select a valid 'power' to set the coefficient to");
throw(ie);} else
{if(r > k) {ie=new IllegalArgumentException ("Please select a valid 'power' to set the coefficient to");
throw(ie);} else{p[r]=coeff;}}
}
public static Polynomial add(Polynomial p1, Polynomial p2){
int a=0;
Polynomial c = new Polynomial(Math.max(p1.deg, p2.deg));
for(int i=0; i<=p1.deg;i++) {a=p1.getCoefficient(i)+p2.getCoefficient(i);
c.setCoefficient(i,a);}
return c;}
public Polynomial derivative(){
int a=0;
Polynomial c= new Polynomial(this.deg-1);
if( this.deg == 0){}else{
for(int i=1; i<=this.deg; i++){
a=this.getCoefficient(i)*i;
c.setCoefficient(i-1,a);
}
}return c;
}
public static Polynomial multiply(Polynomial p1, Polynomial p2){
int[] c = new int[p1.deg+p2.deg+1];
for(int i=0; i<=p1.deg; i++){
for(int j=0; j<=p2.deg; j++) {
c[i+j]= c[i+j]+(p1.getCoefficient(i)*p2.getCoefficient(j)); }
}
Polynomial g=new Polynomial(c);
return g;
}
}
that is polynomial class and this is polynomialRootFinder class
public class PolynomialRootFinder
{
public static double NewtonRhapson(Polynomial p, double x0){
int a=0;
Polynomial c= new Polynomial(p.deg-1);
for(int i=1; i<=p.deg; i++){a=p.getCoefficient(i)*i;
c.setCoefficient(i-1,a);}
double x=0;
double y=0;
y=p.evaluate(x0);
x=c.evaluate(x0);
double b=(x0-(y/x));
return b;
//missing code
}
the problem i am having is writing the missing code..as u can see i have made a very legitimate attempt at the assignment, but i need help writing the iterative part of the code, that goes through and keeps working out new values of Xi, and stops when Xi-X(i-1) < 10^-8....
please help
yes,
i thought that i needed to use a while loop, because i have no idea with recursion, but i am not sure what to put inside the while loop....thats what i need help with.
something like
while(Xi - X(i-1) > 10^-8) {
//do something}
but i dont know what the 'do soemthing' is. I know it needs to check that the last value and the value before that are within 10^-8 of eacth other, and if they are, it outputs the final value, if not, it keeps goinggg.how do i do this part?
Help please
> yes,
> i thought that i needed to use a while loop, because
> i have no idea with recursion, but i am not sure what
> to put inside the while loop....thats what i need
> help with.
> something like
> while(Xi - X(i-1) > 10^-8) {
> //do something}
>
> but i dont know what the 'do soemthing' is. I know it
> needs to check that the last value and the value
> before that are within 10^-8 of eacth other, and if
> they are, it outputs the final value, if not, it
> keeps goinggg.how do i do this part?
>
> Help please
you've already go the Check part done. so all you need to do is the iterative calculations. in psuedocode, it might look like this:
while (x_i - x_i_old > 1e-8) {
x_i_old = x_i // this is critical so that you can remember the previous value
x_i = Newton Raphson Evaluation
}
That's it, that's all there is to it.
By the way, did you read my point about caching the derivative? I think it would really be worth while, especially if you end up with a polynomial where it's going to take a lot of iterations to find the root, or where you may end up wanting find more than one root.
- Adam
> while(Xi - X(i-1) > 10^-8) {
> //do something}
Better make that Math.abs(X_i-X_i-1)
I would simply do this:public double NR(double x) {
Polynomial fxdx= this.deriv();
double delta;
while (Math.abs(delta= this.eval(x)/fxdx.eval(x)) >= 1e-8) {
x-= delta;
}
return x;
}
... which is a straight implementation according to that formula. Note that
polynomial f' (fxdx) is created only once per method invocation.
kind regards,
Jos
JosAHa at 2007-7-13 23:42:37 >
> Better make that Math.abs(X_i-X_i-1)lol. yeah. Thanks Jos. I think I said that too, in an earlier post, but I got a bit sloppy with that last one.thanx- adam
> > Better make that Math.abs(X_i-X_i-1)
>
> lol. yeah. Thanks Jos. I think I said that too, in an earlier post, but I
> got a bit sloppy with that last one.
Yep I saw that when I reread this thread so skip my redundant remark.
I think (all IMVHO of course) that the OP's problem is the programming
part (while-loops, if-clauses etc.) The polynomial part can't be a problem.
kind regards,
Jos
