Thread: 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.

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; 
}

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.

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)

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;

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.

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.

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;