Difference between revisions 4727906 and 4789505 on hywiki

< previous diff
next diff >
ԱԳԱՀ ալգորիթմ
[[Մաթեմատիկա]]յում, '''Monte Carlo ինտեգրումը''' հանդիսանում է [[թվային քառակուսացում|թվային ինտեգրում]], որը օգտագործում է[[pseudorandomness|պատահական համարները]]։ Այսինքն, Monte Carlo ինտեգրման մեթոդները [[ալգորիթմների]] համար որոշակի [[ինտեգրալ]]ների մոտավոր գնահատումն է, սովորաբար նրանցից բազմատարածականները։ Սովորական ալգորիթմները գնահատում են ներառելով հերթական ցանցը։ [[Monte Carlo մեթոդներ]]ը, սակայն, պատահականորեն ընտրում են կետերը, որով ներառվածը գնահատվում է։

Պաշտոնապես, ինչպես գնահատել D դաշտը, նախ ընտրեք այն պարզ դաշտ E-ն, որի տարածքը հեշտությամբ հաշվարկվում և որը պարունակում է D։ Այժմ պատահական հաջորդականությամբ ընկնում է E-ին մոտ։ Որոշ կոտորակներ ընկնում են D-ին մոտ. D դաշտը գնահատվում է, ապա այս մասն բազմապատկվում է E դաշտի կողմից։

Ավանդական Monte Carlo ալգորիթմը տարածում է գնահատման միավորը [[Uniform բաշխման (շարունակական)|uniformly]] ինտեգրման տարածաշրջանում։ Հարմարվող ալգորիթմները, ինչպիսիք են VEGAS և MISER օգտագործում են [[կարևոր նմուշառում]] և [[stratified նմուշառում]] տեխնիկայի ավելի լավ արդյունք ստանալու համար։

== Պարզ   Monte Carlo integration ալգորիթմը  ==
Պարզ Monte Carlo ինտեգրման ալգորիթմը հաշվարկում է [[Multiple անբաժանելի|բազմատարածական որոշակի անբաժան]] նախահաշիվը, որը այս ձևով է,
:<math>I = \int_{a_1}^{b_1}dx_1\int_{a_2}^{b_2}dx_2\dots\int_{a_n}^{b_n}dx_n \,
f(x_1, x_2, \dots, x_n)
\equiv \int_{V}f(\bar{\mathbf{x}}) \, d\bar{\mathbf{x}}</math>

որտեղ <math>\bar{\mathbf{x}}=\{x_1,\dots,x_n\}</math> և [[հիպերխորանարդը]] <math>V</math> տարածաշրջանի ինտեգրացիան է,
(contracted; show full)
Նվազում են, ինչպես <math>1/\sqrt{N}</math>. [[պատահական զբոսանք]] ծանոթ օրենքը տարածվում է։ նվազեցնում է սխալը 10 գործոնից 100- ապատիկի չափով թվի աճ։

Վերը արտահայտությունն ապահովում է վիճակագրական գնահատական սխալի մասին. Արդյունքում, այս հաշվարկը սխալ չէ, խիստ սխալ է կարված; տարածաշրջանի պատահական ընտրանքը չի կարող բացահայտել բոլոր կարևոր հատկանիշները, որոնք գործում են, ինչի արդյունքում է թերագնահատում է այդ սխալը։

== Ռեկուրսիվ շերտավորված ընտրանք
  ==
