تكامل مونت كارلو

📅 آخر تحديث: ١٩ يوليو ٢٠٢٦
✍️ نُشر في: ١٩ يوليو ٢٠٢٦
📷 يحتوي على 34 صور
الموسوعة الحرة
مثال توضيحي لتكامل مونت كارلو. في هذا المثال، المجال D هو الدائرة الداخلية، والمجال E هو المربع. بما أن مساحة المربع (4) يمكن حسابها بسهولة، يمكن تقدير مساحة الدائرة (π × 1.0² ) بنسبة (0.8) عدد النقاط داخل الدائرة (40) إلى العدد الإجمالي للنقاط (50)، مما يعطي قيمة تقريبية لمساحة الدائرة تساوي 4 × 0.8 = 3.2 ≈ π.

في الرياضيات ، يُعدّ تكامل مونت كارلو أسلوبًا للتكامل العددي باستخدام الأرقام العشوائية . وهو طريقة خاصة من طرق مونت كارلو لحساب التكامل المحدد عدديًا . بينما تُقيّم الخوارزميات الأخرى عادةً الدالة المراد تكاملها على شبكة منتظمة، [ 1 ] يختار مونت كارلو عشوائيًا نقاطًا لتقييم الدالة المراد تكاملها. [ 2 ] تُعدّ هذه الطريقة مفيدة بشكل خاص للتكاملات ذات الأبعاد المتعددة. [ 3 ]

توجد طرق مختلفة لإجراء عملية تكامل مونت كارلو، مثل أخذ العينات المنتظم ، وأخذ العينات الطبقية ، وأخذ العينات المهمة ، ومونت كارلو التسلسلي (المعروف أيضًا باسم مرشح الجسيمات)، وطرق الجسيمات ذات المجال المتوسط .

ملخص

في التكامل العددي، تستخدم طرق مثل قاعدة شبه المنحرف منهجًا حتميًا . أما تكامل مونت كارلو، فيستخدم منهجًا غير حتمي : إذ تُنتج كل عملية محاكاة نتيجة مختلفة. في مونت كارلو، تكون النتيجة النهائية تقريبًا للقيمة الصحيحة مع هامش خطأ مناسب، ومن المرجح أن تقع القيمة الصحيحة ضمن هذا الهامش.

تتمثل المشكلة التي يعالجها تكامل مونت كارلو في حساب التكامل المحدد متعدد الأبعادأنا=∫Ωو(x¯)دx¯{\displaystyle I=\int _{\Omega }f({\overline {\mathbf {x} }})\,d{\overline {\mathbf {x} }}} حيث Ω، مجموعة جزئية منRم{\displaystyle \mathbb {R} ^{m}}، له حجم V=∫Ωدx¯{\displaystyle V=\int _{\Omega }d{\overline {\mathbf {x} }}}

تتمثل طريقة مونت كارلو البسيطة في أخذ عينات من النقاط بشكل منتظم على Ω: [ 4 ] بالنظر إلى N عينة منتظمة، x¯1،⋯،x¯شمال∈Ω،{\displaystyle {\overline {\mathbf {x} }}_{1},\cdots ,{\overline {\mathbf {x} }}_{N}\in \Omega ,}

يمكن تقريبي بواسطة أنا≈سؤالشمال≡V1شمال∑أنا=1شمالو(x¯أنا)=V⟨و⟩.{\displaystyle I\approx Q_{N}\equiv V{\frac {1}{N}}\sum _{i=1}^{N}f({\overline {\mathbf {x} }}_{i})=V\langle f\rangle .}

وذلك لأن قانون الأعداد الكبيرة يضمن أن ليمشمال→∞سؤالشمال=أنا.{\displaystyle \lim _{N\to \infty }Q_{N}=I.}

بالنظر إلى تقدير I من Q N ، يمكن تقدير أشرطة الخطأ لـ Q N بواسطة تباين العينة باستخدام التقدير غير المتحيز للتباين .

Vأر(و)=هـ(σشمال2)≡1شمال-1∑أنا=1شمالهـ[(و(x¯أنا)-⟨و⟩)2].{\displaystyle \mathrm {Var} (f)=\mathrm {E} (\sigma _{N}^{2})\equiv {\frac {1}{N-1}}\sum _{i=1}^{N}\mathrm {E} \left[\left(f({\overline {\mathbf {x} }}_{i})-\langle f\rangle \يمين)^{2}\يمين].} مما يؤدي إلى Vأر(سؤالشمال)=V2شمال2∑أنا=1شمالVأر(و)=V2Vأر(و)شمال=V2هـ(σشمال2)شمال.{\displaystyle \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 {\mathrm {E} (\sigma) _{N}^{2})}{N}}.}

