Метод Монте Карло(методи на Монте Карло, MMC) е общото наименование на група числени методи, базирани на получаване на голям брой реализации на стохастичен (случаен) процес, който се формира по такъв начин, че неговите вероятностни характеристики съвпадат с подобни стойности на проблема, който се решава. Използва се за решаване на задачи в различни области на физиката, химията, математиката, икономиката, оптимизацията, теорията на управлението и др.

История

Алгоритъмът на Буфон за определяне на Пи

Случайните променливи се използват за решаване на различни приложни проблеми от доста дълго време. Пример за това е методът за определяне на числото Пи, предложен от Буфон през 1777 г. Същността на метода беше да се хвърли дължина на иглата Лвърху равнина, начертана от успоредни прави, разположени на разстояние rедна от друга (виж фиг. 1).

Снимка 1.Методът на Буфон

Вероятност (както може да се види от по-нататъшния контекст, ние не говорим за вероятност, а за математическото очакване на броя на пресичанията в един експеримент; това става вероятност само ако r>Л), че отсечката пресича правата, е свързано с числото Pi:

, Където

А- разстоянието от началото на иглата до най-близката права линия;

θ е ъгълът на иглата спрямо прави линии.

Лесно е да вземете този интеграл: (при условие, че r>Л), следователно, като преброим дела на сегментите, пресичащи прави, можем приблизително да определим това число. С увеличаването на броя на опитите точността на получения резултат ще се увеличи.

През 1864 г. капитан Фокс, докато се възстановява от нараняване, за да се заеме по някакъв начин, провежда експеримент за хвърляне на игла. Резултатите са представени в следната таблица:

	Брой хвърляния	Брой кръстовища	Дължина на иглата	Разстояние между линиите	Завъртане	Стойност Pi
Първи опит					отсъстващ
Втори опит					настояще
Трети опит					настояще

коментари:

Използвано е въртене на равнината (и, както показват резултатите, успешно), за да се намали систематичната грешка.

При третия опит дължината на иглата беше по-голяма от разстоянието между линиите, което направи възможно, без да се увеличава броят на хвърлянията, ефективно да се увеличи броят на събитията и да се подобри точността.

Връзка между стохастични процеси и диференциални уравнения

Създаването на математическия апарат на стохастичните методи започва в края на 19 век. През 1899 г. лорд Рейли показа, че едномерно произволно ходене по безкрайна решетка може да даде приблизително решение на параболично диференциално уравнение. Андрей Колмогоров през 1931 г. даде голям тласък на развитието на стохастични подходи за решаване на различни математически проблеми, тъй като успя да докаже, че веригите на Марков са свързани с определени интегро-диференциални уравнения. През 1933 г. Иван Петровски показа, че случайното блуждаене, образуващо верига на Марков, е асимптотично свързано с решението на елиптично частично диференциално уравнение. След тези открития стана ясно, че стохастичните процеси могат да бъдат описани с диференциални уравнения и съответно да бъдат изследвани с помощта на добре развитите математически методи за решаване на тези уравнения по това време.

Раждането на метода Монте Карло в Лос Аламос

Първо, Енрико Ферми през 1930 г. в Италия, а след това Джон фон Нойман Станислав Улам през 1940 г. в Лос Аламос, предполагат, че е възможно да се използва връзката между стохастичните процеси и диференциалните уравнения „в обратната посока“. Те предложиха да се използва стохастичен подход за приближаване на многомерни интеграли в транспортните уравнения, възникнали във връзка с проблема за движението на неутрони във визотропна среда.

Идеята е разработена от Улам, който по ирония на съдбата, подобно на Фокс, се бореше с принудително безделие, докато се възстановяваше от болест и докато играеше пасианс, се чудеше каква е вероятността пасиансът да „се получи“. Той излезе с идеята, че вместо да използва обичайните съображения на комбинаториката за такива проблеми, той може просто да извърши „експеримента“ голям брой пъти и по този начин, преброявайки броя на успешните резултати, да оцени тяхната вероятност. Той също така предложи използването на компютри за изчисления на Монте Карло.

Появата на първите електронни компютри, които можеха да генерират псевдослучайни числа с висока скорост, драматично разшири кръга от проблеми, за които стохастичният подход се оказа по-ефективен от другите математически методи. След това настъпи голям пробив и методът Монте Карло беше използван в много задачи, но използването му не винаги беше оправдано поради големия брой изчисления, необходими за получаване на отговор с дадена точност.

