1626435386-4ea3b7438ebb2e92437735aa9b26c4d2 (844201), страница 16
Текст из файла (страница 16)
Ïîñòðîåíèå äîâåðèòåëüíûõ ãðàíèö è îïòèìèçàöèÿ îöåíîê ζn(H) è ζ̃n(H) . Èìååòñÿ òàêæå àíàëîãèÿ ìåæäó îöåíêàìè (19.3) è(20.1) â ðàññóæäåíèÿõ î ïîëó÷åíèè äîâåðèòåëüíûõ ãðàíèö ïîãðåøíîñòè (H)(H)δn = ζn − I è î âûáîðå îïòèìàëüíîãî µ. Çäåñü ëåììà 19.1 ïîçâî(H)ëÿåò óòâåðæäàòü, ÷òî ñëó÷àéíàÿ âåëè÷èíà ζn äëÿ áîëüøèõ n èìååòðàñïðåäåëåíèå, áëèçêîå ê íîðìàëüíîìó, ñ ìàòåìàòè÷åñêèì îæèäàíèåìI è äèñïåðñèåé D(H) . Ñëåäîâàòåëüíî,äëÿ áîëüøèõ n âûïîëíåíî ïðè√(H)áëèæåííîå ðàâåíñòâî P(δn ≤ G D(H) ) ≈ P(|γ| ≤ G), ãäå G ïîëîæèòåëüíàÿ êîíñòàíòà, à γ ∈ N (0, 1) ñòàíäàðòíàÿ íîðìàëüíàÿ ñëó÷àéíàÿâåëè÷èíà.
Îòñþäà äëÿ ëþáîãî ε > 0 íàéäóòñÿ êîíñòàíòà Gε è íàòóðàëü-83íîå ÷èñëî N0 òàêèå, ÷òî äëÿ âñåõ n > N0 âûïîëíåíî íåðàâåíñòâî!rZ2B (H)(H)(H)P δ n ≤ Gε> 1 − ε; B=q(x) − I(2 − H(x)) f (x) dx.nX(20.10)Íåñëîæíî òàêæå ïîëó÷èòü àíàëîã ñîîòíîøåíèÿ (19.11) äëÿ äèñêðåòíî(H)ñòîõàñòè÷åñêîé îöåíêè ζ̃n , ïîëó÷åííîé ïî ôîðìóëàì (20.1), (20.7).Çàòðàòû íà ðåàëèçàöèþ ýòîé îöåíêè ïðèìåðíî ðàâíû s̃(H) = T (µ) +n(t1 + t2 ), ãäå T (µ) âðåìÿ íà ïðåäâàðèòåëüíîå âû÷èñëåíèå âåëè÷èíûI˜, t1 ñðåäíåå âðåìÿ âû÷èñëåíèÿ âåëè÷èíû LM g(αi ), à t2 ñðåäíåå âðåìÿ äëÿ âû÷èñëåíèÿ âåëè÷èíû g(αi ) (çàòðàòû íà ïðèáàâëåíèå äâîéêè èäåëåíèå íà I˜ â (20.7), íà ñëîæåíèå âåëè÷èí g(αi ), H(αi ) è íà îäíî óìíîæåíèå â (20.1) ñ÷èòàåì ìàëûìè è íå ó÷èòûâàåì).
Ñ÷èòàÿ, ÷òî âåðõíÿÿãðàíèöà èç ñîîòíîøåíèÿ (20.10) âîñïðîèçâîäèò ðåàëüíîå ïîâåäåíèå ïî(H)ãðåøíîñòè δn , ïîëó÷àåì, ÷òî ïðè ôèêñèðîâàííîì δ âåëè÷èíà çàòðàò(H)s̃èìååò âèäB̃ (H) (µ)G2(t1 + t2 )(20.11)s̃(H) = T (µ) +δ2ãäå B̃ (H) (µ) âåëè÷èíà èç (20.10) ïðè óñëîâèè, ÷òî ïîïðàâî÷íûé ìíîæèòåëü âûáèðàåòñÿ ïî ôîðìóëå (20.7). Ïîëó÷åíèå òî÷íûõ àíàëèòè÷åñêèõçàâèñèìîñòåé âåëè÷èí T è B̃ (H) îò µ çàòðóäíåíî (çäåñü ìíîãîå çàâèñèòîò êîíêðåòíîé ðåàëèçàöèè îöåíêè (20.1) íà ÝÂÌ). Ïî àíàëîãèè ñ ñîîòíîøåíèåì (19.11), àíàëèç áàëàíñà (20.11) ïðèâîäèò ê âûâîäó î íàëè÷èèîïòèìàëüíîãî çíà÷åíèÿ µ è îá óâåëè÷åíèè ýòîãî çíà÷åíèÿ ñ óìåíüøåíèåì δ .
Ýòîò âûâîä ïîäòâåðæäåí â òåñòîâûõ ýêñïåðèìåíòàõ [9, 17].Îòìåòèì òàêæå, ÷òî ïðè îòíîñèòåëüíî áîëüøèõ ðàçìåðíîñòÿõ d èçíà÷åíèÿõ ÷èñëà äåëåíèé ïî êàæäîé êîîðäèíàòå µ âîçíèêàþò ïðîáëåìûïî ïðåäâàðèòåëüíîìó âû÷èñëåíèþ âåëè÷èíû I˜ è ïî èñïîëüçîâàíèþ îïåðàòèâíîé ïàìÿòè ÝÂÌ äëÿ ìíîãîêðàòíîãî âû÷èñëåíèÿ çíà÷åíèé ôóíêöèè LM g(x). Òàêèì îáðàçîì, ñ ðîñòîì êðàòíîñòè èíòåãðàëà ýôôåêòèâíîñòü ïðèìåíåíèÿ ìîäèôèêàöèè (20.1) ïàäàåò.(H)(α)Äëÿ îöåíîê ζ̃n è ζ̃n , áåçóñëîâíî, ñïðàâåäëèâû âûâîäû ðàáîòû[27], â êîòîðîé ðàññìîòðåíû ìåòîäû óìåíüøåíèÿ äèñïåðñèè (â òîì ÷èñëå, âçâåøåííàÿ ðàâíîìåðíàÿ âûáîðêà è ìåòîä ñ ïîïðàâî÷íûì ìíîæèòåëåì), ñâÿçàííûå ñ âûáîðîì ôóíêöèè a(x), ¾ñõîäíîé¿ ñ ïîäûíòåãðàëüíîéôóíêöèåé g(x); ýòî îçíà÷àåò ÷òî êîýôôèöèåíò êîððåëÿöèèρ̃ = ρ(g(ξ), a(ξ)) ìåæäó âåëè÷èíàìè g(ξ) è a(ξ) áëèçîê ê åäèíèöå.  [27]ïîëó÷åíû ¾óíèâåðñàëüíûå¿ íèæíèå ãðàíèöû äèñïåðñèé äëÿ ðàçëè÷íûõ84ìîäèôèêàöèé ñòàíäàðòíîãî ìåòîäà Ìîíòå-Êàðëî (1.5) â òåðìèíàõ âåëè÷èíû ρ̃. íàøåì ñëó÷àå a(x) = LM g(x).
Ýòî îçíà÷àåò, ÷òî ìû ðàññìàòðèâàåì áëèçîñòü ôóíêöèé g(x) è a(x) â îáû÷íîì ¾äåòåðìèíèðîâàííîì¿ñìûñëå. Âû÷èñëåíèå ñîîòâåòñòâóþùåé âåëè÷èíû ρ̃ çäåñü ïðåäñòàâëÿåòñîáîé çàäà÷ó, ýêâèâàëåíòíóþ ïî ñëîæíîñòè èñõîäíîé çàäà÷å âû÷èñëåíèÿ èíòåãðàëà (1.4), ÷òî çàòðóäíÿåò ïðÿìîå èñïîëüçîâàíèå ïîëó÷åííûõâ [27] ðåçóëüòàòîâ.21.
Ñëó÷àéíûå êóáàòóðíûå ôîðìóëû21.1. Îñíîâû òåîðèè êóáàòóðíûõ ôîðìóë. Êàê óêàçàíî â ïðåäèñëîâèè, ñòàíäàðòíûé àëãîðèòì ìåòîäà Ìîíòå-Êàðëî (ñì. ñîîòíîøåíèÿ (0.2) è (1.5)) ìîæíî ðàññìàòðèâàòü ñ ïîçèöèé îáùåé òåîðèè êóáàòóðíûõ ôîðìóë [2, 6], â êîòîðîé äëÿ ïðèáëèæåííîãî âû÷èñëåíèÿ èíòåãðàëàZI=q(x)f˜(x) dx, X ⊆ Rd ,(21.1)Xèñïîëüçóåòñÿ âûðàæåíèå âèäàI≈nXCi q(xi ).(21.2)i=1Çäåñü êîýôôèöèåíòû {Ci } íàçûâàþòñÿ âåñàìè, à òî÷êè {xi ∈ X} óçëàìè êóáàòóðíîé ôîðìóëû (21.2). Ôèêñèðîâàííàÿ âåñîâàÿ ôóíêöèÿ f˜(x)èç (21.1) â îáùåìñëó÷àå ïðîèçâîëüíà. Õîðîøî èçó÷åíû ñëó÷àè f˜(x) ≡ 1R˜˜è f (x) ≥ 0, X f (x) dx = 1 (ïðè âûïîëíåíèè ïîñëåäíèõ äâóõ ñîîòíîøåíèé âåñîâóþ ôóíêöèþ ìîæíî òðàêòîâàòü êàê âåðîÿòíîñòíóþ ïëîòíîñòü êàê â ñîîòíîøåíèè (1.4)).Èìååòñÿ áîëüøîå êîëè÷åñòâî ïîäõîäîâ, ñâÿçàííûõ ñ ïîñòðîåíèåì èîïòèìèçàöèåé êóáàòóðíûõ ôîðìóë.
 ÷àñòíîñòè, ïðè ïîñòðîåíèè êóáàòóðíûõ ôîðìóë ÍüþòîíàÊîòåñà [2] ïîäûíòåãðàëüíàÿ ôóíêöèÿ q(x)çàìåíÿåòñÿ íà èíòåðïîëÿöèîííûé ìíîãî÷ëåí. Ïðè ïîñòðîåíèè êóáàòóðíûõ ôîðìóë Ãàóññà òðåáóåòñÿ òàê ïîäîáðàòü âåñà {Ci } è óçëû {xi },÷òîáû ôîðìóëà (21.2) áûëà òî÷íà íà ìíîæåñòâå ìíîãî÷ëåíîâ {Pm (x)}íàèáîëåå âûñîêîé ñòåïåíè m (òî÷íîñòü îçíà÷àåò çäåñü çàìåíó ïðèáëèæåííîãî ðàâåíñòâà (21.2) íà òî÷íîå ïðè q(x) = Pm (x)).  êóáàòóðíûõôîðìóëàõ ×åáûøåâà ôèêñèðóþòñÿ è ïîëàãàþòñÿ ðàâíûìè âåñà {Ci } (êñëîâó, ñòàíäàðòíûé ìåòîä Ìîíòå-Êàðëî àëãîðèòì 1.1 äàåò êóáàòóðíóþ ôîðìóëó (21.2) ÷åáûøåâñêîãî òèïà).
