1626435386-4ea3b7438ebb2e92437735aa9b26c4d2 (844201)
Текст из файла
ÔÅÄÅÐÀËÜÍÎÅ ÀÃÅÍÒÑÒÂÎ ÏÎ ÎÁÐÀÇÎÂÀÍÈÞÍÎÂÎÑÈÁÈÐÑÊÈÉ ÃÎÑÓÄÀÐÑÒÂÅÍÍÛÉ ÓÍÈÂÅÐÑÈÒÅÒÊàôåäðà âû÷èñëèòåëüíîé ìàòåìàòèêèÀ. Â. ÂîéòèøåêÄÈÑÊÐÅÒÍÎ-ÑÒÎÕÀÑÒÈ×ÅÑÊÈÅÌÎÄÈÔÈÊÀÖÈÈ ÑÒÀÍÄÀÐÒÍÎÃÎÌÅÒÎÄÀ ÌÎÍÒÅ-ÊÀÐËÎÓ÷åáíîå ïîñîáèåÍîâîñèáèðñê2009ÁÁÊ 22.19ÓÄÊ 519.676ÂÂîéòèøåê À. Â. Äèñêðåòíî-ñòîõàñòè÷åñêèå ìîäèôèêàöèè ñòàíäàðòíîãî ìåòîäà Ìîíòå-Êàðëî: Ó÷åá. ïîñîáèå / Íîâîñèá. ãîñ. óí-ò. Íîâîñèáèðñê, 2009.
104 c.ISBNÄàííîå ïîñîáèå ñîäåðæèò êîíñïåêòèâíîå èçëîæåíèå ëåêöèé ñïåöèàëüíîãî êóðñà ¾Äèñêðåòíî-ñòîõàñòè÷åñêèå ìåòîäû ÷èñëåííîãî èíòåãðèðîâàíèÿ¿, êîòîðûé ðàçðàáîòàí àâòîðîì äëÿ ñòóäåíòîâ ñòàðøèõ êóðñîâìåõàíèêî-ìàòåìàòè÷åñêîãî ôàêóëüòåòà ÍÃÓ. Èçäàíèå ïîäãîòîâëåíî âðàìêàõ âûïîëíåíèÿ ïðîãðàììû ¾Èííîâàöèîííûå îáðàçîâàòåëüíûå ïðîãðàììû è òåõíîëîãèè, ðåàëèçóåìûå íà ïðèíöèïàõ ïàðòíåðñòâà êëàññè÷åñêîãî óíèâåðñèòåòà, íàóêè, áèçíåñà è ãîñóäàðñòâà¿ íàöèîíàëüíîãîïðîåêòà ¾Îáðàçîâàíèå¿.
Ðàáîòà íàä ïîñîáèåì âûïîëíåíà ïðè ôèíàíñîâîé ïîääåðæêå Ðîññèéñêîãî ôîíäà ôóíäàìåíòàëüíûõ èññëåäîâàíèé(ïðîåêòû 070100024, 090100035, 090112116).Âñå çàìå÷àíèÿ è ïðåäëîæåíèÿ ÷èòàòåëåé ïî ñîäåðæàíèþ äàííîé ðàáîòû áóäóò ïðèíÿòû àâòîðîì ñ áëàãîäàðíîñòüþ (êîíòàêòíûé òåëåôîí(8383)3300728; email: vav@osmf.sscc.ru).Ðåöåíçåíòê.ô.-ì.í. È.
À. Øàëèìîâàc Íîâîñèáèðñêèé ãîñóäàðñòâåííûéóíèâåðñèòåò, 2009c Âîéòèøåê À. Â., 2009ISBNÏÐÅÄÈÑËÎÂÈÅÑ ðàçâèòèåì âû÷èñëèòåëüíîé òåõíèêè âîçðàñòàåò èíòåðåñ ê ÷èñëåííûì ìåòîäàì ðåøåíèÿ ïðèêëàäíûõ çàäà÷, â ÷àñòíîñòè, ê ñòàòèñòè÷åñêîìó ìîäåëèðîâàíèþ (èëè ìåòîäó Ìîíòå-Êàðëî) (ñì., íàïðèìåð, [1],à òàêæå ñïèñîê ëèòåðàòóðû â ýòîì ó÷åáíèêå). Òðàäèöèîííî ìåòîäûÌîíòå-Êàðëî ðàññìàòðèâàþòñÿ â êà÷åñòâå àëüòåðíàòèâíûõ ¾äåòåðìèíèðîâàííûì¿ ÷èñëåííûì ìåòîäàì (â ÷àñòíîñòè, êîíå÷íî-ðàçíîñòíûì èêîíå÷íî-ýëåìåíòíûì ñõåìàì) [2]. Îäíàêî âî ìíîãèõ ñëó÷àÿõ ýôôåêòèâíûìè îêàçûâàþòñÿ ñìåøàííûå àëãîðèòìû, ñîäåðæàùèå â ñåáå ýëåìåíòûäåòåðìèíèðîâàííûõ è ñòîõàñòè÷åñêèõ ÷èñëåííûõ ñõåì. Òàêèå êîìáèíèðîâàííûå àëãîðèòìû ìîæíî íàçâàòü äèñêðåòíî-ñòîõàñòè÷åñêèìè ÷èñëåííûìè ìåòîäàìè [3].Ñëåäóåò ñðàçó îòìåòèòü, ÷òî ñïåêòð äèñêðåòíî-ñòîõàñòè÷åñêèõ ÷èñëåííûõ ìåòîäîâ äîñòàòî÷íî øèðîê. Êîìáèíèðîâàííûå àëãîðèòìû âîçíèêàþò âî âñåõ îñíîâíûõ ðàçäåëàõ òåîðèè ìåòîäîâ Ìîíòå-Êàðëî, ê êîòîðûì ñëåäóåò îòíåñòè: ÷èñëåííîå ìîäåëèðîâàíèå ñëó÷àéíûõ âåëè÷èí,âåêòîðîâ è ôóíêöèé [35]; âû÷èñëåíèå ìíîãîêðàòíûõ èíòåãðàëîâ; ïðèáëèæåíèå èíòåãðàëîâ, çàâèñÿùèõ îò ïàðàìåòðà [3, 5]; ðåøåíèå èíòåãðàëüíûõ óðàâíåíèé âòîðîãî ðîäà [3, 5]; ïðèëîæåíèÿ ìåòîäîâ ÌîíòåÊàðëî, ñâÿçàííûå ñ ðåøåíèåì çàäà÷ âû÷èñëèòåëüíîé ìàòåìàòèêè è ìàòåìàòè÷åñêîé ôèçèêè [3].
 äàííîì ïîñîáèè îïèñàíû âîçìîæíîñòè ïðèìåíåíèÿ äèñêðåòíî-ñòîõàñòè÷åñêèõ òåõíîëîãèé â àëãîðèòìàõ ÷èñëåííîãî èíòåãðèðîâàíèÿ.Äëÿ ïðèáëèæåííîãî âû÷èñëåíèÿ èíòåãðàëîâ I ìàëûõ ðàçìåðíîñòåéñ ãëàäêèìè (â îáû÷íîì èëè îáîáùåííîì ñìûñëàõ) ïîäûíòåãðàëüíûìèôóíêöèÿìè è îòíîñèòåëüíî ïðîñòûìè îáëàñòÿìè èíòåãðèðîâàíèÿ ðàçâèòà òåîðèÿ êóáàòóðíûõ ôîðìóë [2, 6].
