A Survey of Methods of Computing Minimax and Near-Minimax Polynomial Approximations for Functions of a Single Independent Variable

ABSTRACT

Methods are described for the derivation of minimax and near-minimax polynomial approximations. For minimax approximations techniques are considered for both analytically defined functions and functions defined by a table of values. For near-minimax approximations methods of determining the coefficients of the Fourier-Chebyshev expansion are first described. These consist of the rearrangement of the coefficients of a power polynomial, and also direct determination of the coefficients from the integral which defines them, or the differential equation which defines the function. Finally there is given a convenient modification of an interpolation scheme which finds coefficients of a near-minimax approximation without requiring numerical integration or the numerical solution of a system of equations.

REFERENCES

• 1: ACHISER, N. I. Theory of Approximation. Ungar, New York, 1956. English translation by C. J. Hymam
• 2: CHENY, E.W. Approximation theory. Dept. of Mathematics, U. of California, 1963. (Mimeo)
• 3: CLNSHAW, C.W. A note on the summation of Chebyshev series. MTAC 9, 1955, 118-120.
• 4: The numerical solution of linear differential equations in Chebyshev series. Proc. Camb. Phil. Soc. 53 (1957), 134-149.
• 5: Chebyshev Series for Mathematical Functions. National Physical Lab., Math. Tables 5, tlM Stat. Off., London, 1962.
• 6: Davis, P. Interpolation and Approximation. Blaisdell, New York, 1963.
• 7: Fox, L. Chebyshev methods for ordinary differential equations. Comput. J. , (1962), 318-31.
• 8: GOLOMB, M. Lectures on theory of approximation, Appl. Math, Div., Argonne Na. Lab., Argonne, Ill., 1962.
• 9: KOPAL, Z. Numerical Analysis. Chapman & ttall, London, 1955.
• 10: LANczos, C. Applied Analy.Gs. Prentice-Hail, Englewood Cliffs, N. J., 1956.
• 11: MqNAratAN, F. D., AND WR:Ct, J.W. Report No. 1175, David Taylor Model Basin, Md., 1960.
• 12: NATIONSON, I.P. Constructive Theory of functions. AEC-tr-4503, Books 1 and 2. English translation by US AEC.
• 13: NATIONAL BUREAU Of STANDARDS. Handbook of Mathematical Functions. NBS Appl. Math. Series 55, US Govt. Printing Off., Washington, D. C., 1964.
• 14: NOVODVORSKII, E. P., ANn PINSKER, 1. S. Tile process of equating maxima. Uspehi Mat. Nauk 6 (1951), 174-181. English translation by A. Shenitzer.
• 15: REMEZ, E. YA. General computational methods of Chebyshev approximation. In The rob lems with IAnear Real Parameters. AEC-tr-4491, Books 1 and 2, English translation by US AEC.
• 16: RICE, J.R. The Approximation of Functions, Vol. i, Linear Theory. Addison-Wesley, Read. ing, Mass., 1964.
• 17: SHANKS, D. Non-linear transformations of divergent and slowly convergent series. J, Math. Phys. 84 (1955), 1-42.
• 18: STIEFEL, E. IJ. Numerical methods of Chebyshev approximation. In On Numerical Approxi. mation, R. E. Langer, Ed., U. of Wisconsin Press, Madison, 1959.
• 19: Henry C. Thacher, Jr., Conversion of a power to a series of Chebyshev polynomials, Communications of the ACM, v.7 n.3, p.181-182, March 1964 [doi>10.1145/363958.363998]
• 20: VALLIE POUSSIN, C. J. DE LA. Sur la m6thode de l'approximation minimum. Ann. Soc. Sci. Bruxelles, Seconde Partie, M6moires 35, pp. 1-16, Bruxelles, 1911. English translation by H. E. Salzer.
• 21: Leons sur l'Approximation des Fonctions d'une Variable Rdelle. Gauthier-Villars, Paris, 1919.
• 22: VEIDINGER, L. On the numerical determination of the best approximations in the Chebyshev sense. Numer. Math. 2 (1960), 99-105.
• 23: WALSH, J.L. Interpolation and Approximation. Amer. Math. Soe. Coll. Publ. 20, Providence, 1960.
• 24: WYNN, P. On a device for computing the e,(S,,) transformation. MTAC 10 (Apr. 1956), 91-96,

INDEX TERMS

Primary Classification:
  A. General Literature

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Minimax approximation and algorithms

General Terms:
Measurement, Performance, Theory