За рождена година на метода Монте Карло се счита 1949 г., когато е публикувана статията на Метрополис и Улам „Методът Монте Карло”. Името на метода идва от името на града в Княжество Монако, широко известен с многобройните си казина, тъй като рулетката е един от най-известните генератори на случайни числа. Станислав Улам пише в автобиографията си „Приключенията на един математик“, че името е предложено от Николас Метрополис в чест на неговия чичо, който е бил комарджия.

Тази публикация ще ви помогне да излезете от доста трудна ситуация. Да приемем, че сте заключени в стая, имате чиле конец и игла и упорито ви се иска да изчислите приблизителната стойност на число Пи, използвайки само тези обекти, добре, всичко може да се случи, нали знаете. И така, днес, докато слушах курс по матан в Университета на Пенсилвания, внезапно научих как да правя това. Това, което дори не можех да си представя, беше това число Писе крие и тук. Оказа се, че корените на този въпрос се връщат към 18 век, когато Жорж-Луи Льоклер дьо Бюфон си поставя следната задача: „да предположим, че подът е направен от дървени ленти в два цвята, те се редуват; Каква е вероятността една хвърлена игла да падне по такъв начин, че да пресече линията, където двете ленти се съединяват?“ Симулация на този процес и отговорът на въпроса можете да намерите под разреза.

Симулация

За да не разваляме интригата, нека започнем с един експеримент. И така, имаме много игли с дължина Ли чиле зелен конец. Нека приложим определен брой успоредни сегменти с еднаква дължина върху повърхността на разстояние Ледин от друг.

Нека хвърлим 100 игли на това поле.

Може би не достатъчно. Нека добавим още 900 и маркираме тези игли, които пресичат нишките в червено.

Да предположим, че хвърлихме не всички игли наведнъж, а една по една и на всяка стъпка записахме съотношението на броя на иглите, които се приземиха върху конците, към общия брой хвърлени игли, като по този начин получихме все по-голямо приближение на вероятността иглата, падайки, да пресече конеца.

Ако хвърлите 10 000 игли, картината ще бъде по-точна.

Сега нека направим следната трансформация: разделете две на всяко число в получената серия.

За 10 000 игли вече е по-точно.

Ако намерим средната стойност на последните пет хиляди термина от поредицата, получаваме 3.141685 , докато pi е равно на 3.141593 .

Като цяло вече не е тайна за никого, че последната серия се сближава с броя Пи. Но как може да се случи това? Научих за това, когато бях на 28 години от горния курс. Нека се потопим в матан.

Теория

Ще разгледаме иглата и най-близката до нея линия вдясно. Нека обозначим разстоянието от левия край на иглата ч, ъгъл на отклонение от линията - а.

Очевидно дължината на противоположния крак от ъгъла Аще бъде равен на синуса на ъгъла, умножен по дължината на хипотенузата. Тогава можем да заявим, че ако чпо-малък или равен на катета срещу ъгъла А, след това иглата пресича конеца. Нека начертаем графика:

Ако броим за всяка хвърлена игла чИ аи маркирайте тези точки на предишната графика, картината ще бъде както следва:

По този начин вероятността иглата да пресече конеца ще бъде равна на съотношението на площта на фигурата под графиката към площта на правоъгълника, т.е. Пи, умножено по дължината на иглата.

От тук получаваме желаното приближение на числото Пи, както показа опитът в първата част.

Равнината е начертана с успоредни прави. Разстоянието между всеки две съседни прави линии е равно на 1. Игла с фиксирана дължина пада върху равнина л (л ≤ 1).

намирамвероятността, с която иглата пресича поне една от линиите (тоест има общи точки с поне една от линиите).
Приемаме, че иглата няма дебелина (тя е просто сегмент) и че пада и лежи плоско върху равнината, а не се забива в нея.

Подсказка 1

Какво се има предвид под вероятност за събитие?

1. Първо, нека се съгласим какво имаме предвид под събитие. Нека проведем серия от еднакви експерименти - тестове, във всеки от които се използват едни и същи начални условия и резултатът от следващия тест не зависи по никакъв начин от резултатите от предишните. Примери от учебника: хвърляне на „перфектна“ монета, хвърляне на „перфектен“ зар. Или, както в нашия проблем, хвърляне на игла върху облицована равнина.

Всеки тест има различни елементарни резултати. Например хвърляне на число от 1 до 6 в примера със зара. Събитиесе нарича някакво подмножество от набора от елементарни резултати. Например „ролка 2“. Или „хвърляне на нечетно число“ (т.е. хвърляне на 1, 3 или 5). Можете да обмислите по-сложни тестове, като например хвърляне на пет монети. Тук елементарните резултати ще бъдат: „паднаха пет глави“, „паднаха четири глави и една опашка“ и т.н. Като събитие можем да приемем например следното: „поне три глави паднаха“.

