მონტე კარლოს ინტეგრირება

Monte Carlo Integration

სურათი ასახავს მონტე კარლოს მეთოდს მუშაობის პროცესში. შერჩევა ხდება წრეწირის მეოთხედში ცდების რაოდენობის გაზრდა იწვევს სიზუსტის გაზრდას.

        მონტე კარლოს ინტეგრირება არის რიცხვითი ინტეგრირების მეთოდი რომელიც შემთხვევითი რიცხვების შერჩევის გამოყენებით ხსნის სასრულ ინტეგრალს. ამ მეთოდს განსაკუთრებით დიდი გამოყენება აქვს მაღალი განზომილების ინტეგრალების ამოხსნისას.
        მონტე კარლოს მეთოდი გამოირჩევა არადეტერმინისტული მუშაობის პრინციპით რაც იმაში გამოიხატება, რომ ერთი და იგივე შემომავალ პარამეტრზე მეთოდი იღებს სხვადასხვა შედეგებს. მართალია სასრული ინტეგრალის გამოთვლისას პასუხი არის ცალსახა და სასრული, თუმცა მონტე კარლოს მეთოდი იძლევა ინტეგრალს სასურველი მიახლოებით. მოვიყვანოთ მაგალითი: ვთქვათ გვინდა დავთვალოთ Pi-ს რიცხვითი მნიშვნელობა სასურველი მიახლოვებით.

        წარმოვიდგინოთ კვადრატი რომელშიც არის ჩახაზული წრეწირი(იხილეთ სურათი).  ვქვათ ამ კვადრატში ვსვავთ თანაბრად განაწილებულ შემთხვევით წერტილებს რომელთაგან ნაწილი მოხვდება წრეწირს შიგნით(წითელი წერტილები), ხოლო ნაწილი გარეთ(ლურჯი წერტილები). რადგან ჩვენ ვაკეთებთ თანაბარ შერჩევას ვიცით რომ, რაც უფრო გავზრდით შერჩევების რაოდენობას მით უფრო თანაბარი გახდება განაწილება. ასეთ შემთხვევაში შეგვიძლია ვთქვათ, რომ წრეწირში ჩავარდნილი წერტილების რაოდენობის შეფარდება საერთო რაოდენობასთან იქნება იგივე რაც წრეწირის ფართობის შეფარდება კვადრატის ფართობთან. ჩვენ ვიცით, რომ წრეწირის ფართობი არის Pi*(r^2), ხოლო კვადრატის (2*r)^2. ვიღებთ: (წითლების რაოდენობა)/(საერთო რაოდენობა) = Pi*(r^2)/4*(r^2) = Pi/4; აქედან Pi = ((წითლების რაოდენობა)*4)/(საერთო რაოდენობა). საერთო რაოდენობა ჩვენთვის ცნობილი პარამეტრია და ვარჩევთ იმის მიხედვით თუ რა სიზუსტით გვსურს პასუხთან მიახლოება. ასევე ცნობილია წრეწირში ჩავარდნილი წერტილების რაოდენობა(ყოველი ახალი წერტილის შერჩევისას ვამოწმებთ წრეწირში ჩავარდა წერტილი თუ არა). უფრო მეტი სიცხადისთვის მოვიყვანოთ პროგრამული მაგალითი:

#include <stdio.h>
#include <stdlib.h>

#define RADIUS 1.0

struct sample2D
{
    sample2D( double _x, double _y )
    {
        x = _x;
        y = _y;
    }
    double x;
    double y;
};

bool IsInsideCircle( const sample2D& s, double r )
{
    return ( sqrt( s.x*s.x + s.y*s.y ) <  r );
}

double GetRandom( double minValue, double maxValue )
{
    return minValue + ( rand()/((double)RAND_MAX) )*( maxValue - minValue );
}

double GetPi( unsigned int n )
{
    unsigned int withinCircle = 0; //წრეწირში ჩავადრნილი წერტილების რაოდენობა

    for ( unsigned int i=0; i<n; i++ ) //ვახდენთ n ცალ შერჩევას
    {
        //შევარჩიოთ შემთხვევითი წერტილი კვადრატში
        sample2D sample( GetRandom( -RADIUS, RADIUS ), GetRandom( -RADIUS, RADIUS ) );

        //თუ ეს წერტილი არის წრეწირში, გავზარდოთ მთვლელი
        if( IsInsideCircle( sample, RADIUS ) )
            withinCircle++;
    }

    return (withinCircle*4)/((double)n);
}

int main()
{
    printf( "%f", GetPi(1000000) );
    return 0;
}

       პროგრამული კოდი მოყვანილია C++-ზე. ფუნქცია double GetPi( unsigned int n ) ითვლის Pi-ს რიცხვით მნიშვნელობას. სიზუსტის გაზრდა ხდება შერჩევების რაოდენობის(n) გაზრდით. რეალურად Pi-ს გამოთვლის ამოცანებში მონტე კარლო ძალიან იშვიათად გამოიყენება თუმცა კარგად ასახავს ამ მეთოდის მუშაობის პრინციპს.