Newton's Method

This is a discussion on Newton's Method within the C++ Programming forums, part of the General Programming Boards category; Hey everyone. I am trying to write a program using Newtons Method. I know there is no code here, but ...

  1. #1
    Registered User hottiefee's Avatar
    Join Date
    Oct 2010
    Location
    TN, USA
    Posts
    32

    Unhappy Newton's Method

    Hey everyone. I am trying to write a program using Newtons Method. I know there is no code here, but that's my problem... I don't know where to start. I know the method is similar to bisection so if anyone could explain either to me or just help me get started, please let me know. Here is my problem:

    I am trying to write a program in C++ to find a root of an equation. It starts with an initial guess, x(0), and generates successive approximate roots x(1), x(2), ... x(j), x(j+1) using the formula:
    x(j+1) = x(j) - ((fx(j)) / f'x(j))
    {x sub j+1 equals x sub j minus f(x sub j) divided by f prime (x sub j)} where f'(x sub j) is the derivative of function f evaluated at x = x(j). The formula generates a new guess, x(j=1), from a previous one, f(j). The program should terminate after 100 trials.
    From geometry we get the equation:
    (y(j+1) - y(j))/(x(j+1) - x(j)) = m
    where m is the slope of the line between points (x(j+1), y(j+1)) and (x(j), y(j)). y(j+1) is zero, y(j) is f(x(j)), and m is f'(x(j)). After rearranging we get:
    -f(x(j)) = f'(x(j)) * (x(j+1) - x(j))
    Write a program that uses Newtons method to approximate the nth root of a number to 6 decimal places.
    If x^n = c thenx^n - c = 0.
    Finding the rood of the second equation you get nroot(c).
    Test the program on sqroot(2), 3root(7), and 3root(-1).
    The program can use c/2 as its initial guess.

    Code:
    #include<iostream>
    #include<cmath>
    using namespace std;
    int main(){
    
          return 0;
    }
    That is how I started to set it up. I just don't know where to start... Thanks for any help.
    Last edited by hottiefee; 02-13-2011 at 06:20 PM. Reason: mispelled words

  2. #2
    -bleh-
    Join Date
    Aug 2010
    Location
    somewhere in this universe
    Posts
    452
    you need to define some tolerance: 10^-6 as the stopping condition. I would do it in the preprocessor.
    you need a c++ function that take in double value x, and return double value for the derivative f'(x).
    you need a c++ function that take in double value of x, and return double value for the function f(x);
    then, just for-loop the heck out of it;
    Code:
    for ( int i = 0 ; i < 100 ; ++ i) 
    {
          x -= f(x)/f'(x);
           if ( abs(x) <= tolerance) break; 
    }
    Last edited by nimitzhunter; 02-12-2011 at 07:29 PM.
    "All that we see or seem
    Is but a dream within a dream." - Poe

  3. #3
    Registered User hottiefee's Avatar
    Join Date
    Oct 2010
    Location
    TN, USA
    Posts
    32
    lol alright thanks. Ill let ya know how it goes.. workin on it now.

  4. #4
    Registered User hottiefee's Avatar
    Join Date
    Oct 2010
    Location
    TN, USA
    Posts
    32
    How can you calculate a derivative in c++? I know how on paper but don't know how to type it up...

  5. #5
    -bleh-
    Join Date
    Aug 2010
    Location
    somewhere in this universe
    Posts
    452
    there is no built-in symbolic derivative for c++. you have the option of doing the derivative on paper then write it into your f'(x) function. like if f(x) = x^2; i would write
    Code:
    double f_prime(double x)
    {
     return 2.0*x;
    }
    you can calculate the derivative numerically from the function f(x), but i don't think that's part of your assignment.
    Last edited by nimitzhunter; 02-12-2011 at 08:58 PM.
    "All that we see or seem
    Is but a dream within a dream." - Poe

  6. #6
    Registered User hottiefee's Avatar
    Join Date
    Oct 2010
    Location
    TN, USA
    Posts
    32
    Yeah. I'm starting to feel overwhelmed... lol I usually get these program fast but I'm stuck on this one... I know f(x) is the function of the curve, I think, so how do I even get that equation? would it be the slope equation y - y1 = m (x - x1) and solve for y? I need the derivative of f(x) but what excactly is that?

    I'm a math major so I can understand the concept of Newton's method but am so confused with the variables and equations..

  7. #7
    -bleh-
    Join Date
    Aug 2010
    Location
    somewhere in this universe
    Posts
    452
    Newton's method - Wikipedia, the free encyclopedia
    look at the examples.

    would it be the slope equation y - y1 = m (x - x1) and solve for y
    not quite, what you think of must be local linear approximation of sqrt(2), that could be done in one step without all the iterations.
    for your test cases; your funtion f(x) should be
    Code:
    f(x) = x^n - c;
    such that f( nroot(c) ) = 0 .

    I'll give you a hint here
    Code:
    double f(double x, int n, int c)
    Last edited by nimitzhunter; 02-12-2011 at 09:49 PM.
    "All that we see or seem
    Is but a dream within a dream." - Poe

  8. #8
    Registered User hottiefee's Avatar
    Join Date
    Oct 2010
    Location
    TN, USA
    Posts
    32
    How will I know what f(x) is if the user only enters the number to find the nth root of and n (the degree of the root)?

  9. #9
    -bleh-
    Join Date
    Aug 2010
    Location
    somewhere in this universe
    Posts
    452
    What do you mean?
    In this type of program, the user must provide the functions for f(x) and f'(x).

    Edit: i think i know what you meant. That's why I gave you that function prototype as a hint. that function take in the value of x, the value of the root n, and the value of c. there is only one version of f(x) that you need for this problem
    Code:
    f(x) = x^n - c;
    Last edited by nimitzhunter; 02-13-2011 at 08:56 PM.
    "All that we see or seem
    Is but a dream within a dream." - Poe

  10. #10
    Registered User hottiefee's Avatar
    Join Date
    Oct 2010
    Location
    TN, USA
    Posts
    32
    Thats what I thought but the end of the instructions said test your program on sqroot(2) 3rd root(7) and 3rd root(-1)... I just asked my professor because that didn't make sense to me.

  11. #11
    -bleh-
    Join Date
    Aug 2010
    Location
    somewhere in this universe
    Posts
    452
    so for example, 3rd root(7)
    n = 3
    c = 7
    your function in the Newton's method become:
    Code:
    x -= -f(x,3,7)/f_prime(x,3,7);

    So, maybe you didn't get what Newton's method does. Using the example above, you want to estimate x=7^(1/3) (or 3rd root of 7).
    I can cube both sides to get x^3 = 7. Then if I substract both side by 7, we'll get x^3-7=0. So you need to find an x that satisfis that condition x^3-7=0, which is equilvalent to find a root of a function. So for any x that satifises x^3-7=0, x=7^1/3. So instead of using local linear approx on 3rdroot of 7, you iterater on f(x)=x^3-7.
    Last edited by nimitzhunter; 02-13-2011 at 09:16 PM.
    "All that we see or seem
    Is but a dream within a dream." - Poe

  12. #12
    Registered User hottiefee's Avatar
    Join Date
    Oct 2010
    Location
    TN, USA
    Posts
    32
    Alright I think I get it. I'll work on it some more... I'll let ya know how it goes tomorrow prob.

  13. #13
    Registered User hottiefee's Avatar
    Join Date
    Oct 2010
    Location
    TN, USA
    Posts
    32
    Thanks.

  14. #14
    Registered User hottiefee's Avatar
    Join Date
    Oct 2010
    Location
    TN, USA
    Posts
    32
    Okay I think I have everything done, but how do you set a tolerance? Like I have to set a tolerance of 10^-6 (6 decimal places). Would it be like:
    Code:
    #define TOLERANCE 10^-6
    ? That's what I tried but I couldn't get it to work. I'll post the code I have now...

    Code:
    #include<iostream>
    #include<cmath>
    
    void getInitGuess(double&);
    double f(double, int, int);
    double fPrime(double, int, int);
    void findRoots(double&, int, int);
    using namespace std;
    int main(){
    	double root, guess;
    	int c, n;
    
    	cout << "Enter the number to find the nth root of: ";
    	cin >> c;
    	cout << "Enter n (the degree of the root): ";
    	cin >> n;
    
    	findRoots(guess, n, c);
    
    	root = guess;
    	cout << "The " << n << " root of " << c << " is: " << root << endl;
     
    	return 0;
    }
    
    void getInitGuess(double& guess){
    	cout << "Enter your initial guess: ";
    	cin >> guess;
    }
    
    double f(double x, int n, int c){
    	double fx;
    
    	fx = pow(x, n) - c;
    
    	return fx;
    }
    
    double fPrime(double x, int n, int c){
    	double fp;
    
    	fp = n * pow(x, (n-1));
    
    	return fp;
    }
    
    void findRoots(double& x, int n, int c){
    	double TOLERANCE = .000001;                       //Here is where I defined tolerance, but is this right?
    	x = 0;
    	for(int i=0; i < TOLERANCE; i++){
    		x -= (f(x, n, c) / fPrime(x, n, c));
    		if(abs(x) <= TOLERANCE)
    			break;
    	}
    }
    When I run it as it is, this happens:
    -------
    Enter the number to find the nth root of: 2
    Enter n (the degree of the root): 2
    The 2 root of 2 is 1.#INF

    The answer is the same for 3rd root of 7 and 3rd root of -1

    What is #INF? How could I fix this? I think this is all I'm lacking now.
    Last edited by hottiefee; 02-14-2011 at 06:52 PM. Reason: needs more details

  15. #15
    -bleh-
    Join Date
    Aug 2010
    Location
    somewhere in this universe
    Posts
    452
    Code:
    for(int i=0; i < TOLERANCE; i++
    should be
    Code:
    for(int i=0; i < 100; i++
    Also;
    Code:
    void findRoots(double& x, int n, int c){
    	double TOLERANCE = .000001;                       //Here is where I defined tolerance, but is this right?
    	x = 0; // GET RID OF THIS LINE;
    Last edited by nimitzhunter; 02-14-2011 at 07:08 PM.
    "All that we see or seem
    Is but a dream within a dream." - Poe

Page 1 of 3 123 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Newton's Method for Systems of Nonlinear Equations
    By Delia in forum C Programming
    Replies: 1
    Last Post: 11-10-2010, 06:17 PM
  2. Packet Container Class
    By ChaoticXSinZ in forum C++ Programming
    Replies: 2
    Last Post: 11-01-2010, 12:07 AM
  3. on method pointers and inheritance
    By BrownB in forum C++ Programming
    Replies: 2
    Last Post: 03-02-2009, 06:50 PM
  4. Cubic Root by Newton's Iterative Method
    By amirahasanen1 in forum C++ Programming
    Replies: 2
    Last Post: 03-15-2005, 01:05 PM
  5. Newton's method
    By Cmuppet in forum C Programming
    Replies: 5
    Last Post: 10-19-2004, 11:02 AM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21