बहुस्तरीय मोंटे कार्लो विधि: Difference between revisions

From Vigyanwiki
Line 13: Line 13:


== अनुप्रयोग ==
== अनुप्रयोग ==
[[File:Multilevel monte carlo sample paths for an SDE.png|thumb|विभिन्न स्तरों पर एक SDE के नमूना पथ का अनुमान।|सही]]एमएलएमसी के पहले आवेदन का श्रेय माइक जाइल्स को दिया जाता है,<ref>{{cite journal |last=Giles |first=M. B. |date=2008 |title=बहुस्तरीय मोंटे कार्लो पथ सिमुलेशन|journal=Operations Research |volume=56 |issue=3 |pages=607–617|url=https://ora.ox.ac.uk/objects/uuid:d9d28973-94aa-4179-962a-28bcfa8d8f00/datastreams/ATTACHMENT01 |doi=10.1287/opre.1070.0496|citeseerx=10.1.1.121.713 |s2cid=3000492 }}</ref> [[मोंटे कार्लो विकल्प मॉडल|मोंटे कार्लो विकल्प]] प्रारूप के लिए [[स्टोचैस्टिक अंतर समीकरण|प्रसंभाव्य अंतर समीकरण]] के संदर्भ में, यद्यपि, पैरामीट्रिक एकीकरण के संदर्भ में हेनरिक के काम में पहले के निशान मिलते हैं। <ref>{{cite journal |last=Heinrich |first=S. |date=2001 |title=बहुस्तरीय मोंटे कार्लो तरीके|journal=Lecture Notes in Computer Science (Multigrid Methods) |series=Lecture Notes in Computer Science |publisher=Springer |volume=2179 |pages=58–67|doi=10.1007/3-540-45346-6_5 |isbn=978-3-540-43043-8 }}</ref> यहाँ, यादृच्छिक चर <math>G=f(X(T))</math> अदायगी समारोह, और सन्निकटन के अनुक्रम के रूप में जाना जाता है <math>G_\ell</math>, <math>\ell=0,\ldots,L</math> प्रतिरूप  पथ के सन्निकटन का उपयोग करें <math>X(t)</math> समय कदम के साथ <math>h_\ell=2^{-\ell}T</math>.
[[File:Multilevel monte carlo sample paths for an SDE.png|thumb|विभिन्न स्तरों पर एक SDE के नमूना पथ का अनुमान।|सही]]एमएलएमसी के पहले आवेदन का श्रेय माइक जाइल्स को दिया जाता है,<ref>{{cite journal |last=Giles |first=M. B. |date=2008 |title=बहुस्तरीय मोंटे कार्लो पथ सिमुलेशन|journal=Operations Research |volume=56 |issue=3 |pages=607–617|url=https://ora.ox.ac.uk/objects/uuid:d9d28973-94aa-4179-962a-28bcfa8d8f00/datastreams/ATTACHMENT01 |doi=10.1287/opre.1070.0496|citeseerx=10.1.1.121.713 |s2cid=3000492 }}</ref> [[मोंटे कार्लो विकल्प मॉडल|मोंटे कार्लो विकल्प]] प्रारूप के लिए [[स्टोचैस्टिक अंतर समीकरण|प्रसंभाव्य अंतर समीकरण]] के संदर्भ में, यद्यपि, पैरामीट्रिक एकीकरण के संदर्भ में हेनरिक के काम में पहले के निशान मिलते हैं। <ref>{{cite journal |last=Heinrich |first=S. |date=2001 |title=बहुस्तरीय मोंटे कार्लो तरीके|journal=Lecture Notes in Computer Science (Multigrid Methods) |series=Lecture Notes in Computer Science |publisher=Springer |volume=2179 |pages=58–67|doi=10.1007/3-540-45346-6_5 |isbn=978-3-540-43043-8 }}</ref>  


अनिश्चितता परिमाणीकरण (यूक्यू) में समस्याओं के लिए एमएलएमसी का अनुप्रयोग अनुसंधान का एक सक्रिय क्षेत्र है।<ref>{{cite journal |last1=Cliffe |first1=A. |last2=Giles |first2=M. B. |last3=Scheichl |first3=R. |last4=Teckentrup |first4=A.|author4-link=Aretha Teckentrup |date=2011 |title=बहुस्तरीय मोंटे कार्लो के तरीके और रैंडम गुणांक वाले अण्डाकार पीडीई के अनुप्रयोग|journal=Computing and Visualization in Science |volume=14 |issue=1 |pages=3–15|url=http://people.maths.ox.ac.uk/~gilesm/files/cgst.pdf |doi=10.1007/s00791-011-0160-x|s2cid=1687254 }}</ref><ref>{{cite journal |last1=Pisaroni |first1=M. |last2=Nobile |first2=F. B. |last3=Leyland |first3=P. |date=2017 |title=कंप्रेसिबल इनविसिड एरोडायनामिक्स में अनिश्चितता मात्रा के लिए एक निरंतरता बहु स्तरीय मोंटे कार्लो विधि|journal=Computer Methods in Applied Mechanics and Engineering |volume=326 |issue=C |pages=20–50|url=https://pdfs.semanticscholar.org/6dbc/8dde601b1757c42a4c54fa9cfd69317c82c8.pdf |archive-url=https://web.archive.org/web/20180214142033/https://pdfs.semanticscholar.org/6dbc/8dde601b1757c42a4c54fa9cfd69317c82c8.pdf |url-status=dead |archive-date=2018-02-14 |doi=10.1016/j.cma.2017.07.030|s2cid=10379943 }}</ref> इन समस्याओं का एक महत्वपूर्ण प्रोटोटाइपिकल उदाहरण [[आंशिक अंतर समीकरण]] (पीडीई) हैं जो [[स्टोकेस्टिक आंशिक अंतर समीकरण]] के साथ हैं। इस संदर्भ में, यादृच्छिक चर <math>G</math> ब्याज की मात्रा के रूप में जाना जाता है, और सन्निकटन का क्रम अलग-अलग जाल आकारों के साथ पीडीई के [[विवेक]] से मेल खाता है।
यहाँ, यादृच्छिक परिवर्तन <math>G=f(X(T))</math> प्रतिफल फ़ंक्शन के रूप में जाना जाता है, और अनुमानों की श्रृंखला <math>G_\ell</math>, <math>\ell=0,\ldots,L</math> समय  सोपान <math>X(t)</math> के साथ प्रतिरूपों के पथ <math>h_\ell=2^{-\ell}T</math>.के एक अनुमान का उपयोग करती है।


== एमएलएमसी अनुकरण के लिए एक एल्गोरिथ्म ==
अनिश्चितता मापन में समस्याओं के लिए एमएलएमसी का अनुप्रयोग एक सक्रिय अनुसंधान क्षेत्र है।<ref>{{cite journal |last1=Cliffe |first1=A. |last2=Giles |first2=M. B. |last3=Scheichl |first3=R. |last4=Teckentrup |first4=A.|author4-link=Aretha Teckentrup |date=2011 |title=बहुस्तरीय मोंटे कार्लो के तरीके और रैंडम गुणांक वाले अण्डाकार पीडीई के अनुप्रयोग|journal=Computing and Visualization in Science |volume=14 |issue=1 |pages=3–15|url=http://people.maths.ox.ac.uk/~gilesm/files/cgst.pdf |doi=10.1007/s00791-011-0160-x|s2cid=1687254 }}</ref><ref>{{cite journal |last1=Pisaroni |first1=M. |last2=Nobile |first2=F. B. |last3=Leyland |first3=P. |date=2017 |title=कंप्रेसिबल इनविसिड एरोडायनामिक्स में अनिश्चितता मात्रा के लिए एक निरंतरता बहु स्तरीय मोंटे कार्लो विधि|journal=Computer Methods in Applied Mechanics and Engineering |volume=326 |issue=C |pages=20–50|url=https://pdfs.semanticscholar.org/6dbc/8dde601b1757c42a4c54fa9cfd69317c82c8.pdf |archive-url=https://web.archive.org/web/20180214142033/https://pdfs.semanticscholar.org/6dbc/8dde601b1757c42a4c54fa9cfd69317c82c8.pdf |url-status=dead |archive-date=2018-02-14 |doi=10.1016/j.cma.2017.07.030|s2cid=10379943 }}</ref> इन समस्याओं का एक महत्वपूर्ण प्रोटोटाइपिकल उदाहरण [[आंशिक अंतर समीकरण|पीडीई]] होते हैं। इस संदर्भ में, यादृच्छिक चर <math>G</math> ये दर्शाता है कि रुचि की मात्रा, और अनुमानों की श्रृंखला पीडीई के ग्रिड आकारों के साथ एक अनुक्रमण को संबंधित करती है।
एमएलएमसी अनुरूपण के लिए एक सरल स्तर-अनुकूली एल्गोरिदम छद्म कोड में नीचे दिया गया है।  
<math>L\gets0</math>
दोहराना
    स्तर पर वार्म-अप के नमूने लें <math>L</math>
सभी स्तरों पर प्रतिरूप  प्रसरण की गणना करें <math>\ell=0,\ldots,L</math>
प्रतिरूपो  की इष्टतम संख्या को परिभाषित करें <math>N_\ell</math> सभी स्तरों पर <math>\ell=0,\ldots,L</math>
प्रत्येक स्तर पर अतिरिक्त नमूने लें <math>\ell</math> के अनुसार <math>N_\ell</math>
अगर <math>L\geq2</math> तब
        अभिसरण के लिए परीक्षण
    अंत
    अगर नहीं मिला तो       
<math>L\gets L+1</math>
अंत
अभिसरण होने तक


== एमएलएमसी अनुकरण के लिए एक कलन-विधि ==
एमएलएमसी अनुरूपण के लिए एक सरल स्तर-अनुकूली कलन-विधि छद्म कोड में नीचे दिया गया है।
    '''repeat'''
    Take warm-up samples at level
    Compute the sample variance on all levels
    Define the optimal number of samples  on all levels
    Take additional samples on each level  according to
    '''if'''  '''then'''
        Test for convergence
    '''end'''
    '''if''' not converged '''then'''
       
    '''end'''
'''until''' converged
== एमएलएमसी का विस्तार ==
== एमएलएमसी का विस्तार ==
बहुस्तरीय मोंटे कार्लो पद्धति के हाल के विस्तार में मल्टी-इंडेक्स मोंटे कार्लो शामिल हैं,<ref>{{cite journal |last1=Haji-Ali |first1=A. L. |last2=Nobile |first2=F. |last3=Tempone |first3=R. |date=2016 |title=Multi-Index Monte Carlo: When Sparsity Meets Sampling |journal=Numerische Mathematik |volume=132 |issue=4 |pages=767–806|doi=10.1007/s00211-015-0734-5|arxiv=1405.3757 |s2cid=253742676 }}</ref> जहां शोधन की एक से अधिक दिशाओं पर विचार किया जाता है, [[क्वासी-मोंटे कार्लो विधि]] पद्धति के साथ एमएलएमसी का संयोजन।<ref>{{cite journal |last1=Giles |first1=M. B. |last2=Waterhouse |first2=B. |date=2009 |title=बहुस्तरीय अर्ध-मोंटे कार्लो पथ अनुकरण|journal=Advanced Financial Modelling, Radon Series on Computational and Applied Mathematics |publisher=De Gruyter |pages=165–181|url=http://people.maths.ox.ac.uk/gilesm/files/jcf07.pdf}}</ref><ref>{{cite journal |last1=Robbe |first1=P. |last2=Nuyens |first2=D. |last3=Vandewalle |first3=S. |date=2017 |title=लॉगनॉर्मल डिफ्यूजन प्रॉब्लम के लिए एक मल्टी-इंडेक्स क्वैसी-मोंटे कार्लो एल्गोरिथम|journal=SIAM Journal on Scientific Computing |volume=39 |issue=5 |pages=A1811–C392|doi=10.1137/16M1082561 |arxiv=1608.03157 |bibcode=2017SJSC...39S.851R |s2cid=42818387 }}</ref>
बहुस्तरीय मोंटे कार्लो पद्धति के हाल के विस्तार में बहु सूचकांक मोंटे कार्लो सम्मिलित हैं,<ref>{{cite journal |last1=Haji-Ali |first1=A. L. |last2=Nobile |first2=F. |last3=Tempone |first3=R. |date=2016 |title=Multi-Index Monte Carlo: When Sparsity Meets Sampling |journal=Numerische Mathematik |volume=132 |issue=4 |pages=767–806|doi=10.1007/s00211-015-0734-5|arxiv=1405.3757 |s2cid=253742676 }}</ref> जहां शोधन की एक से अधिक दिशाओं पर विचार किया जाता है, [[क्वासी-मोंटे कार्लो विधि]] को संगणना के साथ संयोजित किया जाता है।<ref>{{cite journal |last1=Giles |first1=M. B. |last2=Waterhouse |first2=B. |date=2009 |title=बहुस्तरीय अर्ध-मोंटे कार्लो पथ अनुकरण|journal=Advanced Financial Modelling, Radon Series on Computational and Applied Mathematics |publisher=De Gruyter |pages=165–181|url=http://people.maths.ox.ac.uk/gilesm/files/jcf07.pdf}}</ref><ref>{{cite journal |last1=Robbe |first1=P. |last2=Nuyens |first2=D. |last3=Vandewalle |first3=S. |date=2017 |title=लॉगनॉर्मल डिफ्यूजन प्रॉब्लम के लिए एक मल्टी-इंडेक्स क्वैसी-मोंटे कार्लो एल्गोरिथम|journal=SIAM Journal on Scientific Computing |volume=39 |issue=5 |pages=A1811–C392|doi=10.1137/16M1082561 |arxiv=1608.03157 |bibcode=2017SJSC...39S.851R |s2cid=42818387 }}</ref>





Revision as of 11:50, 1 July 2023

संख्यात्मक विश्लेषण में बहुस्तरीय मोंटे कार्लो (एमएलएमसी) विधियाँ संयोजनात्मक अनुरूपण में उत्पन्न होने वाले अपेक्षित मूल्यों की गणना के लिए एक कलन विधि हैं। मोंटे कार्लो विधियों की तरह, बहुस्तरीय मोंटे कार्लो विधियाँ भी दोहरे प्रक्रिया आधारित यादृच्छिक प्रतिरूप चयन पर आधारित होती हैं, परंतु इन प्रतिरूपो को विभिन्न सत्यता स्तरों पर लिया जाता है। एमएलएमसी विधियाँ मुख्य रूप से मानक मोंटे कार्लो विधियों की गणना के गणितीय लागत को अत्यधिक कम कर सकती हैं, क्योंकि इसमें अधिकांश प्रतिरूपो को कम सत्यता और उसके संबंधित कम लागत के साथ लिया जाता है, और मात्र बहुत कम संख्या में प्रतिरूपो को उच्च सत्यता और उसके संबंधित उच्च लागत के साथ लिया जाता है।

लक्ष्य

बहुस्तरीय मोंटे कार्लो विधि का उद्देश्य एक प्रसंभाव्य अनुरूपण के आउटपुट होने वाले यादृच्छिक परिवर्तन की अपेक्षित मान का अनुमान लगाना है। यदि यह यादृच्छिक परिवर्तन सटीकता से अनुकारित नहीं किया जा सकता है, तब यहां एक अनुक्रमणिका होती है जो सुधारती सटीकता के साथ बढ़ती है, परंतु उसके साथ लागत भी बढ़ती है, जैसा कि और अभिसरण करता है बहुस्तरीय विधि का आधार दूरबीन योग समीकरण होता है।,[1]

यह अपेक्षा ऑपरेटर की रैखिकता के कारण आसानी से पूरा किया जा सकता है। इसके बाद हर अपेक्षा को मोंटे कार्लो विधि के द्वारा अनुमानित किया जाता है, जिससे बहुस्तरीय मोंटे कार्लो विधि प्राप्त होती है। ध्यान दें कि स्तर के का एक प्रतिरूप लेना और दोनों अनुरूपण की आवश्यकता होती है।

एमएलएमसी विधि केवल तभी काम करती है जब प्रसरण के रूप में होती है तब , हो सकती है यदि दोनों और एक ही यादृच्छिक परिवर्तन .को अनुमानित करते हैं। केंद्रीय सीमा सिद्धांत के अनुसार, यह इसका अर्थ है कि जैसे ही होता है, अंतर .की अपेक्षा को सटीकता से अनुमानित करने के लिए कम से कम प्रतिरूपों की आवश्यकता होती है।

इसलिए, अधिकांश प्रतिरूप स्तर , पर लिए जाएंगे, जहां प्रतिरूप सस्ते होते हैं, और केवल बहुत कम प्रतिरूप सबसे छोटे स्तर . पर आवश्यक होंगे। इस अर्थ में, एमएलएमसी को एक पुनरावर्ती नियंत्रण भिन्न रणनीति के रूप में माना जा सकता है।

अनुप्रयोग

सही

एमएलएमसी के पहले आवेदन का श्रेय माइक जाइल्स को दिया जाता है,[2] मोंटे कार्लो विकल्प प्रारूप के लिए प्रसंभाव्य अंतर समीकरण के संदर्भ में, यद्यपि, पैरामीट्रिक एकीकरण के संदर्भ में हेनरिक के काम में पहले के निशान मिलते हैं। [3]

यहाँ, यादृच्छिक परिवर्तन प्रतिफल फ़ंक्शन के रूप में जाना जाता है, और अनुमानों की श्रृंखला , समय सोपान के साथ प्रतिरूपों के पथ .के एक अनुमान का उपयोग करती है।

अनिश्चितता मापन में समस्याओं के लिए एमएलएमसी का अनुप्रयोग एक सक्रिय अनुसंधान क्षेत्र है।[4][5] इन समस्याओं का एक महत्वपूर्ण प्रोटोटाइपिकल उदाहरण पीडीई होते हैं। इस संदर्भ में, यादृच्छिक चर ये दर्शाता है कि रुचि की मात्रा, और अनुमानों की श्रृंखला पीडीई के ग्रिड आकारों के साथ एक अनुक्रमण को संबंधित करती है।

एमएलएमसी अनुकरण के लिए एक कलन-विधि

एमएलएमसी अनुरूपण के लिए एक सरल स्तर-अनुकूली कलन-विधि छद्म कोड में नीचे दिया गया है।

   repeat
    Take warm-up samples at level 
    Compute the sample variance on all levels 
    Define the optimal number of samples  on all levels 
    Take additional samples on each level  according to 
    if  then
        Test for convergence
    end
    if not converged then
        
    end
until converged

एमएलएमसी का विस्तार

बहुस्तरीय मोंटे कार्लो पद्धति के हाल के विस्तार में बहु सूचकांक मोंटे कार्लो सम्मिलित हैं,[6] जहां शोधन की एक से अधिक दिशाओं पर विचार किया जाता है, क्वासी-मोंटे कार्लो विधि को संगणना के साथ संयोजित किया जाता है।[7][8]


यह भी देखें

संदर्भ

  1. Giles, M. B. (2015). "बहुस्तरीय मोंटे कार्लो तरीके". Acta Numerica. 24: 259–328. arXiv:1304.5472. doi:10.1017/s096249291500001x. S2CID 13805654.
  2. Giles, M. B. (2008). "बहुस्तरीय मोंटे कार्लो पथ सिमुलेशन". Operations Research. 56 (3): 607–617. CiteSeerX 10.1.1.121.713. doi:10.1287/opre.1070.0496. S2CID 3000492.
  3. Heinrich, S. (2001). "बहुस्तरीय मोंटे कार्लो तरीके". Lecture Notes in Computer Science (Multigrid Methods). Lecture Notes in Computer Science. Springer. 2179: 58–67. doi:10.1007/3-540-45346-6_5. ISBN 978-3-540-43043-8.
  4. Cliffe, A.; Giles, M. B.; Scheichl, R.; Teckentrup, A. (2011). "बहुस्तरीय मोंटे कार्लो के तरीके और रैंडम गुणांक वाले अण्डाकार पीडीई के अनुप्रयोग" (PDF). Computing and Visualization in Science. 14 (1): 3–15. doi:10.1007/s00791-011-0160-x. S2CID 1687254.
  5. Pisaroni, M.; Nobile, F. B.; Leyland, P. (2017). "कंप्रेसिबल इनविसिड एरोडायनामिक्स में अनिश्चितता मात्रा के लिए एक निरंतरता बहु स्तरीय मोंटे कार्लो विधि" (PDF). Computer Methods in Applied Mechanics and Engineering. 326 (C): 20–50. doi:10.1016/j.cma.2017.07.030. S2CID 10379943. Archived from the original (PDF) on 2018-02-14.
  6. Haji-Ali, A. L.; Nobile, F.; Tempone, R. (2016). "Multi-Index Monte Carlo: When Sparsity Meets Sampling". Numerische Mathematik. 132 (4): 767–806. arXiv:1405.3757. doi:10.1007/s00211-015-0734-5. S2CID 253742676.
  7. Giles, M. B.; Waterhouse, B. (2009). "बहुस्तरीय अर्ध-मोंटे कार्लो पथ अनुकरण" (PDF). Advanced Financial Modelling, Radon Series on Computational and Applied Mathematics. De Gruyter: 165–181.
  8. Robbe, P.; Nuyens, D.; Vandewalle, S. (2017). "लॉगनॉर्मल डिफ्यूजन प्रॉब्लम के लिए एक मल्टी-इंडेक्स क्वैसी-मोंटे कार्लो एल्गोरिथम". SIAM Journal on Scientific Computing. 39 (5): A1811–C392. arXiv:1608.03157. Bibcode:2017SJSC...39S.851R. doi:10.1137/16M1082561. S2CID 42818387.