1626435388-4a103190aea56b4a5b3ee742fd66e7b5 (844205), страница 30
Текст из файла (страница 30)
, xM }, êîýôôèöèåíòû {wm (g)} çàâèñÿò îò çíà÷åíèé g = (|g(x1 )|, . . . , |g(xM )|),à H2 íîðìèðóþùàÿ êîíñòàíòà.  ýòîì ñëó÷àå ñîîòâåòñòâóþùèé àëãîðèòì âûáîðêè ïîâàæíîñòè ìîæíî ïðè÷èñëèòü ê ñì. äàëåå ðàçä. 5.3.èíòåãðèðîâàíèÿäèñêðåòíî-ñòîõàñòè÷åñêèì àëãîðèòìàì ÷èñëåííîãîÇäåñü âîçíèêàþò òðåáîâàíèÿ "ìîäåëèðóåìîñòè"ïðèáëèæåíèÿ LM |g(x)|, ñâÿçàííûå ñíåîáõîäèìîñòüþ ñóùåñòâîâàíèÿ ýôôåêòèâíîãî àëãîðèòìà ðåàëèçàöèè âûáîðî÷íûõ çíà÷åíèé âåêòîðà ξ ñîãëàñíî ïëîòíîñòè f (x). Èç ñîîòíîøåíèÿ (3.18) ñëåäóåò, ÷òî äëÿ ìîäåëèðîâàíèÿ âåêòîðà ξ ìîæíî èñïîëüçîâàòü àëãîðèòì ìåòîäà ñóïåðïîçèöèè (àëãîðèòì1.20). Ïðè ýòîì òðåáóåòñÿ íåîòðèöàòåëüíîñòü êîýôôèöèåíòîâ {wm (g)}. Êðîìå òîãî, "áàçèñíûå"ôóíêöèè {χm (x)} äîëæíû áûòü ïðîïîðöèîíàëüíûìè ïëîòíîñòÿì ðàñïðåäåëåíèÿ ñëó÷àéíûõ âåêòîðîâ, äëÿ êîòîðûõ èìåþòñÿ ýôôåêòèâíûå àëãîðèòìû ðåàëèçàöèèâûáîðî÷íûõ çíà÷åíèé.Ïðîâåäåííûå èññëåäîâàíèÿ èçâåñòíûõ ïðèáëèæåíèé âèäà (3.18) ïîêàçàëè, ÷òî òðåáîâàíèÿì "ìîäåëèðóåìîñòè"íàèëó÷øèì îáðàçîì óäîâëåòâîðÿåò êîíå÷íî-ýëåìåíòíàÿ àïïðîêñèìàöèÿ ÑòðåíãàÔèêñà (ñì.
äàëåå ðàçä. 5.3). Çäåñü "áàçèñíûå"ôóíêöèè {χm (x)}ïðîïîðöèîíàëüíû B -ñïëàéíàì (ñì. ïîäðàçä. 1.8.5) è ñâîéñòâî "ìîäåëèðóåìîñòè"ïðèáëèæåíèÿ (3.18) ñëåäóåò èç óòâåðæäåíèÿ 1.17.3.2.5. Èñïîëüçîâàíèå ñóùåñòâåííîé âûáîðêè. Ðàññìîòðèì ñëåäóþùóþ çàäà÷ó.Ïóñòü èìååòñÿ íàáîð âûáîðî÷íûõ çíà÷åíèéΞ = (ξ 1 , . . . , ξ n ),n1(3.19)(èëè ýôôåêòèâíûé ÷èñëåííûé àëãîðèòì äëÿ ïîëó÷åíèÿ òàêîãî íàáîðà) lìåðíîãî ñëó÷àéíîãî âåêòîðà ξ ñ ïëîòíîñòüþ ðàñïðåäåëåíèÿ âèäàf (x) = A g(x), x ∈ X ⊆ Rl ,(3.20)ãäå A = const è g(x) çàäàííàÿ íåîòðèöàòåëüíàÿ ôóíêöèÿ, ïðè÷åì X çàìûêàíèåìíîæåñòâà òåõ x ∈ Rl , äëÿ êîòîðûõ g(x) > 0. Òðåáóåòñÿ âû÷èñëèòü âåëè÷èíóZA = 1/I, ãäå I =g(x) dx,Xñóùåñòâåííîé âû-ìåòîäîì Ìîíòå-Êàðëî, èñïîëüçóÿ íàáîð Ξ, êîòîðûé áóäåì íàçûâàòü.Òàêàÿ çàäà÷à âîçíèêàåò, íàïðèìåð, ïðè èçó÷åíèè ñòàöèîíàðíûõ ðàñïðåäåëåíèé öåïåé Ìàðêîâà, à òàêæå â ñëó÷àå, êîãäà ïî âûáîðî÷íûì çíà÷åíèÿì (3.19) ñòðîèòñÿ ïðèáëèæåíèå ïëîòíîñòè (3.20).Ðåøåíèå ñôîðìóëèðîâàííîé çàäà÷è ñâîäèòñÿ ê âû÷èñëåíèþ èíòåãðàëà I ñ èñïîëüçîâàíèåì ñòàíäàðòíîãî àëãîðèòìà 3.1.
Êàê îòìå÷àëîñü â ïîäðàçä. 3.2.1, íàïðÿìóþ èñïîëüçîâàòü ïëîòíîñòü (3.20) â àëãîðèòìå 3.1 íåâîçìîæíî, òàê êàê íàì íåèçâåñòíà êîíñòàíòàA. Ñëåäóþùèé ïðèåì ïîçâîëÿåò èñïîëüçîâàòü ñóùåñòâåííóþ âûáîðêó (3.19) äëÿ âû÷èñëåíèÿ èíòåãðàëà I .Ðàññìîòðèì ôóíêöèþ G(x), çàäàííóþ íà X , òàêóþ,R ÷òî G(x) 6= 0 ïðè x ∈ X , G(x) =0 ïðè x 6∈ X è èçâåñòíî çíà÷åíèå J èíòåãðàëà J = X G(x) dx. Ïåðåïèøåì ïîñëåäíååðàâåíñòâî â âèäåZG(x)J=f (x) dx = EζG ,IX g(x)áîðêîéãäå ζG = G(ξ)/g(ξ).Âû÷èñëÿåì âåëè÷èíó J/I ñîãëàñíî àëãîðèòìó 3.1, èñïîëüçóÿ ñóùåñòâåííûå âûáîðî÷íûå çíà÷åíèÿ (3.19):Àëãîðèòì 3.2.nnJ1X1 X G(ξ i )≈ ζ̄G,n =ζG,i =In i=1n i=1 g(ξ i )è ïîëàãàåìI≈Jζ̄G,n.(3.21)Ðàññìîòðèì âîïðîñ î ïîãðåøíîñòè àëãîðèòìà 3.2. Èç ñîîòíîøåíèé (3.5), (3.21) ñëåäóåò, ÷òî ñ âåðîÿòíîñòüþ 1 − ε âûïîëíåíîrJDζGζ̄G,n = + β, |β| < βε .InÑëåäîâàòåëüíî,I≈J/I + βJpI=,1+vDζG /nβIv=JrDζG.nÓ÷èòûâàÿ, ÷òî ïðè äîñòàòî÷íî áîëüøîì n âåëè÷èíà v ìàëà, è ðàçëàãàÿ ôóíêöèþ ϕ(v) =I/(1 + v) â ðÿä Òåéëîðà, ïîëó÷àåìr2DζGβI+ O(1/n).I ≈ I − Iv + O(v 2 ) = I −JnÈç ïîñëåäíåãî ñîîòíîøåíèÿ√ñëåäóåò, ÷òî ïîãðåøíîñòü àëãîðèòìà 3.2 èìååò ïî âåðîÿòíîñòè ïîðÿäîê ñõîäèìîñòè 1/ n, è ÷òî ïðè âûáîðå ôóíêöèè G(x) ñëåäóåò ìèíèìèçèðîâàòüâåëè÷èíóS1 = t1 × (DζG /J 2 ),ãäå t1 ñðåäíåå âðåìÿ ÝÂÌ, çàòðà÷èâàåìîå íà âû÷èñëåíèå îäíîé ðåàëèçàöèè ñëó÷àéíîéâåëè÷èíû ζG (ñì.
ñîîòíîøåíèå (3.21)). Ïî àíàëîãèè ñ äîêàçàòåëüñòâîì óòâåðæäåíèÿ 3.1íåñëîæíî ïîëó÷èòü, ÷òî ìíîæèòåëü (DζG /J 2 ) ìèíèìàëåí â ñëó÷àå, êîãäà G(x) = g(x),èç ÷åãî ñëåäóåò, ÷òî ôóíêöèþ G(x) æåëàòåëüíî âûáèðàòü áëèçêîé ê ôóíêöèè g(x). Âêà÷åñòâå G(x), â ÷àñòíîñòè, ìîæíî èñïîëüçîâàòü êîíå÷íî-ýëåìåíòíóþ àïïðîêñèìàöèþïîäûíòåãðàëüíîé ôóíêöèè g(x).Åñëè âûáðàòü ôóíêöèþ G(x)R òàê, ÷òî âûïîëíåíû ñîîòíîøåíèÿ: G(x) ≥ g(x) ïðèx ∈ X , G(x) = 0 ïðè x 6∈ X, X G(x) dx < ∞, è, êðîìå òîãî, èìåþòñÿ ýôôåêòèâíûåìîäåëèðóþùèå ôîðìóëû äëÿ ïîëó÷åíèÿ âûáîðî÷íûõ çíà÷åíèé êîìïîíåíò ñëó÷àéíîãîâåêòîðà ξ (1) , èìåþùåãî ïëîòíîñòü ðàñïðåäåëåíèÿf1 (x) = RG(x),G(x) dxX(3.22)òî ìîæíî ïðèìåíèòü ìåòîä èñêëþ÷åíèÿ (àëãîðèòì 1.24) ñ ìàæîðàíòîé g1 (x) = G(x) äëÿïîëó÷åíèÿ íîâûõ ñóùåñòâåííûõ âûáîðî÷íûõ çíà÷åíèé, èìåþùèõ ïëîòíîñòü ðàñïðåäåëåíèÿ (3.20). Äëÿ ìèíèìèçàöèè çàòðàò àëãîðèòìà 1.24 íóæíî âûáèðàòü ìàæîðàíòóG(x), áëèçêóþ ê g(x) (ñì.
ïîäðàçä. 1.7.2).Ñëåäóåò, îäíàêî, çàìåòèòü, ÷òî åñëè ñóùåñòâåííàÿ âûáîðêà (3.19) íå çàäàíà è ñòàâèòñÿ çàäà÷à âû÷èñëåíèÿ êîíñòàíòû A (èëè èíòåãðàëà I ), òî íå îáÿçàòåëüíî ïîëó÷àòüñóùåñòâåííûå âûáîðî÷íûå çíà÷åíèÿ (3.19) ñîãëàñíî àëãîðèòìó 1.24 è ïðèìåíÿòü àëãîðèòì 3.2, à ëó÷øå èñïîëüçîâàòü âûáîðêó ïî âàæíîñòè: âûáðàòü íåîòðèöàòåëüíóþôóíêöèþ G(x) (íå îáÿçàòåëüíî ìàæîðàíòó), áëèçêóþ ê g(x) è òàêóþ, ÷òî ìîäåëèðóþùèå ôîðìóëû, ñîîòâåòñòâóþùèå ñîâìåñòíîé ïëîòíîñòè (3.22) ÿâëÿþòñÿ ýôôåêòèâíûìè,è ïðèìåíèòü àëãîðèòì 3.1 ñ ïëîòíîñòüþ f (x), òîæäåñòâåííî ðàâíîé ôóíêöèè f1 (x) èç(3.22).3.3. ÂÛÁÎÐÊÀ ÏÎ ÂÀÆÍÎÑÒÈ ÏÎ ×ÀÑÒÈ ÏÅÐÅÌÅÍÍÛÕ3.3.1.
Ðàçáèåíèå ïåðåìåííûõ íà äâå ãðóïïû.  ðàçäåëàõ 3.33.5 ïðåäñòàâëåíû ìåòîäû óìåíüøåíèÿ äèñïåðñèè Dζ , îñíîâàííûå íà ðàçáèåíèè ïåðåìåííûõ x =(x1 , . . . , xl ) íà äâå ãðóïïû: u = (x1 , . . . , xk1 ), v = (xk1 +1 , . . . , xl ), 0 < k1 < l, è ïðåäñòàâëåíèè èíòåãðàëà (3.2) ôîðìóëîé ïîëíîãî ìàòåìàòè÷åñêîãî îæèäàíèÿ:ZZZ ZI = g(x) dx = q(x)f (x) dx =q(u, v) f (u, v) du dv =Z= Eq(γ) = Eq(ξ, η) = Eξ Eη (q(γ)|ξ) =Eη (q(γ)|u)fξ (u) du.(3.23)Çäåñü γ l-ìåðíûé ñëó÷àéíûé âåêòîð, ðàñïðåäåëåííûé ñîãëàñíî ïëîòíîñòè f (u, v) èñîñòàâëåííûé èç êîìïîíåíò k1 -ìåðíîãî âåêòîðà ξ = (ξ1 , . . .
, ξk1 ) è k2 -ìåðíîãî âåêòîðàη = (η1 , . . . , ηkR2 ), k1 + k2 = l. Êðîìå òîãî, â ñîîòíîøåíèè (3.23) ââåäåíû îáîçíà÷åíèÿEη (q(γ)|u) = q(u, v)fη (v|u) dv,Zfξ (u) = f (u, v) dv, fη (v|u) = f (u, v)/fξ (u).(3.24)Ïîñëåäíåå ñîîòíîøåíèå âîñïðîèçâîäèò ïðåäñòàâëåíèå (1.69), (1.70) äëÿ âåêòîðà γ =(ξ, η) (ñì. ïîäðàçä. 1.5.1). Ðàâåíñòâî (3.23) ïðîâåðÿåòñÿ ïðÿìîé ïîäñòàíîâêîé ôîðìóë(3.24) ñ ó÷åòîì òåîðåìû Ôóáèíè î ïðåäñòàâëåíèè äâîéíîãî èíòåãðàëà â âèäå ïîâòîðíîãî.3.3.2.
Âûáîðêà ïî âàæíîñòè ïî ïåðåìåííîé u.  ðÿäå ïðèëîæåíèé âîçíèêàåòñëåäóþùàÿ çàäà÷à. Èíòåãðàë (3.2) îöåíèâàåòñÿ ñ ïîìîùüþ ñòàíäàðòíîãî àëãîðèòìà 3.1,ïðè÷åì ïëîòíîñòü fη (v|u) èç ïðåäñòàâëåíèÿ (3.24) çàäàíà è òðåáóåòñÿ âûáðàòü ïëîòíîñòü fξ (u), ìèíèìèçèðóþùóþ âåëè÷èíó äèñïåðñèè σ 2 èç ôîðìóëû (3.4).  ýòîì ñëó÷àåàëãîðèòì 3.1 ñ îïòèìàëüíîé ïëîòíîñòüþ fξ ,min (u) íàçûâàþò âûáîðêîé ïî âàæíîñòè ïî÷àñòè ïåðåìåííûõ. Çàìåòèì, ÷òîZ 2Zg (u, v) dvdu2− I 2.σ =fξ (u)fη (v|u)Îáîçíà÷èìZg1 (u) =g 2 (u, v) dvfη (v|u)1/2è ïåðåïèøåì ôîðìóëó (3.4) â âèäå2Zσ =g12 (u) du− I 2.fξ (u)(3.25)Ïî àíàëîãèè ñ óòâåðæäåíèåì 3.1 äîêàæåì2Ìèíèìàëüíàÿ äèñïåðñèÿ σminâèäà (3.25) ðåàëèçóåòñÿ â ñëó÷àå,êîãäà ïëîòíîñòü fξ (u) ïðîïîðöèîíàëüíà ôóíêöèè g1(u), òî åñòüÓòâåðæäåíèå 3.4.g1 (u)=fξ ,min (u) = Rg1 (w) dwZg 2 (u, v) dvfη (v|u)1/2 ,Z Zg 2 (w, v) dvfη (v|w)1/2dw(3.26)è ðàâíà2σmin=2Zg1 (u) du− I2 =Z Zg 2 (u, v) dvfη (v|u)!21/2du− I 2.(3.27)Âûðàæåíèå (3.27) ïîëó÷àåòñÿ íåïîñðåäñòâåííîé ïîäñòàíîâêîé ñî2îòíîøåíèÿ (3.26) â (3.25).
Äàëåå, èç ôîðìóë (3.25) è (3.27) ñëåäóåò, ÷òî âåëè÷èíà σminÿâëÿåòñÿ äåéñòâèòåëüíî íàèìåíüøåé, òàê êàê äëÿ ëþáîé ïëîòíîñòè fξ (u) âåëè÷èíàÄîêàçàòåëüñòâî.2σ −2σminZ=g12 (u)du −fξ (u)2Zg1 (u) duÿâëÿåòñÿ äèñïåðñèåé (òî åñòü âåëè÷èíîé íåîòðèöàòåëüíîé) ñëó÷àéíîé âåëè÷èíû g1 (ξ)/fξ (ξ),ãäå âåêòîð ξ èìååò ïëîòíîñòü ðàñïðåäåëåíèÿ fξ (u).Ó÷èòûâàÿ òî îáñòîÿòåëüñòâî, ÷òî âûïîëíåíî ðàâåíñòâîZg(u, η)g(u, v) dv = E,fη (η|u)ìîæíî ñäåëàòü âûâîä î òîì, ÷òî óòâåðæäåíèå 3.4 ïîêàçûâàåò, ÷òî îïòèìàëüíûé âûáîðçíà÷åíèÿ ñëó÷àéíîé âåëè÷èíû ξ îñóùåñòâëÿåòñÿ èç ðàñïðåäåëåíèÿ ñ ïëîòíîñòüþ (3.26),ïðîïîðöèîíàëüíîé êîðíþ êâàäðàòíîìó èç ñðåäíåãî êâàäðàòà ñîîòâåòñòâóþùåãî "âêëàäà"â îöåíêó èíòåãðàëà (3.1).3.4.
ÌÅÒÎÄ ÌÀÒÅÌÀÒÈ×ÅÑÊÈÕ ÎÆÈÄÀÍÈÉ3.4.1. Ïîíèæåíèå ïîðÿäêà èíòåãðèðîâàíèÿ. Ðàññìîòðèì åùå îäíó âîçìîæíîñòüèñïîëüçîâàíèÿ ïðåäñòàâëåíèÿ (3.23) äëÿ óìåíüøåíèÿ ìíîæèòåëÿ Dζ èç (3.6). Ïðåäïîëîæèì, ÷òî âåëè÷èíà óñëîâíîãî ìàòåìàòè÷åñêîãî îæèäàíèÿZq1 (u) = Eη (q(γ)|u) = q(u, v)fη (v|u) dv(3.28)ëåãêî âû÷èñëÿåòñÿ àíàëèòè÷åñêè äëÿ êàæäîãî u. Èç ñîîòíîøåíèÿ (3.23) èìååìZI = q1 (u)fξ (u) du = Eζ (1) , ãäå ζ (1) = q1 (ξ).(3.29)Àëãîðèòì 3.3.Âû÷èñëÿåì èíòåãðàë (3.29) ïî ôîðìóëånI = Eζ(1)≈ζ̄n(1)1X=q1 (ξ i ),n i=1ãäå ñëó÷àéíûé âåêòîð ξ è ñîîòâåòñòâóþùèå âûáîðî÷íûå çíà÷åíèÿ {ξi} ðàñïðåäåëåíûñîãëàñíî ïëîòíîñòè fξ (u).Àëãîðèòì 3.3 íàçûâàþò ìåòîäîì ìàòåìàòè÷åñêèõ îæèäàíèé. Ýòîò àëãîðèòì ñîâïàäàåò ñ àëãîðèòìîì 3.1 äëÿ èíòåãðàëà (3.29) ðàçìåðíîñòè k1 , ìåíüøåé ÷åì l.
Ïîýòîìóàëãîðèòì 3.3 ÷àñòî íàçûâàþò.3.4.2. Óìåíüøåíèå äèñïåðñèè. Äîêàæåì ñëåäóþùååìåòîäîì ïîíèæåíèÿ ïîðÿäêà èíòåãðèðîâàíèÿÓòâåðæäåíèå 3.5.Ñïðàâåäëèâî ðàâåíñòâî ôîðìóëà ïîëíîé äèñïåðñèè:Dζ = Dζ (1) + Eξ Dη (q(γ)|ξ),(3.30)ò.å. ïîëíàÿ äèñïåðñèÿ ðàâíà ñóììå äèñïåðñèè óñëîâíîãî ìàòåìàòè÷åñêîãî îæèäàíèÿè ìàòåìàòè÷åñêîãî îæèäàíèÿ óñëîâíîé äèñïåðñèè.Èñïîëüçóÿ ñîîòíîøåíèÿ (3.4), (3.23), (3.24), èìååìZ ZZ(1)2Dζ − Dζ =q (u, v)f (u, v) du dv − q12 (u) fξ (u) du =Äîêàçàòåëüñòâî.Z "Z=q 2 (u, v)fη (v|u) dv −2 #Zq(u, v)fη (v|u) dvfξ (u) du = Eξ Dη (q(γ)|ξ).Èç ôîðìóëû (3.30) ñëåäóåò, ÷òî äèñïåðñèÿ óñëîâíîãî ìàòåìàòè÷åñêîãî îæèäàíèÿDζ íå ïðåâîñõîäèò ïîëíîé äèñïåðñèè Dζ .3.4.3. Î òðóäîåìêîñòè ìåòîäà ìàòåìàòè÷åñêèõ îæèäàíèé.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
