Monte-Carlo-integrálás

Egy illusztráció a Monte-Carlo-integrálásról A példában D a belső kör, és E a négyzet. A négyzet területe könnyen kiszámítható, így a körlap területe (π*12) megbecsülhető a körön belüli (40) és az összes pont (50) számának arányából. A körlap területe így 4*0.8 = 3.2 ≈ π*12.

A matematikában a Monte-Carlo-integrálás egy olyan numerikus integrálási módszer, mely véletlen számokat használva számol. A többi integrálási algoritmus általában egy szabályos rácson értékeli ki az integrandust, míg a Monte-Carlo-módszerrel véletlen pontokban végez függvénykiértékelést. Ez a módszer különösen hasznos többdimenziós integrálok számításakor.

Áttekintés

Numerikus integrálás esetén egyes módszerek, például a trapézszabály a feladatot determinisztikus módon közelítik meg. Ezzel ellentétben a Monte-Carlo integrálás egy nem determinisztikus (sztochasztikus) módszer: minden végrehajtás után különböző eredményt kapunk, ami a pontos érték egy megközelítése.

A determinisztikus numerikus integrálási módszerek kevés dimenzióban jól működnek, viszont sokváltozós függvények esetében két probléma lép fel. A szükséges függvénykiértékelések száma gyorsan nő a dimenziók számával (hogyha 10 kiértékelés nyújt megfelelő pontosságot egy dimenzióban, akkor 100 dimenzióban 10100 pontban kell értéket kiszámolnunk). A második nehézséget a többdimenziós integrálási tartomány határa jelenti, a feladat legtöbbször nem vezethető vissza egymásba ágyazott egydimenziós integrálok kiszámítására.

A számítási idő exponenciális növekedése áthidalható a Monte-Carlo-módszerek alkalmazásával. Ha a függvény „jól viselkedik”, az integrált megbecsülhetjük a 100 dimenziós térben véletlenszerűen felvett pontokban számolt függvényértékek súlyozott átlagával. A centrális határeloszlás-tétel alapján a módszer konvergenciája (pl.: a mintapontok számát négyszeresére növelve a hiba feleződik, a dimenziók számától függetlenül).

Egy illusztráció a Monte-Carlo-integrálás hiba számolásárol

Az algoritmus javítására egy lehetőség a statisztikában fontossági mintavételként ismert módszer, aminek lényege, hogy a mintapontokat véletlenszerűen választjuk ki, de ott, ahol az integrandus értéke nagyobb, sűrűbben veszünk mintát. Ennek pontos végrehajtásához előre ismernünk kéne az integrált, viszont megközelíthetjük azt egy hasonló függvény integráljával. Adaptív módszerek alkalmazása is hatékonyabbá teszi az algoritmust, ilyenek a rétegzett mintavétel, a rekurzív rétegzett mintavétel, az adaptív esernyő-mintavételi technika vagy a VEGAS algoritmus.

A kvázi Monte-Carlo-módszerek alacsony diszkrepanciájú sorozatokat használnak, melyek egyenletesebben „kitöltik” a tartományt. Egy tartományban véletlen bolyongás módszereivel (Markov-lánc Monte-Carlo MCMC) is generálhatunk véletlenszám-sorozatot. Erre példa a Metropolis-Hastings algoritmus, Gibbs-mintavétel valamint a Wang és Landau algoritmus.

Története

A Monte-Carlo-módszer története az 1930-as évektől ismert, Enrico Fermi nevéhez fűződik, majd az 1940-es években Neumann János és Stanisław Ulam foglalkozott vele, a Manhattan projekt keretein belül.

A módszer kifejlesztése előtt a szimulációkat a már megértett folyamatok ellenőrzésére használták, véletlen mintákkal a determinisztikus modell bizonytalanságait becsülték fel. A második világháború után a Los Alamos-i kutatóintézetben a neutronok szabad úthosszának meghatározása különböző anyagokban, analitikus módszerekkel nem volt megoldható. Stanislaw Ulam javasolta a véletlen értékekkel végzett kísérleteket, melyekből következtetéseket lehetett levonni a jelenségre vonatkozóan.

Monte Carlo szimuláció

Valószínűség-eloszlás mintavételezése. A minták alapján lehetséges kimenetek meghatározása. A lehetséges kimenetek valószínűségének számítása.

Többszörös integrálok értékének meghatározása

A többszörös integrál transzformálása

