# Help with Chebyshev Economization of $\exp(x)$?

This may be a stupid question, so I apologize in advance if it is. This is a very common example of Chebyshev Economization, but I still do not understand how the coefficients are found. I want to approximate $\exp(x)$ over the interval $[-1, 1]$.

$$\exp(x)=1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots$$

I will define

$$P_5(x)=1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\frac{x^4}{4!}+\frac{x^5}{5!}\approx \exp(x)$$

How do I get the coefficients? I have read some online papers explaining this, but I do not understand it still. Often it seems some people use a different method then others because the steps are so different!

-
Which coefficients? The $1,1,1/2!,1/3!,\dots$? Those are just the coefficients in the Taylor (or Maclaurin) series for $e^x$, and have nothing to do with Chebyshev. Chuck "Taylor series" into Google and see what comes out. – Gerry Myerson May 15 '12 at 23:42
@GerryMyerson Of course I am aware of these Taylor's Series and this is what I used to make the polynomial. I am trying to figure out how to find the "new" coefficients of the economized series that is created from the Taylor's series expansion of $\exp$. Look at R. Israel's expansion, these are the coefficients I am referring to. – Argon May 16 '12 at 1:48
Robert is a mind reader. If those were the coefficients you were referring to, why didn't you say so? – Gerry Myerson May 16 '12 at 4:23

If you're interested in the Chebyshev series of $\exp(x)$ on $[-1,1]$, the first few terms, according to Maple, are $$1.26606587775200818\,T \left( 0,x \right) + 1.13031820798497007\,T \left( 1,x \right) + 0.271495339534076507\,T \left( 2,x \right) + 0.0443368498486638174\,T \left( 3,x \right) + 0.00547424044209370542 \,T \left( 4,x \right) + 0.000542926311914030628\,T \left( 5,x \right) + 0.0000449773229543007058\,T \left( 6,x \right) + 0.00000319843646242419376\,T \left( 7,x \right) + 0.000000199212480641916156\,T \left( 8,x \right) + 0.0000000110367716525872165\,T \left( 9,x \right) + 0.000000000550589632227637161\,T \left( 10,x \right)$$ where $T(n,x)$ is the $n$'th Chebyshev polynomial of $x$.
These coefficients can be found by integration: the coefficient of $T(n,x)$ is $$\dfrac{2}{\pi} \int_{-1}^1 \exp(x) T(n,x) (1-x^2)^{-1/2}\ dx$$ (except in the case $n=0$, where the $2/\pi$ is replaced by $1/\pi$).

-
Thank you very much! Plotting a few terms quick shows that this is the correct polynomial. I don't recognize this integral even after reading up on Chebyshev economization. Do people use alternate methods to find the coefficients or is approximating this integral the most common way (and I missed it)? – Argon May 16 '12 at 1:57
This is a pretty standard definition, I think (based on the Chebyshev polynomials being orthogonal with respect to the weight $w(x) = (1-x^2)^{-1/2}$ on $(-1,1)$). On the other hand, it's probably not a very good way to calculate the coefficients, due to the singularities of $w(x)$ at $\pm 1$. The change of variables $x = \cos(t)$ makes this into $\dfrac{2}{\pi} \int_0^{\pi} \exp(\cos(t)) \cos(n t)\ dt$ (which happens to be $2 I_n(1)$ where $I_n$ is a modified Bessel function, but that's beside the point). – Robert Israel May 16 '12 at 4:07
Last I checked, they use DCT, which is effectively the same as using the trapezoidal rule to compute those integrals... – J. M. May 16 '12 at 10:36

The method I am accustomed to for the conversion of a polynomial or a truncated power series of the form $c_0+c_1 x+c_2 x^2+\cdots +c_n x^n$ to Chebyshev form is a specialization of a more general algorithm due to Herbert Salzer. I would ask you to read the paper for more details, but in any event, here is Mathematica code for Salzer's algorithm, adapted to Chebyshev conversion:

c = CoefficientList[Series[Exp[x], {x, 0, 8}], x]
{1, 1, 1/2, 1/6, 1/24, 1/120, 1/720, 1/5040, 1/40320}

n = Length[c] - 1;
a[0, 2] = c[[n - 1]] + c[[n + 1]]/2;
a[1, 2] = c[[n]]; a[2, 2] = c[[n + 1]]/2;
Do[

a[0, k + 1] = c[[n - k]] + a[1, k]/2;
a[1, k + 1] = a[0, k] + a[2, k]/2;

Do[
a[m, k + 1] = (a[m + 1, k] + a[m - 1, k])/2
, {m, 2, k - 1}];

a[k, k + 1] = a[k - 1, k]/2;
a[k + 1, k + 1] = a[k, k]/2;

, {k, 2, n - 1}];
Table[a[m, n], {m, 0, n}]

{2917/2304, 10417/9216, 139/512, 227/5120, 7/1280, 5/9216, 1/23040,
1/322560, 1/5160960}


(I wrote it in a way so that it should be easily adaptable to your favorite computing environment, though you may have to do some index finagling. It is possible to implement Salzer's algorithm so that only a one-dimensional array is needed as opposed to the two-dimensional array a used above, but I'll leave that implementation as an exercise.)

In any event, we obtain the identity

$$\sum_{k=0}^8\frac{x^k}{k!}=\frac{2917}{2304}+\frac{10417}{9216}T_1(x)+\frac{139}{512}T_2(x)+\frac{227}{5120}T_3(x)+\frac{7}{1280}T_4(x)+\frac{5}{9216}T_5(x)+\frac{1}{23040}T_6(x)+\frac{1}{322560}T_7(x)+\frac{1}{5160960}T_8(x)$$

The last two terms are already rather tiny ($\approx3.1\times10^{-6}$ and $\approx1.9\times10^{-7}$, respectively), so we try chopping off the last two terms (keep terms up to $T_6(x)$) and re-expanding back to a monomial series. Doing this gives the polynomial (with coefficients in approximate decimal format)

$$p(x)=0.99999980623759920635+1.0000217013888888889 x+0.50000620039682539683 x^2+0.16649305555555555556 x^3+0.041635664682539682540 x^4+0.0086805555555555555556 x^5+0.0014384920634920634921 x^6$$

Let's try plotting $p(x)-\exp\,x$ over $[-1,1]$:

Not counting the endpoints, we see six extrema in the plot, showing off the equiripple behavior of a Chebyshev economization.

-