Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!wuarchive!gem.mps.ohio-state.edu!rpi!wrf From: wrf@mab.ecse.rpi.edu (Wm Randolph Franklin) Newsgroups: comp.dsp Subject: Re: Taylor vs. Chebyshev polynomials Keywords: Taylor vs. Chebyshev polynomials Message-ID: <1989Oct6.014757.23577@rpi.edu> Date: 6 Oct 89 01:47:57 GMT References: <2421@radio.oakhill.UUCP> <1989Sep28.161516.10353@rpi.edu> <3811@deimos.cis.ksu.edu> Organization: Rensselaer Polytechnic Institute, Troy NY Lines: 64 In <3811@deimos.cis.ksu.edu> mac@harris.cis.ksu.edu (Myron A. Calhoun) writes: >I'm under the impression that in any given range which doesn't have >singularity points, Chebyshev polynomials (of the first kind) can be >used to "telescope" Taylor series of degree N down to degree N-1 >while retaining the same maximum error (but this error may pop up in >places where it wasn't present in the original--kinda like squeezing >a balloon). Well, it was extreme of me to call Taylor series wimpy, especially since sin is about the best example of a Taylor -- it's entire (no singularities) and the coefficients decrease fast. Also, a Taylor series is often by far the easiest approximation to a function. However, even with sin, Chebyshev have an advantage of more than 1 term, and the advantage increases with the degree. Consider sin(x) from 0 to pi/2 -- the obvious interval for a sin implementation. I expanded the Taylor series about pi/4, and did the Chebyshev over [0,pi/2], both to 20 significant digits. These coefs are the approx max error at each stage since I also renormalized x to be in [-1,1]. n abs(Taylor coef) abs(Cheb coef (i.e. coef of T(n,x))) 5 2e-3 7e-6 10 2e-8 3e-11 15 1e-14 9e-19 The 15th degree Taylor has an accuracy between the 12 and 13th degree Chebyshev - more than 1 degree improvement. For other series or intervals, it can be more. Consider sin(x) from -pi to pi. I expanded sin(x)/x about 0. Note that it's an even function so there's no 5th degree. n Taylor Chebyshev 4 3 .2 10 7e-3 1e-5 14 2e-5 2e-9 The 14th degree Taylor is between an 8th and 10th degree Chebyshev. Next, your restriction to non singular functions is quite strict since many smooth, infinitely differentiable, functions, such as 1/(x^2+0.01), have a radius of convergence for the Taylor of 0.1 because of the complex pole at 0+.1i. Also, an N-th degree Taylor requires that the function be differentiable N times, whereas Chebyshev requires only once. In both of these cases, the Chebyshev series converges slowly, but it converges over the whole interval, whereas Taylor converges only in (-0.1, 0.1) in the first, and not at all in the second. Actually, if you allow one division in your approximation, you can use a rational or Pade form of either the Taylor or Chebyshev, which for less well behaved functions vastly improves either approx. They're much more complex to calculate, but can improve on the Taylor even for exp(x). Summary: Taylor is certainly ok for sin(x), but Chebyshev is faster even here, and does a much wider class of functions. However, it is messier to calculate. -- Wm. Randolph Franklin Internet: wrf@ecse.rpi.edu (or @cs.rpi.edu) Bitnet: Wrfrankl@Rpitsmts Telephone: (518) 276-6077; Telex: 6716050 RPI TROU; Fax: (518) 276-6261 Paper: ECSE Dept., 6026 JEC, Rensselaer Polytechnic Inst, Troy NY, 12180