phone +7 (3412) 91 60 92
mail imi@udsu.ru
ru-RU Russian
Home » Issues » Archive of Issues » 2015 - 3 issue » pp. 297-305

Archive of Issues

Russia Nizhni Novgorod
Year
2015
Volume
25
Issue
3
Pages
297-305
>>
Section Mathematics
Title On rational approximations of functions and eigenvalue selection in Werner algorithm
Author(-s) Galkin O.E.a, Galkina S.Yu.a
Affiliations Nizhni Novgorod State Universitya
Abstract The paper deals with the best uniform rational approximations (BURA) of continuous functions on compact (and even finite) subsets of real axis $\mathbb{R}$.The authors show that BURA does not always exist. They study the algorithm of Helmut Werner in more detail. This algorithm serves to search for BURA of the type $P_m/Q_n = \sum\limits_{i=0}^m a_i x^i \big/ \sum\limits_{j=0}^n b_j x^j$ for functions on a set of $N=m+n+2$ points $x_1<\ldots<x_N$. It can be used within the Remez algorithm of searching for BURA on a segment. The Verner algorithm calculates $(n+1)$ real eigenvalues $h_1,\ldots,h_{n+1}$ for the matrix pencil $A-hB$, where $A$ and $B$ are some symmetric matrices. Each eigenvalue generates a rational fraction of the type $P_m/Q_n$ which is a candidate for the best approximation. It is known that at most one of these fractions is free from poles on the segment $[x_1, x_N]$, so the following problem arises: how to determine the eigenvalue which generates the rational fraction without poles? It is shown that if $m=0$ and all values $f(x_1),-f(x_2),\ldots,(-1)^{n+2} f(x_{n+2})$ are different and the approximating function is positive (negative) at all points $x_1,\ldots,x_{n+2}$, then this eigenvalue ranks $[(n+2)/2]$-th ($[(n+3)/2]$-th) in value. Three numerical examples illustrate this statement.
Keywords best uniform rational approximations, rational approximations on finite sets, Remez algorithm, Werner algorithm, selection of eigenvalues in Werner algorithm
UDC 517.518.84
MSC 65D15, 41A20
DOI 10.20537/vm150301
Received 1 August 2015
Language Russian
Citation Galkin O.E., Galkina S.Yu. On rational approximations of functions and eigenvalue selection in Werner algorithm, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2015, vol. 25, issue 3, pp. 297-305.
References
  1. Achiezer N.I. Theory of approximation, New York: Frederick Ungar publishing, 1956, 307 p. Original Russian text published in Akhiezer N.I. Lektsii po teorii approksimatsii, Moscow-Leningrad: Gostekhizdat, 1947, 323 p.
  2. Watson G.A. Approximation theory and numerical methods, New York: John Wiley and Sons, 1980, 229 p.
  3. Powell M.J. Approximation theory and methods, Cambridge: Cambridge University Press, 1981, 339 p.
  4. Brezinski C. Historical perspective on interpolation, approximation and quadrature, Handbook of numerical analysis, vol. 3, Eds.: Ciarlet P.G., Lions J.-L. North-Holland, 1994, pp. 3-46.
  5. Sendov B., Andreev A. Approximation and interpolation theory, Handbook of numerical analysis, vol. 3, Eds.: Ciarlet P.G., Lions J.-L. North-Holland, 1994, pp. 223-462.
  6. Walsh J.L. The existence of rational functions of best approximation, Trans. Amer. Math. Soc., 1931, vol. 33, pp. 668-689.
  7. Borel E. Leçons sur les fonctions de variables réelles, Paris: Gauthier-Villars, 1905.
  8. Achieser N.I. On extremal properties of certain rational fuctions, Dokl. Akad. Nauk SSSR, 1930, vol. 18, pp. 495-498 (in Russian).
  9. Remes E.Ya. Sur le calcul effectif des polynômes d'approximation de Tchebycheff, C.R. Acad. Sci. Paris, 1934, vol. 199, pp. 337-340.
  10. Remez E.Ya. Pro metody naikrashchogo v rozuminni Chebyshova nablizhenogo predstavleniya funktsii (On the methods of the best approximate representation of functions in Chebyshov sense), Kiiv: Ukr. Akad. Nauk, 1935, 162 p. (In Ukrainian).
  11. Werner H. Tschebyscheff-approximation im bereich der rationalen funktionen bei vorliegen einer guten ausgangsnäherung, Arch. Ration. Mech. Anal., 1962, vol. 10, no. 1, pp. 205-219.
  12. Fraser W., Hart J.F. On the computation of rational approximations of continuous functions, Comm. ACM, 1962, vol. 5, no. 7, pp. 401-403.
  13. Ralston A. Rational Chebyshev approximation by Remes' algorithms, Numer. Math., 1965, vol. 7, no. 4, pp. 322-330.
  14. Werner H. Rationale Tschebyscheff-approximation, eigenwerttheorie und differenzenrechnung, Arch. Ration. Mech. Anal., 1963, vol. 13, no. 1, pp. 330-347.
  15. Maehly H.J., Witzgal Ch. Methods for fitting rational approximations. Parts II and III, Journal of the ACM, 1963, vol. 10, no. 3, pp. 257-277.
  16. Parlett B. The symmetric eigenvalue problem, N.J.: Prentice-Hall, Englewood Cliffs, 1980, 348 p. Translated under the title Simmetrichnaya problema sobstvennykh znachenii. Chislennye metody, Мoscow: Mir, 1983, 384 p.
  17. Curtis A., Osborne M.R. The construction of minimax rational approximation to functions, The Computer Journal, 1966, vol. 9, no. 3, p. 286-293.
Full text
/doc/issues-2015/15-03-01.pdf
Next article >>