Search
سایتی برای معرفی نظریه ها و الگوریتم های محاسباتی
صفحه اصلی روش ها و الگوریتم ها انتگرال گیری مونت کارلو و مونت کارلوی کوانتومی وردشی

انتگرال گیری مونت کارلو و مونت کارلوی کوانتومی وردشی

مهر ۰۴, ۱۳۹۵روش ها و الگوریتم ها 0

2

در واقع واژهی مونت کارلو از نام یک بازی قمار که در شهر موناکو فرانسه رایج بوده است، گرفته شده است. روش مونت کارلو راه حلی عددی بر پایهی تولید اعداد کاتورهای برای شبیهسازی برهمکنش اشیا با محیط یا اشیا با یکدیگر ارائه میکند. برای نخستین بار بوفن در سال 1777 با استفاده از روش مونت کارلو عدد را به دست آورد. پیش از این نیز بسیاری از مسایل آماری به وسیلهی نمونهگیریهای کاتوره‌ای و در واقع روش مونت کارلو حل میشد. با پیدایش کامپیوترها و پیشرفت محاسبات رایانهای استفاده از شبیهسازیهای مونت کارلو در دانشهای گوناگون از جایگاه ویژهای برخوردار شد و در حوزهی گستردهای از دانش از جمله بررسی رشد جمعیت، اقتصاد، شار ترافیک، شیمی کوانتومی و …، کاربرد یافتند. بسیاری از محاسبات و حل انتگرالهای پیچیده در مطالعهی مسایل فیزیک مدیون روشهای مونت کارلو هستند.
در این گفتار به بررسی روشهای انتگرالگیری مونت کارلو و الگوریتم متروپلیس به عنوان روشی برای تولید اعداد کاتورهای از یک تابع توزیع دلخواه، میپردازیم.

1- انتگرالگیریهای مونت کارلو

روش های مونت کارلو به محاسبه انتگرال هایی می پردازد که محاسبه آنها به صورت تحلیلی امکان پذیر نیست. تمام روشهای انتگرالگیری مونت کارلو بر پایهی تولید اعداد کاتورهای به محاسبهی انتگرال میپردازد. در زیر به کوتاهی برخی از روشهای انتگرال-گیری را مرور میکنیم.

1-1 روش برخورد یا خطا

ساده ترین روش انتگرالگیری مونت کارلو روشی موسوم به روش بر خورد یا خطا است. شکل1 را در نظر بگیرید،

fx
شکل1 تابع f\left( x \right) که در مستطیل با طول (b-a ) و عرض H قرار گرفته است. S، سطح رنگشده مساحت زیر نمودار و جواب انتگرالگیری از تابع f\left( x \right) است.

در واقع حل انتگرال محاسبه مساحت زیر تابع f\left( x \right) است. مستطیل با عرض H و طول ( b-a) طوری در نظر گرفته شده است که تابع داخل آن تعریف شده باشد . N زوج کاتوره‌ای \left( {{x_i},{y_i}} \right) با شرط a \le {x_i} \le b و 0 \le {y_i} \le H تولید میکنیم. کسری از نقاط \left( {{x_i},{y_i}} \right) که {y_i} \le f\left( x \right) تخمینی از نسبت مساحت مستطیل به مساحت زیر تابع (انتگرال f\left( x \right)) میباشد. بنابراین مقدار تقریبی انتگرال را می توان به صورت زیر نوشت:

