Need to fit polynomial using chebyshev polynomial basis

I think you are looking for the Chebfun toolbox. It overloads, amongst others, the polyfit function using Chebychev points and Chebychev interpolants.

Next to the above, you can always code this yourself. It is not that difficult. EDIT: See the post of mathematician1975 :). EDIT2: updated chebfun website.

I will assume here that you want Chebyshev polynomials of the first kind. As far as I know, Matlab does not have this inbuilt. It is easy to code yourself though. Chebyshev polynomials are only defined on [-1,1] so first you must map your x data to this range. Then use the recurrence relation for generating Chebyshev polynomials http://en.wikipedia.org/wiki/Chebyshev_polynomials#Definition

T_(n+1)(x) = 2xT_(n)x - T_(n-1)(x)

If x are your abscissae and y your data points generate your observation matrix A (this is the equivalent of the Vandermonde matrix for monomial basis) for a degree n polynomial fit using:

n = degree;
m = length(x);
%% Generate the z variable as a mapping of your x data range into the 
%% interval [-1,1]

z = ((x-min(x))-(max(x)-x))/(max(x)-min(x));

A(:,1) = ones(m,1);
if n > 1
   A(:,2) = z;
end
if n > 2
  for k = 3:n+1
     A(:,k) = 2*z.*A(:,k-1) - A(:,k-2);  %% recurrence relation
  end
end

then you can just solve the linear system for your solution parameters (approximation coefficients) b using matrix divide

b = A \ y

What you have to remember here is that when you evaluate your approximation you must map the value to the interval [-1,1] before evaluating it. The coefficients will only be valid on the initial range of x you provide for the approximation. You will not be able to evaulate the approximation (in a valid sense) outside of your initial x range. If you want to do that you should use a wider interval than your data has, that way when you map points interior to that using the transform, your points will always lie in [-1,1] and therefore evaluation of your approximation is valid.

I have not used matlab for a while so new versions may actually have an inbuilt function that will do all of this for you. It was not the case when I last used it and if all else fails the above will allow you to generate least-squares polynomial approximations using chebyshev basis (first kind)