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

Grigori Litvinov

Open Mathematics (2003)

  • Volume: 1, Issue: 1, page 36-60
  • ISSN: 2391-5455

Abstract

top
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.

How to cite

top

Grigori Litvinov. "Error autocorrection in rational approximation and interval estimates. [A survey of results.]." Open Mathematics 1.1 (2003): 36-60. <http://eudml.org/doc/268734>.

@article{GrigoriLitvinov2003,
abstract = {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.},
author = {Grigori Litvinov},
journal = {Open Mathematics},
keywords = {Primary 41A20; Secondary 65Gxx},
language = {eng},
number = {1},
pages = {36-60},
title = {Error autocorrection in rational approximation and interval estimates. [A survey of results.]},
url = {http://eudml.org/doc/268734},
volume = {1},
year = {2003},
}

TY - JOUR
AU - Grigori Litvinov
TI - Error autocorrection in rational approximation and interval estimates. [A survey of results.]
JO - Open Mathematics
PY - 2003
VL - 1
IS - 1
SP - 36
EP - 60
AB - 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.
LA - eng
KW - Primary 41A20; Secondary 65Gxx
UR - http://eudml.org/doc/268734
ER -

References

top
  1. [1] G.L. Litvinov et al., Mathematical Algorithms and Programs for Small Computers, Finansy i Statistika Publ., Moscow, 1981 (in Russian). 
  2. [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). Zbl0532.41019
  3. [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. [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. [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) Zbl0782.41021
  6. [6] G.L. Litvinov, Error auto-correction in rational approximation, Interval Computations, 4 (6), (1992), 14–18. Zbl0829.65008
  7. [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. [8] G. Alefeld and J. Herzberger, Introduction to Interval Computations, Academic Press, New York-London, 1983. Zbl0552.65041
  9. [9] R.B. Kearfott, Interval computations-introduction, uses, and resources, Euromath. Bulletin, 2(1), (1996), 95–112. 
  10. [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. [11] J.F. Hart et al., Computer Approximations, Wiley, New York, 1968. Zbl0174.20402
  12. [12] V.V. Voevodin, Numerical Principles of Linear Algebra, Nauka Publ., Moscow, 1977 (in Russian). Zbl0563.65010
  13. [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. [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. [15] G.E. Forsythe, M. Malcolm and C. Moler, Computer Methods for Mathematical Computations, Prentice-Hall, Englewood Cliffs, N. J., 1977. Zbl0361.65002
  16. [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. Zbl0468.30032
  17. [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 Zbl0169.19801
  18. [18] E.W. Cheney, Introduction to Approximation Theory, McGraw-Hill, New York, 1966. Zbl0161.25202
  19. [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 Zbl0518.30037
  20. [20] S. Paszkowski, Zastosowania Numeryczne Wielomianów i Szeregów Czebyszewa, Panstwowe Wydawnictwo Naukowe, Warszawa, 1975 (in Polish). 
  21. [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. Zbl0112.35303
  22. [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. Zbl0308.65010
  23. [23] A.C. Hearn, REDUCE User’s Manual, Rand. Publ., 1982. 
  24. [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) Zbl0308.65051
  25. [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. [26] B.S. Dobronets and V.V. Shaydurov, Two-sided numerical methods, Nauka Publ., Novosibirsk, 1990 (in Russian). 
  27. [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. [28] B.S. Dobronets, Interval method based on a posteriory estimates, Interval Computations, No. 3(5) (1992), 50–55. Zbl0829.65064
  29. [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 Zbl0798.65081
  30. [30] Yu.V. Matijasevich, Real numbers and computers.-In: Kibernetika i Vychislitelnaya Tekhnika, vol. 2 (1986), 104–133 (in Russian). 
  31. [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 Zbl1012.65065

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.