Simplified Polynomial in C++

Allen04 (10)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
#include <iostream>
using namespace std;
int main()
{
    float y[4] = { 12, 13 , 14 , 16 };
    float x[4] = { 5, 6, 9, 11 };

    //Interpolating Polynomial
    cout << "\n***************************" << endl;
    cout << "Interpolating Polynomial" << endl;

    cout << y[0];
    for (int i = 1; i < 4; i++)
    {
        cout << showpos << y[i];
        for (int j = 0; j < i; j++)
        {
            cout << "(x" << showpos << -x[j] << ")";
        }
    }
    cout << "\n***************************" << endl;

    //Simplified Polynomial
    cout << "\n***************************" << endl;
    cout << "\n***************************" << endl;

    system("pause");
}


Can anyone help me in the Simplified Polynomial part?.
My text file is:
1 1.5 0 2
3 3.25 3 1.667

My expect output is:
Interpolating polynomial is:
3 + 1/2(x-1) +1/3(x-1)(x-3/2) - 2(x-1)(x-3/2)x
Simplified polynomial is:
-2x^3 + 5.334x^2 – 3.334x + 3
Last edited on
lastchance (6980)
First of all, that isn't an "interpolating" polynomial (the sort of thing you would get from Lagrange interpolation).

Secondly, there's no way that second polynomial is the multiplied-out form of the first. The coefficient of x^3 would be 16, for example, and all coefficients would be whole numbers. EDIT: OP has changed his post

State your actual assignment: if you are after Lagrange interpolation then you are doing it wrong.
Last edited on
Allen04 (10)
I did interpolating polynomia in my full code. I can't upload my full code here so I just tried to get a part of it for my example to get helped.

Actually, I've completed the Newton's Divided Difference Table, the Interpolating Polynomials, but I'm sticking on how to convert Interpolating Polynomials into Simplified Polynomials,
lastchance (6980)
If you NEED to multiply it out then you probably ought to develop a simple polynomial class, able to do addition and multiply.

However, most of the interpolation methods don't need multiplying out: they are more efficient to use in their original form.

And in the example that you give, the intended output is NOT the multiplied-out form of the first polynomial. (You appear to have omitted the actual numerical values of the Newton differences.) EDIT: OP has now changed his post.
Last edited on
Allen04 (10)
I know most of the interpolation methods don't need multiplying out but all I have to do is print out Newton's Divided Difference Table, Interpolating Polynomials, and Simplified Polynomials. That's why I need to multiply+ out. I just edited my code above. Can you help me in the Simplified Polynomial part please?
lastchance (6980)
EDIT: Oh dear, you've changed your initial code YET AGAIN!

Try for the last part (on one of the previously posted parts of your code)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
    //Simplified Polynomial
    cout << "\n***************************" << endl;
    cout << "Simplified Polynomial" << endl;
    vector< vector<float> > p(size, vector<float>( size, 0 ) );   // p[i][j] is the ith polynomial
    vector<float> c(size, 0 );                                    // c[j] holds coefficient of x^j
    p[0][0] = 1;
    for ( int i = 1; i < size; i++ )
    {
       p[i][0] = -x[i-1] * p[i-1][0];
       for ( int j = 1; j <= i; j++ ) p[i][j] = p[i-1][j-1] - x[i-1] * p[i-1][j];
    }
    for ( int j = 0; j < size; j++ )
    {  
       for ( int i = 0; i < size; i++ ) c[j] += y[0][i] * p[i][j];
    }
    for ( int j = size - 1; j >= 0; j-- )
    {
       cout << showpos << c[j];
       if ( j > 0 ) cout << noshowpos << "x^" << j;
    }
    cout << "\n***************************" << endl;
Last edited on
lastchance (6980)
Try this one:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
 
#include <iostream>
#include <vector>
using namespace std;


//======================================================================


vector<double> getNewton( const vector<double> &x, vector<double> f )          // Gets Newton polynomial
{
   int N = x.size();
   vector<double> c(N), temp(N);

   c[0] = f[0];
   for ( int i = 1; i < N; i++ )       // Compute ith differences
   {
      for ( int j = 0; j < N - i; j++ ) temp[j] = ( f[j+1] - f[j] ) / ( x[j+i] - x[j] );
      f = temp;
      c[i] = f[0];
   }
   return c;
}


//======================================================================


vector<double> standardPolynomial( const vector<double> &c, const vector<double> &x )    // Multiplies out Newton polynomial
{
   int N = x.size();
   vector<double> a( N, 0.0 );                   // a[j] holds coefficient of x^j in final sum
   vector<double> p(N), prev(N);                 // At the ith step, p[ ] is the ith polynomial of Newton factors
                                                                 
   p[0] = 1;
   a[0] = c[0] * p[0];
   for ( int i = 1; i < N; i++ )
   {
      prev = p;
      p[0] = -x[i-1] * prev[0];
      a[0] += c[i] * p[0];
      for ( int j = 1; j <= i; j++ ) 
      {
         p[j] = prev[j-1] - x[i-1] * prev[j];
         a[j] += c[i] * p[j];
      }
   }

   return a;
}


//======================================================================


void writeNewtonPolynomial( const vector<double> &c, const vector<double> &x )
{
   int N = x.size();
   cout << c[0];
   for ( int i = 1; i < N; i++ )
   {
      cout << showpos << c[i];
      for ( int j = 0; j < i; j++ ) cout << "(x" << showpos << -x[j] << ")";
   }
   cout << '\n';
}


//======================================================================


void writeStandardPolynomial( const vector<double> &a )
{
   int N = a.size();
   cout << a[0];
   for ( int i = 1; i < N; i++ ) cout << showpos << a[i] << "x^" << noshowpos << i;
   cout << '\n';
}


//======================================================================


double evaluateNewtonPolynomial( const vector<double> &c, const vector<double> &x, double xval )
{
   int N = c.size();
   double result = c[0], poly = 1.0;
   for ( int i = 1; i < N; i++ )
   {
      poly *= ( xval - x[i-1] );
      result += c[i] * poly;
   }
   return result;
}


//======================================================================


double evaluateStandardPolynomial( const vector<double> &a, double xval )
{
   int N = a.size();
   double result = a[N-1];
   for ( int i = N-2; i >= 0; i-- ) result = a[i] + xval * result;
   return result;
}


//======================================================================


int main()
{
   vector<double> x = { 1, 2, 3, 4 };
   vector<double> y = { 6, 9, 2, 5 };

   vector<double> c = getNewton( x, y );
   vector<double> a = standardPolynomial( c, x );

   cout << "Newton polynomial:   ";   writeNewtonPolynomial( c, x );
   cout << "Standard polynomial: ";   writeStandardPolynomial( a );

   double test = 2.5;
   cout << "Interpolate for x = " << test << '\n';
   cout << "Newton:   " << evaluateNewtonPolynomial  ( c, x, test ) << '\n';
   cout << "Standard: " << evaluateStandardPolynomial( a,    test ) << '\n';
}


Newton polynomial:   6+3(x-1)-5(x-1)(x-2)+3.33333(x-1)(x-2)(x-3)
Standard polynomial: -27+54.6667x^1-25x^2+3.33333x^3
Interpolate for x = 2.5
Newton:   5.5
Standard: 5.5
Last edited on
Topic archived. No new replies allowed.