Recursive Stratified ընտրանքի վկայումը. Այս օրինակում, այդ ֆունկցիան <math>f(x,y) = \big\{ \begin{smallmatrix}1, & \text{if } x^2+y^2<1\\0, & \text{if } x^2+y^2 \ge 1\end{smallmatrix}</math>- ից բարձր էր լուսաբանելու ինտեգրված միավորի հրապարակում օգտագործելով առաջարկվող ալգորիթմը. Այդ նմուշի միավոր արձանագրվել է և հայտնաբերվել։ Ակնհայտ շերտով դասված նմուշներում ալգորիթմի խտանյութերի կետերը շրջաններում է, որտեղ գործառույթի փոփոխությունը ամենամեծն է։]]
(contracted; show full)ործվում է MISER Monte Carlo ալգորիթմը ինտեգրելու f գործառույթը dim- ծավալայինի նկատմամբ հիպերխորանարդ տարածաշրջանի կողմից սահմանված ստորին և վերին սահմաններն են դաս xl և xu, յուրաքանչյուրը dim չափի։ Ինտեգրումն օգտագործում է ֆիքսված ֆունկցիայի զանգերի համարը, և ստանում պատահական ստուգման կետերը օգտագործելով պատահական r թիվ գեներատորը։ Նախկինում հատկացված աշխատանքային տեղ s-ը պետք է տրամադրվեն։ Ինտեգրման արդյունքը վերադարձվում է, արդյունքում նաև գնահատված բացարձակ սխալը abserr։

=== Ուրվագծված պարամետրեր ===
  
ԱԳԱՀ ալգորիթմը ունի մի քանի ուրագծված պարամետրեր
==== estimate_frac ====
Այս պարամետրը սահմանում է կոտորակ, որը ներկայումս առկա է մի շարք ֆունկցիայի կանչերում, որոնք հատկացված է գնահատելու յուրաքանչյուր վերադարձաց քայլի շեղվում։ Իսկ [[GNU Գիտական Գրադարանի]] (GSL) իրականացման նախնական արժեքը 0.1 է։

====  րոպե_զանգեր (min_calls) ====
Այս պարամետրը սահմանում է ֆունկցիայի կանչերի նվազագույն քանակը, որից յուրաքնաչյուրը շեղվում է հաշվարկի մեջ. Եթե ֆունկցիայի համարի կոչերը հատկացված են գնահատականներով, օգտագործելով estimate_frac ընկնում է ներքև min_calls ապա օգնագործում ենք min_calls-ի փոխարեն. Սա երաշխավորում է, որ յուրաքանչյուր նախահաշիվը պահպանվում է ողջամիտ մակարդակի ճշգրտությամբ. [[GNU գիտական գրադարանի]] իրականացումը, min_calls-ի նախնական արժեքը 16 * dim է։

==== րոպե_զանգեր_կիսորդ (min_calls_per_bisection) ====
Այս պարամետրը սահմանում է ֆունկցիայի կանչերի   նվազագույն քանակը, որը շարունակել է այն կիսում քայլի հետ. Երբ վերադարձ քայլը ունի ավելի քիչ զանգեր, քան առկա min_calls_per_bisection-ը, այն կատարում է պարզ Monte Carlo ընթացիկ ենթահանձնաժողովների նախահաշիվը տարածաշրջանում և դադարեցնում է իր մասնաճյուղի ռեկուրսիան։ [[GNU գիտական գրադարանի]] իրականցումը, պարամետրի նախնական արժեքը 32 * min_calls է։

====  ալֆա(alpha) ====
Այս պարամետրը վերահսկում է, թե ինչպես գնահատած անհամաձայնությունների համար երկու ենթահաշիվների շրջաններից մեկը համակցված կիսում է, երբ հատկացվում է միավոր։ Անհամաձայության ընտրանքի ընդհանուր գժտությունում լայնածավալը ավելի լավ է, քան 1/N-ում, քանի որ ենթահանձնաժողովների շրջաններիվ նախատեսված արժեքները ձեռք են բերել օգտագործման կարգը, որով հստակորեն նվազեցնում են իրենց շեղվումը։ Այս պահվածքի տեղավորելը թույլ է տալիս ԱԳԱՀ ալգորիթմի ընդհանուր գժտություն, որը կախված է մի չափման պարամետրից \ ալֆաից,

