1626435386-4ea3b7438ebb2e92437735aa9b26c4d2 (844201), страница 9
Текст из файла (страница 9)
Ïðîâåäåííûå íàìè ÷èñëåííûå ýêñïåðèìåíòû ïîêàçàëè, ÷òî íàèáîëåå ýôôåêòèâíîé ôîðìóëîé äëÿ ìîäåëèðîâàíèÿ(n)ñëó÷àéíîé âåëè÷èíû αr ÿâëÿåòñÿQrln i=1 αi(n)αr = Qn+1 ,ln i=1 αiêîòîðàÿ îñíîâàíà íà ïðåäñòàâëåíèè ñëó÷àéíîé âåëè÷èíû, èìåþùåé áåòàðàñïðåäåëåíèå ñ íàòóðàëüíûìè ïàðàìåòðàìè, â âèäå êîìïîçèöèè ñëó41÷àéíûõ âåëè÷èí, èìåþùèõ ãàììà-ðàñïðåäåëåíèå ñ öåëûìè ïàðàìåòðàìè[10].8.3. Àïïðîêñèìàöèîííûå ñâîéñòâà è óñòîé÷èâîñòü ïðèáëèæåíèÿ Áåðíøòåéíà.
Ñïðàâåäëèâî ñëåäóþùåå óòâåðæäåíèå.ËÅÌÌÀ 8.2 [19]. Åñëè g(x) ïðèíàäëåæèò C[0, 1] è óäîâëåòâîðÿåò√óñëîâèþ Ëèïøèöà ñ êîíñòàíòîé L, òî ρC[0,1] (g, LM g) ≤ L/(2 M ).Òàêèì îáðàçîì, ñêîðîñòü ñõîäèìîñòè ïðèáëèæåíèÿ (6.1), (8.1), (8.2)(ñì. òðåáîâàíèå 3 èç ïîäðàçä. 6.7) îòíîñèòåëüíî íåâåëèêà. Íàïðèìåð,äëÿ ðàññìîòðåííîé âûøå â ðàçä. 7 êîíå÷íî-ýëåìåíòíîé àïïðîêñèìàöèèÑòðåíãàÔèêñà ñ îáðàçóþùåé áàçèñ ôóíêöèåé χ(x) = β (1) (x) ñêîðîñòüñõîäèìîñòè èìååò ïîðÿäîê 1/M 2 .Äëÿ àïïðîêñèìàöèè Áåðíøòåéíà âûïîëíåíî óòâåðæäåíèå ëåììû 7.3è ñîîòíîøåíèå (7.7), ò. å.
ýòî ïðèáëèæåíèå îáëàäàåò ¾èäåàëüíûì¿ ñâîéñòâîì óñòîé÷èâîñòè (ñì. òðåáîâàíèå 4 èç ïîäðàçä. 6.7).9. Äâóñòîðîííèé ãåîìåòðè÷åñêèé ìåòîä (äèñêðåòíîñòîõàñòè÷åñêàÿ âåðñèÿ)9.1. Ãåîìåòðè÷åñêèé ìåòîä È.Ì.Ñîáîëÿ. Âåðíåìñÿ ê çàäà÷å âû÷èñëåíèÿ èíòåãðàëà (1.4). Ðàññìîòðèì ñëó÷àé, êîãäà âû÷èñëåíèå çíà÷åíèé ôóíêöèè q(x) â àëãîðèòìå (1.5) ÿâëÿåòñÿ òðóäîåìêèì, ò. å. âåëè÷èíàt èç (1.9) äîñòàòî÷íî âåëèêà. Óêàæåì ïðèåì, ñ ïîìîùüþ êîòîðîãî çà ñ÷åòíåêîòîðîãî ðîñòà äèñïåðñèè Dζ èç (1.9) ìîæíî ñóùåñòâåííî óìåíüøèòüâåëè÷èíó t.
Èäåÿ ýòîãî ïðèåìà îñíîâàíà íà òàê íàçûâàåìîì ãåîìåòðè÷åñêîì ìåòîäå Ìîíòå-Êàðëî, êîòîðûé ñôîðìóëèðîâàí â ìîíîãðàôèè[16] â êà÷åñòâå àëüòåðíàòèâíîãî ê ñòàíäàðòíîìó àëãîðèòìó 1.1 ñëåäóþùèì îáðàçîì.Ïóñòü äëÿ ôóíêöèè q(x) èç (1.5) âûïîëíåíî óñëîâèå 0 ≤ q(x) < C ,ãäå x ∈ X è C = const. Ââåäåì äîïîëíèòåëüíóþ êîîðäèíàòóx(d+1)(1)(d)(d+1)è â (d + 1)-ìåðíîì ïðîñòðàíñòâå x , . .
. , x , xðàññìîòðèì öèëèíäðè÷åñêóþ îáëàñòü G̃ = X × (0, C), à â íåé ñëó÷àéíóþ òî÷êóξ̃ = ξ˜(1) , . . . , ξ˜(d) , ξ˜(d+1) , ðàñïðåäåëåííóþ ñîãëàñíî ïëîòíîñòè f (x).(9.1)f˜ x(1) , . . . , x(d) , x(d+1) = f˜ x, x(d+1) =CÇàìåòèì, ÷òî â ýòîì ñëó÷àå âåêòîð ξ = ξ˜(1) , . . . , ξ˜(d) ðàñïðåäåëåí ñîãëàñíî ïëîòíîñòè f (x) â X , à êîìïîíåíòà ξ˜(d+1) ðàâíîìåðíî ðàñïðåäåëåíà â èíòåðâàëå (0, C).42(d+1) ÀËÃÎÐÈÒÌ 9.1 [16]. 1. Ðåàëèçóåì n çíà÷åíèé ξ̃ j = ξ j , ξ˜j(çäåñü j = 1, . . . , n) (d + 1)-ìåðíîãî ñëó÷àéíîãî âåêòîðà ξ̃.2.
Îáîçíà÷èì ÷åðåç ν êîëè÷åñòâî òî÷åê, îêàçàâøèõñÿ íèæå ïîâåðõíîñòè x(d+1) = q(x), äëÿ êîòîðûõ(d+1)ξ˜j≤ q(ξ j ),(9.2)è ïðèáëèæàåì èíòåãðàë ïî ôîðìóëåI ≈ ζ̃n =Cν.n ìîíîãðàôèè [16] àëãîðèòì 9.1 ñôîðìóëèðîâàí äëÿ d = 2 è ïîêàçàíî, ÷òî Eζ̃n = I . Ýòîò æå ðåçóëüòàò (äëÿ ïðîèçâîëüíîãî d) ëåãêîïîëó÷èòü, åñëè çàìåòèòü, ÷òî àëãîðèòì 9.1 ÿâëÿåòñÿ íà ñàìîì äåëå àëãîðèòìîì 1.1 äëÿ âû÷èñëåíèÿ (d + 1)-êðàòíîãî èíòåãðàëàZI=C χG x, x(d+1) f˜ x, x(d+1) dx dx(d+1)G̃ñ ïëîòíîñòüþ f˜ x, x(d+1) âèäà (9.1).  ïîñëåäíåì ñîîòíîøåíèè G îáîçíà÷àåò îáëàñòüG = x, x(d+1) : x ∈ X, 0 ≤ x(d+1) ≤ q(x) ,à χG x, x(d+1) èíäèêàòîð ìíîæåñòâà G.9.2. Ìîäèôèêàöèÿ ãåîìåòðè÷åñêîãî ìåòîäà.
Àëãîðèòì 9.1 ìîæíî ðàññìàòðèâàòü êàê ÷àñòíûé ñëó÷àé ñëåäóþùåé ÷èñëåííîé ñõåìû.Ïóñòü òðåáóåòñÿ âû÷èñëèòü èíòåãðàë (1.4). Ïðåäïîëîæèì, ÷òî 0 ≤ q(x) ≤qup (x), ãäå x ∈ X .(d+1) ÀËÃÎÐÈÒÌ 9.2. 1. Ðåàëèçóåì n çíà÷åíèé ξ̂ j = ξ j , ξˆj,j = 1, . . . , n, (d + 1)-ìåðíîãî ñëó÷àéíîãî âåêòîðà ξ̂ â îáëàñòèGup = x, x(d+1) : x ∈ X, 0 ≤ x(d+1) ≤ qup (x)ñîãëàñíî ïëîòíîñòè fˆ x, x(d+1) = f (x)/qup (x), ò. å.
âåêòîð ξ ðàçûãðûâàåòñÿ ñîãëàñíî ïëîòíîñòèf (x), à êîìïîíåíòà ξˆ(d+1) ðàâíîìåðíîâ èíòåðâàëå 0, qup (ξ) .2. Ñòðîèì îöåíêó èíòåãðàëà (1.4):nI ≈ ζ̂n =1X(d+1) qup (ξ j )χG ξ j , ξˆj.n j=143(9.3)Äëÿ àëãîðèòìà 9.1 èìååì qup (x) ≡ C . Äëÿ âû÷èñëåíèÿ çíà÷åíèÿ(d+1) χG ξ j , ξˆjèç (9.3) ñëåäóåò ïðîâåðÿòü íåðàâåíñòâî (9.2) äëÿ(d+1)(d+1)˜ˆξj= ξj. Çàìåòèì, ÷òî àëãîðèòì 9.1 ïðåäñòàâëÿåò ñîáîé àíàëîãìåòîäà èñêëþ÷åíèÿ Íåéìàíà (ñ ïîñòîÿííîé ìàæîðàíòîé; ñì., íàïðèìåð,[1]), à àëãîðèòì 9.2 ìåòîäà èñêëþ÷åíèÿ ñ ïðîèçâîëüíîé ìàæîðàíòîé(ñì. àëãîðèòì 5.10). Ïî òîé æå àíàëîãèè ïðè 0 ≤ q(x) ≤ qup,1 (x) ≤(1)qup,2 (x), x ∈ X îöåíêà ζ̂n èç àëãîðèòìà 9.2 ñ ìàæîðèðóþùåé ôóíêöè(2)åé qup (x) = qup,1 (x) èìååò ìåíüøóþ äèñïåðñèþ, ÷åì îöåíêà ζ̂n èç àëãîðèòìà 9.2 ñ ôóíêöèåé qup (x) = qup,2 (x), à ìèíèìóì äèñïåðñèè îöåíêèζ̂n äîñòèãàåòñÿ ïðèqup (x) = q(x).(9.4)(i)Äåéñòâèòåëüíî, Dζ̂n = Dζ̂ (i) /n, i = 1, 2, èDζ̂ (2) = Dqup,2 (ξ)χG ξ, ξˆ(d+1) =Z2qup,2(x)χ2G x, x(d+1) fˆ x, x(d+1) dx dx(d+1) − I 2 ==Gup,2Z=Zq(x)dx(d+1) qup,2 (x)f (x) − I˜2 =dxX0≥ Dζ̂ (1) =Zq(x)qup,2 (x)f (x) dx − I 2 ≥XZq(x)qup,1 (x)f (x) dx − I 2 ≥XZq 2 (x)f (x) dx − I 2 = Dζ,Xãäå ζ îöåíêà, ñîîòâåòñòâóþùàÿ ñëó÷àþ (9.4).
Åñëè çàòðàòû íà âû÷èñëåíèå çíà÷åíèé ôóíêöèé q(x), qup,1 (x) è qup,2 (x) ïðèáëèçèòåëüíî îäèíàêîâû, òî îäèíàêîâû è ñðåäíèå âðåìåíà t (ñì. ñîîòíîøåíèå (1.9)) äëÿ(d+1) ïîäñ÷åòà çíà÷åíèé qup (ξ j )χG ξ j , ξˆjèç (9.4) äëÿ ðàçëè÷íûõ âàðèàíòîâ àëãîðèòìà 9.2 (ò. å. äëÿ qup (x) = qup,1 (x), qup,2 (x), q(x)). Åñëè, êðîìå(d+1) òîãî, ïðè ïîäñ÷åòå χG ξ j , ξˆj(ò. å. ïðè ïðîâåðêå íåðàâåíñòâà (9.2))ïðèõîäèòñÿ íåïîñðåäñòâåííî âû÷èñëÿòü çíà÷åíèå q(ξ j ), òî ïîëó÷àåòñÿ,÷òî òðóäîåìêîñòü (1.9) àëãîðèòìà 9.2 ñ ìàæîðàíòîé (9.4) áóäåò íàèìåíüøåé. Îäíàêî â ýòîì ñëó÷àå àëãîðèòì 9.2 ñîâïàäàåò ñ àëãîðèòìîì 1.1,òîëüêî â àëãîðèòìå 9.2 èìååòñÿ ëèøíåå (è â ýòîì ñëó÷àå ñîâåðøåííîáåñïîëåçíîå) äåéñòâèå ðîçûãðûø âåëè÷èíû ξˆ(d+1) .Òàêèì îáðàçîì, ãåîìåòðè÷åñêèé ìåòîä èç ìîíîãðàôèè [16] (àëãîðèòì 9.1) è åãî ìîäèôèêàöèÿ (àëãîðèòì 9.2), ñ îäíîé ñòîðîíû, ìîãóòáûòü ïðåäñòàâëåíû êàê ñòàíäàðòíûé àëãîðèòì (1.5) ñ q̃(x, x(d+1) ) =44qup (x) χG (x, x(d+1) ), fˆ(x, x(d+1) ) = f (x)/qup (x), à ñ äðóãîé ñòîðîíû, âñëó÷àå íåîáõîäèìîñòè âû÷èñëåíèÿ çíà÷åíèé q(ξ j ) ïðè ïðîâåðêå íåðàâåíñòâà (9.2) îíè ÿâëÿþòñÿ íåýôôåêòèâíûìè ìîäèôèêàöèÿìè ñòàíäàðòíîãî àëãîðèòìà 1.1.
Êàê îòìå÷åíî â [16], ïðèìåíåíèå ãåîìåòðè÷åñêîãîìåòîäà ìîæåò îêàçàòüñÿ ïîëåçíûì â ñëåäóþùåé (äîñòàòî÷íî ¾ýêçîòè÷åñêîé¿) ñèòóàöèè: âû÷èñëåíèå çíà÷åíèé q(ξ j ) ÿâëÿåòñÿ òðóäîåìêèì, àñîîòíîøåíèå (9.2) óäàåòñÿ çàìåíèòü íà ðàâíîñèëüíîå íåðàâåíñòâî, ïðèïðîâåðêå êîòîðîãî íå òðåáóåòñÿ âû÷èñëÿòü q(ξ j ).9.3. Äâóñòîðîííèé ãåîìåòðè÷åñêèé ìåòîä.
Ãîðàçäî áîëåå øèðîêîå ïðèìåíåíèå ìîæåò íàéòè ñëåäóþùàÿ ìîäèôèêàöèÿ àëãîðèòìà 9.2èç ðàáîòû [24], èäåÿ êîòîðîé âî ìíîãîì àíàëîãè÷íà èäåå ïîñòðîåíèÿäâóñòîðîííåãî ìåòîäà èñêëþ÷åíèÿ (ñì. àëãîðèòì 5.11).Ïðåäïîëîæèì, ÷òî ñóùåñòâóþò ëåãêî âû÷èñëèìûå íåîòðèöàòåëüíûåôóíêöèè qlow (x) è qup (x) òàêèå, ÷òîqlow (x) ≤ q(x) ≤ qup (x), x ∈ X.(9.5)(d+1) ÀËÃÎÐÈÒÌ 9.3 [24].
1. Ðåàëèçóåì n çíà÷åíèé ξ̂ j = ξ j , ξˆj,j = 1, . . . , n, (d + 1)-ìåðíîãî ñëó÷àéíîãî âåêòîðà ξ̂ â îáëàñòè Gup ñîãëàñíî ïëîòíîñòè fˆ x, x(d+1) = f (x)/qup (x).(d+1)2. Åñëè ξˆj< qlow (ξ j ), òî ïîëàãàåì θj = 1, èíà÷å ïðîâåðÿåì íåðà(d+1)(d+1)âåíñòâî íåðàâåíñòâî (9.2) äëÿ ξ˜j= ξˆj. Åñëè îíî âûïîëíåíî, òîïîëàãàåì θj = 1, èíà÷å θj = 0.3.
Ñòðîèì îöåíêó èíòåãðàëà:n1Xqup (ξ j ) × θj .I ≈ ζ̆n =n j=1(9.6)Äèñïåðñèÿ Dζ̆ îöåíêè (9.6) èç àëãîðèòìà 9.3 ñîâïàäàåò ñ äèñïåðñèåéDζ̂ àëãîðèòìà 9.2, à çíà÷èò, îíà áîëüøå äèñïåðñèè Dζ ñòàíäàðòíîãîàëãîðèòìà (1.5). Îäíàêî, åñëè ôóíêöèè qlow (x), q(x) è qup (x) áëèçêè,òî ðàçíèöà (Dζ̆−Dζ) íåâåëèêà è, êðîìå òîãî, ïðîâåðêà íåðàâåíñòâà (9.2)(à çíà÷èò, è òðóäîåìêèé ïîäñ÷åò çíà÷åíèé q(ξ j )) ïðîèñõîäèò äîñòàòî÷íîðåäêî.  ýòîì ñëó÷àå ìîæíî äîñòè÷ü óìåíüøåíèÿ îáùåé òðóäîåìêîñòèS èç (1.9).459.4. Äèñêðåòíî-ñòîõàñòè÷åñêàÿ âåðñèÿ äâóñòîðîííåãî ãåîìåòðè÷åñêîãî ìåòîäà.
 ñâÿçè ñ òåì, ÷òî êðàòíîñòü d èíòåãðàëà I , êàêïðàâèëî, äîñòàòî÷íî âåëèêà, â êà÷åñòâå ìàæîðàíòû qup (x) è ìèíîðàíòû qlow (x) ôóíêöèè q(x) (ñì. ñîîòíîøåíèå (9.5)) öåëåñîîáðàçíî âûáèðàòü êóñî÷íî-ïîñòîÿííûå ïðèáëèæåíèÿ ñâåðõó è ñíèçó ôóíêöèè q(x). äàëüíåéøåì äëÿ ïðîñòîòû áóäåì ðàññìàòðèâàòü â êà÷åñòâå îáëàñòèèíòåãðèðîâàíèÿ åäèíè÷íûé êóá X = Qd = [0, 1]d . Ðàçîáüåì îáëàñòü èíòåãðèðîâàíèÿ íà ÿ÷åéêè(i)(i)Xm = x = x(1) , . . .
