General algorithm for the numerical integration of functions of several variables

E. A. Bailov   ; M. B. Sikhov   ; N. Temirgaliev

Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 54 (2014) no. 7, pp. 1059-1077

Résumé

An algorithm is proposed for the numerical integration of an arbitrary function representable as a sum of an absolutely converging multiple trigonometric Fourier series. The resulting quadrature formulas have identical weights, and the nodes form a Korobov grid that is completely defined by two positive integers, of which one is the number of nodes. In the case of classes of functions with dominant mixed smoothness, it is shown that the algorithm is almost optimal in the sense that the construction of a grid of $N$ nodes requires far fewer elementary arithmetic operations than $N\ln\ln N$. Solutions of related problems are also given.

Bibliographie

[1] Korobov N. M., Teoretiko-chislovye metody v priblizhennom analize, izdanie vtoroe, pererabotannoe i dopolnennoe, MTsNMO, M., 2004

[2] Korobov N. M., Teoretiko-chislovye metody v priblizhennom analize, Fizmatgiz, M., 1963

[3] Hlawka E., Firneis F., Zinterhof P., Zahlentheoretische methoden in der numerischen mathematik, Wien–München–Oldenbourg, 1981

[4] Hua Loo Keng, Wang Yuan, Application of number theory of numerical analysis, Springer, New York, 1981

[5] Keipers L., Niderreiter G., Ravnomernoe raspredelenie posledovatelnostei, Nauka, M., 1985

[6] Sharygin I. F., “Otsenki snizu pogreshnosti kvadraturnykh formul na klassakh funktsii”, Zh. vychisl. matem. i matem. fiz., 3:3 (1963), 370–376

[7] Roth K. F., “Ogranicheniya dlya regulyarnosti”, Matematika: granitsy i perspektivy, FAZIS, M., 2005, 375–394

[8] Vasilkovskii G. V., Voznyakovskii G., “Obzor slozhnosti v srednei situatsii dlya lineinykh mnogomernykh problem”, Izv. vuzov. Matem., 2009, no. 4, 3–19

[9] Temirgaliev N., Bailov E. A., Zhubanysheva A. Zh., “Ob obschem algoritme chislennogo integrirovaniya periodicheskikh funktsii mnogikh peremennykh”, Dokl. AN, 416:2 (2007), 169–173

[10] Temirgaliev N., Kudaibergenov S. S., Shomanova A. A., “Primenenie tenzornykh proizvedenii funktsionalov v zadachakh chislennogo integrirovaniya”, Izv. RAN. Ser. matem., 73:2 (2009), 183–224 | DOI

[11] Voronin S. M., Temirgaliev N., “O kvadraturnykh formulakh, svyazannykh s divizorami polya gaussovykh chisel”, Matem. zametki, 46:2 (1989), 34–41

[12] Temirgaliev N., “Primenenie teorii divizorov k chislennomu integrirovaniyu periodicheskikh funktsii mnogikh peremennykh”, Matem. sb., 181:4 (1990), 490–505

[13] Korobov N. M., “O priblizhennom vychislenii kratnykh integralov”, Dokl. AN SSSR, 124:6 (1959), 1207–1210

[14] Bakhvalov N. S., “O priblizhennom vychislenii kratnykh integralov”, Vestn. MGU. Ser. matem. mekhan., 1959, no. 4, 3–18

[15] Temlyakov V. N., “Kvadraturnye formuly i vosstanovlenie po znacheniyam v uzlakh teoretiko-chislovykh setok dlya klassov funktsii maloi gladkosti”, Uspekhi matem. nauk, 40:4 (1985), 203–204

[16] Temlyakov V. N., “O vosstanovlenii periodicheskikh funktsii neskolkikh peremennykh po znacheniyam v uzlakh teoretiko-chislovykh setok”, Analysis Math., 12 (1986), 287–305 | DOI

[17] Temlyakov V. N., “Cubature formulas, discrepancy, and nonlinear approximation”, J. Complexity, 19 (2003), 352–391 | DOI

[18] Frolov K. K., “Otsenki sverkhu pogreshnosti kvadraturnykh formul na klassakh funktsii”, Dokl. AN SSSR, 231:4 (1976), 818–821

[19] Wang Yuan, “Number theoretic method in numerical analysis”, Contemporary Math., 77, 1988, 63–82 | DOI

[20] Bykovskii V. A., “Algoritm vychisleniya lokalnykh minimumov reshetok”, Dokl. AN, 399:5 (2004), 587–589

[21] Voronin S. M., “O kvadraturnykh formulakh”, Izv. RAN. Ser. matem., 58:4 (1994), 189–194

[22] Voronin S. M., “O postroenii kvadraturnykh formul”, Izv. RAN. Ser. matem., 59:4 (1995), 3–8

[23] Voronin S. M., Skalyga V. I., “O poluchenii algoritmov chislennogo integrirovaniya”, Izv. RAN. Ser. matem., 60:5 (1996), 13–18 | DOI

[24] Voronin S. M., Izbrannye trudy: Matematika, Izd-vo MGTU im. N. E. Baumana, M., 2006

