1626435386-4ea3b7438ebb2e92437735aa9b26c4d2 (844201), страница 10
Текст из файла (страница 10)
. , (jm− 1)h), . . . ,i√(1)(d)q(jmh, . . . , jmh) + Lh d/2,nh(1)(d)qlow (x) ≡ qlow,m = max 0; min q((jm− 1)h, . . . , (jm− 1)h), . . . ,io√(1)(d)q(jmh, . . . , jmh) − Lh d/2 , x ∈ Xm , h = 1/µ.Ïóñòü äëÿ ïðîñòîòû f (x) ≡ 1 ïðè x ∈ Qd (â ýòîì ñëó÷àå q(x) = g(x))è g(x) ∈ C (1,...,1) (L, . . .
, L; Qd ). Ýòî ÷àñòíûé ñëó÷àé ìíîæåñòâà(1)(d)C r (L; Qd ) = C (r ,...,r ) L(1) , . . . , L(d) ; Qd46ôóíêöèé d ïåðåìåííûõ, ó êîòîðûõ (r(s) −1)-å ïðîèçâîäíûå ïî s-îé êîîðäèíàòå íåïðåðûâíû, à r(s) -å ïðîèçâîäíûå êóñî÷íî-íåïðåðûâíû è îãðàíè÷åíû ïî ìîäóëþ êîíñòàíòîé L(s) â êóáå Qd äëÿ s = 1, . . .
, d. Ôóíêöèÿg(x) ∈ C (1,...,1) (L, . . . , L; Qd ), â ÷àñòíîñòè, óäîâëåòâîðÿåò óñëîâèþ Ëèïøèöà ñ êîíñòàíòîé L ïî êàæäîé èç ïåðåìåííûõ.Ïðåäïîëîæèì, ÷òî ìàæîðàíòà qup (x) è ìèíîðàíòà qlow (x) ïðåäñòàâëÿþò ñîáîé êóñî÷íî-ïîñòîÿííûå ôóíêöèè, ïîñòðîåííûå ïî îïèñàííîìóâûøå ïðèáëèæåííîìó àëãîðèòìó, è èõ çíà÷åíèÿ qlow,m è qup,m áëèçêèê òî÷íûì çíà÷åíèÿì ìàêñèìóìà è ìèíèìóìà ôóíêöèè g(x) â ÿ÷åéêàõðàçáèåíèÿ (9.7). Íàéäåì îïòèìàëüíîå ÷èñëî ðàçáèåíèé µ ïî êàæäîé èçêîîðäèíàò îáëàñòè èíòåãðèðîâàíèÿ, ïðè êîòîðîì çàòðàòû s íà ðåàëèçàöèþ àëãîðèòìà 9.3 ìèíèìàëüíû. Ïóñòü a âðåìÿ, êîòîðîå çàòðà÷èâàåòñÿ íà ñðàâíåíèå äâóõ ÷èñåë, b âðåìÿ âû÷èñëåíèÿ ôóíêöèè g(x)â íåêîòîðîé òî÷êå, ïðè÷åì a b. Ó÷èòûâàÿ çàòðàòû íà ïîñòðîåíèåôóíêöèé qlow (x), qup (x) è íà ðåàëèçàöèþ îöåíêè (9.6), èìååìs = b(µ + 1)d + 2a(2d − 1)µd + (pa + (1 − p)(b + a))n ≈ b(n(1 − p) + (µ + 1)d ),ãäå p âåðîÿòíîñòü ïîïàäàíèÿ ñëó÷àéíîãî âåêòîðà ξ̂ â ïîäãðàôèê Glowìèíîðàíòû qlow (x):X X d qlow,mp = P(ξ̂ ∈ Glow ) =P{ξ ∈ Xm }P ξ (d+1) < qlow,m =hqup,mXmXmÇàìåòèì, ÷òîs ≈ bn 1 −XhXmd qlow,mqup,m!+ b(µ + 1)d = bnX qup,m − qlow,m Xmµd qup,m+√b dnL1 X 1+b(µ + 1) .
ŝ(µ) =× d+ b(µ + 1)d .µµqup,mdXmÇàìå÷àÿ, ÷òî âåëè÷èíàZ1 X 1dxF = d≈µqup,mg(x)QdXmïðèáëèæåííî ðàâíà êîíñòàíòå, íàéäåì òî÷êó ìèíèìóìà ôóíêöèè ŝ(µ).Äèôôåðåíöèðóÿ ýòó ôóíêöèþ, ïîëó÷àåì óðàâíåíèå√bLF n d−+ bd(µmin + 1)d−1 = 0.µ2min47q√Îòñþäà, ïðåäïîëàãàÿ, ÷òî µ + 1 ≈ µ, ïîëó÷àåì µmin ≈ d+1 LnF/ d. ðàáîòàõ [3, 9] íàìè áûëî ïðîâåäåíî òåñòèðîâàíèå àëãîðèòìà 9.3,ïðè ýòîì èñïîëüçîâàëèñü ôóíêöèè òåñòîâîé ñèñòåìû (4.1), (4.3) äëÿ ñëó÷àÿ áîëüøîãî ÷èñëà ñëàãàåìûõ K .10. Äèñêðåòíî-ñòîõàñòè÷åñêàÿ âåðñèÿ ìåòîäàâûáîðêè ïî âàæíîñòè10.1.
Çàâèñèìîñòü äèñïåðñèè îò øàãà ñåòêè. Ðàññìîòðèì àëãîðèòì (1.5), â êîòîðîì ïëîòíîñòü f (x) âûáèðàåòñÿ (ïî ïðèíöèïó âûáîðêèïî âàæíîñòè ñì. ðàçä. 2) â âèäå (6.3) (ñì. ïîäðàçä. 6.1, 6.5):ZLM |g(x)| dx,(10.1)f (x) = CLM |g(x)|, C = 1/c, c =Xïðè÷åì â êà÷åñòâå ïðèáëèæåíèÿ LM |g(x)| áåðåòñÿ ìóëüòèëèíåéíàÿ àïïðîêñèìàöèÿ ÑòðåíãàÔèêñà (ñì.
ïîäðàçä. 7.1, 7.2).ÓÒÂÅÐÆÄÅÍÈÅ 10.1. ÏóñòüT = min g(x) > 0 ïðè x ∈ Xx∈X(10.2)è g(x) ∈ C 2 (X). Òîãäà äëÿ äèñïåðñèè îöåíêè (1.5), (10.1) âûïîëíåíîíåðàâåíñòâîĤ 2 mesX c h4.(10.3)Dζ ≤TÄÎÊÀÇÀÒÅËÜÑÒÂÎ. Çàìåòèì, ÷òî22g(x) − LM g(x) + 2g(x)LM g(x) − LM g(x)g 2 (x)=.f (x)f (x)Ó÷èòûâàÿ ôîðìóëû (10.1) è (2.1), ïîëó÷àåìZg 2 (x)=f (x)ZZDζ =2g(x) − LM g(x)+ 2cI − c2 èf (x)2g(x) − LM g(x)− (I − c)2 .f (x)48Ó÷èòûâàÿ íåðàâåíñòâî (10.2) è òîò ôàêò, ÷òî áàçèñíûå ôóíêöèè (7.1)äëÿ χ(x) = β (l) (x) îáðàçóþò ðàçëîæåíèå åäèíèöû (ñì., íàïðèìåð, [4]),èìååìMXf (x) ≥ C min g(xi )χi (x) ≥ CT, x ∈ X.i=1,...,MÎòñþäàZDζ ≤i=12cρ2 (g, LM g)g(x) − LM g(x)≤ L2.f (x)T(10.4)Ñ ó÷åòîì ñîîòíîøåíèÿ (7.6) èìååì íåðàâåíñòâî (10.3).
Óòâåðæäåíèå 10.1äîêàçàíî.ÇÀÌÅ×ÀÍÈÅ 10.1.  ñëó÷àå, êîãäà ïîäûíòåãðàëüíàÿ ôóíêöèÿ g(x)ÿâëÿåòñÿ çíàêîïåðåìåííîé (ò. å. ñîîòíîøåíèå (10.2) íå âûïîëíåíî), ñïðàâåäëèâî íåðàâåíñòâî2 Z2Zg(x) − LM g(x)g(x) dx − I 2 ,+Dζ ≤f (x)è ïîëó÷åíèå çàâèñèìîñòè äèñïåðñèè Dζ îò h çàòðóäíåíî.ÇÀÌÅ×ÀÍÈÅ 10.2. Íåðàâåíñòâî òèïà (10.3) ìîæíî òàêæå ïîëó÷èòüêàê ñëåäñòâèå èçâåñòíîãî íåðàâåíñòâà (ñì., íàïðèìåð, [1])Dζ ≤(m2 − m1 )24ïðè 0 ≤ m1 ≤ q(x) ≤ m2 , x ∈ X.(10.5)Ïðåäïîëîæèì, ÷òî g(x) ∈ C 2 (X) è âûïîëíåíû ñîîòíîøåíèÿ (7.5), (10.2).Òîãäà g(x) Ĥch2sup − c ≤Tx∈X f (x)è, ñëåäîâàòåëüíî, äëÿ äîñòàòî÷íî ìàëîãî h âûïîëíåíî íåðàâåíñòâî (10.5)äëÿ m1 = c − Ĥch2 /T, m2 = c + Ĥch2 /T .
Äàëåå ïîëó÷àåì m2 − m1 =2Ĥh2 c/T èĤ 2 c2 h4Dζ ≤.(10.6)T2Ïîëó÷åííàÿ îöåíêà äèñïåðñèè íåñêîëüêî õóæå, ÷åì (10.3), ò. ê. äëÿ íåîòðèöàòåëüíûõ ôóíêöèé g(x) âûïîëíåíî c ≥ T mesX .ÇÀÌÅ×ÀÍÈÅ 10.3. Ðàññìîòðèì ñëó÷àé, êîãäà ïîäûíòåãðàëüíàÿ ôóíêöèÿ íåîòðèöàòåëüíà, íî íå îòäåëåíà îò íóëÿ (ò.
å. óñëîâèå (10.2) íå âûïîëíåíî). Çäåñü â ñîîòíîøåíèè (10.4) ìîæíî ïðèìåíèòü íåðàâåíñòâî49ÊîøèÁóíÿêîâñêîãîZDζ ≤2Z1/22g(x) − LM g(x)×≤g(x) − LM g(x) dxf (x)2 !1/2g(x) − LM g(x) dx×= ρL2 (g, LM g) (I2,3 − 2cI1,2 + c2 )1/2 ,f 2 (x)ãäå Iq,t = E g q (ξ) f t (ξ) . Îòñþäà ñëåäóåòÓÒÂÅÐÆÄÅÍÈÅ 10.2. Åñëè g(x) ∈ C 2 (X) è âåëè÷èíû I1,2 , I2,3îãðàíè÷åíû, òî äëÿ äèñïåðñèè îöåíêè (1.5), (10.1) âûïîëíåíî íåðàâåí1/2ñòâî Dζ ≤ Hh2 , ãäå H = Ĥ mesX (I2,3 − 2cI1,2 + c2 ).10.2. ¾Îòäåëåíèå¿ ïîäûíòåãðàëüíîé ôóíêöèè îò íóëÿ. Äëÿðàññìàòðèâàåìîãî ñëó÷àÿ íåîòðèöàòåëüíîé, íå îòäåëåííîé îò íóëÿïîäûíòåãðàëüíîé ôóíêöèè g(x) ìîæíî ïðèìåíèòü ñëåäóþùèé ïðèåì.Ïåðåïèøåì èíòåãðàë (1.4) â âèäå I = I˜ − T mes X , è áóäåì âû÷èñëÿòüìåòîäîì Ìîíòå-Êàðëî èíòåãðàëZZI˜ =g̃T (x) dx =g(x) + T dx,ZXXçäåñü T ôèêñèðîâàííàÿ êîíñòàíòà.
 ýòîì ñëó÷àå â îöåíêàõ òèïà(10.3), (10.6), ñ îäíîé ñòîðîíû, óâåëè÷èâàåòñÿ çíàìåíàòåëü (T èëè T 2 ),à ñ äðóãîé ñòîðîíû, óâåëè÷èâàåòñÿ ÷èñëèòåëü, ñîäåðæàùèé âåëè÷èíûc(T ) = I + T mesX è c2 (T ) (ñóììû âòîðûõ ïðîèçâîäíûõ ôóíêöèé g(x) èg̃(x) ñîâïàäàþò). Ïðè âûáîðå ¾âûñîòû ïîäúåìà¿ T ñëåäóåò ó÷èòûâàòü,÷òî âåðõíÿÿ ãðàíèöà äèñïåðñèè èìååò âèäD(T ) =H (I + T mesX)HI= H mesX +,TTH = (Ĥ)2 mesX h4(ñì. ïðàâóþ ÷àñòü íåðàâåíñòâà (10.3)); ïðè ýòîì D(T ) → const äëÿT → ∞.10.3. Âûáîð îïòèìàëüíîãî ÷èñëà ðàçáèåíèé.
 ñèëó òîãî, ÷òîh ∼ 1/M 1/d , èç ñîîòíîøåíèÿ (10.3) ñëåäóåò, ÷òî äèñïåðñèÿ Dζ óáûâàåò ñ ðîñòîì ÷èñëà óçëîâ M . Îäíàêî ïðè óâåëè÷åíèè M âîçðàñòàåòâðåìÿ ðåàëèçàöèè âåêòîðîâ ξ j ñîãëàñíî ïëîòíîñòè (10.1) â ñâÿçè ñ íåîáõîäèìîñòüþ âûáîðà íîìåðà m ïëîòíîñòè fm (x) ñîãëàñíî âåðîÿòíîñòÿì{P1 , . . . , PM } â àëãîðèòìå 6.1. Ïîýòîìó ìîæíî ïðåäïîëîæèòü ñóùåñòâîâàíèå îïòèìàëüíîãî ÷èñëà óçëîâ M , êîòîðîå ìèíèìèçèðóåò âåëè÷èíó50òðóäîåìêîñòè (1.9). Íàéäåì ýòî çíà÷åíèå â ïðåäïîëîæåíèè, ÷òî X ÿâëÿåòñÿ åäèíè÷íûì êóáîì Qd .  ýòîì ñëó÷àå ÷èñëî µ äåëåíèé ïî êàæäîéêîîðäèíàòå ïðè ïîñòðîåíèè ïðÿìîóãîëüíîé ñåòêè ñ øàãîì h = 1/µ îäèíàêîâî è M = µd .