:<math>\mathrm{Var}(f) = {\sigma_a \over N_a^\alpha} + {\sigma_b \over N_b^\alpha}</math>

Սկզբնական թղթի հեղինակները բնութագրում են ԱԳԱՀ խորհուրդի արժեքը <math>\alpha = 2</math> որպես լավ ընտրություն է, ստացված թվային փորձերից, և դա օգտագործվում է որպես լռելյայն արժեք [[GNU գիտական գրադարանի]] իրականացումում։

==== dither ====
Այս պարամետրը ներկայացնում է պատահական կոտորակային տատանումների չափի dither յուրաքանչյուր կիսումում, որը կարելի է օգտագործել կոտրելու ինտեգրալների սիմետրիան, որոնք կենտրոնացած են հիպերխորանարդ ինտեգրման տարածաշրջանի կենտրոնին շատ ճշգրիտ։ [[GNU գիտական գրադարանի]] իրականացումում, dither-ի նախնական արժեքը զրոյական է, այնպես որ ոչ մի փոփոխություն չի ներկայացվել. Անհրաժեշտության դեպքում dither-ի տիպիկ արժեքը մոտ 0.1-ին։

== Կարևոր   նմուշառումը ==

=== VEGAS Monte Carlo ===

G.P.Lepage-ի [[VEGAS ալգորիթմը]] հիմնված է [[Կարևոր ընտրանքի]] վրա. Այն հավանականության բաշխման ընտրանքների միավորը նկարագրված է ֆունկցիային <math>|f|</math>, որի կետերը կենտրոնացած են ռեգիոններում, որոնք ինտեգրալ ամենամեծ ներդրումն էր.

(contracted; show full)
Այս պարամետրը տալիս է chi-squared-ի մեկ աստիճան ազատություն ինտեգրալի գնահատման համար. Chisq-ի արժեքը պետք է մոտ լինի 1-ի. Chisq-ի արժեքը, որը զգալիորեն տարբերվում է 1-ից, նշենք, որ տարբեր բազմակրկնվող արժեքները անհետևողական են. Այս դեպքում կշռված սխալը գնահատվում է և հետագա բազմակրկնվող ալգորիթմը անհրաժեշտ է ձեռք բերել հուսալի արդյունքներ.

==== ալֆա(alpha) ====
alpha պարամետրը վերահսկում է ստացվող ալգորիթմի կոշտությունը. Այն սովորաբար սահմանվում է մեկ և երկուսի միջև. Զրո արժեքը խանգարում է 
  ստացվող   ցանցին։ [[GNU գիտական գրադարանի]] իրականացման նախնական արժեքը 1.5.

====  iterations(բազմակրկնություն)  ====
բազմակրկնություն թիվը կատարում է յուրաքանչյուր զանգի ռեժիմի վրա. [[GNU գիտական գրադարանի]] իրականացման նախնական արժեքը 5 բազմակրկնություն։

==== փուլ(stage) ====
Համարը որոշում է հաշվարկման փուլը. Սովորաբար, փուլ= 0, որը սկսվում է նոր միասնական ցանցից և դատարկ միջին կշիռ. Կոչված vegas փուլը= 1 պահպանում է ցանց նախորդ հաշվով, սակայն discards միջին կշիռը այնպես, որ կարելի է "tune"   ցանց օգտագործելով համեմատաբար քիչ միավորներ, ապա դա մեծ հաշվով ղեկավարում է փուլ= 1-ին օպտիմիզացված ցանց։ Կարգավորման փուլում = 2 պահում է ցանց և նախորդ հաշվով միջին կշիռը, սակայն կարող է աճել (կամ նվազել) դիագրամմայի bins թվի grid կախված առկա զանգերի քանակից. Ընտրելով փուլ= 3 մտնում է գլխավոր հանգույց, այնպես որ ոչինչ չի փոխվել, և համարժեք է կատարել լրացուցիչ մտադրություն նախորդ այցով։

