1626435387-cbed9341b165fae9f16c4a05686b9115 (Войтишек - Основы метода Монте-Карло)
Описание файла
PDF-файл из архива "Войтишек - Основы метода Монте-Карло", который расположен в категории "". Всё это находится в предмете "методы монте-карло" из 7 семестр, которые можно найти в файловом архиве НГУ. Не смотря на прямую связь этого архива с НГУ, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст из PDF
ÔÅÄÅÐÀËÜÍÎÅ ÀÃÅÍÒÑÒÂÎ ÏÎ ÎÁÐÀÇÎÂÀÍÈÞÍÎÂÎÑÈÁÈÐÑÊÈÉ ÃÎÑÓÄÀÐÑÒÂÅÍÍÛÉ ÓÍÈÂÅÐÑÈÒÅÒÌåõàíèêî-ìàòåìàòè÷åñêèé ôàêóëüòåòÀ. Â. ÂîéòèøåêÎÑÍÎÂÛ ÌÅÒÎÄÀ ÌÎÍÒÅ-ÊÀÐËÎÓ÷åáíîå ïîñîáèåÍîâîñèáèðñê2010ÁÁÊ Â193.3ÿ 731ÓÄÊ 519.676 654Âîéòèøåê À. Â. Îñíîâû ìåòîäà Ìîíòå-Êàðëî: Ó÷åá. ïîñîáèå /Íîâîñèá. ãîñ. óí-ò. Íîâîñèáèðñê, 2010. 108 c.ISBNÄàííîå ó÷åáíîå ïîñîáèå ïóáëèêóåòñÿ â ðàìêàõ ¾Ïðîãðàììû ðàçâèòèÿ ÍÈÓ-ÍÃÓ¿ (íàïðàâëåíèå ¾Ìàòåìàòèêà, ôóíäàìåíòàëüíûå îñíîâûèíôîðìàòèêè è èíôîðìàöèîííûå òåõíîëîãèè¿). Ïðè ýòîì àâòîð èñïîëüçîâàë ìíîãîëåòíèé îïûò ïðåïîäàâàíèÿ îñíîâ òåîðèè ÷èñëåííîãîñòàòèñòè÷åñêîãî ìîäåëèðîâàíèÿ íà ìåõàíèêî-ìàòåìàòè÷åñêîì è ôèçè÷åñêîì ôàêóëüòåòàõ ÍÃÓ.
Èçäàíèå ïðåäíàçíà÷åíî äëÿ êðàòêîãî êóðñà (ñåìü ëåêöèé è ñåìü ñåìèíàðñêèõ çàíÿòèé) äëÿ ìàãèñòðàíòîâ âóçîâ ôèçèêî-ìàòåìàòè÷åñêîãî ïðîôèëÿ. Ïîìèìî êîíñïåêòèâíîãî èçëîæåíèÿ ëåêöèé ïîñîáèå ñîäåðæèò ìíîãî÷èñëåííûå ïðèìåðû ðåøåíèÿ çàäà÷, à òàêæå ìåòîäè÷åñêèå óêàçàíèÿ ïî îðãàíèçàöèè çàíÿòèé. Êðîìåòîãî, ñôîðìóëèðîâàíî òâîð÷åñêîå äîìàøíåå çàäàíèå è ïîäðîáíî ðàçîáðàíû âîçìîæíûå òåõíîëîãèè åãî âûïîëíåíèÿ. Ðàáîòà íàä ïîñîáèåìâûïîëíåíà ïðè ôèíàíñîâîé ïîääåðæêå ÐÔÔÈ (ãðàíòû 100100040à,090100035à) è Ïðåçèäåíòñêîé ïðîãðàììû ¾Âåäóùèå íàó÷íûå øêîëû¿.Ðåöåíçåíòêàíä. ôèç.ìàò. íàóê È. À. ØàëèìîâàISBNc Íîâîñèáèðñêèé ãîñóäàðñòâåííûéóíèâåðñèòåò, 2010ÏðåäèñëîâèåÑ ðàçâèòèåì âû÷èñëèòåëüíîé òåõíèêè âîçðàñòàåò èíòåðåñ ê ÷èñëåííûì ìåòîäàì ðåøåíèÿ ïðèêëàäíûõ çàäà÷, â ÷àñòíîñòè ê ñòàòèñòè÷åñêîìó ìîäåëèðîâàíèþ (èëè ìåòîäó Ìîíòå-Êàðëî) (ñì., íàïðèìåð, [1],à òàêæå ñïèñîê ëèòåðàòóðû â ýòîì ó÷åáíèêå).
Èñòîðè÷åñêè èíòåíñèâíîå ðàçâèòèå òåîðèè è ïðèëîæåíèé ìåòîäà Ìîíòå-Êàðëî áûëî ñâÿçàíîñ ðåøåíèåì àêòóàëüíûõ çàäà÷ òåîðèè ïåðåíîñà èçëó÷åíèÿ â 50-õ ãã. XXñòîëåòèÿ. Çà ïîñëåäíèå ïîëâåêà ñôåðà ïðèìåíèìîñòè ìåòîäîâ ÷èñëåííîãî ñòàòèñòè÷åñêîãî ìîäåëèðîâàíèÿ çíà÷èòåëüíî ðàñøèðèëàñü. Ðàçðàáîòàíà òåîðèÿ âåðîÿòíîñòíûõ ïðåäñòàâëåíèé ðåøåíèé çàäà÷ ìàòåìàòè÷åñêîé ôèçèêè, íà îñíîâå êîòîðîé ïîñòðîåíû ñîîòâåòñòâóþùèå ÷èñëåííûåñòîõàñòè÷åñêèå îöåíêè.
Ýôôåêòèâíûå àëãîðèòìû ðàçðàáîòàíû òàêæå âñòàòèñòè÷åñêîé ôèçèêå (ìåòîä Ìåòðîïîëèñà, ñõåìà Èçèíãà), â ôèçè÷åñêîé è õèìè÷åñêîé êèíåòèêå (ìíîãî÷àñòè÷íûå çàäà÷è, ðåøåíèå óðàâíåíèé Áîëüöìàíà è Ñìîëóõîâñêîãî, ìîäåëèðîâàíèå ðåàêöèé è ôàçîâûõïåðåõîäîâ), â òåîðèè ìàññîâîãî îáñëóæèâàíèÿ, â ôèíàíñîâîé ìàòåìàòèêå, â òåîðèè òóðáóëåíòíîñòè, â ìàòåìàòè÷åñêîé áèîëîãèè è äð.Ïðè ðàçðàáîòêå äàííîãî ïîñîáèÿ, ðåàëèçîâàííîé â ðàìêàõ ¾Ïðîãðàììû ðàçâèòèÿ ÍÈÓ-ÍÃÓ¿ (íàïðàâëåíèå ¾Ìàòåìàòèêà, ôóíäàìåíòàëüíûå îñíîâû èíôîðìàòèêè è èíôîðìàöèîííûå òåõíîëîãèè¿), àâòîðèñïîëüçîâàë ìíîãîëåòíèé îïûò ïðåïîäàâàíèÿ îñíîâ òåîðèè ÷èñëåííîãî ñòàòèñòè÷åñêîãî ìîäåëèðîâàíèÿ íà ìåõàíèêî-ìàòåìàòè÷åñêîì è ôèçè÷åñêîì ôàêóëüòåòàõ Íîâîñèáèðñêîãî ãîñóäàðñòâåííîãî óíèâåðñèòåòà.Äëÿ îñâîåíèÿ êóðñà òðåáóþòñÿ ýëåìåíòàðíûå çíàíèÿ èç êóðñîâ òåîðèèâåðîÿòíîñòåé è ìàòåìàòè÷åñêîé ñòàòèñòèêè (ñì., íàïðèìåð, [2, 3]).Äàííîå èçäàíèå ïðåäñòàâëÿåò ñîáîé äîðàáîòàííóþ âåðñèþ ïîñîáèÿ[4].
Ñëåäóåò îñîáî ïîä÷åðêíóòü, ÷òî äëÿ áîëåå ãëóáîêîãî èçó÷åíèÿ òåîðèè ÷èñëåííîãî ñòàòèñòè÷åñêîãî ìîäåëèðîâàíèÿ öåëåñîîáðàçíî èñïîëüçîâàòü ó÷åáíèê [1] è ñîïóòñòâóþùèå ìîíîãðàôèè (ïðåäñòàâëåííûå âñïèñêå ëèòåðàòóðû â [1]). Îñîáåííîñòüþ äàííîãî ïîñîáèÿ ÿâëÿåòñÿ òî,÷òî ïîìèìî êîíñïåêòèâíîãî èçëîæåíèÿ ëåêöèé îíî ñîäåðæèò ìíîãî÷èñëåííûå ïðèìåðû ðåøåíèÿ çàäà÷, à òàêæå ìåòîäè÷åñêèå óêàçàíèÿ ïî îðãàíèçàöèè çàíÿòèé (ñì.
ïðèë. 4) è èòîãîâîãî ýêçàìåíà (ñì. ïðèë. 2).Êðîìå òîãî, ñôîðìóëèðîâàíî òâîð÷åñêîå äîìàøíåå çàäàíèå è ïîäðîáíîðàçîáðàíû âîçìîæíûå òåõíîëîãèè åãî âûïîëíåíèÿ (ñì. ïðèë. 3).31. Âû÷èñëåíèå ìàòåìàòè÷åñêîãî îæèäàíèÿ èäèñïåðñèè ìåòîäîì Ìîíòå-Êàðëî1.1. Îáùàÿ ñõåìà ìåòîäà Ìîíòå-Êàðëî. Ïîä ÷èñëåííûì ñòàòèñòè÷åñêèì ìîäåëèðîâàíèåì îáû÷íî ïîíèìàþò ðåàëèçàöèþ ñ ïîìîùüþêîìïüþòåðà âåðîÿòíîñòíîé ìîäåëè íåêîòîðîãî îáúåêòà ñ öåëüþ îöåíèâàíèÿ ñðåäíèõ õàðàêòåðèñòèê ìîäåëè íà îñíîâå çàêîíà áîëüøèõ ÷èñåë. ñàìîì îáùåì âèäå ñõåìà ìåòîäà Ìîíòå-Êàðëî âûãëÿäèò ñëåäóþùèì îáðàçîì (ñì., íàïðèìåð, [1]).
Ïóñòü íàì òðåáóåòñÿ âû÷èñëèòü íåêîòîðóþ âåëè÷èíó I . Ïðåäïîëàãàåòñÿ, ÷òî ìîæíî ïîñòðîèòü ñëó÷àéíóþâåëè÷èíó ζ ñ ìàòåìàòè÷åñêèì îæèäàíèåì Eζ , ðàâíûì I , è ñ êîíå÷íîéäèñïåðñèåé Dζ , ïðè÷åì âûáîðî÷íûå çíà÷åíèÿ ζj ñëó÷àéíîé âåëè÷èíû ζäîñòàòî÷íî ïðîñòî ðåàëèçóþòñÿ íà êîìïüþòåðå (çäåñü è äàëåå îáîçíà÷åíèå âûáîðî÷íûõ çíà÷åíèé ñëó÷àéíîé âåëè÷èíû ïðåäñòàâëÿåò ñîáîéãðå÷åñêóþ áóêâó ñ íèæíèì èíäåêñîì, à îáîçíà÷åíèå ñîîòâåòñòâóþùåéñëó÷àéíîé âåëè÷èíû íèæíåãî èíäåêñà íå èìååò). Ïîñòðîèâ äîñòàòî÷íîáîëüøîå êîëè÷åñòâî n âûáîðî÷íûõ çíà÷åíèé ζ1 , . .
. , ζn , íà îñíîâå çàêîíàáîëüøèõ ÷èñåë (ñì., íàïðèìåð, [2, 3]) ïîëó÷àåì ïðèáëèæåíèå èñêîìîéâåëè÷èíû:ζ1 + . . . + ζn.(1.1)I = Eζ ≈ Zn =nÁàçîâàÿ ñëó÷àéíàÿ âåëè÷èíà ζ íàçûâàåòñÿ îöåíêîé âåëè÷èíû I . Òàêèì îáðàçîì, ïîíÿòèå îöåíêè â òåîðèè ìåòîäîâ Ìîíòå-Êàðëî íåñêîëüêî îòëè÷àåòñÿ îò àíàëîãè÷íîãî òåðìèíà â ìàòåìàòè÷åñêîé ñòàòèñòèêå(ñì., íàïðèìåð, [3]), â êîòîðîé îöåíêîé âåëè÷èíû I íàçûâàåòñÿ ñðåäíåå àðèôìåòè÷åñêîå Zn . Âûáîð îöåíêè ζ , êàê ïðàâèëî, íåîäíîçíà÷åí.Ïîýòîìó ãëàâíûìè ïðîáëåìàìè ïðè èñïîëüçîâàíèè ìåòîäîâ ÷èñëåííîãîñòàòèñòè÷åñêîãî ìîäåëèðîâàíèÿ ÿâëÿåòñÿ âûáîð îïòèìàëüíîé îöåíêè ζèñêîìîé âåëè÷èíû I è ðàçðàáîòêà àëãîðèòìîâ, ïîçâîëÿþùèõ ïîëó÷àòüâûáîðî÷íûå çíà÷åíèÿ {ζi } íà ÝÂÌ.×àùå âñåãî îöåíêà ζ èç ñîîòíîøåíèÿ (1.1) èìååò âèäζ = q(ξ),(1.2)ãäå ξ = ξ (1) , .
. . , ξ (d) ñëó÷àéíûé âåêòîð èëè ñëó÷àéíàÿ ïîñëåäîâàòåëüíîñòü (íàïðèìåð, îáðûâàþùàÿñÿ ñ âåðîÿòíîñòüþ åäèíèöà öåïüÌàðêîâà, äëÿ êîòîðîé, âîîáùå ãîâîðÿ, d → ∞) ñ çàäàííûì àáñîëþòíîíåïðåðûâíûì ðàñïðåäåëåíèåì, à q(x) ôóíêöèÿ (íåñëó÷àéíàÿ) d ïåðå-4ìåííûõ. Ïðè ýòîì ñîîòíîøåíèå (1.1) ïðèîáðåòàåò âèänI≈1Xq(ξ i ),n i=1(1.3)ãäå ξ 1 , . . . , ξ n âûáîðî÷íûå çíà÷åíèÿ ñëó÷àéíîãî âåêòîðà ξ .1.2. Ïðèáëèæåííîå âû÷èñëåíèå äèñïåðñèè áàçîâîé ñëó÷àéíîé âåëè÷èíû. Ïðè èññëåäîâàíèè ïîãðåøíîñòè è òðóäîåìêîñòè ìåòîäà(1.1) òðåáóåòñÿ ïðèáëèæåííî âû÷èñëÿòü íåèçâåñòíóþ âåëè÷èíó äèñïåðñèè Dζ ñëó÷àéíîé âåëè÷èíû ζ (ñì. ðàçä.
3).Âåëè÷èíà Dζ äîïóñêàåò ýôôåêòèâíîå îöåíèâàíèå ñ ïîìîùüþ ðåàëèçóåìûõ âûáîðî÷íûõ çíà÷åíèé ζ1 , . . . , ζn̂ (ïðè ýòîì ÷èñëî âûáîðî÷íûõ çíà÷åíèé n̂, êàê ïðàâèëî, çíà÷èòåëüíî ìåíüøå âåëè÷èíû n èç ïðèáëèæåííîãî ðàâåíñòâà (1.1) ñì. ïîäðàçä. 3.4). Ïðîñòåéøåå ïðèáëèæåíèå íåñëîæíî ïîëó÷èòü èç ñîîòíîøåíèé (1.2), (1.3) äëÿ u = u ∈ R èq(u) = u2 :n̂Dζ = Eζ 2 − (Eζ)2 ≈(1)Dn̂1X 2ζ −=n̂ i=1 in̂1Xζin̂ i=1!2.(1.4)Åñëè â ðàâåíñòâå (1.4) òðàêòîâàòü ζ1 , . . . , ζn̂ êàê íåçàâèñèìûå è îäèíàêîâî ðàñïðåäåëåííûå (òàê æå, êàê ñëó÷àéíàÿ âåëè÷èíà ζ ) ñëó÷àéíûåâåëè÷èíû, òî íåñëîæíî ïîêàçàòü, ÷òî1(1)EDn̂ = 1 −Dζ.(1.5)n̂(1)Äåéñòâèòåëüíî, EDn̂ = Eζ 2 − EZn̂2 = Dζ − DZn̂ , òàê êàê EZn̂ = Eζ .(1)Ó÷èòûâàÿ, ÷òî DZn̂ = Dζ/n̂, ïîëó÷àåì ðàâåíñòâî (1.5).
Ðàçäåëèâ Dn̂íà (1 − 1/n̂)n̂(2)Dn̂11 X 2ζi −=n̂ − 1 i=1n̂(n̂ − 1)ïîëó÷àåì íåñìåùåííóþ îöåíêó äèñïåðñèè.5n̂Xi=1!2ζi,(1.6)2. Âû÷èñëåíèå èíòåãðàëà ìåòîäîì Ìîíòå-Êàðëî2.1. Îñíîâíûå ïðîáëåìû òåîðèè ÷èñëåííîãî ñòàòèñòè÷åñêîãî ìîäåëèðîâàíèÿ.  ñâÿçè ñ çàäà÷åé (1.1) âîçíèêàåò ðÿä âîïðîñîâ.1. Êàêèå âåëè÷èíû I äîïóñêàþò ïðåäñòàâëåíèå (1.1)?2. Åäèíñòâåíåí ëè âûáîð ñëó÷àéíîé âåëè÷èíû ζ , è åñëè íååäèíñòâåíåí, òî êàê îïòèìèçèðîâàòü ýòîò âûáîð?3. Ñêîëüêî âûáîðî÷íûõ çíà÷åíèé ζ1 , .
. . , ζn òðåáóåòñÿ äëÿ äîñòèæåíèÿ çàäàííîãî óðîâíÿ ïîãðåøíîñòè?4. Êàê ïîñòðîèòü ýôôåêòèâíûå àëãîðèòìû ðåàëèçàöèè âûáîðî÷íûõ çíà÷åíèé ζ1 , . . . , ζn íà ÝÂÌ?Çàáåãàÿ âïåðåä, îòìåòèì, ÷òî âîïðîñ 4 áóäåò èññëåäîâàòüñÿ â ðàçä.1017; âîïðîñû 2 è 3 îáñóæäàþòñÿ â ðàçä. 3.2.2. Èñïîëüçîâàíèå îáîáùåííîé ôîðìóëû ìàòåìàòè÷åñêîãî îæèäàíèÿ íåïðåðûâíîé ñëó÷àéíîé âåëè÷èíû. Èññëåäóåì âîï-ðîñ 1. Îòìåòèì ïðåæäå âñåãî, ÷òî åñëè îöåíêà ζ èìååò âèä (1.2), òîZ(2.1)I = Eζ = q(x)f (x) dx,ãäå f (x) = f x(1) , .
. . , x(d) ïëîòíîñòü ðàñïðåäåëåíèÿ ñëó÷àéíîãî âåêòîðà ξ .  ñâÿçè ñ ýòèì ìîæíî îáúÿâèòü, ÷òî ñ ìàòåìàòè÷åñêîé òî÷êèçðåíèÿ òåîðèÿ ìåòîäîâ Ìîíòå-Êàðëî ÿâëÿåòñÿ ñïåöèàëüíûì ðàçäåëîì÷èñëåííîãî èíòåãðèðîâàíèÿ (ñì., íàïðèìåð, [5]). Îòìåòèì, ÷òî ýòîò ðàçäåë âêëþ÷àåò (åñëè èìåòü â âèäó èìåííî ìåòîäû Ìîíòå-Êàðëî) è òàêóþâàæíóþ òåìó, êàê ðåøåíèå èíòåãðàëüíûõ óðàâíåíèé âòîðîãî ðîäà (ñì.,íàïðèìåð, [1], à òàêæå ðàçä. 79). Ýòè óðàâíåíèÿ, â ñâîþ î÷åðåäü, ìîãóòîïèñûâàòü ìíîãèå ôèçè÷åñêèå ïðîöåññû, ñâÿçàííûå ñ ïåðåíîñîì èçëó÷åíèÿ è ÷àñòèö (ñì. ðàçä. 6). Âî ìíîãèõ çàäà÷àõ ìàòåìàòè÷åñêîé ôèçèêè èìåþòñÿ âîçìîæíîñòè ïîñòðîåíèÿ èíòåãðàëüíîãî è âåðîÿòíîñòíîãîïðåäñòàâëåíèé ðåøåíèÿ è êîíñòðóèðîâàíèÿ ñîîòâåòñòâóþùåãî ÷èñëåííîãî àëãîðèòìà ìåòîäà Ìîíòå-Êàðëî (ñì., íàïðèìåð, [1]).2.3. Ïðèáëèæåííîå âû÷èñëåíèå èíòåãðàëà.
Ïðåäïîëîæèì, ÷òîðåøåíèåI íåêîòîðîé çàäà÷è äîïóñêàåò èíòåãðàëüíîå ïðåäñòàâëåíèåRI = g(x) dx. Âûáåðåì ïëîòíîñòü f (x) òàêóþ, ÷òî f (x) 6= 0 ïðè g(x) 6= 0.Òîãäà íà îñíîâå ñîîòíîøåíèé (1.2), (1.3) è (2.1) èìååì!ZZ1 g(ξ 1 )g(ξ n )g(x)f (x) dx = Eζ ≈+...+, (2.2)I = g(x) dx =f (x)n f (ξ 1 )f (ξ n )6ïðè ýòîì ζ = q(ξ) = g(ξ)/f (ξ). Ðàâåíñòâî (2.2) îòðàæàåò ïðèíöèï ïîñòðîåíèÿ âåñîâîé îöåíêè ìåòîäà Ìîíòå-Êàðëî äëÿ èíòåãðàëà I .3.
Ïîãðåøíîñòü è òðóäîåìêîñòü ìåòîäà Ìîíòå-Êàðëî3.1. Ïîñòðîåíèå äîâåðèòåëüíîãî èíòåðâàëà ñ èñïîëüçîâàíèåì öåíòðàëüíîé ïðåäåëüíîé òåîðåìû. Ïîãðåøíîñòü δn = |Zn − I|ìåòîäà (1.1) ïðåäñòàâèìà â âèäå S − nI √Dζ S − nEζ n nδn = = √ √ √ ,nnDζ n ãäå Sn = ζ1 +. . .+ζn . Èç öåíòðàëüíîé ïðåäåëüíîé òåîðåìû äëÿ îäèíàêîâî ðàñïðåäåëåííûé ñëó÷àéíûõ âåëè÷èí (ñì., íàïðèìåð, [2]) ñëåäóåò,÷òî√ √ïðè äîñòàòî÷íî áîëüøîì n ñëó÷àéíàÿ âåëè÷èíà (Sn − nEζ)/( Dζ n)áëèçêà ïî ðàñïðåäåëåíèþ ê ñòàíäàðòíîé íîðìàëüíîé ñëó÷àéíîé âåëè÷èíå γ ∈ N (0, 1). Ñëåäîâàòåëüíî, äëÿ ìàëîãî ε > 0 íàéäåòñÿ êîíñòàíòàHε , äëÿ êîòîðîé ïðè n 1 âûïîëíåíî ñîîòíîøåíèå!√Dζ≈ P(|γ| < Hε ) ≥ 1 − ε.(3.1)P δ n ≤ Hε √nÍàïðèìåð, äëÿ ε = 0.003 èìååì Hε ≈ 3.