بما أن التسلسل {هـ(σ12)،هـ(σ22)،هـ(σ32)،...}{\displaystyle \left\{\mathrm {E} (\sigma _{1}^{2})،\mathrm {E} (\sigma _{2}^{2})،\mathrm {E} (\sigma _{3}^{2})،\ldots \right\}} تكون هذه القيمة محدودة لأنها تساوي Var(f) تمامًا ، وطالما افترضنا أن هذه القيمة محدودة، فإن هذا التباين يتناقص تقاربًا إلى الصفر كـ 1/ N . وبالتالي، فإن تقدير خطأ Q N يكوندلتاسؤالشمال≈Vأر(سؤالشمال)=VVأر(و)شمال،{\displaystyle \delta Q_{N}\approx {\sqrt {\mathrm {Var} (Q_{N})}}=V{\frac {\sqrt {\mathrm {Var} (f)}}{\sqrt {N}}},} والذي يتناقص مع1شمال{\displaystyle {\tfrac {1}{\sqrt {N}}}}هذا هو الخطأ المعياري للمتوسط ​​مضروبًا فيV{\displaystyle V}لا تعتمد هذه النتيجة على عدد أبعاد التكامل، وهي الميزة الموعودة لتكامل مونت كارلو مقارنةً بمعظم الطرق الحتمية التي تعتمد أُسّيًا على البُعد. [ 5 ] من المهم ملاحظة أنه، على عكس الطرق الحتمية، فإن تقدير الخطأ ليس حدًا دقيقًا للخطأ؛ فقد لا تكشف العينات العشوائية عن جميع السمات المهمة للدالة المُكاملة، مما قد يؤدي إلى التقليل من قيمة الخطأ.

بينما تُجدي طريقة مونت كارلو البسيطة نفعًا مع الأمثلة البسيطة، لا يُمكن تحقيق تحسينٍ يُضاهي الخوارزميات الحتمية إلا باستخدام خوارزميات تعتمد على توزيعات معاينة مُخصصة للمسألة. مع توزيع معاينة مناسب، يُمكن استغلال حقيقة أن جميع الدوال التكاملية ذات الأبعاد الأعلى تقريبًا مُتمركزة للغاية، وأن مساحة فرعية صغيرة فقط تُساهم بشكلٍ ملحوظ في التكامل. [ 6 ] يُكرّس جزء كبير من أدبيات مونت كارلو لتطوير استراتيجيات لتحسين تقديرات الخطأ. على وجه الخصوص، تُعدّ المعاينة الطبقية - تقسيم المنطقة إلى نطاقات فرعية - والمعاينة المهمة - المعاينة من توزيعات غير منتظمة - مثالين على هذه التقنيات.

مثال

الخطأ النسبي كدالة لعدد العينات، مما يوضح عملية القياس1شمال{\displaystyle {\tfrac {1}{\sqrt {N}}}}

