1626435386-4ea3b7438ebb2e92437735aa9b26c4d2 (844201), страница 4
Текст из файла (страница 4)
Äëÿ èçó÷åíèÿ òåîðåòè÷åñêîé ýôôåêòèâíîñòè àëãîðèòìîâ ÷èñëåííîãî èíòåãðèðîâàíèÿ íóæíî, ÷òîáû èìåëàñü âîçìîæíîñòü ïîëó÷àòü óòî÷íåííûå âåðõíèå ãðàíèöû äëÿ ïîãðåøíîñòåé èñïîëüçóåìûõìåòîäîâ äëÿ çàäàííûõ ìíîæåñòâ ôóíêöèé g(x).4.2. Èñïîëüçîâàíèå ÷èñëåííûõ ìîäåëåé ñëó÷àéíûõ ïîëåé.
Âðàáîòàõ [35, 9, 11] ïîêàçàíî, ÷òî äîñòàòî÷íî óäà÷íûì (ñ òî÷êè çðåíèÿâûïîëíåíèÿ ñôîðìóëèðîâàííûõ òðåáîâàíèé 15) îêàçûâàåòñÿ âûáîð âêà÷åñòâå òåñòîâûõ ôóíêöèé òðàåêòîðèé ñïåêòðàëüíûõ ìîäåëåé îäíîðîäíûõ ãàóññîâñêèõ ñëó÷àéíûõ ïîëåé (ñì., íàïðèìåð, [1, 5]) ñ êîíå÷íûìñïåêòðîì âèäàg(x) = g̃(x) = Ad ΞK (x), ΞK (x) =KX(1)ak [γk(2)cos(x, λk )+γksin(x, λk )].k=1(4.1)Çäåñüi = 1, 2 íåçàâèñèìûå â ñîâîêóïíîñòè ñòàíäàðòíûå íîðìàëüíûå âåëè÷èíû; x ∈ X (÷àùå âñåãî X = Qd = [0, 1]d åäèíè÷íûé êóá).Âåêòîðû λk âûáèðàþòñÿ ñëó÷àéíî â îáëàñòè Λ = [0, A]d (èëè â ðåãóëÿðíûõ ïîäîáëàñòÿõ Λk ðàâíîãî îáúåìà) ñîãëàñíî ïëîòíîñòè ðàâíîìåðíîãîðàñïðåäåëåíèÿ1dïðèλ∈[0,A);0èíà÷å,p(λ) =Ad(i)γk ,18ò. å.
èñïîëüçóåòñÿ ðàíäîìèçèðîâàííàÿ ìîäåëü√ áåç ðàçáèåíèÿ (èëè ñ ðàçáèåíèåì) ñïåêòðà [1, 5]; ïðè ýòîì ak = 1/ K .Çàìåòèì òàêæå, ÷òî ïàðó íåçàâèñèìûõ çíà÷åíèé ñòàíäàðòíîé íîðìàëüíîé ñëó÷àéíîé âåëè÷èíû ìîæíî ïîëó÷èòü ïî ôîðìóëàì (ñì., íàïðèìåð, [1, 4])(1)(2)γk = (−2 ln αk,1 )1/2 cos 2παk,2 , γk = (−2 ln αk,1 )1/2 sin 2π αk,2 ; (4.2)çäåñü è äàëåå áóêâîé α ñ èíäåêñàìè èëè áåç èíäåêñîâ îáîçíà÷àåòñÿ ñòàíäàðòíîå ñëó÷àéíîå ÷èñëî, ò. å.
âûáîðî÷íîå çíà÷åíèå ñëó÷àéíîéâåëè÷èíû, ðàâíîìåðíî ðàñïðåäåëåííîé íà èíòåðâàëå (0, 1) (ñì., íàïðèìåð, [1, 4], à òàêæå ïîäðàçä. 5.1). Òîãäà ñîîòíîøåíèå (4.1) ïðèíèìàåòâèä, óäîáíûé äëÿ íåïîñðåäñòâåííûõ âû÷èñëåíèé íà ÝÂÌ:K1 X0(−2 ln αk,1 )1/2 cos((λk , x) + 2 π αk,2),ΞK (x) = √K k=10αk,2= 1 − αk,2 .(4.3)4.3. Âûïîëíåíèå òðåáîâàíèé 15.
Ôóíêöèè âèäà (4.1), (4.3) óäî-âëåòâîðÿþò ñôîðìóëèðîâàííûì òðåáîâàíèÿì. Äåéñòâèòåëüíî, ¾ñëó÷àéíîñòü¿ ïîëó÷àåìûõ ïîäûíòåãðàëüíûõ ôóíêöèé (òðåáîâàíèå 1) î÷åâèäíà, òàê êàê, íàïðèìåð, â (4.1) èñïîëüçóþòñÿ ðåàëèçàöèè ñòàíäàðòíûõ(j)íîðìàëüíûõ ñëó÷àéíûõ âåëè÷èí {γk , j = 1, 2} è ñëó÷àéíûõ òî÷åê{λk }.
Èäåÿ óìíîæåíèÿ íà êîíñòàíòó Ad â ôîðìóëå (4.1) ïðèøëà ïîñëåðåàëüíûõ òåñòîâûõ ðàñ÷åòîâ [3, 9, 11]. Ñìûñë ýòîé èäåè ñîñòîèò â áîëååòùàòåëüíîì ó÷åòå áîëüøèõ àìïëèòóä ñèíóñà è êîñèíóñà ïðè óâåëè÷åíèèïàðàìåòðà ðàçìåðà A ñïåêòðàëüíîãî ìíîæåñòâà Λ. Âàðüèðîâàòü çàòðàòû íà âû÷èñëåíèå îäíîãî çíà÷åíèÿ ôóíêöèè g̃(x) (òðåáîâàíèå 2) ìîæíîçà ñ÷åò èçìåíåíèÿ ÷èñëà ñëàãàåìûõ (ïàðàìåòðà K ) â ñóììå (4.1).
Àíàëèòè÷åñêè âû÷èñëÿåòñÿ èíòåãðàë (òðåáîâàíèå 3):1ZZ1g̃(x) dx =00K(1)(2)A X γk sin λk − γk (cos λk − 1)AΞK (x) dx = √;λkK k=1çäåñü d = 1. Äëÿ ýòîãî ñëó÷àÿ íåñëîæíî âû÷èñëÿåòñÿ è q -ÿ ïðîèçâîäíàÿñëó÷àéíîé ôóíêöèè AΞK (x) ïî x, êîòîðàÿ èìååò âèä (çäåñü ìû ïîëüçóåìñÿ ôîðìóëîé (4.3))g̃(q)(x) =(q)AΞK (x)1/2K X−2 ln αk,10=Aλqk cos(λk x + 2παk,2+ qπ/2).Kk=119Ïðè äîñòàòî÷íî áîëüøîì A â ýòîé ñóììå âîçíèêíóò áîëüøèå êîýôôèöèåíòû λqk (âî âñÿêîì ñëó÷àå, äëÿ ðåàëèçàöèé λk , áëèçêèõ ê A), ïðè÷åìýòè êîýôôèöèåíòû ðàñòóò ñ óâåëè÷åíèåì q ñòåïåííûì îáðàçîì. Õîòÿôîðìàëüíî ôóíêöèÿ (4.2) ÿâëÿåòñÿ áåñêîíå÷íî äèôôåðåíöèðóåìîé ïî(q)x, ìîæíî ñ÷èòàòü, ÷òî g̃(x) = AΞK (x) ∈ C r (X), åñëè |AΞK (x)| ≤ B(q)äëÿ q ≤ r, x ∈ [0, 1] è |AΞK (x)| > B äëÿ q > r, ãäå B çàäàííîåäîñòàòî÷íî áîëüøîå ïîëîæèòåëüíîå ÷èñëî (ò. å.
íà ïðàêòèêå ðàçóìíîïîëàãàòü, ÷òî ïðîèçâîäíàÿ íå ñóùåñòâóåò, åñëè åå çíà÷åíèå ïî ìîäóëþïðåâûøàåò çàäàííûé óðîâåíü B ). Âàðüèðóÿ A è çàäàâàÿ B , ìîæíî äîáèâàòüñÿ ïðèíàäëåæíîñòè ôóíêöèè g̃(x) = AΞK (x) ïðîñòðàíñòâó C r (X)äëÿ íóæíîãî r (ñì. òðåáîâàíèå 4).×òî êàñàåòñÿ òðåáîâàíèÿ 5, òî â ðàáîòàõ [3, 9, 11] ïîëó÷åíû çàâèñèìîñòè îò ïàðàìåòðîâ A è K îöåíîê ñâåðõó äëÿ ñðåäíèõ ïîãðåøíîñòåé ôîðìóë ïðÿìîóãîëüíèêîâ, òðàïåöèé, Ñèìïñîíà, à òàêæå äèñêðåòíî-ñòîõàñòè÷åñêèõ àëãîðèòìîâ ÷èñëåííîãî èíòåãðèðîâàíèÿ, ïðåäñòàâëåííûõ âäàííîì ïîñîáèè.
 òåõ æå ðàáîòàõ óêàçàíà âîçìîæíîñòü ðàñøèðåíèÿêëàññà òåñòîâûõ ôóíêöèé çà ñ÷åò èñïîëüçîâàíèÿ ìîäåëåé íåãàóññîâñêèõñëó÷àéíûõ ïîëåé.5. Ìåòîäû ÷èñëåííîãî ìîäåëèðîâàíèÿ ñëó÷àéíûõâåêòîðîâ5.1. Ñòàíäàðòíîå ñëó÷àéíîå ÷èñëî. Ñðàçó îòìåòèì, ÷òî ìàòåðèàë äàííîãî ðàçäåëà â áîëåå ðàçâåðíóòîì âèäå ïðåäñòàâëåí â ñïåöèàëüíîì êóðñå êàôåäðû âû÷èñëèòåëüíîé ìàòåìàòèêè ÍÃÓ ¾Äîïîëíèòåëüíûå ñâåäåíèÿ î ÷èñëåííîì ìîäåëèðîâàíèè ñëó÷àéíûõ ýëåìåíòîâ¿[4] (ñì. òàêæå ãëàâó 1 ó÷åáíèêà [1]).Èç ïðåäûäóùèõ ðàçäåëîâ ñëåäóåò, ÷òî êëþ÷åâûì ìîìåíòîì ðåàëèçàöèè ìåòîäà Ìîíòå-Êàðëî ÿâëÿåòñÿ ìîäåëèðîâàíèå (èëè ðåàëèçàöèÿâûáîðî÷íûõ çíà÷åíèé) ñëó÷àéíûõ âåëè÷èí è ñëó÷àéíûõ âåêòîðîâ íàÝÂÌ, êîòîðîå ñîñòîèò èç äâóõ ýòàïîâ:1) ðåàëèçóþòñÿ çíà÷åíèÿ α1 , . . . , αk ñòàíäàðòíîãî ñëó÷àéíîãî ÷èñëàα, ðàâíîìåðíî ðàñïðåäåëåííîãî â èíòåðâàëå (0, 1), ñ ïîìîùüþ ñïåöèàëüíîé ïðîãðàììû èëè óñòðîéñòâà, êîòîðîå íàçûâàåòñÿ ãåíåðàòîðîìñëó÷àéíûõ (ïñåâäîñëó÷àéíûõ) ÷èñåë;2) ñ ïîìîùüþ íåêîòîðûõ ïðåîáðàçîâàíèé ïîëó÷åííûõ ÷èñåë {αj } âû÷èñëÿþòñÿ çíà÷åíèÿ ñëó÷àéíûõ âåëè÷èí ñ çàäàííûìè çàêîíàìè ðàñïðåäåëåíèÿ.20Íàëè÷èå íàäåæíîãî ãåíåðàòîðà ñòàíäàðòíûõ ñëó÷àéíûõ ÷èñåë α ïîçâîëÿåò ïîëó÷àòü âûáîðî÷íûå çíà÷åíèÿ ñëó÷àéíûõ âåëè÷èí (îäíîìåðíûõ è ìíîãîìåðíûõ) ñ ïðîèçâîëüíûìè çàêîíàìè ðàñïðåäåëåíèÿ.