[25] Temirgaliev N., “Ob effektivnosti algoritmov chislennogo integrirovaniya, svyazannykh s teoriei divizorov v krugovykh polyakh”, Matem. zametki, 1997, no. 2, 297–301 | DOI

[26] Temirgaliev N., “Teoretiko-chislovye metody i teoretiko-veroyatnostnyi podkhod k zadacham Analiza. Teoriya vlozhenii i priblizhenii, absolyutnaya skhodimost i preobrazovaniya ryadov Fure”, Vestn. Evraziiskogo un-ta, 1997, no. 3, 90–144

[27] Zhubanysheva A. Zh., Temirgaliev N., Temirgalieva Zh. N., “Primenenie teorii divizorov k postroeniyu tablits optimalnykh koeffitsientov kvadraturnykh formul”, Zh. vychisl. matem. i matem. fiz., 49:1 (2009), 14–25

[28] Sikhov M., Temirgaliev N., “Ob algoritme postroeniya ravnomerno raspredelennykh setok Korobova”, Matem. zametki, 87:6 (2010), 948–950 | DOI

[29] Temirgaliev N., “Kompyuternyi (vychislitelnyi) poperechnik. Algebraicheskaya teoriya chisel i garmonicheskii analiz v zadachakh vosstanovleniya (metod Kvazi–Monte Karlo). Teoriya vlozhenii i priblizhenii. Ryady Fure”, Vest. ENU, 2010, Spets. vypusk, posvyaschennyi nauchn. dostizheniyam matematikov ENU, 1–194

[30] Temirgaliev N., Nepreryvnaya i diskretnaya matematika v organicheskom edinstve v kontekste napravlenii issledovanii, Elektronnoe izdanie, In-t teor. matem. i nauchn. vychisl. Evraziiskii nats. un-t, Astana, 2012, 259 pp.

[31] Smolyak S. A., “Kvadraturnye i interpolyatsionnye formuly na tenzornykh proizvedeniyakh nekotorykh klassov funktsii”, Dokl. AN SSSR, 148:5 (1963), 1042–1045

[32] Smolyak S. A., Ob optimalnom vosstanovlenii funktsii i funktsionalov ot nikh, Dis. ... kand. fiz.-matem. nauk,, Otkrytyi fond bibl. mekhan.-matem. f-ta MGU, M., 1965

[33] Paskov S., “Average case complexity for multivariate integration for smooth functions”, J. Complexity, 1993, no. 9, 291–312 | DOI

[34] Wasilkowski G., Wozniakowski H., “Explicit cost bounds of algorithms for multivariate tensor product problems”, J. Complexity, 1995, no. 11, 1–56 | DOI

[35] Temirgaliev N., “Klassy $U_S(\beta,\theta,\alpha;\psi)$ i kvadraturnye formuly”, Dokl. AN, 393:5 (2003), 605–608

[36] Temirgaliev N., “Tenzornye proizvedeniya funktsionalov i ikh primeneniya”, Dokl. AN, 430:4 (2010), 460–465

[37] Temirgaliev N., Kudaibergenov S. S., Shomanova A. A., “Primeneniya kvadraturnykh formul Smolyaka k chislennomu integrirovaniyu koeffitsientov Fure i v zadachakh vosstanovleniya”, Izv. vuzov. Matem., 2010, no. 3, 52–71

[38] Borevich Z. I., Shafarevich I. R., Teoriya chisel, Nauka, M., 1985

[39] Gekke E., Lektsii po teorii algebraicheskikh chisel, Gostekhizdat, M.–L., 1940

[40] Aierlend K., Rouzen M., Klassicheskoe vvedenie v sovremennuyu teoriyu chisel, Mir, M., 1987

[41] Bukhshtab A. A., Teoriya chisel, Uchpedgiz, M., 1960

[42] Kassels Dzh., Vvedenie v geometriyu chisel, Mir, M., 1965

[43] Gauss C. F., Untersuchungen uber die eigenschaften der positiven ternaren quadratishen former von Ludvig August Seebeer, Gottingische gelehrte Anzeigen, 1831/Juli 9

[44] Prakhar K., Raspredelenie prostykh chisel, Mir, M., 1967

[45] Temlyakov V. N., “Priblizhenie funktsii s ogranichennoi smeshannoi proizvodnoi”, Tr. MIAN SSSR, 178, 1986, 3–113

[46] Dobrovolskii N. M., Klepikova N. L., Tablitsa optimalnykh koeffitsientov dlya priblizhennogo vychisleniya kratnykh integralov, Preprint No 63, Institut obschei fiziki AN SSSR. Prikl. matem. Otdel prikl. probl., M., 1990

[47] Solovev Yu. P., Sadovnichii V. A., Shavgulidze E. T., Belokurov V. V., Ellipticheskie krivye i sovremennye algoritmy teorii chisel, Izhevsk: In-t kompyuternykh issledovanii, M., 2003

[48] Lokutsievskii O. V., Gavrilov M. B., Nachala chislennogo analiza, TOO Yanus, M., 1995