1626435386-4ea3b7438ebb2e92437735aa9b26c4d2 (844201), страница 14
Текст из файла (страница 14)
 ñèëó òîãî, ÷òî ïàðû (ξ m , ξ m,sim ) íåçàâèñèìû äëÿ ðàçíûõ m, èìååì)DΘ̄(M=nM1 XD g(ξ m ) + g(ξ m,sim ) .2n m=1(17.8)Îáîçíà÷èì ÷åðåç xm öåíòð êóáà Xm . Âû÷èòàÿ ïîñòîÿííóþ ïîä çíàêîìäèñïåðñèè, ïîëó÷àåì ðàâåíñòâîD g(ξ m ) + g(ξ m,sim ) = D g(ξ m ) − 2g(xm ) + g(ξ m,sim ) .(17.9)(d)(1)Ïðè ôèêñèðîâàííîé òî÷êå ξ m = (ξm , . . . , ξm ) ∈ Xm ââåäåì â ðàññìîòðåíèå ôóíêöèþ!(1)(1)jm − 1/2jm − 1/2(1)h(t) = g+ ξm −t, . . . ,µµ(d)jm − 1/2+µ(d)jm − 1/2(d)ξm−tµ!!.Î÷åâèäíî, ÷òî h(1) = g(ξ m ), h(0) = g(xm ), h(−1) = g(ξ m,sim ).  òåîðèè÷èñëåííîãî äèôôåðåíöèðîâàíèÿ (ñì., íàïðèìåð, [2]) õîðîøî èçâåñòíîïðåäñòàâëåíèåg(ξ m ) − 2g(xm ) + g(ξ m,sim ) = h(1) − 2h(0) + h(−1) = h00 (θ), |θ| ≤ 1.71Íåïîñðåäñòâåííûì äèôôåðåíöèðîâàíèåì ïîëó÷àåìdX00h (t) =(1)(1)jm − 1/2+µgxi xji,j=1(d)jm − 1/2+µ(1)ξmjm − 1/2−µ(d)(d)ξmjm − 1/2)−µ!t, .
