mac@harris.cis.ksu.edu (Myron A. Calhoun) (10/03/89)
In article <1989Sep28.161516.10353@rpi.edu> wrf@mab.ecse.rpi.edu (Wm Randolph Franklin) writes: [many lines deleted] >You can work out how many Taylor terms it would take to get that >accuracy. Editorial: Taylor series are for wimps. 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). The difference between N and N-1 is only ONE term (although for some common trig functions which have only even- or odd- powered terms, it may LOOK like two?); which seems rather "wimpy" to me. I can see that if I'm going to calculate a particular series a jillion times, one less calculation would be nice, but I don't see that as being particularly significant otherwise. Do other Chebyshev polynomials provide even better telescoping? [more lines deleted] --Myron. -- Myron A. Calhoun, PhD EE, W0PBV, (913) 532-6350 (work), 539-4448 (home). INTERNET: mac@ksuvax1.cis.ksu.edu BITNET: mac@ksuvax1.bitnet UUCP: ...{rutgers, texbell}!ksuvax1!harry!mac
broman@schroeder.nosc.mil (Vincent Broman) (10/03/89)
[mac@ksuvax1.cis.ksu.edu posts a misunderstanding about telescoping
power series with Chebychev polynomials.]
Actually, if one could always reduce the degree of a polynomial
approximation by one, retaining the same max error, then repeating the
process would give us a zeroth degree approximation with the same max
error as the original Nth degree polynomial provided.
Doesn't seem reasonable.
The method looks more like this:
Generate a Taylor series giving significantly better accuracy ofapproximation
than is needed over the interval of interest, say \epsilon / 2.
Express this (N-th degree) polynomial as a weighted sum
of Chebychev polynomials:
\sum_{k=0}^N \alpha_k T_k ( x).
This step is just a change of basis in the vector space of N-th degree
polynomials.
Now choose M such that \sum_{k=M+1}^N \| \alpha_k \| <= \epsilon / 2,
i.e. the tail of the series is small enough.
Then we use the M-th degree polynomial \sum_{k=0}^M \alpha_k T_k ( x)
as our approximating polynomial, and the error will be less
than or equal to \epsilon / 2 + \epsilon / 2 = \epsilon.
Generally M will be much smaller than N; one is trading off
accurate approximation of the function derivatives near one point
for accurate approximation of function values over the whole interval.
Vincent Broman, code 632, Naval Ocean Systems Center, San Diego, CA 92152, USA
Phone: +1 619 553 1641 Internet: broman@nosc.mil Uucp: sdcsvax!nosc!bromanwrf@mab.ecse.rpi.edu (Wm Randolph Franklin) (10/04/89)
You're right that my calling Taylor series wimps is excessive. This is
especially so for sin(x) which is one of the functions that Taylor
series are best suited for since sin is smooth and defined over the
whole complex plane with no singularities, and the Taylor coefficients
shrink fast.
However, even here Chebyshev polynomials are better, and the relative
difference increases as the order increases.
I scaled sin to that [0,Pi] was mapped to [-1,1] and expanded about the
new 0 (for Taylor) or over the interval (for Chebyshev). This is
probably the interval you would want to approximate.
N abs(Coef of x^n) in Taylor
abs(Coef of T(N,x)) in Cheb
0 .7 .6
1 .55 .5
2 .22 .1
3 .06 .01
4 .01 .001
5 .002 .0001
6 .0002 7e-6
7 .00002 3e-7
8 3e-6 2e-8
9 2e-7 9e-10
10 2e-8 3e-11
11 1e-9 1e-12
12 8e-11 4e-14
13 5e-12 1e-15
14 3e-13 3e-17
15 1e-14 9e-19
Note:
1. Truncating the Chebyshev series when it is still expressed in T(n,x)
is equivalent (almost) to truncating the Taylor series expressed in x^n.
In either case, the error from stopping at any term is usually less than
the first unused coefficient. (Picky note to Chebyshev hackers: this is
why it is more useful to look at the coefficients of T rather than
convert to a power basis.)
2. Although I only retyped 1 or 2 digits for this note, the calcs were
done to 20 significant digits to avoid roundoff.
3. The Taylor to the 15th degree is between the 12th and 13th degree
Chebyshev -- which is more than one term.
Well, maybe you think that the interval favored Chebyshev. So try
another interval [-Pi,Pi], scaled to [-1,1]. Note the function is odd.
N Taylor Cheb
1 3 1
3 5 1.6
5 3 .2
7 .6 .01
9 .08 .0005
11 .007 .00001
13 .0004 2e-7
15 .00002 2e-9
The Taylor to x^15 worse than the Chebyshev to x^11.
----------------
In all the above I'm using about the best possible function for the
Taylor. In fact Chebyshev can do a wide class of functions Taylor
can't:
- functions with a complex singularity nearby, such as 1/(x^2+.1).
- functions which are only differentiable a small number of times.
Taylor requires N for N-th degree, Chebyshev requires only 1st order.
Admittedly Chebyshev will converge much more slowly in these cases. But
it WILL converge, and Taylor WON'T.
----------------
(Now I'm really getting on my hobby-horse). There's something often
much better than Chebyshev -- a Pade-Chebyshev expansion, which is a
Chebyshev converted to a rational fraction. Its relative betterness
also increases with N. However it requires one divide to evaluate. The
problem is that Pade expressions are not in the textbooks yet, and even
if they were are more complicated to calculate. Also I can't get Maple
to do it right now.
--
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, 12180wrf@mab.ecse.rpi.edu (Wm Randolph Franklin) (10/06/89)
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