Version 0 of Polynomial fitting

Updated 2004-04-05 06:43:14

Arjen Markus (3 april 2004) Knowing orthogonal polynomials like the Legendre family and others, and having played a bit with discrete Fourier transforms (see Discrete Fourier Transform) I thought I would try an analoguous technique polynomials.

There is one practical difference with discrete Fourier transforms: it is difficult (but not impossible) to write down closed formulae for the polynomials to be used. I started with:

  • The nodes or auxiliary points are x = k/N (where k = -m, -m+1, ..., m-1, m, N=2m+1,

and similar - but different for even N)

  • The poynomials must be orthogonal in the sense that the sum
       m
      Sum   Pi(x)*Pj(x) = 0,   if i != j
      k=-m
  • The first two are simple:
    P0(x) = 1
    P1(x) = x
  • The third becomes troublesome already because you have to distinguish between even and odd N.

So, I decided to give up on this analytic approach and instead use a practical (numerical) one:

  • I try to fit N data points
  • The nodes for the polynomials are x = k, k=1,N
  • The polynomials that I want to fit with are determined "on the fly", using a simple Gram-Schmidt orthogonalisation process and subsequent normalisation.
  • Due to the orthogonality the fitting of the data becomes almost trivial, just as with the discrete Fourier transform.

(Improvements:

  • Reduce the overhead of double computations - certain intermediate results are computed more than once
  • The toString procedure does not take care of minus signs - I overlooked that possibility and was too lazy to repair that. Probably the best solution is to modify the string afterwards.)