Az I integrál geometriai jelentése egy m+1 dimenziójú térfogat, vagyis egy Ox1x2...xmy térben S alapú egyenes hiperhenger, melyet felülről az y=f(x1,x2,...,xm) felület határol.

Legyen az függvény folytonos egy zárt S tartományon.

A feladat az integrál értékének meghatározása.

Az I integrált olyan alakra hozzuk, hogy az új integrálási tartomány egy m dimenziós egységélű hiperkockán belülre kerüljön.

Ha az S tartomány a következő m dimenziós paralelepipedonon belül helyezkedett el változócserét végzünk a következőképpen:

A transzformáció Jacobi-determinánsát felhasználva

ahol

az alábbi jelöléseket bevezetve:

A fenti integrált két véletlen mintavételen alapuló módszerrel számolhatjuk ki:

Az integrál kiszámolása Mote-Carlo-módszerrel

Első módszer

Generáljunk a [0,1] intervallumon m darab, N elemből álló véletlen számsorozatot egyenletes eloszlással. A számsorokból az m dimenziós hiperkockán belül N pontot kapunk:

Elegendő mintapont felvétele után megszámoljuk azokat a pontokat, melyek a σ tartományon belül találhatók. Ha a tartomány határa bonyolult, különösen fontos feltételeket szabni arra, mikor tekintjük a pontot tartományon belülinek. Ha n pont esett a tartományon belülre, y átlagértéke:

A kiszámolandó integrál értéke:

behelyettesítési értéket csak abban az esetben számolunk, ha a pont az integrálási tartományon belül található.

Második módszer

Ha az F függvény nemnegatív, az integrál felírható alakban, aminek geometriai jelentése egy m+1 dimenziós térfogat.

változócserével, ahol

a ν tartomány az m+1 dimenziós egységoldalú hiperkockán belül helyezkedik el. Ezúttal az Oξ1ξ2...ξmη térben vesszük fel a mintapontokat. Ha N pontból n tartozik a ν térfogathoz, elegendően nagy N értékre az integrál:

Források

  • Computational Mathematics B.P. Demidovich, I. A. Maron, Mir Publishers, Moscow, 1981

Read other articles:

Species of bird Armenian gull Conservation status Least Concern (IUCN 3.1)[1] Scientific classification Domain: Eukaryota Kingdom: Animalia Phylum: Chordata Class: Aves Order: Charadriiformes Family: Laridae Genus: Larus Species: L. armenicus Binomial name Larus armenicusButurlin, 1934 Synonyms[2] Larus cachinnans armenicus The Armenian gull (Larus armenicus) is a large gull found in the Caucasus and the Middle East. It was formerly classified as a subspecies of the ...

 

Award2008 Summer Olympics medalsLocationBeijing,  ChinaHighlightsMost gold medals China (48)Most total medals United States (112) ← 2004 · Olympics medal tables · 2012 → Map of the world showing the achievements of each country during the 2008 Summer Olympics in Beijing, People's Republic of China.Gold for countries achieving at least one gold medal.Silver for countries achieving at least one silver medal.Brown for countries achieving...

 

American weekly trade news magazine Publishers WeeklyEditorial DirectorJim MilliotCategoriesPublishingBook reviewsTrade magazineFrequencyWeeklyPublisherCevin BryermanTotal circulation(2017)24,000 [1]First issue1872; 151 years ago (1872)CompanyPWxyz, LLCCountryUnited StatesBased inNew York CityLanguageEnglishWebsitewww.publishersweekly.com ISSN0000-0019 Publishers Weekly (PW) is an American weekly trade news magazine targeted at publishers, librarians, booksellers, an...

Innenhof mit Eingang zum Restaurant Das Haus Scheppen ist ein ehemaliger, adliger Lehnshof der Abtei Werden im Essener Stadtteil Fischlaken. Mit bis zu 23 Unterhöfen gehörte der befestigte Hof im Mittelalter zu den größten Werdener Lehnsgütern. Seine Namensgeber waren die Herren von Scheppen, die im 14. Jahrhundert Lehnsnehmer des Hauses waren. Die Anlage steht am südlichen Ufer des Baldeneysees an der Mündung des Hesperbachs in die Ruhr. Sie befindet sich heute im Besitz der...

 

