Need help understanding Remez Algorithm and Chebyshev Polynomials

[ChaseRLewis]

So I've been reading about minimax polynomial approximations and have found them to be pretty impressive. However, i am confused on exactly how to determine the constants.

The first step is supposed be solving for the Chebyshev polynomials as an initial guess. I'm reading wikipedia but I'm a bit confused on how to approximate a function with them. http://en.wikipedia.org/wiki/Chebyshev_polynomials


From there I use those factors as an initial guess into a linear system of equations
But I'm confused on exactly how to determine the error function (more refined grid?) also how do you iterate through it? Keeping adding dimension until your error criteria is met? Bit lost when I read about it. Lot's of people talking about it but almost no examples.

any code that can be linked or any questions that could be cleared up here would be much appreciated.

 

[jasonRF]

So I've been reading about minimax polynomial approximations and have found them to be pretty impressive. However, i am confused on exactly how to determine the constants.

The first step is supposed be solving for the Chebyshev polynomials as an initial guess. I'm reading wikipedia but I'm a bit confused on how to approximate a function with them. http://en.wikipedia.org/wiki/Chebyshev_polynomials

That is a good page. Section 4.3 of that wiki page lists orthogonality conditions - one in integral form and one discrete. I have used the discrete on quite a few occasions since the integrals tend to require superhuman skill. For an example of using the discrete orthogonality, consider a function $f(x)$ defined for $-1\leq x \leq 1$. We want to represent it as
$$f(x) = \sum_{\ell=0}^{\infty} a_\ell T_\ell (x).$$
We want to use the discrete orthogonality, which states that for $\ell,m<N$,
$$\sum_{k=0}^{N-1} T_\ell(x_k) T_m(x_k) = N \epsilon_{\ell,m}^\prime$$
where
$$x_k = \cos\left( \frac{\pi (k+\frac{1}{2})}{N} \right),$$
and $\epsilon_{\ell,m}^\prime$ is zero if $\ell\neq m$, one if $\ell= m=0$ and $1/2$ if $\ell= m >0$. So we have to pick an N. I would make it big to start, like 50 or 100. Then we take our expansion for $f$ (the first equation I wrote), multiply by a Chebyshev polynomial $T_m(x)$, evaluate at our $x_k$ and sum over k to get,
$$\sum_{k=0}^{N-1} T_m(x_k) f(x_k) = a_m N \epsilon_{m,m}^\prime.$$
So t his gives an expression for the coefficients $a_m$, with $m<N$. These should fall off rather quickly as long as the function isn't too crazy. You only need to keep those that are large enough.

So that gives you the Chebyshev polynomial approximation. I cannot help with the minimax or Remez, as it has never seemed like it was worth all that extra work to me. The normal Chebyshev approximation is very easy once you can compute your function f.

jason

EDIT: forgot to include the nicer form of the sum above. Since $T_n(x)=\cos(n \arccos(x))$, the nicer form for the equations to find the coefficients is:
$$\sum_{k=0}^{N-1} \cos\left( \frac{m \pi (k+\frac{1}{2})}{N} \right) f(x_k) = a_m N \epsilon_{m,m}^\prime.$$

 

[Stephen Tashi]

but I'm a bit confused on how to approximate a function with them. http://en.wikipedia.org/wiki/Chebyshev_polynomials

If you have a sophisticated level of confusion then jasonRF has given an answer. If you are unfamiliar with how "orthogonal" functions can be viewed as vectors in a vector space and how expressing a given function as a sum of component functions is done by "projecting" the function onto an orthogonal basis of functions, you should ask about this. It is the basic idea behind a lot of engineering mathematics.

As to the Remez algorithm, you have to remind me about it! Do you have a link?

The name "Remez" brings to mind a book that gave approximations to functions as ratios of polynomials and I think these approximations were computed by minimizing the maximum deviation between the function and the ratio (of polynomials each having a given degree). It used a somewhat trial-and-error process that took a Chebyshev or Pade approximation as its initial guess. The rationale for not using the theoretical approximations themselves was that they were only exact if they included all terms of an infinite series. So, given that you are only going to use polynomial equations of a given degree, you only have a finite number of coefficients to work with. As I recall, the Remez algorithm was use to find these coefficients. Is that the sort of thing you want to do?