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

Grigori Litvinov

Open Mathematics, Tome 1 (2003), p. 36-60 / Harvested from The Polish Digital Mathematics Library

Résumé

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.

Détail

Publié le : 2003-01-01

Zbl 1087.41015

EUDML-ID : urn:eudml:doc:268734

Bibliographie

[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). | Zbl 0532.41019

[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) | Zbl 0782.41021

[6] G.L. Litvinov, Error auto-correction in rational approximation, Interval Computations, 4 (6), (1992), 14–18. | Zbl 0829.65008

[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. | Zbl 0552.65041

[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. | Zbl 0174.20402

[12] V.V. Voevodin, Numerical Principles of Linear Algebra, Nauka Publ., Moscow, 1977 (in Russian). | Zbl 0563.65010

[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. | Zbl 0361.65002

[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. | Zbl 0468.30032

[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 | Zbl 0169.19801

[18] E.W. Cheney, Introduction to Approximation Theory, McGraw-Hill, New York, 1966. | Zbl 0161.25202

[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 | Zbl 0518.30037

[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. | Zbl 0112.35303

[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. | Zbl 0308.65010

[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) | Zbl 0308.65051

[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. | Zbl 0829.65064

[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 | Zbl 0798.65081

[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 | Zbl 1012.65065