From: allen_abrahamson@my-deja.com Subject: Re: best polynomial fit Date: Wed, 20 Sep 2000 03:44:37 GMT Newsgroups: sci.math.num-analysis Summary: [missing] In article <39C5F71B.6024FAB4@natlab.research.philips.com>, C.I.Softley@ncl.ac.uk wrote: > David Mehringer wrote: > > > > Hi, > > I was wondering if someone could help me with the following problem. > > > > I have N (x,y) data points to which I want to fit polynomial of degree A > > (obviously A < N). > > [snip] > A simpler approach to finding the almost-minimax polynomial is > to find a polynomial in terms of Chebyshev polynomials > which interpolates all of > your data points, then throw away however many high-order terms until > you have the degree of polynomial you want. If you want a > straightforward polynomial, rather than one in terms of Chebyshev > polynomials, it's possible to do that conversion. Maple can also do > this, but the reason I'm mentioning it is that source code for this, as > well as source code for least-squares fitting, can be found in the > 'Numerical Recipes' books. The 'C' and FORTRAN incarnations of these are > available online at http://lib-www.lanl.gov/numerical/ Finally, somebody in this thread suggests orthogonal polynomial fitting! (Apologies, there was one off-hand mention somewhat earlier). The _Numerical Recipes_ discussion is quite clear in the "how". They even go so far as to state flat out: never fit with polynomials. But may I suggest the "why" polynomial fitting in high degree is doomed if there is any noise in the data, and why orthogonal methods will hold a curve's shape? (Of course, this is a rhetorical question; I'm going to in any case :-) Ultimately, curve fitting methods solve a linear system; with polynomial coefficients being the "unknowns". The "columns" of the data matrix are the successive powers of the abscissa values. Make up a simple example, put N (20 or 50 or 100) integers in a spreadsheet column, their squares in the next column, their cubes next, etc. Check the correlations between the columns: all are well above 0.9. If this is X, and the solution entails X'X, the matrix is exceedingly ill conditioned, and any noise on the other side will be greatly amplified in the resultant polynomial coefficients. And a little noise in a high coefficient can translate to a lot of wriggle. On the other hand, columns of successive order othogonal polynomials' values for the abscissa values (transformed to the [-1,1] interval of the Chebychev and Legendre polynomials) will tend to have very low colinearity, the numerical reflection of the pairwise products integrating to zero under some weight function. This results in a much higher condition for the solution's matrix. In passing, this is also an argument for using Legendre, rather than the minimax Chebychev polynomials, in empirical situations; the former's weight function is unity, and the solution system's condition is often better. So it is the preservation of the condition of the solution, as much or more than the minimax property, that makes orthogonal polynomial fitting a vastly superior methodology over simply fitting to successive powers of the abscissa. I'm also surprised there has not been one word about splines. But that's another topic. Sent via Deja.com http://www.deja.com/ Before you buy.