MINIMAX RATIONAL FUNCTION APPROXIMATION

 

 

                                                By

                                    John W. Boushka

            B.S. The George Washington University

                        Washington, D.C. 1966

 

 

Submitted to the Department of Mathematics and the Faculty of the Graduate School of the University of Kansas in partial fulfillment of the requirements for the degree of Master of Arts

 

Instructor in Charge: Richard G. Hetherington

For the Department: Robert D. Brown

 

January 28, 1968

 

ăCopyright 1968 by John W. Boushka and the University of Kansas

Materials from this thesis are made available for non-profit or research purposes only. Please give proper attribution.

 

Image PDF format link.

 

John W. Boushka

4201 Wilson Blvd. #110-688

Arlington, VA 22203-1859

571-334-6107

JBoushka@aol.com

 

 

Preface:

 

During the past few years much has been written about minimax approximation of continuous real-valued functions. The basic problem, stated precisely, is as follows:

 

Let R-rm (x) be the set of all rational functions of x with numerator degree <= r and denominator degree <= m. Suppose we are given two real-valued functions f(x) and g(x) which are both continuous on the interval [a, b]. We assume that g(x) is always positive in [a, b]. For any R-rm (x) belongs to the set of all such functions, we define

 

s-rm (sup R) = max x belongs to [a, b] of |R-rm (x) – f(x) | / g(x)

 

the maximum error in [a, b] of R-rm (x) as an approximation to f9x) with respect to the weight function g(x). We seek R-rm * (x) which among all such members yields the smallest possible maximum (weighted) error s * rm for the given functions f(x) and g(x) in and interval [a, b].

 

In this paper we shall examine in some detail three basic approaches to this problem: the two major “direct methods” and an “indirect” or “combined” method. The reference that provides a springboard for our investigation is “Methods of Fitting Rational Approximations,” Parts II and III, by Maehly and Witzgall.  In Maehly’s words, “the direct methods compute the error curve e(x) = R-rm (x) – f(x) of a rational approximant ‘directly,’ that is, the functions f(x) and R-rm (x) are evaluated and subtracted afterwards.” Among the direct methods there are basically two types: those that work only with the critical points of error curves of successive approximants, and those which work also with the zeros of the error curves. The indirect methods require schemes to evaluate R-rm (x) – f(x) without separate calculations of f(x) and R-rm (x) in order to avoid the loss of significant figures in subtraction.

 

We shall examine here only those algorithms that lead to a “true” minimax approximation. There are “economization” methods that converge to rational functions whose error curves assume the properties of minimax curves only as the interval size approaches zero. In practice the truncation error incurred in these methods often compares favorably (for a given problem) with the roundoff error in the “exact” methods.

 

I wish to express my gratitude to Dr. Richard G. Hetherington, Associate Professor of Mathematics at the University of Kansas, for his generous assistance in the preparation of this paper.

 

CONTENTS

 

1

Introductory Theory

1

2

First Direct Method

7

3

Second Direct Method

55

4

Finding the Critical Points of a Given Error Curve

72

5

Indirect Methods

76

6

Generalizations

81

 

Appendix: Numerical Example comparing Werner’s Method with Fraser-Hart Method

86

 

Bibliography

87

 

BIBLIOGRAPHY

 

C  Curtis, Alan and Osborne, M. R. (1966), “The Construction of Minimax Rational Approximations to Functions,” The Computer Journal, Vol, 9, pp. 286-93.

 

D1  Dunham, Charles (1965). “Convergence  Problems in Maehly’s Second Method,” Part I, Journal of the Association for Computing Machinery, Vol. 12, pp 181-6.

 

D2  Dunham, Charles (1965). “Convergence  Problems in Maehly’s Second Method,” Part II, Journal of the Association for Computing Machinery, Vol. 13, pp 108-13.

 

F  Fraser, W. and Hart J. F. (1962). “On the Computation of Rational Approximations to Continuous Functions,” Communications of the Association for Computing Machinery, Vol. 5, pp. 401-3.

 

G1  Garganti, I. and Pomentale, T. (1964), “Rational Chebyshev Approximations to the Bessel Function Integrals K-is (x) ,” Communications of the Association for Computing Machinery, Vol. 7, pp. 727-30.

 

