A MACSYMA package for the generation and manipulation of chebyshev series

ABSTRACT

Techniques for a MACSYMA package for expanding an arbitrary univariate expression as a truncated series in Chebyshev polynomials and manipulating such expansions is described. A data structure is introduced to represent a truncated expansion in a set of orthogonal polynomials. The data structure contains the independent variable, the name of the orthogonal polynomial set, the number of terms retained, and a list of the expansion coefficients. Although we restrict attention here to the set of Chebyshev polynomials as the orthogonal set, extension to other orthogonal polynomials will be done later. A data structure for truncated power series is provided as an alternative. The principal function of the package converts a given expression into the aforementioned data structure. Special cases are the conversion of sums, products, the ratio, or the composition of truncated Chebyshev expansions. Another special case is converting an expression free of truncated Chebyshev expansions. The package generates exact expansion coefficients whenever possible. In addition to well-known Chebyshev expansions, such as for polynomials, we provide new methods for getting exact Chebyshev expansions for reciprocals of polynomials of degree one or two, meromorphic functions, arbitrary powers of a first-degree polynomial, the error-function, and generalized hypergeometric functions. When exact Chebyshev expansions for a function are unknown, or too costly to compute, approximate expansions are performed. Conversion to power series and interpolation between the roots of a Chebyshev polynomial are supported. The Clenshaw method for symbolic Chebyshev expansion of the solution of a linear differential equation whose coefficients are low degree polynomials is implemented in the package.

REFERENCES

• 1: See, for example, H. Margenau and Murphy "The Mathematics of Physics and Chemistry" Van Nostrand
• 2: This expression can be shown to be a polynomial in x by showing from the definition that T0(x)=l, T l(x)=x, and (the recurrence) Tn+1 (x)=2xTn(x)-Tn.l(X). From the recurrence it follows that Tn+ 1 is a polynomial in x if Tn and Tn_ 1 are.
• 3: E. Cheney "Introduction to Approximation Theory" Second Ed, Chelsea New York 1982 p126
• 4: L. Fox and I. Parker "Chebyshev Polynomials in Numerical Analysis" Oxford London 1968
• 5: Massachusetts Institute of Technology, Artificial Intelligence Laboratory AI Memo 239, a.k.a.Hakmem
• 6: M. Abramowitz and i. Stegun "Handbook of Mathematical Functions" National Bureau of Standards AMS 55 Washington 1964. p376,(9.6.34)
• 7: The identity x+n + x.n = 2 Tn(x) appears in M. Snyder "Chebyshev Methods in Numerical Approximation" Prentice-Hall Englewood Cliffs, New Jersey 1966 p13, (1.1-14) as an alternative definition of Tn but not as part of a Chebyshev transform.
• 8: E. Whittaker and G. Watson "A Course in Modern Analysis" Third Ed. Cambridge 1920 p134
• 9: C. Clenshaw "Chebyshev Series for Mathematical Functions" Her Majesty's Stationery Office London 1962, See also K. Geddes 1977 MACSYMA users' conference.
• 10: We didn't know that there was an exact form for the inverse of the Chebyshev .transform until W. Kahan taught us that The inverse can be obtained by a Poisson integral. In fact: 2 ~-i'I w+x dw where the integration contour is a unit circle, and F(x) is real. tte learned it from J.C.P. Miller at Cambridge in the mid I950%. The appropriate Poisson integral formula is given in {G, Carrier, M. Krook, and C. Pearson "Theory of Functions of a Complex Variable", McGraw-Hill, 1966, p.47 } We know of no case where using the Poisson integral formula gives an answer that could not be obtained by guessing at the inverse. For the case of (4.1.2-6), guessing the inverse Chebyshev transform is much simpler than calc~~lating the Poisson integral by residues. The residue method requires calculating the location of poles, detem~ining whether they are inside the contour, and calc~lating the residue of those that lie inside. Moreover, the residue method must invoke analytic continuation in the case of complex q.
• 11: The advantage of Chebyshev approximations can be glimpsed by comparing numerical approximations for e. The exact value is 2.718...; truncating the Maclaurin series for ex at O(x4) yields 2.708; the corresponding (2,2)Parle approximant is 2.714; truncating the Chebyshev series at O(T4(x)) yields 2.718.
• 12: In the seminal paper on Chebyshev series: C.Lanczos, J.Math. & Phys. 17,123(1938), eq. (4.1.2-6) is derived in a different way. A three-term recurrence with constant coefficients is solved, using as a boundary condition the vanishing of all coefficients in the Chebyshev series witrh index beyond a fixed n. The index n is then allowed to go to infinity. Characteristically, truncating Chebyshev series at a finite index n gives more complicated answers than do the exact Chebyshev series.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION

Additional Classification:
  E. Data

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

General Terms:
Algorithms, Theory