. . ,! !t ×!!(j)(i)j−1/2j−1/2mm(j)(i)× ξm−.× ξm−µµ(1)(d)(i)(i)Òàê êàê ξm , . . . , ξm ∈ Xm , òî |ξm − (jm − 1/2)/µ| ≤ 1/(2µ). Ó÷èòûâàÿ, ÷òî g(x) ∈ C 2 (L; Qd ), ïîëó÷àåìLd2Ld2ïðè |t| ≤ 1 è |g(ξ m ) − 2g(xm ) + g(ξ m,sim )| ≤.24µ4µ2(17.10)Èç ñîîòíîøåíèÿ (17.9) èìååì|h00 (t)| ≤2D g(ξ m ) + g(ξ m,sim ) ≤ E g(ξ m ) − 2g(xm ) + g(ξ m,sim ) ≤Ld24µ22.Ïîäñòàâèâ ýòó îöåíêó â ñîîòíîøåíèå (17.8) è âñïîìèíàÿ, ÷òî n = 2M =2µd , ïîëó÷àåì)DΘ̄(M≤n1×M ×n2Ld24µ22=(Ld2 )2 24/d.32n1+4/dÏî àíàëîãèè ñ ðàññóæäåíèÿìè ðàçäåëà 1.3 èìååìPδ̂n(M )=δn(M ) n=2Mσ̂ (M )Ld2 21/2+2/d≤ Bε p≤ Bε8n1/2+2/dn/2!≥ 1 − ε.q(M )(n/2) DΘ̄n , ïðè÷åì ñïðàâåäëèâî íåðàâåíñòâîÇäåñü σ̂=σ̂ (M ) ≤ Ld2 22/d /(8n2/d ). Èç ëåììû 17.1 ñëåäóåò, ÷òî ïîëó÷åííûé ïî(M )ðÿäîê t = 1/2 + 2/d ÿâëÿåòñÿ äëÿ ïîãðåøíîñòè δ̂n ∼ n−t íåóëó÷øàåìûì (âåäü â ñîîòíîøåíèè (17.6) äëÿ ñëó÷àÿ r = (2, .
. . , 2) ÷èñëî r ðàâíîr = 2/d).(M )72Çàìåòèì, ÷òî àëãîðèòìû 17.1 è 17.2 äîïóñêàþò íåñêîëüêî íàçâàíèé.Âî-ïåðâûõ, ýòî ÷àñòíûå ñëó÷àè àëãîðèòìà ðàññëîåííîé âûáîðêè (ñì. àëãîðèòì 16.1) äëÿ n = M è n = 2M ñîîòâåòñòâåííî. Âî-âòîðûõ, â ñâÿçèñ íàëè÷èåì äèñêðåòèçàöèè îáëàñòè èíòåãðèðîâàíèÿ X , îïðåäåëÿåìîéðàçáèåíèåì X íà ìàëûå êóáû Xm âèäà (17.2), è ñ âûáîðîì îäíîé èëèäâóõ ñëó÷àéíûõ òî÷åê â êàæäîì ìàëîì êóáå ìîæíî îòíåñòè àëãîðèòìû 17.1 è 17.2 ê äèñêðåòíî-ñòîõàñòè÷åñêèì àëãîðèòìàì ÷èñëåííîãîèíòåãðèðîâàíèÿ. Â-òðåòüèõ, àëãîðèòìû 17.1 è 17.2 ÿâëÿþòñÿ ÷àñòíûìèñëó÷àÿìè ñëó÷àéíûõ êóáàòóðíûõ ôîðìóë (ñì.
äàëåå ðàçä. 21).Îòìåòèì, ÷òî ðåçóëüòàòû, ïðåäñòàâëåííûå â äàííîì ðàçäåëå è ïîëó÷åííûå â íà÷àëå øåñòèäåñÿòûõ ãîäîâ äâàäöàòîãî âåêà Í. Ñ. Áàõâàëîâûì(ñì., â ÷àñòíîñòè, ðàáîòó [7]), âûçâàëè áîëüøîé íàó÷íûé ðåçîíàíñ èïðèâåëè ê áóðíîìó ðàçâèòèþ (ãëàâíûì îáðàçîì, â çàïàäíîåâðîïåéñêèõíàó÷íûõ øêîëàõ) òåîðèè ñëîæíîñòè ÷èñëåííûõ àëãîðèòìîâ [8]. Êëàññè÷åñêîé çàäà÷åé â ýòîé òåîðèè ÿâëÿåòñÿ ñëåäóþùàÿ: ïðè ôèêñèðîâàííîì ÷èñëå îïåðàöèé n îïðåäåëèòü ìàêñèìàëüíûé ïîðÿäîê t ïîãðåøíîñòè δn ∼ n−t (â îáû÷íîì èëè âåðîÿòíîñòíîì ñìûñëå) çàäàííîãî êëàññàâû÷èñëèòåëüíûõ àëãîðèòìîâ.
Àëãîðèòìû ÷èñëåííîãî èíòåãðèðîâàíèÿÿâëÿþòñÿ íàèáîëåå óäà÷íûìè èëëþñòðàöèÿìè êîíñòðóêöèé è ìåòîäèêòåîðèè ñëîæíîñòè.18. Ìåòîä ñëîæíîé ìíîãîìåðíîé ñèììåòðèçàöèè18.1. Ìåòîä ïðîòèâîïîëîæíîé ïåðåìåííîé (îäíîìåðíûé ñëó÷àé). Ïóñòü òðåáóåòñÿ ïðèáëèæåííî âû÷èñëèòü îäíîêðàòíûé èíòåãðàëRbI0 = a g(x) dx ïî êîíå÷íîìó èíòåðâàëó a < x < b. Ðàññìîòðèì ñòàíäàðòíûé àëãîðèòì ìåòîäà Ìîíòå-Êàðëî (àëãîðèòì 1.1) ñ ïëîòíîñòüþf (x) ≡ 1/(b − a); x ∈ (a, b):nI0 = Eζ (0) ≈1 X (0)(0)ζ , ãäå ζj = (b − a)g(a + (b − a)αj )n j=1 j(18.1)è αj ðåàëèçàöèè ñòàíäàðòíîãî ñëó÷àéíîãî ÷èñëà (ò.
å. ñëó÷àéíîé âåëè÷èíû α, ðàâíîìåðíî ðàñïðåäåëåííîé â èíòåðâàëå (0, 1)). Ðàññìîòðèìòåïåðü ñèììåòðèçîâàííóþ ôóíêöèþ g (1) (x) = (g(x) + g(a + b − x)) /2 è73çàìåòèì, ÷òîZI0 =nbg (1) (x) dx = Eζ (1) ≈a1 X (1)(1)ζ , ãäå ζj = (b−a)g (1) (a+(b−a)αj ).n j=1 j(18.2)Àëãîðèòì (18.2) ñ îöåíêîé ζ (1) (âìåñòî ζ (0) èç (18.1)) íàçûâàåòñÿ ìåòîäîì ïðîòèâîïîëîæíîé ïåðåìåííîé èëè ìåòîäîì ñèììåòðèçàöèèïîäûíòåãðàëüíîé ôóíêöèè (â àíãëîÿçû÷íîé ëèòåðàòóðå äëÿ ýòîãî ïðèåìà èñïîëüçóåòñÿ òåðìèí ¾antithetic variates¿); ñì., íàïðèìåð, [1, 16].Íåñëîæíî ïîêàçàòü, ÷òî Dζ (1) ≤ Dζ (0) [1, 16]. Îäíàêî äëÿ ðàñ÷åòà îäíîãî çíà÷åíèÿ ζ (1) íàäî âû÷èñëèòü äâà çíà÷åíèÿ ôóíêöèè g(x).
Ïîýòîìó òðóäîåìêîñòü S (1) ìåòîäà ïðîòèâîïîëîæíîé ïåðåìåííîé (18.2) áóäåòìåíüøå òðóäîåìêîñòè àëãîðèòìà (18.1) òîëüêî òîãäà, êîãäà âåëè÷èíàDζ (1) ïî êðàéíåé ìåðå âäâîå ìåíüøå, ÷åì Dζ (0) . Îêàçûâàåòñÿ, äëÿ ìîíîòîííûõ ôóíêöèé g(x) ýòî âñåãäà âûïîëíåíî [1, 16].Äëÿ óìåíüøåíèÿ äèñïåðñèè ðàñ÷åòîâ ìîæíî òàêæå èñïîëüçîâàòüñëîæíóþ ñèììåòðèçàöèþ, ïðè êîòîðîé èíòåðâàë (a, b) ðàçáèâàåòñÿ íàêîíå÷íîå ÷èñëî ÷àñòåé M è äëÿ êàæäîé èç íèõ èñïîëüçóåòñÿ ìåòîä ïðîòèâîïîëîæíîé ïåðåìåííîé.18.2.
Ìíîãîìåðíàÿ ñëîæíàÿ ñèììåòðèçàöèÿ: îöåíêà äèñïåðñèè, òðóäîåìêîñòü.Ïóñòü òðåáóåòñÿ ïðèáëèæåííî âû÷èñëèòü èíòåRãðàë I = Qd g(x) dx ïî d-ìåðíîìó åäèíè÷íîìó êóáó X = Qd . Ðàññìîòðèì ñèììåòðèçîâàííóþ ôóíêöèþg (1) (x) = (g(x) + g(e − x))/2, ãäå e = (1, . . . , 1),è îöåíêè ζ (0) = g(α) è ζ (1) = g (1) (α); çäåñü òî÷êà α = R(α(1) , . . .
, α(d) )ðàâíîìåðíî ðàñïðåäåëåíà â êóáå Qd . Ó÷èòûâàÿ, ÷òî Qd g 2 (x) dx =Rg 2 (e − x) dx, èìååìQdDζ (0) −Dζ (1) =ZQd1=4Zg 2 (x) dx−14Z(g 2 (x)+2g(x)g(e−x)+g 2 (e−x)) dx =Qd1(g (x)−2g(x)g(e−x)+g (e−x)) dx =4Qd22Z(g(x)−g(e−x))2 dx ≥ 0,Qdò. å. ìíîãîìåðíûé âàðèàíò ìåòîäà ñèììåòðèçàöèè äàåò óìåíüøåíèå äèñïåðñèè. Ïîêàçàòü ÷èñëåííóþ ýôôåêòèâíîñòü (ò. å. óìåíüøåíèå äèñïåðñèè áîëåå, ÷åì â äâà ðàçà) â ìíîãîìåðíîì ñëó÷àå óäàåòñÿ òîëüêî ÷èñëåííî.74Ìíîãîìåðíûé àíàëîã ñëîæíîé ñèììåòðèçàöèè ñòðîèòñÿ ñëåäóþùèìîáðàçîì [9, 25].
Êàæäîå ðåáðî êóáà Qd äåëèòñÿ íà µ ðàâíûõ ÷àñòåé,à ñàì êóá íà M = µd ïîäêóáîâ Xm âèäà (17.2) (ñì. òàêæå ôîðìóëó (9.7)). Ðàçûãðûâàåì òî÷êó α è â êàæäîì Xm áåðåì ïî äâå òî÷êè(1)(l)ξ̂ m = (jm − e + α)/µ è ξ̂ m,sim = (jm − α)/µ, ãäå jm = (jm , . . . , jm ),(i)ïðè÷åì jm öåëûå ÷èñëà. Òî÷êè ξ̂ m è ξ̂ m,sim ñèììåòðè÷íû îòíîñèòåëüíî öåíòðà êóáà Xm . Êðîìå òîãî, òî÷êà ξ̂ m1 ìîæåò áûòü ïîëó÷åíàèç ξ̂ m2 ñ ïîìîùüþ öåëîãî ÷èñëà ñäâèãîâ âäîëü êîîðäèíàò íà h = 1/µ.Ðàññìîòðèì îöåíêóΘ̂(M ) =Mg(ξ̂ m ) + g(ξ̂ m,sim )1 Xηm ; ηm =.M m=12(18.3)Ñðàâíèâàÿ ñîîòíîøåíèÿ (17.7) è (18.3), îòìåòèì, ÷òî îöåíêó (18.3) ìîæíî ðàññìàòðèâàòü êàê ìîäèôèêàöèþ ìåòîäà çàâèñèìûõ èñïûòàíèé äëÿîïòèìàëüíîé êóáàòóðíîé ôîðìóëû Í. Ñ.
Áàõâàëîâà äëÿ g(x) ∈ C 2 (L; Qd ).Ïî àíàëîãèè ñ ðàññóæäåíèÿìè èç ïîäðàçä. 17.2 èçó÷èì äèñïåðñèþ îöåíêè (18.3) äëÿ äîñòàòî÷íî áîëüøèõ µ è M .ÓÒÂÅÐÆÄÅÍÈÅ 18.1. Åñëè g(x) ∈ C 2 (L; Qd ), òî äëÿ äèñïåðñèèîöåíêè (18.3) âûïîëíåíî íåðàâåíñòâîDΘ̂(M ) ≤L2 d4.64M 4/dÄÎÊÀÇÀÒÅËÜÑÒÂÎ. Çàìåòèì, ÷òî!2MX11(M )DΘ̂= 2E(ηm − Eηm )= 2MMm=1(18.4)MXcov(ηm1 , ηm2 ).m1 ,m2 =1Èñïîëüçóÿ íåðàâåíñòâî Øâàðöà, ïîëó÷àåì(M )DΘ̂1≤ 2MMXm1 ,m2pp1Dηm1 Dηm2 = 2M=1MXpDηm!2.(18.5)m=1Äàëåå, ïîâòîðÿÿ ñëîâî â ñëîâî ðàññóæäåíèÿ ïîäðàçä.
17.2 (ñì. ôîðìóëû(17.8)(17.10)), ïîëó÷àåì2 2 2E g(ξ̂ m ) − 2g(xm ) + g(ξ̂ m,sim )Ld≤;Dηm ≤48µ275çäåñü xm = (jm − e/2)/µ öåíòð êóáà Xm . Ïîäñòàâèâ ýòó îöåíêó âñîîòíîøåíèå (18.5), ñ ó÷åòîì òîãî, ÷òî M = µd , ïîëó÷àåì íåðàâåíñòâî(18.4). Óòâåðæäåíèå 18.1 äîêàçàíî.Ó÷èòûâàÿ íåðàâåíñòâî (18.4) è òî îáñòîÿòåëüñòâî, ÷òî ñðåäíåå âðåìÿ t ðåàëèçàöèè îäíîãî âûáîðî÷íîãî çíà÷åíèÿ îöåíêè (18.3) ïðîïîðöèîíàëüíî âåëè÷èíå 2M , ìîæíî ïðåäïîëîæèòü ñëåäóþùóþ çàâèñèìîñòüòðóäîåìêîñòè Ŝ (M ) ñîîòâåòñòâóþùåãî ìåòîäà Ìîíòå-Êàðëîn)I ≈ Θ̃(M=n1 X (M )Θ̂n i=1 iîò ïàðàìåòðîâ M è d: Ŝ (M ) ∼ Hd4 M 1−4/d .
Èç ïîñëåäíåãî ñîîòíîøåíèÿ ñëåäóåò, ÷òî äëÿ ðàçìåðíîñòåé d < 4 óâåëè÷åíèå M è µ ïðèâîäèò êóìåíüøåíèþ òðóäîåìêîñòè ìåòîäà ñëîæíîé ñèììåòðèçàöèè, à äëÿ d > 4,íàïðîòèâ, ïðèâîäèò ê óâåëè÷åíèþ òðóäîåìêîñòè. Íàì óäàëîñü ïîäòâåðäèòü ýòî îáñòîÿòåëüñòâî ñ ïîìîùüþ òåñòîâûõ ðàñ÷åòîâ, ïðîâåäåííûõ, âòîì ÷èñëå, ñ èñïîëüçîâàíèåì ôóíêöèé òåñòîâîé ñèñòåìû (4.1), (4.3).19. Äèñêðåòíî-ñòîõàñòè÷åñêàÿ âåðñèÿ ìåòîäàðàâíîìåðíîé âûáîðêè19.1. Ëåììà î ñîñòîÿòåëüíûõ îöåíêàõ.  ðÿäå ñëó÷àåâ óäàåòñÿ óìåíüøèòü âåëè÷èíó òðóäîåìêîñòè (1.9) àëãîðèòìà 1.1 ñ ïîìîùüþñëåäóþùåé ëåììû.(1)(s)ËÅÌÌÀ 19.1 [26].
Ïóñòü {(ηi , . . . , ηi ), i = 1, . . . , n} âûáîðêà èçs-ìåðíîãî ðàñïðåäåëåíèÿ ñ êîíå÷íûìè ñðåäíèìè çíà÷åíèÿìè(k)Eηi = Eη (k) (k = 1, . . . , s) è ïîëîæèòåëüíî îïðåäåëåííîé êîâàðèàöèîííîé ìàòðèöåé{K (k,m) ;k, m = 1, . . . , s}. Ïóñòü òàêæå(1)(s)Φ y ,...,y ôóíêöèÿ,èìåþùàÿ ïåðâûå ïðîèçâîäíûå∂Φ/∂y (k) = Φ(k) (k = 1, . . . , s) âî âñåõ òî÷êàõ íåêîòîðîé îêðåñòíîñòè(k)òî÷êè y0 = (Eη (1) , . . . , Eη (s) ) è Φ0 = Φ(k) (y0 ). Òîãäà åñëè ïî êðàéíåé(k)ìåðå îäíà èç âåëè÷èí Φ0 (k = 1, .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