Model 8 Sirius Sirius at National Air and Space Museum Role Utility transportType of aircraft Manufacturer Lockheed Aircraft Limited Designer Jack NorthropGerard Vultee First flight 1929 Introduction 1929 Number built 15 The Lockheed Model 8 Sirius was a single-engined, propeller-driven monoplane designed and built by Jack Northrop and Gerard Vultee while they were engineers at Lockheed in 1929, at the request of Charles Lindbergh. Two versions of the same basic design were built for the Unit...

 

Public schoolJohn Marshall High SchoolLocation3939 Tracy StreetLos Angeles, California 90027United StatesInformationTypePublic schoolEstablished1931School districtLos Angeles Unified School DistrictPrincipalGary GarciaStaff96.67 vte[1]Grades9–12Number of students2,004 (2021–22)[1]Student to teacher ratio20.73[1]Color(s)Midnight Blue and Sunlight BlueAthleticsJohn Marshall High School BarristersAthletics conferenceNorthern LeagueCIF Los Angeles City SectionMascotJoh...

Canadian actor-singer Liam Russell (formerly Titcomb)Titcomb in 2012Background informationBirth nameLiam Russell-TitcombBorn (1987-08-16) August 16, 1987 (age 36)OriginToronto, Ontario, CanadaGenresRock, Folk rock, AmericanaInstrument(s)vocals, Guitar, Piano, Bass, drumsYears active2001-presentWebsitewww.liamrussellmusic.comMusical artist Liam Russell (born Liam Russell-Titcomb August 16, 1987) is a Canadian musician and actor. He released his self-titled album on Sony Music Canada in 20...

 

1980 single by the Korgis Everybody's Got to Learn SometimeSingle by the Korgisfrom the album Dumb Waiters B-sidePerfect HostessReleased11 April 1980 (1980-04-11)[1]Recorded1980GenrePopnew wavesynthpopsoft rock[2]Length4:24LabelRialto (UK), Asylum (US)Songwriter(s)James WarrenProducer(s)The Korgis, David LordThe Korgis singles chronology I Just Can't Help It (Remix) (1980) Everybody's Got to Learn Sometime (1980) If It's Alright With You Baby / Love Ain't Too Fa...

 

Chinese chess player For the judoka, see Xu Yuhua (judoka). In this Chinese name, the family name is Xu. Xu YuhuaXu Yuhua in 2008CountryChinaBorn (1976-10-29) 29 October 1976 (age 47)[1]Jinhua, Zhejiang, ChinaTitleGrandmaster (2006)Woman Grandmaster (2001)Women's World Champion2006–08FIDE rating2465 (December 2023) [inactive]Peak rating2517 (April 2006) Xu YuhuaTraditional Chinese許昱華Simplified Chinese许昱华TranscriptionsStandard MandarinHanyu PinyinXǔ Y...

1926 film by Renaud Hoffman For other uses, see Unknown Soldier (disambiguation). The Unknown SoldierLobby cardDirected byRenaud HoffmanScreenplay byRichard SchayerJames J. TynanProduced byRenaud HoffmanStarringCharles Emmett MackMarguerite De La MotteHenry B. WalthallClaire McDowellGeorge CooperCinematographyRay JuneProductioncompaniesCharles R. Rogers ProductionsRenaud Hoffman ProductionsDistributed byProducers Distributing CorporationRelease date May 30, 1926 (1926-05-30) Ru...

 

Boruch of MedzhybizhTitleReb Boruch MezhbizherPersonalBornBoruch (of Medzhybizh)1753MedzhybizhReligionJudaismSpouse?? daughter of R. Tovia Katskes, Sima Chusha daughter of R' Aharon of TitievChildrenUdl AverbuchChana Chaya DrubitsherReyzl(no sons)ParentsYechiel of Tulchyn (father)Udl (daughter of Baal Shem Tov) (mother)Began1782Ended4 December 1811, 18 Kislev 5572.Main workButsino diNhoiroDynastyMezhbizh Rabbi Boruch of Medzhybizh (1753–1811), was a grandson of the Baal Shem Tov. Reb Boruch...

 

13th National People's Congress← 12th14th →National Emblem of the People's Republic of China5 March 2018 – 5 March 2023(5 years, 0 days)OverviewTypeHighest organ of state powerElectionNational electionsLeadershipChairmanLi ZhanshuVice ChairmenWang Chen, Cao Jianming, Zhang Chunxian, Shen Yueyue, Ji Bingxuan, Arken Imirbaki, Wan Exiang, Chen Zhu, Wang Dongming, Padma Choling, Ding Zhongli, Hao Mingjin, Cai Dafeng, and Wu WeihuaSecretary-GeneralYang Zhenwu...