Êóáàòóðíàÿ ôîðìóëà â îáùåìñëó÷àå èìååò âèäZg(x) dx ≈ Sn =I=XnXcj g(xj ),(0.1)j=1ãäå {x1 , . . . , xn } çàäàííûå äåòåðìèíèðîâàííûå (è, êàê ïðàâèëî, ðåãóëÿðíûå) óçëû ñåòêè â Rd , à {c1 , . . . , cn } âåñà. Îïòèìàëüíûé âûáîðóçëîâ è âåñîâ â (0.1) ñâÿçàí ñ ìèíèìèçàöèåé ïîãðåøíîñòè δn = |I −Sn | èîñíîâàí (ÿâíî èëè íåÿâíî) íà èñïîëüçîâàíèè àïïðîêñèìàöèé ïîäûíòåãðàëüíîé ôóíêöèè g(x).
Ãëàâíûì äîñòîèíñòâîì êóáàòóðíûõ ôîðìóë ÿâëÿåòñÿ âîçìîæíîñòü ïîëó÷åíèÿ ãàðàíòèðîâàííîé è ñðàâíèòåëüíî áûñò3ðîé ñõîäèìîñòè δn ê íóëþ ïðè n → ∞ äëÿ êëàññîâ ãëàäêèõ ïîäûíòåãðàëüíûõ ôóíêöèé g(x).Ê íåäîñòàòêàì ¾êëàññè÷åñêèõ¿ (äåòåðìèíèðîâàííûõ) êóáàòóðíûõôîðìóë íà êëàññàõ ïîäûíòåãðàëüíûõ ôóíêöèé ñëåäóåò îòíåñòè: ñëàáûé ó÷åò ñïåöèôèêè òîé èëè èíîé ïîäûíòåãðàëüíîé ôóíêöèè, íåîáõîäèìîñòü ðàçðàáîòêè ñïåöèàëüíûõ ÷èñëåííûõ àëãîðèòìîâ ïîèñêà îïòèìàëüíûõ âåñîâ è (èëè) óçëîâ, ÷óâñòâèòåëüíîñòü ê ðîñòó ðàçìåðíîñòèd è ê ãëàäêîñòè íà÷àëüíûõ äàííûõ (ïîäûíòåãðàëüíîé ôóíêöèè g(x)è îáëàñòè èíòåãðèðîâàíèÿ X ), òðóäíîñòè â ïîñòðîåíèè ïîêàçàòåëüíûõòåñòîâûõ ÷èñëåííûõ ïðèìåðîâ è êîíòðîëÿ òî÷íîñòè è çàòðàò ïðè ïðàêòè÷åñêèõ âû÷èñëåíèÿõ.Äëÿ ñóùåñòâåííî ìíîãîìåðíûõ çàäà÷ (ò.
å. äëÿ ñëó÷àÿ d 1 è äàæåd → ∞) äîñòàòî÷íî ýôôåêòèâíûì îêàçûâàåòñÿ ñòàíäàðòíûé ìåòîäÌîíòå-Êàðëî (ñì. äàëåå ðàçä. 1, 3). Ýòîò àëãîðèòì îñíîâàí íà ïðåäñòàâëåíèèZng(ξ)1Xζj , ζ = q(ξ) =;(0.2)I = q(x)f (x) dx = Eζ ≈n j=1f (ξ)çäåñü d-ìåðíûé ñëó÷àéíûé âåêòîð ξ ðàñïðåäåëåí ñîãëàñíî ïëîòíîñòèf (x). Ýòîò àëãîðèòì èìååò ñëåäóþùèå ïîëîæèòåëüíûå ñâîéñòâà. Èìååòñÿ âîçìîæíîñòü óìåíüøåíèÿ òðóäîåìêîñòè àëãîðèòìà çà ñ÷åò óäà÷íîãî (ñîãëàñîâàííîãî ñ âèäîì ïîäûíòåãðàëüíîé ôóíêöèè g(x)) âûáîðàâåñîâîé ôóíêöèè f (x) (àëãîðèòì âûáîðêè ïî âàæíîñòè) èëè ïðåîáðàçîâàíèÿ èñõîäíîãî èíòåãðàëà (âûäåëåíèå ãëàâíîé ÷àñòè) è âåñîâîé ôóíêöèè (ìåòîäû ìàòåìàòè÷åñêîãî îæèäàíèÿ è ðàñùåïëåíèÿ, âûáîðêà ïîãðóïïàì è ò. ï.).
Âåñà èìåþò ïðîñòîé âèä cj = 1/n, à óçëû ðåàëèçóþòñÿ ñîãëàñíî âûáèðàåìîìó âåðîÿòíîñòíîìó ðàñïðåäåëåíèþ ñ ïëîòíîñòüþ f (x). Ýôôåêòèâíîñòü àëãîðèòìà (0.2) îòíîñèòåëüíî ñëàáî çàâèñèòîò ðîñòà ðàçìåðíîñòè d è îò îòñóòñòâèÿ ãëàäêîñòè íà÷àëüíûõ äàííûõ(ïîäûíòåãðàëüíîé ôóíêöèè g(x) è îáëàñòè èíòåãðèðîâàíèÿ X ). Èìååòñÿ âîçìîæíîñòü êîíòðîëÿ çàòðàò è òî÷íîñòè âû÷èñëåíèé.Ãëàâíûì íåäîñòàòêîììåòîäà Ìîíòå-Êàðëî ÿâëÿåòñÿ îòíîñèòåëüíî√íèçêàÿ (ïîðÿäêà 1/ n) ñêîðîñòü ñõîäèìîñòè ïîãðåøíîñòè ê íóëþ ïðèâîçðàñòàíèè ÷èñëà ñëó÷àéíûõ óçëîâ n (ñì.
ðàçä. 1).Ýôôåêòèâíûìè ìîãóò îêàçàòüñÿ è ñìåøàííûå, êîìáèíèðîâàííûåïðîöåäóðû ÷èñëåííîãî èíòåãðèðîâàíèÿ, ñî÷åòàþùèå â ñåáå ýëåìåíòûêóáàòóðíûõ ôîðìóë è ìåòîäà Ìîíòå-Êàðëî. Ïî-âèäèìîìó, îäíà èç ïåðâûõ ÷èñëåííûõ ñõåì ïîäîáíîãî ðîäà áûëà ïðåäñòàâëåíà Í. Ñ. Áàõâàëî4âûì â íà÷àëå øåñòèäåñÿòûõ ãîäîâ ïðîøëîãî âåêà [7]. Èñõîäíîé îáëàñòüþ X ÿâëÿëñÿ d-ìåðíûé åäèíè÷íûé êóá Qd , êîòîðûé ðàçáèâàëñÿ íàn ðàâíûõ êóáîâ ñ âåðøèíàìè â òî÷êàõ ðàâíîìåðíîé ñåòêè.  êàæäîìj -îì ýëåìåíòàðíîì êóáå âûáèðàëñÿ óçåë xj êóáàòóðíîé ôîðìóëû ñëó÷àéíûì îáðàçîì (ñîãëàñíî ðàâíîìåðíîìó ðàñïðåäåëåíèþ).
Ýòîò àëãîðèòì ìîæíî ñ÷èòàòü êàê êóáàòóðíîé ôîðìóëîé ñî ñëó÷àéíûìè óçëàìè, òàê è ïðåäåëüíûì ñëó÷àåì âûáîðêè ïî ãðóïïàì â ìåòîäå ÌîíòåÊàðëî. Í. Ñ. Áàõâàëîâ ïîêàçàë, ÷òî åãî àëãîðèòì ÿâëÿåòñÿ îïòèìàëüíûì (ïî ñêîðîñòè ñõîäèìîñòè ê íóëþ ïîãðåøíîñòè δn ïðè n → ∞) âïðîñòðàíñòâå íåïðåðûâíî äèôôåðåíöèðóåìûõ ïîäûíòåãðàëüíûõ ôóíêöèé C 1 (Qd ). Äëÿ ýòîãî åìó ïîòðåáîâàëîñü ïîëó÷àòü îöåíêè ñâåðõó èñíèçó äëÿ δn . Ìåòîäîëîãèÿ ðàáîò Í. Ñ.
Áàõâàëîâà ÿâèëàñü îñíîâîé äëÿèíòåíñèâíîãî ðàçâèòèÿ (â îñíîâíîì íà Çàïàäå) òàê íàçûâàåìîé òåîðèè ñëîæíîñòè [8].  íåé èçó÷àåòñÿ âîïðîñ î òîì, êàêîâ ìàêñèìàëüíûéïîðÿäîê ñòðåìëåíèÿ ê íóëþ ïîãðåøíîñòè δ̃ñ äëÿ äàííîãî êëàññà âû÷èñëèòåëüíûõ àëãîðèòìîâ ñ êîëè÷åñòâîì îïåðàöèé ñ.Óïîìÿíóòûé ïðèìåð ïîäòâåðæäàåò öåëåñîîáðàçíîñòü ðàçðàáîòêèêîìáèíèðîâàííûõ àëãîðèòìîâ ÷èñëåííîãî èíòåãðèðîâàíèÿ. Òàêèå ÷èñëåííûå ñõåìû ìîãóò óìåíüøèòü òðóäîåìêîñòü ñòàíäàðòíîãî ìåòîäà Ìîíòå-Êàðëî.
 ðÿäå ñëó÷àåâ óäàåòñÿ ïîëó÷èòü ýôôåêòèâíûå äèñêðåòíîñòîõàñòè÷åñêèå ìîäèôèêàöèè ìåòîäà Ìîíòå-Êàðëî, ïðèâîäÿùèå ê ñîñòîÿòåëüíûì (âîîáùå ãîâîðÿ, ñìåùåííûì) îöåíêàì.Ïðè ðàçðàáîòêå äèñêðåòíî-ñòîõàñòè÷åñêèõ ÷èñëåííûõ ìåòîäîâ âîçíèêàþò ïðîáëåìû âûáîðà ïîäõîäÿùèõ àïïðîêñèìàöèîííûõ áàçèñîâ èòåñòîâûõ ôóíêöèé, ïîäòâåðæäàþùèõ ýôôåêòèâíîñòü èññëåäóåìûõ êîìáèíèðîâàííûõ àëãîðèòìîâ.Ïðåäñòàâëÿåìûé â ïîñîáèè ó÷åáíûé êóðñ ñëåäóåò ðàññìàòðèâàòü êàêäîïîëíèòåëüíûé ê êóðñó ¾Ìåòîäû Ìîíòå-Êàðëî¿, êîòîðûé ìíîãèå ãîäû ÷èòàåòñÿ äëÿ ñòóäåíòîâ ÷åòâåðòîãî êóðñà ìåõàíèêî-ìàòåìàòè÷åñêîãîôàêóëüòåòà ÍÃÓ. Ïîýòîìó îñíîâíûå ¾êëàññè÷åñêèå¿ ðåçóëüòàòû, êàñàþùèåñÿ ÷èñëåííîãî ñòîõàñòè÷åñêîãî èíòåãðèðîâàíèÿ (ñì., íàïðèìåð,ãëàâó 3 èç ó÷åáíèêà [1]), èçëîæåíû â ýòîì ïîñîáèè êîíñïåêòèâíî, áåçïîäðîáíûõ îáîñíîâàíèé è äîêàçàòåëüñòâ.