(1)   \begin{equation*} I = \int_a^b {f\left( x \right)} dx \cong S\frac{{N'}}{N} \end{equation*}

که N' شمار نقاطی است که شرط {y_i} \le f\left( x \right) را برآورده میکند و S مساحت زیر نمودار را نشان میدهد. روش برخورد و خطا را به آسانی می توان به فضای چند بعدی گسترش داد و تخمینی از حجم یک جسم نیز به دست آورد.

2-1 روش مقدار میانگین

با توجه به قضیه مقدار میانگین می توانیم انتگرال (1) را به صورت زیر بنویسیم:

(2)   \begin{equation*} {I_N} = \frac{{\left( {b - a} \right)}}{N}\sum\limits_{i = 1}^N {f\left( {{x_i}} \right)} \end{equation*}

که {x_i} ها اعداد کاتورهای در بازه ی \left[ {a,b} \right] هستند. اگر شمار {x_i} ها، N، به اندازه کافی بزرگ باشد، {I_N} به جواب دقیق انتگرال نزدیکتر می شود. این رابطه مشابه روش ذوزنقه ای می باشد با این تفاوت که در روش ذوزنقه ای {x_i} ها با فواصل یکسان گزیده میشوند. در روش های معمول انتگرالگیری با افزایش بعد انتگرال( d)، خطای محاسبات افزایش مییابد درحالیکه در روش مونت کارلو خطا متناسب با \frac{1}{{\sqrt d }} است. از این رو روش های انتگرال گیری مونت در محاسبهی انتگرالهای چندگانه نسبت به سایر روشهای انتگرالگیری برتری قابل توجهی دارد.

3-1 نمونه گیری با اهمیت

خطای محاسبات مونت کارلو متناسب با \sigma (انحراف میانگین نمونه ها) و وارون مجذور N(شمار نمونه گیری ها) میباشد. از اینرو میتوان با کاهش واریانس و یا افزایش شمار نقاط نمونه گیری خطای انتگرالگیری در روش مونت کارلو را کاهش داد. روشهای نمونهگیری با اهمیت با کاهش \sigma، کارایی محاسبات مونت کارلو را افزایش میدهند. در زیر این روش را توضیح میدهیم.
تابع مثبت p\left( x \right) را در نظر بگیرید به طوری که

(3)   \begin{equation*} \int_a^b {p\left( x \right)dx = 1} \end{equation*}

می توان انتگرال (1) را به صورت زیر بازنویسی کرد:

(4)   \begin{equation*} F = \int_a^b {g\left( x \right)p\left( x \right)dx} \end{equation*}

که g\left( x \right) = \frac{{f\left( x \right)}}{{p\left( x \right)}} است. انتگرال رابطه ی (4)، با N نمونه گیری از تابع توزیع p\left( x \right) با محاسبه مجموع زیر به دست می آید:

(5)   \begin{equation*} ${F_n} = \frac{1}{n}\sum\limits_{i = 1}^n {g\left( {{x_i}} \right)}$ \end{equation*}

واضح است که با گزیدن p\left( x \right) = \frac{1}{{b - a}}، رابطه ی (5)، به رابطه ی (2)، تبدیل میشود. تابع p\left( x \right) باید به گونهای باشد که واریانس نسبت \left[ {{{f\left( x \right)} \mathord{\left/ {\vphantom {{f\left( x \right)} {p\left( x \right)}}} \right. \kern-\nulldelimiterspace} {p\left( x \right)}}} \right] را کمینه کند. (بهترین گزینه برای تابع p\left( x \right) میتواند به صورت \left| {{{f\left( x \right)} \mathord{\left/ {\vphantom {{f\left( x \right)} {p\left( x \right)}}} \right. \kern-\nulldelimiterspace} {p\left( x \right)}}} \right| باشد. اکنون نتیجه ی انتگرالگیری بسیار بهتر است، اگرچه میزان خطای مونت کارلو هنوز متناسب با \frac{\sigma }{{\sqrt n }} میباشد.

2-1 الگوریتم متروپولیس

الگوریتم متروپولیس روشی برای تولید نقاط از یک تابع توزیع نایکنواخت است که توسط متروپولیس و همکارانش در سال 1953 ارائه شد. در واقع الگوریتم متروپولیس یک فرایند نمونه گیری با اهمیت است که برای محاسبهی میانگینهایی به شکل

(6)   \begin{equation*} < f > = \frac{{\int {f\left( x \right)p\left( x \right)dx} }}{{\int {p\left( x \right)dx} }} \end{equation*}

مفید است. در رابطهی(6)، p\left( x \right) تابعی است اختیاری، که لازم نیست بهنجار شده باشد. برای سادگی، الگوریتم متروپولیس را در حل یک انتگرال یک بعدی بررسی می کنیم. فرض کنیم که مایل هستیم از نمونه گیری با اهمیت برای تولید متغیرهای کاتورهای با توزیع p\left( x \right) استفاده کنیم. الگوریتم متروپولیس یک ولگشت کاتورهای از نقاط \{ {x_i}\} با تابع توزیع احتمال p\left( x \right) تولید می کند. یک ولگشت کاتورهای با احتمال گذار T\left( {{x_i} \to {x_j}} \right) از نقطه ی {x_i} به نقطه ی {x_j} طوری که توزیع نقاط {x_0},{x_1},... به تابع p\left( x \right) همگرا شود مشخص میشود. برای رسیدن به این امر تنها کافی است (بایسته نیست) که شرط تعادل جزئی برآورده شود:

(7)   \begin{equation*} P\left( {{x_i}} \right)T\left( {{x_i} \to {x_j}} \right) = P\left( {{x_j}} \right)T\left( {{x_j} \to {x_i}} \right) \end{equation*}

در رابطهی(7)، T\left( {{x_i} \to {x_j}} \right) یکتا نیست. یک گزینش ساده می تواند به صورت زیر باشد :

(8)   \begin{equation*} T\left( {{x_i} \to {x_j}} \right) = \min \left[ {1,\frac{{P\left( {{x_j}} \right)}}{{P\left( {{x_i}} \right)}}} \right] \end{equation*}

اگر در ولگشت در نقطه ی {x_i} باشیم، برای تولید نقطه ی {x_{i + 1}} میتوانیم با گزینش T\left( {{x_i} \to {x_j}} \right) از رابطهی (8) مطابق الگوریتم زیر پیش برویم:
1- گزینش موقعیت آزمایشی {x_{trial}} = {x_i} + {\delta _i}، که {\delta _i} یک عدد کاتورهای در بازه ی \left[ { - \delta ,\delta } \right] است .
2- محاسبه ی w = \frac{{P\left( {{x_{trial}}} \right)}}{{P\left( {{x_i}} \right)}}
3- اگر w \ge 1، جابجایی اعمالشده را میپذیریم و ، {x_{i + 1}} = {x_{trial}} قرار میدهیم.
4- اگر w < 1، عدد کاتوره ای r را تولید میکنیم.
5- اگر r \le w، دوباره این تغییر را میپذیریم و {x_{i + 1}} = {x_{trial}}، قرار میدهیم .
6- اگر در طی مراحل بالا تغییر آزمایشی پذیرفته نشد، آنگاه اجازه میدهیم تا {x_{i + 1}} = {x_i}، باشد.
برای آنکه توزیع احتمال نقاط تولید شده به سوی p\left( x \right) میل کند باید در دستگاه تعادل برقرار شود. بنابراین لازم است شمار زیادی نقطه کاتورهای مطابق الگوریتم بالا تولید کنیم. اگر مقدار \delta (گام مونت کارلو) در الگوریتم متروپلیس بسیار بزرگ باشد تنها درصد بسیار کمی از گام های آزمایشی پذیرفته میشود از این رو به نمونه گیری درستی از تابع p\left( x \right) نمیرسیم. از طرف دیگر با گزینش \delta بسیار کوچک درصد زیادی از گام های آزمایشی پذیرفته میشود اما این بار نیز نمونه گیری خوبی از تابع p\left( x \right) صورت نگرفته است.
یک معیار گزینش اندازه ی \delta وقتی است که تقریباً یکسوم تا نصف گامهای آزمایشی مورد پذیرش قرار گیرد. همچنین باید مقدار {x_0} (نخستین نقطه آزمایشی) به گونهای گزینش شود که توزیع \left\{ {{x_i}} \right\} تندتر به سوی توزیع مورد نظر میل کند. واضح است که بهترین گزینش برای {x_0}، این است که ولگشت در بیشینه مقدار تابع p\left( x \right) باشد.

 
TAG
مطلب قبلیمونت کارلوی کوانتومی وردشی

بنده دانشجوی دکترای فیزیک ماده چگال از دانشگاه تربیت مدرس تهران هستم. حوزه مورد علاقه من فیزیک محاسباتی (به طور خاص نظریه تابعیت چگالی) و همچنین سیستم های توپولوژیک است.

مطالب مرتبط

There are no comments yet

  • سلام , مهمان
  • خروج
  • ورود

    Or use one of these social networks

کانال و گروه تلگرام

برای اینکه همیشه در جریان اخبار باشید و از رویدادها جا نمانید، تازه ترین اخبار و آموزش‌ها را در کانال تلگرام فیزیک محاسباتی دنبال کنید. تلگرام برای بحث و گفت و گو پیرامون کدهای محاسباتی و تئوری های مربوطه می توانید عضوگروه تلگرام فیزیک محاسباتی در تلگرام شوید. گروه تلگرام

شبکه های اجتماعی

گردونه مطالب

برندگان جایزه نوبل فیزیک 2017 معرفی شدند

ضرایب اسلیتر کوستر

اثر هال کوانتومی

دانشمندان برای اولین بار در تاریخ، در دمای اتاق به نور مایع دست یافتند

آموزش نصب سریع کد محاسباتی OpenMX

  • سجاد حمره

    نرم افزار Vnl در این زمینه خیلی خوبه. پست آخری که گذاشتم هم در مورد چگونگی بدست آوردن لایس...

  • سجاد حمره

    سلام وقت شما بخیر آموزش خیلی نرم افزار ها توی سایت موجوده. شما دقیقا چی مد نظرتون هست؟...

  • سجاد حمره

    سلام و درود میشه یکم بیشتر توضیح بدید با این توضیحات هیچ حرفی نمیشه زد...

  • ابراهیمی

    با سلام در صورت امکان در مورد اموزش ترم افزار کوانتوم اسپرسو یا دیگر نرم افزارهای فیزیک حا...

مطالب اخیر

اخبار
6

برندگان جایزه نوبل فیزیک 2017 معرفی شدند

مهر ۱۱, ۱۳۹۶

جایزه نوبل فیزیک 2017 به طور مشترک به راینر ویس،بری سی بریش و کیپ اس تورن اعطا شد.  این سه...

This site is protected by wp-copyrightpro.com