MINIMAX
RATIONAL FUNCTION APPROXIMATION
By
John W. Boushka
B.S. The
Submitted to the Department of Mathematics and the Faculty
of the
Instructor in Charge: Richard G. Hetherington
For the Department: Robert D. Brown
ãCopyright
1968 by John W. Boushka and the
Materials from this thesis are made available for nonprofit or research purposes only. Please give proper attribution.
Image PDF format link.
John W. Boushka
4201 Wilson Blvd. #110688
Preface:
During the past few years much has been written about minimax approximation of continuous realvalued functions. The basic problem, stated precisely, is as follows:
Let Rrm (x) be the set of all rational functions of x with numerator degree <= r and denominator degree <= m. Suppose we are given two realvalued 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 Rrm (x) belongs to the set of all such functions, we define
srm (sup R) = max x belongs to [a, b] of Rrm (x) – f(x)  / g(x)
the maximum error in [a, b] of Rrm (x) as an approximation to f9x) with respect to the weight function g(x). We seek Rrm * (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) = Rrm (x) – f(x) of a rational approximant ‘directly,’ that is, the functions f(x) and Rrm (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 Rrm (x) – f(x) without separate calculations of f(x) and Rrm (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
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 FraserHart 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. 28693.
D1 Dunham, Charles (1965). “Convergence Problems in Maehly’s Second Method,” Part I, Journal of the Association for Computing Machinery, Vol. 12, pp 1816.
D2 Dunham, Charles (1965). “Convergence Problems in Maehly’s Second Method,” Part II, Journal of the Association for Computing Machinery, Vol. 13, pp 10813.
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. 4013.
G1 Garganti,
G2 Garganti,
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 25777.
Me Meindaraus, G. and Strauer, H. D. (1961). “Uber die Approximation von Funktionen bei der Aufstellung von Unterprogrammen,” Elektronische Datenverarbeitung, Vol. 12, pp 18087.
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. 229232.
R1
Ralston, Anthony (1965). A First Course in
Numerical Analysis,
R2 Ralston, Anthony (1965). “Rational Chebyshev Approximation by Remes’s Algorithms,” Numerische Mathematik, Vol, 7, pp 32230.
Sc Schecter, S. (1959). “On the Inversion of Certain Matrices,” Mathematical Tables and Aids to Computation, Vol. 13, pp 737.
S1 Stoer, Josef (1964). “A Direct Method for Chebyshev Approximation by Rational Functions,” Journal of the Association for Computing Machinery, Vol. 11, pp. 5969.
S2 Cody, W. J. and Stoer, Josef. (1966). “Rational Chebyshev Approximation Using Interpolation,” Numerische Mathematik, Vol, 9, pp 17788.
T Tornbeim, L. (1950). “On nparameter Families of Functions and Associated Convex Functions,” TransAmerican Mathematical Society, Vol. 69, pp 457467.
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 91116.
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 20519.
W2 Werner, Helmut (1961). “Rationale Tschebyscheff – Approximation Eigenwerttheorie und Differenzenrechung,” Archives for Rational Mechanics and Analysis, Vol. 12, pp 33047.
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
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
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
Some of the bibliographic references here are obscure and
probably not available online, but since I live in the