Newton's Method to find polynomial solution

[mochiboo5]

Hi everyone,

this is my first post and I am new to C++. I am trying to figure out how to do this project. Newton’s method is an algorithm that can be used to solve an equation of the form f(x) = 0 using a sequence of approximations. Here’s how it works: You make a reasonable guess for a solution, x0.
You should create a function which calculates the value of the polynomial at a specific x value (the inputs for the function should be the array representing the polynomial, its size, and the x-value to evaluate at), and a function which calculates the value of the derivative at a specific x value (same inputs as the previous function).
I have been trying to figure this out for 4 hours already but can't go past cout statements. Please help! this is urgent!

[DavidB]

This question would have been more appropriate in the "Software Development"->"Computer Science" section of these forums.

What, exactly, don't you get? The algorithm itself? The C++ coding part of the problem? . . .

Why don't you post what you have done so far, and we'll try to help you from there.

[mochiboo5]

#include<iostream>
#include<cmath>
using namespace std;


double Newtonf(double[], int);
double Newtonf(double polynomial[], int order)
    {
        double b;
        double constant;
        double total;
        double x;
    for(int b=1; b<=order; b++)
        {
            total+=polynomial[b]*pow(x, b)+ constant;
            return total;
        }




    }


double Newtonfd(double[], int);
double Newtonfd(double polynomial[], int order)
    {
        double b;
        int c;
        double total;
        double x;
    for(int b=1; b<=order; b++)
        {
            total+=polynomial[b]*c*pow(x,c-1);
            return total;
        }
    }

int main()
{

    double guess;
    int n;
    cout << "What is the degree of the polynomial equation of the form f(x)=0? ";
    cin >> n;
    int i=1;
    double polynomial[n];

    while(i<=n)
    {
        cout << "Enter the coefficient of the x^" << i << " term: ";
        cin >> polynomial[n-1];
        i++;
    }
    double constant;
    cout << "Enter the constant term: ";
    cin >> constant;

    cout << "Enter a guess for the solution: ";
    cin >> guess;

    cout << Newtonf(polynomial, n) << endl;
    cout << Newtonfd (polynomial, n) << endl;






    system ("pause");
    return 1;
}

thank you for a quick reply!
I am sure how to compose the function in C++ and the function for the derivative.
here is what I have done so far and not sure if it makes sense

[mochiboo5]

I meant I am NOT sure to compose the functions correctly

[ravenous]

This is not directly related to your question, but it will make things easier for you.

From your code, it looks like you're representing your polynomial in the order that it's typically written down, e.g.

a*x^3 + b*x^2 + c*x + d

This is fine, but it's easier to work with if you represent it the other way around, i.e. with the lowest order coefficients and the lowest index in your array. So, something like:

double polynomial[] = { -1, 3, 0, 4 };

would represent the polynomial

4x^3 + 3x - 1

Using this method, when you want to evaluate the polynomial, you just loop over the components like this:

size_t order = 3;
double result = 0;
double x = 3.212313;  // A random position to evaluate the polynomial at
for ( size_t i = 0; i < order + 1; ++i )
    result += polynomial[ i ] * pow( x, i );

std::cout << "f(" << x << ") = " << result << std::endl;

There's actually a better way to evaluate a polynomial called Horner's method, but I'll leave that up to you to read about.

If you wanted to go the whole hog, it would be prefereable to make a simple polynomial class that encapsulates the idea of a evaluating a polynomial. Maybe an interface like:

class Polynomial
{
public :
    /// Construct from a vector of coefficients
    Polynomial( const std::vector< double >& coeffs );

    /// Get the value at a specified position
    double Evaluate( double x ) const;

    /// Get the value of the nth derivative
    double EvaluateDerivative( double x, size_t n = 1 ) const;

    /// Get the value of the ith coefficient
    double GetCoefficient( size_t i ) const;
};

I'll let you think about how you might implement this interface :o)

[mochiboo5]

Thank you! We talked about classes briefly but havent learnt them yet. :(

Maybe you need to use numerical methods to calculate the derivative.

Especially if your function contains sin or cosine functions. There's no way you can be expected to write a program to handle those... Exception being you know you will be only given simple functions.

So

http://stackoverflow.com/questions/1559695/implementing-the-derivative-in-c-c

is probably your best bet.I'm more inclined to believe this is what you need to do especially if you haven't cover classes yet.

Best just to be sure and ask your teacher, s/he should point you in the right direction.

Failing that for simple functions click on my username and go to code snippets. I wrote a simple polynomial differential function which extends on the method outlined by ravenous.

[DavidB]

(Assuming you are dealing just with polynomial functions)

A couple suggestions.

C++ array indexing starts at 0.
From line 49, you have input the coefficients of the polynomial starting at polynomial[1], and then a few lines down you assign the constant term to a separate variable, constant.
Why not just assign it to polynomial[0].
Then you'd have all the coefficients in a single array and everything later could be dealt with more smoothly:

a0 * x^0 + a1 * x^1 + a2 * x^2 + a3 * x^3 + . . .

Then,
polynomial[0] = a0, which is the constant,
polynomial[1] = a1,
polynomial[2] = a2,
polynomial[3] = a3,
. . .

And you know that the array index corresponds to the power of x for a particular term (e.g. - polynomial[2] corresponds to the term for which the power of x is 2, etc.).
Having this connection makes things a lot easier.

In Newtonf, you define b twice, as a double, and in the loop as an array index. You should only need it once. You define c but don't use it.

In Newtonfd, you define c, and use it, but don't initialize it.

And you don't pass 'x' into either function. You need to pass in the x-point at which you want each function to be evaluated.

You know the derivatives of a polynomial are simply n * an * x^(n-1), where n is the power of the term.

Then
poly_der[0] = 0.
The rest of the entries of poly_der could be computed in a simple loop (where 'i' is the loop index):
poly_der[i] = i * ai * x^(i-1)

Beyond that, it is a staightforward application of Newton's Method. Do you know how to do that?