Revision 793004 of "ԱԳԱՀ ալգորիթմ" on hywiki


[[Մաթեմատիկա]]յում, '''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> տարածաշրջանի ինտեգրացիան է,
:<math>\{ \bar{\mathbf{x}} ; a_1\le x_1\le b_1, a_2\le x_2\le b_2,\dots, a_n\le x_n\le b_n\}</math>.
Բայց ստորեւ մենք պետք է օգտագործենք <math>V</math> մատնանշելով այս տարածաշրջանի չափումը.

Իսկ ալգորիթմի նմուշների միավորները միասնական են ինտեգրման տարածաշրջանից  գնահատելով այն ամբողջական և  իր սխալը. Ենթադրենք, որ ընտրանքը ունի չափ <math>N</math>  եւ այդ ընտրանքի միավորները մատնանշվում են <math>\bar{\mathbf{x}}_1, \dots,  \bar{\mathbf{x}}_N</math >  կողմից . Այնուհետեւ ինտեգրալի նախահաշիվը  տրվում է

:<math> I \approx Q_N \equiv V\frac{1}{N} \sum_{i=1}^N f(\bar{\mathbf{x}}_i) = V \langle f \rangle </math>,
Որտեղ <math>\langle f \rangle</math>  նշանակում է ենթաինտեգրալ-ի  [[նմուշ]]. <math> I = \lim_{N \to \infty} Q_N </math>  հետեւում է այն փաստը, որ  <math> \{ \bar{\mathbf{x}}_1, \bar{\mathbf{x}}_2, \bar{\mathbf{x}}_3, \ldots \} </math>  ինտեգրման  շրջանի [[էկվիվալենտ տարածված հաջորդականությունը ]] (անտեսելով իրականացման հարցեր, ինչպիսիք են  [[կեղծ պատահական գեներատորի համարը |կեղծ պատահական գեներատորների շարքը]] եւ սահմանափակ ճշգրտության  [[լողացող կետը]]).

ենթաինտեգրալ-ի  [[Sample_variance#Population_variance_and_sample_variance|նմուշի դիսպերսիան]]  կարելի է գնահատել, օգտագործելով
:<math> \mathrm{Var}(f)\equiv\sigma_N^2 = \frac{1}{N-1} \sum_{i=1}^N (f(\bar{\mathbf{x}}_i) - \langle f \rangle)^2, </math>
Որտեղ օգտագործվում է <math>N-1</math>  <math>N</math>-ի փոխարեն,  որպեսզի ստանան [[Bias_of_an_estimator#Sample_variance|դիսպերսիայի անկողմնակալ գնահատականը]].

Քանի որ հետեւյալ ուժի մեջ է ցանկացած անկախ փոփոխականների ակուստիկան <math>Y_i</math>,
:<math>\mathrm{Var}\left(\sum_{i=1}^N Y_i\right)=\sum_{i=1}^N \mathrm{Var}(Y_i)</math>,
եւ քանի որ, որպես մշտական  <math> a </math> ունի հետեւյալ գույքը,
:<math>\mathrm{Var}(a f) = a^2 \mathrm{Var}(f)</math>,
Ապա ինտեգրալի գնահատականների փոփոխությունը
:<math> \mathrm{Var}(Q_N) =  \frac{V^2}{N^2} \sum_{i=1}^N \mathrm{Var}(f)  =V^2 \frac{\mathrm{Var}(f)}{N} = V^2\frac{\sigma_N^2}{N}</math>.

Քանի դեռ հաջորդականությանը <math> \{ \sigma_1^2, \sigma_2^2, \sigma_3^2, \ldots \} </math>սահմանափակ է, այդ փոփոխությունը նվազեցնում  է ասիմպտոտորեն մինչեւ զրո, ինչպես  <math>\frac{1}{N}</math>. Սխալ նախահաշիվը,
:<math>\delta Q_N\approx\sqrt{\mathrm{Var}(Q_N)}=V\frac{\sigma_N}{\sqrt{N}},</math>
Նվազում են, ինչպես <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>- ից բարձր էր լուսաբանելու ինտեգրված միավորի հրապարակում օգտագործելով առաջարկվող ալգորիթմը. Այդ նմուշի միավոր արձանագրվել է և հայտնաբերվել. Ակնհայտ շերտով դասված նմուշներում ալգորիթմի խտանյութերի կետերը շրջաններում է, որտեղ  գործառույթի փոփոխությունը ամենամեծն է.]]
'''Ռեկուրսիվ շերտավորված ընտրանքը''' մեկ տարածական ընդհանրացում է [[հարմարվող քառակուսու]] բազմակողմ ինտեգրալի  հետ. Յուրաքանչյուր ռեկուրսի քայլ  ամբողջական է եւ սխալ է գնահատվում օգտագործելով պարզ Monte Carlo ալգորիթմը. Եթե նախահաշիվի սխալը  ավելի մեծ է, քան պահանջվող ճշգրտության ինտեգրումը, ծավալը բաժանվում է ենթահաշիվների ծավալների եւ այդ ընթացակարգը կիրառվում է վերադարձում ենթահաշիվների ծավալներով.

Սովորական ' երկուի բաժանարար ' ռազմավարությունը չի աշխատում բազմամյա հարթություններում, քանի որ ենթահաշիվներից մի շանիսի ծավալները աճում են, շատ արագ ուղին չկորցնելով. Մեկ գնահատականների փոխարեն, որոնց ստորաբաժանումը բերում է ամենաշատ շահաբաժինները եւ միայն այս հարթության ստորաբաժանումի ծավալի երկայնքով.

Ահա տիպիկ ալգորիթմ  Ռեկուրսիվ շերտավորված ընտրանք-ի համար:

Օրինակ  <math>N</math> պաըահական կետերը;
Միջին գնահատականը  և սխալը;
'''If (Եթե)''' սխալը համարվում է ընդունելի:
'''Return(Վերադարձնել)'''միջինը և սխալը;
'''Each(Հակառակ դեպքում)''' :
'''For each''' փոփոխություն:
Երկու փոփոխության ծայրերի գումարը բաժանել;
Գնահատել երկու ծայրերի միջին նշանակությունները;
Ընտրել փոփոխությունը ամենամեծ ենթակետի միջինից;
Բաժանել երկու ծայրերի փոփոխությունների չափը;
Ամեն մի ենթածավալի համար ուղղարկել երկու ռեկուրսիվ արժեքներ;
Գնահատել մեծ միջինը և մեծ դիսպերսիան;
'''Return(Վերադարձնել)''' մեծ միջինը և մեծ դիսպերսիան;

Ռեկուրսիվ շերտավորված ալգորիթմը  կենտրոնանում է ռեգիոններում (ծայրերում) կետերի ընտրման վրա ,  որտեղ գործառույթի անհամաձայնությունը խոշորագույնն  է, այդպիսով նվազեցնելով մեծ վեճ ու դարձնելով առավել արդյունավետ  ընտրանք  , ինչպես  լուսաբանվում է.


Լուսաբանելու համար կետերը գեներացվել են հետևյալ կերպ [[JavaScript]]-1.8  վերը նշված ալգորիթմի իրականացումը,

<syntaxhighlight lang="javascript">
 function strata(f,a,b,acc,eps,N,aold,vold,nold,V)
 {
 if(typeof(N)=="undefined")N=42; // the number of points to be added at each recursion
 var randomx = function(a,b) [a[i]+Math.random()*(b[i]-a[i]) for (i in a)]
 var range   = function(n) {for(var i=0;i<n;i++) yield i}
 var stats   = function(xs){ // statistics
   var xmean=xs.reduce(function(a,b)a+b,0)/xs.length
   var sigma2=xs.reduce(function(a,b)a+b*b,0)/xs.length-Math.pow(xmean,2) 
   return [xmean,Math.sqrt(sigma2),xs.length]
   }
 if(typeof(aold)=="undefined"){ // first call: setting up 'old' values
   var V=1; for(let k in a) V*=(b[k]-a[k])
   let xs=[randomx(a,b) for(i in range(N))]
   let ys=[f(x) for each (x in xs)]
   var [aold,vold,nold]=stats(ys)
   }
 var xs=[randomx(a,b) for(i in range(N))] // new points
 var ys=[f(x) for each (x in xs)]         // new function values
 var [av,va,]=stats(ys)                    // average and variance
 var integ=V*(av*N+aold*nold)/(N+nold)    // integral and error
 var error=V*Math.sqrt( (va*va*N+vold*vold*nold)/(N+nold)/(N+nold) )
 if(error<acc+eps*Math.abs(integ)) return [integ,error]; // done
 else{ // not done: need to dispatch a recursive call
   var vmax=-1, kmax=0
   for(let k in a){ // look in all dimensions for which is best to bisect
      var [al,vl,nl]=stats([ys[i] for(i in xs)if(xs[i][k]< (a[k]+b[k])/2)])
      var [ar,vr,nr]=stats([ys[i] for(i in xs)if(xs[i][k]>=(a[k]+b[k])/2)])
      var v=Math.abs(al-ar) // take the one with largest variation
      if(v>vmax){ // remember the values
         vmax=v;kmax=k;
         var alo=al, vlo=vl, nlo=nl; var aro=ar, vro=vr, nro=nr
      }
   } // now dispatch two recursive calls
   let a2=a.slice(); a2[kmax]=(a[kmax]+b[kmax])/2
   let b2=b.slice(); b2[kmax]=(a[kmax]+b[kmax])/2
   let [i1,e1]=strata(f,a,b2,acc/1.414,eps,N,alo,vlo,nlo,V/2)
   let [i2,e2]=strata(f,a2,b,acc/1.414,eps,N,aro,vro,nro,V/2)
   return [i1+i2,Math.sqrt(e1*e1+e2*e2)] // return results
   }
 }
 var points=[]
 var fun=function([x,y]){
    points.push([x,y])
    return x*x+y*y<1 ? 1:0
    }
 var a=[-1,-1], b=[1,1]
 var acc=eps=0.5e-2
 var [q,err]=strata(fun,a,b,acc,eps,32)
 print("# m=0, S=1")
 for each(var [x,y] in points) print(x,y)
</syntaxhighlight>

Այսօր հայտնի ԱԳԱՀ ռեժիմը իրականացնում է նմանատիպ մի ալգորիթմ.
=== ԱԳԱՀ Monte Carlo ===

Մեդիա և Farrar ագահ ալգորիթմը  հիմնված է ռեկուրսիվ շերտավորված ընտրանք-ի վրա. Այս տեխնիկայի նպատակն է նվազեցնել ընդհանուր ինտեգրացիոն սխալը` կենտրոնացնելով ինտեգրացիոն միավորը ամենաբարձր շեղման ռեգիոններում (ծայրերում) .
. 

շերտավորված ընտրանք-ի գաղափարը սկսվում է դիտարկվել, որ  երկու a և b  շրջաններում, , ինչպես նաեւ  Monte Carlo-ում ինտեգրալի հաշվարկները <math>E_a(f)</math> և <math>E_b(f)</math> և գժտությունը <math>\sigma_a^2(f)</math> և <math>\sigma_b^2(f)</math>, իսկ գժտությունը <math>Var(f)</math> համակցված գնահատականներով <math>E(f) = (1/2) (E_a(f) + E_b(f))</math> տրված է, 

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


Կարելի է ցույց տալ, որ վեճը  նվազագույնի  է հասցվել բաշխման կետերի կողմից, օրինակ, 

:<math>N_a / (N_a + N_b) = \sigma_a / (\sigma_a + \sigma_b)</math>

Հետեւաբար ամենափոքր սխալ նախահաշիվը ստացվել է օրինակելի միավորը հատկացնելուց համամասնության ստանդարտ շեղումը չունեցող յուրաքանչյուր ենթահանձնաժողովների տարածաշրջանում. 

Այդ ԱԳԱՀ  ալգորիթմը ստացված է կիսված ինտեգրացիոն միջոցով տարածաշրջանի երկայնքով մեկ կոորդինատային առանցքին տալով երկու ենթախմբի շրջաններ յուրաքանչյուր քայլի համար. Ուղղությունը, որը ընտրվել է  ուսումնասիրու  բոլոր հնարավոր d  ժամերի կիսվածությունը  և ընտրելով մեկը, որը նվազագույնի է հասցնելու համակցված շեղումը  երկու ենթահաշիվների  ռեգիոններում . Ենթահանձնաժողովներից ռեգիոններում  գժտությունը գնահատվում է  մի ընդհանուր թվի մասի մատչելի ընթացիկ քայլով. Նույն ընթացակարգը, ապա կրկնում է յուրաքանչյուրի համար երկու կեսի տարածքների համար լավագույն կիսում. Մնացած ուղարկված միավորները հատկացվել են ենթահանձնաժողովների  ռեգիոններում օգտագործելով N_a and N_b բանաձեւը. Այս կրկնվող ինտեգրացիոն կետերի շարունակումը  տրամադրում է իջնել  օգտագործողի կողմից սահմանված խորությամբ, որտեղ յուրաքանչյուր ենթաօրենսդրական տարածաշրջանը (ռեգիոններում)  միասնական օգտագործում է պարզ Monte Carlo նախահաշիվը. Այս անհատական արժեքներն ու դրանց սխալի հաշվարկներն համակցված են տալու ընդհանուր արդյունքը եւ նախահաշիվի  սխալը. 

Այս հրամանաշարը օգտագործվում է  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>, որի կետերը կենտրոնացած են ռեգիոններում, որոնք ինտեգրալ ամենամեծ ներդրումն էր.


Ընդհանրապես, եթե Monte Carlo անբաժան է <math>f</math>  օրինակ, հավանականության բաշխումը նկարագրվում է ֆունկցիայի կողմից <math>g</math>, մենք ստանալու ենք գնահատական <math>E_g(f; N)</math>, 

<math>E_g(f; N) = E(f/g; N)</math>

ինչպես նաեւ համապատասխան գործավարությանը,
<math>Var_g(f; N) = Var(f/g; N)</math>

Եթե  բաշխման հավանականությունը ընտրված է որպես <math>g = |f|/I(|f|)</math>, ապա կարելի է ցույց տալ գործավարության դիսպերսիա <math>V_g(f; N)</math> անհետանալը, սխալ գնահատականները կլինեն  զրո. Գործնականում  հնարավոր չէ  բաշխման ընտրանքից  <math>g</math> կամայական գործողության համար, այսպես կարեւորության ստուգման ալգորիթմների  նպատակն է արտադրել արդյունավետ ցանկալի մոտեցում.

VEGAS ալգորիթմը մոտենում է հստակ բաժանումներին անցման թիվը դարձնելով ռեգինների ընտրման միջոցով ֆունկցիայի հիստոգրամացվելու յամանակ <math>f</math>. Ամեն հիստոգրամ օգտագործվում է ընտրանքի բաժանման որոշման համար հաջորդ անցման համար: Ասիմպտոտորեն այս պրոցեսը գնում է ցանկալի բաժանմանը: որպեսզի խուսապենք հիստոգրամային աղբից, մեծացնելով  <math>K^d</math> հավանականության բաժանումը պետք է մոտեցնենք բաժանման ֆունկցիային. <math>g(x_1, x_2, \ldots) = g_1(x_1) g_2(x_2) \ldots</math> այսպիսով վանդակների քանակը <math>Kd</math>: Եթե հնարավոր լինի ենթաինտեգրալը վերագրել ֆորմային, որը մոտորապես բաժանված է, դա կբարձրացնի VEGAS–ի հետ ինտեգրացիայի արդյունավետությունը: 

VEGAS-ը  ներառում է մի շարք լրացուցիչ հնարավորություններ,և  համատեղում է և շերտավորված ընտրանք, և ստուգման կարեւորությունը. Շրջանի ինտեգրումը բաժանված է մի շարք " արկղերի ", յուրաքանչյուր վանդակում ստանալու կայուն միավոր (նպատակը 2). Յուրաքանչյուր արկղ կարող  է ունենալ կոտորակային շարքեր,  բայց եթե արկղերը երկուսից պակաս են, Vegas-ը կրճատում է շեղումը  ( այլ ոչ թե կարեւոր  նմուշառումը). 

VEGAS Monte Carlo ալգորիթմը այս ընթացակարգից օգտվում է, որպեսզի ինտեգրի հետևյալ ֆունկցիան  <math>f</math> տարածական հիպերխորանարդի տարածքւոմ, որը որոշում է զանգվածի առաջին և վերջին ծայրերը <math>xl</math> և  <math>xu</math>, որոնցից ամենքի չափսերը <math>dim</math>. Ինտեգրացիան օգտագործում է ֆունկցիայի կանչերի ֆունկցիոնաալ քանակը և ստանում է պատահական ընտրանքի կետերը պատահական թվերի գեներատորի միջոցով <math>r</math>. Աշխատանքային մասից ուղղարկված այս  <math>s</math> պետքէ ներկայացվի: Արդյունքում վերադառնում է ինտեգրացիայի արդյունքը  <math>result</math> արժեքով,  բացարձակ սխալով <math>abserr</math>.Արդյունքը և նրա գնահատականի սխալը հիմնված են կշռվախ անկախ ընտրանքի վրա: Խի քառակուսին ազատության աստիճանի համար միջինում վերադառնում է գլխավոր բաղադրիչի կառուցվածքով, <math>s\to chisq</math>, և պետք է համաձայնացված լինեն 1-ի հետ Որպեսզի միջին կշռվածը լինի հուսալի: 

VEGAS  ալգորիթմը հաշվում է անկախ գնահատականների բաժանել մի շարքով, ըստ ստորեւ նկարագրված մտադրված պարամետրի, և  վերադարձնում է իրենց միջին կշիռը. Պատահական ընտրանքի  ինտեգրալը կարող է երբեմն արտադրել  նախահաշիվը, եթե սխալ է- զրոյական, հատկապես եթե այդ գործառույթը հաստատուն է  որոշ ռեգիոններում. Նախահաշիվը զրոյական սխալի պատճառ է դառնում, որի միջին կշիռը ներքեւ է եւ պետք է վարվել  առանձին. Օրիգինալ Fortran  VEGAS կատարումն է, որ սխալ է գնահատում  ոչ զրոյական մի փոքր արժեքի փոխարինման կողմից (սովորաբար 1e-30). Ծրագրի իրականացման դեպքում GSL  տարբերվում է և  խուսափում է օգտագործել կամայական հաստատուն -- դա էլ նշանակում արժեքի մի քաշ, որը նախորդ գնահատականների միջին քաշն է, կամ  հետաձգել այն  հետեւյալ կարգով:

* '''Միջին գնահատականը զրոյական սխալ է, միջին կշռվածը վերջավոր սխալի է ''' <br> Ընթացիկ նախահաշիվը`նշանակվում է մի քաշ, որի միջին քաշը նախորդ գնահատականներով է..
* '''Միջին գնահատականը  վերջավոր սխալի  է, նախորդ գնահատականները  զրոյական սխալի են <br> Նախորդ գնահատականները  անտեսվել են ու կշռված միջին ընթացակարգը սկսվում է ընթացիկ գնահատականներով.
* '''Միջին գնահատականը զրոյական սխալի է, նախորդ գնահատականները զրոյական սխալի են'''  <br> Օգտագործելով  գնահատականների  միջին թվաբանությունը նշանակում է, սակայն սխալ է հաշվարկվում.

=== Ուրվագծված պարամետրեր ===

VEGAS  ալգորիթմը ուրվագծված է

==== chisq ====
Այս պարամետրը տալիս  է 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. 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]]