1626435388-4a103190aea56b4a5b3ee742fd66e7b5 (844205), страница 3
Текст из файла (страница 3)
. .ðàâåí 1/M s äëÿ ëþáîãî öåëîãî ïîëîæèòåëüíîãî M .Äîêàçàòåëüñòâî. Óòâåðæäåíèå äîêàçûâàåòñÿ èíäóêöèåé ïî s. Îñíîâàíèå èíäóêöèè äàåò ñîîòíîøåíèå r(α, β) = 1/M , êîòîðîå îáîñíîâûâàåòñÿ ñëåäóþùèì îáðàçîì. Èçóòâåðæäåíèÿ 1.4 ñëåäóåò, ÷òî ñëó÷àéíàÿ âåëè÷èíà β ÿâëÿåòñÿ òàêæå ñòàíäàðòíîé èêîýôôèöèåíò êîððåëÿöèè ðàâåí!!!!!!α − 1/2β − 1/2M α − M/2β − 1/2ppppr(α, β) = E=E=1/121/12M 1/121/12!!![M α] + {M α} − (M/2 − 1/2) − 1/2β − 1/2pp=E=M 1/121/12!!!!!!β − 1/2β − 1/2β − 1/2γ − (M/2 − 1/2)pppp+E,=EM 1/121/12M 1/121/12ãäå γ = [M α]. Ñëó÷àéíàÿ âåëè÷èíà γ , ïðèíèìàþùàÿ çíà÷åíèÿ 0, 1, . . . , M − 1 ñ ðàâíûìèâåðîÿòíîñòÿìè 1/M , è íåïðåðûâíàÿ ñëó÷àéíàÿ âåëè÷èíà β íåçàâèñèìû. Äåéñòâèòåëüíî,k+ck+dP{(γ = k) ∩ (β ∈ (c, d))} = P(k + c < M α < k + d) = P<α<=MMc−dk+d k+c−== P(γ = k) × P(β ∈ (c, d));MMMçäåñü k = 0, 1, . .
. , M − 1 è 0 < c < d < 1. Òàêèì îáðàçîì,√1Dγ1r(α, β) = pr(γ, β) +r(β, β) =.MMM 1/12=Èíäóêòèâíûé ïåðåõîä îáîñíîâûâàåòñÿ àíàëîãè÷íî.Èç óòâåðæäåíèÿ 1.5 ñëåäóåò, ÷òî ïðè M >> 1 êîýôôèöèåíò êîððåëÿöèè ìåæäóçàâèñèìûìè âåëè÷èíàìè αn+s è αn íåâåëèê è ðàâåí 1/M s .Ó÷èòûâàÿ òî îáñòîÿòåëüñòâî, ÷òî ìåòîä Ìîíòå-Êàðëî âåñüìà ýôôåêòèâåí ïðè îöåíêå ìíîãîêðàòíûõ èíòåãðàëîâ, âàæíóþ ðîëü èãðàåòk, ñìûñëêîòîðîãî ñîñòîèò â òîì, ÷òî âåêòîðûñâîéñòâî -ðàâíîìåðíîñòè(k)(k)α1 = (α1 , . . .
, αk ), α2 = (αk+1 , . . . , α2k ), . . . , α(k)n = (αk(n−1)+1 , . . . , αnk )(1.11)äîëæíû ñ ðîñòîì n ñ âåðîÿòíîñòüþ åäèíèöà ðàâíîìåðíî çàïîëíÿòü åäèíè÷íûé k -ìåðíûéêóá Qk . Ýòî îçíà÷àåò, ÷òî ÷àñòîòà ïîïàäàíèÿ â ëþáóþ ïðÿìîóãîëüíóþ ïîäîáëàñòü êóáàñòðåìèòñÿ ê îáúåìó ýòîé îáëàñòè ïðè n → ∞.Îïðåäåëåííûì íåäîñòàòêîì ìóëüòèïëèêàòèâíîãî ìåòîäà âû÷åòîâ (1.8), (1.10) ÿâëÿåòñÿ òî îáñòîÿòåëüñòâî, ÷òî k -ìåðíûå ðàñïðåäåëåíèÿ âåêòîðîâ âèäà (αj , αj+1 , .
. . , αj+k )ñîñðåäîòî÷åíû íà ñåìåéñòâàõ ïëîñêîñòåé, ò.å. íà ìíîãîîáðàçèÿõ ìåíüøèõ ðàçìåðíîñòåé.Íàïðèìåð, íåòðóäíî ïîêàçàòü, ÷òî òî÷êè âèäà (1.9) ðàñïîëîæåíû íà M ïàðàëëåëüíûõïðÿìûõ. Äåéñòâèòåëüíî, åñëè sM −1 ≤ αj < (s + 1)M −1 , òî αj+1 = {M αj } = M αj − s.Ìîæíî ïîêàçàòü, ÷òî ïðè áîëüøîì M è äðóãèå óïîìÿíóòûå ìíîãîîáðàçèÿ äîñòàòî÷íîïëîòíî çàïîëíÿþò k -ìåðíûå êóáû.
Ïîýòîìó óêàçàííûì íåäîñòàòêîì ìåòîäà âû÷åòîâìîæíî ïðåíåáðå÷ü.Äëÿ ïîñëåäîâàòåëüíîñòåé {αn }, îáëàäàþùèõ ñâîéñòâîì k -ðàâíîìåðíîñòè, âûïîëíÿþòñÿ ñîîòíîøåíèÿ âèäàZ 1ZZ 1n1X(k)(k)(k)(k)¯ξn =...g(x1 , . . . , xk ) dx1 . . . dxkg(αj ) → J , ãäå J =g(x) dx =n j=100Qk(1.12)äëÿ ëþáîé èíòåãðèðóåìîé ïî Ðèìàíó ôóíêöèè g(x), ÷òî è îïðåäåëÿåò âàæíîñòü ñâîéñòâà k -ðàâíîìåðíîñòè ñ òî÷êè çðåíèÿ ïðèáëèæåííîãî âû÷èñëåíèÿ ìíîãîêðàòíûõ èíòåãðàëîâ.
Îòìåòèì òàêæå, ÷òî ìíîãèå àâòîðû â êà÷åñòâå îïðåäåëåíèÿ k -ðàâíîìåðíîñòèèñïîëüçóþò ñîîòíîøåíèå (1.12).  ÷àñòíîñòè, íà îñíîâå òàêîãî ïîäõîäà ñòðîèòñÿ êðèòåðèé Âåéëÿ (ñì. äàëåå óòâåðæäåíèå 1.7).Ïîñëåäîâàòåëüíîñòü (1.8), (1.10) îáëàäàåò àñèìïòîòè÷åñêèì (ïðè M → ∞) ñâîéñòâîì (1.12). Ýòî âûòåêàåò èç ñëåäóþùåãî óòâåðæäåíèÿ. ÏóñòüZ 1(k)ϕM (x) dx, ãäå ϕM (x) = g(x, {M x}, {M 2 x}, . . . , {M k−1 x}).JM =0Ïðè óñëîâèè, ÷òî α0 ðàâíîìåðíî ðàñïðåäåëåíî â (0, 1), è ïðè ñïåöèàëüíîì âûáîðå M(k)(k)(ñì.
äàëåå ôîðìóëó (1.13)) âûïîëíåíî JM = Eξn .Óòâåðæäåíèå 1.6 [1].M0M > M0(k)(k)ϕM (x)(0, 1)limM →∞ JM = Jg(x)QkÅñëè äëÿ íåêîòîðîãî ïðè âñåõâñå ôóíêöèèèíòåãðèðóåìû ïî Ðèìàíó â, òî. Åñëè ïðè ýòîì ïîäûíòåãðàëüíàÿ ôóíêöèÿîáëàäàåò â óñëîâèþ Ëèïøèöà000|g(x ) − g(x )| ≤ LΦkX|x0i − x00i |γ ,0 < γ < 1,i=1òî äëÿ M > M0 âûïîëíåíî |J (k) − JM(k)| ≤ ((k − 1)LΦ)/M γ . ðàìêàõ àëãîðèòìà ìåòîäà Ìîíòå-Êàðëî âìåñòî ïîñëåäîâàòåëüíîñòåé âèäà (1.8),(1.10) äëÿ âû÷èñëåíèÿ èíòåãðàëîâ âèäà J (k) ìîæíî èñïîëüçîâàòü ñïåöèàëüíûå ðàâíîìåðíûå ïîñëåäîâàòåëüíîñòè óçëîâ êóáàòóðíûõ ôîðìóë ñ ðàâíûìè âåñàìè. Ýòî ìîæåòäàòü ñóùåñòâåííîå óëó÷øåíèå ðàñ÷åòîâ, åñëè âû÷èñëÿåòñÿ èíòåãðàë íå ñëèøêîì âûñîêîé êðàòíîñòè (k ≤ 12) îò äîñòàòî÷íî "õîðîøåé"(ãëàäêîé) ôóíêöèè.
Òàêèå ïîñëåäîâàòåëüíîñòè êóáàòóðíûõ óçëîâ íàçûâàþòñÿ. Èç íèõ íàèáîëååèçó÷åíû è ïðîâåðåíû ïîñëåäîâàòåëüíîñòè Õîëòîíà è Ñîáîëÿ [2].1.1.4. Ñâîéñòâà ìóëüòèïëèêàòèâíîãî ìåòîäà âû÷åòîâ. Îòìåòèì, ÷òî óòâåðæäåíèÿ 1.4 è 1.5 ñôîðìóëèðîâàíû äëÿ "íàñòîÿùåãî"ñòàíäàðòíîãî ñëó÷àéíîãî ÷èñëà α.Ìîæíî ñôîðìóëèðîâàòü àíàëîãè ýòèõ óòâåðæäåíèé â ñëó÷àå ïðèìåíåíèÿ ìåòîäà (1.8),(1.10) äëÿ ÷èñåë αn ñ îãðàíè÷åííîé ìàíòèññîé äëèíû m. Ïðè ýòîì äëÿ äîñòàòî÷íî áîëüøîãî m ïðè óäà÷íîì ïîäáîðå ìíîæèòåëÿ M ñòàòèñòè÷åñêèå ñâîéñòâà ÷ëåíîâ ïîñëåäîâàòåëüíîñòè (1.8), (1.10) è "íàñòîÿùåãî"ñòàíäàðòíîãî ÷èñëà α áëèçêè (ýòî ïîêàçûâàþòñîîòâåòñòâóþùèå ñòàòèñòè÷åñêèå òåñòû ñì.
äàëåå ïîäðàçä. 1.1.5).Ïðåäïîëîæèì, ÷òî íà÷àëüíûé ýëåìåíò ïîñëåäîâàòåëüíîñòè (1.8), (1.10) ðàâåí α0 =2−m , à ìíîæèòåëü èìååò âèä M = 52p+1 , ãäå p öåëîå ïîëîæèòåëüíîå ÷èñëî. Òàêîé âûáîð îáúÿñíÿåòñÿ, â ÷àñòíîñòè, òåì, ÷òî ìíîãèå ñïåöèàëèñòû èñïîëüçîâàëè è ïðîâåðÿëèïîñëåäîâàòåëüíîñòè ñ ìíîæèòåëÿìè M èìåííî òàêîãî âèäà. Ñïðàâåäëèâî ïðåäñòàâëåíèåêâàçèñëó÷àéíûìè ÷èñëàìèαn = kn 2−m ;k0 = 1, kn ≡ kn−1 52p+1 (mod 2m ).(1.13)Ñóùåñòâåííûé íåäîñòàòîê ìóëüòèïëèêàòèâíîãî ìåòîäà âû÷åòîâ (1.13) ñâÿçàí ñ òåì,÷òî êîëè÷åñòâî ÷èñåë, èìåþùèõ ìàíòèññó äëèíû m è ïðèíàäëåæàùèõ èíòåðâàëó (0, 1),ïåðèîäè÷åñêîéÿâëÿåòñÿ êîíå÷íûì, è ïîýòîìó ïîñëåäîâàòåëüíîñòü (1.13) ÿâëÿåòñÿ, ò.å.ðàíî èëè ïîçäíî êàêîå-íèáóäü çíà÷åíèå αL ñîâïàäåò ñî çíà÷åíèåì α0 , è òîãäà, â ñèëó(1.8), èìååìαL+i = αi ïðè i = 1, 2, .
. .(1.14)äëèíîé ïåðèîäàÍàèìåíüøåå ÷èñëî L, óäîâëåòâîðÿþùåå (1.14), íàçûâàåòñÿ. Îáû÷íî äëÿðàñ÷åòîâ íå ðåêîìåíäóþò èñïîëüçîâàòü áîëüøå ÷åì L/2 ÷èñåë ïîñëåäîâàòåëüíîñòè (1.8),(1.10).Ñòàíäàðòíûìè ìåòîäàìè òåîðèè ÷èñåë ìîæíî äîêàçàòü, ÷òî äëÿ ìóëüòèïëèêàòèâíîãî ìåòîäà âû÷åòîâ (1.13) ïåðèîä ðàâåí L = 2m−2 .
Âåëè÷èíà M = 52p+1 â äâîè÷íîìïðåäñòàâëåíèè îêàí÷èâàåòñÿ íà 01, ïîýòîìó âñå αn ÿâëÿþòñÿ m-ðàçðÿäíûìè äâîè÷íûìè äðîáÿìè, ïîñëåäíèå äâà ðàçðÿäà êîòîðûõ ðàâíû 01. Âñëåäñòâèå ðàâåíñòâà L = 2m−2îñòàëüíûå m − 2 ðàçðÿäà "ïðîáåãàþò"âñå âîçìîæíûå êîìáèíàöèè. Ïîýòîìó â êà÷åñòâåα0 ìîæíî âûáðàòü ëþáóþ m-ðàçðÿäíóþ äâîè÷íóþ äðîáü óêàçàííîãî òèïà.Âîïðîñ î ïðèãîäíîñòè ïñåâäîñëó÷àéíûõ ÷èñåë (1.13) èññëåäóåòñÿ ñ ïîìîùüþ ñïåöèàëüíûõ ñòàòèñòè÷åñêèõ òåñòîâ (ñì. äàëåå ïîäðàçä. 1.1.5) è ðåøåíèÿ äîñòàòî÷íî ñëîæíûõòåñòîâûõ çàäà÷.
Äëÿ íåêîòîðûõ ïàðàìåòðîâ (m, p) ïîëó÷àþòñÿ óäîâëåòâîðèòåëüíûå ïîñëåäîâàòåëüíîñòè, äëÿ äðóãèõ ïëîõèå.  íîâîñèáèðñêîé øêîëå ìåòîäîâ Ìîíòå-Êàðëîäëÿ àëãîðèòìîâ ñ ÷èñëîì èñïûòàíèé n ïîðÿäêà 109 è ìåíüøå äîëãèå ãîäû âïîëíå óäîâëåòâîðèòåëüíûì ñ÷èòàåòñÿ ãåíåðàòîð (1.13) ñ ïàðàìåòðàìè m = 40 è p = 8, ïðîøåäøèéâñåñòîðîííåå ìíîãîëåòíåå òåñòèðîâàíèå.  ïîñëåäíåå âðåìÿ â ñâÿçè ñ ðîñòîì ìîùíîñòåéñîâðåìåííûõ âû÷èñëèòåëüíûõ ñèñòåì âîçíèêëà ïîòðåáíîñòü â ãåíåðàòîðàõ ñ óâåëè÷åííûì ïåðèîäîì.  ÷àñòíîñòè, äëÿ ïàðàëëåëüíûõ âû÷èñëåíèé èñïîëüçóåòñÿ ãåíåðàòîð(1.13) ñ ïàðàìåòðàìè m = 128 è p = 50059 èç [3] (ñì. äàëåå ïîäðàçä.
1.1.6). Îïðåäåëåííûå òðóäíîñòè êîíêðåòíîé ðåàëèçàöèè ôîðìóë (1.13) íà êîìïüþòåðå ñâÿçàíû ñ òåì, ÷òîíóæíî ïðîèçâîäèòü äåéñòâèÿ ñ ÷èñëàìè, èìåþùèìè ìàíòèññó äëèíû m, ïðåâîñõîäÿùóþñòàíäàðòíûé ôîðìàò ÝÂÌ. çàêëþ÷åíèå ýòîãî ïîäðàçäåëà ñôîðìóëèðóåì äâà âàæíûõ çàìå÷àíèÿ.Çàìå÷àíèå 1.1. Êàê ïðàâèëî, ãåíåðàòîðû ïñåâäîñëó÷àéíûõ ÷èñåë, ïðåäñòàâëåííûåâ ñîâðåìåííûõ âåðñèÿõ ÿçûêîâ ïðîãðàììèðîâàíèÿ (FORTRAN, PASCAL, ÑÈ++ è äð.)äîñòàòî÷íî õîðîøî ïðîòåñòèðîâàíû è äàþò ñòàòèñòè÷åñêè óäîâëåòâîðèòåëüíûå ðåçóëüòàòû âû÷èñëåíèé ïî ìåòîäó Ìîíòå-Êàðëî (âî âñÿêîì ñëó÷àå, äëÿ çàäà÷, â êîòîðûõ èñïîëüçóåòñÿ óìåðåííî áîëüøîå êîëè÷åñòâî âûáîðî÷íûõ çíà÷åíèé ñëó÷àéíûõ âåëè÷èí).Ïîýòîìó íåñìîòðÿ íà ñôîðìóëèðîâàííûå âûøå çàìå÷àíèÿ î âîçìîæíûõ íåäîñòàòêàõäàò÷èêîâ (êîíå÷íîñòü èñïîëüçóåìîé ìàíòèññû, ïåðèîäè÷íîñòü è ò.
ï.), â äàëüíåéøåìáóäåì ïîëàãàòü, ÷òî èñïîëüçóåìûé â ðàñ÷åòàõ ãåíåðàòîð ñòàíäàðòíûõ ñëó÷àéíûõ ÷èñåëäàåò "íàñòîÿùèå"(òåîðåòè÷åñêèå) âûáîðî÷íûå çíà÷åíèÿ α.Çàìåòèì, îäíàêî, ÷òî äëÿ ïðîâåäåíèÿ ïðåöåçèîííûõ ðàñ÷åòîâ öåëåñîîáðàçíî èñïîëüçîâàòü äàò÷èê, ðåçóëüòàòû ïðîâåðêè êîòîðîãî èçâåñòíû. Îñîáóþ ðîëü èãðàþò êîíòðîëüíûå ðàñ÷åòû äëÿ çàäà÷ (áëèçêèõ ê ðåàëüíûì) ñ èçâåñòíûì ðåøåíèåì.Çàìå÷àíèå 1.2. Ìóëüòèïëèêàòèâíûé ìåòîä âû÷åòîâ (1.13), äàæå ðåàëèçîâàííûéîïòèìàëüíî äëÿ èñïîëüçóåìîãî ÿçûêà ïðîãðàììèðîâàíèÿ, ÿâëÿåòñÿ îòíîñèòåëüíî òðóäîåìêèì (ïî ñðàâíåíèþ, íàïðèìåð, ñ ïðîñòûì óìíîæåíèåì ÷èñåë).
Ïîýòîìó ïðè îïòèìèçàöèè àëãîðèòìîâ ìåòîäà Ìîíòå-Êàðëî öåëåñîîáðàçíî ïî-âîçìîæíîñòè óìåíüøàòü÷èñëî îáðàùåíèé ê ïîäïðîãðàììå òèïà RAN DOM .1.1.5. Òåñòèðîâàíèå è ìîäèôèêàöèÿ ãåíåðàòîðîâ ñëó÷àéíûõ è ïñåâäîñëó-Êàê óêàçàíî âûøå, îêîí÷àòåëüíûé âûâîä î êà÷åñòâå òîãî èëè èíîãîãåíåðàòîðà ñëó÷àéíûõ èëè ïñåâäîñëó÷àéíûõ ÷èñåë ñëåäóåò èç ðåçóëüòàòîâ òåñòèðîâàíèÿýòîãî ãåíåðàòîðà. Ñðàçó ñëåäóåò çàìåòèòü, ÷òî íèêàêàÿ, äàæå ñàìàÿ øèðîêàÿ, ñèñòåìà÷àéíûõ ÷èñåë.òåñòîâ íå ÿâëÿåòñÿ äîñòàòî÷íîé äëÿ òîãî, ÷òîáû îáúÿâèòü òîò èëè èíîé ãåíåðàòîð ïîäõîäÿùèì. Ïðîöåññ ïðîâåðêè äàííîãî ãåíåðàòîðà, âîîáùå ãîâîðÿ, áåñêîíå÷åí.
Áîëåå òîãî,êàæäóþ çàäà÷ó ñ èçâåñòíûì ðåøåíèåì, ïðè ÷èñëåííîì ðåøåíèè êîòîðîé èñïîëüçóåòñÿãåíåðàòîð ñëó÷àéíûõ (ïñåâäîñëó÷àéíûõ) ÷èñåë, ìîæíî ðàññìàòðèâàòü êàê î÷åðåäíîéòåñò äëÿ ýòîãî äàò÷èêà. Ìû óïîìÿíåì íàèáîëåå ðàñïðîñòðàíåííûå òåñòû äëÿ ïðîâåðêèãåíåðàòîðîâ.Êàê óêàçàíî â ïîäðàçä. 1.1.3, îäíèì èç âàæíåéøèõ õàðàêòåðèñòèê ïîñëåäîâàòåëüíîñòåé {αn } ÿâëÿåòñÿ ñâîéñòâî k -ðàâíîìåðíîñòè. Ïðîâåðêó ýòîãî ñâîéñòâà ìîæíî îñóùåñòâëÿòü, íàïðèìåð, ñ ïîìîùüþ êðèòåðèÿ õè-êâàäðàò. Îáëàñòü Qk ðàçáèâàåòñÿ íàr = sk îäèíàêîâûõ äîñòàòî÷íî ìàëûõ êóáîâ (ïðè ýòîì ââîäèòñÿ ðàâíîìåðíàÿ ñåòêà øàãà 1/s ïî êàæäîé êîîðäèíàòå), ïîäñ÷èòûâàþòñÿ ÷àñòîòû {νi } ïîïàäàíèÿ âåêòîðîâ (1.11)â ýòè ìàëûå êóáû è âåëè÷èíàχ̃2r−1 (n) =rX(νi − npi )2i=1npi,(1.15)ãäå {pi = 1/r} "òåîðåòè÷åñêèå"âåðîÿòíîñòè ïîïàäàíèÿ ðàâíîìåðíî ðàñïðåäåëåííûõâåêòîðîâ (1.11) â ñîîòâåòñòâóþùèå êóáû ðàçáèåíèÿ.
Ñîãëàñíî òåîðåìå Ïèðñîíà, ñïðàâåäëèâî ñîîòíîøåíèåZ xu(r−1)/2−1 e−u/22lim P(χ̃r−1 (n) < x) =fχ2r−1 (u) du, ãäå fχ2r−1 (u) = (r−1)/2n→∞2Γ((r − 1)/2)0ÿâëÿåòñÿõè-êâàäðàò ðàñïðåäåëåíèÿ ñ (r − 1) ñòåïåíÿìè ñâîáîäû, à Γ(v) =R +∞ v−1 ïëîòíîñòüþ−wwe dw ãàììà-ôóíêöèÿ. Çàäàåòñÿ äîâåðèòåëüíàÿ âåðîÿòíîñòü (èëè êîýôôè0öèåíò äîâåðèÿ) ε (÷àùå âñåãî áåðóò ε = 0.95; 0.99; 0.999) è èç óðàâíåíèÿZ ∞fχ2l−1 (u) du = 1 − εχ2 (r−1,1−ε)íàõîäÿò (÷àùå âñåãî ñ ïîìîùüþ ñîîòâåòñòâóþùèõ òàáëèö) âåëè÷èíó χ2 (r − 1, 1 − ε), êîòîðóþ íàçûâàþò(1−ε).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
