1626435388-4a103190aea56b4a5b3ee742fd66e7b5 (844205), страница 29
Текст из файла (страница 29)
ãë. 4). Äëÿ ðàçìåðíîñòåé 3 < l < 10 èìååò ñìûñë ðàññìàòðèâàòü ñìåøàííûå äèñêðåòíî-ñòîõàñòè÷åñêèåìåòîäû ÷èñëåííîãî èíòåãðèðîâàíèÿ (ñì. äàëåå ðàçä. 3.2 è 3.6). Ðÿä çàìå÷àíèé î ñîîòíîøåíèè êóáàòóðíûõ ôîðìóë è ìåòîäà Ìîíòå-Êàðëî ñôîðìóëèðîâàí òàêæå â ðàçäåëàõ3.9, 3.10.3.1.3. Òðóäîåìêîñòü ìåòîäà Ìîíòå-Êàðëî. Âàæíûì ïðåèìóùåñòâîì ìåòîäàÌîíòå-Êàðëî ÿâëÿåòñÿ ïðîñòîòà ó÷åòà âû÷èñëèòåëüíûõ çàòðàò, ïîçâîëÿþùàÿ ïðîâîäèòü îïòèìèçàöèþ àëãîðèòìà 3.1 çà ñ÷åò ñïåöèàëüíîãî âûáîðà ïëîòíîñòè f (x). Äåéñòâèòåëüíî, çàòðàòû íà âû÷èñëåíèå âåëè÷èíû ζ̄n ðàâíû s = nt, ãäå t ñðåäíåå âðåìÿäëÿ ïîëó÷åíèÿ îäíîãî âûáîðî÷íîãî çíà÷åíèÿ ζi ñëó÷àéíîé âåëè÷èíû ζ (çàòðàòàìè íàñóììèðîâàíèå√ è äåëåíèå íà n â ôîðìóëå (3.3) ìîæíî ïðåíåáðå÷ü). Ïîëàãàÿ, ÷òî âåëè÷èíà βε σ/ n èç (3.5) îïðåäåëÿåò ïîãðåøíîñòü δn :βε σδn = √ ,nïîëó÷àåì, ÷òî ïðè çàäàííîì óðîâíå ïîãðåøíîñòè δn = δ = const è ïðè ôèêñèðîâàííîìε âûïîëíåíîβ 2 (ε)n = Aσ 2 ; A =.δ2Ñëåäîâàòåëüíî, ÷èñëî èñïûòàíèé n ïðîïîðöèîíàëüíî äèñïåðñèè σ 2 = Dζ , è ïîýòîìóìîæíî çàìåíèòü âåëè÷èíó s íàS = t × Dζ.(3.6)òðóäîåìêîñòüþ ìåòîäà Ìîíòå-ÊàðëîÂåëè÷èíà (3.6), íàçûâàåìàÿ, ÿâëÿåòñÿ êðèòåðèåì êà÷åñòâà àëãîðèòìà 3.1.
Òîò âûáîð ïëîòíîñòè f (x) ñ÷èòàåòñÿ ëó÷øå, äëÿ êîòîðîãîâåëè÷èíà S ìåíüøå.√Íåèçâåñòíàÿ âåëè÷èíà σ = Dζ èç (3.5) äîïóñêàåò ýôôåêòèâíîå îöåíèâàíèå ñ ïîìîùüþ ðåàëèçóåìûõ âûáîðî÷íûõ çíà÷åíèé ζ1 , . . . , ζn . Ïðîñòåéøåå ïðèáëèæåíèå íåñëîæíîïîëó÷èòü èç ñîîòíîøåíèÿ (3.2) äëÿ q(u) = u2 :n22Dζ = Eζ − (Eζ) ≈D(1)n1X 2=ζ −n i=1 in1Xζin i=1!2.(3.7)Åñëè â (3.7) òðàêòîâàòü ζ1 , . . . , ζn êàê íåçàâèñèìûå è îäèíàêîâî ðàñïðåäåëåííûå (òàêæå êàê ñëó÷àéíàÿ âåëè÷èíà ζ ) ñëó÷àéíûå âåëè÷èíû, òî íåñëîæíî ïîêàçàòü, ÷òî1(1)Dζ.(3.8)EDn = 1 −n(1)Äåéñòâèòåëüíî, EDn = Eζ 2 −Eζ̄n2 = Dζ −Dζ̄n , òàê êàê Eζ̄n = Eζ . Ó÷èòûâàÿ, ÷òî Dζ̄n =(1)Dζ/n, ïîëó÷àåì (3.8). Íåñìåùåííóþ îöåíêó äèñïåðñèè ìîæíî ïîëó÷èòü, ðàçäåëèâ Dníà (1 − 1/n):nD(2)n1 X 21=ζi −n − 1 i=1n(n − 1)nX!2ζi.(3.9)i=1√Îòìåòèì, ÷òî çàìåíà√ â ñîîòíîøåíèè (3.5) âåëè÷èíû σ íà 4Dn èçìåíÿåò "äîâåðèòåëüíóþ ãðàíèöó"βε σ/ n íà âåëè÷èíó ïîðÿäêà O(1/n), åñëè Eζ < +∞.Èìååòñÿ ðÿä ïðèåìîâ, ïîçâîëÿþùèõ óìåíüøàòü äèñïåðñèþ Dζ äëÿ ñëó÷àéíîé âåëè÷èíû ζ èç (3.2) (ñì.
äàëåå ðàçäåëû 3.23.9). Ñïîñîáû óìåíüøåíèÿ âðåìåíè t íàïðàâëåíû,êàê ïðàâèëî, íà îïòèìèçàöèþ ìîäåëèðîâàíèÿ ñëó÷àéíîãî âåêòîðà ξ .3.2. ÂÛÁÎÐÊÀ ÏÎ ÂÀÆÍÎÑÒÈ3.2.1. Òåîðåìà î ìèíèìóìå äèñïåðñèè.  ðàçäåëàõ 3.23.9 èññëåäóþòñÿ âîçìîæíîñòè óìåíüøåíèÿ ìíîæèòåëÿ Dζ = σ 2 â âûðàæåíèè äëÿ òðóäîåìêîñòè S = t × Dζàëãîðèòìà 3.1 (ñì.
ñîîòíîøåíèÿ (3.4), (3.6)). Âî-ïåðâûõ, âûÿñíèì, äëÿ êàêîé ïëîòíîñòèf (x) äèñïåðñèÿ (3.4) ñëó÷àéíîé âåëè÷èíû ζ èç (3.2) ÿâëÿåòñÿ ìèíèìàëüíîé.2Óòâåðæäåíèå 3.1.σminf (x)íîñòüðåàëèçóåòñÿ â ñëó÷àå, êîãäà ïëîòÌèíèìàëüíàÿ äèñïåðñèÿïðîïîðöèîíàëüíà ìîäóëþ ïîäûíòåãðàëüíîé ôóíêöèè:|g(x)|,|g(y)| dy(3.10)2|g(x)| dx − I 2 .(3.11)fmin (x) = Rè ðàâíà2σminZ=Äîêàçàòåëüñòâî. Ñîîòíîøåíèå (3.11) ïîëó÷àåòñÿ íåïîñðåäñòâåííîé ïîäñòàíîâêîéâûðàæåíèÿ (3.10) â (3.4) ñ ó÷åòîì òîãî, ÷òî g 2 (x)/|g(x)| = |g(x)|.
Äàëåå, èç ôîðìóë (3.4)2è (3.11) ñëåäóåò, ÷òî äèñïåðñèÿ σminÿâëÿåòñÿ äåéñòâèòåëüíî íàèìåíüøåé, òàê êàê äëÿëþáîé ïëîòíîñòè f (x) âåëè÷èíàZ 2g (x)222σ − σmin =dx − I −f (x)! ZZ2Z2g 2 (x)2−|g(x)| dx − I=dx −|g(x)| dxf (x)ÿâëÿåòñÿ äèñïåðñèåé (òî åñòü âåëè÷èíîé íåîòðèöàòåëüíîé) ñëó÷àéíîé âåëè÷èíû |g(ξ)|/f (ξ),ãäå ñëó÷àéíûé âåêòîð ξ èìååò ïëîòíîñòü ðàñïðåäåëåíèÿ f (x).Ñôîðìóëèðóåì òàêæå âàæíîå ñëåäñòâèå óòâåðæäåíèÿ 3.1 äëÿ ñëó÷àÿ çíàêîïîñòîÿííîé ïîäûíòåãðàëüíîé ôóíêöèè g(x).Óòâåðæäåíèå 3.2.Ïóñòüg(x) ≥ 0Åñëè2òî Dζ = σmin= 0.ïðèf (x) = g(x)/Ix ∈ Rl .ïðèx ∈ Rl ,(3.12)(3.13)Ïëîòíîñòè (3.10) è (3.13) íå èñïîëüçóåòñÿäëÿ âû÷èñëåíèÿ èíòåãðàëà I ïî òîé ïðèR÷èíå, ÷òî íàõîæäåíèå âåëè÷èíû |g(y)| dy èç ñîîòíîøåíèÿ (3.10) ïðåäñòàâëÿåò ñîáîéçàäà÷ó, ýêâèâàëåíòíóþ ïî ñëîæíîñòè èñõîäíîé çàäà÷å (3.1) (â ñëó÷àå (3.12) â òî÷íîñòèýêâèâàëåíòíóþ).
Áîëåå òîãî, äëÿ ñëó÷àÿ (3.12) àëãîðèòì 3.1 "âûðîæäàåòñÿ"èïðèáëèPnæåííîå ðàâåíñòâî (3.3) ïðåâðàùàåòñÿ â òîæäåñòâî I = (1/n) × i=1 I .3.2.2. Âûáîðêà ïî âàæíîñòè è åå ïîãðåøíîñòü. Èç óòâåðæäåíèé 3.1 è 3.2 ìîæíîñäåëàòü âûâîä, ÷òî â ðÿäå ñëó÷àåâ ìîæíî äîáèòüñÿ óìåíüøåíèÿ òðóäîåìêîñòè S =t × Dζ àëãîðèòìà 3.1, âûáèðàÿ ïëîòíîñòü f (x), áëèçêîé (ñ òî÷íîñòüþ äî ïîñòîÿííîãîìíîæèòåëÿ H1 ) ê ôóíêöèè (3.10):f (x) ≈ H1 R|g(x)|.|g(y)| dy(3.14)âûáîðêîé ïî âàæíîñòèÀëãîðèòì 3.1 â ýòîì ñëó÷àå íàçûâàåòñÿ, ÷òî ñîîòâåòñòâóåò àíãëèéñêîìó òåðìèíó".
Òàêîå íàçâàíèå îáúÿñíÿåòñÿ òåì, ÷òî åñëèf (x) ïðîïîðöèîíàëüíà ìîäóëþ ïîäûíòåãðàëüíîé ôóíêöèè g(x), òî â òåõ ÷àñòÿõ îáëàñòè X , â êîòîðûõ |g(x)| áîëüøå è âêëàä êîòîðûõ â èíòåãðàë I áîëåå ñóùåñòâåíåí, áóäåòâûáèðàòüñÿ áîëüøå ñëó÷àéíûõ òî÷åê {ξ i }.Ñîîòíîøåíèå (3.14) ïîçâîëÿåò íàäåÿòüñÿ ïîëó÷èòü àëãîðèòì ìåòîäà Ìîíòå-Êàðëî(3.3) ñ ìàëîé äèñïåðñèåé. Ïðîäåìîíñòðèðóåì ýòî ñíà÷àëà äëÿ ñëó÷àÿ (3.12). Îáîçíà÷èì÷åðåç X çàìûêàíèå ìíîæåñòâà òåõ x ∈ Rl , äëÿ êîòîðûõ g(x) > 0. Ïîëàãàåì òàêæå, ÷òîf (x) = 0 ïðè x ∈/ X."important samplingÓòâåðæäåíèå 3.3.Ïðåäïîëîæèì, ÷òî0 ≤ m1 ≤ q(x) =g(x)≤ m2 < +∞,f (x)x ∈ X.(3.15)Òîãäà èìååò ìåñòî ñëåäóþùàÿ îöåíêà äëÿ äèñïåðñèè(m2 − m1 )2Dζ = Dq(ξ) ≤.4Äîêàçàòåëüñòâî.Çàìåòèì, ÷òîm1 + m2E ζ−2m1 + m2+ Eζ −22(3.16)2m1 + m2= E (ζ − Eζ) + Eζ −2m1 + m2+ 2E (ζ − Eζ) Eζ −2Ñëåäîâàòåëüíî,m1 + m2Dζ ≤ E ζ −22≤2= Dζ+m1 + m2= Dζ + Eζ −22.(m2 − m1 )2.4Çäåñü èñïîëüçîâàíî òî, ÷òî m1 ≤ ζ ≤ m2 (âåäü ζ = q(ξ)) è ÷òî ëèíåéíàÿ ôóíêöèÿϕ(t) = t − (m1 + m2 )/2, m1 ≤ t ≤ m2 ïðèíèìàåò ñâîå ìàêñèìàëüíîå è ìèíèìàëüíîåçíà÷åíèÿ â òî÷êàõ t1 = m1 è t2 = m2 .Cëó÷àé m2 − m1 ≈ 0 ñîîòâåòñòâóåò ñîîòíîøåíèþ (3.14) äëÿ g(x) ≥ 0 äëÿ H1 ≈m1 ≈ m2 .
Íåðàâåíñòâà (3.15) è (3.16) äàþò ñïîñîá àïðèîðíîé îöåíêè äèñïåðñèè ïðèèñïîëüçîâàíèè âûáîðêè ïî âàæíîñòè (3.14) äëÿ ñëó÷àÿ (3.12).Ïðèìåð 3.1. Ðàññìîòðèì èíòåãðàërZ +∞Z +∞1sin2 (x1 . . . x10 )−(x21 +...+x210 )/2I=...e1+dx1 . . . dx10 .(2π)5 −∞4−∞Ïðè ïîñòðîåíèè àëãîðèòìà 3.1 öåëåñîîáðàçíî ïîëîæèòü10Y1−(x21 +...+x210 )/2f (x) = f (x1 , . . .
, x10 ) ==e(2π)5j=11 −xj /2√ e.2π(3.17)pÏðè ýòîì√q(x) = 1 + (sin2 (x1 . . . x10 ))/4 è âûïîëíåíî ñîîòíîøåíèå (3.15) äëÿ m1 = 1è m2 = 5/2. Ñëó÷àéíûé âåêòîð ξ = (ξ1 , . . . , ξ10 ), ðàñïðåäåëåííûé ñîãëàñíî ïëîòíîñòè (3.17), ñîñòîèò èç íåçàâèñèìûõ ñòàíäàðòíûõ íîðìàëüíûõ ñëó÷àéíûõ âåëè÷èí{ξj }. Èñïîëüçóÿ ôîðìóëû (1.139) èç ðàçä. 1.10, ïîëó÷àåì âûáîðî÷íûå çíà÷åíèÿ ξ i =(ξ1,i , .
. . , ξ10,i ), ãäåqq(s)(s)(s)(s)ξ2s−1,i = − ln α1,i sin 2πα2,i , ξ2s,i = − ln α1,i cos 2πα2,i ,s = 1, . . . , 5; i = 1, . . . , n. Ôîðìóëà (3.3) èç àëãîðèòìà 3.1 èìååò âèän q1 XI≈1 + (sin2 (ξ1,i . . . ξ10,i ))/4.n i=1pÏîãðåøíîñòü ýòîãî ïðèáëèæåíèÿ ïðîïîðöèîíàëüíà âåëè÷èíå Dζ/n. Ñîãëàñíî ñîîòíîøåíèþ (3.16), äèñïåðñèÿ îöåíèâàåòñÿ ñâåðõó âåëè÷èíîé Dζ ≤ (m2 − m1 )2 /4 ≈ 3.6 × 10−3 .Áîëåå òî÷íûå çíà÷åíèÿ âåëè÷èíû Dζ äàþò ñòàòèñòè÷åñêèå îöåíêè âèäà (3.7),(3.9).3.2.3. Âêëþ÷åíèå îñîáåííîñòè â ïëîòíîñòü. Âîçìîæíîñòü âûáîðà ïëîòíîñòèâèäà (3.14) ïîçâîëÿåò òàêæå îáåñïå÷èòü êîíå÷íîñòü äèñïåðñèè (3.4) ïðè âû÷èñëåíèèíåñîáñòâåííûõ èíòåãðàëîâ.Ïðèìåð 3.2. Ðàññìîòðèì èíòåãðàëZ 1Z 1ϕ(x)√ dx,I=g(x) dx =x00ãäå ϕ(x) íåïðåðûâíàÿ íà [0, 1] ôóíêöèÿ òàêàÿ, ÷òî ϕ(0) 6= 0. Åñëè â êà÷åñòâå f (x) âûáðàòü ïëîòíîñòü ðàñïðåäåëåíèÿ ñòàíäàðòíîãîñëó÷àéíîãî ÷èñëà ξ = α (òî åñòü f (x) ≡√1, 0 < x < 1), òî îöåíêà q(ξ) = ϕ(α)/ α èìååò áåñêîíå÷íóþ äèñïåðñèþ (3.4) è àëãîðèòì3.1 íåïðèìåíèì.
Îäíàêî ìîæíî âûáðàòü ïëîòíîñòü f (x) òàêèì îáðàçîì, ÷òîáû îòíîøåíèå |g(x)|/f (x) (à ñ íèì è äèñïåðñèÿ Dq(ξ)) áûëè îãðàíè÷åíû. Òàêîé ïðèåì íàçûâàþò√.  íàøåì ñëó÷àå ìîæíî âçÿòü f (x) = 1/(2 x)(ñîîòâåòñòâóþùàÿ ìîäåëèðóþùàÿ ôîðìóëà ξ = α2 ), è òîãäà îöåíêà q(ξ) = 2ϕ(ξ) èìååòóæå êîíå÷íóþ äèñïåðñèþ (3.4).âêëþ÷åíèåì îñîáåííîñòè â ïëîòíîñòüÏðèâåäåííûé ïðèìåð èìååò "èñêóññòâåííûé"õàðàêòåð, ò.ê. ìåòîä Ìîíòå-Êàðëî, êàêïðàâèëî, íå èñïîëüçóåòñÿ äëÿ âû÷èñëåíèÿ îäíîêðàòíûõ èíòåãðàëîâ (ñì.
ïîäðàçä. 3.1.2).Îòìåòèì, îäíàêî, ÷òî íåñëîæíî ïîñòðîèòü ìíîãîìåðíûé àíàëîã ïðèìåðà 3.2, è ÷òî îïèñàííàÿ ñèòóàöèÿ ÿâëÿåòñÿ ïîêàçàòåëüíîé èëëþñòðàöèåé òîãî, ÷òîïðîñòîòà ðåàëèçàöèè òîãî èëè èíîãî àëãîðèòìà ìåòîäà Ìîíòå-Êàðëî íå ãàðàíòèðóåò ýôôåêòèâíîñòüýòîãî àëãîðèòìà. ðÿäå ïðèëîæåíèé îñîáåííîñòè ïîäûíòåãðàëüíîé ôóíêöèè îïèñûâàþòñÿ îáîáùåííûìè ôóíêöèÿìè:!ZAXI = s(x)ϕj (x)δ(Fj (x)) dx, A = J ∨ ∞.j=1Çäåñü ôóíêöèè ϕj (x) ïðèíèìàþò ïîëîæèòåëüíûå çíà÷åíèÿ íà ãèïåðïîâåðõíîñòÿõ Γj ,îïðåäåëÿåìûõ óðàâíåíèÿìè Fj (x) = 0. Êàê ïðàâèëî, ñòàíäàðòíûå êóáàòóðíûå ôîðìóëûíå äàþò ýôôåêòèâíûõ àëãîðèòìîâ ïîäñ÷åòà òàêèõ èíòåãðàëîâ. ÂûáåðåìâèäàAXf (x) =pj ψj (x) δ(Fj (x)).äîïóñòèìóþïëîòíîñòüj=1Çäåñü ôóíêöèè ψj (x) ÿâëÿþòñÿ ïëîòíîñòÿìè ðàñïðåäåëåíèÿ íà ãèïåðïîâåðõíîñòÿõ Γj ,à {pj } âåðîÿòíîñòè.
Ó÷èòûâàÿ, ÷òî ïðè x ∈ Γj âûïîëíåíî f (x) = pj ψj (x), ïåðåïèøåìèñõîäíûé èíòåãðàë â âèäå (3.2):!ZAXϕj (x)δ(Fj (x))I = s(x)pj ψj (x) dx =pj ψj (x)j=1Z=AXs(x)ϕj (x)δ(Fj (x))!pj ψj (x)j=1Çäåñüζ=f (x) dx = Eζ.AXs(ξ)ϕj (ξ)δ(Fj (ξ))j=1pj ψj (ξ),à ñëó÷àéíûé âåêòîð ξ èìååò ïëîòíîñòü ðàñïðåäåëåíèÿ f (x). Òàêèì îáðàçîì, ìîæíî ðåàëèçîâàòü àëãîðèòì 3.1, ïðè÷åì ïðè ìîäåëèðîâàíèè âûáîðî÷íûõ çíà÷åíèé ξ i ïðèìåíÿåòñÿ ìåòîä ñóïåðïîçèöèè (àëãîðèòì 1.20): ñíà÷àëà ñîãëàñíî âåðîÿòíîñòÿì {pj } âûáèðàåòñÿíîìåð mi , à çàòåì ñîãëàñíî ïëîòíîñòè ψmi (x) ðåàëèçóåòñÿ òî÷êà ξ i íà ãèïåðïîâåðõíîñòè Γmi .
Ñîîòâåòñòâóþùèé âêëàä â îöåíêó (3.3) ðàâåí ζi = s(ξ i )ϕmi (ξ i )/(pmi ψmi (ξ i )).Ïî àíàëîãèè ñ óòâåðæäåíèåì 3.1 íåñëîæíî ïîêàçàòü, ÷òî ìèíèìàëüíàÿ äèñïåðñèÿ Dζäîñòèãàåòñÿ â ñëó÷àå, êîãäà ïëîòíîñòü f (x) ïðîïîðöèîíàëüíà ôóíêöèèf (x) ∼AX|s(x)| ϕj (x) δ(Fj (x)).j=1Èç ýòîãî ðåçóëüòàòàP∞ ñëåäóåò, â ÷àñòíîñòè, ÷òî åñëè ìû îöåíèâàåì ñóììó àáñîëþòíîñõîäÿùåãîñÿ ðÿäà j=1 aj , ðåàëèçóÿ ñ âåðîÿòíîñòüþ pj âåëè÷èíó aj /pj è áåðÿ ñðåäíååàðèôìåòè÷åñêîå òàêèõ ðåàëèçàöèé â êà÷åñòâå ïðèáëèæåíèÿ (3.3), òî íàèìåíüøàÿ äèñïåðñèÿ áóäåò ñîîòâåòñòâîâàòü çíà÷åíèÿì {pj }, ïðîïîðöèîíàëüíûì {|aj |}.3.2.4. Ïîñòðîåíèå ïëîòíîñòè f (x) êàê ïðèáëèæåíèÿ ôóíêöèè |g(x)|.
Èç ñîîòíîøåíèÿ (3.14) ñëåäóåò, ÷òî â êà÷åñòâå ïëîòíîñòè f (x) öåëåñîîáðàçíî âûáèðàòü êëàññè÷åñêèå (÷àùå âñåãî êóñî÷íî-ïîëèíîìèàëüíûå) ïðèáëèæåíèÿ ìîäóëÿ ïîäûíòåãðàëüíîéôóíêöèè g(x) âèäàf (x) = H2 LM |g(x)| = H2MXwm (g)χm (x).(3.18)m=1Çäåñü {χm (x)} çàäàííûå "áàçèñíûå"ôóíêöèè, ñîãëàñîâàííûå ñ çàäàííûìè óçëîâûìèòî÷êàìè {x1 , . . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
