1626435388-4a103190aea56b4a5b3ee742fd66e7b5 (844205), страница 34
Текст из файла (страница 34)
Îäíàêî â ïðîöåññå äîêàçàòåëüñòâà óòâåðæäåíèÿ 3.8 ìûïîêàçàëè, ÷òî ìåòîä ðàññëîåííîé âûáîðêè äàåò óìåíüøåíèå äèñïåðñèè ïî ñðàâíåíèþ ñîñòàíäàðòíûì àëãîðèòìîì 3.1 óæå ïðè âûïîëíåíèè óñëîâèÿ (3.51). Íà ïðàêòèêå âåðîÿòíîñòè {pm }, êàê ïðàâèëî, èçâåñòíû, è âûáîð ÷èñåë èñïûòàíèé {nm } ïðè ïðèìåíåíèèðàññëîåííîé âûáîðêè ïðîèñõîäèò ïî ôîðìóëå (3.51).  ìàòåìàòè÷åñêîé ñòàòèñòèêå òàêàÿ âûáîðêà íàçûâàåòñÿ. äåéñòâèòåëüíîñòè âûáèðàòü {nm } ïî ôîðìóëàì (3.50) èëè (3.51) íåëüçÿ, òàê êàê{nm } îáÿçàíû áûòü öåëûìè. Îáû÷íî âûáèðàþò áëèæàéøèå ê çíà÷åíèÿì (3.50) è (3.51)öåëûå ÷èñëà, óäîâëåòâîðÿþùèå ñîîòíîøåíèþ n = n1 + . . .
+ nM .Óòâåðæäåíèå 3.8 ïîêàçûâàåò, ÷òî ðàññëîåííàÿ âûáîðêà ïî èäåå áëèçêà ê âûáîðêåïî âàæíîñòè: çäåñü òàêæå ïðåäëàãàåòñÿ âûáèðàòü áîëüøå òî÷åê â áîëåå "ñóùåñòâåííûõ"îáëàñòÿõ, îäíàêî âûáîð ðåãóëèðóåòñÿ íå ñïåöèàëüíîé ïëîòíîñòüþ, à óêàçàíèåìêîëè÷åñòâà òî÷åê â ðàçëè÷íûõ îáëàñòÿõ.3.9.3. Ïðèìåðû óäà÷íîãî è íåóäà÷íîãî âûáîðà ÷èñåë {nm }. Ìåòîä ðàññëîåííîé âûáîðêè íå âñåãäà äàåò óìåíüøåíèå äèñïåðñèè. Íåóäà÷íûé âûáîð {nm } ìîæåòïðèâåñòè è ê óâåëè÷åíèþ äèñïåðñèè ïî ñðàâíåíèþ ñî ñòàíäàðòíûì àëãîðèòìîì3.1.R1Ïðèìåð 3.8. Ðàññìîòðèì òåñòîâóþ çàäà÷ó âû÷èñëåíèÿ èíòåãðàëà I = 0 ex dx.
Ñíà÷àëà îöåíèì âåëè÷èíó I ñ èñïîëüçîâàíèåì n = 10 òî÷åê, ðàâíîìåðíî ðàñïðåäåëåííûõ âèíòåðâàëå (0, 1): ζ̄10 = (eα1 + . . . + eα10 ) /10. Äèñïåðñèÿ ýòîé îöåíêè ðàâíàZ 12 !Z 11 e2 112xx2e dx −e dx=− − (e − 1) ≈ 0.02421.Dζ̄10 =1010 2200òèïè÷åñêîéÒåïåðü ðàçîáüåì (0, 1) íà äâà èíòåðâàëà (0, 1/2) è (1/2; 1) (òî åñòü çäåñü M = 2) èáóäåì âûáèðàòü â íèõ ðàâíîìåðíî ðàñïðåäåëåííûå òî÷êè ïî ôîðìóëàì ξ (1) = 0.5α0 èξ (2) = 0.5(1 + α00 ). Òîãäà p1 = p2 = 1/2 è(M )ζ̄10 =n1n21 X1 X(1)(2)exp ξi1 +exp ξi2 ,2n1 i =12n2 i =112ïðè÷åì n1 + n2 = 10. Ñîãëàñíî ôîðìóëå (3.47), äèñïåðñèÿ ýòîé îöåíêè ðàâíà(M )Dζ̄10 =D exp ξ (1) D exp ξ (2)+,4n14n2ãäåD exp ξ (1) = 2Z01/2e2x dx −Z20!21/2ex dx√= e − 1 − 4( e − 1)2 ≈ 0.03492,D exp ξ(2)1Z=221 Ze dx − 2x2xe dx= e2 − e − 4(e −√e)2 ≈ 0.09493.1/21/2Ñîãëàñíî ñîîòíîøåíèþ (3.50), ÷èñëî n1 ñëåäóåò âûáèðàòü áëèçêèì ê.
1 pp1p(1)(1)(2)5 D exp ξD exp ξ +D exp ξ≈ 3.775.22Âîçüìåì n1 = 4 è n2 = 6. Òîãäà(M )Dζ̄10 =11D exp ξ (1) +D exp ξ (2) ≈ 0.006138,1624÷òî çàìåòíî ìåíüøå, ÷åì Dζ̄10 . Åñëè æå âîñïîëüçîâàòüñÿ ôîðìóëàìè (3.51) è âçÿòün1 = n2 = 5, òî1(M )D exp ξ (1) + D exp ξ (2) ≈ 0.006493,Dζ̄10 =20÷òî òàêæå ìåíüøå, ÷åì Dζ̄10 .
 êà÷åñòâå ïðèìåðà íåóäà÷íîãî âûáîðà n1 è n2 ìîæíîðàññìîòðåòü n1 = 9 è n2 = 1. Çäåñü(M )Dζ̄10 =11D exp ξ (1) + D exp ξ (2) ≈ 0.02470,364÷òî óæå áîëüøå, ÷åì Dζ̄10 .g(x) ∈ C(1,...,1) (A, . . . , A; Ql ).(M )Âåñüìà èíòåðåñíûì ÿâëÿåòñÿ ïðåäåëüíûé ñëó÷àé ðàññëîåííîé âûáîðêè ζ̄n , äëÿ êîòîðîãî M = n è n1 = . . . = nM = 1. Çäåñü íà êëàññàõ ãëàäêèõ ïîäûíòåãðàëüíûõ ôóíêöèé(M )óäàåòñÿ ïîëó÷èòü îïòèìàëüíûå (ïî ïîðÿäêó t âåðîÿòíîñòíîé ïîãðåøíîñòè δn ∼ n−tèç (3.5) ïðè n → ∞) àëãîðèòìû ÷èñëåííîãî èíòåãðèðîâàíèÿ [3]. Ïðèâåäåì ñîîòâåòñòâóþùèå ðàññóæäåíèÿ â ñëó÷àå âû÷èñëåíèÿ èíòåãðàëà ïî åäèíè÷íîìó l-ìåðíîìó êóáóZZ 1Z 1I=g(x) dx =...g(x1 , .
. . , xl ) dx1 . . . dxl .(3.52)3.9.4. Îöåíêè ñ îïòèìàëüíîé ñêîðîñòüþ ñõîäèìîñòè äëÿQl00Âûáåðåì â êà÷åñòâå ôóíêöèè f (x) ïëîòíîñòü ðàâíîìåðíîãî ðàñïðåäåëåíèÿ â Ql , ò.å.f (x) ≡ 1 ïðè x ∈ Ql ; ïðè ýòîì ôóíêöèè g(x) è q(x) = g(x)/f (x) ñîâïàäàþò.Ïîëîæèì n = M = K l è ðàçîáüåì èñõîäíóþ îáëàñòü èíòåãðèðîâàíèÿ íà ðàâíûåêóáû()(m)(m)(m)(m)k1 − 1k1kl − 1kl≤ x1 ≤, ... ,≤ xl ≤,(3.53)Xm = (x1 , . .
. , xl ) :KKKK(m)çäåñü ki = 1, . . . , K; i = 1, . . . , l.  ýòîì ñëó÷àå âñå âåðîÿòíîñòè pm îäèíàêîâû è ðàâíû1/K l = 1/n, à ïëîòíîñòè fm (x) ≡ K l ÿâëÿþòñÿ ïëîòíîñòÿìè ðàâíîìåðíîãî ðàñïðåäåëåíèÿ â Xm .Àëãîðèòì 3.6.ξ (m)Xm(3.53)(3.52)Ðåàëèçóåì ïî îäíîé ñëó÷àéíîé òî÷êåè âû÷èñëÿåì èíòåãðàëñîãëàñíî ôîðìóëåI≈θ̄n(M )1= lKKX(m)(m)k1 ,...,kl =1g(ξ(m)â êàæäîì êóáåM1X)=g(ξ (m) ).n m=1âèäà(3.54)Äëÿ îöåíêè (3.54) âûïîëíåíî ñîîòíîøåíèå (3.51) è, ñîãëàñíî ðàññóæäåíèÿì èç äî(M )êàçàòåëüñòâà óòâåðæäåíèÿ 3.8, âûïîëíåíî Dθ̄n ≤ Dζ̄n .Óòî÷íèì îöåíêó äèñïåðñèè â ïðåäïîëîæåíèè, ÷òî ïîäûíòåãðàëüíàÿ ôóíêöèÿ g(x)ïðèíàäëåæèò êëàññó C(1,...,1) (A, . . .
, A; Ql ). Ýòî ÷àñòíûé ñëó÷àé ìíîæåñòâàCr (A; Ql ) = C(r1 ,...,rl ) (A1 , . . . , Al ; Ql )ôóíêöèé l ïåðåìåííûõ, ó êîòîðûõ (rs − 1)-å ïðîèçâîäíûå ïî s-îé êîîðäèíàòå íåïðåðûâíû, à rs -å ïðîèçâîäíûå êóñî÷íî-íåïðåðûâíû è îãðàíè÷åíû ïî ìîäóëþ êîíñòàíòîé As âêóáå Ql äëÿ s = 1, . .
. , l. Ôóíêöèÿ g(x) ∈ C(1,...,1) (A, . . . , A), â ÷àñòíîñòè, óäîâëåòâîðÿåòóñëîâèþ Ëèïøèöà ñ êîíñòàíòîé A ïî êàæäîé èç ïåðåìåííûõ.Èç ñîîòíîøåíèé (3.47) è (3.54) ñëåäóåò ðàâåíñòâîDθ̄n(M )MMXD(g(ξ (m) )) X E(g(ξ (m) ) − gm )2==,n2n2m=1m=1(3.55)Rãäå gm = Eg(ξ (m) ) = K l Xm g(x) dx. Èç òåîðåìû î ñðåäíåì ñëåäóåò, ÷òî äëÿ êàæäîãîRm íàéäåòñÿ òî÷êà xm ∈ Xm , òàêàÿ, ÷òî Xm g(x) dx = g(xm )/K l . Ñëåäîâàòåëüíî, gm =g(xm ). òî æå âðåìÿ äëÿ ïðèðàùåíèé ∆i , i = 1, .
. . , l èìååìg(x1 + ∆1 , . . . , xl + ∆l ) − g(x1 , . . . , xl ) = g(x1 + ∆1 , . . . , xl + ∆l )−−g(x1 + ∆1 , . . . , xl ) + g(x1 + ∆1 , . . . , xl−1 + ∆l−1 , xl ) − g(x1 + ∆1 , . . . , xl−1 , xl ) + . . .. . . + g(x1 + ∆1 , x2 , . . . , xl ) − g(x1 , . . . , xl ) .Îòñþäà ñëåäóåò, ÷òî äëÿ g(x) ∈ C(1,...,1) (A, .
. . , A; Ql ) âûïîëíåíî|g(x1 + ∆1 , . . . , xl + ∆l ) − g(x1 , . . . , xl )| ≤ A(|∆1 | + . . . + |∆l |).Òàê êàê òî÷êà ξ (m) ïðèíàäëåæèò Xm , òî êàæäàÿ èç åå êîîðäèíàò îòëè÷àåòñÿ îò ñîîòâåòñòâóþùåé êîîðäèíàòû òî÷êè xm íå áîëåå ÷åì íà K −1 . Ïîýòîìó èç ïîñëåäíåãîíåðàâåíñòâà, ñ ó÷åòîì ñîîòíîøåíèÿ ∆i < K −1 , èìååì|g(ξ (m) ) − g(xm )| ≤ AlK −1 èëè |g(ξ (m) ) − gm | ≤ AlK −1 .(3.56)Ó÷èòûâàÿ, ÷òî äëÿ ëþáîé ñëó÷àéíîé âåëè÷èíû η âûïîëíåíî íåðàâåíñòâî |Eη| ≤ sup |η|,èç ñîîòíîøåíèé (3.55), (3.56) ïîëó÷àåìDθ̄n(M )MM sup (m)(g(ξ (m) ) − gm )2XXA2 l 2(AlK −1 )2ξ ∈Xm−2 2 2 −2/l≤=nnAln=.≤n2n2n1+2/lm=1m=1Ïî àíàëîãèè ñ ðàññóæäåíèÿìè ðàçäåëà 3.1, èìååìσ̃ (M )Al(M )P δ̃n ≤ βε √ ≤ βε 1/2+1/l ≥ 1 − ε.nnq(M )(M )Çäåñü σ̃= n Dθ̄n , ïðè÷åì ñïðàâåäëèâî íåðàâåíñòâî σ̃ (M ) ≤ Al/n1/l .
Ïîëó÷åííûé(M )ïîðÿäîê t = 1/2 + 1/l ÿâëÿåòñÿ äëÿ ïîãðåøíîñòè δ̃nñëåäóþùåå∼ n−t íåóëó÷øàåìûì. Ýòî äàåòÑóùåñòâóþò ïîëîæèòåëüíûå êîíñòàíòû H(r, A) è P , óäîâëåòâîðÿþùèå ñëåäóþùåìóñîîòíîøåíèþ. Äëÿ ëþáîãî íàòóðàëüíîãî M è ëþáîé ðàññëîåííîé âûáîðêè ζ̄n(M ) âèäà (3.46) èç àëãîðèòìà 3.5 íàéäåòñÿ ôóíêöèÿ g(x) ∈ Cr(A; Ql ),äëÿ êîòîðîéÓòâåðæäåíèå 3.9.H(r, A)(3.57)nr+1/2r = (r1 , . . . , rl ), A = (A1 , . . . , Al ), 1/r = 1/r1 + . . . + 1/rl .δn(M ) (r, A) = |ζ̄n(M ) − I| >ñ âåðîÿòíîñòüþ P ; çäåñüÄëÿ ðàññìàòðèâàåìîãî ìíîæåñòâà ôóíêöèé èìååì r = (1, .
. . , 1), A = (A, . . . , A) èr = 1/l. Ñëåäîâàòåëüíî, ñîãëàñíî ñîîòíîøåíèþ (3.57), äëÿ êëàññà C(1,...,1) (A, . . . , A; Ql )(1)ïîëó÷àåì δ̃n > H/n1/2+1/l . Òàêèì îáðàçîì, äëÿ îöåíêè (3.54) íàøëèñü êîíñòàíòû H1 (P )è H2 (P ), äëÿ êîòîðûõ ñ çàäàííîé âåðîÿòíîñòüþ P âûïîëíåíî äâîéíîå íåðàâåíñòâîH2 (P )H1 (P )< δ̃n(M ) ≤ 1/2+1/l ,1/2+1/lnn÷òî îçíà÷àåò îïòèìàëüíîñòü àëãîðèòìà 3.6 ïî ïîðÿäêó t âåðîÿòíîñòíîé ïîãðåøíîñòè(M )δ̃n ∼ n−t .3.9.5.
Îöåíêè ñ îïòèìàëüíîé ñêîðîñòüþ ñõîäèìîñòè äëÿ g(x) ∈ C(2,...,2) (A, . . . , A; Ql ).Ñëó÷àé r = (2, . . . , 2), A = (A, . . . , A) èíòåðåñåí òåì, ÷òî â ñîîòâåòñòâóþùåì îïòèìàëüíîì àëãîðèòìå èñïîëüçóåòñÿ ìåòîä ïðîòèâîïîëîæíîé ïåðåìåííîé ïî ñëó÷àéíîìóíàïðàâëåíèþ [3].Àëãîðèòì 3.7.ξ (m)Xm(m)(m)ξXm(3.53)ξ sim(3.52)!MM(m)(m)X1)1 X (m)g(ξ)+g(ξ(m)sim));(3.58)I ≈ Θ̄(M==g(ξ)+g(ξnsimM m=12n m=1Ðåàëèçóåì ïî îäíîé ñëó÷àéíîé òî÷êåâ êàæäîì êóáå âèîòíîñèòåëüíî öåíòðà êóáà .äà.
Ñòðîèì òî÷êó , ñèììåòðè÷íóþÂû÷èñëÿåì èíòåãðàëñîãëàñíî ôîðìóëåçäåñü n = 2M= 2K l .(m)(m)Òî÷êè ξEè ξ sim ðàñïðåäåëåíû ðàâíîìåðíî â Xm , ïîýòîìó! Z!!(m)(m)g(ξ (m) )g(ξ sim )g(ξ (m) ) + g(ξ sim )=E=E=g(x) dxKlKlnXm(M )è, ñëåäîâàòåëüíî, EΘ̄nm, èìååì(m)= I .  ñèëó òîãî, ÷òî ïàðû (ξ (m) , ξ sim ) íåçàâèñèìû äëÿ ðàçíûõ)DΘ̄(MnM1 X (m)(m)= 2D g(ξ ) + g(ξ sim ) .n m=1(3.59)Îáîçíà÷èì ÷åðåç xm öåíòð êóáà Xm . Âû÷èòàÿ ïîñòîÿííóþ ïîä çíàêîì äèñïåðñèè, ïîëó÷àåì ðàâåíñòâî(m)(m)(m)(m)D g(ξ ) + g(ξ sim ) = D g(ξ ) − 2g(xm ) + g(ξ sim ) .(3.60)(m)(m)Ïðè ôèêñèðîâàííîé òî÷êå ξ (m) = (ξ1 , .
. . , ξl(m)h(t) = gk1(m)− 1/2 ξ1+K(m)) ââåäåì â ðàññìîòðåíèå ôóíêöèþ(m)− (k1 − 1/2)kt, . . . , lK(m)− 1/2 ξl+K!(m)− (kl − 1/2)t .K(m)Î÷åâèäíî, ÷òî h(1) = g(ξ (m) ), h(0) = g(xm ), h(−1) = g(ξ sim ).  òåîðèè ÷èñëåííîãîäèôôåðåíöèðîâàíèÿ õîðîøî èçâåñòíî ïðåäñòàâëåíèå(m)g(ξ (m) ) − 2g(xm ) + g(ξ sim ) = h(1) − 2h(0) + h(−1) = h00 (θ), |θ| ≤ 1.Íåïîñðåäñòâåííûì äèôôåðåíöèðîâàíèåì ïîëó÷àåì00h (t) =lX(m)k1gxi xji,j=1(m)− 1/2 ξ1+K(m)(m)× ξi(m)(m)Òàê êàê (ξ1 , .
. . , ξl|h00 (t)| ≤−ki(m)(m)− (k1 − 1/2)kt, . . . , lK− 1/2K(m)) ∈ Xm , òî |ξi!(m)×(m)− (ki(m)ξj−kj(m)− 1/2 ξl+K− 1/2K!(m)− (kl − 1/2)t ×K!.− 1/2)/K| ≤ 1/(2K). ÏîýòîìóAl2Al2(m)(m))|≤ïðè|t|≤1è|g(ξ)−2g(x)+g(ξ.msim4K 24K 2Èç ñîîòíîøåíèÿ (3.60) èìååìD g(ξ(m))+(m)g(ξ sim )≤ E g(ξ(m)) − 2g(xm ) +2(m)g(ξ sim )≤Al24K 22.Ïîäñòàâèâ ýòó îöåíêó â ñîîòíîøåíèå (3.59) è âñïîìèíàÿ, ÷òî n = 2M = 2K l , ïîëó÷àåì)DΘ̄(Mn1≤ 2 ×M ×nAl24K 22=(Al2 )2 24/l.32n1+4/lÏî àíàëîãèè ñ ðàññóæäåíèÿìè ðàçäåëà 3.1, èìååìP δ̂n(M )qσ̂ (M )Al2 21/2+2/l≤ βε p≤ βε8n1/2+2/ln/2!≥ 1 − ε.(M )Çäåñü σ̂= (n/2) DΘ̄n , ïðè÷åì ñïðàâåäëèâî íåðàâåíñòâî σ̂ (M ) ≤ Al2 22/l /(8n2/l ).
Èçóòâåðæäåíèÿ 3.9 ñëåäóåò, ÷òî ïîëó÷åííûé ïîðÿäîê t = 1/2 + 2/l ÿâëÿåòñÿ äëÿ ïîãðåø(M )íîñòè δ̂n ∼ n−t íåóëó÷øàåìûì (âåäü â ñîîòíîøåíèè (3.57) äëÿ ñëó÷àÿ r = (2, . . . , 2)÷èñëî r ðàâíî r = 2/l).Çàìåòèì, ÷òî àëãîðèòìû 3.6 è 3.7 äîïóñêàþò íåñêîëüêî íàçâàíèé. Âî-ïåðâûõ, ýòî÷àñòíûå ñëó÷àè(ñì. àëãîðèòì 3.5) äëÿ n = M èn = 2M ñîîòâåòñòâåííî.
Âî-âòîðûõ, â ñâÿçè ñ íàëè÷èåì äèñêðåòèçàöèè îáëàñòè èíòåãðèðîâàíèÿ X , îïðåäåëÿåìîé ðàçáèåíèåì X íà ìàëûå êóáû Xm âèäà (3.53), è ñ âûáîðîìîäíîé èëè äâóõ ñëó÷àéíûõ òî÷åê â êàæäîì ìàëîì êóáå ìîæíî îòíåñòè àëãîðèòìû 3.6 è3.7 ê(ñì. äàëååðàçäåë 5.3). Â-òðåòüèõ, àëãîðèòìû 3.6 è 3.7 ÿâëÿþòñÿ ÷àñòíûìè ñëó÷àÿìè(ñì. äàëåå ïîäðàçä. 3.10.2).Îòìåòèì, ÷òî ðåçóëüòàòû, ïðåäñòàâëåííûå â ïîäðàçä. 3.9.4 è 3.9.5 è ïîëó÷åííûåâ íà÷àëå øåñòèäåñÿòûõ ãîäîâ 20-ãî âåêà Í.Ñ.Áàõâàëîâûì, âûçâàëè áîëüøîé íàó÷íûéðåçîíàíñ è ïðèâåëè ê áóðíîìó ðàçâèòèþ (ãëàâíûì îáðàçîì, â çàïàäíîåâðîïåéñêèõ íàó÷íûõ øêîëàõ)[6].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