G2  Garganti, I. (1966). “On the Application of the Process of Equalization of Maxima to Obtain Rational Function Approximation to Certain Modified Bessel Functions,” Communications of the Association for Computing Machinery, Vol. 9, pp. 859-63.

 

M  Maehly, Hans J. and Witzgall, Christoph (1963). “Methods for Fitting Rational Approximations,” Parts II and III, Journal of the Association for Computing Machinery, Vol. 10, pp 257-77.

 

Me Meindaraus, G. and Strauer, H. D. (1961). Uber die Approximation von Funktionen bei der Aufstellung von Unterprogrammen,” Elektronische Datenverarbeitung, Vol. 12, pp 180-87.

 

N  Novodvorskii, E. P. and Pinsker, I. Sh. (1951) “On a Process of Equalization of Maxima,” Uspehi Mat. Nauk,, Vol. 6, Issue 6, translation by A Shenitzer from Russian, available from New York University Library.

 

O  Osborne, M. R (1964). “A New Method for the Solution of Eigenvalue Problems,” The Computer Journal, Vol. 7, pp. 229-232.

 

R1  Ralston, Anthony (1965). A First Course in Numerical Analysis, McGraw-Hill, New York, 1965.

 

R2  Ralston, Anthony (1965). “Rational Chebyshev Approximation by Remes’s Algorithms,” Numerische Mathematik, Vol, 7, pp 322-30.

 

Sc Schecter, S. (1959). “On the Inversion of Certain Matrices,” Mathematical Tables and Aids to Computation, Vol. 13, pp 73-7.

 

S1  Stoer, Josef (1964). “A Direct Method for Chebyshev Approximation by Rational Functions,” Journal of the Association for Computing Machinery, Vol. 11, pp. 59-69.

 

S2  Cody, W. J. and Stoer, Josef. (1966). “Rational Chebyshev Approximation Using Interpolation,” Numerische Mathematik, Vol, 9, pp 177-88.

 

T  Tornbeim, L. (1950). “On n-parameter Families of Functions and Associated Convex Functions,” Trans-American Mathematical Society, Vol. 69, pp 457-467.

 

Wa  Wall, H. S. (1929). “On the Pade Approximants Associated with the Continued Fraction and Series of Stieltjes,” Transactions of the American Mathematical Society, Vol. 31, pp 91-116.

 

W1  Werner, Helmut (1961). “Die constructive Ermittlung der Tschebyscheff – Approximation im Bereich der rationalen Funktionen,” Part I, Archives for Rational Mechanics and Analysis, Vol. 10, pp 205-19.

 

W2  Werner, Helmut (1961). “Rationale Tschebyscheff – Approximation Eigenwerttheorie und Differenzenrechung,  Archives for Rational Mechanics and Analysis, Vol. 12, pp 330-47.

 

W3  Werner, Helmut (1961). “Die Bedeutung der Normalitat bei rationaler Tschebyscheff – Approximation,  Computing, Vol. 2, p 34

 

I believe that Dr. John W. Wrench, then at the David Taylor Model Basin (Naval Surface Warfare Center) in Carderock, Md (in the late 1960s) also contributed material.

 

 

I typed the original thesis on a manual typewriter in Pica with special keys for mathematics symbols and also for chemistry equations. I was going to be a chemistry major before the “disaster” at the College of William and Mary in the fall of 1961.

 

I did have to do a defense and oral exam in January, 1968, right before getting my M.A. and then entering the Army. I actually had a copy of the thesis mailed to me in Basic Training at Fort Jackson, S.C.  for a failed direct commission interview!  For a job interview (successful) at RCA in late 1969 I gave a technical talk on this thesis at the David Sarnoff Research Center in Princeton, N.J.  It is ironic that thirty or so years of life would ensue in many locations before my next big public speaking (and, as it turned out, cable television) appearance on my “Do Ask Do Tell” book and libertarianism (it was broadcast on the Liberty Channel in Minneapolis) in February 1998, after such a revolution in technology that mathematics like this helped to stimulate.

 

Some of the bibliographic references here are obscure and probably not available online, but since I live in the Washington, DC area I suppose that I could find them at the Library of Congress if there were interest.