Ïðåäïîëàãàåì òàêæå, ÷òî ïðè âûáîðå íîìåðà m âàëãîðèòìå 6.1 èñïîëüçîâàí êâàíòèëüíûé ìåòîä ñ µr êâàíòèëÿìè (ñì.àëãîðèòì 5.4). Òîãäà â ñàìîì ïëîõîì ñëó÷àå, êîãäà ïëîòíîñòü áëèçêà êðàâíîìåðíîé (ò. å. ïîäûíòåãðàëüíàÿ ôóíêöèÿ g(x) áëèçêà ê êîíñòàíòå),ñðåäíåå êîëè÷åñòâî íåîáõîäèìûõ âû÷èòàíèé âåðîÿòíîñòåé Pj èç ñòàíäàðòíîãî ÷èñëà α áóäåò µd /(2µr ). Òîãäà âåëè÷èíà t ðàâíà G1 µd−r /2+G2 ,ãäå G1 çàòðàòû íà îäíî âû÷èòàíèå Pj èç α, à êîíñòàíòà G2 âêëþ÷àåòçàòðàòû íà ìîäåëèðîâàíèå âåêòîðà ξ j ñîãëàñíî ïëîòíîñòè fm (x) è ïîäñ÷åò çíà÷åíèÿ q(ξ j ). Ñîãëàñíî (10.3) èìååì, ÷òî äèñïåðñèÿ Dζ îöåíèâàåòñÿ âåëè÷èíîé G3 /µ4 .
Ïîýòîìó ïðè âûáîðå îïòèìàëüíîãî µ ñëåäóåòìèíèìèçèðîâàòü ôóíêöèþ S̃(µ) = G4 (µd−r−4 + G5 µ−4 ). Ïðèðàâíèâàÿ êíóëþ ïðîèçâîäíóþ ýòîé ôóíêöèè è ó÷èòûâàÿ, ÷òî âåëè÷èíû d, r, µ, G5íåîòðèöàòåëüíû, ïîëó÷àåì, ÷òî óñëîâèåì ñóùåñòâîâàíèÿ îïòèìàëüíîãîêîëè÷åñòâà ðàçáèåíèé ïî êàæäîé êîîðäèíàòå áóäåò: d − r − 4 > 0, à ñàìîóñëîâíî-îïòèìàëüíîå çíà÷åíèå ðàâíîrd/(d−r)4G54G5d−rè Mopt =.µopt =d−r−4d−r−4 ðàáîòàõ [3, 9] íàìè áûëî ïðîâåäåíî òåñòèðîâàíèå àëãîðèòìà (1.5),(10.1); ïðè ýòîì èñïîëüçîâàëèñü ôóíêöèè òåñòîâîé ñèñòåìû (4.1), (4.3).11. Èñïîëüçîâàíèå ñóùåñòâåííîé âûáîðêè â ìåòîäåÌîíòå-Êàðëî11.1.
Ñóùåñòâåííàÿ âûáîðêà. Ðàññìîòðèì ñëåäóþùóþ çàäà÷ó.Ïóñòü èìååòñÿ íàáîð âûáîðî÷íûõ çíà÷åíèéΞ = (ξ 1 , . . . , ξ n ),n1(11.1)(èëè ýôôåêòèâíûé ÷èñëåííûé àëãîðèòì äëÿ ïîëó÷åíèÿ òàêîãî íàáîðà)d-ìåðíîãî ñëó÷àéíîãî âåêòîðà ξ ñ ïëîòíîñòüþ ðàñïðåäåëåíèÿ âèäàf (x) = H g(x), x ∈ X ⊆ Rd ,(11.2)ãäå H = const è g(x) çàäàííàÿ íåîòðèöàòåëüíàÿ ôóíêöèÿ, ïðè÷åìX çàìûêàíèå ìíîæåñòâà òåõ x ∈ Rd , äëÿ êîòîðûõ g(x) > 0. Òðåáóåòñÿ51âû÷èñëèòü âåëè÷èíóH = 1/I, ãäå I =Zg(x) dx,Xìåòîäîì Ìîíòå-Êàðëî, èñïîëüçóÿ íàáîð Ξ, êîòîðûé áóäåì íàçûâàòü ñóùåñòâåííîé âûáîðêîé.Òàêàÿ çàäà÷à âîçíèêàåò, íàïðèìåð, ïðè èçó÷åíèè ñòàöèîíàðíûõ ðàñïðåäåëåíèé öåïåé Ìàðêîâà, à òàêæå â ñëó÷àå, êîãäà ïî âûáîðî÷íûìçíà÷åíèÿì (11.1) ñòðîèòñÿ ïðèáëèæåíèå ïëîòíîñòè (11.2).11.2.
Àëãîðèòì ñ èñïîëüçîâàíèåì ñóùåñòâåííîé âûáîðêè.Ðåøåíèå ñôîðìóëèðîâàííîé çàäà÷è ñâîäèòñÿ ê âû÷èñëåíèþ èíòåãðàëà I ñ èñïîëüçîâàíèåì ñòàíäàðòíîãî àëãîðèòìà 1.1. Êàê îòìå÷àëîñü âïîäðàçä. 2.1, íàïðÿìóþ èñïîëüçîâàòü ïëîòíîñòü (11.2) â àëãîðèòìå 1.1íåâîçìîæíî, òàê êàê íàì íåèçâåñòíà êîíñòàíòà H . Ñëåäóþùèé ïðèåì,ïðåäëîæåííûé â ðàáîòå [24], ïîçâîëÿåò èñïîëüçîâàòü ñóùåñòâåííóþ âûáîðêó (11.1) äëÿ âû÷èñëåíèÿ èíòåãðàëà I .Ðàññìîòðèì ôóíêöèþ G(x), çàäàííóþ íà X , òàêóþ, ÷òî G(x) 6= 0ïðè Rx ∈ X , G(x) = 0 ïðè x 6∈ X è èçâåñòíî çíà÷åíèå J èíòåãðàëàJ = X G(x) dx.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
