Polynomial Lagrange Function to get the correct coefficients

Question

My aim is to create a polynomial with given coefficients, then evaluate the polynomial on giving points. and then use PolynomialFunctionLagrangeForm class to recreate the same polynomial and retrieve the same coefficients.

However, I'm getting different coefficients even that both polynomials have the same degree.

My question is how to get the same coefficients ? is there a way to get all possible polynomials ?

 static double [] points= {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16};
// Create polynomial using PolynomialFunction class 
PolynomialFunction pf = new PolynomialFunction(coeffecient); 
System.out.println("-------------------Encoding------------------ \nPolynomial degree: "+pf.degree());
System.out.println("Polynomial: "+pf);
System.out.println("Coffecients: ");
System.out.println(Arrays.toString(pf.getCoefficients()));
evaluatePolynomial(pf, points);
PolynomialFunctionLagrangeForm LF = new PolynomialFunctionLagrangeForm(points,polynomial_values);
System.out.print("-------------------Decoding------------------ \nDegree of     Lagrange polynomial:");
System.out.println(LF.degree());
System.out.println("Polynomial: "+LF);
System.out.println("Coffecient of Lagrange polynomial:");
System.out.println(Arrays.toString(LF.getCoefficients()));

output:

-------------------Encoding------------------ 
Polynomial degree: 15
Polynomial: 40.0 x - 53.0 x^2 - 8.0 x^3 - 29.0 x^4 + 99.0 x^5 + 71.0 x^6 -   86.0 x^7 + 127.0 x^8 + 35.0 x^9 + 14.0 x^10 - 53.0 x^11 + 121.0 x^12 - x^13 + 22.0 x^14 - 27.0 x^15
Coffecients: 
[0.0, 40.0, -53.0, -8.0, -29.0, 99.0, 71.0, -86.0, 127.0, 35.0, 14.0, -53.0, 121.0, -1.0, 22.0, -27.0]
-------------------Decoding------------------ 
Degree of Lagrange polynomial:15
Polynomial:    org.apache.commons.math.analysis.polynomials.PolynomialFunctionLagrangeForm@5f150435
Coffecient of Lagrange polynomial:
[241664.0, -196608.0, 819200.0, -360448.0, 24576.0, -81920.0, 24576.0, -256.0, 640.0, -28.0, 18.0, -52.921875, 121.021484375, -1.000274658203125, 22.000003814697266, -27.000000070780516]

Update

I should stick with the following points

 points= {34121,51152,59804,40922,41678,33985,55244,61576,41866,37365,63178,45530,52928,35006,34671,43212};

 P(x)= 37.0 + 79.0 x + 95.0 x^2 - 118.0 x^3 + 66.0 x^4 - 47.0 x^5 - 64.0 x^6 + 77.0 x^7 + 7.0 x^8 + 113.0 x^9 - 81.0 x^10 + 36.0 x^11 - 33.0 x^12 + 7.0 x^13 - 91.0 x^14 + 80.0 x^15

The result after evaluating on polynomial

 (points, P(points))= {(34121,7.914104306379832E69),(51152,3.435734636341671E72),(59804,3.5812547774323177E73),(40922,1.209012191911663E71),(41678, 1.5910403312602316E71),(33985,7.453917205941376E69 ),(55244, 1.0898275780150622E73),(61576,5.5495027051432293E73),(41866,1.702159385167097E71),(37365,3.0906623702059587E70),(63178,8.157747712897765E73),(45530,5.991614888661553E71),(52928,5.732748723914476E72),(35006,1.1620189256906411E70),(34671,1.005938101921578E70),(43212,2.736176231116627E71)};

however, send (points, P(points)) to Lagrange interpolation produce wrong coefficients:

 -7.125711012263528E27, -1.7102522454360707E26, -3.9998444109905895E24, -1.1156590815779537E23, -1.3650590614545068E21, -8.762203435012037E19, 1.36909428672063078E18, -1.125899906842624E17, 7.0368744177664E14, -2.3089744183296E13, 3.95136991232E11, -3.3554432E9, 1.572864E7, -110592.0, 192.0, 79.38.

Any suggested solution?

Do you need to call computeCoefficients() before getting them? If not, it is probably a numerical issue. What points are you feeding in? — Nico Schertler
@Nico Schertler I've added points array in the question. I did not call 'computeCoefficients()', since 'getCoefficients()' method calls 'computeCoefficients()' . Also, I cannot call 'computeCoefficients()' since it is protected. — Haya aziz
The given polynomial returns values around 10^18 at the end of your range. This is definitely a numerical issue. It might get better for reasonable input. — Nico Schertler
@Nico Schertler if points array is from 1 to 14 it gives me correct result, can you give me a reasonable input example, it should be 16 numbers. — Haya aziz
Already moving the points towards the origin (i.e. -7 to 8) should produce much better results. You can also try scaling them, e.g. -1.0, -0.9, -0.8 .... — Nico Schertler

Nico Schertler Nico Schertler · Accepted Answer · 2016-09-09T00:18:59

The problem of your example is that the polynomial yields very large values when evaluated at some of your points (mostly the larger ones), while others yield very small values. Since you use a numeric data-type with a fixed bit-depth, the details around zero may get lost due to floating-point precision.

If you examine the result of the Lagrange polynomial, you will see that the higher-order coefficients match. These are the coefficients that are responsible for the large values. If you plot this polynomial, you will hardly see a difference because the wrong lower-order coefficients introduce a very small error (compared to the large scale).

In order to solve this, you should feed in points that produce a smaller dynamic range. What points satisfy the condition depends on the input polynomial. As a general rule of thumb, values close to zero should be ok for most polynomials.

Polynomial Lagrange Function to get the correct coefficients

1 Answers