, x(d) : (jm− 1)/µ ≤ x(i) ≤ jm/µ ;(9.7)(i)çäåñü i = 1, . . . , d, jm = 1, . . . , µ.  êà÷åñòâå ïðèáëèæåííûõ çíà÷åíèéìàæîðàíòû (ìèíîðàíòû) â êàæäîé ÿ÷åéêå ìîæíî âçÿòü ìàêñèìàëüíûå(ìèíèìàëüíûå) èç çíà÷åíèé ïîäûíòåãðàëüíîé ôóíêöèè q(x) â óçëàõ ñåòêè, îïðåäåëÿþùèõ äàííóþ ÿ÷åéêó (ýòîò ñïîñîá áóäåò ñ÷èòàòüñÿ â äàëüíåéøèõ ðàññóæäåíèÿõ îñíîâíûì). Äëÿ áîëüøåé òî÷íîñòè íàõîæäåíèÿìàæîðàíòû è ìèíîðàíòû ìîæíî òàêæå èñïîëüçîâàòü çíà÷åíèÿ ôóíêöèèq(x) â äîïîëíèòåëüíûõ òî÷êàõ, â ÷àñòíîñòè, çíà÷åíèÿ â öåíòðå ÿ÷åéêèè/èëè â ñðåäíèõ òî÷êàõ êàæäîãî ðåáðà ÿ÷åéêè.
Îäíàêî, è â ýòîì ñëó÷àå íåò ãàðàíòèè òîãî, ÷òî íàéäåííûå ìàæîðàíòà (ìèíîðàíòà) áóäóòäåéñòâèòåëüíî îãðàíè÷èâàòü ôóíêöèþ q(x), èç-çà ýòîãî âîçíèêàåò äèñêðåòíàÿ îøèáêà ìåòîäà. ñëó÷àå, êîãäà íàõîæäåíèå òî÷íûõ ìèíèìóìîâ è ìàêñèìóìîâ âÿ÷åéêàõ çàòðóäíåíî, ìîæíî èñïîëüçîâàòü ïðèáëèæåííûå ìàæîðàíòû èìèíîðàíòû (ïðè ýòîì íåñêîëüêî âîçðàñòàåò òðóäîåìêîñòü ìåòîäà). Íàïðèìåð, åñëè ïîäûíòåãðàëüíàÿ ôóíêöèÿ q(x) Ëèïøåöåâà ñ êîíñòàíòîéL, òî â êà÷åñòâå ìàæîðàíò è ìèíîðàíò â ÿ÷åéêàõ ìîæíî âçÿòüh(1)(d)qup (x) ≡ qup,m = max q((jm− 1)h, . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
