1626435386-4ea3b7438ebb2e92437735aa9b26c4d2 (844201), страница 11
Текст из файла (страница 11)
Ïåðåïèøåì ïîñëåäíåå ðàâåíñòâî â âèäåZG(x)J=f (x) dx = EζG ,IX g(x)ãäå ζG = G(ξ)/g(ξ).ÀËÃÎÐÈÒÌ 11.1 [24]. Âû÷èñëÿåì âåëè÷èíó J/I ñîãëàñíî àëãîðèòìó(1.5), èñïîëüçóÿ ñóùåñòâåííûå âûáîðî÷íûå çíà÷åíèÿ (11.1):nn1 X G(ξ i )J1XJζG,i =≈ ζ̄G,n =è ïîëàãàåì I ≈.In i=1n i=1 g(ξ i )ζ̄G,n(11.3)11.3. Ïîãðåøíîñòü è òðóäîåìêîñòü àëãîðèòìà 11.1.
Èç ñîîòíîøåíèé (1.6), (11.3) ñëåäóåò, ÷òî ñ âåðîÿòíîñòüþ 1 − ε âûïîëíåíîrJDζGζ̄G,n = + B, |B| < Bε .InÑëåäîâàòåëüíî,IJp=,I≈1+vJ/I + B DζG /n52BIv=JrDζG.nÓ÷èòûâàÿ, ÷òî ïðè äîñòàòî÷íî áîëüøîì n âåëè÷èíà v ìàëà, è ðàçëàãàÿôóíêöèþ ϕ(v) = I/(1 + v) â ðÿä Òåéëîðà, ïîëó÷àåìrB I 2 DζG2I ≈ I − Iv + O(v ) = I −+ O(1/n).JnÈç ïîñëåäíåãî ñîîòíîøåíèÿ ñëåäóåò, ÷òî ïîãðåøíîñòüàëãîðèòìà 11.1√èìååò ïî âåðîÿòíîñòè ïîðÿäîê ñõîäèìîñòè 1/ n, è ÷òî ïðè âûáîðåôóíêöèè G(x) ñëåäóåò ìèíèìèçèðîâàòü âåëè÷èíóS1 = t1 × (DζG /J 2 ),ãäå t1 ñðåäíåå âðåìÿ ÝÂÌ, çàòðà÷èâàåìîå íà âû÷èñëåíèå îäíîé ðåàëèçàöèè ñëó÷àéíîé âåëè÷èíû ζG (ñì. ñîîòíîøåíèå (11.3)).
Ïî àíàëîãèèñ äîêàçàòåëüñòâîì ëåììû 2.1 (ñì., íàïðèìåð, [1]) íåñëîæíî ïîëó÷èòü,÷òî ìíîæèòåëü (DζG /J 2 ) ìèíèìàëåí â ñëó÷àå, êîãäà G(x) = g(x), èç÷åãî ñëåäóåò, ÷òî ôóíêöèþ G(x) æåëàòåëüíî âûáèðàòü áëèçêîé ê ôóíêöèè g(x).  êà÷åñòâå G(x), â ÷àñòíîñòè, ìîæíî èñïîëüçîâàòü êîíå÷íîýëåìåíòíóþ àïïðîêñèìàöèþ ïîäûíòåãðàëüíîé ôóíêöèè g(x).11.4. Î öåëåñîîáðàçíîñòè ðåàëèçàöèè ñóùåñòâåííîé âûáîðêè. Åñëè âûáðàòü ôóíêöèþ G(x) òàê, ÷òî âûïîëíåíûñîîòíîøåíèÿ:RG(x) ≥ g(x) ïðè x ∈ X , G(x) = 0 ïðè x 6∈ X, X G(x) dx < ∞, è, êðîìåòîãî, èìåþòñÿ ýôôåêòèâíûå ìîäåëèðóþùèå ôîðìóëû äëÿ ïîëó÷åíèÿâûáîðî÷íûõ çíà÷åíèé êîìïîíåíò ñëó÷àéíîãî âåêòîðà ξ (1) , èìåþùåãîïëîòíîñòü ðàñïðåäåëåíèÿf1 (x) = RG(x),G(x) dxX(11.4)òî ìîæíî ïðèìåíèòü ìåòîä èñêëþ÷åíèÿ (àëãîðèòì 5.10) ñ ìàæîðàíòîég1 (x) = G(x) äëÿ ïîëó÷åíèÿ íîâûõ ñóùåñòâåííûõ âûáîðî÷íûõ çíà÷åíèé, èìåþùèõ ïëîòíîñòü ðàñïðåäåëåíèÿ (11.2).
Äëÿ ìèíèìèçàöèè çàòðàò àëãîðèòìà 5.10 íóæíî âûáèðàòü ìàæîðàíòó G(x), áëèçêóþ ê g(x)(ñì. ïîäðàçä. 5.6, à òàêæå ðàáîòû [1, 4]).Ñëåäóåò, îäíàêî, çàìåòèòü, ÷òî åñëè ñóùåñòâåííàÿ âûáîðêà (11.1)íå çàäàíà è ñòàâèòñÿ çàäà÷à âû÷èñëåíèÿ êîíñòàíòû H (èëè èíòåãðàëà I ), òî íå îáÿçàòåëüíî ïîëó÷àòü ñóùåñòâåííûå âûáîðî÷íûå çíà÷åíèÿ(11.1) ñîãëàñíî àëãîðèòìó 5.10 è ïðèìåíÿòü àëãîðèòì 11.1, à ëó÷øåèñïîëüçîâàòü âûáîðêó ïî âàæíîñòè (ñì.
ðàçä. 2, 10): âûáðàòü íåîòðèöàòåëüíóþ ôóíêöèþ G(x) (íå îáÿçàòåëüíî ìàæîðàíòó), áëèçêóþ êg(x) (â ÷àñòíîñòè, ïî àíàëîãèè ñ ñîîòíîøåíèåì (10.1), ìîæíî âçÿòü53G(x) = LM |g(x)|) è òàêóþ, ÷òî ìîäåëèðóþùèå ôîðìóëû, ñîîòâåòñòâóþùèå ïëîòíîñòè (11.4), ÿâëÿþòñÿ ýôôåêòèâíûìè, è ïðèìåíèòü àëãîðèòì1.1 ñ ïëîòíîñòüþ f (x), òîæäåñòâåííî ðàâíîé ôóíêöèè f1 (x) èç (11.4).12. Äèñêðåòíî-ñòîõàñòè÷åñêàÿ âåðñèÿ ìåòîäàâûäåëåíèÿ ãëàâíîé ÷àñòè12.1. Âûäåëåíèå ãëàâíîé ÷àñòè. Äîïóñòèì, ÷òî èçâåñòíà áëèçêàÿ ê Rg(x) ôóíêöèÿ g0 (x), äëÿ êîòîðîé ëåãêî âû÷èñëÿåòñÿ èíòåãðàëI0 = X g0 (x) dx (àíàëèòè÷åñêè èëè ÷èñëåííî ñ ìàëûìè çàòðàòàìè èâûñîêîé òî÷íîñòüþ). Òîãäà äëÿ óâåëè÷åíèÿ ýôôåêòèâíîñòè ðàñ÷åòîâïî ìåòîäó Ìîíòå-Êàðëî (1.5) ìîæíî èñïîëüçîâàòü ñòàíäàðòíûé ïðèåìâûäåëåíèÿ ãëàâíîé ÷àñòè (ñì., íàïðèìåð, [1, 16]), êîòîðûé îñíîâàí íàñîîòíîøåíèèZn1Xq(ξ j ) − q0 (ξ j ) ,(12.1)I = I0 +(g(x) − g0 (x)) dx ≈ I0 +n j=1Xãäå q0 (ξ) = g0 (ξ)/f (ξ).
Äèñïåðñèÿ îöåíêè (12.1) ðàâíà D q(ξ) − q0 (ξ) èìîæåò áûòü ìàëîé, åñëè g0 (x) õîðîøî àïïðîêñèìèðóåò g(x).12.2. Èñïîëüçîâàíèå ìóëüòèëèíåéíîé àïïðîêñèìàöèèÑòðåíãàÔèêñà.  êà÷åñòâå g0 (x) ðàññìîòðèì ìóëüòèëèíåéíîå ïðèáëèæåíèå èç ïîäðàçä. 7.1, 7.2:g0 (x) = LM g(x) =MXg(xi ) χi (x).(12.2)i=1Äëÿ ïðîñòîòû ðàññìîòðèì ñëó÷àé,åäèíè÷íûé êóáR êîãäà X d-ìåðíûéPMQd . Íåñëîæíî âû÷èñëèòü I0 = Qd LM g0 (x) dx ≈ hd i=1 g0 (xi ) (çíàêïðèáëèæåííîãî ðàâåíñòâà ñâÿçàí ñ òåì, ÷òî äëÿ óçëîâ, ðàñïîëîæåííûõ íà ãðàíèöå îáëàñòè èíòåãðèðîâàíèÿ Qd , íîñèòåëè ñîîòâåòñòâóþùèõ¾ôóíêöèé-êðûøåê¿ ÷àñòè÷íî ðàñïîëîæåíû âî âíåøíîñòè êóáà).  ñèëóñîîòíîøåíèé (7.5), (7.6) ôóíêöèÿ g(x) − g0 (x) = g(x) − LM g(x) ¾ðàâíîìåðíî ìàëà¿, è ïîýòîìó â êà÷åñòâå ïëîòíîñòè f (x) â àëãîðèòìå (12.1)ðàçóìíî âûáðàòü ïëîòíîñòü ðàâíîìåðíîãî ðàñïðåäåëåíèÿ:f (x) = 1 ïðè x ∈ X,f (x) = 0 èíà÷å.(12.3)ÓÒÂÅÐÆÄÅÍÈÅ 12.1.
Äëÿ äèñïåðñèè îöåíêè (12.1)(12.3) âûïîëíåíî íåðàâåíñòâîD q(ξ) − q0 (ξ) ≤ Ĥ 2 h4 ïðè g(x) ∈ C 2 (Qd ).(12.4)54ÄÎÊÀÇÀÒÅËÜÑÒÂÎ. Ñ ó÷åòîì ñîîòíîøåíèé (12.1)(12.3) èìååì2Z2Zg(x) − g0 (x) dxD q(ξ) − q0 (ξ) =−g(x) − g0 (x) dx ≤f (x)QdQdZ2≤g(x) − LM g(x) dx = ρ2L2 (Qd ) (g, LM g).QdÓ÷èòûâàÿ ñîîòíîøåíèå (7.6), ïîëó÷àåì íåðàâåíñòâî (12.4). Óòâåðæäåíèå 12.1 äîêàçàíî.12.3. Ñðàâíåíèå äèñêðåòíî-ñòîõàñòè÷åñêèõ âåðñèé àëãîðèòìîâ âûáîðêè ïî âàæíîñòè è âûäåëåíèÿ ãëàâíîé ÷àñòè.
Ñðàâ-íèâàÿ äèñêðåòíî-ñòîõàñòè÷åñêèå àëãîðèòìû (1.5), (10.1) è (12.1)(12.3),îòìåòèì, ÷òî: ïîðÿäêè óìåíüøåíèÿ äèñïåðñèè ïî øàãó ñåòêè h îäèíàêîâû (ñì.ñîîòíîøåíèÿ (10.3), (10.6), (12.4)), ïðè÷åì ïîëó÷åíèå íåðàâåíñòâà (12.4)íàìíîãî ïðîùå â ñðàâíåíèè ñ íåðàâåíñòâàìè (10.3), (10.6) (ñì. äîêàçàòåëüñòâà óòâåðæäåíèé 10.1, 12.1 è çàìå÷àíèå 10.2); àëãîðèòì (12.1)(12.3) áîëåå ïðîñò äëÿ ðåàëèçàöèè: íå òðåáóþòñÿóñëîâèÿ òèïà (10.2), ïðîñòî ðåàëèçóþòñÿ âûáîðî÷íûå çíà÷åíèÿ {ξ j } ñîãëàñíî ïëîòíîñòè (12.3) (â ñðàâíåíèè ñ ïëîòíîñòüþ (10.1), äëÿ êîòîðîéòðåáóåòñÿ èñïîëüçîâàíèå àëãîðèòìîâ 6.1, 7.1). ðàáîòàõ [3, 9] íàìè áûëî ïðîâåäåíî òåñòèðîâàíèå àëãîðèòìà (12.1),(12.2); ïðè ýòîì èñïîëüçîâàëèñü ôóíêöèè òåñòîâîé ñèñòåìû (4.1), (4.3).13. Èíòåãðèðîâàíèå ïî ÷àñòè îáëàñòè13.1.
Ðàçäåëåíèå îáëàñòè èíòåãðèðîâàíèÿ. Ðàññìîòðèì ñëåäóþùèé àíàëîãR àëãîðèòìà âûäåëåíèÿ ãëàâíîé ÷àñòè. Äîïóñòèì, ÷òî èíòåãðàë I = X g(x) dx ïðåäñòàâëåí â âèäå (1.4) è óäàåòñÿ âû÷èñëèòü(àíàëèòè÷åñêè èëè ÷èñëåííî ñ ìàëûìè çàòðàòàìè è âûñîêîé òî÷íîñòüþ)èíòåãðàëû ïî íåêîòîðîé ÷àñòè X2 îáëàñòè èíòåãðèðîâàíèÿ X ⊆ Rd :ZZq(x)f (x) dx = I2 èf (x) dx = i2 ,X2X2ãäå 0 < i2 < 1. Çäåñü ìû ïîëàãàåì, ÷òî f (x) = 0 ïðè x ∈/ X.Êàê ïðàâèëî, âûãîäíî ïðåäñòàâèòü èíòåãðàë (1.4) â âèäå ñóììûZZI = I2 +q(x)f (x) dx = I2 +i1 q(x)f1 (x) dx = Eζ (1) ,(13.1)X1X155ãäå X1 = X\X2 , i1 = 1 − i2 , ζ (1) = I2 + i1 q(ξ (1) ), à ξ (1) ñëó÷àéíûéâåêòîð, ðàñïðåäåëåííûé â X1 ñîãëàñíî óñå÷åííîé ïëîòíîñòè f1 (x) =f (x)/i1 . Çàìåíà àëãîðèòìà 1.1 íà àíàëîãè÷íûé àëãîðèòì, ñîîòâåòñòâóþùèé ïðåäñòàâëåíèþ (13.1), íàçûâàåòñÿ èíòåãðèðîâàíèåì ïî ÷àñòè îáëàñòè (ñì., íàïðèìåð, [1, 16]).
Åñëè îáëàñòü X2 áëèçêà ê X , òî ìîæíîñ÷èòàòü, ÷òî ìû âûäåëÿåì ãëàâíóþ ÷àñòü (ñì. ðàçä. 12). Îäíàêî îïèñàííûé ïðèåì âûãîäåí è òîãäà, êîãäà îáëàñòü X2 çàìåòíî ìåíüøå îáëàñòèX , ïðàâäà, è ïîíèæåíèå äèñïåðñèè â ýòîì ñëó÷àå îòíîñèòåëüíî íåâåëèêî (ñì. äàëåå óòâåðæäåíèå 13.1).13.2. Óìåíüøåíèå äèñïåðñèè. Öåëåñîîáðàçíîñòü ïðèìåíåíèÿ ìåòîäèêè èíòåãðèðîâàíèÿ ïî ÷àñòè îáëàñòè îáîñíîâûâàåòÓÒÂÅÐÆÄÅÍÈÅ 13.1. Ñïðàâåäëèâî ñîîòíîøåíèå Dζ (1) ≤ i1 Dζ .ÄÎÊÀÇÀÒÅËÜÑÒÂÎ. Ñîãëàñíî ôîðìóëå (2.1) è îïðåäåëåíèþ äèñïåðñèè èìååìZq 2 (x)f (x) dx − I 2i1 Dζ = i1=XZZ2= i1q 2 (x)f (x) dx − i1 I 2 ,q (x)f (x) dx + i1X1X2Dζ (1) = i21 Dq(ξ (1) ) = i21X1ZX12q(x)f (x) dx .Z2q (x)f (x) dx −= i12q(x)f1 (x) dx = Zq 2 (x)f1 (x) dx − i1ZX1X1Ðàññìîòðèì ðàçíîñòüi1 Dζ − Dζ(1)Z22Zq (x)f (x) dx − i1 I += i1X22q(x)f (x) dx .X1Çàìåòèì, ÷òîZ2Zq(x)f (x) dx = (I − I2 )2 èX2X1ãäå ∆ =q 2 (x)f (x) dx = ∆ + I22 /i2 ,RX2(q(x) − I2 /i2 )2 f (x) dx ≥ 0.
Ñëåäîâàòåëüíî,i1 Dζ − Dζ (1) = i1 (∆ + I22 /i2 ) − i1 I 2 + (I − I2 )2 = i1 ∆+√√+I22 /i2 + i2 I 2 − 2II2 = i1 ∆ + (I2 / i2 − i2 I)2 ≥ 0,56÷òî è òðåáîâàëîñü äîêàçàòü.13.3. Î ïðèìåíåíèè ìåòîäà èñêëþ÷åíèÿ äëÿ ìîäåëèðîâàíèÿóñå÷åííîãî ðàñïðåäåëåíèÿ. Åñëè èìååòñÿ àëãîðèòì ðåàëèçàöèè ñëó-÷àéíîãî âåêòîðà ξ ∈ X ñîãëàñíî ïëîòíîñòè f (x), òî äëÿ ñëó÷àéíîãîâåêòîðà ξ (1) ∈ X1 ⊂ X ìîæíî èñïîëüçîâàòü àëãîðèòì ìåòîäà èñêëþ÷åíèÿ äëÿ ìîäåëèðîâàíèÿ óñå÷åííîãî ðàñïðåäåëåíèÿ: ïðèíèìàåì ξ (1) = ξ ,åñëè ðåàëèçîâàííîå ñîãëàñíî ïëîòíîñòè f (x) çíà÷åíèå âåêòîðà ξ ïðèíàäëåæèò ïîäîáëàñòè X1 [1, 4]. Ïðè ýòîì ìåòîä èíòåãðèðîâàíèÿ ïî ÷àñòè îáëàñòè ïðàêòè÷åñêè íå äàåò âûèãðûøà, ò.
ê. óìåíüøåíèå äèñïåðñèè âèäà i1 σ 2 ñî÷åòàåòñÿ ñ íåîáõîäèìîñòüþ ìîäåëèðîâàíèÿ â ñðåäíåìP(ξ ∈ X)/P(ξ ∈ X1 ) = 1/i1 âûáîðî÷íûõ çíà÷åíèé âåêòîðà ξ .Áîëåå ïðåäïî÷òèòåëüíûì ÿâëÿåòñÿ ðîçûãðûø ñëó÷àéíîãî âåêòîðàξ (1) íåïîñðåäñòâåííî â îáëàñòè X1 ñîãëàñíî ïëîòíîñòè f1 (x).ÏÐÈÌÅÐ 13.1 [1]. Ïóñòü òðåáóåòñÿ âû÷èñëèòü îáúåì Ḡ òðåõìåðíîéôèãóðû G, îãðàíè÷åííîé ïîâåðõíîñòüþ (â ñôåðè÷åñêèõ êîîðäèíàòàõ(r, θ, φ))r = a + h t(θ, φ), ãäå − 1 ≤ t(θ, φ) ≤ 1 è a − h > 0.Îáîçíà÷èì ÷åðåç X2 è X âïèñàííûé â G è îïèñàííûé îêîëî G øàðû,ðàäèóñû è îáúåìû êîòîðûõ ðàâíû ñîîòâåòñòâåííî a − h, a + h è X̄2 , X̄ .Çàìåòèì, ÷òî èñêîìàÿ âåëè÷èíà ðàâíà èíòåãðàëóZḠ =χG (x1 , x2 , x3 ) dx1 dx2 dx3 ,Xãäå χG (x1 , x2 , x3 ) èíäèêàòîð ìíîæåñòâà G.
Ðàññìîòðèì ñíà÷àëà àëãîðèòì 1.1 ñî ñëó÷àéíûì âåêòîðîì ξ = (ξ1 , ξ2 , ξ3 ), èìåþùèì ïëîòíîñòüðàâíîìåðíîãî ðàñïðåäåëåíèÿ â X :f (x) =31=, x = (x1 , x2 , x3 ) ∈ X.4π(a + h)3X̄Ýòîò àëãîðèòì äàåò ïðèáëèæåíèåḠ = X̄ EχG (ξ) ≈nX̄ XχG (ξ i ).n i=1(13.2)Ìîäåëèðóþùèå ôîðìóëû äëÿ âûáîðî÷íûõ çíà÷åíèé êîìïîíåíò ñëó÷àéíîãî âåêòîðà ξ èìåþò âèä [1, 4]:ξ1 = r̂ sin θ̂ cos φ̂,ξ2 = r̂ sin θ̂ sin φ̂,57ξ3 = r̂ cos θ̂;(13.3)1/3r̂ = (a + h) α1 , cos θ̂ = 1 − 2α2 , φ̂ = 2πα3 .(13.4)Çàìåòèì, ÷òî ïðè ïîëó÷åíèè çíà÷åíèé χG (ξ) âû÷èñëåíèÿ (13.3) ìîæíîíå îñóùåñòâëÿòü, à ëèøü ïðîâåðÿòü óñëîâèår̂ ≤ a + h t(θ̂, φ̂),(13.5)ïðè âûïîëíåíèè êîòîðîãî χG (ξ) = 1 (èíà÷å χG (ξ) = 0).Âûäåëèì òåïåðü îáúåì X̄2 = (4/3)π(a − h)3 øàðà X2 :ZḠ = X̄2 +χG (x) dx,X1ãäå X1 = X\X2 = {(x1 , x2 , x3 ) : (a − h)2 < x21 + x22 + x23 < (a + h)2 }.Ðàññìîòðèì ñîîòâåòñòâóþùóþ ìîäèôèêàöèþ èíòåãðèðîâàíèÿ ïî ÷àñòèîáëàñòè:Ḡ = E X̄2 + X̄1 χG (ξ(1)nX̄1 X(1)) ≈ X̄2 +χG (ξ i ),n i=1(1)(1)(13.6)(1)ãäå ñëó÷àéíàÿ òî÷êà ξ (1) = (ξ1 , ξ2 , ξ3 ) ðàñïðåäåëåíà ðàâíîìåðíî âX1 ñîãëàñíî ïëîòíîñòèf1 (x) =13=, x ∈ X1 .34π ((a + h) − (a − h)3 ))X̄1Ïî àíàëîãèè ñ ðåàëèçàöèåé ðàâíîìåðíî ðàñïðåäåëåííîé ñëó÷àéíîé òî÷êè â øàðå ñ ïîìîùüþ ïåðåõîäà ê ñôåðè÷åñêèì êîîðäèíàòàì ìîæíîïîëó÷èòü ôîðìóëû äëÿ ðåàëèçàöèè ñëó÷àéíîé òî÷êè ξ (1) , ðàâíîìåðíîðàñïðåäåëåííîé â øàðîâîì ñëîå X1 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
