Evaluating high-degree polynomials

[Undoubtedly0]

Hi all. I am trying to evaluate high-degree Chebyshev polynomials of the first kind. It is well known that for each Chebyshev polynomial $T_n$, if $$-1\le x\le1$$ then

$$-1\le T_n(x)\le 1$$

However, when I try to evaluate a Chebyshev polynomial of a high degree, such as $T_{60}$, MATLAB gives results that do not stay within these bounds. I assume this is due to a lack of precision. Any suggestions?

As an example, try

>> x = 0.9;
>> p60 = ChebyshevPoly(60);
>> polyval(p60,x)

ans =

  -1.4447e+04

where ChebyshevPoly() comes from mathworks.com.

 

[coalquay404]

First off, that file isn't from the Mathworks; it's a user submission to the Matlab File Exchange. As you've learned, anything you get from there should be treated with suspicion until it's known to be good.

You're also correct that this is a precision issue. The first few terms in the 60-degree polynomial are

$$1 - 1800 x^2 + 539400 x^4 - 64440320 x^6 + \cdots$$

That Matlab file, however, thinks that there are lots of vanishing coefficients where in fact there shouldn't be. You can see this for yourself by running

ChebyshevPoly(60) < eps

and looking for the zeros.

You could try writing the routine yourself; a look at numerical recipes suggests it isn't that hard.

 

[Undoubtedly0]

Thanks for the response, coalquay404. I think the command you meant to use was

abs(ChebyshevPoly(60)) < eps

I have previously written my own coefficient generator, but achieved only the same bad results. Any thoughts?

 

[uart]

Thanks for the response, coalquay404. I think the command you meant to use was

abs(ChebyshevPoly(60)) < eps

I have previously written my own coefficient generator, but achieved only the same bad results. Any thoughts?

Yes, that's what I'd expect. Take a look at the coefficients of $T_{60}$ and you'll see they go as high as ~3x10^21 (and as low as -3x10^21). Evaluating the polynomial will involve differences of very large numbers of this sort of magnitude, so with double precision only extending to about 15 significant figures, it's not surprising that you're getting erratic results.

You'll probably get "ok" results (correct to several significant digits) if the coefficients don't exceed about the +/- 10^12 range. I just checked T35 for example, and the coefficients extend to about +/- 2.4x10^12 and got the following results.

Matlab polyval(T35,0.9) returned 0.99689, while cos(35*acos(0.9)) returned 0.99696, which agrees, but only to 3 (nearly 4) significant digits.

 

[Undoubtedly0]

Thanks uart. Through what you said I have realized that it would far far easier to simply evaluate the polynomials using the cosine-arcosine property, rather than evaluating the polynomials directly. Thanks!