Error autocorrection in rational approximation and interval estimates. [A survey of results.]

• Autorzy: Grigori Litvinov
• Języki publikacji: EN

Abstrakty

EN

The error autocorrection effect means that in a calculation all the intermediate errors compensate each other, so the final result is much more accurate than the intermediate results. In this case standard interval estimates (in the framework of interval analysis including the so-called a posteriori interval analysis of Yu. Matijasevich) are too pessimistic. We shall discuss a very strong form of the effect which appears in rational approximations to functions. The error autocorrection effect occurs in all efficient methods of rational approximation (e.g., best approxmations, Padé approximations, multipoint Padé approximations, linear and nonlinear Padé-Chebyshev approximations, etc.), where very significant errors in the approximant coefficients do not affect the accuracy of this approximant. The reason is that the errors in the coefficients of the rational approximant are not distributed in an arbitrary way, but form a collection of coefficients for a new rational approximant to the same approximated function. The understanding of this mechanism allows to decrease the approximation error by varying the approximation procedure depending on the form of the approximant. Results of computer experiments are presented. The effect of error autocorrection indicates that variations of an approximated function under some deformations of rather a general type may have little effect on the corresponding rational approximant viewed as a function (whereas the coefficients of the approximant can have very significant changes). Accordingly, while deforming a function for which good rational approximation is possible, the corresponding approximant’s error can rapidly increase, so the property of having good rational approximation is not stable under small deformations of the approximated functions. This property is “individual”, in the sense that it holds for specific functions.

Słowa kluczowe

EN

error autocorrection; rational approximation; algorithms; interval estimats; Primary 41A20; Secondary 65Gxx

• Wydawca: De Gruyter Open
• Czasopismo: Open Mathematics
• Rocznik: 2003
• Tom: 1
• Numer: 1
• Strony: 36-60

Daty

wydano

2003-03-01

online

2003-03-01

Twórcy

autor

Grigori Litvinov

• Independent University of Moscow B. Vlasievskii per.

Bibliografia

