Received 10.12.2020; Revised 15.12.2020; Accepted 17.12.2020

Published 31.12.2020; First Online 22.01.2021

https://doi.org/10.34229/2707-451X.20.4.4

Previous  |  Full text (in Ukrainian)  |  Next

 

MSC 65-11

Optimal Numerical Integration

V.K. Zadiraka ^* ,   L.V. Luts ^* ,   I.V. Shvidchenko

V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv

^* Correspondence: This email address is being protected from spambots. You need JavaScript enabled to view it., This email address is being protected from spambots. You need JavaScript enabled to view it.

 

Introduction. In many applied problems, such as statistical data processing, digital filtering, computed tomography, pattern recognition, and many others, there is a need for numerical integration, moreover, with a given (often quite high) accuracy. Classical quadrature formulas cannot always provide the required accuracy, since, as a rule, they do not take into account the oscillation of the integrand. In this regard, the development of methods for constructing optimal in accuracy (and close to them) quadrature formulas for the integration of rapidly oscillating functions is rather important and topical problem of computational mathematics.

The purpose of the article is to use the example of constructing optimal in accuracy (and close to them) quadrature formulas for calculating integrals for integrands of various degrees of smoothness and for oscillating factors of different types and constructing a priori estimates of their total error, as well as applying to them of the theory of testing the quality of algorithms-programs to create a theory of optimal numerical integration.

Results. The optimal in accuracy (and close to them) quadrature formulas for calculating the Fourier transform, wavelet transforms, and Bessel transform were constructed both in the classical formulation of the problem and for interpolation classes of functions corresponding to the case when the information operator about the integrand is given by a fixed table of its values. The paper considers a passive pure minimax strategy for solving the problem. Within the framework of this strategy, we used the method of “caps” by N. S. Bakhvalov and the method of boundary functions developed at the V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine. Great attention is paid to the quality of the error estimates and the methods to obtain them.

The article describes some aspects of the theory of algorithms-programs testing and presents the results of testing the constructed quadrature formulas for calculating integrals of rapidly oscillating functions and estimates of their characteristics. The problem of determining the ranges of admissible values of control parameters of programs for calculating integrals with the required accuracy, as well as their best values for integration with the minimum possible error, is considered for programs calculating a priori estimates of characteristics.

Conclusions. The results obtained make it possible to create a theory of optimal integration, which makes it possible to reasonably choose and efficiently use computational resources to find the value of the integral with a given accuracy or with the minimum possible error.

 

Keywords: quadrature formula, optimal algorithm, interpolation class, rapidly oscillating function, quality testing.

 

Cite as: Zadiraka V.K., Luts L.V., Shvidchenko I.V. Optimal Numerical Integration. Cybernetics and Computer Technologies. 2020. 4. P. 47–64. (in Ukrainian) https://doi.org/10.34229/2707-451X.20.4.4

 

References

           1.     Sergienko I.V., Lytvyn O.M. New information operators in mathematical modeling. K.: Naukova dumka, 2018. 550 p. (in Ukrainian)

           2.     Bakhvalov N.S. Numerical methods. M.: Nauka, 1973. 1. 632 p. (in Russian)

           3.     Zadiraka V.K., Ivanov V.V. The issues of calculations optimization. K.: Obshhyestvo «Znanije» Ukrainskoj SSR, 1979. 36 p. (in Russian)

           4.     Ivanov V.V. Computer Computation Methods: A Reference Guide. K.: Naukova dumka, 1986. 584 p. (in Russian)

           5.     Bakhvalov N.S. On the optimality of linear methods for operator approximation in convex classes of functions. Zhurnal Vychislityel'noj Matyematiki i Matyematichyeskoj Fiziki. 1971. 11 (4). P. 244–249. (in Russian) https://doi.org/10.1016/0041-5553(71)90017-6

           6.     Daubechies I. Ten lectures on wavelets. Society for Industrial and Applied Mathematics, Philadelphia, Pennsylvania, 1992. 357 p. https://epubs.siam.org/doi/book/10.1137/1.9781611970104

           7.     Dremin I.M., Ivanov O.V.,Nechitailo V.A. Wavelets and their uses. Uspekhi Fizicheskikh Nauk and Russian Academy of Sciences. 2001. 44 (5). P. 447–478. http://dx.doi.org/10.1070/PU2001v044n05ABEH000918

           8.     Dyakonov V.P. Wavelets. From theory to practice. M.: SOLON-Pryess, 2002. 448 p. (in Russian) https://www.studmed.ru/dyakonov-vp-veyvlety-ot-teorii-k-praktike_3fd5e176555.html

           9.     Zadiraka V.K., Melnikova S.S., Luts L.V. Optimal Quadrature Formulas for Computation of Continuous Wavelet Transforms of Functions in Certain Classes. Journal of Automation and Information Sciences. 2010. 42 (5). P. 30–44. http://dx.doi.org/10.1615/JAutomatInfScien.v42.i5.40

       10.     Watson G.N. A Treatise on the Theory of Bessel Functions. Cambridge University Press, 1995. 814 p.

       11.     Zadiraka V.K., Luts L.V. Optimal for Accuracy Quadrature Formulas for Calculating of the Besel Transformation for Certain Classes of Sub-integral Functions. Cybernetics and Systems Analysis. 2021. 57 (2). P. 81–95. (in Ukrainian)

       12.     Stein E. Harmonic Analysis: Real-Variable Methods, Orthogonality, and Oscillatory Integrals. Princeton University Press,Princeton, NJ, 1993. 695 p. https://doi.org/10.1515/9781400883929-004

       13.     Zubov V.I. Bessel functions: Study guide. M.: Moskovskij Fiziko-Tyekhnichyeskij Institut, 2007. 51 p. (in Russian) https://mipt.ru/education/chair/mathematics/upload/0a5/Posobie_Zubov.pdf

       14.     Luts L.V. Estimation of Quality of Some Quadrature Formulas of Calculation of Integrals of Fast-Oscillating Functions. Shtuchnyj Intelekt. 2008. 4. P. 671–682. (in Ukrainian) http://dspace.nbuv.gov.ua/handle/123456789/7665

       15.     Zadiraka V.K. The theory of computing the Fourier transform. K.: Naukova dumka, 1983. 215 p. (in Russian)

       16.     Sergienko I.V., Zadiraka V.K., Lytvyn O. M., Melnikova S.S., Nechuiviter O.P. Optimal Algorithms for Calculating Integrals of Fast-Oscillating Functions and Their Application. K.: Naukova dumka, 2011. Vol. 2. 348 p. (in Ukrainian)

 

 

ISSN 2707-451X (Online)

ISSN 2707-4501 (Print)

Previous  |  Full text (in Ukrainian)  |  Next