В нашата задача тестът е едно хвърляне на игла, а събитието, от което се нуждаем, е пресичането на поне една права.

2. Под вероятност за събитиеможете да разберете съотношението на броя на изходите, благоприятни за това събитие, към броя на всички възможни изходи (следователно се оказва, че вероятността винаги е число от 0 до 1). Например, вероятността от събитието „хвърляне на нечетно число“ при хвърляне на един зар е 1/2, защото точно половината от всички възможни резултати съвпадат. Вероятността за събитието „поне три глави“ при хвърляне на 5 монети също е 1/2.

Това определение на вероятността работи добре, когато наборът от възможни резултати е краен. Но в нашия проблем има безкрайно много резултати - позициите на падналата игла. Освен това има безкрайно много подходящи резултати. Как да бъдем? Нека коригираме малко нашата „дефиниция“: вероятност за събитие- това е делът, който „заемат” благоприятните изходи в съвкупността от всички изходи. С тази „дефиниция“ вече е възможно да се изчисли вероятността, изисквана в проблема.

Честно казано, всичко казано по-горе е „практическо“ обяснение и не може да се разглежда с цялата математическа строгост. Но за нашите цели този подход е напълно достатъчен.

3. Само още един пример за яснота. Нека разгледаме квадрат и свържем средните точки на две съседни страни с сегмент, като по този начин отрежем ъгъл. След това произволно ще забием иглата в квадрата. С каква вероятност ще влезем в ъгъла? Тук резултатът от всеки тест е мястото, където се приземява краят на иглата, тоест една точка вътре в квадрата. Ясно е, че има безкрайно много изходи и също така има безкрайно много изходи, подходящи за нашето събитие – влизането в ъгъла. Следователно вече е безсмислено да се говори за броя на резултатите, за да се изчисли вероятността. Но фракцията може да се изчисли - тя е просто съотношението на площите на ъгъла и квадрата. То е равно на 1/8. Имайте предвид, че границите на фигурите имат нулева площ, така че не е нужно да мислите за тях. По-специално, иглата ще удари сегмента, който отрязва ъгъла с вероятност 0.

Подсказка 2

Последният пример от първата подсказка може да подскаже възможен начин за решаване на проблема. Необходимо е да се въведат параметри, които да определят позицията на иглата и да ни позволят да опишем всички случаи, когато тя пресича линиите. Два параметъра са напълно достатъчни тук. След това трябва да разберем какви стойности могат да приемат тези параметри и какви стойности описват нашето събитие. Ако изберете добре параметрите, тогава тези условия ще бъдат доста прости и можете дори да ги „изобразите“: вземете координатна равнина, чиито оси съответстват на параметрите, и начертайте област, чиито точки отговарят на получените условия. След това остава само да се изчисли площта на целия регион и площта на тази част от него, която съответства на пресечната точка на иглата и линиите. И след това намерете отношението на тези площи.

Решение

Нека се съгласим, че правите от условието вървят хоризонтално. Така че хвърлихме иглата в самолета. Как да опишем местоположението му, така че да е удобно да се вземе предвид пресичането с прави линии? Нека отбележим една особена симетрия: за нас не е толкова важно върху коя ивица (или кои, ако има две) между правите линии ще попадне иглата - всички ивици са еднакви. Също така е ясно, че хоризонталните смени също нямат ефект. Но това, което наистина е важно, е колко „далеч“ е иглата от правите линии и под какъв ъгъл е наклонена спрямо тях. Следователно като параметри от втората подсказка можете да вземете ъгъла на наклон α на иглата спрямо правите линии и разстоянието дот средата на иглата до най-близоправ (фиг. 1). Така използваме друга „симетрия“, възникнала в проблема.

Какви стойности могат да приемат тези параметри? Радианната мярка на ъгъл α варира от 0 до π и дприема стойности от 0 (ако средата на иглата е на права линия) до 1/2 (средата на иглата не може да бъде по-далеч от правата линия). На равнината с координати (α, д) тези ограничения определят правоъгълник (фиг. 2).

От фигура 3 е ясно при какви условия върху α и диглата пресича поне една права линия: проекцията на половината игла в посока, перпендикулярна на правите линии, трябва да бъде по-голяма д. Тоест неравенството трябва да е изпълнено.

Така че имаме описание на всички случаи, когато иглата пресича поне една права (ще има пресичане с две прави само ако са изпълнени равенствата α = π/2 и д= 1/2, което може да даде само една точка в нашия правоъгълник - безкраен набор от всички възможни стойности на двойка параметри). Остава да се изчисли площта под синусоидалната графика и да се раздели на площта на целия правоъгълник, която е равна на π/2 (фиг. 4).