Äëÿ ðÿäà ïîäõîäîâ, íàïðîòèâ,85ôèêñèðóåòñÿ îäèí èëè íåñêîëüêî óçëîâ xi (ôîðìóëû Ëîáàòòî, ôîðìóëû Ìàðêîâà). Ïðè ïîñòðîåíèè ôîðìóë Ýéëåðà è ôîðìóë Ãðåãîðè èñïîëüçóþòñÿ çíà÷åíèÿ ïðîèçâîäíûõ ïîäûíòåãðàëüíîé ôóíêöèè q(x) â óçëàõêóáàòóðíîé ôîðìóëû {xi }. ðàçäåëå 1 áûëî îòìå÷åíî, ÷òî äëÿ ìàëûõ ðàçìåðíîñòåé d çàäà÷âû÷èñëåíèÿ èíòåãðàëà (21.1) è äëÿ ãëàäêèõ ïîäûíòåãðàëüíûõ ôóíêöèéq(x) óæå ïðîñòåéøèå êóáàòóðíûå ôîðìóëû (21.2)Pn èìåþò áîëåå âûñîêóþñêîðîñòü ñõîäèìîñòè ïîãðåøíîñòè δn = |I − i=1 Ci q(xi )| ê íóëþ ïðèn → ∞.Ïðîäåìîíñòðèðóåì ýòî äëÿ ñëó÷àÿ d = 1 (â ýòîì ñëó÷àå ôîðìóëû(21.2) íàçûâàþò êâàäðàòóðíûìè), X = Q1 = [0, 1] è f˜(x) ≡ 1.
Ðàññìîòðèì ïðîñòåéøóþ ôîðìóëó ïðÿìîóãîëüíèêîâZ 1nXi − 1/2(21.3)q(x) dx ≈hq(xi ), h = 1/n, xi =n0i=1(ñì. òàêæå ôîðìóëó (1.7)). Èíòåðåñíî îòìåòèòü, ÷òî ýòà ôîðìóëà ÿâëÿåòñÿ îïòèìàëüíîé è êàê ôîðìóëà ÍüþòîíàÊîòåñà, è êàê ôîðìóëàÃàóññà, è êàê ôîðìóëà ×åáûøåâà.ËÅÌÌÀ 21.1 [2]. Åñëè q(x) ∈ C 2 (L; Q1 ), òî ïîãðåøíîñòü δn êâàäðàòóðíîéôîðìóëû(21.3)îöåíèâàåòñÿñâåðõóâåëè÷èíîéL/(24 n2 ).Íàïîìíèì, ÷òî êëàññ C 2 (L; Q1 ) ÿâëÿåòñÿ ÷àñòíûì ñëó÷àåì ââåäåííîãî â ðàçä. 9 ìíîæåñòâà C r (L; Qd ).
Ýòî îçíà÷àåò, â ÷àñòíîñòè, ÷òî âòîðàÿïðîèçâîäíàÿ ôóíêöèè q(x) êóñî÷íî-íåïðåðûâíà è îãðàíè÷åíà ïî ìîäóëþ êîíñòàíòîé L íà [0, 1].Îäíàêî ñ ðîñòîì ðàçìåðíîñòè d è äëÿ êëàññîâ íåãëàäêèõ ôóíêöèéq(x) ïðåèìóùåñòâî ¾äåòåðìèíèðîâàííûõ¿ êóáàòóðíûõ ôîðìóë (21.2)ïåðåä ñòîõàñòè÷åñêèìè èñ÷åçàåò. Ïîêàæåì ýòî íà ïðèìåðå ôóíêöèé èçC r (L; Qd ). Èìååò ìåñòî ñëåäóþùååËÅÌÌÀ 21.2 [2]. Ïðè óñëîâèè îòäåëåííîñòè âåñîâîé ôóíêöèè îòíóëÿ: f˜(x) ≥ T > 0, ñïðàâåäëèâî ñîîòíîøåíèåinfsupCi ,xi q∈C r (L;Qd )δn ≥ D(r, L; Qd )T n−r , ãäå D(r, L; Qd ) > 0,r = r(1) , . .
. , r(d) , L = L(1) , . . . , L(d) , 1/r = 1/r(1) + . . . + 1/r(d) .Íàïðèìåð, äëÿ q(x) ∈ C (1,...,1) (L, . . . , L; Qd ) âûïîëíåíî δn > Hn−1/dè óæå äëÿ d ≥ 2 ìåòîä Ìîíòå-Êàðëî (àëãîðèòì 1.1) ñðàâíèì ñ ¾äåòåðìèíèðîâàííîé¿ êóáàòóðíîé ôîðìóëîé (21.2).8621.2. Ðàíäîìèçàöèÿ êóáàòóðíûõ ôîðìóë. Ðàññóæäåíèÿ èç ðàçäåëà 17 ïîêàçàëè, ÷òî ðàññìîòðåíèå êóáàòóðíûõ ôîðìóë ñî ñëó÷àéíûìè óçëàìè ïîçâîëÿåò ïîëó÷èòü ïîâûøåííûå ïîðÿäêè t âåðîÿòíîñòíîéïîãðåøíîñòè δn ∼ n−t ïðè n → ∞. Àëãîðèòìû 17.1, 17.2 èç ýòèõ ïîäðàçäåëîâ, êàê è ñàì ñòàíäàðòíûé àëãîðèòì 1.1, ÿâëÿþòñÿ âàðèàíòàìèñëó÷àéíîé êóáàòóðíîé ôîðìóëûI≈NXκi q(ξ i ).(21.4)i=1Çäåñü {κi }, N ñêàëÿðíûå, à {ξ i } âåêòîðíûå ñëó÷àéíûå âåëè÷èíû.
Âàëãîðèòìàõ 1.1, 17.1, 17.2 ñëó÷àéíûìè ÿâëÿþòñÿ óçëû {ξ i }, à êîýôôèöèåíòû {κi } è ÷èñëî ñëàãàåìûõ N äåòåðìèíèðîâàíû. èçâåñòíîé ìåðå ïðîòèâîïîëîæíàÿ ñèòóàöèÿ ïîëó÷àåòñÿ â ñëó÷àå,êîãäà óçëû è êîýôôèöèåíòû äåòåðìèíèðîâàíû è èçâåñòíà èõ çàâèñèìîñòü îò ÷èñëà N , êîòîðîå âûáèðàåòñÿ ñëó÷àéíî ñîãëàñíî ðàñïðåäåëåíèþ π = {p1 , p2 , . . .}; pn = P(N = n). Íàïðèìåð, äëÿ èíòåãðèðîâàíèÿíà îòðåçêå [0, 1] ìîæíî ïîñòðîèòü ïî çàäàííîìó N = n ôîðìóëó ïðÿìîóãîëüíèêîâ (21.3) ñ n óçëàìè, ëèáî áîëåå ñëîæíûå ôîðìóëû òàêîãîòèïà (ôîðìóëû òðàïåöèé, Ñèìïñîíà è ò.ï).
Âûáèðàÿ â ñîîòâåòñòâèè ñçàäàííûì ðàñïðåäåëåíèåì π âûáîðî÷íûå çíà÷åíèÿ n1 , . . . , nM , îöåíèâàåì èíòåãðàë I ñ ïîìîùüþ ñðåäíåãî àðèôìåòè÷åñêîãîI≈nmM1 X 1 X(m)q(xi ).M m=1 nm i=1Ïðèìåðîì îäíîâðåìåííîãî èñïîëüçîâàíèÿ ñëó÷àéíûõ âåñîâ {κi } èñëó÷àéíûõ óçëîâ {ξ i } ìîæåò ñëóæèòü ìåòîäèêà, ïðåäñòàâëåííàÿ äàëååâ ïîäðàçä. 21.3.21.3. Èíòåðïîëÿöèîííûå êóáàòóðíûå ôîðìóëû ñî ñëó÷àéíûìè óçëàìè. Ðàññìîòðèì ãèëüáåðòîâî ïðîñòðàíñòâî L2 (X; f ) èíòå-ãðèðóåìûõ ñ êâàäðàòîìñ âåñîì f (x) ôóíêöèé ñî ñêàëÿðíûì ïðîèçâåRäåíèåì (q1 , q2 ) = X q1 (x)q2 (x)f (x) dx.Èíòåðïîëÿöèîííàÿ êâàäðàòóðíàÿ ôîðìóëà ýòî ïðèáëèæåíèå èíòåãðàëà, ïîëó÷åííîå ïóòåì èíòåãðèðîâàíèÿ êàêîé-ëèáî èíòåðïîëÿöèîííîé ôîðìóëû äëÿ ôóíêöèè q(x).
Ïðèìåðîì òàêèõ ôîðìóë ÿâëÿþòñÿôîðìóëû ÍüþòîíàÊîòåñà, óïîìÿíóòûå â ïîäðàçä. 21.1 (ïðè ïîñòðîåíèè ýòèõ ôîðìóë èñïîëüçóåòñÿ ïîëèíîìèàëüíàÿ èíòåðïîëÿöèÿ ôóíêöèèq(x)).87Ðàññìîòðèì ïîñòðîåíèå èíòåðïîëÿöèîííîé ôîðìóëû ñ ïîìîùüþ ñèñòåìû îðòîíîðìèðîâàííûõ ñ âåñîì f (x) ôóíêöèé ϕ1 (x), . . . , ϕn (x), äëÿêîòîðûõ (ϕi , ϕj ) = δij R. Äëÿ ïðîñòîòû ïîëàãàåì, ÷òî âåñîâàÿ ôóíêöèÿïîëîæèòåëüíà â X è X f (x) dx = 1, òî åñòü, êàê è â ôîðìóëå (1.4),ôóíêöèþ f (x) ìîæíî òðàêòîâàòü êàê âåðîÿòíîñòíóþ ïëîòíîñòü.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
