Skip to main content

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

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-ს გამოთვლის ამოცანებში მონტე კარლო ძალიან იშვიათად გამოიყენება თუმცა კარგად ასახავს ამ მეთოდის მუშაობის პრინციპს.

Comments

Popular posts from this blog

რუსული რულეტკის მეთოდი

Russian Roulette Technique რუსული რულეტკის მეთოდი არის ფართოდ გავრცელებული ტექნიკა მონტე-კარლოს ინტეგრირების პროცესის შესაწყვეტად(სახელწოდება მოდის ცნობილი რუსული თამაშიდან). იმის მაგივრად, რომ პროცესი შევწყვითოთ ხისტად, მაგალითად შერჩევების რაოდენობის რაიმე მაქსიმალურ რაოდენობაზე, რუსული რულექტკის მეთოდი გვეხმარება ინტეგრირების პროცესის მიუკერძოვებლად შეწყვეტაში. მთავარი იდეა რუსული რულეტკის მეთოდისა არის ის, რომ რუსული რულეტკა წყვეტს მონტე კარლოს მეთოდს რაიმე არანულოვანი p ალბათობით(ალბათობა შეიზლება შეირჩეს ერთხელ ან მონტე კარლოს მეთოდის ყოველ ბიჯზე სათითაოდ რაიმე მნიშვნელოვნობით) ან აგრძელებს მას და შემდგომი პროცესიდან მიღებულ შედეგს ამრავლებს 1/p - ზე. რადგან რუსული რულეტკის მეთოდი პროცესის შეწყვეტას ახდენს რაიმე არანულოვანი p ალბათობით ყოველთვის რჩება იმის შანსი, რომ პროცესი გაგრძელდეს რაც იმას ნიშნავს, რომ მონტე კარლოს ინტეგრირების პროცესისათვის ნებისმიერი სიღრმე მიღწევადი ხდება. სწორედ ამიტომ ხისტი შეზღუდვით მიღებული მიკერძოება( სისტემატიური შეცდომა ) ქრება რუსული რ...

ფერების RGB მოდელი

RGB Color Model         ფერების RGB მოდელი წარმოადგენს ისეთ მოდელს რომელშიც სამი ძრირითადი ფერის წითელი, მწვანე და ლურჯის საშუალებით მიიღება ფერების ფართო სპექტრი. მისი დასახელებაც მოდის სწორედ ძირითადი ფერების ინგლისური სახელწოდების ინიციალებიდან(Red, Green, Blue).         ფერთა სპექტრის ამდაგვარი წარმოდგენა დაკავშირებულია იმასთან, რომ გამოსახულების გამოტანის მოწყობილობებში რომელიც გააჩნიათ კომპიუტერებს, ტელევიზორებს ფერის მიღება ფიზიკურად ხდება სწორედ ამ სამი ძირითადი ფერის შეზავებით. დღესდღეობით ყველაზე გავრცელებული არის 24 ბიტიანი RGB მოდელი, სადაც თითოეულ კომპონენტს ეთმობა ერთი ბაიტი და შესაბამისად შეუძლია მიიღოს ნებისმიერი მნიშვნელობა [0, 255] დიაპაზონში, რაც საბოლოოდ გვაძლევს 16777216 განსხვავებულ ფერს.

ბეზიეს წირი

Bezier Curve         ბეზიეს წირები ფართოდ გამოიყენება კომპიუტერული მეცნიერების სხვადასხვა მიმართულებებში  CAD  სისტემებში, კომპიუტერულ გრაფიკაში და ა.შ. ისისნი პოპულარობით სარგებლობენ მისი სიმარტივის, ინტუიტიურობის და მოსახერხებულობის გამო.         მათემატიკურად ბეზიეს წირი არის ფუნქცია რომელსაც გადაეცემა ერთი პარამეტრი t(0-დან 1-მდე) და ის გვიბრუნებს წერტილს წირზე. ფუნქციის მნიშვნელობა დამოკიდებულია შემავალ t პარამეტრზე და n ცალ წერტილზე, რომლიდანაც პირველ და ბოლო წერტილს ვუწოდებთ კვანძებს(knots), ხოლო დანარჩენებს საკონტროლო წერტილებს(Control points). როდესაც t=0 ფუნქცია გვიბრუნებს პირველ კვანძს, როდესაც t=1 ფუნქცია გვიბრუნებს მეორე კვანძს, დანარჩენ მნიშვნელობებზე ფუნქცია გვიბრუნებს წირის სხვა წერტილებს. გამოდის რომ წირი იწყება პირველი კვანძში დამოკიდებულია საკონტროლო წერტილებზე,თუმცა არ გადის მათზე და სრულდება მეორე კვანძში. მათემატიკურად ნებისმიერ ბეზიეს წირს შეესაბამება პოლინომი რომლის ხარისხიც არის მოცემული წერტილების რაოდენობ...