Thesis on Minimax Rational Function Approximation

MINIMAX RATIONAL FUNCTION APPROXIMATION

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

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.

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.

CONTENTS