Newton's method

The goal is to use Newton's method in order find the zero of a function. So in the end I want my program to look somewhat like:

1
2
3
4
f(x)
f'(x)
initial value close to 0
number of times it took to get zero 


In my case I have the function: 6x^5-5x^4-4x^3+3x^2


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
  #include <iostream>
#include <cmath>
using namespace std;

double function(double x) {
	6 * pow(x, 5) - 5 * pow(x, 4) - 4 * pow(x, 3) + 3 * pow(x, 2);
}

double derivative(double x) {
	30 * pow(x, 4) - 20 * pow(x, 3) - 12 * pow(x, 2) + 6 * x;
}

double newtons(double f, double df, double x0, double e) {
	//newtons method
}

int main() {
	cout << "f(x) = 6x^5-5x^4-4x^3+3x^2" << endl;
	cout << "f'(x) = 30x^4-20x^3-12x^2+6x" << endl;

	return 0;
}


I'm stuck. I'm not sure where to go from here. I'm not even sure if I am declaring the polynomial right
Last edited on
Edit: With a little googling, a simple polynomial class can be created in about 130 lines:
https://www.daniweb.com/programming/software-development/code/217091/simple-polynomial-class
This class does not take care of all the complexities that should be considered, but it's good enough if you don't want to drive yourself insane.

I saw that some people used linked lists which might be a way to get the exponent to accept more complexities if needed.
Last edited on
You would need to pass f(x) and f'(x) functions as function pointers to your newtons() function.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
using fx = double(*)(double);

double newtons( fx f, fx df, double x0, double e ) 
{
    double x1{};
    while( true ) {
        x1 = x0 - f( x0 ) / df( x0 );
        
        if( std::abs( x1 - x0 ) <= e ) break;
        
        x0 = x1;
    }
    
    return x1;
}


Make sure to return in your f(x) and f'(x) functions.
1
2
3
4
5
6
7
8
9
double function( double x ) 
{
    return 6 * std::pow( x, 5 ) - 5 * std::pow( x, 4 ) - 4 * std::pow( x, 3 ) + 3 * std::pow (x, 2 );
}

double derivative( double x ) 
{
    return 30 * std::pow( x, 4 ) - 20 * std::pow( x, 3 ) - 12 * std::pow( x, 2 ) + 6 * x;
}


Example usage:
1
2
3
4
5
6
7
8
9
10
11
int main() 
{
    std::cout << "f(x) = 6x^5-5x^4-4x^3+3x^2\n";
    std::cout << "f'(x) = 30x^4-20x^3-12x^2+6x\n";
    
    constexpr int dec_places{ 5 };
    constexpr double precision{ std::pow( 10, -dec_places ) }, initial_guess{ 0.6 };
    std::cout << "root found at x = " 
              << std::fixed << std::setprecision( dec_places ) 
              << newtons( function, derivative, initial_guess, precision ) << '\n';
}


f(x) = 6x^5-5x^4-4x^3+3x^2
f'(x) = 30x^4-20x^3-12x^2+6x
root found at x = 0.62867
You should start slowly.

First of all, test your function and its derivative. At the moment, the only thing wrong with them is that they don't return anything. That's the word ... return. Send them a value of x from main and get them to work out the polynomial and its derivative. Print them out in main() and check them on a calculator.

I slightly baulk at giving the name 'function', since it is a keyword in so many programming languages. However, let that be for now. There are also better ways of working out polynomials than a sequence of pow() evaluations. However, again, that is less important for now.


Once you have your function (f) and its derivative (f ') working then you can move on to Newton's method. It only needs a starting value (x or x0) which you can pass as an argument. You might pass an error tolerance (e) or set it in the function itself - up to you. The function will involve a loop which keeps replacing x by
x - f(x) / f'(x)
and you can use your function and its derivative to work this out. Incidentally, there is no necessity to pass pointers to these functions as parameters - they are in the same programming unit, so perfectly well known to your newtons function. You need a loop stopping criterion, which is usually something like
(abs(f(x)) < e ) OR (number of iterations reaches a maximum)
The method isn't guaranteed to work, so you will need the second condition as well. While developing the method you could just get it to do a fixed number of loops instead, just to test that everything else is working.

The function needs to return the final value of x, either as a reference parameter of the function or the value of the function itself - your choice. Actually, during initial development it is not crucial that you have a separate newtons function - you could get this part running in main() first.

Develop your code incrementally. Don't expect to write the whole thing at once and then go through a painful debugging stage.
Last edited on
Topic archived. No new replies allowed.