Overdetermined system of equations - 8 degree polynomial

I manually generate an arbitrarily eight degree polynomial, i.e. I know the coefficient of the curve. Next, I added some random data point (noise) around this curve. Now, I want to reverse the problem and get "almost" the same curve by (estimating 9 unknown coefficient of the curve) solving a set of overestimated system of equations in least square manner (let's say 10000 data point which means 10000 equations). I used X=A\B command. This works perfectly for example for 2 degree polynomial. But for the case of eight degree, it does not return back nine correct coefficients of the curve. The return curve is not close to the main curve at all. Given the fact that equations are linear, is this an inherent problem of matlab?! Do you have any suggestions?

Answer 1

[dpb]

" is this an inherent problem of matlab?!"

Yes, but it's not really Matlab, per se, but computational numerics with FP arithmetic. Using such high-order polynomials is bound to cause difficulties without extreme measures taken to counteract.

"Do you have any suggestions?"

Yes, do NOT try to do this -- if you want/need an interpolating polynomial to go thru specific points, use a spline or other interpolating method more suitable instead of high-order polynomials.

If you're adamant that you're bound and determined to proceed anyway, you can try standardizing the independent variables and see if that will help the numerics sufficiently. Not guaranteed, and may work on some cases and still fail miserably on others, depending on just what the values are.

Answer 2

[Bruno Luong]

If you rescale your data, making for example x coordinates between (-1,1) it might hep to get a better condition linear system.

Also you should use POLYFIT rather than doing you own linear algebra.

And third advise is what dbp says, reduce the order. IMO something more than degree 6 will not do well. Use other model such as SPLINE fitting if you want to have better fit by a more flexible model rather than go higher polynomial degree.

Answer 3

[Walter Roberson]

"Given the fact that equations are linear, is this an inherent problem of matlab?!"

It is inherent in using finite precision to find roots of a polynomial. See https://en.wikipedia.org/wiki/Wilkinson%27s_polynomial

Note that the equations are not linear: linear requires degree 0 or 1 for each term of the equation.

[Bruno Luong]

Fitting polynomial problem has nothing to do find finding ROOTS problem.

[Walter Roberson]

polyfit creates the vandermode matrix and uses \ . In the overdetermined case that would be nonsquare, so qr decomposition would be used. qr decomposition is an eigenvalue algorithm. eigenvalues are mathematically equivalent to finding the roots of the characteristic polynomial. Therefore there is a mathematical relation between fitting polynomials and finding roots.

Now it is perhaps the case that the projection between similar but not identical inputs through to the matrix for eigenvalue calculations is such that the kinds of instabilities discussed for the Wilkinson polynomial cannot occur, but that would be a different question.

[Bruno Luong]

"qr decomposition would be used. qr decomposition is an eigenvalue algorithm"

Sorry Walter, but this is again wrong.

1. Firstly: Poly fitting use QR just to solve linear system, something that you denies in your post.
2. Secondly: QR algorithm is carried out either successive by GIVENS's transformation or HOUSHOLDER's transformation. QR is not eigen value problem.*QR factorization can applied on any matrix, even one that do not have eigen values.Note that the opposite is true, *some eigen value algorithm might use QR succesively.