==== ռեժիմ(mode) ====
Հնարավոր ընտրություններ են GSL_VEGAS_MODE_IMPORTANCE, GSL_VEGAS_MODE_STRATIFIED, GSL_VEGAS_MODE_IMPORTANCE_ONLY. Այս սահմանում VEGAS-ը կօգտագործի կարևորության նմուշառումը կամ շերտ-շերտ կազմած ստուգումը, կամ արդյոք այն կարող է վերցնել իր սեփականը. Ցածր հարթություններում VEGAS-ը օգտագործում խիստ է շերտ-շերտ կազմած ստուգումը (ավելի ճիշտ, շերտ-շերտ դասված նմուշառումը ընտրվում է, եթե մեկ արկղում առկա է 2-ից պակաս արկղ).

==  Տես նաև ==
*  [[Auxiliary field Monte Carlo]]

== Հիշատակում և հետագա ընթերցանությունը ==
Հետևյալ հղում Monte Carlo-յի մասին և quasi-Monte Carlo մեթոդները ընդհանրապես (ինչպես նվազեցման տեխնիկայի շեղման նկարագրության մեջ) հիանալի է սկսել։
* R. E. Caflisch, ''Monte Carlo and quasi-Monte Carlo methods'', Acta Numerica vol. 7, Cambridge University Press, 1998, pp.&nbsp;1–49.
Nice survey on arXiv, based on lecture for graduate students in high energy physics։
* S. Weinzierl, ''[http://arxiv.org/abs/hep-ph/0006269/ Introduction to Monte Carlo methods]'', 
The MISER algorithm is described in the following article, 
* W.H. Press, G.R. Farrar, Recursive Stratified Sampling for Multidimensional Monte Carlo Integration, Computers in Physics, v4 (1990), pp190–195. 
The VEGAS algorithm is described in the following papers, 
* G.P. Lepage, A New Algorithm for Adaptive Multidimensional Integration, Journal of Computational Physics 27, 192-203, (1978) 
* G.P. Lepage, VEGAS։ An Adaptive Multi-dimensional Integration Program, Cornell preprint CLNS 80-447, March 1980 
Early works։
* J. M. Hammersley, D.C. Handscomb (1964) Monte Carlo Methods. Methuen. ISBN 0-416-52340-4
Ընդհանուր քննարկումը, ներառելով և MISER-ը և VEGAS-ը և համեմատելով, դա
*  {{Cite book | last1=Press | first1=WH | last2=Teukolsky | first2=SA | last3=Vetterling | first3=WT | last4=Flannery | first4=BP | year=2007 | title=Numerical Recipes: The Art of Scientific Computing | edition=3rd | publisher=Cambridge University Press |  publication-place=New York | isbn=978-0-521-88068-8 | chapter=Section 7.9 Adaptive and Recursive Monte Carlo Methods | chapter-url=http://apps.nrbook.com/empanel/index.html#pg=410}}
----
''Հիմնվելով   [[GNUգիտական գրադարան]]ի ձեռնարկի վրա, որը հրապարակվում է GFDL (և հետևաբար ազատ է Wikipedia օգտագործման համար). Original available [http://www.gnu.org/software/gsl/manual/gsl-ref_23.html here].''

== Արտաքին հղումներ ==
*  [http://math.fullerton.edu/mathews/n2003/MonteCarloMod.html Module for Monte Carlo Integration]
*  [http://math.fullerton.edu/mathews/n2003/montecarlo/MonteCarloBib/Links/MonteCarloBib_lnk_1.html Internet Resources for Monte Carlo Integration]

[[Կատեգորիա:Monte Carlo methods]]

[[ca:Integració de Montecarlo]]
[[de:Monte-Carlo-Algorithmus]]
[[es:Integración de Monte Carlo]]
[[sr:Монте Карло интеграција]]
[[vi:Tích phân Monte-Carlo]]