Soveratocollegio elettoraleStato Italia Elezioni perCamera dei deputati ElettiDeputati Periodo 1993-2005Tipologiauninominale Territorio Manuale Il collegio di Soverato fu un collegio elettorale uninominale della Repubblica Italiana per l'elezione della Camera dei deputati. Apparteneva alla circoscrizione Calabria e fu utilizzato per eleggere un deputato nella XII, XIII e XIV legislatura. Venne istituito nel 1993 con la cosiddetta Legge Mattarella (Legge n. 277, Nuove norme per l'elezione...

 

Guerre franco-chinoise Batailles de la campagne de 1884-1885. Informations générales Date de août 1884 à juin 1885 Lieu Chine, Taïwan et Viêt Nam Issue Victoire française Traité de Tianjin : La Chine abandonne sa suzeraineté sur l'Annam (actuel Viêt Nam), que la France achève de coloniser. Belligérants République française Empire de Chine Pavillons noirs  Empire d'Annam Commandants Amédée Courbet Sébastien Lespès Louis Brière de l'Isle Oscar de Négrier Laurent Gi...

 

Lambang Daerah Istimewa Yogyakarta Peta Lokasi Daerah Istimewa Yogyakarta di Indonesia Peta Kabupaten di Daerah Istimewa Yogyakarta Berikut daftar kapanewon/kemantren dan kelurahan/kalurahan di Daerah Istimewa Yogyakarta, Indonesia. Daerah Istimewa Yogyakarta terdiri dari 4 kabupaten, 1 kota, 78 kapanewon/kemantren, 46 kelurahan dan 392 kalurahan. Pada tahun 2017, jumlah penduduknya diperkirakan mencapai 3.606.111 jiwa dengan total luas wilayah 3.133,15 km².[1][2] Pada t...

Finnish singer This biography of a living person needs additional citations for verification. Please help by adding reliable sources. Contentious material about living persons that is unsourced or poorly sourced must be removed immediately from the article and its talk page, especially if potentially libelous.Find sources: Danny Finnish singer – news · newspapers · books · scholar · JSTOR (August 2017) (Learn how and when to remove this template m...

 

Гіпсографі́чна крива́ (рос.гипсографическая кривая, англ. hypsometric graph, нім. hypsometrische Kurve f) — графік співвідношення площ земної поверхні, зайнятих різними абсолютними висотами та глибинами. При побудові гіпсографічної кривої по осі ординат відкладають висоти і глибини, п...

 

For gnus (the animals), see wildebeest. GnusGnus 5.11 under GNU Emacs and FedoraDeveloper(s)Gnus teamInitial release1987; 37 years ago (1987)[1]Repositorygit.savannah.gnu.org/cgit/emacs.git/tree/lisp/gnus/ Operating systemCross-platformTypeE-mail client and news clientLicenseGPL-3.0-or-laterWebsitewww.gnus.org Gnus (/ɡəˈnuːz, ˈɡnuːz/), or Gnus Network User Services, is a message reader which is part of GNU Emacs. It supports reading and composing both e-mail a...

A Methodist chapel in Leliefontein, Northern Cape, South Africa. The Presiding Bishop of the Methodist Church of Southern Africa The Rev Pumla Nzimande The Methodist Church of Southern Africa (MCSA) is a large Wesleyan Methodist denomination, with local churches across South Africa, Namibia, Botswana, Lesotho and Eswatini, and a more limited presence in Mozambique. It is a member church of the World Methodist Council. The church is the largest mainline Protestant denomination in South Africa ...

 

Disambiguazione – Se stai cercando la Serie A in altri sport, vedi Serie A (disambigua). Serie AAltri nomiSerie A TIM Sport Calcio TipoClub FederazioneFIGC Paese Italia OrganizzatoreLega Serie A TitoloCampione d'Italia Cadenzaannuale Aperturaagosto Chiusuramaggio Partecipanti20 squadre Formulagirone unico asimmetrico Retrocessione inSerie B Sito Internetwww.legaseriea.it StoriaFondazione1898[N 1] Numero edizioni122 Detentore Napoli Record vittorie Juventus (36) Ultim...

 

Strategi Solo vs Squad di Free Fire: Cara Menang Mudah!