• [1] G.L. Litvinov et al., Mathematical Algorithms and Programs for Small Computers, Finansy i Statistika Publ., Moscow, 1981 (in Russian).
• [2] G.L. Litvinov and V.N. Fridman, Approximate construction of rational approximants, C. R. Acad. Bulgare Sci., 36, No. 1 (1981), 49–52 (in Russian).
• [3] I.A. Andreeva, G. L. Litvinov, A. Ya. Rodionov and V. N. Fridman, The PADE-program for Calculation of Rational Approximants. The Program Specification and its Code, Fond Algoritmov i Programm NIVTs AN SSSR, Puschino, 1985. (in Russian).
• [4] A.P. Kryukov, G.L. Litvinov and A.Ya. Rodionov, Construction of rational approximations by means of REDUCE, in: Proceeding of the ACM-SIGSAM Symposium on Symbolic and Algebraic Computation (SYMSAC 86), Univ. of Waterloo, Canada, 1986, pp. 31–33.
• [5] G.L. Litvinov, Approximate construction of rational approximations and an effect of error autocorrection, in: Mathematics and Modeling, NIVTs AN SSSR, Puschino, 1990, 99–141 (in Russian)
• [6] G.L. Litvinov, Error auto-correction in rational approximation, Interval Computations, 4 (6), (1992), 14–18.
• [7] G.L. Litvinov, Approximate construction of rational approximations and the effect of error autocorrection. Applications, Russian J. Math. Phys., 1, No. 3 (1994), 14–18.
• [8] G. Alefeld and J. Herzberger, Introduction to Interval Computations, Academic Press, New York-London, 1983.
• [9] R.B. Kearfott, Interval computations-introduction, uses, and resources, Euromath. Bulletin, 2(1), (1996), 95–112.
• [10] Y. Matijasevich, A posteriori version of interval analysis, in: Proc. Fourth Hung. Computer Sci. Conf., Topics in the Theoretical Basis and Applications of Computer Science, eds. M. Arato, I. Katai, L. Varga, Acad. Kiado, Budapest, 1986, pp. 339–349.
• [11] J.F. Hart et al., Computer Approximations, Wiley, New York, 1968.
• [12] V.V. Voevodin, Numerical Principles of Linear Algebra, Nauka Publ., Moscow, 1977 (in Russian).
• [13] Y.L. Luke, Computations of coefficients in the polynomials of Padé approximations by solving systems of linear equations, J. Comp. and Appl. Math., 6, No. 3 (1980), 213–218. http://dx.doi.org/10.1016/0771-050X(80)90028-5
• [14] Y.L. Luke, A note on evaluation of coefficients in the polynomials of Padé approximants by solving systems of linear equations, J. Comp. and Appl. Math., 8, No. 2 (1982), 93–99. http://dx.doi.org/10.1016/0771-050X(82)90061-4
• [15] G.E. Forsythe, M. Malcolm and C. Moler, Computer Methods for Mathematical Computations, Prentice-Hall, Englewood Cliffs, N. J., 1977.
• [16] G.A. Baker and P. Graves-Morris, Padé Approximants. Part I: Basic Theory. Part II: Extensions and Applications, Encyclopaedia of Mathematics and its Applications 13, 14, Addison-Wesley, Reading, Mass., 1981.
• [17] W.J. Cody, W. Fraser and J.F. Hart, Rational Chebyshev approximation using linear equations, Numer. Math., 12 (1968) 242–251. http://dx.doi.org/10.1007/BF02162506
• [18] E.W. Cheney, Introduction to Approximation Theory, McGraw-Hill, New York, 1966.
• [19] D.S. Lubinsky and A. Sidi, Convergence of linear and nonlinear Padé approximants from series of orthogonal polynomials, Trans. Amer. Math. Soc., 278, No. 1, (1983) 333–345. http://dx.doi.org/10.2307/1999319
• [20] S. Paszkowski, Zastosowania Numeryczne Wielomianów i Szeregów Czebyszewa, Panstwowe Wydawnictwo Naukowe, Warszawa, 1975 (in Polish).
• [21] H.J. Maehly, Rational approximations for transcendental functions, in: Proceedings of the International Conference on Information Processing, UNESCO, Butterworths, London, 1960, pp. 57–62.
• [22] C.K. Clenshaw and K. Lord, Rational approximations from Chebyshev series, in: Studies in Numerical Analysis, ed. B.K.P. Scaife, Academic Press, London and New York, 1974, pp. 95–113.
• [23] A.C. Hearn, REDUCE User’s Manual, Rand. Publ., 1982.
• [24] E.A. Volkov, Two-sided difference methods for solving linear boundary-value problems for ordinary differential equations, Proc. Steklov Inst. Math. 128 (1972), 131–152 (translated from Russian by AMS in 1974)
• [25] E.A. Volkov, Pointwise estimates of the accuracy of a difference solution of a boundary-value problem for an ordinary differential equation, Differential Equations, vol. 9, No. 4 (1973), 717–726 (in Russian; translated into English by Plenum Publ. Co. in 1975, 545–552).
• [26] B.S. Dobronets and V.V. Shaydurov, Two-sided numerical methods, Nauka Publ., Novosibirsk, 1990 (in Russian).
• [27] B.S. Dobronets, On some two-sided methods for solving systems of ordinary differential equations, Interval Computations, No 1(3) (1992), 6–21.
• [28] B.S. Dobronets, Interval method based on a posteriory estimates, Interval Computations, No. 3(5) (1992), 50–55.
• [29] L.F. Shampine, Ill-conditioned matrices and the integration of stiff ODEs, J. of Computational and Applied Mathematics 48 (1993), 279–292. http://dx.doi.org/10.1016/0377-0427(93)90025-7
• [30] Yu.V. Matijasevich, Real numbers and computers.-In: Kibernetika i Vychislitelnaya Tekhnika, vol. 2 (1986), 104–133 (in Russian).
• [31] G.L. Litvinov and A.S. Sobolevskii, Idempotent interval analysis and optimization problems, Reliable Computing, 7 (2001), 353–377. http://dx.doi.org/10.1023/A:1011487725803

Identyfikatory

DOI

10.2478/BF02475663