1626435386-4ea3b7438ebb2e92437735aa9b26c4d2 (844201), страница 13
Текст из файла (страница 13)
Âûáîðêàïî ãðóïïàì. Ðàññìîòðèì ïðåäñòàâëåíèå (1.4) èíRòåãðàëà I =Xg(x) dx. Çàïèøåì âåëè÷èíó I â âèäåI=M ZXm=1q(x)f (x) dx,Xmãäå Xm ïîäîáëàñòè X , èìåþùèå ïîïàðíûå ïåðåñå÷åíèÿ ìåðû íóëü,ïðè÷åì X = X1 ∪ . . . ∪ XM . Ââåäåì îáîçíà÷åíèÿZZf (x)f (x) dx, Im =q(x)f (x) dx, fm (x) =pm =pmXmXmïðè x ∈ Xm . Ïðåäïîëîæèì, ÷òî f (x) = 0 ïðè x 6∈ X . Òîãäàp1 + . .
. + pM = 1,I1 + . . . + IM = I è Im = E pm q(ξ (m) ) ,ãäå ñëó÷àéíûé âåêòîð ξ (m) ðàñïðåäåëåí â Xm ñîãëàñíî ïëîòíîñòè fm (x).ÀËÃÎÐÈÒÌ 16.1. Ïðèáëèæåííî âû÷èñëåíèåì çíà÷åíèÿ Im ñîãëàñíîñòàíäàðòíîìó àëãîðèòìó (1.5) ñ ÷èñëîì èñïûòàíèé nmImnmnmMXpm Xpm X(m)(m)(M )≈q(ξ im ) è ïîëàãàåì I ≈ ζ̄n =q(ξ im ),nm i =1nm=1 m i =1mm(16.1)çäåñü n = n1 + . . .
+ nM .Àëãîðèòì 16.1 îïðåäåëÿåò ìåòîä ðàññëîåííîé âûáîðêè èëè âûáîðêó ïî ãðóïïàì (ñì., íàïðèìåð, [1, 16]). Ýòîò àëãîðèòì îòëè÷àåòñÿ ïðèM = 2 îò ìåòîäà èíòåãðèðîâàíèÿ ïî ÷àñòè îáëàñòè èç ðàçä. 13,ò. ê. ïîñëåäíèé ïðåäïîëàãàåò, ÷òî èíòåãðàë I2 èçâåñòåí (â òî âðåìÿ êàêâ àëãîðèòìå 16.1 ýòîò èíòåãðàë âû÷èñëÿåòñÿ ïðèáëèæåííî ïî âûáîðêå(2){ξ i2 }).16.2. Ìèíèìèçàöèÿ äèñïåðñèè ìåòîäà ðàññëîåííîé âûáîðêè.Ñðàâíèì äèñïåðñèþ Dζ̄n = Dζ/n ñòàíäàðòíîãî ìåòîäà (1.5) âû÷èñëåíèÿ èíòåãðàëà I (çäåñü ñëó÷àéíûå òî÷êè ξ âûáèðàþòñÿ âî âñåé îáëàñòè(M )èíòåãðèðîâàíèÿ X ) è äèñïåðñèþ Dζ̄nìåòîäà ðàññëîåííîé âûáîðêèïðè óñëîâèè, ÷òî ôèêñèðîâàíû ÷èñëî èñïûòàíèé (äëÿ âûáîðêè ïî ãðóï64ïàì ñóììàðíîå ÷èñëî èñïûòàíèé) n è ðàçáèåíèå îáëàñòè èíòåãðèðîâàíèÿ X = X1 ∪ .
. . ∪ XM . Ïî àíàëîãèè ñ ôîðìóëîé (2.1) èìååìDζ̄n(M )2 XnmM MXXpmp2m Dq(ξ (m) )(m)=Dq(ξ im ) =,nmnmm=1m=1i =1(16.2)mãäåDq(ξ (m) ) =1pmZq 2 (x)f (x) dx −XmImpm2;(16.3)(m)çäåñü èñïîëüçîâàíà íåçàâèñèìîñòü ñëó÷àéíûõ òî÷åê {ξ im }.(M )ÓÒÂÅÐÆÄÅÍÈÅ 16.1. Ìèíèìóì âåëè÷èíû Dζ̄n!2qM1 X(m)2dn =pm Dq(ξ ) .n m=1ðàâåíÝòà âåëè÷èíà íå ïðåâîñõîäèò Dζ̄n è ðåàëèçóåòñÿ ïðè, MqqX0(m)nm = npm Dq(ξ )pm0 Dq(ξ (m ) ).(16.4)(16.5)m0 =1ÄÎÊÀÇÀÒÅËÜÑÒÂÎ. Âåëè÷èíà d2n èç (16.4) ïðåäñòàâèìà â âèäå2srM(m)XDq(ξ)nmd2n = pm×.nnmm=1Èñïîëüçóÿ íåðàâåíñòâî ÊîøèÁóíÿêîâñêîãî, ïîëó÷àåìd2n ≤MMMXXp2m Dq(ξ (m) ) X nmp2m Dq(ξ (m) )=×,nmnnmm=1m=1m=1ãäå ñïðàâà ñòîèò âûðàæåíèå (16.2). Íåñëîæíî ïðîâåðèòü, ÷òî ïðè ïîäñòàíîâêå ðàâåíñòâà (16.5) â ôîðìóëó (16.2) ïîëó÷àåòñÿ ñîîòíîøåíèå(16.4).Äàëåå, óìíîæàÿ (16.3) íà pm è ñóììèðóÿ ïîëó÷åííûå ðåçóëüòàòû ïîm, èìååìMXm=1pm Dq(ξ(m)Zq 2 (x)f (x) dx −)=X65M2XIm.pm=1 mÅùå ðàç ïðèìåíÿÿ íåðàâåíñòâî ÊîøèÁóíÿêîâñêîãî, ïîëó÷àåì2I =MX!2MM MM22XXXXImImIm√p≤××.p=√mmpmppm=1 m m=1m=1m=1 m!2Im=m=1Îòñþäà ñëåäóåò, ÷òî1Dζ̄n =nZ2q (x)f (x) dx − I2X1≥n(M )Ïîñëåäíåå âûðàæåíèå ðàâíî âåëè÷èíå Dζ̄nnm = n pm .(M )MX!pm Dq(ξ(m)) .m=1ïðè óñëîâèè(16.6)Òàêèì îáðàçîì, d2n ≤ Dζ̄n |nm =n pm ≤ Dζ̄n .
Óòâåðæäåíèå 16.1 äîêàçàíî. ðåàëüíûõ çàäà÷àõ äèñïåðñèè {Dq(ξ (m) )}, êàê ïðàâèëî, íåèçâåñòíû è âûáîð {nm } ïî ôîðìóëå (16.5) íåâîçìîæåí. Îäíàêî â ïðîöåññåäîêàçàòåëüñòâà óòâåðæäåíèÿ 16.1 ìû ïîêàçàëè, ÷òî ìåòîä ðàññëîåííîéâûáîðêè äàåò óìåíüøåíèå äèñïåðñèè ïî ñðàâíåíèþ ñî ñòàíäàðòíûì àëãîðèòìîì (1.5) óæå ïðè âûïîëíåíèè óñëîâèÿ (16.6).
Íà ïðàêòèêå âåðîÿòíîñòè {pm }, êàê ïðàâèëî, èçâåñòíû, è âûáîð ÷èñåë èñïûòàíèé {nm }ïðè ïðèìåíåíèè ðàññëîåííîé âûáîðêè ïðîèñõîäèò ïî ôîðìóëå (16.6)(â ìàòåìàòè÷åñêîé ñòàòèñòèêå òàêàÿ âûáîðêà íàçûâàåòñÿ òèïè÷åñêîé).Íàïðèìåð, ïðè X = Qd è f (x) ≡ 1 äëÿ ðàçáèåíèÿ (9.7) ìîæíî âçÿòü âñånm ðàâíûìè n/M (ïîçàáîòèâøèñü î òîì, ÷òîáû ýòî ÷èñëî áûëî öåëûì).Óòâåðæäåíèå 16.1 ïîêàçûâàåò, ÷òî ðàññëîåííàÿ âûáîðêà ïî èäåå áëèçêà ê âûáîðêå ïî âàæíîñòè (ñì. ðàçä. 2, 10): çäåñü òàêæå ïðåäëàãàåòñÿâûáèðàòü áîëüøå òî÷åê â áîëåå ¾ñóùåñòâåííûõ¿ îáëàñòÿõ, îäíàêî âûáîð ðåãóëèðóåòñÿ íå ñïåöèàëüíîé ïëîòíîñòüþ, à óêàçàíèåì êîëè÷åñòâàòî÷åê â ðàçëè÷íûõ îáëàñòÿõ.16.3. Ïðèìåðû óäà÷íîãî è íåóäà÷íîãî âûáîðà ÷èñåë {nm }.Ìåòîä ðàññëîåííîé âûáîðêè íå âñåãäà äàåò óìåíüøåíèå äèñïåðñèè. Íåóäà÷íûé âûáîð {nm } ìîæåò ïðèâåñòè è ê óâåëè÷åíèþ äèñïåðñèè ïîñðàâíåíèþ ñî ñòàíäàðòíûì àëãîðèòìîì (1.5).R1Ðàññìîòðèì òåñòîâóþ çàäà÷ó âû÷èñëåíèÿ èíòåãðàëà I = 0 ex dx.Ñíà÷àëà îöåíèì âåëè÷èíó I ñ èñïîëüçîâàíèåì n = 10 òî÷åê, ðàâíîìåðíî ðàñïðåäåëåííûõ â èíòåðâàëå (0, 1): ζ̄10 = (eα1 + .
. . + eα10 ) /10.66Äèñïåðñèÿ ýòîé îöåíêè ðàâíàDζ̄101Z1=102 !e dx=1Z2xxdx −ee22−0012− (e − 1)2≈ 0.02421.10Òåïåðü ðàçîáüåì (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.
Ñîãëàñíî ôîðìóëå (16.2), äèñïåðñèÿ ýòîé îöåíêèðàâíàD exp ξ (1)D exp ξ (2)(M )Dζ̄10 =+,4n14n2ãäåD exp ξ (1) = 2Z1/2e2x dx− 20D exp ξ(2)Z!21/2Zex dx√= e−1−4( e−1)2 ≈ 0.03492,01=22xe1/2Z!21dx− 2xe dx√= e2 −e−4(e− e)2 ≈ 0.09493.1/2Ñîãëàñíî ñîîòíîøåíèþ (16.5), ÷èñëî 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 . Åñëè æå âîñïîëüçîâàòüñÿôîðìóëàìè (16.6) è âçÿòü n1 = n2 = 5, òî(M )Dζ̄10=1 D exp ξ (1) + D exp ξ (2) ≈ 0.006493,2067÷òî òàêæå ìåíüøå, ÷åì Dζ̄10 .  êà÷åñòâå ïðèìåðà íåóäà÷íîãî âûáîðà n1è n2 ìîæíî ðàññìîòðåòü n1 = 9 è n2 = 1. Çäåñü(M )Dζ̄10=11D exp ξ (1) + D exp ξ (2) ≈ 0.02470,364÷òî óæå áîëüøå, ÷åì Dζ̄10 .17. Îïòèìàëüíûå êóáàòóðíûå ôîðìóëûâ C (1,...,1) (L, .
. . , L; Qd ) è C 2 (L; Qd )17.1. Îöåíêè ñ îïòèìàëüíîé ñêîðîñòüþ ñõîäèìîñòè äëÿg(x) ∈ C (1,...,1) (L, . . . , L; Qd ). Âåñüìà èíòåðåñíûì ÿâëÿåòñÿ ïðåäåëüíûé(M )ñëó÷àé ðàññëîåííîé âûáîðêè ζ̄n , äëÿ êîòîðîãî M = n è n1 = . . . =nM = 1. Çäåñü íà êëàññàõ ãëàäêèõ ïîäûíòåãðàëüíûõ ôóíêöèé óäàåòñÿ ïîëó÷èòü îïòèìàëüíûå (ïî ïîðÿäêó t âåðîÿòíîñòíîé ïîãðåøíîñòè(M )δn ∼ n−t èç (1.6) ïðè n → ∞) àëãîðèòìû ÷èñëåííîãî èíòåãðèðîâàíèÿ[2, 7]. Ïðèâåäåì ñîîòâåòñòâóþùèå ðàññóæäåíèÿ â ñëó÷àå âû÷èñëåíèÿèíòåãðàëà ïî åäèíè÷íîìó d-ìåðíîìó êóáóZZ 1Z 1I=g(x) dx =...g(x(1) , . . .
, x(d) ) dx(1) . . . dx(d) .(17.1)Qd00Âûáåðåì â êà÷åñòâå ôóíêöèè f (x) ïëîòíîñòü ðàâíîìåðíîãî ðàñïðåäåëåíèÿ â Qd , ò. å. f (x) ≡ 1 ïðè x ∈ Qd ; ïðè ýòîì ôóíêöèè g(x) èq(x) = g(x)/f (x) ñîâïàäàþò.Ïîëîæèì n = M = µd è ðàçîáüåì èñõîäíóþ îáëàñòü èíòåãðèðîâàíèÿíà ðàâíûå êóáû(i)(i)Xm = x = x(1) , . . . , x(d) : (jm− 1)/µ ≤ x(i) ≤ jm/µ ;(17.2)(i)çäåñü i = 1, . . . , d, jm = 1, . . .
, µ (ñì. òàêæå ôîðìóëó (9.7)).  ýòîìñëó÷àå âñå âåðîÿòíîñòè pm îäèíàêîâû è ðàâíû 1/µd = 1/n, à ïëîòíîñòèfm (x) ≡ µd ÿâëÿþòñÿ ïëîòíîñòÿìè ðàâíîìåðíîãî ðàñïðåäåëåíèÿ â Xm .ÀËÃÎÐÈÒÌ 17.1. Ðåàëèçóåì ïî îäíîé ñëó÷àéíîé òî÷êå ξ m â êàæäîì êóáå Xm âèäà (17.2) è âû÷èñëÿåì ïðèáëèæåíèå èíòåãðàëà (17.1)ñîãëàñíî ôîðìóëåI≈θ̄n(M )1= dµµX(1)g(ξ m ) =(d)jm ,...,jm =168M1 Xg(ξ m ).n m=1(17.3)Äëÿ îöåíêè (17.3) âûïîëíåíî ñîîòíîøåíèå (16.6) è, ñîãëàñíî ðàññóæ(M )äåíèÿì èç äîêàçàòåëüñòâà óòâåðæäåíèÿ 16.1, âûïîëíåíî Dθ̄n ≤ Dζ̄n .Óòî÷íèì îöåíêó äèñïåðñèè â ïðåäïîëîæåíèè, ÷òî ïîäûíòåãðàëüíàÿôóíêöèÿ g(x) ïðèíàäëåæèò êëàññó C (1,...,1) (L, . .
. , L; Qd ) (ñîîòâåòñòâóþùåå îïðåäåëåíèå äàíî âûøå â ïîäðàçä. 9.4).Èç ñîîòíîøåíèé (16.2) è (17.3) ñëåäóåò ðàâåíñòâîDθ̄n(M )MMXXE(g(ξ m ) − gm )2D(g(ξ m )=,=n2n2m=1m=1(17.4)Rãäå gm = Eg(ξ m ) = µd Xm g(x) dx. Èç òåîðåìû î ñðåäíåì ñëåäóåò, ÷òîRäëÿ êàæäîãî m íàéäåòñÿ òî÷êà xm ∈ Xm , òàêàÿ, ÷òî Xm g(x) dx =g(xm )/µd . Ñëåäîâàòåëüíî, gm = g(xm ). òî æå âðåìÿ äëÿ ïðèðàùåíèé ∆(i) , i = 1, . . . , d èìååìg(x(1) + ∆(1) , . .
. , x(d) + ∆(d) ) − g(x(1) , . . . , x(d) ) == g(x(1) +∆(1) , . . . , x(d) +∆(d) )−g(x(1) +∆(1) , . . . , x(d−1) +∆(d−1) , x(d) ) ++ g(x(1) +∆(1) , . . . , x(d−1) +∆(d−1) , x(d) )−g(x(1) +∆(1) , . . . , x(d−1) , x(d) ) +. . .+ g(x(1) + ∆(1) , x(2) , . . . , x(d) ) − g(x(1) , . . . , x(d) ) .Îòñþäà ñëåäóåò, ÷òî äëÿ g(x) ∈ C (1,...,1) (L, . . . , L; Qd ) âûïîëíåíî (1)g(x + ∆(1) , . . .
, x(d) + ∆(d) ) − g(x(1) , . . . , x(d) ) ≤ L(|∆(1) | + . . . + |∆(d) |).Òàê êàê òî÷êà ξ m ïðèíàäëåæèò Xm , òî êàæäàÿ èç åå êîîðäèíàò îòëè÷àåòñÿ îò ñîîòâåòñòâóþùåé êîîðäèíàòû òî÷êè xm íå áîëåå ÷åì íà µ−1 .Ïîýòîìó èç ïîñëåäíåãî íåðàâåíñòâà, ñ ó÷åòîì ñîîòíîøåíèÿ ∆(i) < µ−1 ,èìååì|g(ξ m ) − g(xm )| ≤ Ldµ−1 èëè |g(ξ m ) − gm | ≤ Ldµ−1 .(17.5)RÈñïîëüçóÿ î÷åâèäíîå íåðàâåíñòâî Y z(y) dy ≤ supy∈Y |z(y)| × mes Y ,èç ñîîòíîøåíèé (17.4), (17.5) è n = M ïîëó÷àåìDθ̄n(M ) ≤MXsupym ∈Xm (g(ym ) − gm )2≤n2m=169≤MX(Ldµ−1 )2L2 d2= n n−2 L2 d2 n−2/d = 1+2/d .2nnm=1Ïî àíàëîãèè ñ ðàññóæäåíèÿìè ïîäðàçä.
1.3 èìååìσ̃ (M )Ld(M )(M ) P δ̃n = δn n=M ≤ Bε √ ≤ Bε 1/2+1/d ≥ 1 − ε.nnq(M )Çäåñü σ̃ (M )=n Dθ̄n , ïðè÷åì ñïðàâåäëèâî íåðàâåíñòâîσ̃ (M ) ≤ Ld/n1/d . Ïîëó÷åííûé ïîðÿäîê t = 1/2 + 1/d ÿâëÿåòñÿ äëÿ(M )ïîãðåøíîñòè δ̃n ∼ n−t íåóëó÷øàåìûì. Ýòî äàåò ñëåäóþùàÿËÅÌÌÀ 17.1 [2, 7]. Ñóùåñòâóþò ïîëîæèòåëüíûå êîíñòàíòûH(r, L) è P , óäîâëåòâîðÿþùèå ñëåäóþùåìó ñîîòíîøåíèþ.
Äëÿ ëþáî(M )ãî íàòóðàëüíîãî M è ëþáîé ðàññëîåííîé âûáîðêè ζ̄n âèäà (16.1) èçàëãîðèòìà 16.1 íàéäåòñÿ ôóíêöèÿ g(x) ∈ C r (L; Qd ), äëÿ êîòîðîéH(r, L)nr+1/2r(1) , . . . , r(d) , L =δn(M ) (r, L) = |ζ̄n(M ) − I| >(17.6)ñ âåðîÿòíîñòüþ P ; çäåñü r =L(1) , . . . , L(d) ,1/r = 1/r1 + . . . + 1/rd .Äëÿ ðàññìàòðèâàåìîãî ìíîæåñòâà ôóíêöèé èìååì r = (1, . . . , 1),L = (L, . . . , L) è r = 1/d. Ñëåäîâàòåëüíî, ñîãëàñíî ñîîòíîøåíèþ (17.6),(M )> H̃/n1/2+1/d . Òàêèìäëÿ êëàññà C (1,...,1) (L, . . .
, L; Qd ) ïîëó÷àåì δ̃nîáðàçîì, äëÿ îöåíêè (17.3) íàøëèñü êîíñòàíòû H1 (P ) è H2 (P ), äëÿ êîòîðûõ ñ çàäàííîé âåðîÿòíîñòüþ P âûïîëíåíî äâîéíîå íåðàâåíñòâîH1 (P )H2 (P )< δ̃n(M ) ≤ 1/2+1/d ,n1/2+1/dn÷òî îçíà÷àåò îïòèìàëüíîñòü àëãîðèòìà 17.1 ïî ïîðÿäêó t âåðîÿòíîñòíîé(M )ïîãðåøíîñòè δ̃n ∼ n−t .17.2. Îöåíêè ñ îïòèìàëüíîé ñêîðîñòüþ ñõîäèìîñòè äëÿg(x) ∈ C 2 (L; Qd ). Ïðåäïîëîæèì, ÷òî ïîäûíòåãðàëüíàÿ ôóíêöèÿ g(x)ïðèíàäëåæèò êëàññó C 2 (L, Qd ) ⊂ C (2,..,2) (L, .., L; Qd ) ôóíêöèé, èìåþùèõ íåïðåðûâíûå ñìåøàííûå ïðîèçâîäíûå âòîðîãî ïîðÿäêà, îãðàíè÷åííûå â ñîâîêóïíîñòè îáùåé êîíñòàíòîé L. Ýòîò ñëó÷àé èíòåðåñåíòåì, ÷òî â ñîîòâåòñòâóþùåì îïòèìàëüíîì àëãîðèòìå èñïîëüçóåòñÿ ìåòîä ïðîòèâîïîëîæíîé ïåðåìåííîé ïî ñëó÷àéíîìó íàïðàâëåíèþ (ñì. äàëåå ðàçä.
18).70ÀËÃÎÐÈÒÌ 17.2. Ðåàëèçóåì ïî îäíîé ñëó÷àéíîé òî÷êå ξ m â êàæäîì êóáå Xm âèäà (17.2). Ñòðîèì òî÷êó ξm,sim , ñèììåòðè÷íóþ ξmîòíîñèòåëüíî öåíòðà êóáà Xm . Âû÷èñëÿåì ïðèáëèæåíèå èíòåãðàëà(17.1) ñîãëàñíî ôîðìóëåM M1 X g(ξ m ) + g(ξ m,sim )1 XI≈==g(ξ m ) + g(ξ m,sim ) ;M m=12n m=1(17.7)çäåñü n = 2M = 2µd .Òî÷êè ξ m è ξ m,sim ðàñïðåäåëåíû ðàâíîìåðíî â Xm , ïîýòîìó)Θ̄(MnEg(ξ m )µd=Eg(ξ m,sim )µd=Eg(ξ m ) + g(ξ m,sim )nZg(x) dx=Xm(M )è, ñëåäîâàòåëüíî, EΘ̄n = I .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
