Notes Re. Best Fit Program

1) Contains useful functions

Matrix manipulation functions ludcmp and lubksb for LU decomposition and
backsubstitution. These can be used to solve matrix equations and, if
you know how, to find an inverse matrix. I gratefully acknowledge the
inspiration of Numerical Recipes and recommend that you should get the
book which explains all this much better than I can.

I have used ludcmp and lubksb within function matsolve which is a pretty
useful general matrix solver. I have got good results with it for up to
about 81x81 matrices but be warned that it can fail for ill-conditioned
equations.

2) How the Best Fit program works

given a list of points x(1..n) and y(1..n)

find best fit coefficients c[1..m]

for the best fit equation y(x)=c[1]*f1(x)+c[2]*f2(x)..

such that the sum of the (y_errors squared), is minimised

For a polynomial curve fit f1(1)=1, f2(x)=x^1 .. fm(x)=x^(m-1)

Each data point produces a row in the matrix equation:-

[x].[c] = [y]

where [x] (for 3 coefficients and n data points) is:-

1 x[1] x[1]^2
1 x[2] x[2]^2
1 x[3] x[3]^2
..
1 x[n] x[n]^2

[y] is:-

y[1]
y[2]
y[3]
..
y[n]

[c] is the vector of coefficients

In the above [x] means the matrix of x values and x[i] means x subscript
i as in awk notation. [y] is the vector of y values.

To find the best fit (least square) solution premultiply by the transpose 
of [x] and solve the matrix equation. (I state this recipe without proof. 
You're going to have to either trust me or see Numerical Recipes)

[x].[c] = [y]

becomes:-

[x]'.[x].[c] = [x]'.[y]

In the above "." is a standard matrix multiply operation and suffix "'"
means transpose.

This makes the product matrix [x]'.[x] square, reduces the size of the
matrices to the size of [c] and gives the least square solution. I used
to be able to prove it but it would give me a headache to repeat the
feat now.

premultiply both sides by [x]' giving:-

| n        sum(x)   sum(x^2) | x | c[1] | = | sum(y)     |
| sum(x)   sum(x^2) sum(x^3) |   | c[2] |   | sum(y*x)   |
| sum(x^2) sum(x^3) sum(x^4) |   | c[3] |   | sum(y*x^2) |

I solved this by LU decomposition and backsubstitution without
explicitly calculating an inverse matrix.

The decomposition function uses pivoting to improve accuracy.


3) How to specify the model equation used in the best fit program.

This involves changing the first block of the program but I think
it is fairly obvious what you need to do. I start with a 3 coefficient 
polynomial and then discuss how to specify alternatives.

#-----------------------------------------------------------------------
#best fit

NF==2 && isnum($1) && isnum($2) {
  n++
  x   =$1
  y[n]=$2

  #change the following lines to define the form of curve fit
  m=0
  f[n,++m]=1
  f[n,++m]=x
  f[n,++m]=x^2

}

# leave the program unchanged from here on ...
#-----------------------------------------------------------------------

Input data:-

Best fit test data: y(x) = 1-x/2+x^2/3
  0.000000  1.000000
  0.100000  0.953333
  0.200000  0.913333
  0.300000  0.880000
  0.400000  0.853333
  0.500000  0.833333
  0.600000  0.820000
  0.700000  0.813333
  0.800000  0.813333
  0.900000  0.820000
  1.000000  0.833333

Results:-

>awk95 -f bestfit2.awk bestfit2.dat
Best Fit using 3 coefficients

coeff[1] = +0.99999985
coeff[2] = -0.50000029
coeff[3] = +0.33333357

errors: rms= 1.57862e-007 , min= -2.39161e-007 , max= 1.59441e-007

So this is saying that the best fit curve is:-

y(x)= 0.99999985-0.50000029*x+0.33333357*x^2

Which is better expressed as:-

y(x)= 0.99999985+x*(-0.50000029+x*0.33333357)

The coefficients differ slightly from the ideal values of 1, -1/2 
and 1/3 mainly because the input data is rounded to 6 decimal places.


Now suppose you know that the first coefficient should be 1 exactly and
you want to find the coefficients of x and x^2.

y(x) = 1 + c[1]*x + c[2]*x^2

Move the 1 to the left hand side:-

y(x) - 1 = c[1]*x + c[2]*x^2

Change the program to solve this problem:-

NF==2 && isnum($1) && isnum($2) {
  n++
  x   =$1
  y[n]=$2-1

  #change the following lines to define the form of curve fit
  m=0
  f[n,++m]=x
  f[n,++m]=x^2

}

Results:-

>awk95 -f bestfit2.awk bestfit2.dat
Best Fit using 2 coefficients

coeff[1] = -0.50000085
coeff[2] = +0.33333401

errors: rms= 1.68221e-007 , min= -2.6747e-007 , max= 2.54984e-007


Now suppose you want to do a Fourier series best fit of the form

y(x) = c[1]+c[2]*cos(x)+c[3]*sin(x)+c[4]*cos(2*x)+c[5]*sin(2*x)

The first block of the program becomes:-

#-----------------------------------------------------------------------
#best fit

NF==2 && isnum($1) && isnum($2) {
  n++
  x   =$1
  y[n]=$2

  #change the following lines to define the form of curve fit
  m=0
  f[n,++m]=1
  f[n,++m]=cos(x)
  f[n,++m]=sin(x)
  f[n,++m]=cos(2*x)
  f[n,++m]=sin(2*x)

}

# leave the program unchanged from here on ...
#-----------------------------------------------------------------------

Using the same data file as before the results are :-

>awk95 -f bestfit2.awk bestfit2.dat
Best Fit using 5 coefficients

coeff[1] = +1.6750451
coeff[2] = -0.68171785
coeff[3] = -0.62967319
coeff[4] = +0.0066650255
coeff[5] = +0.065164063

errors: rms= 8.77821e-006 , min= -1.19356e-005 , max= 1.58136e-005


Similarly the program is easily adapted to calculate Chebyshev series,
Fourier series, y(x)=sqrt(polynomial), y(x1,x2) = a function of two
variables etc.

-- 
Alan Linton 20th February 2001
alan@cranley.demon.co.uk