يُعد تقدير قيمة π مثالًا نموذجيًا على تكامل مونت كارلو. لنفترض الدالة ح(x،y)={1لو x2+y2≤10آخر{\displaystyle H\left(x,y\right)={\begin{cases}1&{\text{if }}x^{2}+y^{2}\leq 1\\0&{\text{else}}\end{cases}}} والمجموعة Ω = [−1,1] × [−1,1] حيث V = 4. لاحظ أن أناπ=∫Ωح(x،y)دxدy=π.{\displaystyle I_{\pi }=\int _{\Omega }H(x,y)dxdy=\pi .}

وبالتالي، فإن إحدى الطرق التقريبية لحساب قيمة π باستخدام تكامل مونت كارلو هي اختيار N عددًا عشوائيًا على Ω وحساب سؤالشمال=41شمال∑أنا=1شمالح(xأنا،yأنا){\displaystyle Q_{N}=4{\frac {1}{N}}\sum _{i=1}^{N}H(x_{i},y_{i})}

في الشكل الموجود على اليمين، الخطأ النسبيسؤالشمال-ππ{\displaystyle {\tfrac {Q_{N}-\pi }{\pi }}} يتم قياسها كدالة لـ N ، مما يؤكد1شمال{\displaystyle {\tfrac {1}{\sqrt {N}}}}.

مثال C/C++

#include <stdio.h> #include <stdlib.h> #include <time.h> int main () { // تهيئة عدد العدّات إلى 0، وتعيين العدد الإجمالي إلى 100000 في الحلقة. int throws = 99999 , insideCircle = 0 ; double randX , randY , pi ;srand ( time ( NULL ));// يتحقق من كل زوج عشوائي من x و y ما إذا كانا داخل دائرة نصف قطرها 1. for ( int i = 0 ; i < throws ; i ++ ) { randX = rand () / ( double ) RAND_MAX ; randY = rand () / ( double ) RAND_MAX ; if ( randX * randX + randY * randY < 1 ) { insideCircle ++ ; } }// حساب قيمة باي وطباعتها. باي = 4.0 * داخل الدائرة / throws ; printf ( "%lf \n " , باي ); }

مثال بايثون

تم إنشاؤه باستخدام لغة بايثون .

استيراد numpy كـ nprng = np.random.default_rng ( 0 )​​​​عدد الرميات = 2000، نصف القطر = 1# اختر بيانات X و Y عشوائية متمركزة حول النقطة ( 0,0 ) x = rng.uniform ( -radius , radius , throws ) y = rng.uniform ( -radius , radius , throws )# احسب عدد مرات وجود (x, y ) داخل الدائرة، # وهو ما يحدث عندما يكون جذر ( x² + y²) ≤ نصف القطر. داخل_الدائرة = np.count_nonzero ( np.hypot ( x , y ) ≤ نصف_القطر )# احسب المساحة واطبعها؛ ينبغي أن تقترب من قيمة باي مع ازدياد عدد الرميات. المساحة = ( 2 * نصف القطر ) ** 2 * داخل الدائرة / عدد الرميات. اطبع ( المساحة )

مثال من Wolfram Mathematica

يصف الكود أدناه عملية دمج الوظيفة و(x)=11+سينه⁡(2x)سجل⁡(x)2{\displaystyle f(x)={\frac {1}{1+\sinh(2x)\log(x)^{2}}}} من0.8<x<3{\displaystyle 0.8<x<3}استخدام طريقة مونت كارلو في برنامج Mathematica :

func [ x_ ] := 1 / ( 1 + Sinh [ 2 * x ] * ( سجل [ x ]) ^ 2 );(*أخذ عينة من التوزيع الطبيعي المقتطع لتسريع التقارب*) Distrib [ x_ , average_ , var_ ] := PDF [ NormalDistribution [ average , var ], 1.1 * x - 0.1 ]; n = 10 ; RV = RandomVariate [ TruncatedDistribution [{ 0.8 , 3 }, NormalDistribution [ 1 , 0.399 ]], n ]; Int = 1 / n Total [ func [ RV ] / Distrib [ RV , 1 , 0.399 ]] * Integrate [ Distrib [ x , 1 , 0.399 ], { x , 0.8 , 3 }]NIntegrate [ func [ x ], { x , 0.8 , 3 }] (*قارن مع الإجابة الحقيقية*)

أخذ العينات الطبقية المتكررة

توضيح لأسلوب المعاينة الطبقية المتكررة. في هذا المثال، الدالة: و(x،y)={1x2+y2<10x2+y2≥1{\displaystyle f(x,y)={\begin{cases}1&x^{2}+y^{2}<1\\0&x^{2}+y^{2}\geq 1\end{cases}}} تم دمج الرسم التوضيحي أعلاه ضمن مربع وحدة باستخدام الخوارزمية المقترحة. سُجلت النقاط المأخوذة ورُسمت بيانيًا. من الواضح أن خوارزمية أخذ العينات الطبقية تُركز النقاط في المناطق التي يكون فيها تباين الدالة أكبر ما يمكن.

يُعدّ أخذ العينات الطبقية المتكررة تعميمًا للتكاملات التكيفية أحادية البعد لتشمل التكاملات متعددة الأبعاد. في كل خطوة تكرارية، يُقدّر التكامل والخطأ باستخدام خوارزمية مونت كارلو بسيطة. إذا كان تقدير الخطأ أكبر من الدقة المطلوبة، يُقسّم حجم التكامل إلى أحجام فرعية، ويُطبّق الإجراء بشكل متكرر على هذه الأحجام الفرعية.

لا تُجدي استراتيجية "القسمة على اثنين" المعتادة مع الأبعاد المتعددة، إذ يزداد عدد الأجزاء الفرعية بسرعة كبيرة يصعب تتبعها. بدلاً من ذلك، يُقدّر المرء البُعد الذي يُفترض أن يحقق فيه التقسيم الفرعي أكبر قدر من الأرباح، ثم يُقسّم الحجم على هذا البُعد فقط.

تركز خوارزمية أخذ العينات الطبقية نقاط أخذ العينات في المناطق التي يكون فيها تباين الدالة هو الأكبر، مما يقلل من التباين الكلي ويجعل أخذ العينات أكثر فعالية، كما هو موضح في الرسم التوضيحي.

يطبق روتين MISER الشهير خوارزمية مماثلة.

بيسر مونت كارلو

تعتمد خوارزمية MISER على أخذ العينات الطبقية المتكررة . تهدف هذه التقنية إلى تقليل خطأ التكامل الكلي من خلال تركيز نقاط التكامل في المناطق ذات التباين الأعلى. [ 7 ]

تبدأ فكرة أخذ العينات الطبقية بملاحظة أنه بالنسبة لمنطقتين منفصلتين a و b مع تقديرات مونت كارلو للتكاملهـأ(و){\displaystyle E_{a}(f)}وهـب(و){\displaystyle E_{b}(f)}والتبايناتσأ2(و){\displaystyle \sigma _{a}^{2}(f)}وσب2(و){\displaystyle \sigma _{b}^{2}(f)}، التباين Var( f ) للتقدير المجمع هـ(و)=12(هـأ(و)+هـب(و)){\displaystyle E(f)={\tfrac {1}{2}}\left(E_{a}(f)+E_{b}(f)\right)} يُعطى بواسطة، Vأر(و)=σأ2(و)4شمالأ+σب2(و)4شمالب{\displaystyle \mathrm {Var} (f)={\frac {\sigma _{a}^{2}(f)}{4N_{a}}}+{\frac {\sigma _{b}^{2}(f)}{4N_{b}}}}

يمكن إثبات أن هذا التباين يتم تقليله إلى أدنى حد من خلال توزيع النقاط بحيث، شمالأشمالأ+شمالب=σأσأ+σب{\displaystyle {\frac {N_{a}}{N_{a}+N_{b}}}={\frac {\sigma _{a}}{\sigma _{a}+\sigma _{b}}}}

وبالتالي، يتم الحصول على أصغر تقدير للخطأ عن طريق تخصيص نقاط العينة بما يتناسب مع الانحراف المعياري للدالة في كل منطقة فرعية.

تعتمد خوارزمية MISER على تقسيم منطقة التكامل إلى نصفين على طول أحد محاور الإحداثيات، مما ينتج عنه منطقتان فرعيتان في كل خطوة. يُحدد اتجاه التقسيم بفحص جميع عمليات التقسيم الممكنة (d) واختيار التقسيم الذي يُقلل التباين الكلي للمنطقتين الفرعيتين. يُقدّر التباين في المنطقتين الفرعيتين عن طريق أخذ عينات من جزء من إجمالي عدد النقاط المتاحة في الخطوة الحالية. ثم تُكرر هذه العملية بشكل متكرر لكل من نصفي الفضاء الناتجين عن أفضل عملية تقسيم. تُوزع نقاط العينة المتبقية على المنطقتين الفرعيتين باستخدام الصيغة الخاصة بـ N<sub> a</sub> و N<sub> b</sub> . يستمر هذا التوزيع المتكرر لنقاط التكامل حتى عمق يُحدده المستخدم، حيث تُكامل كل منطقة فرعية باستخدام تقدير مونت كارلو بسيط. تُجمع هذه القيم الفردية وتقديرات أخطائها تصاعديًا للحصول على نتيجة إجمالية وتقدير لخطئها.

أخذ العينات المهمة

توجد مجموعة متنوعة من خوارزميات أخذ العينات المهمة، مثل

خوارزمية أخذ العينات المهمة

تُعدّ معاينة الأهمية أداةً بالغة الأهمية لإجراء تكامل مونت كارلو. [ 3 ] [ 8 ] وتتمثل النتيجة الرئيسية لمعاينة الأهمية في هذه الطريقة في أخذ عينات منتظمة منx¯{\displaystyle {\overline {\mathbf {x} }}}هي حالة خاصة من اختيار أكثر عمومية، حيث يتم سحب العينات من أي توزيعص(x¯){\displaystyle p({\overline {\mathbf {x} }})}الفكرة هي أنص(x¯){\displaystyle p({\overline {\mathbf {x} }})}يمكن اختيارها لتقليل تباين القياس Q N.

لنفترض المثال التالي حيث نرغب في حساب التكامل العددي لدالة غاوسية ، مركزها صفر، وانحرافها المعياري σ = 1، من -1000 إلى 1000. بطبيعة الحال، إذا تم سحب العينات بشكل منتظم على الفترة [-1000، 1000]، فإن جزءًا صغيرًا جدًا منها فقط سيكون ذا أهمية للتكامل. يمكن تحسين ذلك باختيار توزيع مختلف عن التوزيع الذي تم اختيار العينات منه، على سبيل المثال، عن طريق أخذ عينات وفقًا لتوزيع غاوسي مركزه صفر، وانحرافه المعياري σ = 1. بالطبع، يعتمد الاختيار "الصحيح" بشكل كبير على الدالة المراد تكاملها.

بصورة رسمية، بالنظر إلى مجموعة من العينات المختارة من توزيع معين ص(x¯):x¯1،⋯،x¯شمال∈V،{\displaystyle p({\overline {\mathbf {x} }}):\qquad {\overline {\mathbf {x} }}_{1},\cdots ,{\overline {\mathbf {x} }}_{N}\in V,}يتم إعطاء المقدر لـ I بواسطة [ 3 ]سؤالشمال≡1شمال∑أنا=1شمالو(x¯أنا)ص(x¯أنا){\displaystyle Q_{N}\equiv {\frac {1}{N}}\sum _{i=1}^{N}{\frac {f({\overline {\mathbf {x} }}_{i})}{p({\overline {\mathbf {x} }}_{i})}}}

بشكل بديهي، يعني هذا أنه إذا اخترنا عينة معينة ضعف عدد العينات الأخرى، فإننا نعطيها نصف وزن العينات الأخرى. هذا التقدير صالح بطبيعته لأخذ العينات المنتظمة، وهي الحالة التيص(x¯){\displaystyle p({\overline {\mathbf {x} }})}ثابت.

تُعد خوارزمية متروبوليس -هاستينغز واحدة من أكثر الخوارزميات استخدامًا لتوليدx¯{\displaystyle {\overline {\mathbf {x} }}}منص(x¯){\displaystyle p({\overline {\mathbf {x} }})}[ 3 ] وبالتالي توفير طريقة فعالة لحساب التكاملات .

لاس فيغاس مونت كارلو

تقوم خوارزمية VEGAS بتقريب التوزيع الدقيق من خلال إجراء عدد من المرورات على منطقة التكامل، مما يُنشئ المدرج التكراري للدالة f . يُستخدم كل مدرج تكراري لتحديد توزيع المعاينة للمرور التالي. يتقارب هذا الإجراء تقاربًا مقاربًا إلى التوزيع المطلوب. [ 9 ] ولتجنب تزايد عدد خانات المدرج التكراري بمعدل K d ، يتم تقريب التوزيع الاحتمالي بدالة قابلة للفصل. ز(x1،x2،...)=ز1(x1)ز2(x2)...{\displaystyle g(x_{1},x_{2},\ldots )=g_{1}(x_{1})g_{2}(x_{2})\ldots } بحيث يكون عدد الفئات المطلوبة Kd فقط . وهذا يُعادل تحديد مواقع قمم الدالة من إسقاطات الدالة التكاملية على محاور الإحداثيات. وتعتمد كفاءة برنامج VEGAS على صحة هذا الافتراض. وتكون كفاءته في ذروتها عندما تكون مواقع قمم الدالة التكاملية محددة بدقة. وإذا أمكن إعادة كتابة الدالة التكاملية بصيغة قابلة للفصل تقريبًا، فإن ذلك سيزيد من كفاءة التكامل باستخدام VEGAS. يتضمن VEGAS عددًا من الميزات الإضافية، ويجمع بين كلٍ من أخذ العينات الطبقية وأخذ العينات المهمة. [ 9 ]

انظر أيضاً

ملحوظات

مراجع