1
$\begingroup$

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!

  • 2
    Robert is a mind reader. If those were the coefficients you were referring to, why didn't you say so?2012-05-16

2 Answers 2

5

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$).

  • 0
    Last I checked, they use DCT, which is effectively the same as using the trapezoidal rule to compute those integrals...2012-05-16
5

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]$:

equiripple plot

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