Както е известно, площта под графиката на функцията е равна на определен интеграл на тази функция върху необходимия интервал: .

В резултат откриваме, че желаната вероятност е равна на .

Послеслов

Смята се, че този проблем за първи път е поставен и изследван доста задълбочено от френския учен от 18 век граф дьо Бюфон - доста необикновен човек с много широк спектър от интереси, който е направил много полезни неща в различни области на знанието. Поради това често се нарича проблем с иглата на Бюфон. Очевидно това беше първият проблем за така наречената геометрична вероятност. Както видяхме, същността на този подход е да представи набора от елементарни резултати от някакъв тест под формата на геометрична фигура и да намали въпроса за намиране на вероятността за конкретно събитие до изчисляване на съотношението на площите на подходящи фигури . По този начин можете да разрешите още няколко доста добре познати проблеми - може би ще се запознаете с някои от тях по-късно тук на „Елементи“. Затова ще представим само още една проста задача като упражнение:

С каква вероятност кръгла монета с диаметър d, хвърлена върху карирана равнина (разделена на единични квадратчета), не покрива никоя от линиите на решетката, тоест завършва изцяло вътре в един от квадратите?

Обърнете внимание, че когато решавате проблема на Буфон, можете да разсъждавате малко по-различно. Ходът на такова решение е описан подробно (макар и на английски).

Сега малко за смисъла на отговора, който получихме. При л = 1 отговорът е приблизително 0,6366197... Какво точно представлява това число? Както обикновено, в теорията на вероятностите това трябва да се разбира по следния начин. Да кажем, че направихме много дълга поредица от тестове. Да кажем, че сме имали търпението да хвърлим игла милион пъти във всеки тест и да си спомним колко пъти е пресичала прави линии в равнина. И също така проведохме милион такива тестове. Оказва се, че в повечето от тях (най-вероятно преобладаващия брой) броят на пресичанията е близо 636 619. И колкото повече такива тестове провеждаме, толкова по-близък ще бъде делът на успешните резултати (когато иглата пресече чертата) да се. И всъщност, разбира се, няма никакво значение как разделяте тестовете на серии - само общият брой е важен. В действителност няма достатъчно търпение за провеждане на толкова дълга поредица от тестове. Но можете да напишете програма (или да използвате съществуващи като тази), която да изпълнява рутинни операции и да дава само броя на пресичанията за голям брой хвърляния.

Казаното в предишния параграф дава необичаен подход към важния проблем за точното изчисляване на числото π = 3,1415926... Нека припомним, че това число се определя като съотношението на дължината на окръжност към нейния диаметър (за всички окръжности това съотношение е същото). Числото π е една от основните константи в математиката и физиката. Това отчасти може да се обясни с факта, че окръжностите и елипсите се появяват в математиката и физиката в различни задачи и модели – от чисто геометрични до практически такива като изчисления на орбитите на планети и спътници. Ето защо е важно да можете точно да изчислите стойността на числото π. Известно е, че това число е ирационално, тоест не може да бъде представено като рационална дроб (отношението на две цели числа), но има дроби, близки до него с малки знаменатели. Архимед също е знаел, че дробта 22/7 = 3 (142 857) се приближава до π с точност до хилядни. Около V в. сл. н. е. д. приблизителното 355/113 = 3.14159292... беше вече известно - грешката е по-малка от една милионна.

Какво общо има иглата на Буфон? Както вече разбираме, в дълга поредица от тестове делът на пресичанията от общия брой хвърляния на игла ще бъде приблизително равен на 2/π. Следователно можем емпирично да намерим тази дроб и да изчислим приблизителна стойност. Колкото повече хвърляния, толкова по-точна ще бъде дробта и следователно стойността на π. През 19 век имаше герои, които бяха готови да прекарат няколко вечери в такава дейност. Те имат различни стойности около 3,14. Можете да прочетете повече на тази страница в английската Wikipedia.

Сега, разбира се, никой не хвърля игла и числото π вече е изчислено много над 10 трилиона цифри. Странно е, че такава прецизност не е почти необходима за практически изчисления - смята се, че е достатъчно да знаете π до около 40-ия знак след десетичната запетая, за да изчислите точно обема на видимата Вселена с точност до един атом. Така че изчисляването на π с такава точност е по-скоро надпревара за рекорди и съревнование между суперкомпютри.

Точните изчисления се основават на различни формули. По принцип се използват последователности, сходни към π и сумиране на серии; много алгоритми могат да бъдат намерени в Wikipedia. Тук представяме само една чудесна формула

което ви позволява да изчислите всяка цифра от π, без да изчислявате останалите цифри.