Îñîáîå âíèìàíèå â ýòîì ðàçäåëå áóäåò óäåëåíî àëãîðèòìàì (â òîì ÷èñëå,äèñêðåòíî-ñòîõàñòè÷åñêèì) ðåàëèçàöèè âåëè÷èí âèäà ζ = q(ξ) (ñì. ñîîòíîøåíèå (1.2)), ãäå q(x) íåñëó÷àéíàÿ ôóíêöèÿ ìíîãèõ ïåðåìåííûõ,à ξ ìíîãîìåðíûé ñëó÷àéíûé âåêòîð.5.2. Ìîäåëèðîâàíèå äèñêðåòíîãî ðàñïðåäåëåíèÿ. Ðàññìîòðèìâîïðîñ î ìîäåëèðîâàíèè äèñêðåòíîé ñëó÷àéíîé âåëè÷èíû ξ ñ êîíå÷íûì÷èñëîì çíà÷åíèé x1 , .
. . , xN è ðàñïðåäåëåíèåì âåðîÿòíîñòåéP(ξ = xi ) = pi ; pi > 0,NXpi = 1.(5.1)i=1 ñèëó ñîîòíîøåíèé (5.1), ðåàëèçàöèÿ òîãî èëè èíîãî çíà÷åíèÿ xm ñëó÷àéíîé âåëè÷èíû ξ îçíà÷àåò ðîçûãðûø ñîáûòèÿ ñ âåðîÿòíîñòüþ pm .Êðîìå òîãî, èç ñîîòíîøåíèé (5.1) ñëåäóåò, ÷òî èíòåðâàë (0, 1) ìîæíîðàçáèòü íà ïîëóèíòåðâàëû ∆m äëèíû pm :∆m = [Rm−1 , Rm ); Rm =mXpi ; m = 1, 2, .
. . , N ;i=1äëÿ m = 1 ïîëàãàåì Rm−1 = R0 = 0. Èñïîëüçóÿ ñîîòâåòñòâóþùèé ãåíåðàòîð, ðåàëèçóåì âûáîðî÷íîå çíà÷åíèå α ñòàíäàðòíîãî ñëó÷àéíîãî÷èñëà. Èç ñâîéñòâ ñòàíäàðòíîãî ñëó÷àéíîãî ÷èñëà (ñì., íàïðèìåð, [1])ñëåäóåò, ÷òî P(α ∈ ∆m ) = pm . Òàêèì îáðàçîì, åñëè α ∈ ∆m , òî äëÿäàííîãî èñïûòàíèÿ ïîëàãàåì ξ = xm .Òåõíè÷åñêè îïðåäåëåíèå òîãî íîìåðà m ïîëóèíòåðâàëà ∆m , â êîòîðûé ïîïàëî âûáîðî÷íîå çíà÷åíèå α, îñóùåñòâëÿåòñÿ ïîñëåäîâàòåëüíûìâû÷èòàíèåì èç α ñóìì Rm äëÿ m = 1, 2, . . . äî òåõ ïîð, ïîêà ðàçíîñòüα−Rm íå ñòàíåò îòðèöàòåëüíîé. Îïèñàííóþ îïåðàöèþ ìîæíî îñóùåñòâëÿòü áåç íåïîñðåäñòâåííîãî âû÷èñëåíèÿ ñóìì Rm , èñïîëüçóÿ îïåðàöèþïåðåïðèñâàèâàíèÿ.ÀËÃÎÐÈÒÌ 5.1. Ðåàëèçóåì çíà÷åíèå Q := α è ïîëàãàåì m := 1.Ïðîèçâîäèì ïåðåïðèñâàèâàíèåQ := Q − pm(5.2)(ò.
å. çàíîñèì íîâîå çíà÷åíèå (α − p1 ) â ÿ÷åéêó Q). Åñëè íîâîå Q íåïîëîæèòåëüíî, òî â êà÷åñòâå m âûáèðàåì òåêóùåå åãî çíà÷åíèå è21ïîëàãàåì ξ = xm , â ïðîòèâíîì ñëó÷àå ïðîèçâîäèì ïåðåïðèñâàèâàíèÿm := m+1 è (5.2) è âíîâü ïðîèçâîäèì ïðîâåðêó Q íà ïîëîæèòåëüíîñòüè ò. ä. äàííîì ïîñîáèè â îñíîâíîì áóäóò èñïîëüçîâàòüñÿ öåëî÷èñëåííûåäèñêðåòíûå ñëó÷àéíûå âåëè÷èíû η , äëÿ êîòîðûõxi = i, P(η = i) = pi ; i = 1, 2, . .
. , N.(5.3)Àëãîðèòì 5.1 â ýòîì ñëó÷àå èìååò ñëåäóþùèé âèä.ÀËÃÎÐÈÒÌ 5.2. Ðåàëèçóåì çíà÷åíèå Q := α è ïîëàãàåì m := 1.Ïðîèçâîäèì ïåðåïðèñâàèâàíèå (5.2). Åñëè íîâîå çíà÷åíèå Q íå ïîëîæèòåëüíî, òî ïîëàãàåì η = m, â ïðîòèâíîì ñëó÷àå ïðîèçâîäèì ïåðåïðèñâàèâàíèÿ m := m + 1 è (5.2) è âíîâü ïðîèçâîäèì ïðîâåðêó Q íàïîëîæèòåëüíîñòü è ò. ä.Ïîäñ÷åò ñðåäíèõ çàòðàò àëãîðèòìîâ 5.1 è 5.2, îïòèìèçàöèÿ ýòèõ àëãîðèòìîâ, èõ ïðèìåíåíèå äëÿ ñëó÷àÿ ìàëîãî è áîëüøîãî (â òîì ÷èñëå,ñ÷åòíîãî) ÷èñëà âåðîÿòíîñòåé N ïîäðîáíî îïèñàíû â [1, 4].Ðåàëèçàöèÿ ñëó÷àéíîé âåëè÷èíû ξ ñ êîíå÷íûì ÷èñëîì çíà÷åíèé çàìåòíî óïðîùàåòñÿ, êîãäà âñå çíà÷åíèÿ x1 , . . . , xN ðàâíîâåðîÿòíû, ò.
å. âñîîòíîøåíèè (5.1) âñå pi ðàâíû 1/N (òàêîå ðàñïðåäåëåíèå âåðîÿòíîñòåéíàçûâàåòñÿ äèñêðåòíûì ðàâíîìåðíûì).ÀËÃÎÐÈÒÌ 5.3. Ðåàëèçóåì âûáîðî÷íîå çíà÷åíèå α ñòàíäàðòíîãîñëó÷àéíîãî ÷èñëà è ïîëàãàåìm = [α N ] + 1 = [αN + 1](5.4)(çäåñü [A] îáîçíà÷àåò öåëóþ ÷àñòü ÷èñëà A) è ξ = xm .Àëãîðèòì 5.3 ïîçâîëÿåò ïîñòðîèòü ñëåäóþùóþ ýôôåêòèâíóþ ìîäèôèêàöèþ àëãîðèòìîâ 5.1 è 5.2, êîòîðàÿ íîñèò íàçâàíèå êâàíòèëüíûéìåòîä (ñì., íàïðèìåð, [1, 4]).Çàäàäèì öåëîå ÷èñëî K è ðàçîáüåì èíòåðâàë (0, 1) íà K ðàâíûõ÷àñòåé [(j − 1)/K, j/K), j = 1, .
. . , K . Äàëåå ïîñòðîèì ìàññèâ öåëûõ÷èñåë {Xj }Kj=1 òàêîé, ÷òîXj = min{k : Rk = p1 + p2 + . . . + pk ≥ (j − 1)/K},êîòîðûé íàçûâàåòñÿ ìàññèâîì íèæíèõ êâàíòèëåé. Ýòîò ìàññèâ çàäàåò íîìåð k ýëåìåíòà ìàññèâà {Ri ; i = 1, 2, . . . , N }, ñ êîòîðîãî ñëåäóåòíà÷èíàòü ïîèñê ¾ââåðõ¿ (ò. å. êàê è â àëãîðèòìå âèäà 5.1, âû÷èòàòü âåëè÷èíû Rq , q = k, k + 1, . . . èç α äî ïîëó÷åíèÿ ïåðâîãî îòðèöàòåëüíîãî22çíà÷åíèÿ) ïðè (j − 1)/K ≤ α < j/K . Îêîí÷àòåëüíî ìîäåëèðîâàíèå äèñêðåòíîé ñëó÷àéíîé âåëè÷èíû âûãëÿäèò ñëåäóþùèì îáðàçîì.ÀËÃÎÐÈÒÌ 5.4.
1. Ðåàëèçóåì âûáîðî÷íîå çíà÷åíèå α ðàâíîìåðíîðàñïðåäåëåííîé â èíòåðâàëå (0, 1) ñëó÷àéíîé âåëè÷èíû.2. Âû÷èñëÿåì íîìåð j ïîëóèíòåðâàëà [(j − 1)/K, j/K), â êîòîðûéïîïàäàåò α ïî ôîðìóëå òèïà (5.4): j = [Kα + 1].3. Ðåàëèçóåì ïîñëåäîâàòåëüíûé ïîèñê ¾ñíèçó ââåðõ¿ íà÷èíàÿ ñ RXj .Òåñòîâûå âû÷èñëåíèÿ ïîêàçàëè, ÷òî ïðè N ≤ 3M0 (çäåñü ÷åðåç M0îáîçíà÷åí ðàçìåð ìàêñèìàëüíîãî ìàññèâà äëÿ çàäàííîãî êîìïüþòåðà èâûáðàííîãî ÿçûêà ïðîãðàììèðîâàíèÿ) ñëåäóåò âûáèðàòü ÷èñëî K êâàíòèëåé [(j − 1)/K, j/K) òàê, ÷òîáû âûïîëíÿëîñü ñîîòíîøåíèå N/K ≈ 3(ïðè ýòîì òðóäîåìêîñòü àëãîðèòìà 5.4 ïðàêòè÷åñêè íå ìåíÿåòñÿ ñ ðîñòîì N ).
Îñîáî ïîä÷åðêíåì, ÷òî êâàíòèëüíûé ìåòîä ðàáîòàåò è â ñëó÷àåáåñêîíå÷íîãî ÷èñëà çíà÷åíèé ñëó÷àéíîé âåëè÷èíû ξ (ò. å. äëÿ N = ∞);çäåñü ìîæíî áðàòü K ≈ M0 .Ýôôåêòèâíûå âåðñèè êâàíòèëüíîãî ìåòîäà ìîæíî ñòðîèòü è äëÿîòíîñèòåëüíî ìàëîãî ÷èñëà âåðîÿòíîñòåé. Ïóñòü 1/pmin < M0 (çäåñüpmin = min(p1 , . . . , pN )). Òîãäà ìîæíî âçÿòü ÷èñëî êâàíòèëåé, ðàâíîåK = [1/pmin ] + 1. Ïðè ýòîì äëÿ ðåàëèçàöèè òðåòüåãî ïóíêòà àëãîðèòìà5.4 ïîòðåáóåòñÿ íå áîëåå îäíîãî âû÷èòàíèÿ òèïà (5.2).Çàìåòèì òàêæå, ÷òî â öåëîì ðÿäå ñèòóàöèé öåëåñîîáðàçíî èñïîëüçîâàòü âìåñòî êâàíòèëüíîãî ìåòîäà àëãîðèòì Óîëêåðà èëè äàæå áèíàðíûéïîèñê (ñì., íàïðèìåð, [1]), îäíàêî àëãîðèòì 2.6 ÿâëÿåòñÿ áîëåå óíèâåðñàëüíûì è ïðîñòûì äëÿ ðåàëèçàöèè íà ÝÂÌ.5.3.
Ìåòîä îáðàòíîé ôóíêöèè ðàñïðåäåëåíèÿ. Ðàññìîòðèì òåïåðü àëãîðèòìû ìîäåëèðîâàíèÿ ñëó÷àéíîé âåëè÷èíû ξ , îáëàñòüþ çíà÷åíèé êîòîðîé ÿâëÿåòñÿ èíòåðâàë èëè îáúåäèíåíèå èíòåðâàëîâ.  äàëüíåéøåì â ïîäàâëÿþùåì ÷èñëå ñëó÷àåâ ïðåäïîëàãàåòñÿ, ÷òî ξ ∈ (a, b),ò. å. ñëó÷àéíàÿ âåëè÷èíà ξ ïðèíèìàåò çíà÷åíèÿ â èíòåðâàëå (a, b), ãäå−∞ ≤ a < b ≤ +∞, è åå ôóíêöèÿ ðàñïðåäåëåíèÿ F (u) = P(ξ < u) íåïðåðûâíà è ñòðîãî âîçðàñòàåò ïðè u ∈ (a, b).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