Íåîáõîäèìî òàêæå îòìåòèòü,÷òî ðÿä ðåçóëüòàòîâ, ïðåäñòàâëåííûõ â äàííîé êíèãå, ïîëó÷åí àâòîðîìñîâìåñòíî ñ Å. Ã. Êàáëóêîâîé (ýòè ðåçóëüòàòû âîøëè â äèññåðòàöèþ [9],âûïîëíåííóþ ïîä íàó÷íûì ðóêîâîäñòâîì àâòîðà ïîñîáèÿ).51. Âû÷èñëåíèå èíòåãðàëà ìåòîäîì Ìîíòå-Êàðëî.Ïîãðåøíîñòü è òðóäîåìêîñòü ìåòîäà Ìîíòå-Êàðëî1.1. Îáùàÿ ñõåìà ìåòîäà Ìîíòå-Êàðëî. Ïîä ÷èñëåííûì ñòàòèñòè÷åñêèì ìîäåëèðîâàíèåì îáû÷íî ïîíèìàþò ðåàëèçàöèþ ñ ïîìîùüþêîìïüþòåðà âåðîÿòíîñòíîé ìîäåëè íåêîòîðîãî îáúåêòà ñ öåëüþ îöåíèâàíèÿ ñðåäíèõ õàðàêòåðèñòèê ìîäåëè íà îñíîâå çàêîíà áîëüøèõ ÷èñåë. ñàìîì îáùåì âèäå ñõåìà ìåòîäà Ìîíòå-Êàðëî âûãëÿäèò ñëåäóþùèì îáðàçîì (ñì., íàïðèìåð, [1]).
Ïóñòü íàì òðåáóåòñÿ âû÷èñëèòü íåêîòîðóþ âåëè÷èíó I . Ïðåäïîëàãàåòñÿ, ÷òî ìîæíî ïîñòðîèòü ñëó÷àéíóþâåëè÷èíó ζ ñ ìàòåìàòè÷åñêèì îæèäàíèåì Eζ , ðàâíûì I , è ñ êîíå÷íîéäèñïåðñèåé Dζ , ïðè÷åì âûáîðî÷íûå çíà÷åíèÿ ζj ñëó÷àéíîé âåëè÷èíû ζäîñòàòî÷íî ïðîñòî ðåàëèçóþòñÿ íà êîìïüþòåðå. Ïîñòðîèâ áîëüøîå êîëè÷åñòâî n âûáîðî÷íûõ çíà÷åíèé ζ1 , . . . , ζn , íà îñíîâå çàêîíà áîëüøèõ÷èñåë ïîëó÷àåì ïðèáëèæåíèå èñêîìîé âåëè÷èíû:I = Eζ ≈ ζ̄n =ζ1 + . . . + ζn.n(1.1)Áàçîâàÿ ñëó÷àéíàÿ âåëè÷èíà ζ íàçûâàåòñÿ îöåíêîé âåëè÷èíû I . Òàêèì îáðàçîì, ïîíÿòèå îöåíêè â òåîðèè ìåòîäîâ Ìîíòå-Êàðëî íåñêîëüêîîòëè÷àåòñÿ îò àíàëîãè÷íîãî òåðìèíà â ìàòåìàòè÷åñêîé ñòàòèñòèêå, âêîòîðîé îöåíêîé âåëè÷èíû I íàçûâàåòñÿ ñðåäíåå àðèôìåòè÷åñêîå ζ̄n .Âûáîð îöåíêè ζ , êàê ïðàâèëî, íåîäíîçíà÷åí.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
